Основные аспекты работы эксперта

 

При составлении алгоритмов эксперта были учтены следующие возможности OpenMP:

1) возможность работы с циклами (директива DO).

2) возможность обработки редукционных переменных (директива REDUCTION).

3) возможность исполнять часть кода внутри цикла в "естественном" порядке (директива ORDERED).

4) возможность приватизировать переменные (директива PRIVATE).

5) возможность образовывать конвейер посредством OpenMP директив (эта возможность будет рассмотрена ниже).

6) возможность отмены синхронизаций между параллельными циклами (директива NOWAIT).

При работе эксперта все циклы в программе разбиваются на Потенциально Параллельные Циклы (далее ППЦ) и Циклы, Неподдающиеся Распараллеливанию (далее ЦНР). ППЦ – цикл, который можно распараллелить средствами OpenMP, не обязательно эффективно. ЦНР – циклы, которые не поддаются распараллеливанию из-за зависимостей по данным между витками цикла. Такие циклы бывают следующих видов:

1) содержащие ввод/вывод.

2) содержащие выход из цикла.

Основная цель "Эксперта"- нахождение для последовательной программы набора директив OpenMP такого, что ускорение параллельной программы при заданном варианте работы программы будет максимально. Назовем такой набор директив наилучшими комментариями к программе. Все комментарии разобьем на два вида: комментарии по локализации переменных (PRIVATE, REDUCTION и т.д.) и все другие комментарии. Назовем Вариантом параллелизма программы (далее Вариант параллелизма) – вариантдиректив OpenMP, описывающих параллельные области и параллельные циклы (без директив локализации переменных). Тогда Вариант локализации переменных (Вариант локализации) – вариантдиректив локализации переменных. Для каждого варианта параллелизма может существовать несколько вариантов локализации. Проверкой Альтернативной Локализации назовемнахождение минимума оценочной функции для набора локализаций для данного варианта параллелизма с фиксированием комментариев, соответствующих минимальной оценочной функцией. Схема распараллеливания – фиксация одного варианта параллелизма и одного варианта локализации.

Работа Эксперта для мультипроцессора разделена на 4 стадии:

1) Разделение всех циклов программы на ППЦ и ЦНР, обозначение видов ППЦ и предварительное фиксирование набора вариантов локализации переменных.

2) Перебор всевозможных вариантов распараллеливания программы, предварительное фиксирование наилучшего варианта параллелизма.

3) Перебор вариантов локализаций программы, фиксирование наилучшей схемы распараллеливания, подсчет ускорения.

4) Расстановка директив OpenMP, соответствующих наилучшей схеме распараллеливания, в программу.

В процессе работы "Эксперта" создаются внутренние представления данных, обеспечивающие решение задачи, представленные в Таблице 1

 

Название представления	На каком шаге создается	Что содержит	Зачем нужно
Первое внутреннее	1 шаг	1. Информация обо всех операторах программы 2. Информация о локализации программы "по умолчанию"	Базовое представление, на основании которого производится последующий анализ
Второе внутреннее	2-3 шаг	Схема распараллеливания, которая считается наилучшей	Для формирования комментариев (содержит информацию по распараллеливанию)
Список параллельных регионов	2 шаг	Все параллельные регионы программы	Для формирования комментариев (содержит информацию по локализации)
Программный список локализаций переменных	3 шаг	Список переменных, для каждой из которых ведется список локализаций в параллельных регионах программы	Для простановки комментария threadprivate

Таблица 1. Внутренние представления "Эксперта".

 

Первое внутреннее представление содержит информацию о локализации переменных.

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

Пометки проставляются для всех переменных, используемых внутри данного оператора. Все возможные пометки представлены в Таблице 2.

 

1-е значение 1-й пары (вид приватной)	2-е значение 1-й пары - пометка приватной
private (по умолчанию) firstprivate lastprivate reduction	Ind – индекс Set – Необходимо указать в комментариях Redtype() – тип редукции (только для редукционных) Pos (по умолчанию) – возможно объявить приватной, но не обязательно No – невозможно объявить приватной
1-е значение 2-й пары (общая)	2-е значение 2-й пары (пометка общей)
Shared (по умолчанию)	Def (по умолчанию) – общая по умолчанию Set – необходимо указать в директивах No – невозможно объявить общей

Таблица 2. Пометки по локализации переменных.

 

Как пометки соответствуют директивам OpenMP:

Если 2-е значение 1-й пары = Set, переменную необходимо объявить PRIVATE.

Если 2-е значение 2-й пары = Set, переменную необходимо объявить SHARED.

Если 1-е значение 1-й пары = reduction, необходима директива REDUCTION(2-е значение 1-й пары: имя переменной).

Если 1-е значение 1-й пары = lastprivate, необходима директива LASTPRIVATE(имя переменной).

Если 1-е значение 1-й пары = firstprivate, необходима директива FIRSTPRIVATE(имя переменной).

 

Оценочные функции

 

1) Оценочная функция стоимости параллельного региона вычисляется по следующей формуле:

Стоимость параллельного исполнения = (стоимость последовательного исполнения / число нитей + стоимость ordered) * число итераций + стоимость создания и удаления параллельной области стоимость последовательного исполнения

 

Это стоимость одной итерации цикла (предоставлена анализатором) без учета стоимости выражений, окруженных директивами Ordered/End Ordered число нитей – количество "полезных" процессоров. Для цикла это значение равно минимуму из общего количества процессоров и количества итераций цикла.

 

стоимость ordered = стоимость последовательного исполнения выражений, окруженных директивами Ordered/End Ordered.

стоимость создания и удаления параллельной области = const + стоимость создания m приватных переменных + стоимость синхронизации. Константа зависит от архитектуры системы и берется из базы данных или определяется пользователем. Это время, необходимое для создания (инициализации) и удаления параллельного региона.

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

стоимость синхронизации = количество приватных переменных. Синхронизация происходит при закрытии параллельного цикла. При этом необходимо синхронизировать все локальные копии переменных. Стоимость барьерной синхронизации, зависящей от аппаратуры, учитывается в стоимости удаления параллельной области.

 

2) Оценочная функция стоимости вычисляется по следующей формуле:

 

Стоимость конвейера = стоимость действий внутри конвейера * количество действий конвейера + инициализация конвейера + синхронизация конвейера.

стоимость действий внутри конвейера = стоимость последовательного исполнения внутреннего цикла (конвейер возможен лишь для тесно вложенных циклов).

количество действий конвейера, количество действий, когда в работу задействована хотя бы 1 нить.

инициализация конвейера = const, зависит от архитектуры системы и берется из базы данных или определяется пользователем.

синхронизация конвейера = количество директив FLUSH, BARRIER и ENDDO * количество локальных переменных * количество действий конвейера.

 

3) Оценочная функция региона равна сумме всех оценочных функций членов региона.

5. Пошаговая реализация "Эксперта"