Каталог Рефератов - Система автоматизации распараллеливания отображения на мультипроцессор

	Информационно-образоательный портал
	Рефераты, курсовые, дипломы, научные работы,



МЕНЮ\|

поиск

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

сли в Программном списке локализации переменных, какой-либо переменная во всех параллельных регионах становится приватным, то в программном списке локализаций переменных данный массив помечается как threadprivate. Для следующих параллельных регионов, использующих данный массив, он объявляется в списке copyin. Установка данных директив дает ускорение за счет отсутствия инициализации private переменных.

Для всех массивов, для которых не проставлены комментарии threadprivate, рассчитываем альтернативную локализации для всей программы, считая переменную приватной, но вычитая стоимость инициализации и синхронизации для массива. Если оценочная функция альтернативной локализации лучше оценочной функции для 2-го внутреннего представления, альтернативная локализация заносится во 2-е внутреннее представление, переменная во всех параллельных регионах становится: private, def, shared, no и помечается как threadprivate.

5.4 Шаг 4. Внесение конечных комментариев в Базу Данных и подсчет ускорения
Данные на входе: База Данных, незаконченное 2-е внутреннее представление.

Данные на выходе: База Данных с комментариями.

Как проходит преобразование входных данных в выходные:

Из 2-го внутреннего представления комментарии переносятся в Базу Данных, соблюдая синтаксис OpenMP. Оценивается общее ускорение.

Алгоритм преобразования входных данных в выходные:

Проходим все вершины в Базе Данных. Каждую вершину пытаемся найти во 2-м внутреннем представлении, в случае успеха проставляем соответствующие комментарии следующим образом:

1) Если есть массивы с пометкой threadprivate, то в вершину с описанием переменных заносится !$OMP THREADPRIVATE (список переменных).

2) Если цикл первый в параллельном регионе и цикл выгодный для распараллеливания !$OMP PARALLEL <список необходимых к обозначению PRIVATE и SHARED переменных> <COPYIN (список переменных)>

<список необходимых к обозначению PRIVATE и SHARED переменных> - перечисление директив (клауз) вида PRIVATE (имя переменной) или SHARED (имя переменной). В одном списке может быть несколько и PRIVATE, и SHARED.

<COPYIN (список переменных)> - указывается, если в цикле используются переменные с пометкой threadprivate, причем все они должны быть перечислены через запятую в списке переменных.

3) Если цикл последний в параллельном регионе - !$OMP END PARALLEL, как директива после цикла.

4) Если цикл выгодный для распараллеливания - !$OMP DO <ORDERED> <список REDUCTION, LASTPRIVATE, FIRSTPRIVATE>

<ORDERED> - директива ORDERED. Указывается, если при распараллеливании цикла используется ORDERED.

<список REDUCTION, LASTPRIVATE, FIRSTPRIVATE> - перечисление директив (клауз) вида REDUCTION (имя переменной), или LASTPRIVATE (имя переменной), или FIRSTPRIVATE (имя переменной). В одном списке может быть несколько и REDUCTION, LASTPRIVATE, FIRSTPRIVATE.

5) Если цикл выгодный для распараллеливания - !$OMP END DO, как директива после цикла.

6) Если у цикла пометка Ordered, перед первой вершиной с пометкой "первое использование ORDERED" вносится !$OMP ORDERED.

7) Если у цикла пометка Ordered, в конец последней вершины с пометкой "последнее использование ORDERED" вносится, !$OMP END ORDERED.

8) Если у цикла пометка pipeline - вставляются следующие директивы:

В области инициализации переменных, проверяется уникальность и происходит объявление функций и переменных, необходимых для функционирования конвейера:

!$ INTEGER OMP_GET_NUM_THREADS, OMP_GET_THREAD_NUM

!$ INTEGER IAM, NUMT, ISYNC("количество процессоров")

При инициализации параллельного региона, в который входит цикл с конвейером:

!$OMP PARALLEL PRIVATE (IAM,NUMT,ILIMIT)

Перед do внешнего цикла - инициализация нитей и синхронизационного массива ISYNC:

!$ iam = omp_get_thread_num ()

!$ numt = omp_get_num_threads ()

!$ ILIMIT=MIN(NUMT-1,Число витков внешнего цикла)

!$ ISYNC (IAM) = 0

!$OMP BARRIER

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

!$ 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

Перед 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

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

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

5.5 Примеры работы алгоритма
5.5.1 Программа "Якоби"
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
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 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

!$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

Стоимость = 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-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

Стоимость = 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 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

Стоимость = 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 во втором цикле).

Страницы: 1, 2, 3, 4, 5, 6

© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент.