Структура DVM/OpenMP-эксперта

Рисунок 3. Схема работы "DVM/OpenMP-эксперта"

В DVM/OpenMP-эксперте DVM-варианты, сгенерированные Блоком поиска DVM-вариантов передаются Блоку поиска DVM/OpenMP-вариантов. Этот блок распараллеливает каждый DVM-вариант на OpenMP, выбирая при этом наиболее подходящий способ распараллеливания. Таким образом, из каждого DVM-варианта получается по одному DVM/OpenMP-варианту. Далее отрабатывает Блок поиска наилучшего DVM/OpenMP-варианта, который в качестве результата выдает наилучший DVM/OpenMP-вариант. Блок записи результатов в Базу данных записывает выбранный вариант распараллеливания в Базу данных.

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

Варианты распараллеливания на OpenMP

Блок поиска DVM/OpenMP-вариантов получает на вход набор вариантов распараллеливания программы на кластере. Теперь нам требуется добавить еще один уровень параллелизма, и распределить работу, доставшуюся узлу кластера, между ядрами данного узла.

DVM-рекомендации позволяют распределить работу по выполнению циклов между узлами кластера. Сначала с помощью специальных DVM-директив между узлами кластера распределяются элементы массивов (блоками). Затем осуществляется распараллеливание циклов по принципу собственных вычислений. Если между витками цикла имеется зависимость по данным, цикл не распараллеливается. Исключение составляют редукционная зависимость и регулярная зависимость.

Рассмотрим несколько простых примеров.

Пример 1

Пусть DVM-эксперт распараллелил следующий цикл:

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

do i=1,N

do j=1,M

A(I, J) = B(J, I)

enddo

Директива CDVM$ PARALLEL (i,j) ON a(i,j) говорит о том, что виток цикла со значением итераторов (i, j) будет выполняться на то узле, на котором распределен элемента массива a(i, j). Существует два способа распараллелить на OpenMP этот многомерный цикл: распараллелить внутренний или внешний цикл.

Вариант 1.1

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

!$OMP PARALLEL PRIVATE(i, j)

!$OMP DO SCHEDULE (STATIC)

do i=1,N

do j=1,M

A(I, J) = B(J, I)

enddo

!$OMP END DO

!$OMP END PARALLEL

Директива!$OMP PARALLEL говорит о том, что на каждом узле начинается параллельная область. То есть на узле создаются нити, между которыми будет распределяться работа. Все порождённые нити исполняют один и тот же код, соответствующий параллельной области. Предполагается, что в SMP-системе нити будут распределены по различным ядрам процессора. Клауза PRIVATE(i, j) означает, что для каждой нити выделяется локальная память под две переменные: i и j. Действительно, у каждой нити должен быть свой итератор цикла. По достижении директивы!$OMP END PARALLEL нити останавливают свою работу, и на узле остается работать только одна мастер-нить.

Директива!$OMP DO сообщает нам, что далее в программе следует цикл, витки которого будут распределяться между нитями. Клауза SCHEDULE (STATIC) гласит, что все множество итераций внешнего цикла делится на непрерывные куски примерно одинакового размера, и полученные порции итераций распределяются между нитями.

Директива!$OMP END DO сообщает об окончании параллельного цикла. Происходит неявная барьерная синхронизация нитей и неявный вызов!$OMP FLUSH. Выполнение FLUSH предполагает, что значения всех переменных (или переменных из списка, если он задан), временно хранящиеся в регистрах и кэш-памяти текущей нити, будут занесены в основную память; все изменения переменных, сделанные нитью во время работы, станут видимы остальным нитям. [9]

Вариант 1.2

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

do i=1,N

!$OMP PARALLEL PRIVATE(i, j)

!$OMP DO SCHEDULE (STATIC)

do j=1,M

A(I, J) = B(J, I)

enddo

!$OMP END DO

!$OMP END PARALLEL

enddo

Отличие этого варианта от предыдущего заключается в том, на каждой итерации внешнего цикла будет создаваться новая параллельная область, то есть будут создаваться нити, и выделяться локальная память для них. Затем нити будут синхронизоваться, выполнять FLUSH и останавливаться. Всё это накладные расходы, которые будут возникать N раз. Еще одно отличие заключается в том, что в этом варианте между нитями распределяются витки внутреннего цикла, а не внешнего.

Другим важным критерием, помимо накладных расходов на вызовы библиотеки OpenMP, является загруженность нитей. Если рассматривать первый вариант, то N витков внешнего цикла сначала распределяются между узлами, а потом витки, соответствующие одному узлу, распределяются между ядрами этого узла. Если количество витков цикла меньше суммарного количества ядер нашего SMP-кластера, то некоторые ядра будут простаивать. Если некоторый цикл способен загрузить не более чем по одному ядру на каждом узле, то распараллеливать на OpenMP такой цикл смысла не имеет.

Пример 2

Пусть DVM-эксперт распараллелил то же самый цикл следующим образом:

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

do i=1,N

do j=1,M

A(I, J) = B(J, I)

enddo

Отличие этого примера от предыдущего заключается в распределении данных. Здесь, между узлами одномерной процессорной решетки распределено только второе измерение массива A. Соответственно, между узлами будут распределяться только итерации внутреннего цикла. Таким образом, если количество витков внешнего цикла меньше суммарного количества ядер нашего SMP-кластера, но больше количества ядер на одном узле, то распараллеливание на OpenMP внешнего цикла позволит загрузить все ядра (заметим, что в варианте 1.1 на каждом узле работало бы не более одного ядра).

Для этого примера также существует два варианта распараллеливания, аналогичных вариантам 1.1 и 1.2.

Пример 3

Пусть DVM-эксперт распараллелил следующий цикл:

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

*DVM$* REDUCTION (SUM(s))

do i=1,N

do j=1,M

S = S + A(I, J)

enddo

Клауза REDUCTION (SUM(s)) означает, что каждый узел создаст в своей локальной памяти редукционную переменную, и будет накапливать в ней суммы элементов массива. По окончанию цикла эти локальные переменные будут просуммированы и записаны в s. В таком случае мы по-прежнему имеем два варианта распараллеливания:

Вариант 3.1	Вариант 3.2
CDVM$ PARALLEL (i,j) ON a(i,j), DVM$ REDUCTION (SUM(s)) !$OMP PARALLEL PRIVATE(i, j) !$OMP*REDUCTION(+: s) !$OMP DO SCHEDULE (STATIC) do i=1,N do j=1,M S = S + A(I, J) enddo enddo !$OMP END DO !$OMP END PARALLEL	CDVM$ PARALLEL (i,j) ON a(i,j), DVM$ REDUCTION (SUM(s)) do i=1,N !$OMP PARALLEL PRIVATE(i, j) !$OMP*REDUCTION(+: s) !$OMP DO SCHEDULE (STATIC) do j=1,M S = S + A(I, J) enddo !$OMP END DO !$OMP END PARALLEL enddo

Клауза REDUCTION(+: s) означает, что каждая нить создаст в своей локальной памяти редукционную переменную, и будет накапливать в ней суммы элементов массива. По окончанию цикла эти локальные редукционные переменные нитей будут просуммированы и записаны в локальную редукционную переменную узла.

В варианте 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

Тело данного цикла примечательно тем, что невозможно независимое выполнение витков цикла, т.к. прежде чем вычислить 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. Принцип конвейерного выполнения отображен на рисунке.

Нить 1

Нить 2

Нить 3

Нить 4

Массив A

J = 2…4

J = 5…7

J = 8…10

J = 11…13

I = 2

Такт 1

Такт 2

Такт 3

Такт 4

I = 3

Такт 2

Такт 3

Такт 4

Такт 5

I = 4

Такт 3

Такт 4

Такт 5

Такт 6

I = 5

Такт 4

Такт 5

Такт 6

Такт 7

I = 6

Такт 5

Такт 6

Такт 7

Такт 8

Рисунок 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

Здесь регулярная зависимость присутствует только по второму измерению массива 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

!$OMP END DO