Система автоматизации распараллеливания Отображение на SMP-кластер (стр. 6 из 8)
- Время барьерной синхронизации
- Накладные расходы на использование 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.
1.11.4.3 Оценка времени выполнения параллельного цикла с конвейером
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 * Число_раб_ядер
Расходы на REDUCTION := OMP_REDUCTION_OVERHEARDS * Число_редукционных_переменных * Число_раб_ядер
Отметим, что параллельный цикл создается Ni раз, поэтому
Расходы на DO := OMP_DO_OVERHEARDS * Ni * Число_раб_ядер
Расходы на OpenMP вычисляется как сумма всех составляющих:
Расходы на OpenMP := Расходы на PARALLEL + Расходы на DO + Расходы на REDUCTION + Расходы на синхронизацию.
Просуммируем все составляющие, и получим Время i-го цикла:
Время i-го цикла := Время полезных вычислений + Время барьерной синхронизации + Расходы на OpenMP.
1.11.4.4 Оценка времени выполнения гнезда циклов
Итак, мы оценили Время i-го цикла. Чтобы вычислить время выполнения всего гнезда циклов, это время следует умножить на количество раз, которое этот цикл выполняется. Таким образом, время выполнения гнезда равняется N1 * N2 * … * Ni-1 * Время i-го цикла.
1.12 Блок поиска наилучшего DVM/OpenMP-варианта
Рисунок 6. Принцип работы "Блока поиска DVM-варианта"
Для начала рассмотрим принцип работы Блока поиска DVM-варианта. DVM-варианты подаются на вход "Блоку перебора вариантов и поиска наилучшего" (далее, Блок перебора вариантов). Этот блок занимается поиском оптимальной решетки процессоров, а также наилучшего варианта распараллеливания.
Для поиска оптимальной решетки и наилучшего варианта, Блок перебора пользуется Библиотекой предсказателя производительности DVM-программ, сокращенно Библиотеке DVM-предиктора.
DVM-предиктор предназначен для анализа и отладки производительности DVM-программ без использования реальной параллельной машины (доступ к которой обычно ограничен или сложен). С помощью DVM-предиктора пользователь имеет возможность получить предсказанные временные характеристики выполнения его программы на MPP или кластере рабочих станций с различной степенью подробности. [10]
Библиотека DVM-предиктора позволяет получить характеристики эффективности DVM-варианта на некоторой решетке процессоров. Характеристики эффективности подсчитываются для каждого гнезда циклов, а также для всего варианта в целом. О том, какие бывают характеристики эффективности речь пойдет ниже.
Сначала Блок перебора ищет оптимальную решетку процессоров. Он подает на вход Библиотеке DVM-предиктора некоторый DVM-вариант на различных решетках. Сравнивая полученные характеристики эффективности, Блок перебора выбирает оптимальную решетку.
Далее, Блок перебора подает на вход Библиотеке предиктора DVM-варианты только на оптимальной решетке.
Блок перебора вариантов анализирует полученные характеристики эффективности, и выбирает наилучший вариант распараллеливания. Номер наилучшего варианта распараллеливания передается Блоку записи результатов в Базу данных.
Теперь рассмотрим, какие следует внести изменения, чтобы получить "Блок поиска наилучшего DVM/OpenMP-варианта".
Рисунок 7. Принцип работы "Блока поиска DVM/OpenMP-варианта"
Характеристики эффективности DVM-вариантов для всех циклов, посчитанные с помощью Библиотеки DVM-предиктора, подаются на вход Блоку пересчета DVM-характеристик.