malyshkin_ve_korneev_vd_-_parallelnoe_programmirovanie_multikompyuterov

ячейки, всегда оказываются в одном ПЭ.

Для бόльшей конкретности дальнейших рассуждений фрагментированную программу можно представлять себе как множество атомарных фрагментов. Каждый атомарный фрагмент реализован в виде процедуры. На каждый процессорный элемент назначается на исполнение такое количество фрагментов, чтобы загрузка всех ПЭ была одинаковой. Это может быть сделано хорошо, если фрагменты невелики1. Напомним, что в первых трех стадиях моделирования (см. 6.1.1) вычисления ведутся в цикле по всем частицам. Время, затрачиваемое на выполнение этого цикла, составляет в зависимости от задачи от 70 до 90%

всего счетного времени. Поэтому критерием загрузки процессоров в этой задаче может служить число обрабатываемых в процессоре частиц. Таким образом, если в процессоре р0

обрабатывается N0 частиц, а в процессоре p1 – N1 частиц, то процессоры считаются равно загруженными при выполнении условия N1-ε < N0 < N1+ε . Пороговое значение ε определяет частоту проведения операции балансировки загрузки и выбирается специальным алгоритмом.

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

208

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

Понятно, что такая программа может быть крайне неэффективной при большом числе маленьких фрагментов

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

10% уменьшение её производительности по сравнению с монолитной программой. Обеспечение перелета многочисленных небольших фрагментов многократно уменьшило бы производительность всей программы.

Вообще желательно описывать сборочную программу в

1Аналог упаковки чемодана песком в предыдущей главе

2Да и реализация фрагментов процедурой неприемлема по той же причине.

209

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

Поэтому вводится дополнительно понятие минимального фрагмента, объединяющего несколько атомарных фрагментов.

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

6.3.Распараллеливание метода частиц

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

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

6.3.1.Распараллеливание метода частиц для линейки ПЭ (линеаризация PIC)

В качестве минимального фрагмента используется слой ПМ «толщиной» в одну ячейку. Всё ПМ разбивается на блоки

(рис. 6.5), каждый блок состоит из нескольких прилегающих слоёв. Блоки назначаются на ПЭ, число слоёв в каждом блоке выбирается таким образом, чтобы загрузка всех ПЭ была бы

210

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

Пространство моделирования

Коммуникационная

сеть

Рис. 6.5

6.3.2.Отображение линеаризованного PIC на 2D решетку ПЭ

Колонка ячеек выбирается в качестве минимального фрагмента для мультикомпьютеров со структурой коммуникационной сети типа 2D решетки и/или гиперкуба.

Для обеспечения исполнения линеаризованного PIC на решетке ПЭ строится его отображение на решетку. Пусть дана l×m 2D решетка ПЭ. Блок block_i (рис. 6.6) назначается для обработки на i-ю строку 2D решетки ПЭ, 1≤i≤l. Понятно, что block_i формируется таким образом, чтобы обеспечить равную

211

загрузку каждой строки ПЭ мультикомпьютера. При этом,

например, строка ПЭ, в которой один или более ПЭ неработоспособны, получит пропорционально меньшую нагрузку. Далее, каждый block_i делится на m подблоков block_ij, j=1,...,m, (по числу ПЭ в строке процессоров), которые распределяются на исполнение среди ПЭ строки. В свою очередь блоки block_ij формируются таким образом, чтобы обеспечить равную загрузку каждого ПЭ строки (рис. 6.6).

block_i

i-th row of processor grid

Рис. 6.6

6.3.3. Отображение 2D решетки ПЭ на гиперкуб

Коммуникационная структура гиперкуба также хорошо подходит для исполнения линеаризованного PIC. Линеаризованный PIC

отображается в гиперкуб следующим образом.

Обозначим узлы n-гиперкуба ai1,i2,...,in, ik={1,-1}, 1≤k≤n.

Каждый узел ai1,i2,...,in соединён с n другими узлами, чьи номера отличаются от номера узла ai1,i2,...,in только в одной позиции

212

индексов, т.е. их номера имеют вид i1,..., -ik,....,in для некоторого

k, 1≤k≤n.

Пусть мы используем 2l×2m решетку, l+m=n. Тогда соответствие между узлами гиперкуба и решетки таково:

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

213

6.4.Централизованные алгоритмы балансировки загрузки

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

6.4.1. Начальная балансировка загрузки ПЭ

Эвристический алгоритм конструирования начальной балансировки загрузки. В каждом ПЭ строятся два массива:

∙ А содержит данные о количестве частиц в каждом слое ПМ

(A[i] - количество частиц в i-м слое);

∙в S заносятся данные о распределении слоев между ПЭ (S(i)

- номер первого слоя блока, размещенного в ПЭi).

214

Таким образом, каждый ПЭ «знает», какие слои назначаются в другие ПЭ, это, собственно, карта распределения нагрузки между ПЭ.

Алгоритм имеет сложность О(km), где km - количество слоев ПМ. Обозначим общее количество частиц как NP, число ПЭ - как

NPE, среднее количество частиц в каждом ПЭ ANP=NP/NPE.

Нулевой слой назначается в ПЭ0 (нумерация ПЭ и слоев начинается с нуля). Далее в цикле по элементам массива А, слой j+1 назначается в ПЭi, если при этом количество частиц в первых

215

i+1 ПЭ менее отличается от (i+1)*ANP, чем без частиц этого слоя (рис. 6.7). Этот эвристический алгоритм строит очень хорошую начальную загрузку процессоров мультикомпьютера

216

6.4.2. Динамическая балансировка загрузки

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

«переливаться» из перегруженных ПЭ в недогруженные ПЭ так же, как жидкость переливается из переполненного сосуда в менее заполненный. Алгоритмы балансировки загрузки должны так же сглаживать пики нагрузки ПЭ, как сила притяжения сглаживает волны на поверхности воды в пруду (небольшие волны остаются).

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

217