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

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.

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

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.

1.11.4.4 Оценка времени выполнения гнезда циклов

Итак, мы оценили Время i-го цикла. Чтобы вычислить время выполнения всего гнезда циклов, это время следует умножить на количество раз, которое этот цикл выполняется. Таким образом, время выполнения гнезда равняется N₁ * N₂ * … * N_i-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-характеристик.

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

1.12.1 Характеристики эффективности параллельной программы

DVM-предиктор вычисляет достаточно много характеристик эффективности для интервала. В качестве интервала может выступать гнездо циклов, а также вся программа. Нам потребуется пересчитать только некоторые из этих характеристик:

§ CPU_time_usr - полезное процессорное время - время, потраченное на выполнение вычислений в интервале.

§ CPU_time_sys - полезное системное время - время, проведенное процессором в системной фазе (время, затраченное Lib-DVM).

§ CPU_time - полное процессорное время. Равняется сумме CPU_time_usr и CPU_time_sys.

§ Execution_time - время выполнения интервала.

Остальные характеристики пересчитываются вызовом специальных функций Библиотеки DVM-предиктора, поэтому мы их рассматривать не будем.

Указанные характеристики вычисляются для всех интервалов на каждом узле. Поядерные характеристики мы вычислять не будем.

Рассмотрим интервал, соответствующий гнезду циклов. Обозначим внешний цикл гнезда как L. Значение характеристики <Имя_ характеристики > на этом интервале на i-м узле мы будем обозначать как <Имя_характеристики> _Li.Требуется пересчитать эти поузловые характеристики с учетом того, что в каждом узле работает по несколько ядер. Поядерные характеристики не высчитываются.

1.12.2 Алгоритм пересчета характеристик эффективности

Алгоритм выполняет весьма приближенную оценку характеристик эффективности DVM/OpenMP-варианта, поэтому в дальнейшем нуждается в доработке.

Будем говорить, что интервал распараллелен на OpenMP (или DVM), если этот интервал соответствует гнезду циклов, распараллеленному на OpenMP (или DVM).

Поочередно обрабатываем каждый интервал. Нас будут интересовать только те интервалы, которые распараллелены на OpenMP. Пусть текущий интервал - это гнездо циклов, распараллеленное на OpenMP. Обозначим внешний цикл гнезда за L. Выполняем следующие действия.

Шаг 1. Находим коэффициент ускорения. Коэффициент ускорения отражает во сколько раз быстрее цикл будет вычисляться на SMP-кластере, нежели на кластере с тем же количеством узлов. То есть во сколько раз полезное процессорные время DVM/OpenMP-варианта меньше соответствующего DVM-варианта. Системные затраты в расчет не берутся.

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

Затем находим, какое максимальное количество итераций этого цикла может прийтись на одно ядро этого узла. Коэффициент ускорения равняется отношению первой величины на вторую.

Шаг 2. Пересчитываем поузловые характеристики эффективности текущего интервала

· Для каждого узла кластера пересчитываем полезное процессорное время выполнения гнезда циклов, поделив старое значение параметра CPU_time_usr_Li на коэффициент ускорения.

· Вычисляем для каждого узла разность между старым и новым значение параметра CPU_time_usr_Li. Обозначим эту величину для i-го узла как CPU_usr_diff_Li.

· Пересчитываем полное процессорное время:

CPU_time_Li := CPU_time_usr_Li + CPU_time_sys_Li.

· Пересчитываем время выполнения интервала. Execution_time_Li складывается из полезного процессорного времени, системных затрат, простоев и пр. Мы предполагаем, что из всех этих характеристик изменяется только полезное процессорное время, и не учитываем системные затраты на использование OpenMP, а также простои ядер и время на их синхронизацию. Для каждого узла из Execution_time_Li следует вычесть CPU_usr_diff_Li.

Шаг 3. Пересчитываем характеристики эффективности интервалов, вложенных в текущий (гнезда циклов, вложенные, но не тесно-вложенные в текущее гнездо циклов). Для каждого вложенного интервала следует выполнить действия, описанные на Шаге 2.

Шаг 4. Пересчитываем характеристики эффективности интервалов, содержащих текущий интервал.

Пусть цикл L непосредственно вложен в цикл P. В качестве P может также выступать тело всей программы. Возможны два случая:

1) Цикл P является внешним для некоторого гнезда циклов или является телом всей программы. В этом случае, циклу P соответствует некоторый интервал, для которого DVM-предиктором подсчитаны характеристики эффективности. Эти характеристики следует пересчитать. Для каждого узла (i от 1 до Число_узлов) выполняем следующие действия:

· CPU_time_usr_Pi := CPU_time_usr_Pi - CPU_usr_diff_Li

· CPU_time_Pi := CPU_time_usr_Pi + CPU_usr_sys_Pi

· Execution_time_Pi := Execution_time_Pi - CPU_usr_diff_Li

2) Цикл P не является внешним для некоторого гнезда циклов.

Пусть N_p - количество итераций цикла P. Для цикла P характеристики эффективности не вычислялись. Нам известно, что тело цикла P на i-м узле стало выполняться на CPU_usr_diff_Li быстрее. Соответственно, весь цикл P будет выполняться на i-м узле быстрее на N_p * CPU_usr_diff_Li. Отразим этот факт следующей записью:

CPU_usr_diff_Pi := N_p * CPU_usr_diff_Li.

Если P является самым внешним циклом (телом всей программы), останавливаемся. В противном случае все действия, описанные в шаге 4, следует повторить для цикла, в который непосредственно вложен цикл P.

1.13 Особенности реализации

1.13.1 Классы решаемых задач

DVM/OpenMP-эксперт, имеет следующие ограничения:

§ Входная программы должна быть написана на языке Фортран 77

§ Входная программы не должна содержать процедуры или допускать их инлайн-подстановку.

§ DVM/OpenMP-эксперт распараллеливает только циклы.

§ На OpenMP распараллеливаются только те циклы, которые сумел распараллелить DVM-эксперт, а также циклы, тесно-вложенные в него.

1.13.2 Специальные комментарии.

Текущая версия анализатора не предоставляет DVM/OpenMP эксперту информацию об особенностях цикла. Недостающую информацию должен сообщать пользователь, используя специальные комментарии. Рассмотрим их подробнее.

Если программист хочет задать дополнительную информацию о программе, он должен вставить в текст программы комментарий, начинающийся с последовательности символов CPRG. Всё, что идёт после этих символов записывается в Базу Данных в таблицу специальных комментариев. Если требуется прокомментировать свойства какого-нибудь цикла, комментарии вставляются перед заголовком цикла.

DVM/OpenMP-эксперт обрабатывает следующие специальные комментарии:

· private(<переменная>) - задаёт переменную, для которой порождается локальная копия в каждой нити; начальные значения локальных переменной не определено.

· private_all(<переменная>) - задаёт переменную, которая будет private на протяжении всей программы.

· first_private(<переменная>) - задаёт переменную, для которой порождается локальная копия в каждой нити; локальные копии переменных инициализируются значением этой переменной в нити-мастере;.

· last_private(<переменная>) -переменной присваивается результат с последнего витка цикла;

· reduction(<переменная>(<оператор>)) - задаёт оператор и переменную; для переменной создаются локальные копии в каждой нити; локальные копии инициализируются соответственно типу оператора (для аддитивных операций - 0 или его аналоги, для мультипликативных операций - 1 или её аналоги); над локальными копиями переменной после выполнения всех операторов параллельной области выполняется заданный оператор [9]. В Таблице 1 отражено соответствие между текстовым представлением <оператор> и его аналогом на языке Fortran.

<оператор>	Оператор языка Fortran
SUM	+
PRODUCT	*
MAX	Max
MIN	Min
AND	.and.
OR	.or.
EQV	.eqv.
NEQV	.neqv.

Таблица 1. Редукционные операции.

1.13.3 Аргументы командной строки

Рассмотрим аргументы командной строки, доступные при использовании DVM/OpenMP-эксперта.

Ключ	Описание
-omp	Отрабатывает только OpenMP-эксперт. На выходе получаем параллельную программу для SMP-системы на языке Fortran-OpenMP.
-dvm	Отрабатывает только DVM-эксперт. На выходе получаем параллельную программу для кластера на языке Fortran-DVM.
-omp -dvm	Если присутствуют оба ключа (или нет ни одного из этих ключей), отрабатывает DVM/OpenMP-эксперт. На выходе получаем параллельную программу для SMP-кластера на языке Fortran-DVM/OpenMP
-variants	Включается режим, в котором на выходе выдаются все варианты распараллеливания. Это могут быть DVM-варианты, OpenMP-варианты или DVM/OpenMP-варианты в зависимости от присутствия ключей -omp и -dvm.
-nproc <число>	Задаем количество узлов кластера
-ncore <число>	Задаем количество ядер, находящихся на каждом из узлов

Таблица 2.Аргументы командной строки

1.14 Результаты тестирования

Тестирование анализатора проводилось на программах, реализующих решение уравнения Пуассона в трехмерном пространстве классическими итерационными методами: методом Якоби, методом последовательной верхней релаксации (SOR), методом красно-черного упорядочения (RedBlack), а также тесте, разработанном NASA Ames Research Center (LU). В тестах Якоби, SOR и RedBlack использовалась матрица размером 3000x3000.

DVM/OpenMP-варианты, полученные на указанных тестах с помощью DVM/OpenMP-эксперта, успешно прошли проверку на инструменте Intel Thread Checker 3.1. Intel Thread Checker - инструмент для отладки параллельных программ. Он осуществляет поиск мест с возможным недетерминированным поведением многопоточной программы, написанной как на основе библиотеки потоков (Windows или POSIX threads), так и с использованием технологии OpenMP. Intel Thread Checker рассматривает DVM/OpenMP-вариант как программу на языке Fortran-OpenMP. Отметим, что Intel Thread Checker не в состоянии проверить отсутствие ошибок в работе конвейерного алгоритма.

Тесты NAS являются самопроверяющимися, что позволяет убедиться в том, что распараллеленная программа выдает такой же результат, что и последовательная программа. Все сгенерированные DVM/OpenMP-варианты теста LU прошли проверку успешно.

Также отметим, что скорость работы DVM/OpenMP-эксперта почти не уступает скорости DVM-эксперта. Замедление в работе отражено в Таблице 3 на различных тестах.

Название теста	Замедление работы эксперта
Якоби	0,45%
SOR	0,18%
RedBlack	3%
LU	0,0683%

Таблица 3. Замедление работы DVM/OpenMP-эксперта по сравнению с DVM-экспертом

В Таблице 4 приведены времена выполнения DVM/OpenMP-вариантов для тестовых программ. В Таблице 5 - ускорения программ. Ускорение вычисляется как отношение времени выполнения теста на одном ядре ко времени выполнения распараллеленного теста на нескольких ядрах. Программы компилировались как Fortran-OpenMP-программы, и запускались на вычислительном комплексе IBM eServer pSeries 690 (Regatta).

Количество ядер	Времена выполнения тестовых программ, сек.
	Якоби	SOR	RedBlack	LU
1	2,26	0,42	5,48	206,41
2	1,41	0,28	3,39	148,44
4	0,91	0,23	3,36	125,79
8	0,76	0,46	6,13	117,21

Таблица 4. Времена запуска тестовых программ, в секундах

Количество ядер	Ускорение тестовых программ
	Якоби	SOR	RedBlack	LU
2	1,60	1,50	1,62	1,39
4	2,48	1,83	1,63	1,64
8	2,97	0,91	0,89	1,76

Таблица 5. Ускорения, продемонстрированное на тестовых программах

Графики временен выполнения и ускорений распараллеленных тестовых примеров можно найти в Приложении А.

Заключение

В рамках дипломной работы был реализована программа DVM/OpenMP-эксперт. Общий объем разработанного кода составил более 2000 строк на языке С++.

DVM/OpenMP-эксперт входит в состав экспериментальной системы автоматизации распараллеливания. За основу разработки был взят компонент системы, реализованный к моменту начала работы над поставленной задачей - DVM-эксперт.

Работа системы успешно прошла проверку инструментом Intel Thread Checker, а также самопроверяющимся тестом от NASA Ames Research Center. Также система была протестирована на Fotran-программах, реализующих следующие алгоритмы: классический алгоритм Якоби, алгоритм верхней релаксации (SOR), алгоритм решения системы линейных алгебраический уравнения методом Гаусса, алгоритм красно-черного упорядочения (RedBlack), а также на тесте NAS LU. Распараллеленные тесты продемонстрировали ускорение при запуске на SMP-системе.

Приложение А. Графики времен выполнения и ускорений распараллеленных тестовых программ

График 1.А График 1.Б

График 2.А График 2.Б



График 3.А График 4.Б

График 4.А График 4.Б