99 Continue

Вычисляет среднее арифметическое между четырьмя точками.

Уравнение плоскости: 2*I+J+K = const

Для перехода к параллельному циклу используем переменные:

1 конструкция (прямое)	2 конструкция (обратное)	Результирующий (параллельный) цикл
I1, J1, K1: I1=2*I+J+K J1=I K1=K	I, J, K I = J1 J=I1-2*J1-K1 K=K1	DO 99 I=6,2*L+N+M DO 99 CONC FOR ALL (J1, K1)  { ( J1, K1): 1 ≤ J1 ≤ K1, 2 ≤ I1-2*J1-K1 ≤ M, 2 ≤ K1 ≤ N } (тело цикла для всех точек будет выполняться параллельно и независимо, причем для каждой точки может быть свой процессор; если количество процессоров соответствует количеству точек – получаем максимальное ускорение) V ( I1-2*J1-K1, K1 ) = ( V ( I1-2*J1-K1+1,K1 ) + V (I1-2*J1-K1, K1+1 ) + V (I1-2*J1-K1, K1 ) + V (I1-2*J1-K1, K1-1 ) ) *0.25 99 CONTINUE

В 1 конструкции количество повторений равно L*(M-1)*(N-1)

Во 2 новой конструкции 2*L+M+N-5 раз. Исходное пространство итераций сворачивается с 1-го по 3-х мерное. Выигрыш при больших M-N.

Общая постановка задачи:

DO A I¹=l¹, U¹

…

DO A Iⁿ=lⁿ, Uⁿ

<тело цикла>

A CONTINUE

Для использования метода гиперплоскостей необходимо, чтобы тело цикла не содержало:

• операторов ввода–вывода

• передач управления вне цикла

• обращений к процедурам и функциям, которые изменяют переменные в теле цикла.

Индексные выражения в операторах тела цикла должны иметь вид lⁱ+mⁱ, где lⁱ – i-я переменная, mⁱ - i-я константа. Разрешено I+2; запрещено I+J, I*2, I*J.

В результате применения метода гиперплоскостей исходный цикл преобразуется к виду:

DO A J¹=L¹, M¹

…

DO A J^k=L^k,M^k

DO A CONC FOR ALL (J^k+1, … Jⁿ)  S_Y¹_...Yⁿ

< тело цикла>

A CONTINUE

Максимальный выигрыш можно получить, когда все итерации в исходном цикле выполняются полностью, т.е. нет принудительного прекращения выполнения тела цикла.

Происходит свертывание пространственных операций, то есть изменение размерности на N-K

Для нахождения уравнения гиперплоскости строится взаимно-однозначное отображение переменных в теле исходного цикла в новые переменные. Это отображение ищется в виде:

Для нахождения коэффициентов а_jⁿ решается задача линейного целочисленного программирования, в которой формулируется ряд ограничений на коэффициенты а: в исходном и результирующем цикле все использования переменных должны следовать за их генерациями в теле цикла.

a=b. (a – использование, b – генерация.)

I₁ = a_{11 *} I + a_{12 *} J

J₂ = a_{21 *} I + a_{22 *} J

[-1 ÷ +1]

+1 – поворот на 45 градусов против часовой

-1 – по часовой.

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

«+»: метод хорошо формализован и, следовательно, он может быть использован в трансляторах с параллельных языков программирования для автоматического распараллеливания циклов; для каждой точки вычисления могут выполняться на отдельном процессоре и не требуется никакой синхронизации; мах. выигрыш если пространство итераций достаточно большое.

«-»: сложность получения алгоритма гиперплоскости а также неприменимость для некоторых видов циклов (в частности для простых циклов); неравномерность загрузки процессора;

МЕТОД КООРДИНАТ.

*Этот метод предполагает, что пространство независимых итераций следует искать в форме гиперплоскостей, параллельных одной из координатных плоскостей. Метод координат допускает также, в случае необходимости, введение вспомогательных переменных и изменение порядка следования операторов в теле цикла.

Наиболее подходит для систем типа 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.

«-»: Сильная зависимость от архитектуры вычислений.

Рассмотренный ранее пример для метода гиперплоскостей не может быть решен методом координат. Для каждого вида цикла подходит тот или иной метод.

МЕТОД ПАРАЛЛЕЛЕПИПЕДОВ.

В этом методе подмножества независимо выполняемых операций ищутся в форме прямоугольных параллелепипедов. Данный метод так же применим и для простых циклов.

ПРИМЕР:

DO 2 I=1,15

X(I)=X(G*I-27)

2 CONTINUE

В этом примере рассматривается одномерный случай пространства итераций, и в результате параллельный счет осуществляется для точек, принадлежащий отрезку прямой длиной = 4.

DO 2 I=1, 4

DO 2 CONC FOR ALL J  { 4*(I-1) ≤ J ≤ MIN {4*I,15} }

X(I)=X(G*I-27)

2 CONTINUE

Общая постановка задачи.

Пусть I={I₁,I₂,…,I_n} – исходное пространство итераций. Требуется найти такие целые числа, P₁,P₂,…,P_n, называемые ребрами параллелепипеда, при которых исходные конструкции вида

DO 1 I₁=1,R₁

DO 1 I₂=1,R₂

……

DO 1 I_n=1,R_n

<ТЕЛО ЦИКЛА>

1 CONTINUE

ставится в соответствие эквивалентная конструкция вида

DO 2 CONC FOR ALL J  {1,N}

DO 2 K_j=1, P_j

DO 2 I₁=K₁, R₁, P₁

DO 2 I₂=K₂, R₂, P₂

……

DO 2 I_n=K_n, R_n, P_n

<ТЕЛО ЦИКЛА>

2 CONTINUE

Искомая конструкция создает для каждого набора K_i…K_n параллельную ветвь, представляющую собой вложенный цикл с шагами исполнения P₁ ….P_n. (1≤ K_j≤ P_j)

Для эквивалентности исходного и полученного цикла достаточно, чтобы в каждом из P₁*P₂…*P_n параллелепипедов не содержалось конкуренционно зависимых итераций, а так же порядок выполнения итераций группами, состоящими из параллелепипедов, был таков, чтобы все использования выполнялись после соответствующих генераций.

Поитерационая синхронизация метода: в каждой ветви осуществляется ожидание выполнения всех итераций одного и того же параллелепипеда.

Если не требовать выполнения условия прямоугольности параллелепипедов, то этот метод является естественным методом гиперплоскостей (гиперплоскость получается как параллелепипед, одна из сторон которого имеет длину =1 , а все остальные совпадают с границей R_k).

Данный метод может использоваться для простых циклов.

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

МЕТОД ПИРАМИД.

*В методе пирамид в исходном пространстве итераций выделяются независимые параллельные ветви, каждая из которых представляет собою «дерево» зависимых итераций, корень которого – одна из результирующих итераций исходного цикла. Если индексные выражения в теле цикла линейно зависимы, то итерации каждой параллельной ветви образуют пирамиду (в случае двумерного пространства итераций это – угол между некоторыми крайними векторами). Очевидно, что при таком порядке формирования ветвей в них неизбежно дублирование некоторых итераций.

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

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

Для этого:

1. в цикле выбираются все результирующие итерации. Каждая такая итерация служит основой отдельной параллельной ветви.

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

«-»:необходимость дублирования некоторых операций в разных ветвях.

При ленейно-независимых индексных выражениях итерации каждой ветви образуют пирамиду в пространстве итераций, «натянутую на векторы», задающие направление зависимостей внутри итераций.

ПРИМЕР:

DO 10 I₁=1,R₁

DO 10 I₂=1,R₂

<ТЕЛО ЦИКЛА>