Оценка времени выполнения цикла, не распараллеленного на OpenMP

Первый вариант распараллеливания гнезда, время которого нам нужно оценить,

 

CDVM$ PARALLEL … ON …

do IT₁ = 1, N₁

<…………>

enddo

 

При оценке мы берем в расчет только время, потраченное на вычисления. На один узел может максимум быть распределено ┌N₁/Число_узлов┐ итераций 1-го цикла. Таким образом, время параллельного выполнения цикла будет равняться ┌N₁/Число_узлов┐* t_1.

 

Оценка времени выполнения параллельного цикла без конвейера

Рассмотрим вариант распараллеливания гнезда циклов:

 

CDVM$ PARALLEL … ON …

do IT₁ = 1, N₁

<…………>

!$OMP PARALLEL PRIVATE(j)

!$OMP DO SCHEDULE (STATIC)

do IT_i = 1, N_i

<………….>

do IT_m = 1, N_m

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

enddo

 <…………>

enddo

!$OMP END DO

!$OMP END PARALLEL

<…………>

enddo

 

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

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

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

 

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

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

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

Число_раб_ядер:= ┌N_i / Число_узлов┐

 

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

 

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

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

o Если N_i < Число_ядер, то

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

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

 

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

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

 

Число_итераций_блока:= ┌┌ N_i / Число_узлов┐/ Число_раб_ядер┐

 

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

 

Число_итераций_блока:= ┌ N_i / Число_раб_ядер┐

 

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

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

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

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

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

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

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

 

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

 

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