Система автоматизации распараллеливания отображения на мультипроцессор (стр. 7 из 9)

!$OMPBARRIER

Таким образом, все нити входят в параллельный регион. Отрабатывает 1-я нить со своей частью витков внутреннего цикла. Вступает в работу 2-я нить, работают обе нити, причем 1-я со 2-м значением итератора, а 2-я с первым и т.д. Пример функционирования конвейера показан на Рис. 10.

Рис. 10. Вычисление цикла с конвейерной зависимостью для 2-х мерного случая. Квадраты – области элементов массива; цифра - № нити, которая вычислит эту область; цифра в скобках – шаг работы конвейера, на котором вычислится область.

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

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

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

PROGRAMJAC

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

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

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

(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

3) Второй шаг

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

!$OMP PARALLEL PRIVATE (I)!$OMP DODO 1 J = 1, LDO 1 I = 1, LA(I, J) = 0.IF(I.EQ.1 .OR. J.EQ.1 .OR. I.EQ.L .OR. J.EQ.L) THENB(I, J) = 0.ELSEB(I, J) = ( 1. + I + J )ENDIFENDDOENDDO!$OMP END DO!$OMP END PARALLEL	DO 1 J = 1, L!$OMP PARALLEL!$OMP DODO 1 I = 1, LA(I, J) = 0.IF(I.EQ.1 .OR. J.EQ.1 .OR. I.EQ.L .OR. J.EQ.L) THENB(I, J) = 0.ELSEB(I, J) = ( 1. + I + J )ENDIFENDDO!$OMP END DOENDDO!$OMP END PARALLEL
Стоимость = 6*8*8/4 + 14 = 110Количество приватных = 2Время инициализации = 5Время синхронизации переменных и удаления региона = 7Итого: 14	Стоимость = 8*(6*8/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-1DO 21 I = 2, L-1EPS = 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-1EPS = MAX ( EPS, ABS( B( I, J) - A( I, J)))A(I, J) = B(I, J)!$OMP END DO!$OMP END PARALLEL21 CONTINUE
Стоимость = 5*6*6/4+16=61Количество приватных = 3Время инициализации = 5Время синхронизации переменных и удаления региона = 8Итого: 16	Стоимость = 6*(5*6/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 DODO 22 J = 2, L-1DO 22 I = 2, L-1B(I, J) = (A( I-1, J ) + A( I, J-1 ) + A( I+1, J)+ A( I, J+1 )) / 422 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-1EPS = MAX ( EPS, ABS( B( I, J) - A( I, J)))A(I, J) = B(I, J)!$OMP END DO!$OMP END PARALLEL21 CONTINUE
Стоимость = 9*6*6/4+14=95Количество приватных = 2Время инициализации = 5Время синхронизации переменных и удаления региона = 7Итого: 14	Стоимость = 6*(9*6/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) Шаг 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

do 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 ENDDO

!OMP END PARALLEL

do it = 1,itmax

eps = 0

!variable EPS is used for calculation of maximum value

!OMP PARALLEL PRIVATE(i)

!OMP DO REDUCTION(MAX:eps)

do j = 2,l - 1

do i = 2,l - 1

eps = max (eps,abs (b(i,j) - a(i,j)))

a(i,j) = b(i,j)

enddo

enddo

!Copying shadow elements of array A from

!neighbouring processors before loop execution

!OMP ENDDO

!OMP DO

do j = 2,l - 1

do i = 2,l - 1

b(i,j) = (a(i - 1,j) + a(i,j - 1) + a(i + 1,j) + a(i,j +

&1)) / 4

enddo

enddo

!OMP ENDDO

!OMP END PARALLEL

print 200, it,eps

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

if (eps .lt. 5.000000e-008) goto 3

enddo

3 open (unit = 3,file = 'JAC.DAT',form = 'FORMATTED',status = 'UNKNO

&WN')

write (unit = 3,fmt = *) b

close (unit = 3)

end

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

Общее время последовательного выполнения: 10547 у.е.

Общее время параллельного выполнения (4 нити): 3231 у.е

Суммарное ускорение: в 3,26 раза

5.5.2 Программа "Sor"

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

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

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

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

(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