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

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

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

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

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

Теперь рассмотрим, как следует изменить структуру DVM-эксперта, чтобы получить 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-варианта. Также подлежит изменению Блок записи результатов в Базу данных. Остальные компоненты останутся без изменений.

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

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

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

Пример 1

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

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

do i=1,N

do j=1,M

A(I, J) = B(J, I)

enddo

enddo

Директива CDVM$ PARALLEL (i,j) ON a(i,j) говорит о том, что виток цикла со значением итераторов (i, j) будет выполняться на то узле, на котором распределен элемента массива a(i, j). Существует два способа распараллелить на OpenMP этот многомерный цикл: распараллелить внутренний или внешний цикл.

Вариант 1.1

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

!$OMP PARALLEL PRIVATE(i, j)

!$OMP DO SCHEDULE (STATIC)

do i=1,N

do j=1,M

A(I, J) = B(J, I)

enddo

enddo

!$OMP END DO

!$OMP END PARALLEL

Директива !$OMP PARALLEL говорит о том, что на каждом узле начинается параллельная область. То есть на узле создаются нити, между которыми будет распределяться работа. Все порождённые нити исполняют один и тот же код, соответствующий параллельной области. Предполагается, что в SMP-системе нити будут распределены по различным ядрам процессора. Клауза PRIVATE(i, j) означает, что для каждой нити выделяется локальная память под две переменные: i и j. Действительно, у каждой нити должен быть свой итератор цикла. По достижении директивы !$OMP END PARALLEL нити останавливают свою работу, и на узле остается работать только одна мастер-нить.

Директива !$OMP DO сообщает нам, что далее в программе следует цикл, витки которого будут распределяться между нитями. Клауза SCHEDULE (STATIC) гласит, что все множество итераций внешнего цикла делится на непрерывные куски примерно одинакового размера, и полученные порции итераций распределяются между нитями.

Директива !$OMP END DO сообщает об окончании параллельного цикла. Происходит неявная барьерная синхронизация нитей и неявный вызов !$OMP FLUSH. Выполнение FLUSH предполагает, что значения всех переменных (или переменных из списка, если он задан), временно хранящиеся в регистрах и кэш-памяти текущей нити, будут занесены в основную память; все изменения переменных, сделанные нитью во время работы, станут видимы остальным нитям. [9]

Вариант 1.2

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

do i=1,N

!$OMP PARALLEL PRIVATE(i, j)

!$OMP DO SCHEDULE (STATIC)

do j=1,M

A(I, J) = B(J, I)

enddo

!$OMP END DO

!$OMP END PARALLEL

enddo

Отличие этого варианта от предыдущего заключается в том, на каждой итерации внешнего цикла будет создаваться новая параллельная область, то есть будут создаваться нити, и выделяться локальная память для них. Затем нити будут синхронизоваться, выполнять FLUSH и останавливаться. Всё это накладные расходы, которые будут возникать N раз. Еще одно отличие заключается в том, что в этом варианте между нитями распределяются витки внутреннего цикла, а не внешнего.

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

Пример 2

Пусть DVM-эксперт распараллелил то же самый цикл следующим образом:

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

do i=1,N

do j=1,M

A(I, J) = B(J, I)

enddo

enddo

Отличие этого примера от предыдущего заключается в распределении данных. Здесь, между узлами одномерной процессорной решетки распределено только второе измерение массива A. Соответственно, между узлами будут распределяться только итерации внутреннего цикла. Таким образом, если количество витков внешнего цикла меньше суммарного количества ядер нашего SMP-кластера, но больше количества ядер на одном узле, то распараллеливание на OpenMP внешнего цикла позволит загрузить все ядра (заметим, что в варианте 1.1 на каждом узле работало бы не более одного ядра).

Для этого примера также существует два варианта распараллеливания, аналогичных вариантам 1.1 и 1.2.

Пример 3

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

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

*DVM$* REDUCTION (SUM(s))

do i=1,N

do j=1,M

S = S + A(I, J)

enddo

enddo

Клауза REDUCTION (SUM(s)) означает, что каждый узел создаст в своей локальной памяти редукционную переменную, и будет накапливать в ней суммы элементов массива. По окончанию цикла эти локальные переменные будут просуммированы и записаны в s. В таком случае мы по-прежнему имеем два варианта распараллеливания:

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