Возможны два способа для распараллеливания i-го цикла в гнезде:
Способ 1. Распараллеливание с использованием конвейера.
Если цикл соответствует измерению массива с регулярной зависимостью, для него невозможно независимое выполнение витков. Мы можем организовать конвейерное выполнение цикла при условии, что для него есть тесно-вложенный цикл (см. варианты 4.1 и 5.2). В противном случае, мы не будем распараллеливать этот цикл. Также, мы не сможем распараллелить цикл конвейером, если для записи этих двух циклов используется одна и та же метка.
| Циклы нельзя распараллелить конвейером | Циклы можно распараллелить конвейером |
| DO 21 J = 1, NDO 21 I = 1, M <body>21 CONTINUE | DO J = 1, N DO I = 1, M <body>ENDDOENDDO |
Такой эффект вызван особенностью используемого алгоритма распараллеливания конвейером.
Итак, если цикл соответствует измерению массива с регулярной зависимостью, имеет тесно-вложенный цикл и для записи этих циклов не используется одна и та же метка, мы ставим для этого цикла метку "Распараллелен конвейером".
Способ 2. Распараллеливание без конвейера.
Если цикл не соответствует измерению массива с регулярной зависимостью, этот цикл распараллеливается без конвейера (см. варианты 1.1, 1.2, 3.1, 3.2, 5.1 и 5.3). Ставим для этого цикла метку "Распараллелен без конвейера".
Если ни один из способов не подошел, i-й цикл мы распараллеливать не будем. Также, если количество итераций i-го цикла достаточно мало (каждому узлу достанется не более одного витка цикла, то есть работать на узле будет не более одного ядра), цикл признается неэффективным для распараллеливания на OpenMP, и соответствующий вариант отбрасывается.
Шаг 2.3. Поиск наилучшего варианта распараллеливания гнезда.
С помощью оценочной функции (о ней мы поговорим далее), мы вычисляем приближенное время выполнения каждого варианта на SMP-кластере с заданным количеством узлов и ядер. Располагая прогнозируемым временем выполнения каждого варианта распараллеливания гнезда циклов, мы выбираем вариант с наименьшим временем. При оценке учитываем, каким способом мы распараллеливаем цикл – с использованием конвейера, или без.
Шаг 2.4. Вставка OpenMP-директив в DVM/OpenMP-вариант.
Итак, мы выбрали, как лучше всего распараллелить гнездо циклов: либо распараллеливаем на OpenMP один из циклов гнезда, либо не распараллеливаем ни один из них. Если мы приняли решение распараллелить i-й цикл в гнезде, нам нужно вставить OpenMP-директивы в DVM/OpenMP-вариант. Возможны два случая:
Случай 1. i-й цикл имеет метку "Распараллелен с конвейером".
Выполняем следующие действия:
1. Если это первый цикл, распараллеленный конвейером в DVM/OpenMP-варианте, в начало программы добавляем описание служебных переменных. Если имена служебных переменных уже заняты, генерируем для уникальные имена. Перед первым оператором в программе вставляем:
!$ INTEGER omp_get_num_threads, omp_get_thread_num
!$ INTEGER IAM, NUMT, ISYNC(<количествонитей>), ILIMIT
2. Добавляем в описание i-го цикла три особенности приватного типа – для переменных IAM, NUMT и ILIMIT.
3. Формируем директиву !$OMP PARALLEL. Для распараллеливания на OpenMP цикла с особенностями после директивы требуется вставить клаузы. Пробегаемся по списку особенностей.
3.1. Если особенность имеет тип private, first_private или last_private, для нее формируем клаузу PRIVATE (<список переменных>), FIRSTPRIVATE (<список переменных>) или LASTPRIVATE (<список переменных>). Отметим, что в списке особенностей одна и та же переменная может иметь одновременно две разных особенности – private и first_private (private и last_private). В этом случае переменную следует занести только в клаузу FIRSTPRIVATE (LASTPRIVATE).
3.2. Если особенность имеет тип reduction, для нее формируем клаузу REDUCTION(<операция>: <список переменных>). Для разных операций создается отдельная клауза REDUCTION.
4. Обозначаем начало параллельной области. Перед заголовком i-го цикла вставляем директиву !$OMP PARALLEL с клаузами, сформированными в предыдущем пункте.
5. Сразу после !$OMPPARALLEL <список клауз> добавляем инициализацию служебных переменных и барьерную синхронизацию нитей:
!$ iam = omp_get_thread_num ()
!$ numt = omp_get_num_threads ()
!$ ILIMIT=MIN(NUMT-1,<число витков i-го цикла>)
!$ ISYNC (IAM) = 0
!$OMP BARRIER
6. Перед заголовком i+1-го цикла добавляем инициализацию конвейера: ядро дожидается, пока предыдущее ядро выполнит очередную итерацию i-го цикла, и только после этого
!$ 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
7. Перед ENDDOi-го цикла добавляем операции по синхронизации работы ядер
!$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
8. После ENDDOi-го цикла обозначаем завершение параллельной области.
!$OMP END PARALLEL
Случай 2. i-й цикл имеет метку "Распараллелен без конвейера".
1. Формируем директиву !$OMP PARALLEL. Выполняем действия, описанные в пункте 3 предыдущего случая.
2. Обозначаем начало параллельной области и распределение витков цикла между ядрами. Вставляем сформированную директиву !$OMP PARALLEL с клаузами, а также директиву !$OMP DOSCHEDULE(STAITC), перед заголовком i-го цикла.
3. Обозначаем конец параллельного цикла и параллельной области. После ENDDOi-го цикла вставляем директивы:
!$OMP END DO
!$OMP END PARALLEL
Если наименьшее значение оценочной функции соответствует варианту, в котором мы распараллеливаем гнездо циклов только на DVM, ничего делать не нужно.
Оценочная функция нужна для того, чтобы вычислить примерное время выполнения гнезда циклов, распараллеленного на DVM/OpenMP. Оценив время выполнения варианта распараллеливания гнезда циклов, мы сможем определить, какой из вариантов распараллеливания лучше.
Введем некоторые обозначения:
- Число_узлов – это количество узлов кластера.
- Число_ядер – это количество ядер на одном узле. Предполагаем, что на всех узлах одинаковое количество ядер.
- Число_раб_ядер – количество ядер на узле, которым достались витки параллельного цикла. Остальные ядра узла простаивают.
- Число_редукционных_переменных – количество редукционных переменных, находящихся в клаузе REDUCITON директивы !$OMPPARALLEL. Если клауза редукции отсутствует, то Число_редукционных_переменных равняется нулю.
- Ni – количество итераций i-го цикла. Напомним, что 1-й цикл в гнезде – внешний, а M-й – внутренний. Всего в гнезде M циклов.
- Блок итераций – итерации, которые достались некоторому ядру после выполнения конструкции разделения работы !$OMPDO. Если речь идет о конвейерном выполнения i-го и i+1-го цикла, то Блок итераций – это итерации i+1-го цикла, которые достанутся ядру на одной итерации i-го цикла.
- Число_итераций_блока – максимальное количество итераций в Блоке итераций. Отметим, что ядрам, которым достались работа, может быть распределено различное количество витков цикла. Так как мы занимаемся оценкой времени выполнения, нас будет интересовать сколько времени будет работать ядро, которому досталось больше всего работы, так как все остальные ядра при синхронизации будут ждать именно это ядро.
- ti – время выполнения одной итерации i-го цикла.
- ┌ A┐ - округление дробного числа A в большую сторону.
Нам известно количество итераций каждого цикла и время выполнения одной итерации самого внутреннего цикла – тела цикла M. Обозначим это время за tm.
Первый вариант распараллеливания гнезда, время которого нам нужно оценить,
CDVM$ PARALLEL … ON …
do IT1 = 1, N1
<…………>
enddo
При оценке мы берем в расчет только время, потраченное на вычисления. На один узел может максимум быть распределено ┌N1/Число_узлов┐ итераций 1-го цикла. Таким образом, время параллельного выполнения цикла будет равняться ┌N1/Число_узлов┐* t1.
Рассмотрим вариант распараллеливания гнезда циклов:
CDVM$ PARALLEL … ON …
do IT1 = 1, N1
<…………>
!$OMP PARALLEL PRIVATE(j)
!$OMP DO SCHEDULE (STATIC)
do ITi = 1, Ni
<………….>
do ITm = 1, Nm
<телоцикла m>
enddo
<…………>
enddo
!$OMP END DO
!$OMP END PARALLEL
<…………>
enddo
ЗдесьвнешнийциклраспараллеленнаDVM, аi-йцикл – наOpenMP. При этом, i-й цикл не соответствует измерению массива с регулярной зависимостью, поэтому в организации конвейерного выполнения нет необходимости.
Посчитаем количество ядер, которым достались витки цикла i:
- Если итерации цикла распределятся между узлами кластера
o Если Ni >= Число_ядер * Число_узлов, то
Число_раб_ядер := Число_ядер
o Если Ni < Число_ядер * Число_узлов, то
Число_раб_ядер := ┌Ni / Число_узлов┐
- Если итерации цикла НЕ распределятся между узлами кластера
o Если Ni >= Число_ядер, то
Число_раб_ядер := Число_ядер
o Если Ni < Число_ядер, то
Число_раб_ядер := Ni
Если Число_раб_ядер <= 1, i-й цикл является неэффективным для распараллеливания на OpenMP.
Посчитаем максимальное количество итераций цикла i, которое может достаться какому-нибудь из ядер SMP-кластера, следующим образом:
- Если итерации цикла распределятся между узлами кластера, то
Число_итераций_блока := ┌┌ Ni / Число_узлов┐/ Число_раб_ядер┐
- Если итерации цикла НЕ распределяются между узлами кластера
Число_итераций_блока := ┌ Ni / Число_раб_ядер┐
Время параллельного выполнения i-го цикла (далее Время i-го цикла), складывается из нескольких составляющих:
- Время полезных вычислений