Список массивов (и простых переменных)

Для каждого массива:

· идентификатор;

· размер по каждому измерению;

· список обращений к массиву.

Вариант задачи:

· размерности массивов по каждому измерению (уже как константы);

· число итераций;

· или значения внешних переменных, от которых зависят эти величины.

Вариант массива процессоров:

· число измерений и размер по каждому измерению (решетка процессоров).

Обращения к массивам (и переменным) в цикле – отношение "к < массиву > обращаются в < цикле >". Для каждой пары <массив, цикл>:

· нет (не создает) зависимости ни между итерациями, ни внутри;

· зависимость внутри одной итерации;

· REDUCTION (зависимость между итерациями создают операторы специального вида, типа a=a+x_i);

· Private, Lastprivate, Firstprivate – приватные переменные

· возникающая из-за него зависимость между итерациями общего вида.

Список всех обращений, т.е. наборов индексных выражений, желательно без повторений. Про каждое надо указать:

· чтение или/и присваивание;

· индексные выражения;

 

Выходные и сохраняемые данные

 

Выходные данные представляют собой:

· Вариантраспараллеливания программы. Вариант представляет собой набор правил получения OpenMP-программы. Оценка эффективности выполняется для данного варианта распараллеливания и данного варианта запуска.

· Оценка данного варианта распараллеливания и данного варианта запуска: параметры производительности цикла, программы в целом и эффективности распараллеливания.

· Информация, объясняющая, почему выбрано данное распределение. Для каждой вставленной директивы производится вычисление ускорения, полученного за счет этой директивы.

3. Предыдущие решения "систем автоматизации распараллеливания"

 

Здесь будет произведен краткий обзор систем, в которых разработчики и рабочие группы достигли значительных продвижений в решении задачи.

1) Interactive Parallelizing Assistance Tool for OpenMP [7]

Aachen University, Германия. 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, соответствующие комментарию будут стоять после действий оператора, соответствующего вершине.