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

Рассмотрим несколько простых примеров.

Пример 1

Пусть DVM-эксперт распараллелил следующий цикл:

CDVM$ PARALLEL (i,j) ON a(i,j)

do i=1,N

do j=1,M