Параллельное программирование



              

Граф-схемы параллельных алгоритмов


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

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

F = F1(X1 , X2 ; X3 , X4 ) F2 (X2 ; X5 ) F3 (X3 ; X6 ) F4 (X1 , X4 ; X7 ) F5 (X3 , X4 , X5 ; X8 ) F6 (X3 , X4 , X7 ; X9 ) F7 (X5 , X7 ; X10) F8 (X6 , X8 , X9 , X10 ; Y), где точкой с запятой отделены входные данные от выходных, X = {X1, X2} — исходные данные задачи, Y — выходные данные или результат.

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

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

Пусть относительно данного алгоритма и предполагаемой ВС нам известны следующие оценки T = {t1, t2, ... , t8}.

Тогда, чтобы отразить прохождение обрабатываемой информации и выявить возможности распараллеливания, представим информационную граф-схему алгоритма или информационный граф G (рис. 7.1). Вершины соответствуют работам. Дуги отражают частичную упорядоченность работ.

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

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

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

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


Содержание  Назад  Вперед