*DVM$* ACROSS (a(0:0,1:1,0:0))
do i=1,N-1
do j=1,M
!$OMP PARALLEL PRIVATE(j, k)
!$OMP DO SCHEDULE (STATIC)
do k=1,P
A( I, J, K ) = (A( I, J, K ) + A( I, J, K ) +
* A( I, J-1, K) + A( I, J+1, K ))
enddo
!$OMP END DO
!$OMP END PARALLEL
enddo
enddo
Тесно-вложенные циклы – два цикла, расположенные таким образом, что один цикл является телом другого цикла.
Гнездо циклов - набор циклов, расположенных таким образом, что один цикл является телом другого цикла, гнездо циклов может состоять из одного цикла.
Внешний цикл в гнезде – цикл, который не вложен ни в один из циклов гнезда.
Внутренний цикл в гнезде – цикл, в который не вложен ни один из циклов гнезда.
Гнездо циклов распараллелено на DVM – витки циклов, принадлежащих гнезду, распределяются между узлами с помощью DVM-директив.
Гнездо циклов распараллелено на OpenMP – один из циклов гнезда распараллелен на OpenMP.
Интервал – некоторый участок выполнения программы. В дальнейшем нас будет интересовать только два вида интервалов: гнездо циклов и тело всей программы.
Внутреннее представление DVM-эксперта – набор структур, хранящих информацию о программе. DVM-эксперт заполняет эти структуры, пользуясь информацией из Базы данных.
Специальные комментарий – комментарий языка программирования, который пользователь может вставить в код программы. Специальный комментарий начинается с последовательности символов CPRG. Он сообщает о какой-нибудь особенности, относящейся к оператору, следующему после специального комментария.
Блок поиска DVM/OpenMP-вариантов распараллеливает на OpenMP каждый DVM-вариант. Результатом его работы являются DVM/OpenMP-варианты. При этом DVM/OpenMP-вариантов получается ровно столько же, сколько было DVM-вариантов.
Для каждого гнезда циклов, распараллеленного в DVM-варианте, Блок поиска DVM/OpenMP-вариантов выполняет следующее:
- Формирует варианты распараллеливания этого гнезда циклов на DVM/OpenMP.
- Оценивает время выполнения распараллеленного гнезда циклов в модели DVM/OpenMP.
- На основании оценки выбирает наилучший вариант распараллеливания гнезда циклов.
- Заносит OpenMP-директивы, распараллеливающие гнездо циклов выбранным способом, в DVM/OpenMP-вариант.
Блок поиска DVM/OpenMP-вариантов работает не напрямую с Базой данных, а использует Внутреннее представление, сформированное DVM-экспертом. Нас будет интересовать следующая информация о программе:
· Описание SMP-кластера
o количество узлов кластера
o количество ядер, располагающихся на одном узле
· Описание программной единицы (модуля)
o номер строки первого оператора
· Описание переменных (в том числе массивов):
o текстовое представление
o количество измерений массива (для скаляра – одно измерение)
o количество элементов массива (для скаляра – один элемент)
· Описание циклов (отметим, что модуль программы также считается циклом – циклом верхнего уровня)
o индексная переменная
o начальное значение, конечное значение и шаг итератора цикла.
o приближенное время выполнения одной итерации цикла
o цикл, в который вложен данный цикл (родительский цикл)
o признак тесно-вложенности данного цикла в родительский цикл
o список циклов, вложенных в данный
o номера строк, на которых располагаются операторы цикла
o номер первой строки цикла (заголовка цикла)
o список особенностей цикла.
Рассмотрим, какие цикл может иметь особенности:
· Цикл содержит приватные переменные. Существует три вида приватности: private, first_private, last_private.
· Цикл имеет редукционную зависимость (reduction).
Таким образом, особенность – это пара (<тип особенности>, <переменная>). Типособенностиможетбытьтаким: private, first_private, last_private, reduction. Если тип особенности – reduction – то дополнительно хранится редукционная операция.
Примечание:
Эти особенности взаимно-однозначно соответствуют клаузам OpenMP, и подробнее о них можно прочитать в разделе Специальные комментарии.
Также отметим, что Внутреннее представление DVM-эксперта не содержит полную информацию о переменных с приватной особенностью. Так, индексные переменные циклов и скаляры, используемые в цикле на запись, не отмечены как приватные в особенностях циклов. Нам следует добавить эти особенности самостоятельно.
Рассмотрим более детально алгоритм работы Блока поиска 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$ PARALLELON и определить
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 до М.