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



              

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


Граф G — взвешенный, ориентированный и не содержит контуров. (Т.к. время выполнения алгоритма конечно, то программные циклы либо погружены внутрь работ, либо развёрнуты.)

Например, представим себе информационный граф, соответствующий скалярному умножению векторов заданной длины: A = B ? C способом "пирамиды", В = {b1 , ... , b8}, C = {c1 , ... , c8}. Схема счёта показана на рис. 7.2.

Схема счёта "пирамидой"

Рис. 7.2.  Схема счёта "пирамидой"

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

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

Рис. 7.3.  Информационный граф — "пирамида"

Мы рассмотрели составление информационных графов. Можно рассматривать информационно-логические графы, если учитывать альтернативные ветви алгоритмов.

Например, может быть целесообразным следующее разбиение программы (алгоритма) на модули (работы):

F = F1(X1; X2) if A then F2(X2; X3) else F3(X1;X4) F4(X1, X3, X4; Y).

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

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

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

Преемственность информации (1

2), а также (1
3), при наличии "жирной" стрелки "по управлению" можно не указывать, так как частичная упорядоченность работ в таком случае полностью определена.

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

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




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