Каталог Рефератов - Система автоматизации распараллеливания отображения на мультипроцессор

	Информационно-образоательный портал
	Рефераты, курсовые, дипломы, научные работы,



МЕНЮ\|

поиск

Система автоматизации распараллеливания отображения на мультипроцессор

b>2. Цели дипломной работы

2.1 Цели проекта "Система автоматизации распараллеливания"

Данная дипломная работа является лишь частью проекта автоматизации распараллеливания программ, поэтому сначала остановимся на проекте.

Рис. 8. Проект: Система автоматизации распараллеливания.

На Рис. 8 схематически показаны составляющие проекта: "Анализ программы", "Эксперт для мультипроцессора" (OpenMP) и "Эксперт для кластера" (DVM).

Пользователь создает последовательную программу на языке Fortran. В итоге работы системы, пользователь получает информацию для анализа:

· дерево циклов; для каждого цикла - его параметры и атрибуты (результаты анализа);

· описания данных;

· описание использования массивов в циклах и найденные зависимости;

· список предложенных (в том числе рассмотренных, но отвергнутых) вариантов распределения (задача "Эксперта");

· созданные и модифицируемые пользователем наборы конфигураций целевой машины и размеров задач;

· для каждого предложенного варианта распараллеливания (всех конфигураций и размеров) и каждого цикла и всей программы, как корня дерева циклов, - оценки времени выполнения и качества распараллеливания для данного варианта (задача "Эксперта");

Программа, поступая в систему автоматизации распараллеливания, проходит анализ, на основании которого формируется База Данных, в которую входят: дерево циклов; описания массивов, описание использования массивов в циклах; дополнительные комментарии.

С информацией из базы данных "Эксперты" ищут самые оптимальные способы распараллеливания и добавляют информацию о них в базу данных. Код программы на выходе системы не изменяется, а всего лишь добавляются комментарии, где рекомендуется вставить директивы OpenMP или DVM (возможно несколько лучших вариантов), насколько будут эффективны эти вставки, а также информация из анализа.

2.2 Цели "Эксперта для мультипроцессора"

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

2.3 Входные данные

Описание цикла содержит:

· указание на переменную цикла;

· первое, последнее значение;

· наличие в цикле операторов ввода-вывода, побочных выходов и т.п.

· оценка трудоемкости одного витка цикла;

· признак тесной вложенности;

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

Дерево циклов - множество циклов с отношением "непосредственно вложен в". Корень "дерева циклов", уровень программы, сам циклом не является, но формально может считаться "циклом" без переменной цикла с однократным выполнением.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

· Вариант распараллеливания программы. Вариант представляет собой набор правил получения 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.

4. Построение решения задачи

Так как решение задачи вставки OpenMP директив напрямую зависит от данных, предоставляемых анализатором, то построение решения задач "Эксперта" мы можем рассматривать только в тесной привязке к данным анализа.

4.1 Формат входных данных

Работа с Базой Данных для эксперта происходит посредством интерфейса. Основная часть Базы Данных- дерево циклов. Структура дерева важна для описания алгоритмов работы эксперта. Вершины дерева могут быть следующих типов:

· Процедура. В данной версии "Системы автоматического распараллеливания" процедурой считается только тело программы.

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

· Линейный фрагмент.

· Условный оператор.

Выходными данные эксперта являются комментарии к вершинам дерева циклов. По этим комментариям в выходную программу вставляются директивы OpenMP. Важно заметить, что комментарии могут быть проставлены до вершины, что означает директивы OpenMP, соответствующие комментарию будут стоять до оператора, соответствующего вершине. Второй вариант - комментарии после вершины, что означает директивы OpenMP, соответствующие комментарию будут стоять после действий оператора, соответствующего вершине.

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

При составлении алгоритмов эксперта были учтены следующие возможности 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 - невозможно объявить общей

Страницы: 1, 2, 3, 4, 5, 6

© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент.