Система автоматизации распараллеливания Отображение на SMP-кластер (стр. 2 из 8)

Данное направление является весьма востребованным по следующим причинам:

- Распараллеливание готовой программы требует от программиста тщательного анализа ее кода (подчас, чужого), что делает процесс распараллеливания достаточно сложным, и подчас приводит к неудовлетворительным результатам. К тому же, в процессе распараллеливания могут быть допущены ошибки. Если бы распараллеливание осуществлялось автоматически, то появление новых ошибок было бы исключено.

- Распараллеливание уже готовых последовательных программ является очень востребованным, особенно в области научного программирования, где за многолетнюю историю жизни языка Fortran была написано огромное количество программ, не потерявших свою актуальность. Таким образом отпала бы необходимость писать все эти программы заново, но уже в параллельном варианте, и появилась бы возможность использовать старые наработки.

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

Постановка задачи

1.5 Структура "Системы автоматизации распараллеливания"

Данная дипломная работа посвящена разработке блока экспериментальной системы автоматизации распараллеливания, поэтому сначала ознакомимся с её структурой:

Рисунок 1. Экспериментальная система автоматизации распараллеливания

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

Пользуясь информацией из Базы данных, DVM/OpenMP-эксперт формирует варианты распределения вычислений и данных, и ищет наилучший вариант. Для поиска требуется информация о количестве вычислительных узлов, их производительности, а также латентности вычислительно сети. Далее, База данных подается на вход Генератору, который формирует параллельный код на языке Fortran-DVM/OpenMP. Код программы на выходе системы не изменяется, в него лишь добавляются директивы OpenMP и DVM.

1.6 Цель работы "DVM/OpenMP-эксперт"

К моменту написания работы, Система автоматизации распараллеливания содержала блок, именуемый DVM-экспертом. DVM-эксперт, пользуясь результатами анализа программы, распараллеливает программу на языке Fortran-DVM. Целью дипломной работы является доработка DVM-эксперта до DVM/OpenMP-эксперта.

DVM/OpenMP-эксперт, пользуясь результатами анализа, распараллеливает программу на языке Fortran-DVM/OpenMP и заносит информацию о полученной параллельной программе в Базу данных.

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

В настоящее время имеется только одна развивающаяся система автоматизированного распараллеливания для кластеров – Parawise (системы FORGE Magic/DM и BERT77 уже не развиваются и не поддерживаются). Только для нее имеется информация о применимости для реальных Fortran-приложений и эффективности выполнения распараллеленных программ.

1.7 Система Parawise

Система Parawise является коммерческой системой, созданной компанией Parallel Software Products совместно с NASA Ames на базе системы CAPTools, разработанной в Лондонском университете Гринвича в середине 90-х годов. [3]

Общая схема процесса получения параллельной программы из последовательной состоит из следующих этапов:

o Системе Parawise подаётся на вход программа на языке FORTRAN (F77/F90/F95).

o Пользователь выбирает способы анализа данной программы.

o Parawise анализирует программу и формирует вопросы, на которые пользователь обязан дать ответ для успешного распараллеливания.

o Пользователь следует по построенному системой графу зависимостей, отвечает на поставленные вопросы и участвует в выборе варианта распределения массивов.

o Система создаёт параллельный код программы.

o Пользователь проверяет результаты распараллеливания, и, если они не удовлетворительные, заново отвечает на поставленные вопросы или изменяет программу. [7]

Главным достоинством системы Parawise являются развитые возможности межпроцедурного анализа, которые создавались в течение многих лет. Главный недостаток – программист должен сам принимать ответственное решение о том, какие массивы и каким образом требуется распределить между процессорами. [3]

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

Исследование и построение решения задачи

1.8 Автоматическое распараллеливание программ на DVM и DVM/OpenMP

При распараллеливании программы на DVM пользователю необходимо:

1) распределить массивы данных между узлами

2) распределить витки циклов между узлами по принципу собственных вычислений

3) организовать доступ к удаленным данным.

При распараллеливании на на DVM/OpenMP пользователю дополнительно следует выполнить еще один шаг:

4) распределить витки циклов, распределенные на узел, между ядрами на узле.

Отметим, что эти этапы можно выполнить различными способами. Полученные варианты распараллеливания будут иметь различную эффективность.

Рассмотрим общий алгоритм работы автоматического распараллеливателя Fortran-программ – DVM-эксперта. Пользуясь результатами анализа последовательной программы, DVM-эксперт формирует варианты распределения данных и вычислений Fortran-программы. Будем называть DVM-вариантом программу на языке Fortran-DVM, сгенерированную DVM-экспертом. DVM-вариантотражает один из способов распараллеливания последовательной программы на языке DVM. DVM-директивы несут для параллельного компилятора информацию о том, как следует выполнить пункты 1) – 3). Вариантов распараллеливания программы для одной Fortran-программы может быть несколько, поэтому среди всех возможных DVM-вариантов следует отыскать наилучший, и выдать его пользователю системы. Чтобы определить, какой из DVM-вариантов лучше, DVM-эксперт обращается к Библиотеке предсказателя производительности DVM-программ, сокращенно Библиотеке DVM-предиктора. DVM-предиктор моделирует параллельное выполнение DVM-программы и вычисляет характеристики эффективности параллельного выполнения DVM-программы. Полученные характеристики позволяют DVM-эксперту выбрать наилучший DVM-вариант.

DVM/OpenMP-эксперт является доработкой DVM-эксперта. После генерации вариантов распараллеливания программы на DVM, каждый DVM-вариант следует распараллелить на OpenMP – то есть выполнить пункт 4). Полученные DVM/OpenMP-программы будем называть DVM/OpenMP-вариантами.

1.9 Структура DVM-эксперта

Для начала, рассмотрим структуру и принцип работы DVM-эксперта, существовавшего до начала работы.

Рисунок 2. Схема работы DVM-эксперта

База данных подается на вход Блоку поиска DVM-вариантов, который пользуется результатами анализа программы, и формирует варианты распараллеливания программы на DVM (DVM-варианты). Далее, DVM-варианты передаются Блоку поиска наилучшего DVM-варианта, который выбирает решетку процессоров и наилучший вариант распараллеливания программы. Затем Блок записи результатов в Базу данных записывает выбранный вариант распараллеливания в Базу данных.

Теперь рассмотрим, как следует изменить структуру DVM-эксперта, чтобы получить DVM/OpenMP-эксперт.

Структура DVM/OpenMP-эксперта

Рисунок 3. Схема работы "DVM/OpenMP-эксперта"

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

Таким образом, следует разработать Блок поиска DVM/OpenMP-вариантов. Блок поиска наилучшего DVM-варианта следует доработать до Блока поиска наилучшего DVM/OpenMP-варианта. Также подлежит изменению Блок записи результатов в Базу данных. Остальные компоненты останутся без изменений.

1.9.1 Варианты распараллеливания на OpenMP

Блок поиска DVM/OpenMP-вариантов получает на вход набор вариантов распараллеливания программы на кластере. Теперь нам требуется добавить еще один уровень параллелизма, и распределить работу, доставшуюся узлу кластера, между ядрами данного узла.

DVM-рекомендации позволяют распределить работу по выполнению циклов между узлами кластера. Сначала с помощью специальных DVM-директив между узлами кластера распределяются элементы массивов (блоками). Затем осуществляется распараллеливание циклов по принципу собственных вычислений. Если между витками цикла имеется зависимость по данным, цикл не распараллеливается. Исключение составляют редукционная зависимость и регулярная зависимость.