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

 

CDVM$ PARALLEL … ON … ACROSS …

do IT₁ = 1, N₁

<…………>

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

!$OMP BARRIER

do IT_i = 1, N_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 SCHEDULE (STATIC)

 do IT_i+1 = 1, N_i+1

<………….>

do IT_m = 1, N_m

 <тело цикла 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 Если N_i+1 >= Число_ядер * Число_узлов, то

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

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

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

 

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

 

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

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

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

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

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

 

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

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

 

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

 

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

 

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

 

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

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

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

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

o Расходы на PARALLEL

o Расходы на DO

o Расходы на REDUCTION

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

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

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

 

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

 

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

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

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

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

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

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

 

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

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

 

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

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

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

 

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

 

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

 

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

 

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

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

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

 

Отметим, что параллельный цикл создается N_i раз, поэтому

 

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

Расходы на OpenMP вычисляется как сумма всех составляющих:

Расходы на OpenMP:= Расходы на PARALLEL + Расходы на DO + Расходы на REDUCTION + Расходы на синхронизацию.

 

Просуммируем все составляющие, и получим Время i-го цикла:

 

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