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

ЗАРУЧЕВСКАЯ ГАЛИНА ВАСИЛЬЕВНА

ПРИМЕНЕНИЕ МЕЛКОЗЕРНИСТОГО ЛОКАЛЬНОПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ ПРИ РЕШЕНИИ ЗАДАЧ

МАТЕМАТИЧЕСКОЙ ФИЗИКИ МЕТОДОМ СЕТОК

05.13.18 – математическое моделирование,

численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Петрозаводск 2008

Работа выполнена в Поморском государственном университете Научный руководи- доктор технических наук, профессор тель Воробьев Владимир Анатольевич Официальные оппо- доктор физико-математических наук, ненты: доцент Попов В.Н.

кандидат технических наук, доцент Борматова Е.П.

Ведущая организация Институт прикладных математических исследований КарНЦ РАН

Защита состоится « 12 » декабря 2008 г. в 10 часов на заседании Диссертационного Совета Д 212.190.03 при Петрозаводском государственном университете по адресу: 185910, Петрозаводск, пр. Ленина, д. 33.

С диссертацией можно ознакомиться в библиотеке Петрозаводского государственного университета.

Автореферат разослан « 5 » ноября 2008 г.

Ученый секретарь диссертационного совета _ Поляков В.В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

В работах В.А. Воробьева рассмотрены три обязательных условия, при которых не происходит снижения производительности МЛПП:

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

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

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

В работах Молчанова И.Н., Галба Е.Ф., Воеводина В.В., Родрига Г., Ильина В. П., Марчук Г.И., Фета Я. И., Ортега Дж. и др. рассматриваются исключительно крупноблочные алгоритмы решения задач математической физики, предназначенные для вычислительной техники со стандартной системой коммутаций типа линейка, решетка, кольцо, кольцо с хордами, гиперкубовая архитектура, универсальная связь и т.п. В более поздних работах (Гергель В.П., Воеводин В.В., Корнеев В.В.) рассматривается структура под названием «решетка-тор». Эта структура появляется в технологии параллельного программирования MPI. Так, Корнеев В.В. приводит пример перемножения двух матриц больших размерностей в торе. В этом алгоритме элементы матрицы циклически распределены в узлах тора, число обменов минимизировано, обмен данными производится блоками. Такая реализация параллельного перемножения матриц относится к блочному типу. Если авторы упоминали об использовании решетки-тора для решения сеточных задач математической физики (Гергель В.П.), то на самом деле в алгоритме оказывались задействованы только узлы и связи решетки, а связи противоположных сторон не использовались. В своей работе В.П.Ильин упоминает о «мелкозернистом распараллеливании» для решетки с числом процессоров, равным числу узлов сеточной области, но связи рассмотренного им алгоритма не являются локальными. Заметим, что ни один из авторов МЛП-алгоритмы не рассматривает, ориентируясь на возможности реально существующей вычислительной техники. Таким образом, разработка и исследование МЛП–алгоритмов для задач математической физики – одно из перспективных направлений современного параллельного программирования. Актуальность выполненной работы состоит в создании и анализе ряда МЛП– алгоритмов для задач математической физики. В работе Бадман О.Л. для этих целей применяются модели клеточных автоматов.

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

Для достижения поставленной цели поставлены и решены следующие задачи:

• Задать особенности параллельной архитектуры MIMD (МКМД) машины, для которой будет эффективен МЛП–стиль программирования.

• Определить основные положения стиля МЛП–программирования.

• Рассмотреть специальные структуры межпроцессорных связей, используемые для разработки эффективных МЛП–алгоритмов.

• Предложить варианты исполнения МЛП–алгоритмов некоторых сеточных задач математической физики в КАИС–структурах с иллюстрацией размещения в ней обрабатываемых данных.

• Разработать программу, в которой показаны результаты вычислений некоторых алгоритмов задач математической физики и оценки эффективности мелкозернистых локально-параллельных алгоритмов.

На защиту выносятся 1. Разработанная трехмерная структура межпроцессорных связей– тороидальный куб (конструкция вложенных торов).

2. Разработанные специфические мелкозернистые локально– параллельные алгоритмы для задач математической физики.

3. Программа для решения задач математической физики в методе сеток с вычислением оценок параллелизма для МЛП –алгоритмов.

Методы исследования. Для разработки новых МЛП–алгоритмов использовались основные положения теории однородных вычислительных структур, теории разностных схем, теории алгоритмов.

Практическая ценность работы. Практическая ценность проведенного исследования заключается в том, что полученные в ней результаты могут быть использованы для повышения эффективности численных процедур решения задач математической физики, которые применимы к изучению многих физических процессов и явлений. Специальные вычислительные системы, предназначенных для решения этого круга задач, отличающихся большой размерностью, применяются во многих отраслях промышленности, народного хозяйства и военно-технического комплекса. В частности, к таким параллельным вычислительным архитектурам относятся двумерные и трехмерные тороидальные структуры ОВС. Перспективность применения этих систем для разработки МЛП–алгоритмов решения задач математической физики в методе сеток доказана в настоящем диссертационном исследовании. В настоящее время результаты диссертационного исследования включены в дисциплину «Архитектура компьютера», которая читается студентам 5 курса специальности 050201. «Математика» с дополнительной специальностью «Информатика» (квалификация учитель математики) математического факультета ГОУ ВПО «Поморский государственный университет имени М.В. Ломоносова». Применение подтверждают приложенные лекционные слайды и акт о внедрении в образовательный процесс.

Научная новизна работы. Разработана новая трехмерная структура межпроцессорных связей– тороидальный куб для решения трехмерных задач математической физики методом сеток.

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

Разработана программа «Решение задач математической физики в методе сеток с вычислением оценок параллелизма для МЛП – алгоритмов».

Апробация работы. Основные результаты диссертации докладывались и обсуждались на: Втором Международном научно–практическом семинаре и Всероссийской молодежной школе «Высокопроизводительные параллельные вычисления на кластерных системах». (Нижний Новгород, 2002); Четвертом Международном научно-практическом семинаре и Всероссийской молодежной школе «Высокопроизводительные параллельные вычисления на кластерных системах». (Самара, 2004); IIXX Ломоносовских чтениях, (Архангельск, 2006);

Шестом Международном научно–практическом Семинаре и Молодежной Школе «Высокопроизводительные параллельные вычисления на кластерных системах». (Санкт–Петербург, 2006); IXX Ломоносовских чтениях, (Архангельск, 2007); Седьмом Международный научно–практический Семинар и Молодежная Школа «Высокопроизводительные параллельные вычисления на кластерных системах». (Нижний Новгород, 2007).

Публикации. Основные результаты опубликованы в 10 работах, в том числе в 3-х статьях в журналах, входящих в список изданий, рекомендованных ВАК. Список основных работ приведен в конце автореферата.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Объем диссертации составляет 198 машинописных страниц, текст содержит 41 рисунок. Список литературы включает 60 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы диссертации, формулируются цели работы, а также приводится краткое содержание глав диссертации.

В первой главе приведена классификация ЭВМ, предложенная Флинном.

Представлено описание типов межпроцессорных связей, используемых у других авторов (Молчанова И.Н., Галба Е.Ф., Воеводина В.В., Ильина В. П., Ортега Дж. и др.). Приведены коэффициенты, характеризующие эффективность параллельных алгоритмов. Рассмотрены некоторые идеи концепции ОВС и описана архитектура ОВС, предназначенная для выполнения алгоритмов в этом стиле программирования. Дано описание одного из видов программирования – мелкозернистого локально–параллельного программирования.

Впервые сформулированы требования к архитектуре MIMD–машины (МКМД- много потоков команд, много потоков данных; к этому типу относятся многопроцессорные ЭВМ с распределенной памятью), при которых стиль МЛП – программирования был наиболее эффективен:

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

2. Все возможные в данный момент обмены машинными словами совершаются параллельно и одновременно с процессом счёта за время, сравнимое со временем выполнения одной арифметической операции (из-за близости связанных процессоров в физическом пространстве).

3. Имеется возможность программировать структуру межпроцессорных связей.

В п.1.3.5 перечислены преимущества использования тороидальной структуры для МЛП-алгоритмов:

1. Эта структура позволяет «масштабировать» сетку любой размерности, но не по подобластям, а по соответствующим кратным узлам (процессор с координатой (k, p) обрабатывает вычисления в узлах сетки с номерами (k+aN, p+bM), где (N, M)-размерность тора, a,bZ). Такое распределение данных называется циклическим и сохраняет вычисления локальными и мелкозернистыми, так как данные, необходимые для расчета в каждом витке цикла, располагаются в ближайших связанных процессорах.

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

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

3. Разработанные МЛП-алгоритмы используют внутренний параллелизм сеточных методов, их вычислительная сложность равна вычислительной сложности соответствующего быстрейшего алгоритма для однопроцессорных машин, поэтому их эффективность при tсдв=0 равна 1. Так, МЛП–алгоритмы в тороидальных структурах для разностных схем эллиптических уравнений не требуют использования так называемых «дополнительных сеточных прямых». Для разностных схем, решаемых с помощью метода прогонки, не нужно прибегать к «распараллеливанию» этого метода согласно алгоритмам ЯненкоКоновалова и их модификациям, что существенно снижает вычислительную сложность алгоритмов.

Для мелкозернистого распараллеливания трехмерных задач введена новая структура процессорный тороидально связанный куб CDE. Эту структуру можно рассматривать как продолжение процессорного куба размерностью CDE. Каждый процессор обозначается Pi,j,k, где i, j, k – координаты узла, в котором располагается процессор. Дополним процессорный куб следующими связями: каждый процессор P1,j,k соединим регулярным каналом с процессором PС,j,k, j=1..D, k=1..E; Pi,1,k соединим регулярным каналом с процессором Pi,D,k, i=1..C, k=1..E; Pi,j,1 соединим регулярным каналом с процессором Pi,j,E, i=1..C, j=1..D. Получим новую структуру – тороидально связанный куб CDE, изображенный на рис. 1. Заметим, что каждая плоскость, параллельная плоскостям COD, COE и DOE и содержащая процессорные узлы, представляет собой тороидальную структуру.

Опишем еще одну структуру, в которой так же могут рассматриваться трехмерные алгоритмы. Расположим EC процессоров в E колец с одним общим центром (рис.2) и определим для них следующую нумерацию: верхний индекс означает номер кольца, а нижний - номер процессора в кольце. Межпроцессорные связи показаны штрихпунктирной линией. Пусть имеется D вложенных кольцевых структур, описанных выше. Расположим и занумеруем эти кольцевые структуры так, как показано на рис. 3. Обозначение (Pkj)m означает, что процессор принадлежит m-ой кольцевой структуре на кольце с номером j и занимает на нем k-тую позицию. Будем полагать, что процессоры с одинаковыми первыми нижними индексами k и верхними индексами j соединены общим регулярным каналом. Очевидно, что структура состоит из числа E вложенных друг в друга торов, соединенных специальным образом, причем она изоморфна тороидально связанному кубу CDE, описанному выше. Поэтому алгоритмы, разработанные для одной из этих структур, будут иметь эквивалентную интерпретацию для другой, и наоборот. Очевидно, что обе структуры вложимы в физическое пространство, однако не являются планарными. Гипотетически можно предположить, что конструкция вложенных торов позволит обеспечить теплоотвод: их внутренняя полость может быть использована как расширитель для испарения хладоагента. Заметим, что конструкция вложенных торов содержит на порядок меньше удаленных связей, чем тороидально связанный куб, а значит, обеспечивает большую эффективность мелкозернистому локальнопараллельному стилю программирования.

Таким образом, впервые обоснована возможность использования тороидальных структур для МЛП – вычислений, в том числе в сеточных методах решения задач математической физики.

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

При описании алгоритмов параллельных вычислений на ЭВМ класса MIMD авторы полагали, что MIMD – машина состоит из p одинаковых процессоров, каждый из которых обладает определенным объемом своей локальной памяти (одинаковым для всех параллельных процессоров) и способен осуществлять численную обработку информации в автономном и управляемом режимах.

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