ГРАФ-СХЕМЫ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ

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

Например, программа F представляется как

где точкой с запятой отделены входные данные от выходных, Х = {Хи Х2} — исходные данные задачи, Y — выходные данные или результат.

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

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

Пусть для данного алгоритма и предполагаемой ВС нам известны такие оценки: Т = {t, t2,..., /в}. Тогда, чтобы отразить прохождение обрабатываемой информации и выявить возможности распараллеливания, представим информационную граф-схему алгоритма, или информационный граф G (рис. 9.1). Вершины соответствуют работам. Дуги отражают частичную упорядоченность работ.

Информационный граф алгоритма

Рис. 9.1. Информационный граф алгоритма

Если работа (3 использует в качестве входной информации результат выполнения работы а, то ее выполнение не может быть начато до того, как закончится выполнение работы а. Такая преемственность информации и отражена в графе. Граф G — взвешенный, ориентированный и не содержащий контуров. (Поскольку время выполнения алгоритма исключает «зацикливание», то программные циклы либо погружены внутрь работ либо развернуты.)

Например, представим себе информационный граф, соответствующий скалярному умножению векторов заданной длины: А = В х С способом «пирамиды», В = {Ь, ..., b$}, С = {с, ..., с8}. Схема счета показана на рис. 9.2.

Схема счета «пирамидой»

Рис. 9.2. Схема счета «пирамидой»

Примем время сложения равным единице. Время умножения пусть превышает время сложения в четыре раза. Информационный граф G, соответствующий счету способом «пирамиды», представлен на рис. 9.3.

Информационный граф — «пирамида»

Рис. 9.3. Информационный граф — «пирамида»

Мы изучили составление информационных графов. Можно рассматривать информационно-логические графы, если учитывать альтернативные ветви алгоритмов. Например, может быть целесообразным следующее разбиение программы (алгоритма) на модули (работы):

Информационно-логический граф G показан на рис. 9.4.

Информационно-логический граф

Рис. 9.4. Информационно-логический граф

Преемственность информации (1 —> 2), а также (1 —» 3) при наличии «жирной» стрелки «по управлению» можно не указывать, так как частичная упорядоченность работ в таком случае полностью определена.

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

Для формальных исследований информационный граф G представляется матрицей следования S или, с добавлением столбцов весов, — расширенной матрицей следования S*. При этом поскольку граф G не содержит контуров (циклов), то S может быть сведена к треугольной «правильным» выбором нумерации вершин. Ниже (рис. 9.5) приведены матрицы S и ,5* для графа, представленного на рис. 9.1 и для некоторых известных значений весов.

Матрица следования с задающими связями

Рис. 9.5. Матрица следования с задающими связями

Определение 9.1. Назовем все связи по информации, обусловленные исходным видом графа G, задающими связями.

Определение 9.2. Путями в графе G будем называть последовательности вершин вида вь а2, ..., as такие, что для любой пары соседних вершин а, и ai+l существует дуга, исходящая из вершины я, и входящая в вершину дж. Будем считать все пути в графе G допустимыми, т.е. реально существующими ветвями отображаемой программы.

Определение 9.3. Длиной пути в информационном графе G назовем сумму весов вершин, составляющих этот путь.

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

Если в графе G есть дуга, исходящая из вершины а и входящая в вершину Ь, т.е. существует задающая связь а Ь, а также есть дуга, исходящая из вершины b и входящая в вершину с, т.е. существует задающая связь b —> с, но нет задающей связи а —> с, то последовательный порядок выполнения работ а ис определяется двумя указанными задающими связями. Иными словами, граф G можно дополнить дугой, соответствующей связи а -> с, что только подтвердит заданную частичную упорядоченность работ.

Определение 9.5. Множество связей, которые введены направленно внутри всех пар работ, принадлежащих одному пути в графе Си не связанных задающими связями, назовем множеством транзитивных связей. Транзитивные связи определяются задающими связями.

Алгоритм 9.1. Дополнения треугольной матрицы S транзитивными связями:

  • 1. Организуем просмотр сверху вниз строк матрицы следования S.
  • 2. В очередной /-й строке организуем просмотр элементов в порядке увеличения j номеров столбцов.
  • 3. Если (/, у) = 1, складываем строки i и j по правилу операции дизъюнкции.
  • 4. Если исходная матрица следования S не треугольная, последовательный просмотр ее строк производится неоднократно до установления факта неизменности окончательно полученной матрицы.

Конец алгоритма.

В представленном выше примере после введения всех транзитивных связей матрица следования S примет вид, представленный на рис. 9.6 (введенные транзитивные связи выделены курсивом).

Матрица следования с транзитивными связями

Рис. 9.6. Матрица следования с транзитивными связями

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

Например, пусть задан граф G на рис. 9.7.

После первого шага преобразования S принимает вид, показанный на рис. 9.8.

После второго шага преобразования S принимает вид, показанный на рис. 9.9.

Граф алгоритма и матрица следования

Рис. 9.7. Граф алгоритма и матрица следования

Первый шаг обнаружения контура

Рис. 9.8. Первый шаг обнаружения контура

Обнаружение контура

Рис. 9.9. Обнаружение контура

Поскольку на главной диагонали матрицы появились единицы, то граф G содержит циклы (контуры). Из рисунка графа виден цикл 2—>6—>3—>5—>2. «Участники» цикла отмечены единицами на главной диагонали.

Определение 9.6. Работы а и b будем называть взаимно независимыми, если в матрице следования S выполняется условие (а, Ь) = = (Ь, а) = 0.

Определение 9.7. Работы {а,}, / = 1, ..., s образуют полное множество взаимно независимых работ (ПМВНР), если для любой работы j ? {я,} существует задающая или транзитивная связь (яй,у) = 1 или (/', av) = 1 (p, v е {1, ..., s}).

Например, для графа G, представленного на рис. 9.1, после введения транзитивных связей, что учтено в матрице следования на рис. 9.6, можно установить следующие ПМВНР: {1, 2}, {2, 3, 4}, {3,4, 5}, {2,3,6}, {3, 5,6,7}, {8}.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >