автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Некоторые вопросы технологии распараллеливания задач численного анализа и ее программной поддержки

Р Г Б ОЛ

О •"V " о ¡.и.! >■• -•

На правах рукописи

МАМЕДОВА Ирада Гариб кызы

НЕКОТОРЫЕ ВОПРОСЫ ТЕХНОЛОГИИ РАСПАРАЛЛЕЛИВАНИЯ ЗАДАЧ ЧИСЛЕННОГО АНАЛИЗА И ЕЁ ПРОГРАММНОЙ ПОДДЕРЖКИ

(специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, - комплексов, систем и сетей)

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 1996

Работа выполнена в Вычислительном центре Российской академии наук

Научный руководитель: доктор физико-математических наук

профессор ' В.А.Серебряков.

Официальные оппоненты: доктор физико-математических наук,

Защита состоится июня 1996 г. в _ эв на заседании

специализированного совета К 002.32.01 при Вычислительном центре Российской Академии наук.

Адрес совета: 117967, ГСП1, Москва, ул. Вавилова, дом 40. С диссертацией можно ознакомиться з библиотеке института.

Автореферат разослан мая 1996 г.

профессор Б.Н.Четверушкин.

кандидат физико-математических наук С.С.Гайсарян.

Ведущая организация: ИПМ РАН.

ъ

Ученый секретарь специализированного Совета доктор физико-математических наук

К.В.РУДАКОВ

Актуальность проблемы. В последние годы в связи с широким распространением и доступностью суперЭВМ с большим числом процессоров с распределенной памятью, стала острой проблема создания для них прикладного математического обеспечения. Определилось два основных направления в решении этой проблемы:

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

разработка автоматических систем распараллеливания численных алгоритмов.

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

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

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

В диссертации предложена эффективная

Коммуникационный пакет РагКР,

СИНАПС, может быть применен при релизации вычислительных алгоритмов на многопроцессорных машинах с распределенной памятью типа PARS УТЕС. Пакет может оказаться полезным при создании компилятора языка СИНАПС.

Публикации и апробации. По теме диссертации опубликовано б работ. Основные результаты докладывались на международных конференциях "Parallel computing technologies" (Обнинск, 1993; Москва, 1995) и "Software for multiprocessors and supercomputers: Theory, practice, experience" (Москва, 1994), международном симпозиуме "The 19th International Symposium, on Rarefied Gas Dynamics" (Оксфорд, 1994).

Структура и объем работы. Диссертация состоит из введения, пяти став, заключения, перечня литературы и приложения. Объем работы - 131 страница, перечень литературы включает 129 наименований.

Содержание работы.

Во введении дается обоснование актуальности темы и приводится общая структура работы.

Глава 1 содержит исторический обзор различных подходов к проектированию параллельных численных алгоритмов. В настоящее время выделяют три подхода в решении этой проблемы.

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

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

Второй подход состоит в построении специализированных вычислительных моделей (систолических массивов) для решения математических задач. Систолические алгоритмы разрабатываются для непосредственной физической реализации (тоща как МШО-алгоритмы, например, выполняются на многопроцессорных системах общего назначения).

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

последовательных машин дорогостоящего программного обеспечения.

Автоматические системы адаптации последовательного программного обеспечения под архитектуру конкретной параллельной ЭВМ пользуются только исходным текстом профаммы, проводят его анализ с целью нахождения потенциального параллелизма и прогнозирования поведения программы на этапе выполнения и, на основе этого знания, делают вывод о возможности его параллельной реализации. Проводимый при этом анализ называют статическим анализом, т. к. никакой информации со стадии исполнения программы не используется. На этапе статического анализа решается задача определения информационной зависимости между двумя вхождениями одной и той же переменной; при этом существует множество различных методов. Заметим, что по полученным в Иллинойском Университете данным, лишь для 15% всех пар вхождений нет трудностей с обнаружением характеристик зависимости. Хорошо известно, что автоматическое распараллеливание не всегаа ведет к наиболее эффективным параллельным программам. Кроме того, некоторые параллельные профаммы не имеют их последовательных аналогов (например, профаммы, которые реализуют асинхронные алгоритмы). Другая возникающая здесь проблема-автоматизация распределения данных на множество процессоров с определенной топологией связи между ними. Эта проблеиа далеко не вполне разработана.

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

В птаве 2 дается краткое изложение основ теории зависимости по данным и языка параллельного программирования СИНАПС.

В главе 3 рассматриваются основные функции коммуникационного пакета РаЛБР, предназначенного для адаптации параллельных программ, написанных на паралле ьном язйке программирования СИНАПС (наследующем семантику языка С) к многопроцессорным системам с распределенной памятью. Приводятся различные локальные преобразования циклов в программе, осуществляемые с целью придания про1рамме формы, необходимой для выполнения ее на многопроцессорном компьютере с системой внешних каналов связи.

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

инициализировать систему процессоров; произвес-ч разбиение данных; у

/

отобразить виртуальную сеть процессоров на реально существующую;

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

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

осуществить передачу и прием данных и сообщений процессорами и обеспечить корректность этих обменов. Для поддержки выполнения всех этих задач разработан коммуникационный пакет РагКР. Пользуясь функциями такого пакета, пользователь мог бы заменить конструкции языка СИНАПС привычными для него по опьгг> использования последовательных языков программирования обращениями к функциям этого пакета, дополнительно снабдив программу указаниями о желаемом разбиении данных с помощью конструкций описания распределений языка СИНАПС. Таким образом, процесс создания параллельного алгоритма для М1МО-архитектуры можно представить как проходящий в рамках "полуручной"-полуавтоматизированной системы. Основные этапы этого процесса можно изобразить в виде следующей блок-схемы:

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

Пакет разрабатывался для многопроцессорной машины с распределенной памятью типа PARSYTEC.

Основные группы функций, составляющие коммуникационный пакет ParISP, следующие:

группа функции define_dislribution\ труппа функций process_mapping; ipynna функций process „.communication", группа функции broadcast.

Далее дается краткое изложение назначения кажпой из этих групп.

1. Группа definejiistribution предназначена для реализации различных видов разбиений, задаваемых пользователем с помощью конструкций языка СИНАПС. Вычислительная область задачи (массивы в программе) делится на непересекающиеся сегменты так, что каждый сегмент посуществу определяет локальное адресное пространство процесса, назначаемого отдельному процессору. Выбранное разбиение совместно с информацией о зависимостях по данным предопределяют структуру процессов конечной параллельной реализации. Эту структуру можно представить как виртуальную сеть процессоров.

Функции этой группы определяют размер блока данных, назначаемых каждому процессору, а также минимальное min и максимальное max значения индексов индексированной переменной для каждого виртуального процессора так, что все элементы распределяемой структуры дагных со значениями индексов, попадающими в интервал [min,max] и инкрементируемыми с шагом Д, гае А-расстоянне зависимости для измерения, по которому производится желаемое пользователем разбиение или число процессоров, обрабатываются на этом процессоре.

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

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

3. Группа process^communication поддерживает механизм межпроцессорных коммуникаций. Так как область данных цикла (массив) разбивается таким образом, что различные сегменты назначаются разным процессорам, и каждый процесс имеет.

о

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

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

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

4. Группа broadcast. Функции этой группы предназначены для реализации оператора reduce языка СИНАПС, который позволяет записать проверку условия сходимости задачи в параллельной программе. Эти функции дают возможность также осуществлять контроль правильности - юхождения программы на параллельной машине и получить информацию о "семени ее выполнения. Подпрограммы построены на едином алгоритме с незначительными отличиями. Каждое из этих средств подразумевает соединение

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

В главе 3 также приводится описание некоторых трансформаций циклов, относительно которых есть указание на параллельное выполнение вычислений в них посредством конструкции par и параллельной формы оператора for языка СИНАПС, в такую форму записи которая позволяет локализовать на конкретном процессоре часть вычислений цикла, назначаемую на этот процессор. Преобразование исходного цикла в соответствующую форму записи для описания схемы работы этого цикла на многопроцессорной системе определяется на основе информации о зависимостях по данным и областях обмениваемых данных, а также указываемом пользователем разбиении данных.

Такие преобразования могли бы быть применены при разработке компилятора языка параллельного программирования СИНАПС для многопроцессорных систем с локальной памятью. "Ручной" эксперимент подтверждает целесообразность использования таких преобразований в подобного рода компиляторах.

В главе 4 показывается, как осуществляется распараллеливание некоторых краевых задач для систем типа Стокса с мг ым параметром, решаемых на основе многосеточного метода, и алгорит? ов решения основного уравнения кинетической теории

газов, построенных на прямом методе, на многопроцессорную систему с распределенной памятью типа PARSYTEC.

В главе 5 приводятся полученные результаты. Основными мерами параллелизма, по которым производилась оценка качества параллельных алгоритмов, были ускорение s, эффективность е, а также доля последовательной части программы g. Доля последовательной части программы gzconst, что свидетельствует о равномерном распределении работ по процессорам. Значения эффективности е параллельных алгоритмов равны »1. Так, для более полной оценки эффективности параллельной реализации многосеточного метода в диссертации обращается внимание на следующий факт. Для последовательных программ с матрицей 2 >6 х 256 время выполнения одного V-цикла с шестью сеточными уровнями, оказывается равным 34.5s, тогда как параллельная программа на сетке 2048 х 2048 выполняется за время 35.Hs. Поскольку объем вычислений в последнем случае в 64 раза превосходит обоем вычислений в последовательном варианте, то степень параллелизации данного метода, очевидно, равна

Ш-»

Заключение.

В диссертации получены следующие основные результаты:

1. Предложена методика распараллеливания вычислительных алгоритмов из различных областей науки и техники. В качестие исходного материала ложет служить как программа, написаг ная

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

2. Создан коммуникационный пакет ParISP для поддержки распараллеливания программ, написанных на языке параллельного программирования СИНАПС, на многопроцессорные системы с распределенной памятью.

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

4. Выявлены некоторые дополнительные требования к языкам параллельного программирования, ориентированным на MIMD-архнтектуру.

5. Определены некоторые преобразования, применяемые к циклам с целью адаптации программы к многопроцессорным машинам с системой внешних каналов связи. Такие преобразования целесообразно применить при разработке компилятора с языка СИНАПС.

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

Основные публикации по теме диссертации:

1. Mamedova I.G., Aristov V.V. Parallel implementation of numerical algorithms for solving the Boltzmann equation.//Parallel computing technoIogies./Ed. V.E.Malyshkin. Proc. of Int. Conf., Obninsk. Russia, Aug.30-Sept.4, 1993, pp. 103-108.

2. Mamedova I.G., Aristov V.V. Investigation of parallel algorithms for solving the Boltzmann equation and their efficiency. Proc. of the 2nd Int. Conf. on Software for multiprocessors and supercomputers: Theory, practice, experience. Moscow, Sept.19-23, 1994, pp.417-425.

3. Mamedova I.G., Aristov V.V, Parallel algorithms based on the direct approaches of solving the Boltzmann equation. The 19th Int. Symp. on.Rarefied Gas Dynamics, Oxford, 1994, July 25-29.

4. Мамедова И.Г., Аристов B.B. Параллельные алгоритмы для уравнения Больцмана. 1996. ЖВМиМФ. Т.Зб, N.2, стр.139-148.

5. I.G. Mamedova. Implementation of the Multigrid Method for Solving the Boundary-value Problems for the Poisson and Helmholt?, Equations on the Massively Parallel Computers. 1995. Lecture Notes iri Computer Science, 964:427-433.

6. И.Г. Мамедова, B.A. Серебряков. Распараллеливание алгоритмов решения краевых задач для уравнений Пуассона и Гельмголь-ца многосеточным методом. 1995. Программирование. N.5, стр.3-23.

Подписано в печать t4.0S.96 Формат 60/84/16 Объем: 1,5 пл. Тираж З^экз. Цена договорная Заказ N2 1С