Система автоматизации распараллеливания. Отображение на SMP-кластер

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

Для каждого гнезда циклов, распараллеленного в DVM-варианте, Блок поиска DVM/OpenMP-вариантов выполняет следующее:

§ Формирует варианты распараллеливания этого гнезда циклов на DVM/OpenMP.

§ Оценивает время выполнения распараллеленного гнезда циклов в модели DVM/OpenMP.

§ На основании оценки выбирает наилучший вариант распараллеливания гнезда циклов.

§ Заносит OpenMP-директивы, распараллеливающие гнездо циклов выбранным способом, в DVM/OpenMP-вариант.

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

Этап 1. Подготовительная работа

Шаг 1.1. Переход от DVM-вариантов к DVM/OpenMP-вариантам.

Прежде всего, DVM-варианты следует перенести из внутреннего представления DVM-эксперта во внутреннее представление DVM/OpenMP-варианта. Внутреннее представление каждого DVM/OpenMP-варианта - это ассоциативный массив. Ключами ассоциативного массива являются номера строк программы, а значением - список DVM- и OpenMP-директив, которые следует вставить перед данной строкой. Соответственно, по окончанию данного этапа списки директив будут содержать только DVM-директивы.

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

Шаг 1.2. Добавление приватных особенностей для индексных переменных

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

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

Шаг 1.3 Добавление приватных особенностей для скаляров

Предположим, в теле цикла в некоторую скалярную переменную происходит запись, и между витками цикла отсутствуют зависимости по данным. Если оставить эту переменную общей для всех нитей, мы получим условие гонок (race-condition). Чтобы избежать этой ситуации, в описание цикла следует добавить private-особенность для данной переменной.

Возможна ситуация, что эта переменная по окончанию цикла будет использована на чтение. В этом случае, для данной переменной в описании цикла уже должна была присутствовать last-особенность.

Подытожим: если в теле цикла в какую-нибудь скалярную переменную происходит запись, для неё в описание цикла следует добавить private-особенность.

Шаг 1.4 Добавление all_private особенностей

Из Базы данных может поступить информация о том, что какая-либо переменная является приватной на протяжении всей работы программы. Для отражения этого факта существует специальный комментарий all_private (см. раздел Специальные комментарии).

Чтобы добавить эту информацию в описания циклов, нужно сделать следующее:

· На этапе считывания особенностей из Базы данных запомнить список all_private переменных

· Добавить private-особенности для полученного списка переменных в описание всех циклов программы.

Этап 2. Распараллеливание DVM-вариантов на OpenMP

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

Итак, для каждого гнезда циклов, распараллеленного на DVM в DVM/OpenMP-варианте, выполняем следующие шаги:

Шаг 2.1. Сбор информации о циклах в гнезде.

Просматриваем дерево циклов программы. Нас будут интересовать только те циклы, которые распараллелены в DVM-варианте. Для формирования DVM/OpenMP-варианта распараллеливания программы, необходимо собрать следующую информацию о гнезде циклов:

· Список циклов, принадлежащих гнезду. Первый элемент цикла - внешний цикл.

· Количество итераций каждого цикла из гнезда (если точное значение вычислить невозможно, выбирается значение по умолчанию).

· Время выполнения одной итерации каждого цикла из гнезда.

· Проанализировать DVM-директиву CDVM$ PARALLEL ON и определить

o Как отображаются измерения массива на циклы из гнезда.

o На какие циклы из гнезда не распределены измерения массива.

o Присутствует ли в гнезде регулярная зависимость. Если да, то определить, для каких измерений массива присутствует регулярная зависимость, и каким из циклов в гнезде эти зависимости соответствуют.

Примечание:

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

Этот метод не может дать точного результата. Например, если все измерение массива распределено на узел, то ни клауза ACROSS, ни клауза SHADOW_RENEW не смогут сообщить о наличии регулярной зависимости.

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

Шаг 2.2. Формирование вариантов распараллеливания гнезда.

Этот шаг следует выполнить для каждого гнезда циклов, которое распараллелено в DVM-варианте.

Пробегаемся по списку циклов гнезда, и пытаемся поочередно распараллелить их на OpenMP. Пусть наше гнездо содержит M циклов. Пронумеруем циклы от 1 до M. Цикл с номером 1 - внешний. Первый вариант распараллеливания гнезда у нас уже есть - распараллелить внешний цикл на DVM, и не распараллеливать на OpenMP. Формируем еще M вариантов следующего вида: внешний цикл распараллелен на DVM, а i-й цикл гнезда распараллелен на OpenMP, где i принимает значения от 1 до М.

Возможны два способа для распараллеливания i-го цикла в гнезде:

Способ 1. Распараллеливание с использованием конвейера.

Если цикл соответствует измерению массива с регулярной зависимостью, для него невозможно независимое выполнение витков. Мы можем организовать конвейерное выполнение цикла при условии, что для него есть тесно-вложенный цикл (см. варианты 4.1 и 5.2). В противном случае, мы не будем распараллеливать этот цикл. Также, мы не сможем распараллелить цикл конвейером, если для записи этих двух циклов используется одна и та же метка.

Такой эффект вызван особенностью используемого алгоритма распараллеливания конвейером.

Итак, если цикл соответствует измерению массива с регулярной зависимостью, имеет тесно-вложенный цикл и для записи этих циклов не используется одна и та же метка, мы ставим для этого цикла метку "Распараллелен конвейером".

Способ 2. Распараллеливание без конвейера.

Если цикл не соответствует измерению массива с регулярной зависимостью, этот цикл распараллеливается без конвейера (см. варианты 1.1, 1.2, 3.1, 3.2, 5.1 и 5.3). Ставим для этого цикла метку "Распараллелен без конвейера".

Если ни один из способов не подошел, i-й цикл мы распараллеливать не будем. Также, если количество итераций i-го цикла достаточно мало (каждому узлу достанется не более одного витка цикла, то есть работать на узле будет не более одного ядра), цикл признается неэффективным для распараллеливания на OpenMP, и соответствующий вариант отбрасывается.

Шаг 2.3. Поиск наилучшего варианта распараллеливания гнезда.

С помощью оценочной функции (о ней мы поговорим далее), мы вычисляем приближенное время выполнения каждого варианта на SMP-кластере с заданным количеством узлов и ядер. Располагая прогнозируемым временем выполнения каждого варианта распараллеливания гнезда циклов, мы выбираем вариант с наименьшим временем. При оценке учитываем, каким способом мы распараллеливаем цикл - с использованием конвейера, или без.

Шаг 2.4. Вставка OpenMP-директив в DVM/OpenMP-вариант.

Итак, мы выбрали, как лучше всего распараллелить гнездо циклов: либо распараллеливаем на OpenMP один из циклов гнезда, либо не распараллеливаем ни один из них. Если мы приняли решение распараллелить i-й цикл в гнезде, нам нужно вставить OpenMP-директивы в DVM/OpenMP-вариант. Возможны два случая:

Случай 1. i-й цикл имеет метку "Распараллелен с конвейером".

Выполняем следующие действия:

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

!$ INTEGER omp_get_num_threads, omp_get_thread_num

!$ INTEGER IAM, NUMT, ISYNC(<количество нитей>), ILIMIT

2. Добавляем в описание i-го цикла три особенности приватного типа - для переменных IAM, NUMT и ILIMIT.

3. Формируем директиву !$OMP PARALLEL. Для распараллеливания на OpenMP цикла с особенностями после директивы требуется вставить клаузы. Пробегаемся по списку особенностей.

3.1. Если особенность имеет тип private, first_private или last_private, для нее формируем клаузу PRIVATE (<список переменных>), FIRSTPRIVATE (<список переменных>) или LASTPRIVATE (<список переменных>). Отметим, что в списке особенностей одна и та же переменная может иметь одновременно две разных особенности - private и first_private (private и last_private). В этом случае переменную следует занести только в клаузу FIRSTPRIVATE (LASTPRIVATE).

3.2. Если особенность имеет тип reduction, для нее формируем клаузу REDUCTION(<операция>: <список переменных>). Для разных операций создается отдельная клауза REDUCTION.

4. Обозначаем начало параллельной области. Перед заголовком i-го цикла вставляем директиву !$OMP PARALLEL с клаузами, сформированными в предыдущем пункте.

5. Сразу после !$OMP PARALLEL <список клауз> добавляем инициализацию служебных переменных и барьерную синхронизацию нитей:

!$ iam = omp_get_thread_num ()

!$ numt = omp_get_num_threads ()

!$ ILIMIT=MIN(NUMT-1,<число витков i-го цикла>)

!$ ISYNC (IAM) = 0

!$OMP BARRIER

6. Перед заголовком i+1-го цикла добавляем инициализацию конвейера: ядро дожидается, пока предыдущее ядро выполнит очередную итерацию 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

7. Перед ENDDO i-го цикла добавляем операции по синхронизации работы ядер

!$OMP ENDDO NOWAIT

!$ IF (IAM .LT. ILIMIT) THEN

!$ DO WHILE (ISYNC (IAM) .EQ. 1)

!$OMP FLUSH (ISYNC)

!$ ENDDO

!$ ISYNC (IAM)=1

!$OMP FLUSH(ISYNC)

!$ ENDIF

8. После ENDDO i-го цикла обозначаем завершение параллельной области.

!$OMP END PARALLEL

Случай 2. i-й цикл имеет метку "Распараллелен без конвейера".

1. Формируем директиву !$OMP PARALLEL. Выполняем действия, описанные в пункте 3 предыдущего случая.

2. Обозначаем начало параллельной области и распределение витков цикла между ядрами. Вставляем сформированную директиву !$OMP PARALLEL с клаузами, а также директиву !$OMP DO SCHEDULE(STAITC), перед заголовком i-го цикла.

3. Обозначаем конец параллельного цикла и параллельной области. После ENDDO i-го цикла вставляем директивы:

!$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 * Число_раб_ядер

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

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

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

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

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

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

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

Итак, мы оценили Время i-го цикла. Чтобы вычислить время выполнения всего гнезда циклов, это время следует умножить на количество раз, которое этот цикл выполняется. Таким образом, время выполнения гнезда равняется N1 * N2 * … * Ni-1 * Время i-го цикла.

Для начала рассмотрим принцип работы Блока поиска DVM-варианта. DVM-варианты подаются на вход "Блоку перебора вариантов и поиска наилучшего" (далее, Блок перебора вариантов). Этот блок занимается поиском оптимальной решетки процессоров, а также наилучшего варианта распараллеливания.

Для поиска оптимальной решетки и наилучшего варианта, Блок перебора пользуется Библиотекой предсказателя производительности DVM-программ, сокращенно Библиотеке DVM-предиктора.

DVM-предиктор предназначен для анализа и отладки производительности DVM-программ без использования реальной параллельной машины (доступ к которой обычно ограничен или сложен). С помощью DVM-предиктора пользователь имеет возможность получить предсказанные временные характеристики выполнения его программы на MPP или кластере рабочих станций с различной степенью подробности. [10]

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

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

Далее, Блок перебора подает на вход Библиотеке предиктора DVM-варианты только на оптимальной решетке.

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

Теперь рассмотрим, какие следует внести изменения, чтобы получить "Блок поиска наилучшего DVM/OpenMP-варианта".

Рисунок 7. Принцип работы "Блока поиска DVM/OpenMP-варианта"

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Страницы: 1, 2