В варианте 3.1 локальные редукционные переменные нитей будут суммироваться по окончании внешнего цикла. В варианте 3.2 локальные редукционные переменные нитей суммируются на каждой итерации внешнего цикла, и это снова дополнительные накладные расходы.

Пример 4

Рассмотрим пример с регулярной зависимостью:

CDVM$ PARALLEL (i,j) ON a(i,j),

*DVM$* ACROSS (a(1:1,1:1))

do i=2,N-1

do j=2,M-1

A(I, J) = A(I-1, J) + A(I+1, J)

* + A(I, J-1) + A(I, J+1)

enddo

enddo

Тело данного цикла примечательно тем, что невозможно независимое выполнение витков цикла, т.к. прежде чем вычислить A(I, J), необходимо вычислить A(I-1, J) и A(I, J-1).

Прежде всего, клауза ACROSS (a(1:1,1:1)) определяет точное местоположение удаленных данных (теневые грани). Также ACROSS обеспечивает сохранение порядка вычислений витков цикла.

Для распараллеливания на OpenMP циклов с регулярной зависимостью используется алгоритм конвейерного выполнения при помощи синхронизующего массива. Этот алгоритм применялся в тестах NAS [12]. Цикл с регулярной зависимостью должен содержать тесно-вложенный цикл. Вариант распараллеливания здесь всего один:

Вариант 4.1

CDVM$ PARALLEL (i,j) ON a(i,j),

*DVM$* ACROSS (a(1:1,1:1))

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

!$ IAM = omp_get_thread_num ()

!$ NUMT = omp_get_num_threads ()

!$ ISYNC (IAM) = 0

!$ ILIMIT=MIN(NUMT-1, N-3)

!$OMP BARRIER

do i=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 SCHEDULE (STATIC)

do j=2,M-1

A( I, J ) = A( I-1, J ) + A( I+1, J ) +

* A( I, J-1 ) + A( I, J+1 )

enddo

!$OMP END DO 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 END PARALLEL

Предположим, что N = 7, M = 14, а количество нитей - 4. Принцип конвейерного выполнения отображен на рисунке.

Рисунок 4. Иллюстрация принципа конвейерной работы

Такт 1. Нить 1 выполняет три витка цикла: (I = 2, J = 2), (I = 2, J = 3), (I = 2, J = 4). Все остальные нити ждут. Таким образом, элементы массива A(2,2), A(2,3), A(2,4) получают новые значения.

Такт 2. Работают 1-я и 2-я нить. Нить 1 выполняет три витка цикла: (I = 3, J = 2), (I = 3, J = 3), (I = 3, J = 4). Отметим, что A(2, 2), A(2, 3) и A(2, 4), требуемые для вычисления A(I, J) для 1-й нити в текущем такте, уже содержат новое значение. Аналогично, нить 2 выполняет три витка: (I = 2, J = 5), (I = 2, J = 6), (I = 2, J = 7). Элемент A(2, 4), требуемый для вычисления A(2, 5), был уже посчитан 1-й нитью в 1-м такте.

Такт 3. Работают 1-я, 2-я и 3-я нить. Каждая нить выполняет по три витка. Для каждого элемента A(I, J), обрабатываемого в текущем такте, элементы A(I-1, J) и A(I, J-1) уже содержат новое значение.

Такт 4, 5, 6, 7, 8 - аналогично.

Таким образом, порядок вычисления витков при параллельной работе нитей сохраняется.

В работе конвейера можно отметить три этапа:

· Разгон конвейера (Такты 1,2,3).

· Работа с полной загрузкой (Такты 4,5).

· Остановка конвейера (Такты 6,7,8).

Пример 5

CDVM$ PARALLEL (i,j,k) ON a(i,j,k),

*DVM$* ACROSS (a(0:0,1:1,0:0))

do i=1,N-1

do j=1,M

do k=1,P

A( I, J, K ) = (A( I, J, K ) + A( I, J, K ) +

* A( I, J-1, K ) + A( I, J+1, K ))

enddo

enddo

enddo

Здесь регулярная зависимость присутствует только по второму измерению массива A. Соответственно, внешний или внутренний цикл можно распараллелить с помощью OMP PARALLEL DO, а для среднего можно организовать конвейер.

Вариант 5.1

CDVM$ PARALLEL (i,j,k) ON a(i,j,k),

*DVM$* ACROSS (a(0:0,1:1,0:0))

!$OMP PARALLEL PRIVATE(j, i, k)

!$OMP DO SCHEDULE (STATIC)

do i=1,N-1

do j=1,M

do k=1,P

A( I, J, K ) = (A( I, J, K ) + A( I, J, K ) +

* A( I, J-1, K ) + A( I, J+1, K ))

enddo

enddo

enddo

!$OMP END DO

!$OMP END PARALLEL

Вариант 5.2

CDVM$ PARALLEL (i,j,k) ON a(i,j,k),

*DVM$* ACROSS (a(0:0,1:1,0:1))

do i=1,N-1

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

!$ IAM = omp_get_thread_num ()

!$ NUMT = omp_get_num_threads ()

!$ ISYNC (IAM) = 0

!$ ILIMIT=MIN(NUMT-1, 11)

!$OMP BARRIER

do j=1,M

!$ 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 SCHEDULE (STATIC)

do k=1,P

A( I, J, K ) = (A( I, J, K ) + A( I, J, K ) +

* A( I, J-1, K) + A( I, J+1, K ))

enddo

!$OMP END DO 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 END PARALLEL

Enddo

Вариант 5.3

CDVM$ PARALLEL (i,j,k) ON a(i,j,k),

*DVM$* ACROSS (a(0:0,1:1,0:0))

do i=1,N-1

do j=1,M

!$OMP PARALLEL PRIVATE(j, k)

!$OMP DO SCHEDULE (STATIC)

do k=1,P

A( I, J, K ) = (A( I, J, K ) + A( I, J, K ) +

* A( I, J-1, K) + A( I, J+1, K ))

enddo

!$OMP END DO

!$OMP END PARALLEL

enddo

enddo

Блок поиска DVM/OpenMP-вариантов распараллеливает на OpenMP каждый DVM-вариант. Результатом его работы являются DVM/OpenMP-варианты. При этом DVM/OpenMP-вариантов получается ровно столько же, сколько было DVM-вариантов.

Для каждого гнезда циклов, распараллеленного в DVM-варианте, Блок поиска DVM/OpenMP-вариантов выполняет следующее:

§ Формирует варианты распараллеливания этого гнезда циклов на DVM/OpenMP.

§ Оценивает время выполнения распараллеленного гнезда циклов в модели DVM/OpenMP.

§ На основании оценки выбирает наилучший вариант распараллеливания гнезда циклов.

§ Заносит OpenMP-директивы, распараллеливающие гнездо циклов выбранным способом, в DVM/OpenMP-вариант.

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