glava3 4 (Лобусов Е.С. Теоретические основы параллельных вычислений), страница 3

где  - некоторый выбираемый скаляр.

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

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

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

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

3.1.1.2 Некоторые общие замечания по распределению.

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

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

Другой момент связан с тем, что эффективность распределения , оцениваемая показателем качества (21), существенно зависит от степени равномерности величин вычислительных загрузок компонент алгоритма обработки. Так для примера на рис.2.15 компонента F₂(x) по своей вычислительной загрузке значительно превышает все другие компоненты (низкая степень равномерности).

Н

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

В то же самое время отчетливо прослеживается тенденция: чем больше число компонент алгоритма и чем меньше величины загрузок для одного и того же алгоритма обработки, тем более эффективные решения по распределению могут быть получены. На том же рисунке 3.3б показано другое распределение загрузок, когда введение дополнительной переменной состояния загрузка F₂(x) оказалась разделенной на две части. Такое разделение привело к повышению степени равномерности и улучшению показателю качества при использовании 3-х процессорной сети.

Укажем, что сделанные замечания носят неформальный характер, но они оправдываются.

3.1.2 Составление расписания.

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

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

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

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

Получим математическое описание процесса составления расписания.

Введем расширенный граф алгоритма G_A и соответствующую матрицу распределения компонент S.

Основу графа G_A составляет граф G_A , веса вершин которого равны временам выполнения соответствующих компонент, так как уже известно распределения вершин G_A на подграфы (т.е. вершины графа G_C). Дуги, соединяющие вершины внутри каждого подграфа, являются невзвешенными. Дуги, соединяющие вершины G_A из разных подграфов преобразуются по следующему правилу. Допустим такая дуга соединяет вершины c и c, распределенные на процессоры р₁ и р_k соответственно; и пусть кратчайший путь между данными процессорами р₁ , р₂ , ... р_{k -1} , р_k проходит через промежуточные процессоры. Тогда для каждой пары процессоров р_i и р_i+1 , где i = 1, k-1 требуется выполнить по одной операции обмена. Поэтому исходная дуга в G_A заменяется на последовательность из k-1 вершин, каждая из которых соответствует времени передачи заданного объема информации для исходной дуги между двумя процессорами из общего k-1 числа пар. Естественно, что эти вновь введенные вершины соединяются невзвешенными дугами в том же самом порядке как образуется последовательность процессоров для передачи информации, то есть вершина c соединяется дугой с дополнительной вершиной первой пары процессоров р₁ и р₂ , потом с дополнительной вершиной следующей пары процессоров р₂ и р₃ и так далее. Последняя дуга соединяет дополнительную вершину пары процессоров р_к-1 , р_к и вершину c.

Отсюда в число вершин n нового (расширенного) графа G_A входят n вершин исходного графа G_A и n_с дополнительных вершин, образованных операциями обмена, то есть n = n + n_c .

Предположим теперь, что в процессорах отсутствует совмещение операций счета и ввода-вывода.

Новая (расширенная) матрица распределения S имеет размер m  n. Для вершины с номерами от 1 до n матрица S совпадает с матрицей S. Дополнительные вершины от операций обмена между двумя процессорами будут как бы одновременно принадлежать тем подграфам, которые соответствуют (распределены) этим процессорам.

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

Таким образом, в расширенном ориентированном графе G_А веса имеют только вершины.

Допустим исходный граф G_А приведен на рис.3.4а, а граф G_C на рис.3.4б. Распределение вершин (компонент) G_A дается матрицей S(рис.3.4в). Вершины графа G_A 3 и 6, назначенные на процессоры 3 и 1, обмениваются данными через процессор 2; а вершины 2 и 9, принадлежащие процессорам 2 и 3 , обмениваются данными непосредственно. На рис.3.4а пунктиром показаны дополнительные вершины, учитывающие наличие процессов обмена. А в матрице S (рис.3.4в) дополнительные вершины от обмена принадлежат одновременно 2-м подграфам.

Теперь дадим математическую постановку для составления решения.

Составить расписание - это означает найти вектор t = [t_i], где i = 1, n - время начала выполнения (запуска) компоненты соответствующей i-ой вершине в G_А , удовлетворяющее следующим условиям:

1.

2. для всех дуг (i, j) в G_А (t_i - время выполнения операции i-ой вершины G_А) (23)

3. , если вершины i и j принадлежат одному подграфу (в силу последовательного характера работы каждого процессора )

Рис.3.4

Под длиной расписания понимается время завершения работы всего алгоритма, считается, что он начал выполняться в нулевой момент времени. Поэтому длина расписания

(24)

Требуется найти расписание t, которое обеспечивает получение минимальной длины min t_max .Такая минимизация выполняется за счет нахождения определенного порядка выполнения вершин графа G_А .

Для нахождение решения, то есть нахождение вектора t в [4] предлагается воспользоваться известным списочным методом HLFET (High Level First with Estimated Time). Этот метод позволяет получить решение, хотя критерий оптимальности не определяется.

Каждой вершине графа G_А ставится в соответствие число, называемое приоритетом. Если две вершины графа G_А связана дугой, то приоритет вершины, из которой дуга выходит, больше приоритета второй вершины. Список приоритетов определяет последовательный или линейный порядок выполнения компонент алгоритма, соответствующих вершинам графа G_А в одном из подграфов - из 2-х вершин выполняется раньше та, которая имеет больший приоритет. Конкретно приоритеты могут быть определены следующим образом. Введем в граф G_А конечную вершину с номером n +1 (на рис.3.4а эта вершина затемнена) и направим в нее дуги из тех вершин G_А , которые не имеют выходных дуг. Из всех путей, ведущих из i-ой вершины в конечную найдем путь, имеющий максимальную длину (критический путь).

Чтобы найти максимальную длину для графа с положительными весами можно воспользоваться алгоритмом нахождения кратчайшего пути, но для графа с отрицательными весами. Приоритет i-ой вершины равен длине этого пути. Тем самым для любых двух вершин i и j, связанных дугой, приоритет i-ой вершины как минимум на величину t_i больше приоритета j-ой вершины.