2020-01-15
152
Общее время параллельного выполнения (4 нити): 3231 у.е
Суммарное ускорение: в 3,26 раза
5.5.2 Программа "Sor"
Листинг последовательной программы
PROGRAM SOR
PARAMETER (N = 10)
REAL A(N, N), EPS, MAXEPS, W
INTEGER ITMAX
PRINT *, '********** TEST_SOR **********'
ITMAX=20
MAXEPS = 0.5E - 5
W = 0.5
DO 1 J = 1, N
DO 1 I = 1, N
IF (I.EQ.J) THEN
A(I, J) = N + 2
ELSE
A(I, J) = -1.0
ENDIF
1CONTINUE
DO 2 IT = 1, ITMAX
EPS = 0.
DO 21 J = 2, N-1
DO 21 I = 2, N-1
S = A(I, J)
A(I, J) = (W / 4) * (A(I-1, J) + A(I+1, J) + A(I, J-1) +
*A(I, J+1)) + (1-W) * A(I, J)
EPS = MAX (EPS, ABS(S - A(I, J)))
21CONTINUE PRINT 200, IT, EPS
200 FORMAT(' IT = ',I4, ' EPS = ', E14.7)
IF (EPS.LT. MAXEPS) GO TO 4
2CONTINUE
4 OPEN (3, FILE='SOR.DAT', FORM='FORMATTED',STATUS='UNKNOWN')
WRITE (3,*) A CLOSE (3) END
Первое внутреннее представление для циклов
После первого шага в первом внутреннем представлении помеченным в листинге последовательной программы циклам будут соответствовать следующие вершины:
(1) Тип:ППЦ,уровень = 0, число итераций = 8
Использование переменных:
Имя: i. Пометки: PRIVATE, SET, SHARED, NO
Имя: j. Пометки: PRIVATE, IND, SHARED, NO
Имя: a. Пометки: PRIVATE, POS, SHARED, DEF
(2) Тип:ППЦ,уровень = 1, число итераций = 8
Использование переменных:
Имя: i. Пометки: PRIVATE, IND, SHARED, NO
Имя: j. Пометки: PRIVATE, POS, SHARED, DEF
Имя: a. Пометки: PRIVATE, POS, SHARED, DEF
(3) Тип:ЦНР,уровень = 0, число итераций = 20
Использование переменных:
Имя: eps. Пометки: PRIVATE, SET, SHARED, NO
Имя: j. Пометки: PRIVATE, SET, SHARED, NO
Имя: i. Пометки: PRIVATE, SET, SHARED, NO
Имя: a. Пометки: PRIVATE, NO, SHARED, SET ORDERED! PIPELINE!
Имя: s. Пометки: PRIVATE, SET, SHARED, NO
(4) Тип:ППЦ,уровень = 1, число итераций = 6
Использование переменных:
Имя: i. Пометки: PRIVATE, SET, SHARED, NO
Имя: eps. Пометки: REDUCTION, MAX, SHARED, NO
Имя: j. Пометки: PRIVATE, IND, SHARED, NO
Имя: a. Пометки: PRIVATE, NO, SHARED, SET, rw= 2 ORDERED! PIPELINE!
Имя: s. Пометки: PRIVATE, SET, SHARED, NO
(5) Тип:ППЦ,уровень = 2, число итераций = 6
Использование переменных:
Имя: i. Пометки: PRIVATE, IND, SHARED, NO
Имя: j. Пометки: PRIVATE, POS, SHARED, DEF
Имя: eps. Пометки: REDUCTION, MAX, SHARED, NO
Имя: a. Пометки: PRIVATE, NO, SHARED, SET, rw= 2 ORDERED! PIPELINE!
Имя: s. Пометки: PRIVATE, SET, SHARED, NO
Второй шаг
На этом шаге будет устроен перебор различных вариантов распараллеливания. Рассмотрим их, группируя по регионам. Все варианты будем рассматривать при числе процессоров=4.
1-й регион: циклы (1) и (2). Здесь будет рассмотрено 3 варианта, время последовательного исполнения 1 витка = 1.
| !$OMP PARALLEL PRIVATE(I) !$OMP DO DO 1 J = 1, N DO 1 I = 1, N IF (I.EQ.J) THEN A(I, J) = N + 2 ELSE A(I, J) = -1.0 ENDIF 1CONTINUE !$OMP END DO !$OMP END PARALLEL | DO 1 J = 1, N !$OMP PARALLEL !$OMP DO DO 1 I = 1, N IF (I.EQ.J) THEN A(I, J) = N + 2 ELSE A(I, J) = -1.0 ENDIF !$OMP END DO !$OMP END PARALLEL 1 CONTINUE |
| Стоимость = 1*10*10/4 + 14 = 39 Количество приватных = 2 Время инициализации = 5 Время синхронизации переменных и удаления региона = 7 Итого: 14 | Стоимость = 10 * (1*10/ 4 + 12) = 145 Количество приватных = 1 Время инициализации = 5 Время синхронизации переменных и удаления региона = 6 Итого: 12 |
Рис. 14. Сравнение вариантов распараллеливания в 1-м регионе программы "SOR".
На Рис. 14 показаны возможные рассматриваемые варианты распараллеливания: цикла по J в левой части и цикла по I в левой части. Стоимость последовательная = 10*10=100, следовательно, будет выбран вариант, показанный в левой части Рис. 14.
2-й регион: циклы (4) и (5). Здесь будет рассмотрено 4 варианта, время последовательного исполнения 1 витка = 22.
| !$OMP PARALLEL PRIVATE(S) PRIVATE(I) !$OMP DO REDUCTION(EPS,MAX) DO 21 J = 2, N-1 DO 21 I = 2, N-1 !$OMP ORDERED S = A(I, J) A(I, J) = (W / 4) * (A(I-1, J) + A(I+1, J) + A(I, J-1) + *A(I, J+1)) + (1-W) * A(I, J) EPS = MAX (EPS, ABS(S - A(I, J))) !$OMP END ORDERED 21CONTINUE !$OMP END DO !$OMP END PARALLEL | DO 21 J = 2, N-1 !$OMP PARALLEL PRIVATE(S) !$OMP DO REDUCTION(EPS,MAX) DO 21 I = 2, N-1 !$OMP ORDERED S = A(I, J) A(I, J) = (W / 4) * (A(I-1, J) + A(I+1, J) + A(I, J-1) + *A(I, J+1)) + (1-W) * A(I, J) EPS = MAX (EPS, ABS(S - A(I, J)))!$OMP END ORDERED !$OMP END DO !$OMP END PARALLEL 21 CONTINUE |
| Стоимость = 22*8*8 + 18 = 1426 Количество приватных = 4 Время инициализации = 5 Время синхронизации переменных и удаления региона = 9 Итого: 18 | Стоимость = 8*(22*8 + 16) = 1536 Количество приватных = 3 Время инициализации = 5 Время синхронизации переменных и удаления региона = 8 Итого: 16 |
Рис. 15. Сравнение вариантов распараллеливания в 2-м регионе программы "SOR" с директивой ORDERED.
| !$OMP PARALLEL !$ iam = omp_get_thread_num () !$ numt = omp_get_num_threads () !$ ISYNC (IAM) = 0 !$ ILIMIT=MIN(NUMT-1,N-1-2) !$OMP BARRIER DO 21 J = 2, N-1 !$OMP DO PRIVATE(S), REDUCTION(EPS,MAX) !$ IF (IAM.GT. 0.AND. IAM.LE. ILIMIT) THEN !$ DO WHILE (ISYNC(IAM-1).EQ. 0) !$OMP FLUSH(ISYNC) !$ ENDDO !$ ISYNC(IAM-1)=0 !$OMP FLUSH(ISYNC) !$ ENDIF DO 21 I = 2, N-1 S = A(I, J) A(I, J) = (W / 4) * (A(I-1, J) + A(I+1, J) + A(I, J-1) + *A(I, J+1)) + (1-W) * A(I, J) EPS = MAX (EPS, ABS(S - A(I, J))) !$OMP ENDDO NOWAIT !$ IF (IAM.LT. ILIMIT) THEN !$ DO WHILE (ISYNC (IAM).EQ. 1) !$OMP FLUSH (ISYNC) !$ ENDDO !$ ISYNC (IAM)=1 !$OMP FLUSH(ISYNC) !$ ENDIF !$OMP END DO !$OMP BARRIER !$OMP END PARALLEL 21 CONTINUE |
| Стоимость = 22*32+3+9+22 = 738 Количество действий конвейера = 32 Количество приватных = 3 Время инициализации конвейера без учета приватных = 5 + 4 = 9 Время синхронизации переменных и удаления региона = 3+5+4+3+3+4 = 22 (синхронизация приватных + инициализация региона + барьер до первого цикла + по барьеру во время инициализации каждой нити + по барьеру во время инициализации последующей нити + барьер в конце региона) |
Рис. 16. Схема распараллеливания в 2-м регионе программы "SOR" при конвейерном варианте.
На Рис. 15 и Рис. 16 показаны варианты параллелизма, которые будут перебираться "Экспертом". Стоимость последовательная = 22*8*8=1408, следовательно, будет выбран вариант c конвейером.
Шаг 3 и Шаг 4
На шаге 3 не найдется параллельных соседних параллельных регионов для склейки. Из всевозможных альтернативных локализаций ни одна не будет принята, т.к. в любой из них количество приватных переменных (а следовательно, и оценочная функция будут расти). Для простановки threadprivate не найдется ни одного приватного массива.
На шаге 4 получим выходную программу для варианта задачи с 4 процессорами:
program sor
parameter (n = 10)
real a(n,n),eps,maxeps,w
integer itmax
!$INTEGER OMP_GET_NUM_THREADS,OMP_GET_THREAD_NUM
!$INTEGER IAM, NUMT,ISYNC(4)
print *, '********** TEST_SOR **********'
itmax = 20
maxeps = 5.000000e-006
w = 5.000000e-001
!$OMP PARALLEL PRIVATE(i)
!$OMP DO
do j = 1,n
do i = 1,n
if (i.eq. j) then
a(i,j) = n + 2
else
a(i,j) = (-(1.0))
endif
enddo
enddo
!$OMP END DO
!$OMP END PARALLEL
do it = 1,20
eps = 0
!$OMP PARALLEL PRIVATE (IAM,NUMT,ILIMIT) PRIVATE(i) SHARED(a) PRIVATE(s) & &REDUCTION(MAX:eps)
!$ iam = omp_get_thread_num ()
!$ numt = omp_get_num_threads ()
!$ ISYNC (IAM) = 0
!$ ILIMIT=min(NUMT-1,n-1-2)
!$OMP BARRIER
do j = 2,n - 1
!$IF (IAM.GT. 0.AND. IAM.LE. ILIMIT) THEN
!$ DO WHILE (ISYNC(IAM-1).EQ. 0)
!$OMP FLUSH(ISYNC)
!$ ENDDO
!$ ISYNC(IAM-1)=0
!$OMP FLUSH(ISYNC)
!$ ENDIF
!$OMP DO
do i = 2,n - 1
s = a(i,j)
a(i,j) = 5.000000e-001 / 4 * (a(i - 1,j) + a(i + 1,j) + a
&(i,j - 1) + a(i,j + 1)) + (1 - 5.000000e-001) * a(i,j)
eps = max (eps,abs (s - a(i,j)))
enddo
!$OMP ENDDO NOWAIT
!$ IF (IAM.LT. ILIMIT) THEN
!$ DO WHILE (ISYNC (IAM).EQ. 1)
!$OMP FLUSH (ISYNC)
!$ ENDDO
!$ ISYNC (IAM)=1
!$OMP FLUSH(ISYNC)
!$ ENDIF
enddo
!$OMP BARRIER
!$OMP END PARALLEL
print 200, it,eps
200 FORMAT(' IT = ',I4, ' EPS = ', E14.7)
if (eps.lt. 5.000000e-006) goto 4
enddo
4 open (unit = 3,file = 'SOR.DAT',form = 'FORMATTED',status = 'UNKNO
&WN')
write (unit = 3,fmt = *) a
close (unit = 3)
end
Для данной программы будет выдана следующая оценка производительности:
