Содержание к диссертации
Введение
1. Анализ известных методов и алгоритмов планирования размещения задач в кластерных вычислительных системах 11
1.1. Коммуникационные задержки в кластерных системах 11
1.2. Понятие о размещении задач по процессорам параллельной системы 17
1.3. Связь между топологиями вычислительных систем и методами размещения задач 19
1.4. Классификация методов размещения 23
1.5. Анализ алгоритмов размещения задач и целесообразность их аппаратной реализации 31
1.6. Выводы 38
2. Метод планирования размещения задач в кластерных вычислительных системах . 40
2.1. Постановка задачи минимизации коммуникационной задержки в кластерных вычислительных системах 40
2.2. Формализованная постановка задачи размещения в кластерных вычислительных системах 46
2.3. Метод минимизации коммуникационных задержек в матричных базовых кластерных блоках 49
2.3.1. Постановка задачи 49
2.3.2. Поиск гипотетической нижней оценки величины коммуникационной задержки 50
2.4. Алгоритм планирования размещения задач в кластерных вычислительных системах 52
2.4.1. Этапы поиска решения 52
2.4.2. Операция парной перестановки столбцов и строк матрицы обмена информации 54
2.5. Перестановочный алгоритм планирования размещения задач 55
2.6. Метод ускорения сходимости алгоритма 57
2.7. Ускоренный алгоритм планирования размещения задач 58
2.8. Методика ускоренного выполнения процедуры планирования размещения задач 59
2.9. Выводы 62
3. Моделирование процедур планирования размещения задач в кластерных системах 64
3.1. Описание программной модели процедур планирования 64
3.2. Методы моделирования 65
3.3. Результаты исследования на модели эффективности алгоритма планирования размещения 66
3.4. Выводы 76
4. Организация двухуровневого микропроцессорного акселератора планирования размещения задач 78
4.1. Принципы аппаратной реализации процедур планирования размещения 78
4.2. Двухуровневая структурная организация микропроцессорного акселератора планирования размещения задач 79
4.3. Алгоритмы функционирования акселератора 82
4.4. Производительность акселератора и функциональные схемы узлов его нижнего уровня 86
4.5. Методика и быстродействующее устройство проверки качества размещения задач 93
4.6. Выводы 102
Заключение 103
Библиографический список 106
- Понятие о размещении задач по процессорам параллельной системы
- Формализованная постановка задачи размещения в кластерных вычислительных системах
- Результаты исследования на модели эффективности алгоритма планирования размещения
- Двухуровневая структурная организация микропроцессорного акселератора планирования размещения задач
Введение к работе
Планирование оптимального размещения задач по множеству обрабатывающих процессоров - важный этап в процедурах подготовки комплекса взаимодействующих программ к параллельной обработке в мультикомпьютерах и кластерных системах. Оно выполняется с целью минимизации величин коммуникационных задержек, обусловленных способом обмена данными между задачами в ходе их обработки путем передачи сообщений между процессорами. Неудачное распределение задач между процессорами может привести к появлению длинных составных и перекрывающихся маршрутов транзитной передачи данных, возрастанию коммуникационных задержек и существенному снижению степени ускорения обработки, ожидаемой от распараллеливания.
В связи с началом освоения отказоустойчивых мультикомпьютеров и кластеров высокой готовности повышаются требования к скорости выполнения процедур планирования размещения задач. Быстрое восстановление правильности функционирования- системы путем реконфигурации ее структуры с отключением неисправного процессора и заменой его резервным, расположенным обычно вне поля обрабатывающих процессоров, приводит к существенному изменению конфигурации связей между ними и образованию длинных и перекрывающихся маршрутов передачи данных. Они могут быть уменьшены и разнесены путем оперативного переразмещения задач. В то же время процедуры планирования размещения являются комбинаторными, имеют большую вычислительную сложность и поэтому могут привести к существенному увеличению времени восстановления и снижению коэффициента готовности системы. Отказываться из-за этого от переразмещения задач перед рестартом восстанавливаемой системы нецелесообразно, так как возросшие коммуникационные задержки могут привести к такой потере системной производительности, которая превысит ожидаемый выигрыш от применения параллельной многопроцессорной обработки комплекса взаимодействующих программ. Поэтому для уменьшения времени восстановления многопроцессорных кластерных систем необходимо многократно снизить затраты времени на планирование размещения задач по сравнению с его программной реализацией в управляющей машине кластера: Этого можно достичь путем создания специализированного ускоряющего вычислительного устройства (акселератора), а при разработке алгоритмов его функционирования целесообразно найти новый метод снижения вычислительной сложности процедур планирования размещения задач по процессорам матричных базовых блоков кластерных систем высокой готовности.
В связи с вышеизложенным актуальной является научно-техническая задача многократного повышения скорости выполнения процедур планирования размещения параллельно обрабатываемых задач по процессорам кластерной системы путем реализации названных процедур в специализированном вычислительном устройстве.
Объект исследования: алгоритмы и технические средства реализации процедуры планирования размещения задач по процессорам кластерной вычислительной системы высокой готовности.
Предмет исследования: метод ускорения выполнения процедур планирования размещения задач в матричном базовом блоке кластерной системы, алгоритм функционирования и структурно-функциональная организация специализированного вычислительного устройства планирования размещения.
Цель работы: разработка метода ускорения составления плана субоптимального размещения задач по процессорам матричного базового блока кластерной системы, алгоритма, структурной и функциональной схем специализированного вычислительного устройства планирования размещения, позволяющих многократно снизить затраты времени на планирование размещения и уменьшить время восстановления кластера.
Для достижения поставленной цели решены следующие задачи.
1. Анализ известных методов планирования субоптимального размещения задач по процессорам мультикомпьютеров и кластерных систем и способов построения акселераторов планирования размещения (АПР).
2. Разработка метода ускорения составления плана субоптимального размещения задач по сравнению с известными программными и аппаратными реализациями процедуры планирования размещения.
3. Разработка методики ускоренного программно-аппаратного выполнения процедур планирования размещения задач по процессорам матричного базового блока кластерных систем высокой готовности.
4. Разработка алгоритма функционирования, структурной и функциональной схем специализированного вычислительного устройства планирования размещения задач в матричном базовом блоке.
5. Программное моделирование алгоритма функционирования АПР, оценка достигаемого ускорения составления плана размещения задач и производительности АПР.
Научная новизна результатов работы состоит в следующем:
1. Разработан метод ускорения поиска субоптимального варианта размещения задач по процессорам, основанный на целенаправленных перестановках строк и столбцов матрицы обмена информацией (МОИ) между задачами и мин-максном критерии оптимизации, отличающийся применением контроля степени уменьшения величин коммуникационных задержек в ходе направленных перестановок и позволяющий снизить общее число требуемых перестановок.
2. Разработана методика укоренного программно-аппаратного выполнения процедур планирования размещения задач в матричном базовом блоке кластерной системы, отличающаяся тем, что в каждом шаге поиска на аппаратном уровне реализуется быстрое вычисление максимального значения полученных величин задержек, а на программном уровне акселератора - перестановка строк и столбцов МОИ, анализ отношения достигнутого мин-максного значения задержки к гипотетической минимально возможной ее величине, принятие решения о целесообразности продолжения поисковых перестановок, и позволившая в результате контроля достижения заданно го порогового значения названного отношения отбрасывать большое число заключительных неэффективных перестановок и многократно повысить скорость поиска субоптимального варианта размещения.
3. Разработаны алгоритмы, структурные и функциональные схемы микропроцессорного акселератора планирования размещения с двухуровневой организацией, отличающегося аппаратной реализацией нижнего уровня нахождения максимального значения коммуникационных задержек в виде пятиступенчатого конвейерного вычислительного устройства, содержащего трехступенчатый матрично— конвейерный блок умножения и рекуррентный блок выделения максимума, и позволившего повысить производительность по сравнению с программной реализацией. Практическая ценность работы заключается в следующем
1. В результате программного моделирования и статистических исследований алгоритма функционирования разработанного акселератора показано, что скорость составления плана субоптимального размещения задач по процессорам матричного базового блока кластерной системы может быть повышена в 10 раз по сравнению с программной реализацией разработанного алгоритма в управляющей машине кластера и в 100 раз по сравнению с известными алгоритмами, основанными, на поиске субоптимального размещения методом ветвей и границ.
2. Для поддержки процедур принятия решений разработаны алгоритм вычисления на программном уровне гипотетической минимально возможной величины коммуникационной задержки, а также методика и устройство оперативной проверки качества размещения задач, позволяющие уменьшить потерю степени снижения коммуникационных задержек после маршрутизации.
3. Разработанная методика ускоренной процедуры планирования размещения позволяет уменьшить коммуникационные задержки в базовых блоках кластерных систем в 1.5...4 раза. Снижение выигрыша по сравнению с лучшими результатами, достигаемыми за счет больших затрат времени на поиск, не превышает 16.. .19%.
4. Разработанные методика и быстродействующее устройство оперативной проверки качества размещения задач позволяют уменьшить вероятность возникновения потерь в степени снижения коммуникационных задержек в результате последующей маршрутизации.
5. Результаты исследований являются необходимыми предпосылками к применению оперативного переразмещения задач по процессорам перед рестартом восстанавливаемой вычислительной системы без существенного снижения коэффициента ее готовности и с сохранением запланированной степени ускорения параллельной обработки комплекса взаимосвязанных программ.
На защиту выносится следующие результаты
1. Метод ускорения поиска субоптимального варианта размещения задач, основанный на мин-максном критерии оптимизации, отличающийся применением контроля степени уменьшения величин коммуникационных задержек в ходе направленных поисковых перестановок строк и столбцов матрицы обмена информацией между задачами и позволяющий снизить общее число требуемых перестановок.
2. Методика ускоренного программно-аппаратного выполнения процедур планирования размещения задач по процессорам матричного базового блока кластерной системы, отличающаяся вынесением на аппаратный уровень акселератора вычислительно сложного этапа нахождения максимума задержек, образующихся в результате поисковой перестановки, а на программный уровень - выполнения очередной перестановки, выделения минимума из последовательности названных максимумов по результатам ряда перестановок, принятия решений о целесообразности инициализации поиска или о прекращении поиска и отбрасывании заключительных неэффективных перестановок, позволившая многократно повысить скорость поиска субоптимального варианта размещения.
3.Алгоритм вычисления гипотетической минимально возможной величины коммуникационной задержки, основанный на допущении о тождественности топологий связей между размещаемыми задачами и связей между процессорами и позво ливший определить требуемую для принятия решения пороговую величину кратности превышения достигаемого в процессе поиска мин-максного значения задержки над названной минимально возможной ее величиной.
4. Алгоритмы и структурно-функциональная организация двухуровневого микропроцессорного акселератора планирования размещения задач, отличающегося аппаратной реализацией нижнего уровня нахождения максимума коммуникационных задержек в виде пятиступенчатого конвейерного вычислительного устройства, содержащего трехступенчатый матрично-конвейерный блок умножения, и позволившего повысить производительность по сравнению с программной реализацией.
5. Методика и быстродействующее устройство оперативной проверки качества размещения задач, позволяющие уменьшить вероятность возникновения потерь в степени снижения коммуникационных задержек в результате последующей маршрутизации.
Области возможного использования. Результаты диссертационной работы могут быть использованы в кластерных системах высокой готовности, например, в случае отказа одного из процессорных модулей, когда необходимо оперативное переразмещение задач. Применение разработанного акселератора позволит дополнительна снизить затраты времени на планирование размещения задач и организовать оперативное переразмещение задач перед рестартом восстанавливаемой системы без существенного снижения ее коэффициента готовности, а также уменьшить сложность алгоритмов последующей маршрутизации параллельной передачи сообщений в матричных многопроцессорных системах.
Понятие о размещении задач по процессорам параллельной системы
На содержательном уровне задача размещения может быть представлена как выбор такого варианта распределения задач между модулями параллельной системы (ПС), которому будет соответствовать минимальное время выполнения комплекса взаимодействующих задач в целом [9,10,13-18].
Очевидно, что время выполнения подзадач, не содержащих операторов межмодульного взаимодействия (передачи управления, ожидания передачи управления и ожидания завершения параллельных ветвей), зависит в основном от информационного взаимодействия подзадач друг с другом. Для минимизации времени выполнения задач необходимо уменьшение среднего суммарного времени межмодульного взаимодействия. Последнее может обеспечиваться за счет уменьшения расстояний между задачами, которым соответствует наибольшая интенсивность взаимодействия, а также минимизации суммарной интенсивности взаимодействия между смежными процессорными модулями, обусловленной наложением-(перекрытием) в канале связи маршрутов передачи сообщений между разными парами взаимодействующих задач, и, следовательно, за счет сокращения средних длин очередей межмодульных сообщений. С учетом выделенных факторов исходную задачу размещения можно представить следующим образом. Найти такой способ распределения подзадач между модулями ПС, который минимизирует [9] интенсивности взаимодействия между смежными процессорными модулями; расстояния между подзадачами, которым свойственен наибольший объем передаваемых данных.
Одним из ключевых вопросов, возникающих при решении задачи размещения, является выбор адекватной модели представления размещаемой задачи.
Для представления комплекса взаимодействующих задач традиционно существует два вида топологического описания [15-17]: граф предшествования задач (task precedence graph) и граф взаимодействия задач (task interaction graph); Первое из них - ориентированный граф GI V,Er , вершины которого соответствуют участкам алгоритма (подзадачам), а дуги определяют зависимости (связи) между участками, проявляющиеся в динамике исполнения,комплекса подзадач. Граф предшествования задач представляет отношение частичной упорядоченности (precedence relation) на множестве участков.
Второе описания графом взаимодействия задач GP= V,EP , в отличие от рассмотренной выше модели, не несет информации о временных соотношениях между моментами запуска участков программ и позволяет задать только факт наличия или отсутствия взаимосвязей (как управляющих, так и информационных) между участками. Вершины данного графа соответствуют различным участкам алгоритма, а дуги (или ребра) отображают связи между участками. При этом как вершинам, так и дугам ставятся в соответствие некоторые (как правило, положительные) числа — веса. Веса вершин графа могут определять, например, вычислительную сложность соответствующих участков, а веса дуг (ребер) — объем данных т, передаваемых между участками (подзадачами) в динамике их исполнения [9,10,20], так как он определяет коммуникационной задержки t„d(m) по формулам (1.1-1.4) известной методики [11].
Одним из важных условий решения задачи субоптимального размещения является выбор метода размещения. В настоящее время существует множество методов размещения в ПС. Поэтому, прежде чем приступать к решению задачи размещения, необходимо рассмотреть наиболее распространенные из них.
Самый простой вариант топологической организации ПС - цепочка [9,21]. Она представляет собой последовательность процессоров (рис. 1.2а), і-й процессор которой соединен с (і+1)-м и (і-І)-м. Достоинством данной топологии является малая и не зависящая от размеров ПС удельная сложность. Кроме того, при добавлении дополнительного процессора ПС легко расширяется. Недостатком рассмотренной топологии является невозможность построения систем больших размеров (N 10), поскольку возрастают задержки в передаче сообщений. Другим недостатком является то, что при выходе из строя і-го процессора разрушается канал взаимодействия между процессорами mk и т/, хотя остальная часть системы остается работоспособной. Вследствие этих недостатков ПС с линейной топологической организацией отдельно.. практически не используются, однако цепочки важны в связи с возможностью применения их в более сложных системах, например матричных. Действительно, в матричной ПС каждую строку и/или столбец матрицы можно рассматривать как отдельную линейку (рис. 1 .За-в). .того „НШ
Простые топологии параллельных систем При замыкании связей первого и последнего процессоров линейной ПС топология системы из цепочки превращается в кольцо [9,15-20]. На рис. 1.26 представлена кольцевая ПС, в которой і-й процессор может принимать информацию как от соседнего справа ((i+l)mod N), так и от соседнего слева процессора ((i+N-l)mod N), i = 0,N-l. Такая топология называется двунаправленной кольцевой. На рис. 1.2в представлена система, которая называется однонаправленной или ориентированной кольцевой ПС. В данной топологии информация от і-го процессора передается либо процессору (i+l)mod N либо процессору (i+N-l)mod N, при этом принимается - от процессора (i+N-l)mod N либо от (i+l)mod N соответственно. Кольцевым ПС независимо от направления передачи информации присущи практически те же свойства, что и цепочке - простота маршрутизации сообщений, малая удельная сложность, простота комплексирования и т.д. Так же как и в случае цепочки на кольцевых ПС сложно построить системы с большим количеством модулей (N 10-20). ПС с кольцевой организацией также обладает малой надежностью. В них возникает практически такая же ситуация, как и в случае с линейной ПС. В таких системах размещение организуется легко и поэтому их можно использовать в качестве базы для построения более сложных систем (кластерных, матричных). Максимально возможного быстродействия можно получить при реализации ПС в виде полносвязных структур (рис. 1.2г). Межмодульный обмен информацией осуществляется фактически без ретрансляции, так как любая пара модулей соединяется индивидуальным двунаправленным каналом. Такие структуры обладают достаточной степенью надежности, т.к. при отказе одного элемента вся система в целом сохраняет свою работоспособность, а нарушается связь только между і-м и j-м элементом. Но, несмотря на очевидные достоинства, такие системы не позволяют строить системы с большим количеством модулей из-за квадратичного роста сложности, роста числа связей с увеличением размера системы и, в то же время, чрезвычайно низкой загрузкой каналов связей.
Другой вариант построения ПС является система с шинной топологической организацией (рис. 1.2д). Очевидным достоинством шинной организации является независимость числа связей от числа модулей в системе и простота наращиваемости сети. Тем не менее, они не позволяют построить ПС с большим количеством модулей (N 10-20). Это обусловливается ограниченной пропускной способностью шины. Так при равномерной генерации сообщений каждый из модулей вынужден ожидать освобождения шины в среднем в течение — условных временных интервалов [9,23].
Другой недостаток этой топологии - низкая надежность, т.к. выход из строя шины выводит из строя всю структуру.
Один из возможных способов улучшения организации систем с шинной топологией является ПС с мультишинной (рис. 1.2е). Кроме того, такие системы используются как часть других топологий, например, матриц или гиперкубов. Очевидно, что такие системы обладают более высокой степенью надежности, но, несмотря на это, они обладают и высокой удельной сложностью. Например, при использовании N общих шин затраты на каналы связи зависят от размеров ПС как 0(N ) [9,23].
Формализованная постановка задачи размещения в кластерных вычислительных системах
Коммуникационная задержка при постоянной скорости передачи данных в коммуникационной среде пропорциональна произведению длины маршрута / и объема m передаваемой информации (1.1-1.4) [4,5,6,11,53]. Учитывая что при оптимальном прокладывании маршрутов их длины (/Л - Ыу\ стремятся к минимальным расстояниям dy между процессорами и не могут быть уменьшены менее, чем минимальные расстояния djj, определяемые топологией коммуникационной среды, т.е. Ц dtJ-, процедура субоптимального размещения задач может быть сведена к поиску такого их расположения в процессорах, при котором минимизируется максимальная величина всевозможных задержек на всевозможных маршрутах межсоединений между процессорами, необходимых для организации передачи данных между задачами в динамике параллельного выполнения комплекса обрабатываемых взаимосвязанных задач. Такой критерий позволит достичь одновременного уменьшения задержек на всех требуемых маршрутах. Причем в первом приближении можно учитывать в процедуре размещения не длины маршрутов, а их минимально возможные величины — минимальные расстояния dy, что позволит использовать результаты размещения для снижения сложности процедуры последующей маршрутизации. На основании изложенного выше задача размещения комплекса взаимосвязанных программ по процессорным модулям ПС может быть формализована в следующей математической постановке.
Планирование размещения задач в базовых кластерных блоках с матричной топологией может быть выполнено по специальному алгоритму целенаправленной перестановки строк и столбцов в матрице обмена информацией (МОИ) М=т; IINXN - = "2 =И описывающей граф G, где элемент т1} - количество байт, которое передается между задачами х, и Xj в процессе их выполнения [53].
Математическая постановка задачи поиска аналогична описанной выше (п. 2.2). Так как мощность множества i// = {/3s) возможных отображений (2.1) равна числу всевозможных перестановок задач ixqk\ в матрице X: \i//\ = N\, поиск наилучшего варианта размещения /? по критерию (2.2) является очень сложной переборной задачей. В тоже время затраты времени на поиск лучшего варианта размещения должны быть меньше, чем получаемый в результате этого выигрыш по времени в снижении величины коммуникационной задержки. В противном случае поиск лучшего варианта будет просто бессмысленным [11]. Поэтому основной целью данной работы является достижение максимально возможного ускорения процедуры планирования за счет снижения выигрыша в снижении величины коммуникационных задержек не более, чем 20-30%, по сравнению с лучшими результатами, достигаемыми при больших затратах времени на поиск.
Для этого необходимо в ходе поиска контролировать степень уменьшения величины образующихся коммуникационных задержек (2.3) и принимать решение о целесообразности продолжения поисковых перестановок строк и столбцов матрицы МОИ. Оно может быть принято в результате анализа величины отношения достигнутого мин—максного значения задержки (2.2) к гипотетической минимально возможной ее величине, алгоритм вычисления которой рассмотрен ниже (см. п. 2.3.2).
Для поиска субоптимального варианта размещения (3 , удовлетворяющего критерию (2.2), первоначально необходимо вычислить недостижимую минимальную оценку размещения Tjnf при допущении, что топологии исходного графа- G и графа связей Н между модулями тождественны. При вычислении нижней оценки будем назначать дуги графа G с наибольшим весом на самые короткие маршруты в графе Н, не обращая внимания на ограничения, накладываемые фактическими связями между задачами в графе G [53].
Для этого необходимо ввести понятие стандартного графа. Пусть дан орграф G с числом вершин Пі и числом ребер п2. Стандартным графом по отношению к исходному графу G называется граф G , содержащий П] вершин и п2 ребер, оптимальным образом размещенный в заданной ПС [24].
Рассмотрим способ получения стандартного графа G . Очевидно, что оптимальное размещение вершин произвольного графа может быть достигнуто только тогда, когда вершины, связанные ребрами с большим весом, закрепляются за близлежащи 50 ми позициями модулей ПС. Таким образом, стандартный граф может быть получен путем ранжирования ребер исходного графа G по их весам и последовательного размещения инцидентных им вершин в позиции, расстояние между которыми минимально возможное. Первоначально из множества ребер стандартного графа.выбираются ребра с наибольшим весом. Далее веса выбираемых ребер последовательно уменьшаются до тех пор, пока не будут рассмотрены ребра с наименьшим весом, размещения которых в удаленных модулях ПС не дадут существенного прироста коммуникационной задержки. Выбираемые ребра вкладываются в топологическую модель ПС, описываемую графом Н. При этом вложение осуществляется независимо от смежности ребер исходного графа G, но учитывается единственное ограничение на число возможных пар вершин графа Н, находящихся на определенном расстоянии S. Так как вложение осуществляется независимо от смежности связей в исходном графе G, получим соответствующую нижнюю, практически недостижимую оценку. Все вышеуказанные соображения позволили применить в данной работе алгоритм [9] для получения нижней оценки коммутационной задержки при передаче данных между задачами.
Результаты исследования на модели эффективности алгоритма планирования размещения
После ввода параметров заполнения матрицы М (МОИ) выполняется алгоритм поиска нижней оценки в соответствии с алгоритмом перестановок строк и столбцов в МОИ выполняется поиск варианта размещения, а далее строится график изменения Т величины т] = — при каждой очередной перестановке [53,55]. 1. При таком начальном заполнении МОИ объемами передаваемых между зада чами данных, когда т\ц 2, выигрыш в снижении коммуникационной задержки со ставляет всего a = 1,3...2 раза. Причем наибольший выигрыш может быть достигнут лишь в изначально наихудшем по разбросу объемов передаваемых данных случае заполнения МОИ, когда отношение элементов — = —, где m - элемент матрицы тпах 10 МОИ с размерностью [т]=байт. 2. Сходимость поиска можно значительно улучшить путем ввода дополнитель ных критериев (2.16, 2.17) контроля целесообразности перестановки по ускоренному алгоритму (п. 2.7). Это позволяет избавиться от заведомо неудачных перестановок и сократить вдвое общее число требуемых перестановок Q (рис. 3.5). 3.
В связи с необходимостью выполнения по перестановочному алгоритму (п. 2.5) избыточного количества перестановок, большая часть которых приходится на заключительную часть процедуры поиска, когда значение г/ перестает существенно снижаться, целесообразно вести порог /;„ эффективности перестановок, который отсекал бы эти избыточные перестановки по неравенству ri 7]u
Для уточнения величины порога вначале были получены характеристики при минимальном его значении г}п = 1,8 (рис. 3.6, 3.7). На основании графиков (Рис. 3.4 -3.7) и данных из таблицы 3.1 можно установить, что при использовании дополнительных критериев по ускоренному алгоритму планирования размещения (п. 2.7) могут быть получены следующие результаты в ускорении сходимости сходимости поиска.
1. Кол-во требуемых шагов перестановок до достижения rjmin = 1.8 уменьшается в среднем лишь на 4%.
2. Максимальное количество перестановок, требуемых для целесообразного перебора всех элементов матрицы МОИ с целью достижения минимально возможного значения показателя тіп(77тіп) 1.8 (Рис. 3.5), уменьшается в 2 раза по сравнению с перестановочным алгоритмом, основанным только на одном критерии 2.13 (Рис. 3.4).
Приведенные зависимости позволяют сделать вывод, что введение дополнительных критериев в ускоренный алгоритм позволяет вдвое снизить затраты времени за счет исключения избыточных явно нецелесообразных перестановок. В связи с. этим, несмотря даже на незначительное ускорение поиска по достижению порога 7 = 1.8, введение дополнительных критериев (2.16, 2.17) оправдано существенным снижением потерь времени на поиск в тех случаях, когда порог rjn = 1.8 недостижим.
Это возможно при сильно связаной МОИ, например, при наличии задачи с большим количеством связей и большими объемами передаваемой по ним информации. Тогда не всегда удается в результате поиска достичь порога rjmin =?]п=1Я,и может потребоваться полный перебор всех элементов МОИ.
Двухуровневая структурная организация микропроцессорного акселератора планирования размещения задач
Акселератор планирования размещения задач На рисунке 4.1 приняты следующие обозначения блоков и узлов: АВПКЗ - акселератор вычисления показателя коммуникационной задержки, МП - микропроцессор, ОП - оперативная память, БСПДП - контроллер прямого доступа в память, Ппорт - последовательный порт, Прпорт - параллельный порт, MUX - мультиплексор, УУ - устройство управления, БУМК - блок умножения матрично-конвейерный, МАХ - блок сравнения и нахождения максимума.
МП контроллера работает в соответствии с программой, записанной в ОП, переставляет строки (столбцы) матрицы МОИ и передает новое МОИ в ОЗУ1. В ОЗУ2 можно заранее передавать ММР, а далее ее многократно использовать при поиске. Самую частую операцию, требующую ускорения - вычисление максимальной ком 81 муникационной задержки предполагается вычислять в аппаратном ускорителе. Для этих целей в состав схемы введен акселератор вычисления показателя коммуникационной задержки (АВПКЗ), ускоряющий решение задачи планирования размещения задач в базовом блоке кластерной ПС. Блок АВПКЗ отличается тем, что в нем применены конвейерный и матричный подходы для поэлементного перемножения векторов с одновременным подсчетом максимального произведения. В составе АВПКЗ можно выделить шесть основных функциональных блоков. Данные с параллельного порта поступают в блок специализированного мультиплексора (MUX). В зависимости от режима работы MUX загружает одно из ОЗУ данными соответствующей разрядности, при этом если идет загрузка В ОЗУ2 из 8-ми разрядного порта за один цикл приема.MUX принимает два 4-х разрядных слова; если же идет загрузка в ОЗУ] то MUX принимает два байта 16-ти разрядного слова и после их склеивания-помещает целое слово в ОЗУ].
Блок умножения матричной-конвейерный (БУМК) осуществляет перемножение синхронно считанных из ОЗУ! и ОЗУ2 двух слов и выдает результат в блок нахождения максимума (МАХ). Умножение происходит конвейерно за один такт. Исключение составляет первые такты загрузки ступеней матричного конвейера. Таких ступеней 3, т.к. при размерности данных в ОЗУ2, равный 4 битам, используется только 3 из них.
Алгоритм планирования размещения задач в матричном базовом блоке Приведенные алгоритмы реализованы в аппаратной части блока АВПКЗ и в программной части контроллера акселератора. Описание его программной части, в том числе структур представления данных, структуры программы контроллера и программных объектов управления обменом данных между контроллером и АВПКЗ через параллельный порт приведено в приложении 2.
Описанные принципы структурной и функциональной организации акселератора позволяют достичь более высокой производительности по сравнению с программной реализацией алгоритмов планирования в управляющей ЭВМ кластерной системы. Это достигается за счет применения двухуровневой конвейерной обработки. На верхнем уровне организован двухступенчатый конвейер, в котором совмещаются во времени 2 этапа каждого цикла обработки: 1) выполнение в микропроцессорном контроллере следующего шага перестановок строк/столбцов матрицы МОИ, вычисление оценок и принятие решения по результатам предыдущего шага; 2) вычисление на нижнем уровне в АВПКЗ показателя коммуникационной задержки, соответствующего предыдущему шагу перестановок, выполненном ранее в контроллере.
В соответствии с разработанной выше методикой ускоренного выполнения процедуры планирования размещения (п. 2.8) и результатами ее проверки на программной модели (п. 3.3) в большинстве случаев размещения в матричном базовом кластерном блоке комплекса взаимосвязанных задач с реальной степенью связности требуемое в процедуре число циклов обработки (циклов перестановки Q) колеблется в пределах: Q=160...730.
Таким образом, может быть достигнута высокая производительность составления планов размещения и переразмещения задач в современных кластерных системах высокой готовности, позволяющая уменьшить требуемое при этом увеличение времени восстановления системы после отказа процессорного модуля до 1.. .5 мс. Производительность данного микропроцессорного акселератора существенно выше производительности, получаемой при программной реализации его алгоритма (Рис. 4.4) в управляющей ЭВМ кластерной системы. Как следует из результатов его моделирования (Рис. 3.8), затраты времени при программной реализации изменяются в пределах: NT =(0.007К 0.03)-109 тактов работы процессора, или Npn =NT-ffl =10К 50 мс работы микропроцессора Alpha 21264 системы МВС 1000М. Таким образом, производительность, достигаемая при аппаратной реализации процедуры размещения, в 10 раз выше по сравнению с ее программной реализацией.
Однако для достижения приведенных выше показателей производительности необходима такая аппаратная реализация функций нижнего уровня акселератора в блоке АВПКЗ, которая позволила бы вычислять показатель коммуникационной задержки (максимальное ее значение) с максимальной скоростью в темпе выполнения последовательных циклов1 синхронного считывания элементов матриц МОИ и ММР из памятей ОЗУ1 и ОЗУ2. Поэтому на нижнем уровне акселератора применена конвейерная организация путем последовательного соединения узлов БУМК и МАХ (Рис. 4.1) и конвейеризации матричного блока умножения БУМК. Длина-конвейера-равна пяти ступеням.
