автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Акселератор планирования размещения задач в кластерных вычислительных системах высокой готовности

У

^ На правах рукописи

У У

** V 5

Аль-Мараят Бакер Ибрахим

Акселератор планирования размещения задач в кластерных вычислительных системах высокой готовности

05 13 05 - Элементы и устройства вычислительной техники и систем управления

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

ООЗ167572

Курск-2008

Работа выполнена в ГОУ ВПО «Курский государственный технический университет» на кафедре вычислительной техники в совместной научно-исследовательской лаборатории Центра информационных технологий в проектировании РАН и Курского государствен- -ного технического университета «Информационные распознающие телекоммуникационные интеллектуальные системы»

Научный руководитель

доктор технических наук, профессор Типикин Александр Петрович

официальные оппоненты

доктор технических наук, Бурмака Александр Александрович

Старший научный сотрудник

кандидат технических наук Тюпин Дмитрий Викторович

Защита диссертации состоится «12» мая 2008 г в 16 часов на заседании диссертационного совета Д212 105 02 при Курском государственном техническом университете по адресу 305040, г Курск, ул 50 лет Октября, 94 (конференц-зал) С диссертацией можно ознакомиться в библиотеке университета

Ведущая организация Тульский Государственный университет

Автореферат разослан «10» апреля 2008 г

Ученый секретарь совета по защите докторских и кандидатских диссертаций Д 212 105 02

Е А Титенко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Планирование оптимального размещения задач по множеству обрабатывающих процессоров - важный этап в процедурах подготовки комплекса взаимодействующих программ к параллельной обработке в мультикомпьютерах и кластерных системах Оно выполняется с целью минимизации величин коммуникационных задержек, обусловленных способом обмена данными между задачами в ходе их обработки путем передачи сообщений между процессорами Неудачное распределение задач между процессорами может привести к появлению длинных составных и перекрывающихся маршрутов транзитной передачи данных, возрастанию коммуникационных задержек и существенному снижению степени ускорения обработки, ожидаемой от распараллеливания

В связи с началом освоения отказоустойчивых мультикомпьютеров и кластеров высокой готовности повышаются требования к скорости выполнения процедур планирования размещения задач Быстрое восстановление правильности функционирования системы путем реконфигурации ее структуры с отключением неисправного процессора и заменой его резервным, расположенным обычно вне поля обрабатывающих процессоров, приводит к существенному изменению конфигурации связей между ними и образованию длинных и перекрывающихся маршрутов передачи данных Они могут быть уменьшены и разнесены путем оперативного переразмещения задач В то же время процедуры планирования размещения являются комбинаторными, имеют большую вычислительную сложность и поэтому могут привести к существенному увеличению времени восстановления и снижению коэффициента готовности системы Отказываться из-за этого от переразмещения задач перед рестартом восстанавливаемой системы нецелесообразно, так как возросшие коммуникационные задержки могут привести к такой потере системной производительности, которая превысит ожидаемый выигрыш от применения параллельной многопроцессорной обработки комплекса взаимодействующих программ Поэтому для уменьшения времени восстановления многопроцессорных кластерных систем необходимо многократно снизить затраты времени на планирование размещения задач Этого можно достичь путем создания специализированного ускоряющего вычислительного устройства (акселератора), а при разработке алгоритмов его функционирования целесообразно найти новый метод снижения вычислительной сложности процедур планирования размещения задач по процессорам матричных базовых блоков кластерных систем высокой готовности

В связи с вышеизложенным актуальной является научно-техническая задача многократного повышения скорости выполнения процедур планирования размещения параллельно обрабатываемых задач по процессорам кластерной системы путем реализации названных процедур в специализированном вычислительном устройстве

Объект исследования алгоритмы и технические средства реализации процедуры планирования размещения задач по процессорам кластерной вычислительной системы высокой готовности

Предмет исследования метод ускорения выполнения процедур планирования размещения задач в матричном базовом блоке кластерной системы, алгоритм функционирования и структурно-функциональная организация специализированного вычислительного устройства планирования размещения

Работа выполнена по плану инициативных НИР 2005-2007 г.г. кафедры вычисли-

тельной техники Курского государственного технического университета

Цель диссертации разработка метода ускорения составления плана субоптималь ного размещения задач по процессорам матричного базового блока кластерной системы алгоритма, структурной и функциональной схем специализированного вычислительног устройства планирования размещения, позволяющих многократно снизить затраты вре мени на планирование размещения и уменьшить время восстановления кластера

Задачи исследований

1 Анализ известных методов планирования субоптимального размещения задач п процессорам мультикомпьютеров и кластерных систем и способов построения акселера торов планирования размещения (АПР).

2 Разработка метода ускорения составления плана субоптимального размещени задач по сравнению с известными программными и аппаратными реализациями проце дуры планирования размещения

3 Разработка методики ускоренного программно-аппаратного выполнения проц дур планирования размещения задач по процессорам матричного базового блока кл стерных систем высокой готовности

4 Разработка алгоритма функционирования, структурной и функциональной схе специализированного вычислительного устройства планирования размещения задач матричном базовом блоке

5 Программное моделирование алгоритма функционирования АПР, оценка дост гаемого ускорения составления плана размещения задач и производительности АПР

Научная новизна результатов диссертации-

1 Разработан метод ускорения поиска субоптимального варианта размещения зад по процессорам, основанный на целенаправленных перестановках строк и столбцов ма рицы обмена информацией (МОИ) между задачами и мин-максном критерии оптимиз ции, отличающийся применением контроля степени уменьшения величин коммуникац онных задержек в ходе направленных перестановок и позволяющий снизить общее чи ло требуемых перестановок

2 Разработана методика укоренного программно-аппаратного выполнения проц дур планирования размещения задач в матричном базовом блоке кластерной систем отличающаяся тем, что в каждом шаге поиска на аппаратном уровне реализуется б строе вычисление максимального значения полученных величин задержек, а на пр граммном уровне акселератора - перестановка строк и столбцов МОИ, анализ отнош ния достигнутого мин-максного значения задержки к гипотетической минимально во можной ее величине, принятие решения о целесообразности продолжения поисковь перестановок, и позволившая в результате контроля достижения заданного порогово значения названного отношения отбрасывать большое число заключительных неэффе тивных перестановок и многократно повысить скорость поиска субоптимального вар анта размещения

3 Разработаны алгоритмы, структурные и функциональные схемы микропроце сорного акселератора планирования размещения с двухуровневой организацией, отл чающегося аппаратной реализацией нижнего уровня нахождения максимального знач ния коммуникационных задержек в виде пятиступенчатого конвейерного вычислител ного устройства, содержащего в том числе трехступенчатый матрично-конвейернь блок умножения и рекуррентный блок выделения максимума, и позволившего повыси

производительность по сравнению с программной реализацией на современных многоядерных процессорах

Достоверность результатов диссертационной работы обеспечивается корректным и обоснованным применением аппарата математической логики, положений и методов теории множеств, графов, теории вероятностей и математической статистики, теории проектирования ЭВМ, а также подтверждается имитационным моделированием с использованием зарегистрированных программных средств.

Практическая ценность результатов исследований-

1 В результате программного моделирования и статистических исследований алгоритма функционирования разработанного акселератора показано, что скорость составления плана субоптимального размещения задач по процессорам матричного базового блока кластерной системы может быть повышена в 10 раз по сравнению с программной реализацией разработанного алгоритма в управляющей машине кластера и в 100 раз по сравнению с известными алгоритмами, основанными на поиске субоптимального размещения методом ветвей и границ

2 Дня поддержки процедур принятия решений разработаны алгоритм вычисления на программном уровне гипотетической минимально возможной величины коммуникационной задержки, а также методика и устройство оперативной проверки качества размещения задач, позволяющие уменьшить потерю степени снижения коммуникационных задержек после маршрутизации

3 Разработанная методика ускоренной процедуры планирования размещения позволяет уменьшить коммуникационные задержки в базовых блоках кластерных систем в 1 5 4 раза Снижение этого выигрыша по сравнению с лучшими результатами, достигаемыми за счет больших затрат времени на поиск, не превышает 16 19%

На защиту выносится следующие научные результаты

1 Метод ускорения поиска субоптимального варианта размещения задач, основанный на мин-максном критерии оптимизации, отличающийся применением контроля степени уменьшения величин коммуникационных задержек в ходе направленных поисковых перестановок строк и столбцов матрицы обмена информацией между задачами и позволяющий снизить общее число требуемых перестановок

2 Методика ускоренного программно-аппаратного выполнения процедур планирования размещения задач по процессорам матричного базового блока кластерной системы, отличающаяся вынесением на аппаратный уровень акселератора вычислительно сложного этапа нахождения максимума задержек, образующихся в результате поисковой перестановки, а на программный уровень - выполнения очередной перестановки, выделения минимума из последовательности названных максимумов по результатам ряда перестановок, принятия решений о целесообразности инициализации поиска или о прекращении поиска и отбрасывании заключительных неэффективных перестановок, позволившая многократно повысить скорость поиска субоптимального варианта размещения

3 Алгоритм вычисления гипотетической минимально возможной величины коммуникационной задержки, основанный на допущении о тождественности топологий связей между размещаемыми задачами и связей между процессорами и позволивший определить требуемую для принятия решения пороговую величину кратности превышения достигаемого в процессе поиска мин-максного значения задержки над названной мини-

мально возможной ее величиной

4 Алгоритмы и структурно-функциональная организация двухуровневого микро процессорного акселератора планирования размещения задач, отличающегося аппарат ной реализацией нижнего уровня нахождения максимума коммуникационных задерже в виде пятиступенчатого конвейерного вычислительного устройства, содержащего в то числе трехступенчатый матрично-конвейерный блок умножения, и позволившего повы сить производительность по сравнению с программной реализацией на современны многоядерных процессорах

Практическое использование результатов работы. Основные научные результа ты и выводы диссертации внедрены в учебном процессе на кафедре вычислительно техники КурскГТУ при проведении занятий по дисциплинам «Организация ЭВМ и сис тем», «Теоретические основы организации многопроцессорных комплексов и систем» Апробация работы. Основные положения и результаты диссертации обсуждались получили положительную оценку на следующих конференциях и семинарах на седьмо Международном научно-практическом семинаре «Практика и перспективы развит партнерства в сфере высшей школы» (Известия ТРТУ-ДонНТУ, Таганрог, 2006), на VI Международной научно-практической конференции «Методы и алгоритмы прикладно математики в технике, медицине и экономике (Новочеркасск, 2007)

Публикации. Содержание диссертации опубликовано в 7 работах, среди которы имеется 1 статья в научных изданиях, входящих в перечень ВАК Минобрнауки РФ, оди патент РФ на изобретение и свидетельство о регистрации программы ЭВМ

Личный вклад соискателя. Все выносимые на защиту научные результаты получ ны соискателем лично В работах по теме диссертации, опубликованных в соавторств личный вклад соискателя определяется следующим образом: в [1,3] алгоритм и методик поиска размещения близкого к субоптимальному, в [1,4,5] принцип построения аппара ной части акселератора, в [2,6] критерий оценки качества размещения, в [7] методик тестирования программы

Структура и объем работы. Диссертация включает введение, четыре главы, з ключение, приложения и список литературы из 61 наименований Работа содержит 14 страниц текста (с учетом приложений) и поясняется 36 рисунками и 6 таблицами

Области возможного использования. Результаты диссертационной работы могу быть использованы в кластерных системах высокой готовности, например, в случае о каза одного из процессорных модулей, когда необходимо оперативное переразмещени задач Применение разработанного акселератора позволит дополнительно снизить затр ты времени на планирование размещения задач и организовать оперативное переразм щение задач перед рестартом восстанавливаемой системы без существенного снижени ее коэффициента готовности, а также уменьшить сложность алгоритмов последующе маршрутизации параллельной передачи сообщений в матричных многопроцессорны системах

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность, сформулированы цель и задачи исследования, перечислены результаты, выносимые на защиту, отмечена их научная новизна и практическая ценность

В первой главе выполнен анализ известных методов и алгоритмов планирования размещения задач в кластерных вычислительных системах, проводится обзор современных кластерных систем, дана их краткая характеристика, рассмотрены известные методы определения коммуникационной задержки При высокой загрузке кластерной системы задачи, между которыми передаются большие объемы данных, должны быть по возможности назначены на соседние процессоры, а обмены информацией между отдельными кластерными блоками необходимо минимизировать Одним из факторов, сдерживающим рост производительности современных мультикомпьютеров и кластерных систем, является большая коммуникационная задержка. Методом ее снижения является планирование размещения задач На содержательном уровне задача размещения может быть представлена как выбор такого варианта распределения задач между модулями параллельной системы (ПС), которому соответствует минимальное время выполнения комплекса взаимодействующих задач в целом

Известные методы планирования размещения задач обладают большим временем поиска за счет большого числа вариантов перебора и решают эту задачу в основном программным путем Для кластерных систем высокой готовности это является неприемлемым, что приводит к необходимости применения аппаратных средств. В тоже время существующие аппаратные средства поиска субоптимального варианта размещения имеют узкую специализацию и обладают большой прогнозируемой аппаратной сложностью В связи с этим целесообразно разработать такую структурно-функциональную организацию специализированного ускоряющего вычислительного устройства (акселератора), которая была бы основана на типовых БИС микропроцессорных систем и в которой увеличение размера матричной топологии ПС приводило бы к лишь к увеличению требуемой емкости модулей оперативной памяти Так как алгоритм функционирования данного узко специализированного акселератора составляется в строгом соответствии с процедурой планирования размещения задач, многократное ускорение ее выполнения аппаратными средствами в данной работе достигается прежде всего за счет снижения вычислительной сложности самой реализуемой процедуры

Во второй главе поставлена задача уменьшения коммуникационной задержки в кластерных вычислительных системах путем субоптимального размещения комплекса взаимодействующих параллельно обрабатываемых программ по процессорам системы, формализована задача размещения и разработан метод ускорения поиска субоптимального варианта размещения Ускоренная процедура размещения комплекса взаимосвязанных задач разработана на примере 64-хпроцессорного матричного базового блока кластерной системы МВС-1000М

Размещение задач в кластерной системе выполняется за два этапа вначале - предварительное распределение подмножеств задач между кластерными базовыми блоками для минимизации трафика коммутационной среды Муппе^ а затем - локальное размещение каждого из подмножеств задач, позволяющее снизить коммуникационную задержку при обмене данными между задачами внутри каждого базового кластерного блока Для этого необходимо найти такой способ распределения задач между процессорами базового кластер-

ного блока, который минимизирует топологические расстояния между подзадачами, обменивающимися большими объемами информации

Разработанный метод ускорения поиска субоптимального варианта размещения задач по процессорам базового матричного кластерного блока основан на следующем подходе

Пакет взаимодействующих программ (задач), запланированных к обработке в базовом блоке, описывается графом взаимодействия задач

С=<Х,Е>, где

-"11 2 X 1 я

хи хгг хгп

•V

х„г хпл

(1)

множество вершин графа в, вершины Хф е X которого соответствуют задачам, а дуг связей между ними ече£ при г, у = (д -1) п + к взвешиваются объемами данных тц передаваемыми между задачами и сведенными в матрицу обмена информацией (МОИ

НК1*„'ГдеЛГ="Ч4

Матричный базовый блок кластерной системы представляется топологической мо

Ад Р\, 2 Р\,п

делью в виде графа Н=<Р,У>, где р = . Рг,\ Р2,2 Р2,п . - множество идентификато

Рп,1 Рп, 2 Рп,п

ров процессорных модулей базового блока, организованных в матрицу |Р]0хп, гд \р\ = И = г? - число процессорных модулей базового блока, V- множество межмодуль ных связей, задаваемых матрицей смежности ||^|Л,хЛ, размером п

х п

Размещение пакета программ (задач), описываемых графом О (1), в параллельно системе (ПС) может быть аналитически описано отображением

(2

где $ = 1,ЛП, к = 1,п, <7 = 1,и

Здесь 5 - это номер очередной перестановки задач по процессорным модуля соответствующий «-му варианту размещения Мощность множества ц/ = {Д5 всевозможных отображений (2) равна числу всевозможных перестановок задач {хдк} матрице X |у/( = /V" Для описания множества длин кратчайших маршрутов передач

1 Х*12 ДД Р1,2 Р1,к Р\,п

2 йд Р2,2 Р2,к Р2,п

Л = хз 1 ■VI \к ЛЧ п Рч. 2 Рч,к Рч,п

хз , п 2 5и и . /V Рп,2 Рп,к Рп.п

данных в пределах базового блока введем матрицу минимальных расстояний (ММР) D=||d4üNxN, N = п2 = \Р\, которая строится по матрице смежности

Задачу планирования размещения, можно сформулировать как поиск такого отображения ß'e1?, что

V =Т{аЫТа (Ра'ь'Рх>у^\ (3)

где Tßs (ра:ь,рх,у) ~ коммуникационная задержка при передаче данных между процессорными модулями ра Ь и рх у, соответствующая отображению ßs и вычисляемая как произведение

Tß,{Pa,b>Px,y) = d,j Щ] С, (4)

где г = (а-1) п + Ь И у = (х-\) п + у,

3 {ра,Ь>Рх,у)} = тахЦт,у} (5)

Присутствующий в (4) сомножитель С не учитывается в выражениях (3,5) и последующем анализе, так как он обратно пропорционален постоянной скорости передачи данных и поэтому не влияет на результаты минимизации по (3)

Поиск наилучшего варианта размещения ß* по критерию (3) является сложной переборной задачей Одним из путей его ускорения может быть применение целенаправленных перестановок строк и столбцов матрицы МОИ с выбором в ней ак-го места перестановки ее элемента maß по критерию

dak < d,,ß> (6)

где dak, daß - одноименные элементы матрицы ММР; maß - элемент МОИ, которому соответствует тах^тц j, найденный в предыдущем шаге перестановок

Новизна подхода состоит в том, что общее число требуемых перестановок можно дополнительно уменьшить, если отбросить явно нецелесообразные из них, разрешая очередную перестановку по следующим дополнительным критериям

так dak<maß daß, (7)

™ак < maß (8)

Многократное ускорение поиска возможно за счет допустимого снижения выигрыша на снижение величины коммуникационной задержки, например, не более, чем на 2030%, по сравнению с лучшими результатами, достигаемыми при больших затратах времени на поиск Дня этого необходимо в ходе поиска контролировать степень уменьшения величины образующейся коммуникационной задержки (3) и принимать решение о целесообразности продолжения поисковых перестановок строк и столбцов матрицы МОИ Процедура принятия решения основана на вычислении недостижимой минимальной оценки размещения T,„f (гипотетического минимума коммуникационной задержки) при допущении, что топологии графов G и Н тождественны При вычислении нижней оценки будем назначать дуги графа G с наибольшим весом mv на самые короткие маршруты в графе Н, не обращая внимания на ограничения, накладываемые фактическими связями между задачами в графе G Соответствующий формализованный алгоритм вы-

глядит следующим образом

1 Переписать элементы du матрицы D в вектор-строку D'=|d^| так, что

d^ < d^. <=> z, > z2, где zt и z2 - порядковые номера элементов в D'

2 Переписать элементы матрицы М в вектор-строку М'=Щ*|| так, что rnz' > т** о z, > z2, где Z[ и Z2 — порядковые номера элементов в М'

3 Положить

где z = 1,|£|, а ¡£|- мощность множества Е, равная количеству дуг в графе G, m2. d' - одноименные элементы векторов М' и D' с одинаковыми порядковыми номерами от начала названных выше вектор-строк

Для многократного ускорения поиска разработана следующая методика ускоренного выполнения процедур планирования размещения задач

1 Составляются две матрицы обмена информацией между задачами (МОИ) и кратчайших маршрутов (ММР) между процессорами в коммуникационной среде базового блока

2 Вычисляются гипотетический минимум коммуникационной задержки T,nf и коэффициент эффективности исходного произвольного размещения задач 7,, =TH/T,„f

3 По порогу эффективности пн > 2 принимается решение о целесообразности инициализации процедуры поиска субоптимального размещения Под коэффициентом эффективности перестановок r/-T/Tmf понимается отношение реально полученной величины задержки (5) к гипотетической rmf

4 Выполняются шаги целенаправленных перестановок столбцов и строк матрицы обмена информацией Находится максимальное значение коммуникационной задержки (5) по предыдущему варианту перестановок задач

5 Находится минимум (3) из максимумов задержек по всем вариантам перестановок и вычисляется коэффициент эффективности /7

6 Если 77 оказывается менее установленного порога эффективности tj< 2, шаги поиска прекращаются и найденный вариант матрицы обмена информацией считается соответствующим субоптимальному размещению

Величина порога эффективности г)п-2, выбрана в результате статических исследований на программной модели алгоритма функционирования АПР

На основании разработанных в данной главе метода ускорения поиска и методики ускорения выполнения процедур планирования размещения составлен следующий алгоритм, программно-аппаратно реализованный в двухуровневом микропроцессорном акселераторе

1 Ввести м=|К||№д,, o=|K!L> "»-KL«' WHKS„„»> ^HKIL' Vm,j=0, Vml(J=0, Vm24=0, Vm3,j=0

2 Переписать Уту в М~

—г ГПу

с изменением порядка следования элементов так, что

т2^ > т^ о г! < г2, где гх и г2 порядковые номера элементов М 3 Переписать в /)=|Ь^|| с изменением порядка следования элементов так, что

^ <г2, где г\ и гг порядковые номера элементов В

4 Положить Г1пГ = тах{т2ё2}, где г = 1,|£|, N

5 Найти г„=тах{т,у 4,},./ =ЦУ. где И-число задач

6 Вычислить „ = 1к_ Если ?7 < Т]п, то останов, иначе перейти к п 7

7 Принять Т0=ТН

8 Выполнить М1=М Щ,]) => Л/2,, = М4 9. Принять к=1

10 Выбрать тк из М

11. Найти т2аР из М2 такой, что т2ае = тк, и - соответствующий ему из Б

12. Если ¿/^ =/, то М2а/) = -1, к=к+1 и перейти к п 10, иначе п.13,

13 Принять 1=1

14 Если I < 64, то перейти к п 15, иначе - п 25

15 Если Ыа, < 5 и <4, Ф 0 и тар йар > тт (1а, и тар йар > тт (1а0, т0 перейти к п 16, иначе г=г+1 и-п 14

16 Для м выполнить операцию ; <н>- р и сформировать М1 V«/,., *!>&(/,./* Р)) М\ = , У((1 = ;)&0 * Д)) =>М1„ = АГЛ, V«/ = /?)&(_,*I)) ОМ1/у = Ми, V((/*г)&0 = /?)) = Л/,, V«/ * /?) & (у = 0) => ¿А; = , Щ, = , = Л/„

17 Вычислить Т, = тах|»гй Если Т\ ^ ?о> то перейти к п 18, иначе ; = г +1 и-п 14

Т

18 Вычислить г] = -а- Если Т] <Т]п,то останов и выдача М1, иначе перейти к п 19

19 Принять М = Л/1 У(/,у) => Мь = М1)у

20 Принять Т0=Т1

21 Принять М2ар = -1

22. Для А/2 выполнить операцию г р и сформировать МЗ

у((/, 7 * о & (/^ */?))=> ш4 =ш,у, м\ = мгя,

Щ1 = Р) 0) => М3,у = М2у, у((/ *1)&и = р))=> м\ = А/2,,, V«/ * /?) & (у = 0) => = МЗф = Л/2^, МЗ^ = М2(/)

23 Принять М2 = МЗ =5. М1,1 = М3;/

24 Принять к-к+1 и перейти к п.26.

25. М2ар = -ь к=к+1.

26. Если к<Щ, то останов и выдача М1, иначе перейти к п.9

В третьей главе описаны программная модель разработанного алгоритма планиро вания размещения задач и результаты статистических исследований его эффективности.

Для моделирования и тестирования разработанного метода планирования размеще ния задач в кластерных системах была разработана на языке Си++ программная систем^ которая позволяет программно реализовать алгоритм размещения, строить графики и^

менения показателей эффективности „ = Л и а=[н_ при каждой пробной перестановке и \

Ты т I

заданной точностью фиксировать время расчета.

Целью исследования было определение величины выигрыша сг в снижении задер»! ки в результате применения разработанного метода при разных видах и степенях запод нения МОИ, соответствующих широкому диапазону изменения степени связности мел ду задачами пакета программ, запланированных к обработке в базовом матричном блс ке. Результаты, соответствующие матрице наилучшего размещения МК, начальному достигнутому отклонению задержки Т от Т.^: и /? соответственно, достигнутому вь! игрышу а в разах, а так же времени, затраченному на поиск, выводятся на экран.

В результате вычислительного эксперимента на ЭВМ получены зависимости пок; зателей а от 7И (рис. 1) и г/ от О (Рис. 2).

На рисунке 1 приняты следующи^

обозначения: график 1 - матрица МОИ заполнена так, что отношение элементов

Рис. 1. Графики зависимости <х от г/н

- = -Ь график 10

- матрица МОИ заполнена так, чт< отношение элементов -^в- = -;

"'та* 5

график 3 - матрица МОИ заполнена так, что отношение элементов ^^- = ~; график 4 - матрица

МОИ заполнена так, что отноше-1

ние элементов —1я- = -.

т„„ 3

Рис. 2. Графики зависимости г] от количества последовательных перестановок 0: а) только по критерию (6); б) по комплексу критериев (6-8). Из приведенных графиков (Рис. 1,2) следует:

1) если т}И <2, выигрыш в снижении величины задержки составляет всего <7 = 1,3...'

раза;

2) в связи с необходимостью выполнения избыточного количества перестановок большая часть которых приходится на заключительную часть процедуры поиска, когд

значение г/ перестает существенно снижаться (рис 2), целесообразно вести порог 7?„ эффективности перестановок, который отсекал бы эти избыточные перестановки по неравенству Г1<Т}а

Величина порога т]п = 2, необходимая для многократного ускорения поиска в соответствии с описанной выше методикой ускоренного выполнения процедур планирования размещения, найдена в результате определения на программной модели зависимости числа необходимых перестановок (5 и степени снижения коммуникационной задержки сг от относительной величины начальной задержки ?/„ (табл 1)

Таблица 1

3 4 5 6 7 8

При пороге 1}„= 18 Сдоп критериями 0 7004 4080 6167 4813 5204 3901

сг 1,71 2,27 2,84 3,41 3,98 4,54

Без доп критериев 0 8017 4406 5976 4985 4811 4050

а 1,7 2,27 2,84 3,41 3,98 4,54

При пороге ПЙ = 2 С доп критериями <? 159 714 556 378 186 708

О 1,5 2 2,50 3,00 3,64 4,17

Без доп критериев 0 137 732 577 390 205 723

а 1,5 2 2,50 3,00 3,64 4,17

Без порога Сдоп критериями 0 51884 51468 51334 51370 50544 51322

а 1,78 2,47 2,98 3,70 4,17 4,94

V 1,68 1,62 1,68 1,62 1,68 1,62

Без доп критериев 0 102488 102386 102666 103523 101817 102022

а 1,78 2,38 2,98 3,57 4,17 4,94

П 1,68 1,68 1,68 1,68 1,68 1,62

Из таблицы 1 и рис 1,2 можно сделать следующие выводы Приемлемым вариантом организации поиска субоптимального размещения является использование при принятии решения величины порога Г]а = 2 Кроме того, использование описанных выше критериев позволяет значительно сократить время поиска до О =160 700 перестановок и при этом обеспечивать степень снижения величины задержки в 1,5 4 раза (табл 1) Причем снижение выигрыша в величине а по сравнению с наилучшими результатами, полученными при больших затратах времени на поиск без использования разработанной во второй главе методики ускоренного выполнения процедур планирования (без порога, табл 1), не превышает 16-19%

Достигнутая при этом величина ускорения выполнения процедур планирования размещения задач, установленная в результате статистических исследований на модели в широком диапазоне изменения степени связности между задачами, запланированными к обработке в базовом кластерном блоке, составляет 100 раз по сравнению с известным методом ветвей и границ

В четвертой главе приведено описание алгоритмов функционирования, структурных и функциональных схем микропроцессорного акселератора планирования размещения (АПР) (рис 3) с двухуровневой организацией, разработанных на основании описанных выше теоретических результатов и алгоритма планирования размещения задач

Рис 3. Акселератор планирования размещения задач На рис 3 приняты следующие обозначения. МП - микропроцессор, ОП - оператив ная память, КДЦП- контроллер прямого доступа в память, Прпорт - параллельный порт Ппорт - последовательный порт, DMX - демультиплексор, БУМК - блок умножени матрично-конвейерный, МАХ - блок сравнения и нахождения максимума, УУ - устрой ство управления, АВПКЗ - акселератор вычисления показателя коммуникационной за держки, УПКР - устройство проверки качества размещения

Самую частую операцию вычисления максимальной коммуникационной задержг предполагается выполнять в аппаратном ускорителе акселераторе вычисления показа теля коммуникационной задержки (АВПКЗ) Блок АВПКЗ отличается тем, что в нем применены конвейерный и матричный подходы для поэлементного перемножения век торов с одновременным подсчетом максимального произведения В составе АВПК можно выделить шесть основных функциональных блоков (Рис 3,4) Данные с парал лельного порта поступают в блок специализированного демультиплексора (DMX) В за висимости от режима работы DMX загружает одно из ОЗУ данными соответствующей разрядности Если идет загрузка в ОЗУ2, из 8-ми разрядного порта за один цикл прием MUX принимает два 4-х разрядных слова Если же идет загрузка в ОЗУь то MUX при нимает два байта 16-ти разрядного слова и после их склеивания помещает целое слово в ОЗУ1 Блок умножения матричной-конвейерный (БУМК) осуществляет перемножени синхронно считанных из ОЗУ! и ОЗУ2 двух слов и выдает результат в блок нахождения максимума (МАХ) Умножение происходит конвейерно за один такт Блок МАХ находит максимум и по сигналу об окончании расчета выдает результат за три цикла вывод в порт контроллера Устройство управления (УУ) выдает управляющие сигналы, обозначенные на рис 3 как множество микроопераций (МО), а также значения адресов для ОЗУ1 и ОЗУ2 в режимах загрузки и вычисления

Рис 4 Функциональная схема акселератора вычисления показателя коммуникационной задержки Кроме этого разработаны методика и устройство проверки качества размещения задач (Положительное решение на выдачу патента РФ по заявке №2007100634/09 (000664)), позволяющие уменьшить возможные потери в степени снижения коммуникационных задержек после маршрутизации Названные потери могут образоваться при недостаточном качестве размещения в результате возможного наложения (перекрытия) в каналах связи между соседними процессорами нескольких маршрутов, организующих параллельную передачу данных между несколькими задачами в пределах многопроцессорного кластерного блока Если до маршрутизации выполнить субоптимальное размещение задач разработанным в диссертации методом, то качество полученного варианта размещения будет высоким, так как все связанные задачи будут чаще всего размещены максимально близко друг к другу в соседних процессорах, а последующая маршрутизация по наиболее коротким маршрутам не приведет к их перекрытию Разработанное устройство проверки качества размещения позволяет сравнивать качество вариантов размещения задач и инициализировать продолжение приостановленного поиска новых вариантов размещения до нахождении варианта, обладающего наилучшим качеством

Разработанный акселератор отличается применением двухуровневой конвейерной обработки На верхнем уровне организован двухступенчатый программно-аппаратный конвейер с совмещением во времени двух этапов каждого цикла обработки 1) вычисление в контроллере оценок и принятие решения по результатам предыдущего шага пере-

становок строк и столбцов МОИ, выполнение следующего шага перестановок, 2) вычи ление на нижнем аппаратном уровне в АВПКЗ показателя коммуникационной задерж соответствующего следующему шагу перестановок Блок АВПКЗ на нижнем уров (Рис 4) представляет собой пятиступенчатый конвейер Это позволило уменьшить затр ты времени на выполнение процедуры планирования размещения комплекса задач в 6 процессорном базовом кластерном блоке до 6 6 105 2 99 106 тактов работы акселер тора по сравнению с 7 106 3 107 тактов работы управляющей ЭВМ кластерной сист мы, требующимися в соответствии с результатами моделирования при программн реализации разработанного в данной диссертации алгоритма, и тем самым повыси производительность примерно в 10 раз

В заключении сформулированы основные результаты диссертации В приложениях представлен пакет программ моделирования процедур планиров ния размещения задач в матричных базовых кластерных блоках, описание программн части, реализованной в контроллере акселератора, функциональная схема конвейерез рованного блока умножения, а также справки о внедрении результатов исследований предприятиях и в учебном процессе.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

В диссертации решена актуальная научно-техническая задача многократного пов шения скорости выполнения процедуры планирования размещения комплекса взаим связанных задач по процессорам базового блока кластерной системы путем аппарата реализации названной процедуры и усовершенствования метода поиска субоптимальн го варианта размещения Получены следующие основные результаты

1 Разработан метод ускорения поиска субоптимального варианта размещения з дач по процессорам, основанный на целенаправленных перестановках строк и столбц матрицы обмена информации (МОИ) между задачами и мин-максном критерии оптим зации, отличающийся применением контроля степени уменьшения величин коммуник ционных задержек в ходе направленных перестановок и позволяющий снизить общ число перестановок, требуемых для минимизации коммуникационных задержек

2. Разработана методика укоренного программно-аппаратного выполнения проц дур планирования размещения задач в матричном базовом блоке кластерной систем отличающаяся тем, что в каждом шаге поиска на аппаратном уровне реализуется б строе вычисление максимального значения полученных величин задержек, а на пр граммном уровне акселератора - перестановка строк и столбцов МОИ, анализ отнош ния достигнутого мин-максного значения задержек к гипотетической минимально во можной ее величине, принятие решения о целесообразности продолжения поисковь перестановок, и позволившая в результате контроля достижения заданного порогово значения названного отношения отбрасывать большое число заключительных неэффе тивных перестановок и многократно повысить скорость поиска субоптимального вар анта размещения

3 Разработаны алгоритмы, структурные и функциональные схемы микропроце сорного акселератора планирования размещения с двухуровневой организацией, отл чающегося аппаратной реализацией нижнего уровня нахождения максимального знач ния коммуникационных задержек в виде пятиступенчатого конвейерного вычислител ного устройства, содержащего в том числе трехступенчатый матрично-конвейернь

блок умножения и рекуррентный блок выделения максимума, и позволившего повысить производительность по сравнению с программной реализацией на современных многоядерных процессорах

4 Для поддержки процедур принятия решений разработаны алгоритм вычисления на программном уровне гипотетической минимально возможной величины коммуникационной задержки, а также методика и устройство оперативной проверки качества размещения задач, позволяющие уменьшить потери степени снижения коммуникационных задержек после маршрутизации

5 В результате программного моделирования и статистических исследований на модели алгоритма функционирования разработанного акселератора показано, что скорость составления плана субоптимального размещения задач по процессорам матричного базового блока кластерной системы может быть повышена в 10 раз по сравнению с программной реализацией этого же алгоритма в управляющей машине кластера и в 100 раз по сравнению с известными алгоритмами, основанными на поиске субоптимального размещения методом ветвей и границ Коммуникационные задержки в базовых блоках кластерных систем уменьшаются в 1 5 4 раза Снижение этого выигрыша по сравнению с лучшими результатами, достигаемыми за счет больших затрат времени на поиск, не превышает 16 19%

6 Разработаны пакет программ моделирования на ЭВМ процедуры планирования размещения задач в матричном базовом кластерном блоке, позволивший оценить производительность акселератора, а также программа микропроцессорного контроллера, реализующая верхний уровень конвейерного вычислительного процесса акселератора

Результаты исследований являются необходимыми предпосылками к применению оперативного переразмещения задач по процессорам перед рестартом восстанавливаемой вычислительной системы без существенного снижения коэффициента ее готовности и с сохранением запланированной степени ускорения параллельной обработки комплекса взаимосвязанных программ

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи, в научных изданиях, входящих в перечень ВАК Министерства образования и науки РФ

1 Мараят Б И Акселератор планирования размещения задач в кластерных вычислительных системах высокой готовности [Текст] / Б.И Мараят, ДБ Борзов, АП Типикин // Известия вузов Приборостроение, 2008, №2, С 29-33

Патент

2 Мараят Б И Устройство оценки качества размещения в системах с матричной организацией [Текст] / Б И Мараят, Д Б Борзов, Т А Заикина, M X Наджаджра // Положительное решение на выдачу патента РФ по заявке №2007100634/09(000664))

'Депонированные рукописи

3 Мараят Б И Методика планирования размещения задач в матрично-торроидальных базовых блоках кластерных мультикомпьютеров [Текст] / Б.И Мараят, Д Б Борзов // Деп в ВИНИТИ 18 07 06 г, №961-В 2006

4 Мараят Б И Алгоритмы и принцип организации аппаратных средств ускорения составления плана размещения задач в кластерных мультикомпьютерах [Текст] / Б И Мараят, Д Б Борзов, А П Типикин // Деп в ВИНИТИ 25.10.07 г, №998-В 2007

Материалы конференций

5 Мараят Б И Устройства планирования размещения задач в матричных системах [Текст] / Б И Аль-Мараят, Д Б Борзов // Практика и перспективы развития партнерства в сфере высшей школы материалы седьмого Международного научно-практического семинара - Известия ТРТУ-ДонНТУ В 3-х книгах Таганрог Изд-во ТРТУ Кн 1 2006, №6.-С 57-63

6 Мараят Б И Устройство оценки качества размещения в системах с матричной организацией [Текст] / Б И Мараят, Д Б Борзов, M И Гладилина // Материалы VII Международной научно-практической конференции «Методы и алгоритмы прикладной математики в технике, медицине и экономике. Часть 1», - Новочеркасск, 2007 - С 66-69

Свидетельство о регистрации программы для ЭВМ

7 Свидетельство о регистрации программы для ЭВМ №2008610132 Метод перестановки строк и столбцов в матрице обмена информацией для планирования размещения задач в матричных базовых блоках кластерных систем [Текст] / Б И Аль-Мараят, ДБ Борзов, А С Масалов // свидетельство о гос рег прог на ЭВМ, 9 01 2008

О

Соискатель \ Б И Аль-Мараят

/

одписано в печать 7 2008 Формат 60x84 1/16

еч л 1_0 Тираж 100 экз Заказ 9

урекий государственный технический университет

здательско-полиграфический центр

урского государственного технического университета

05040, г Курск, ул 50 лет Октября, 94

Введение.

1. Анализ известных методов и алгоритмов планирования размещения задач в кластерных вычислительных системах.

1.1. Коммуникационные задержки в кластерных системах.

1.2. Понятие о размещении задач по процессорам параллельной системы.

1.3. Связь между топологиями вычислительных систем и методами размещения задач.

1.4. Классификация методов размещения.

1.5. Анализ алгоритмов размещения задач и целесообразность их аппаратной реализации.

1.6. Выводы.

2. Метод планирования размещения задач в кластерных вычислительных системах.

2.1. Постановка задачи минимизации коммуникационной задержки в кластерных вычислительных системах.

2.2. Формализованная постановка задачи размещения в кластерных вычислительных системах.

2.3. Метод минимизации коммуникационных задержек в матричных базовых кластерных блоках.

2.3.1. Постановка задачи.

2.3.2. Поиск гипотетической нижней оценки величины коммуникационной задержки.

2.4. Алгоритм планирования размещения задач в кластерных вычислительных системах.

2.4.1. Этапы поиска решения.

2.4.2. Операция парной перестановки столбцов и строк матрицы обмена инф ормации.

2.5. Перестановочный алгоритм планирования размещения задач.

2.6. Метод ускорения сходимости алгоритма.

2.7. Ускоренный алгоритм планирования размещения задач.

2.8. Методика ускоренного выполнения процедуры планирования размещения задач.

2.9. Выводы.

3. Моделирование процедур планирования размещения задач в кластерных системах.

3.1. Описание программной модели процедур планирования.

3.2. Методы моделирования.

3.3. Результаты исследования на модели эффективности алгоритма планирования размещения.

3.4. Выводы.

4. Организация двухуровневого микропроцессорного акселератора планирования размещения задач.

4.1. Принципы аппаратной реализации процедур планирования размещения.

4.2. Двухуровневая структурная организация микропроцессорного акселератора планирования размещения задач.

4.3. Алгоритмы функционирования акселератора.

4.4. Производительность акселератора и функциональные схемы узлов его нижнего уровня.

4.5. Методика и быстродействующее устройство проверки качества размещения задач.

4.6. Выводы.

Планирование оптимального размещения задач по множеству обрабатывающих процессоров - важный этап в процедурах подготовки комплекса взаимодействующих программ к параллельной обработке в мультикомпьютерах и кластерных системах. Оно выполняется с целью минимизации величин коммуникационных задержек, обусловленных способом обмена данными между задачами в ходе их обработки путем передачи сообщений между процессорами. Неудачное распределение задач между процессорами может привести к появлению длинных составных и перекрывающихся маршрутов транзитной передачи данных, возрастанию коммуникационных задержек и существенному снижению степени ускорения обработки, ожидаемой от распараллеливания.

В связи с началом освоения отказоустойчивых мультикомпьютеров и кластеров высокой готовности повышаются требования к скорости выполнения процедур планирования размещения задач. Быстрое восстановление правильности функционирования' системы путем реконфигурации ее структуры с отключением неисправного процессора и заменой его резервным, расположенным обычно вне поля обрабатывающих процессоров, приводит к существенному изменению конфигурации связей между ними и образованию длинных и перекрывающихся маршрутов передачи данных. Они могут быть уменьшены и разнесены путем оперативного переразмещения задач. В то же время процедуры планирования размещения являются комбинаторными, имеют большую вычислительную сложность и поэтому могут привести к существенному увеличению времени восстановления и снижению коэффициента готовности системы. Отказываться из-за этого от переразмещения задач перед рестартом восстанавливаемой системы нецелесообразно, так как возросшие коммуникационные задержки могут привести к такой потере системной производительности, которая превысит ожидаемый выигрыш от применения параллельной многопроцессорной обработки комплекса взаимодействующих программ. Поэтому для уменьшения времени восстановления многопроцессорных кластерных систем необходимо многократно снизить затраты времени на планирование размещения задач по сравнению с его программной реализацией в управляющей машине кластера: Этого можно достичь путем создания специализированного ускоряющего вычислительного устройства (акселератора), а при разработке алгоритмов его функционирования целесообразно найти новый метод снижения вычислительной сложности процедур планирования размещения задач по процессорам матричных базовых блоков кластерных систем высокой готовности.

В связи с вышеизложенным актуальной является научно-техническая задача многократного повышения скорости выполнения процедур планирования размещения параллельно обрабатываемых задач по процессорам кластерной системы путем реализации названных процедур в специализированном вычислительном устройстве.

Объект исследования: алгоритмы и технические средства реализации процедуры планирования размещения задач по процессорам кластерной вычислительной системы высокой готовности.

Предмет исследования: метод ускорения выполнения процедур планирования размещения задач в матричном базовом блоке кластерной системы, алгоритм функционирования и структурно-функциональная организация специализированного вычислительного устройства планирования размещения.

Цель работы: разработка метода ускорения составления плана субоптимального размещения задач по процессорам матричного базового блока кластерной системы, алгоритма, структурной и функциональной схем специализированного вычислительного устройства планирования размещения, позволяющих многократно снизить затраты времени на планирование размещения и уменьшить время восстановления кластера.

Для достижения поставленной цели решены следующие задачи.

4.6. Выводы

1. Разработаны алгоритмы, структурные и- функциональные схемы микропроцессорного акселератора планирования размещения с двухуровневой организацией.

2. Нижний аппаратный уровень акселератора целесообразно реализовать в виде пятиступенчатого конвейерного вычислительного устройства, содержащего трехступенчатый матрично-конвейерный блок умножения и рекуррентный блок выделения максимума и позволяющего многократно ускорить составление плана субоптимального размещения задач.

3. Производительность акселератора может быть существенно повышена путем аппаратной реализации- вычисления показателя коммуникационной задержки и двухуровневой конвейерной организации вычислительного процесса планирования размещения, содержащего двухступенчатый программно-аппаратный конвейер верхнего уровня и пятиступенчатый конвейер нижнего аппаратного уровня.

4. Разработаны методика и быстродействующее устройство оперативной проверки качества размещения задач, позволяющие уменьшить вероятность возникновения потерь в степени снижения коммуникационных задержек в результате последующей маршрутизации.

Заключение

В диссертации решена актуальная научно-техническая задача многократного повышения скорости выполнения процедуры планирования размещения комплекса взаимосвязанных задач по процессорам базового блока кластерной системы путем аппаратной реализации названной процедуры и усовершенствования метода поиска субоптимального варианта размещения. Получены следующие основные результаты.

1. Разработан метод ускорения поиска субоптимального варианта размещения задач по процессорам, основанный на целенаправленных перестановках строк и столбцов матрицы обмена информации (МОИ) между задачами и мин-максном критерии оптимизации, отличающийся применением контроля степени уменьшения величин коммуникационных задержек в ходе направленных перестановок и позволяющий снизить общее число перестановок, требуемых для минимизации коммуникационных задержек.

2. Разработана методика укоренного программно-аппаратного выполнения процедур планирования размещения задач в матричном базовом блоке кластерной системы, отличающаяся тем, что в каждом шаге поиска на аппаратном уровне реализуется быстрое вычисление максимального значения полученных величин задержек, а на программном уровне акселератора - перестановка строк и столбцов МОИ, анализ отношения достигнутого мин-максного значения задержек к гипотетической минимально возможной ее величине, принятие решения о целесообразности продолжения поисковых перестановок, и позволившая в результате контроля достижения заданного порогового значения названного отношения отбрасывать большое число заключительных неэффективных перестановок и многократно повысить скорость поиска субоптимального варианта размещения.

3. Разработаны алгоритмы, структурные и функциональные схемы микропроцессорного акселератора планирования размещения с двухуровневой организацией, отличающегося аппаратной реализацией нижнего уровня нахождения максимального значения коммуникационных задержек в виде пятиступенчатого конвейерного вычислительного устройства, содержащего трехступенчатый матрично— конвейерный блок умножения и рекуррентный блок выделения максимума, и позволившего повысить производительность по сравнению с программной реализацией.

4. Для поддержки процедур принятия решений разработаны алгоритм вычисления на программном уровне гипотетической минимально возможной величины коммуникационной задержки, а также методика и устройство оперативной проверки качества размещения задач, позволяющие уменьшить потери степени снижения коммуникационных задержек после маршрутизации.

5. В результате программного моделирования и статистических исследований на модели алгоритма функционирования разработанного акселератора показано, что скорость составления плана субоптимального размещения задач по процессорам матричного базового блока кластерной системы может быть повышена в 10 раз по сравнению с программной реализацией этого же алгоритма в управляющей машине кластера и в 100 раз по сравнению с известными алгоритмами, основанными на поиске субоптимального размещения методом ветвей и границ. Коммуникационные задержки в базовых блоках кластерных систем снижаются в 1.5.4 раза. Снижение выигрыша по сравнению с лучшими результатами, достигаемыми за счет больших затрат времени на поиск, не превышает 16. .19%.

6. Разработаны пакет программ моделирования на ЭВМ процедуры планирования размещения задач в матричном базовом кластерном блоке, позволивший оценить производительность акселератора, а также программа микропроцессорного контроллера, реализующая верхний уровень конвейерного вычислительного процесса акселератора.

Результаты исследований являются необходимыми предпосылками к применению оперативного переразмещения задач по процессорам перед рестартом восстанавливаемой вычислительной системы без существенного снижения коэффициента ее готовности и с сохранением запланированной степени ускорения параллельной обработки комплекса взаимосвязанных программ.

1. Цилькер, Б.Я. Организация ЭВМ и систем Текст.: учебник для вузов / Б .Я. Циль-кер, С.А. Орлов. СПб.: Питер, 2004.668 с.

2. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления- СПб.: БХВ- Петербург, 2002.- 608 с.

3. Keller A., Reinfeld A. Anatomy of a Resource Management System for HPC Clusters. Preprint. To appear in: Annual Review of Scalable Computing, Vol. 3, 2001.

4. Barker, M. (Ed.) (2000). Cluster Computing Whitepaper

5. Андреев A.H., Воеводин В.В. Методика измерения основных характеристик программно-аппаратной среды.

6. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999.

7. R. Buyya. High Performance Cluster Computing: Systems and Architectures. Volume 1, Prentice Hall PTR, NJ, 1999.

8. Борзов Д.Б. Модели и методы размещения задач в параллельных системах и устройства для их реализации / Д.Б. Борзов. канд. дис., Курск, 2002

9. Ю.Зотов И.В. и др. Организация и синтез микропрограммных мультимикрокон-троллеров. Курск.: Изд-во «Курск», 1999. - 368 с.

10. А.В. Гергель, Р.В. Виноградов. Оценка сложности коммуникационных операций в кластерных вычислительных системах / Нижегор. гос. тех. ун-т им. Н.И. Лобачевского С. 73-77

11. R. Buyya. High Performance Cluster Computing: Systems and Architectures. Volume 1, Prentice Hall PTR, NJ, 1999.

12. Pfister, G. Sizing Up Parallel Architectures Text. / G Pfister // DataBase Programming & Design OnLine. May 1998

13. A. Barak and O. La'adan. Performance of the MOSIX Parallel System for a Cluster of PC's. In Proceedings of HPCN Europe conference, 1997

14. Коршунов Ю.М. Математические основы кибернетики. М.: Энергоатомиз-дат, 1987.-496 с.

15. Воеводин В.В. Математические модели и методы в параллельных процессах. -М.: Наука., 1986.-296 с.

16. Arden B.W., Lee H. Analysis of chordial ring network // IEEETC. 1981. -Vol. C-30,№4.-PP. 291-295.

17. Reames C.C., Liu M. T. A loop network simultaneous transmission of variable length message // In: 2nd ASCA, Houston, Tex. 1975. - PP. 7-12.

18. Virginia Lo, Wanqian Liu. Noncontiguous processor allocation algorithms for mesh-connected multicomputers // IEEE Transactions on parallel and dist. Systems. -1997. Vol. 8, №7. - PP. 712-725.

19. Siegel H.J., McMillen R.J., Mueller Р.Т. A survey of interconnection methods for reconfigurable parallel processing systems // In: AFIPS Conf. Proc., Washington, D.C. 1979. - Vol. C-29, №2. - PP. 108-115.

20. Ope О. Теория графов. — M.: Наука, 1968. — 352 с.

21. Feng T-Y. A survey of interconnection network // IEEE Computer. 1981. - Vol. 14, №12. - PP.12-27.

22. Wittie L.D. Communication structures for large networks of microcomputers // ШЕЕ Transactions on Computers. 1981. - Vol. C-30, №4. - PP. 264-273.

23. K. Windisc, V.M. Lo, B. Bose. Contiguous and noncontiguous processor allocation algorithms for k-ary n-cubes // Proc. Int'l Conf. Parallel processing. 1995.

24. Ma P.R., Lee E.Y.S., Tsuchiya M. A task allocation model for distributed computing systems // IEEE Transactions on Computers. — 1982. — Vol. G-31, №1. — PP. 41-47.

25. Chu W.W., Holloway L.J., Lan M.-T., Efe K. Task allocation in distributed data processing // IEEE Computer. — 1980. — № 11. — PP. 57-69.

26. Lee Ch.-H., Lee D., Kim M. Optimal task assignment in linear array networks // IEEE Transactions on Computers. — 1992. — Vol. 41, №7. — PP. 877-880.

27. G.S. Rao, H.S. Stone, T.C. Hu. Assignment of tasks in a distributed processor system with limited memory // IEEE Trans. Comput. C-28 (4), - 1979, - PP. 291 -299.

28. Jo B.-L. et al. Task assignment in homogeneous linear array networks // IEICE Trans. 1991. - Vol. 74, №9. - PP. 2642-2648.

29. H.S. Stone, S.H. Bokhair. Control of distributed processes // Computer. 1978. -№6.-PP. 97-106.

30. L.M. Ni, K. Hwang. Optimal load balancing strategies for a multiply processor system // Proc. Inernat. Conf. Parallel. Proc. 1981. - PP. 352 - 357.

31. Gottlieb A., Schawarts J.T. Networks and algorithms for very-large-scale parallel computation // Computer. 1982. - Vol. 15, №1. - PP. 27-36.

32. Шоу А. Логическое проектирование операционных систем. М.: Мир, 1981.

33. Wu S.S., Sweeting D. Heuristic algorithms for task assignment and scheduling in a processor network // Parallel Computing. 1994. — №20. — PP. 1-14.

34. Bokhari Sh. H. On the mapping problem // IEEE Transactions on Computers. — 1981. — Vol. C-30, №3. — PP. 207-214.

35. Sadayappan P., Ercal F. Nearest-neighbor mapping of finite element graphs onto processor meshes // IEEE Transactions on Computers. — 1987. — Vol. C-36, №12. — PP. 1408-1424.

36. K. Efe. Heuristic models for task assignment scheduling in distributed systems // IEEE Comput. 1982. - 15(6). - PP. 50-56.

37. B.W. Kerninghan, S. Lin. An efficient heuristic procedure for partitioning graph // Bell Syst. Tech J. 1970. - №2, PP. 291-307.

38. Shen Ch.-Ch., Tsai W.-H. A graph matching approach to optimal task assignment in distributed computing systems using a minimax criterion // IEEE Transactions on Computers. — 1985. — Vol. C-34, №3. — PP. 197-203.

39. H.S. Stone. Multiprocessor scheduling with the aid of network flow algorithms // IEEE Trans. Software Eng. 1977. - Vol. SE-3. - PP. 85-93.

40. P. Chuang, N. Tseng. An efficient submesh allocation strategy for mesh computer systems // Proc. 1991 Int'l Conf. Distributed Computer Systems. 1991. - PP. 256263.

41. Y. Zhu. Efficient processor allocation strategies for mesh-connected parallel computers // Parallel and distributed computers. 1992. - Vol. 16. - PP. 328-337.

42. Борзов Д.Б., Зотов И.В., Титов B.C. О субоптимальном размещении процессов и данных в кольцевых сетях. Известия вузов. Приборостроение. - Санкт-Петербург, - 2003, - Т46, №11, С. 48-54.

43. Борзов, Д.Б. Процедура размещения комплексов алгоритмов управления в микроконтроллерных сетях с кольцевой структурой / Д.Б. Борзов, И.В. Зотов // Сборник материалов 4-ой международной конференции «Распознавание-99». -Курск, 1999.- С. 137-139.

44. Борзов Д.Б. Устройство поиска нижней оценки размещения в матричных системах / Патент РФ №2275681, БИ №12; от 27.04.2006.

45. Борзов Д.Б., Зотов И.В., Титов B.C. Устройство для формирования субоптимального размещения и его оценки / Патент РФ №2193796, БИ №33, 2002.

46. L.M. Silva, R. Buyya. Parallel programming and paradigms Text. // Silva L.M., Buyya R. A cluster computer and its architecture. Chapter 1, PP. 1-27.

47. Борзов ДБ., Мараят Б.И., Масолов С.А. Метод снижения коммуникационной задержки путем субоптимального размещения задач в матричных базовых блоках кластера, Телекоммуникации 2008№4, С 21-25.

48. Tanenbaum A.S. Distributed Operation Systems // Prentice-Hall Engeneer-ing/Science/Mathematics; 1st edition- 1994.-PP. 1-648.

49. Борзов Д.Б., Мараят Б.И., Типикин А.П. Алгоритмы и принцип организации аппаратных средств ускорения составления плана размещения задач в кластерных мультикомпьютерах / Деп. в ВИНИТИ 25.10.07 г., №998-В 2007.

50. Борзов Д.Б., Мараят Б.И. Методика планирования размещения задач в матрич-но-торроидальных базовых блоках кластерных мультикомпьютеров / Деп. в ВИНИТИ 18.07.06 г., №>961-В 2006.

51. Борзов Д.Б., Мараят Б.И., Типикин А.П. Акселератор планирования размещения задач в кластерных вычислительных системах высокой готовности. Известия вузов. Приборостроение, 2008, №2, С. 29-33.

52. Мараят Б.И. Устройство оценки качества размещения в системах с матричной организацией Текст. / Б.И. Мараят, Д.Б. Борзов, Т.А. Заикина, М.Х. Наджад-жра // Положительное решение на выдачу патента РФ по заявке №2007100634/09(000664)).