(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
3) Второй шаг
На этом шаге будет устроен перебор различных вариантов распараллеливания. Рассмотрим их, группируя по регионам. Все варианты будем рассматривать при числе процессоров=4.
1-й регион: циклы (1) и (2). Здесь будет рассмотрено 3 варианта, время последовательного исполнения 1 витка = 1.
| !$OMP PARALLEL PRIVATE(I)!$OMP DODO 1 J = 1, NDO 1 I = 1, NIF ( I .EQ.J) THEN A( I, J ) = N + 2ELSE A( I, J ) = -1.0ENDIF1CONTINUE!$OMP END DO!$OMP END PARALLEL | DO 1 J = 1, N!$OMP PARALLEL!$OMP DODO 1 I = 1, NIF ( I .EQ.J) THEN A( I, J ) = N + 2ELSE A( I, J ) = -1.0ENDIF!$OMP END DO!$OMP END PARALLEL1 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-1DO 21 I = 2, N-1!$OMP ORDEREDS = 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 ORDERED21CONTINUE!$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 ORDEREDS = 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 PARALLEL21 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 BARRIERDO 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)!$ ENDIFDO 21 I = 2, N-1S = 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 PARALLEL21 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 конвейером.
4) Шаг 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
Для данной программы будет выдана следующая оценка производительности:
Общее время последовательного выполнения: 28343 у.е.
Общее время параллельного выполнения (4 нити): 14880 у.е.
Суммарное ускорение: в 1,9 раза
Данный пример приведен для того, чтобы показать работу "Эксперта" на зависимостях по данным в массиве, для которого невозможно применение конвейера.
1) Листинг последовательной программы
PROGRAM SOR
PARAMETER ( N = 10 )
REAL A( N, N ), B(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+1, J+1)
B(I,J) = A(I,J)
EPS = MAX ( EPS, ABS( S - B( 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
2) Работа "Эксперта"
Для данной программы будут произведены действия, аналогичные тем, что описаны в пункте 5.5.2. Остановимся лишь на отличиях в шаге 2 и выходных данных.
2-й регион: циклы (4) и (5). Здесь будет рассмотрено 3 варианта, время последовательного исполнения первых 3 директив = 19, 4-й директивы = 4:
| !$OMP PARALLEL PRIVATE(S) PRIVATE(I)!$OMP DO REDUCTION(EPS,MAX)DO 21 J = 2, N-1DO 21 I = 2, N-1!$OMP ORDEREDS = 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+1, J+1)B(I,J) = A(I,J)!$OMP END ORDEREDEPS = MAX ( EPS, ABS( S - B( I, J )))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 ORDEREDS = 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+1, J+1)B(I,J) = A(I,J)!$OMP END ORDEREDEPS = MAX ( EPS, ABS( S - B( I, J )))!$OMP END DO!$OMP END PARALLEL21 CONTINUE |
| Стоимость = 19*8*8 + 4*8*8/4 + 18 = 1298Количество приватных = 4Время инициализации = 5Время синхронизации переменных и удаления региона = 9Итого: 18 | Стоимость = 8*(19*8 + 4*8/4 + 16) = 1408Количество приватных = 3Время инициализации = 5Время синхронизации переменных и удаления региона = 8Итого: 16 |
Рис. 17. Сравнение вариантов распараллеливания в 2-м регионе программы "модифицированный SOR".
На Рис. 17 показаны возможные варианты параллелизма для данного региона. Как видно, случай с конвейером не будет рассмотрен, из-за того, что элемент A(I,J) зависит от "бокового" элемента A(I+1,J+1). Стоимость последовательная = 23*8*8=1472, следовательно, будет выбран 1-й вариант.
На выходе получим следующую программу:
program sor
parameter (n = 10)
real a(n,n),b(n,n),eps,maxeps,w
integer itmax
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(i) SHARED(a) PRIVATE(s)
!$OMP DO ORDERED REDUCTION(MAX:eps)
do j = 2,n - 1
do i = 2,n - 1
!$OMP ORDERED
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 + 1,j + 1)
b(i,j) = a(i,j)
!$OMP END ORDERED
eps = max (eps,abs (s - b(i,j)))
enddo
enddo
!$OMP END DO
!$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
Общее время последовательного выполнения: 29623 у.е.
Общее время параллельного выполнения (4 нити): 26143 у.е.
Суммарное ускорение: в 1,13 раза
Данный пример приведен для того, чтобы показать работу "Эксперта", при установке директивы NOWAIT. Исходная программа "Якоби" была изменена, чтобы проверка установки NOWAIT была успешна. Работа "Эксперта" на этом примере повторяет действия из пункта 5.5.1 за исключением того, что проверка установки NOWAITдаст положительный результат.
1) Листинг последовательной программы
PROGRAMJAC
PARAMETER(L=8, ITMAX=20)
REAL A(L,L), EPS, MAXEPS, B(L,L), C(L,L)
C arrays A and B with block distribution
PRINT *, '********** TEST_JACOBI **********'
MAXEPS = 0.5E - 7
Cnest of two parallel loops, iteration (i,j) will be executed on
Cprocessor, which is owner of element A(i,j)
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
1 CONTINUE
DO 2 IT = 1, ITMAX
EPS = 0.
Cvariable EPS is used for calculation of maximum value
DO 21 J = 2, L-1
DO 21 I = 2, L-1
A(I, J) = B(I, J)
21 CONTINUE
CCopying shadow elements of array A from
Cneighbouring processors before loop execution
DO 22 J = 2, L-1
DO 22 I = 2, L-1
A(I, J) = (C( I-1, J ) + C( I, J-1 ) + C( I+1, J)+
* C( 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
2) Выходная программа
program jac
parameter (l = 8,itmax = 20)