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

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

Суммарное ускорение: в 1,9 раза

5.5.3 Программа "Модифицированный SOR"

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

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

 

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-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+1, J+1) B(I,J) = A(I,J) !$OMP END ORDERED EPS = 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 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+1, J+1) B(I,J) = A(I,J) !$OMP END ORDERED EPS = MAX (EPS, ABS(S - B(I, J))) !$OMP END DO !$OMP END PARALLEL 21 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 раза

5.5.4 Программа "Модифицированный Якоби"

Данный пример приведен для того, чтобы показать работу "Эксперта", при установке директивы NOWAIT. Исходная программа "Якоби" была изменена, чтобы проверка установки NOWAIT была успешна. Работа "Эксперта" на этом примере повторяет действия из пункта 5.5.1 за исключением того, что проверка установки NOWAIT даст положительный результат.

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

 

PROGRAM JAC

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

 

Выходная программа

 

program jac

parameter (l = 8,itmax = 20)

real a(l,l),eps,maxeps,b(l,l),c(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 END DO

!$OMP END PARALLEL

do it = 1,itmax

eps = 0

!variable EPS is used for calculation of maximum value

!$OMP PARALLEL PRIVATE(i)

!$OMP DO

do j = 2,l - 1

do i = 2,l - 1

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

enddo

enddo

!Copying shadow elements of array A from

!neighbouring processors before loop execution

!$OMP END DO NOWAIT

!$OMP DO

do j = 2,l - 1

do i = 2,l - 1

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

&1)) / 4

enddo

enddo

!$OMP END DO

!$OMP END PARALLEL

print 200, it,0

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

if (0.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

 

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

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

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

 

Заключение

 

В рамках дипломной работы был реализован "Эксперт по распараллеливанию на мультипроцессор", как компонент "Системы автоматизации распараллеливания".

Работа системы была протестирована на примерах, описанных в пункте 5.5. В качестве выходного результата формируется файл с выходной программой, а также файл, описывающий пошаговые действия "Эксперта" с аргументированием причины формирования выходного файла, а также подсчитывающего ускорение программы.

Проект реализован в программе Visual Studio.NET на языке C++. Общий объем программного кода, реализующего "Эксперт"- свыше 1800 строк.