Примеры работы алгоритма

6 7 8 9 10 11 12

5.5.1 Программа "Якоби"

Листинг последовательной программы

PROGRAM JAC

PARAMETER (L=8, ITMAX=20)

REAL A(L,L), EPS, MAXEPS, B(L,L)

PRINT *, '********** TEST_JACOBI **********'

MAXEPS = 0.5E - 7

DO 1 J = 1, L(1)

DO 1 I = 1, L(2)

A(I, J) = 0. IF(I.EQ.1.OR. J.EQ.1.OR. I.EQ.L.OR. J.EQ.L) THEN

B(I, J) = 0.

ELSE

B(I, J) = (1. + I + J) ENDIF

1 CONTINUE

DO 2 IT = 1, ITMAX(3)

EPS = 0.

DO 21 J = 2, L-1(4)

DO 21 I = 2, L-1(5)

EPS = MAX (EPS, ABS(B(I, J) - A(I, J)))

A(I, J) = B(I, J)

21 CONTINUE

DO 22 J = 2, L-1(6)

DO 22 I = 2, L-1(7)

B(I, J) = (A(I-1, J) + A(I, J-1) + A(I+1, J)+ A(I, J+1)) / 4

22 CONTINUE

PRINT 200, IT, EPS

200 FORMAT(' IT = ',I4, ' EPS = ', E14.7)

IF (EPS. LT. MAXEPS) GO TO 3

2 CONTINUE

3 OPEN (3, FILE='JAC.DAT', FORM='FORMATTED', STATUS='UNKNOWN')

WRITE (3,*) B CLOSE (3) END

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

После первого шага в первом внутреннем представлении помеченным в листинге последовательной программы циклам будут соответствовать следующие вершины:

(1) Тип:ППЦ,уровень = 0, число итераций = 8

Использование переменных:

Имя: i. Пометки: PRIVATE, SET, SHARED, NO

Имя: j. Пометки: PRIVATE, IND, SHARED, NO

Имя: a. Пометки: PRIVATE, POS, SHARED, DEF

Имя: b. Пометки: PRIVATE, POS, SHARED, DEF

(2) Тип:ППЦ,уровень = 1, число итераций = 8

Использование переменных:

Имя: i. Пометки: PRIVATE, IND, SHARED, NO

Имя: j. Пометки: PRIVATE, POS, SHARED, DEF

Имя: a. Пометки: PRIVATE, POS, SHARED, DEF

Имя: b. Пометки: PRIVATE, POS, SHARED, DEF

(3) Тип:ЦНР,уровень = 0, число итераций = 20

Использование переменных:

Имя: eps. Пометки: PRIVATE, SET, SHARED, NO

Имя: j. Пометки: PRIVATE, SET, SHARED, NO

Имя: i. Пометки: PRIVATE, SET, SHARED, NO

Имя: b. Пометки: PRIVATE, NO, SHARED, SET ORDERED!

Имя: a. Пометки: PRIVATE, NO, SHARED, SET ORDERED!

(4) Тип:ППЦ,уровень = 1, число итераций = 6

Использование переменных:

Имя: i. Пометки: PRIVATE, SET, SHARED, NO

Имя: eps. Пометки: REDUCTION, MAX, SHARED, NO

Имя: b. Пометки: PRIVATE, POS, SHARED, DEF

Имя: j. Пометки: PRIVATE, IND, SHARED, NO

Имя: a. Пометки: PRIVATE, POS, SHARED, DEF

(5) Тип:ППЦ,уровень = 2, число итераций = 6

Использование переменных:

Имя: eps. Пометки: REDUCTION, MAX, SHARED, NO

Имя: b. Пометки: PRIVATE, POS, SHARED, DEF

Имя: i. Пометки: PRIVATE, IND, SHARED, NO

Имя: j. Пометки: PRIVATE, POS, SHARED, DEF

Имя: a. Пометки: PRIVATE, POS, SHARED, DEF

(6) Тип:ППЦ,уровень = 1, число итераций = 6

Использование переменных:

Имя: i. Пометки: PRIVATE, SET, SHARED, NO

Имя: a. Пометки: PRIVATE, POS, SHARED, DEF

Имя: j. Пометки: PRIVATE, IND, SHARED, NO

Имя: b. Пометки: PRIVATE, POS, SHARED, DEF

(7) Тип:ППЦ,уровень = 2, число итераций = 6

Использование переменных:

Имя: a. Пометки: PRIVATE, POS, SHARED, DEF

Имя: i. Пометки: PRIVATE, IND, SHARED, NO

Имя: j. Пометки: PRIVATE, POS, SHARED, DEF

Имя: b. Пометки: PRIVATE, POS, SHARED, DEF

Второй шаг

На этом шаге будет устроен перебор различных вариантов распараллеливания. Рассмотрим их, группируя по регионам. Все варианты будем рассматривать при числе процессоров=4. 1-й регион: циклы (1) и (2). Здесь будет рассмотрено 3 варианта, время исполнения 1 витка внутреннего цикла =6, L=8.

!$OMP PARALLEL PRIVATE (I) !$OMP DO DO 1 J = 1, L DO 1 I = 1, L A(I, J) = 0. IF(I.EQ.1.OR. J.EQ.1.OR. I.EQ.L.OR. J.EQ.L) THEN B(I, J) = 0. ELSE B(I, J) = (1. + I + J) ENDIF ENDDO ENDDO !$OMP END DO !$OMP END PARALLEL	DO 1 J = 1, L !$OMP PARALLEL !$OMP DO DO 1 I = 1, L A(I, J) = 0. IF(I.EQ.1.OR. J.EQ.1.OR. I.EQ.L.OR. J.EQ.L) THEN B(I, J) = 0. ELSE B(I, J) = (1. + I + J) ENDIF ENDDO !$OMP END DO ENDDO !$OMP END PARALLEL
Стоимость = 688/4 + 14 = 110 Количество приватных = 2 Время инициализации = 5 Время синхронизации переменных и удаления региона = 7 Итого: 14	Стоимость = 8(68/4 + 12) = 192 Количество приватных = 1 Время инициализации = 5 Время синхронизации переменных и удаления региона = 6 Итого: 12

Рис. 11. Сравнение вариантов распараллеливания в 1-м регионе программы "Якоби".

На Рис. 11 показаны возможные рассматриваемые варианты распараллеливания: цикла по J в левой части и цикла по I в левой части. Пункт "Стоимость" отражает подсчет оценочной функции. Она берется, как сумма "параллельного" вычисления цикла и "дополнительных" расходов, подсчитанных в пункте "Итого". Так как стоимость последовательная = 6*8*8 = 384, будет выбран вариант, показанный в левой части.

2-й регион: циклы (4) и (5). Время исполнения 1 витка внутреннего цикла =5.

!$OMP PARALLEL PRIVATE (I) !$OMP DO REDUCTION(EPS,MAX) DO 21 J = 2, L-1 DO 21 I = 2, L-1 EPS = MAX (EPS, ABS(B(I, J) - A(I, J))) A(I, J) = B(I, J) 21 CONTINUE !$OMP END DO !$OMP END PARALLEL	DO 21 J = 2, L-1 !$OMP PARALLEL !$OMP DO REDUCTION(EPS,MAX) DO 21 I = 2, L-1 EPS = MAX (EPS, ABS(B(I, J) - A(I, J))) A(I, J) = B(I, J) !$OMP END DO !$OMP END PARALLEL 21 CONTINUE
Стоимость = 566/4+16=61 Количество приватных = 3 Время инициализации = 5 Время синхронизации переменных и удаления региона = 8 Итого: 16	Стоимость = 6(56/4+14)=129 Количество приватных = 2 Время инициализации = 5 Время синхронизации переменных и удаления региона = 7 Итого: 14

Рис. 12. Сравнение вариантов распараллеливания в 2-м регионе программы "Якоби".

На Рис. 12 показаны возможные рассматриваемые варианты распараллеливания: цикла по J в левой части и цикла по I в левой части. Стоимость последовательная = 6*6*5= 180, следовательно, будет выбран вариант, описанный в левой части Рис. 12. Редукционная переменная считается как приватная.

3-й регион: циклы (6) и (7). Время исполнения 1 витка внутреннего цикла =9.

!$OMP PARALLEL PRIVATE (I) !$OMP DO DO 22 J = 2, L-1 DO 22 I = 2, L-1 B(I, J) = (A(I-1, J) + A(I, J-1) + A(I+1, J)+ A(I, J+1)) / 4 22 CONTINUE !$OMP END DO !$OMP END PARALLEL	DO 21 J = 2, L-1 !$OMP PARALLEL !$OMP DO SHARED(J), REDUCTION(EPS,MAX) DO 21 I = 2, L-1 EPS = MAX (EPS, ABS(B(I, J) - A(I, J))) A(I, J) = B(I, J) !$OMP END DO !$OMP END PARALLEL 21 CONTINUE
Стоимость = 966/4+14=95 Количество приватных = 2 Время инициализации = 5 Время синхронизации переменных и удаления региона = 7 Итого: 14	Стоимость = 6(96/4+12)=153 Количество приватных = 1 Время инициализации = 5 Время синхронизации переменных и удаления региона = 7 Итого: 12

Рис. 13. Сравнение вариантов распараллеливания в 3-м регионе программы "Якоби".

На Рис. 13 показаны возможные рассматриваемые варианты распараллеливания: цикла по J в левой части и цикла по I в левой части. Стоимость последовательная = 9*6*6=324, следовательно, будет выбран 1-й вариант из Рис. 13.

2-й и 3-й параллельные регионы объединятся в один регион, т.к. нет противоречий по локализации переменных. Проверка на NOWAIT не будет успешна: для обращения A(I, J) = B(I, J) есть обращение B(I, J) = (A(I-1, J) + A(I, J-1) + A(I+1, J)+ A(I, J+1)) / 4 (может возникнуть ситуация, когда одной нити придется использовать "старое" значение массива A во втором цикле).

Шаг 3 и Шаг 4

На шаге 3 не найдется параллельных соседних параллельных регионов для склейки. Из всевозможных альтернативных локализаций ни одна не будет принята, т.к. в любой из них количество приватных переменных (а следовательно и оценочная функция будут расти). Для простановки threadprivate не найдется ни одного приватного массива.

На шаге 4 получим выходную программу:

program jac

parameter (l = 8,itmax = 20)

real a(l,l),eps,maxeps,b(l,l)

! arrays A and B with block distribution

print *, '********** TEST_JACOBI **********'

maxeps = 5.000000e-008

!nest of two parallel loops, iteration (i,j) will be executed on

!processor, which is owner of element A(i,j)

!OMP PARALLEL PRIVATE(i)

!OMP DO

do j = 1,l