3. Методы отображения алгоритмов обработки.

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

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

Пусть описание алгоритма обработки задаётся графом G_A , а описание ВС - графом G_C. Тогда в теории назначений под отображением понимается распределение вершин графа G_A по вершинам графа G_C, а в теории расписаний - дополнительно учитывается ещё и время начала выполнения распределённой вершины G_A.

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

3.1. Статические методы.

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

3.1.1. Распределение компонент алгоритма обработки.

Зададим распределение компонент алгоритма обработки по процессорам матрицей размера m  n (m - число процессоров, n - число компонент), элементы которой s_ji = 1,если i-ая компонента (вершина) принадлежит j-ому процессору (подграфу алгоритма обработки, выполняемому на этом процессоре) и s_ji = 0 в противном случае.

Для оценки поярусной параллельности распределения вводится матрица Q = [q_ij] размера h  m, где h-число ярусов алгоритма обработки

Q = H  D_c  S^T , (8)

Элементы этой матрицы q_ij определяют суммарный вес (вычислительную сложность) вершин , принадлежащих j-му подграфу и i-му ярусу в графе алгоритма G_A.

Для оценки величины суммарного объема информации , которым обмениваются отдельные подграфы вводится матрица F = [f_ij] размерностью m  m

F = S  E  S^T , (9)

(диагональные элементы f_ij определяют величину суммарного объема информации при обмене между компонентами (вершинами) внутри каждого подграфа).

Отметим также , что соотношение (9) определяет направленный обмен , то есть от i к j.

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

Допустим, что алгоритм обработки представлен на рис.3.1 и там же дано распределение его по подграфам (вершинам сети процессоров). Тогда матрицы S, H , E , Q , F , имеют следующий вид

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

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

(11)

Первое слагаемое

,

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

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

Отметим, что уже сама форма функционала при  = 1 предполагает, что процессор непосредственно выполняет обмены, то есть в модели процессора предполагается отсутствие совмещения вычислений и обмена!

Выбранный функционал качества (11) допускает постановку задачи оптимального распараллеливания алгоритма обработки. При известных графах алгоритма G_A = <C, E> и вычислительной сети G_C = <P, T> найти матрицу S распределения задач алгоритма на m подграфов такую, чтобы обеспечить минимум функционала J.

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

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

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

Найти:

(12)

где элементы функционала J задаются матрицами Q, T, , P, при ограничениях:

(12)

Данная постановка относится к задачам NP-сложности. Поэтому для нее малопригодны точные (переборные) методы .

Для нахождения решения существует ряд подходов. Опишем один из методов, используемый в [4] и называемый аналоговым методом Монте-Карло. Целесообразно применять его при больших размерностях графа алгоритма обработки G_A и вычислительной сети G_C .

Аналоговое решение оптимизационной задачи строится следующим образом. Вершины графа G_A будем моделировать частицами, совершающими вязкое движение в потенциальном силовом поле. В качестве потенциала взаимодействия частиц выберем функционал времени счета J(S) (11). Тогда координаты частиц меняются со временем согласно уравнению

(13)

Под действием поля частицы - вершины графа, имеющие координаты, задаваемые матрицей S , то есть , если s_ij = 1, то это определяет некоторую вершину графа G_A в m-мерном пространстве координатой (i, j) , где i - номер оси (строки) j - положение на оси (строке), будут стремиться расположиться по подграфам так, чтобы доставить минимум функционалу J. Однако расчет координат по детерминистическому уравнению (13) может привести к попаданию частиц в один из локальных минимумов, из которого они не в состоянии выбраться. Поэтому в систему вводятся дополнительные стохастические силы, приводящие к тепловым флуктуациям частиц, которые помогают им выбраться из локальных минимумов. Тогда процесс поиска оптимального расположения частиц в подграфах будем моделировать процессом случайного блуждания в потенциальном силовом поле J(S) . Пусть вероятность P(S, t) обнаружить частицу в момент t в точке с координатами S подчиняется уравнению Фоккера-Планка [5]

(14)

Стационарное распределение вероятностей для уравнения (14) запишется следующим образом:

(15)

где z - нормирующий коэффициент, обеспечивающий .

Максимум вероятности (15) соответствует такому расположению частиц по подграфам, которое доставляет минимум функционалу J. Соотношение Эйнштейна D =  связывает подвижность  и коэффициент диффузии D, характеризующий тепловые флуктуации. Распределение (15) является распределением Больцмана с температурой .

Тепловые флуктуации ведут к перебросам частиц между минимумами потенциала J(S). Если два минимума разделены потенциальным барьером J, то среднее время перехода между ними оценивается как   ехр(J/). Характерное время установления равновесного распределения вероятностей при температуре  тем больше, чем выше потенциальные барьеры и чем ниже температура .

Если в область абсолютного минимума попадают локальные минимумы, отделенные от него потенциальным барьером J  , то при наличии флуктуаций динамическая система не может отличить их от абсолютного минимума. Чтобы избежать этого используют имитацию "отжига" системы, постепенно понижая температуру  и устремляя её к нулю. Чтобы длительность отжига , гарантирующего правильное отыскание глобального минимума J, не была экспоненциально велика , его нужно начинать с температуры   J_max .

Описание метода Монте-Карло.

Стационарное решение (15) моделируется методом Монте-Карло. Общая схема метода такова:

Алгоритм Монте-Карло:

1. Полагаем начальную температуру равной ₀.

2. Выбираем равновероятно начальное расположение вершин Sо и вычисляем его эффективность J₀ = J(S₀).

3. На каждой итерации t случайным образом перебираем все частицы-вершины. Для каждой из вершин случайно выбираем новый подграф и определяем приращение функционала J при переносе в него данной вершины. Если J < 0, то вершина переносится в новый подграф, иначе она переносится в него с вероятностью ехр(-J / t).

4. Понижаем температуру по закону t = ₀ / t .

5. Если зафиксирован выход на стационарное значение функционала J, то конец алгоритма, иначе переходим на 3.

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

3.1.1.1 Распределение алгоритмов обработки, основанных на методах численного интегрирования.

Для данного алгоритма обработки уже известно графовое представление, имеющее вид на рис.2.13. Его параллельно-ярусная форма составляет вектор 1 n с компонентами, равными 1, то есть

H = [ 1, 1, ... ,1 ].

Поэтому такая матрица Н никак не влияет на последующее рассмотрение, то есть её можно не учитывать.

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

Определим вычислительную загрузку j-го процессора wl_j(S) в размерности времени