!$OMP END DO

!$OMP END PARALLEL

Если наименьшее значение оценочной функции соответствует варианту, в котором мы распараллеливаем гнездо циклов только на DVM, ничего делать не нужно.

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

Введем некоторые обозначения:

§ Число_узлов - это количество узлов кластера.

§ Число_ядер - это количество ядер на одном узле. Предполагаем, что на всех узлах одинаковое количество ядер.

§ Число_раб_ядер - количество ядер на узле, которым достались витки параллельного цикла. Остальные ядра узла простаивают.

§ Число_редукционных_переменных - количество редукционных переменных, находящихся в клаузе REDUCITON директивы !$OMP PARALLEL. Если клауза редукции отсутствует, то Число_редукционных_переменных равняется нулю.

§ Ni - количество итераций i-го цикла. Напомним, что 1-й цикл в гнезде - внешний, а M-й - внутренний. Всего в гнезде M циклов.

§ Блок итераций - итерации, которые достались некоторому ядру после выполнения конструкции разделения работы !$OMP DO. Если речь идет о конвейерном выполнения 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-го цикла), складывается из нескольких составляющих:

§ Время полезных вычислений

§ Время барьерной синхронизации

§ Накладные расходы на использование OpenMP (далее Расходы на OpenMP)

o создание и удаление параллельной области, выделение памяти под локальные переменные. (далее Расходы на PARALLEL)

o организация параллельного выполнения цикла (далее Расходы на DO)

o применение клаузы REDUCTION (далее, Расходы на REDUCTION)

Время полезных вычислений := ti * Число_итераций_блока

Исходим из эвристических предположений, что время барьерной синхронизации ядер, а также накладные расходы на использование OpenMP прямо пропорционально зависят от количества работающих ядер.

Введем следующие константы:

· CORE_SYNC_TIME - отражает накладные расходы на барьерную синхронизацию ядер,

· OMP_PARALLEL_OVERHEARDS - отражает накладные расходы на создание и удаление параллельной области,

· OMP_DO_OVERHEARDS - отражает накладные расходы на организацию параллельного выполнения цикла,

· OMP_REDUCTION_OVERHEARDS - отражает накладные расходы на применение клаузы REDUCTION.

Чтобы оценить временные расходы, возникающие при применение тех или иных возможностей OpenMP, нужно соответствующую константу умножить на количество работающих ядер. Накладные расходы на применение клаузы REDUCTION также зависят и от количества редукционных переменных. Таким образом:

Время барьерной синхронизации := CORE_SYNC_TIME * Число_раб_ядер,

Расходы на PARALLEL := OMP_PARALLEL_OVERHEARDS * Число_раб_ядер

Расходы на DO := OMP_DO_OVERHEARDS * Число_раб_ядер

Расходы на REDUCTION := OMP_REDUCTION_OVERHEARDS * Число_редукционных_переменных * Число_раб_ядер

Расходы на OpenMP := Расходы на PARALLEL + Расходы на DO + Расходы на REDUCTION.

Просуммируем все составляющие, и получим Время вычисления:

Время i-го цикла := Время полезных вычислений + Время барьерной синхронизации + Расходы на OpenMP.

CDVM$ PARALLEL … ON … ACROSS …

do IT1 = 1, N1

<…………>

!$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, Ni-1)

!$OMP BARRIER

do ITi = 1, Ni

!$ 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 ITi+1 = 1, Ni+1

<………….>

do ITm = 1, Nm

<тело цикла m>

enddo

<…………>

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

Здесь внешний цикл распараллелен на DVM, а для i-го и i+1-го цикла организовано конвейерное выполнение на OpenMP. При этом, i-й цикл соответствует измерению массива с регулярной зависимостью.

Посчитаем количество ядер, которым достались витки цикла i+1:

§ Если итерации цикла распределятся между узлами кластера

o Если Ni+1 >= Число_ядер * Число_узлов, то

Число_раб_ядер := Число_ядер

o Если Ni+1 < Число_ядер * Число_узлов, то

Число_раб_ядер := - Ni +1 / Число_узлов¬

§ Если итерации цикла НЕ распределятся между узлами кластера

o Если Ni+1 >= Число_ядер, то

Число_раб_ядер := Число_ядер

o Если Ni+1 < Число_ядер, то

Число_раб_ядер := Ni

Если Число_раб_ядер <= 1, i-й цикл является неэффективным для распараллеливания на OpenMP.

Посчитаем максимальное количество итераций цикла i, которое может достаться какому-нибудь из ядер SMP-кластера, следующим образом:

§ Если итерации цикла распределятся между узлами кластера, то

Число_итераций_блока := --Ni+1 / Число_узлов¬/ Число_раб_ядер¬

§ Если итерации цикла НЕ распределяются между узлами кластера

Число_итераций_блока := -Ni+1 / Число_раб_ядер¬

Время i-го цикла складывается из нескольких составляющих:

§ Время полезных вычислений

§ Время барьерной синхронизации

§ Расходы на OpenMP:

o Расходы на PARALLEL

o Расходы на DO

o Расходы на REDUCTION

o Расходы на синхронизацию работы ядер в конвейере. Этой величиной мы будем пренебрегать, так как она очень мала.

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

Обратимся к Рисунку 5. На нем схематически иллюстрирована конвейерное выполнение. Кружочками обозначены Блоки итераций. По вертикали отмеряются значения итератора ITi, по горизонтали - ITi+1. Блоки итераций, соединенные сплошной линией, выполняются параллельно разными ядрами. Стрелочка означает зависимость выполнения одного Блока итераций от другого. То есть стрелочками обозначено, какие Блоки итераций обязаны быть выполнены прежде чем начнется выполняться Блок итераций, из которого исходит стрелка. Оранжевым цветом обозначены Блоки итераций, соответствующие разгону конвейера, голубым - полной загрузке конвейера, желтым - остановке конвейера.

Рисунок 5. Схематическая иллюстрация конвейерного выполнения

Существует два случая:

1) Работающих ядер меньше количества итераций i-го цикла (Число_раб_ядер < Ni).

Этот случай иллюстрирован на Рисунки 5.2. Для разгона конвейера требуется выполнить Число_раб_ядер Блоков итераций. Далее конвейер работает с полной загрузкой (Ni - Число_раб_ядер) Блоков итераций. Остановка займет (Число_раб_ядер - 1) Блоков итераций. Таким образом:

Время разгона := Число_раб_ядер * ti+1 * Число_итераций_блока

Время полной загрузки := (Ni - Число_раб_ядер) * ti+1 * Число_итераций_блока

Время остановки := (Число_раб_ядер - 1) * ti+1 * Число_итераций_блока

2) Работающих ядер больше или равно количества итераций i-го цикла (Число_раб_ядер>= Ni)

Этот случай иллюстрирован на Рисунки 5.3. Для разгона конвейера требуется выполнить Ni Блоков итераций. Далее конвейер работает с полной загрузкой (Число_раб_ядер - Ni) Блоков итераций. Остановка займет (Ni - 1) Блоков итераций. Таким образом:

Время разгона := Ni * ti+1 * Число_итераций_блока

Время полной загрузки := (Число_раб_ядер - Ni) * ti+1 * Число_итераций_блока

Время остановки := (Ni - 1) * ti+1 * Число_итераций_блока

Теперь посчитаем Время полезных вычислений как сумму его составляющих. Отметим, что для обоих рассмотренных случаев получаем один и тот же результат.

Время полезных вычислений := Время разгона + Время полной загрузки + Время полной загрузки = (Ni - 1 + Число_раб_ядер) * ti+1 * Число_итераций_блока.

Время барьерной синхронизации, Расходы на PARALLEL и Расходы на REDUCTION рассчитываются также, как в пункте 6.2.2.1:

Время барьерной синхронизации := CORE_SYNC_TIME * Число_раб_ядер,

Расходы на PARALLEL := OMP_PARALLEL_OVERHEARDS * Число_раб_ядер

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