Понятие минимальной параллельной формы.
Параллельные алгоритмы (ПА).
Любая параллельная вычислительная система может быть представлена как совокупность функционально независимых обрабатывающих устройств, осуществляющих обработку информации одновременно. Алгоритм, для реализации на такой вычислительной системе (ВС) должен быть представлен в виде последовательности групп операций, причем все операции одной группы независимы и могут быть выполнены на любом обрабатывающем устройстве системы.
Каждая группа операций (ярус) зависит либо от исходных данных, либо от результатов выполнения предыдущих групп. Группы выполняются последовательно. Представленный, в таком виде алгоритм называется параллельным. Он находится в «параллельной форме».
Каждая группа – ярус ПФ.
Общее число ярусов называется высотой параллельной формы.
Максимальное число операций в ярусе называется шириной параллельной формы.
Теоретически такой алгоритм может быть реализован на параллельной ВС, за время, пропорциональное высоте параллельной формы.
Среди всех возможных параллельных форм одного алгоритма имеется одна или несколько форм минимальной высоты, такие формы называются максимальными и определяют минимально возможное время выполнения алгоритма на ВС.
Метод координат.
*Этот метод предполагает, что пространство независимых итераций следует искать в форме гиперплоскостей, параллельных одной из координатных плоскостей. Метод координат допускает также, в случае необходимости, введение вспомогательных переменных и изменение порядка следования операторов в теле цикла.
Наиболее подходит для систем типа SIMD.
Р
ассмотрим
следующий пример:
Исходный цикл:
DO 24 I=2,M
DO 24 J=1,N
21 A(I,J)=B(I,J)+C(I)
22 C(I)=B(I+1,J)
23 B(I,J)=A(I+1,J)*2
24 CONTINUE
Методом координат этот цикл будет преобразован следующим образом:
DO 24 I=1,N
DO 24 SIM FOR ALL I {I: 2 ≤ I ≤ M}
21 A(I,J)=B(I,J)+C(I)
23 B(I,J)=TEMP(I)**2
22 C(I)=B(I-1,J)
24 CONTINUE
Здесь, в отличии от метода гиперплоскостей, употребляется конструкция SIM.
SIM конструкция: тело цикла можно выполнять параллельно для нескольких итераций, но необходимо пооператорная синхронизация, т.е. параллельно выполняется первый оператор цикла для всех итераций, и только по окончании выполнения этого оператора во всех итерациях осуществляется переход ко второму оператору и так далее.
Из примера видно, что значения, вычисленные оператором 23 в i-той итерации используется в операторе 22 в i+1-ой итерации, что и мешает их независимой работе.
Из этого примера так же видно, что для эквивалентности исходного и полученного цикла пришлось вводить дополнительную переменную TEMP и менять метами 23 и 22 операторы, то есть осуществлять неформальные преобразования.
«+»: 1. Если рассмотренный пример
решать методом гиперплоскостей, то при
переходе к новым переменным
,
,
получаем M+N-2
повторений, а для метода координат
- N повторений.
2. Метод координат не требует сложных преобразований индексов.
3. Метод применим и для простых циклов. Наиболее целесообразно использовать метод координат при распараллеливании в системах класса SIMD.
«-»: Сильная зависимость от архитектуры вычислений.
Рассмотренный ранее пример для метода гиперплоскостей не может быть решен методом координат. Для каждого вида цикла подходит тот или иной метод.