Список используемых терминов
Тесно-вложенные циклы – два цикла, расположенные таким образом, что один цикл является телом другого цикла.
Гнездо циклов -набор циклов, расположенных таким образом, что один цикл является телом другого цикла, гнездо циклов может состоять из одного цикла.
Внешний цикл в гнезде – цикл, который не вложен ни в один из циклов гнезда.
Внутренний цикл в гнезде – цикл, в который не вложен ни один из циклов гнезда.
Гнездо циклов распараллелено на DVM – витки циклов, принадлежащих гнезду, распределяются между узлами с помощью DVM-директив.
Гнездо циклов распараллелено на OpenMP – один из циклов гнезда распараллелен на OpenMP.
Интервал – некоторый участок выполнения программы. В дальнейшем нас будет интересовать только два вида интервалов: гнездо циклов и тело всей программы.
Внутреннее представление DVM-эксперта – набор структур, хранящих информацию о программе. DVM-эксперт заполняет эти структуры, пользуясь информацией из Базы данных.
Специальные комментарий – комментарий языка программирования, который пользователь может вставить в код программы. Специальный комментарий начинается с последовательности символов CPRG. Он сообщает о какой-нибудь особенности, относящейся к оператору, следующему после специального комментария.
|
|
Блок поиска DVM/OpenMP-вариантов
Краткий алгоритм работы
Блок поиска 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-особенность для индексных переменных этих циклов, а также всех вложенных циклов.