Цель данного диплома – разработка программы, реализующей "Эксперт для мультипроцессора" в проекте. На основании данных, полученных на стадии анализа, и характеристик конкретного мультипроцессора "Эксперт" должен занести в базу данных информацию о комментариях (директивах OpenMP), которые должны быть вставлены в программу, которая получится на выходе системы, а также информацию о прогнозируемой эффективности распараллеливания. Таким образом, "Эксперт" генерирует, оценивает и выбирает лучшие варианты распределения вычислений и локализации данных. Эксперт не изменяет код программы, а лишь вносит в базу данных информацию о "наилучших рекомендациях по распараллеливанию". Эта информация впоследствии и будет выдана пользователю.
Описание цикла содержит:
· указание на переменную цикла;
· первое, последнее значение;
· наличие в цикле операторов ввода-вывода, побочных выходов и т.п.
· оценка трудоемкости одного витка цикла;
· признак тесной вложенности;
· список обращений к массивам и переменным.
Дерево циклов – множество циклов с отношением "непосредственно вложен в". Корень "дерева циклов", уровень программы, сам циклом не является, но формально может считаться "циклом" без переменной цикла с однократным выполнением.
Список массивов (и простых переменных).
Для каждого массива:
· идентификатор;
· размер по каждому измерению;
· список обращений к массиву.
Вариант задачи:
· размерности массивов по каждому измерению (уже как константы);
· число итераций;
· или значения внешних переменных, от которых зависят эти величины.
Вариант массива процессоров:
· число измерений и размер по каждому измерению (решетка процессоров).
Обращения к массивам (и переменным) в цикле – отношение "к <массиву> обращаются в <цикле>". Для каждой пары <массив, цикл>:
· нет (не создает) зависимости ни между итерациями, ни внутри;
· зависимость внутри одной итерации;
· REDUCTION (зависимость между итерациями создают операторы специального вида, типа a=a+xi);
· Private, Lastprivate, Firstprivate – приватныепеременные
· возникающая из-за него зависимость между итерациями общего вида.
Список всех обращений, т.е. наборов индексных выражений, желательно без повторений. Про каждое надо указать:
· чтение или/и присваивание;
· индексные выражения;
Выходные данные представляют собой:
· Вариантраспараллеливания программы. Вариант представляет собой набор правил получения OpenMP-программы. Оценка эффективности выполняется для данного варианта распараллеливания и данного варианта запуска.
· Оценка данного варианта распараллеливания и данного варианта запуска: параметры производительности цикла, программы в целом и эффективности распараллеливания.
· Информация, объясняющая, почему выбрано данное распределение. Для каждой вставленной директивы производится вычисление ускорения, полученного за счет этой директивы.
Здесь будет произведен краткий обзор систем, в которых разработчики и рабочие группы достигли значительных продвижений в решении задачи.
1) Interactive Parallelizing Assistance Tool for OpenMP [7]
AachenUniversity, Германия. 2003 г.
Система анализирует эффективность OpenMP программы и выдает результаты анализа пользователю. Система работает только с циклами. Для конкретного цикла можно посмотреть, какие директивы OpenMP возможны для вставки. По результатам анализа пользователь сам вставляет директивы или меняет код программы. Есть опция выбора отдельного участка программы для проверки на возможность распараллеливания.
2) Interprocedural Parallelizing Compiler WPP and Analysis Information Visualization tool Aivi [8]
Hitachi, Ltd. Япония. 2000 г.
Система производит межпроцедурный анализ: анализ скаляров и массивов, клонирование процедур, анализ вызовов функций. Система работает только с циклами. Генерация OpenMP директив происходит автоматически. В систему входит мощный инструмент визуализации, показывающий пользователю результаты анализа.
3) The ParaWise Expert Assistant [6]
University of Greenwich, Великобритания. Август 2004.
Представляет собой один из инструментов системы ParaWise/CAPO [5]. На основании инструментов системы, проводящих анализ программы, "Эксперт- ассистент" подсказывает: возможно ли распараллеливание, и представляет некоторые варианты распараллеливания (вставки OpenMP директив).
Новыми свойствами, отличающими нашу систему от перечисленных здесь, являются ориентация на кластер и мультипроцессор и возможность пропустить взаимодействие с пользователем, лишь только запросив "добро" на вставку директив. Первое свойство особо важно, так как распараллеливание программ для будущих высокопроизводительных систем с многоуровневым параллелизмом связано с использованием обеих моделей OpenMP и DVM.
Так как решение задачи вставки OpenMP директив напрямую зависит от данных, предоставляемых анализатором, то построение решения задач "Эксперта" мы можем рассматривать только в тесной привязке к данным анализа.
Работа с Базой Данных для эксперта происходит посредством интерфейса. Основная часть Базы Данных- дерево циклов. Структура дерева важна для описания алгоритмов работы эксперта. Вершины дерева могут быть следующих типов:
· Процедура. В данной версии "Системы автоматического распараллеливания" процедурой считается только тело программы.
· Цикл. Цикл содержит информацию обо всех переменных, использующихся в нем, зависимостях, найденных в нем анализатором, времени исполнения одного витка, количество итераций для данного варианта задачи.
· Линейный фрагмент.
· Условный оператор.
Выходными данные эксперта являются комментарии к вершинам дерева циклов. По этим комментариям в выходную программу вставляются директивы OpenMP. Важно заметить, что комментарии могут быть проставлены до вершины, что означает директивы OpenMP, соответствующие комментарию будут стоять до оператора, соответствующего вершине. Второй вариант – комментарии после вершины, что означает директивы OpenMP, соответствующие комментарию будут стоять после действий оператора, соответствующего вершине.
При составлении алгоритмов эксперта были учтены следующие возможности 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. Внутренние представления "Эксперта".