Конференции ИВТ СО РАН

Третья российско-германская школа по параллельным вычислениям на высокопроизводительных вычислительных системах

28 августа - 8 сентября 2006 года, Новосибирск, Академгородок

Тезисы докладов

31-ое августа

Разработка формализованных методов распараллеливания алгоритмов, заданных аффинными гнездами циклов

Адуцкевич Е.В.

Институт математики НАН Беларуси (Минск)

Задаче распараллеливания последовательных алгоритмов посвящено много исследований. Можно выделить два подхода к решению этой задачи. Первый подход заключается в реализации естественного параллелизма задачи. Существует довольно много практических задач, обладающих естественным параллелизмом, и разработка способов наиболее эффективной реализации такого параллелизма является практически важной. Но кроме этого существуют важные задачи со сложными информационными связями, которые не обладают естественным параллелизмом. Для того, чтобы найти варианты параллельной реализации таких задач, необходимо применение специального математического аппарата (второй подход). Строгое математическое обоснование позволяет пользователю такого аппарата быть уверенным в качестве результатов его применения.

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

-- распределение операций и данных алгоритма между процессорами,

-- установление порядка выполнения операций и обмена данными,

-- улучшение локальности данных в процессорах вычислительной системы,

-- оптимизация необходимых в процессе выполнения программы коммуникаций.

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

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

Оптимизация коммуникаций крайне необходима для реализации алгоритмов на параллельном компьютере с распределенной памятью. Известно, что при выполнении алгоритмов на таких компьютерах реализация коммуникаций между процессорами имеет, как правило, большие накладные расходы. Поэтому коммуникации следует организовывать таким образом, чтобы эти расходы максимально снизить. Для этого решают две задачи: уменьшение количества коммуникаций и объема передаваемых данных, а также оптимизацию структуры коммуникаций (поиск вариантов наиболее эффективного обмена данными).

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

Отметим, что указанные формализованные методы разрабатываются с целью автоматизации процесса распараллеливания последовательных программ. Предполагается создание пакета программ, работа над которым в настоящее время ведется в Институте математики НАН Беларуси.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]