Практическая реализация

 

Список используемых терминов

Тесно-вложенные циклы – два цикла, расположенные таким образом, что один цикл является телом другого цикла.

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

Внешний цикл в гнезде – цикл, который не вложен ни в один из циклов гнезда.

Внутренний цикл в гнезде – цикл, в который не вложен ни один из циклов гнезда.

Гнездо циклов распараллелено на 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-особенность для индексных переменных этих циклов, а также всех вложенных циклов.