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

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

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

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

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

003453045

Работа выполнена в Поморском государственном университете

Научный руководитель

Официальные оппоненты:

Ведущая организация

доктор технических наук, профессор Воробьев Владимир Анатольевич доктор физико-математических наук, доцент Попов В.Н. кандидат технических наук, доцент Борматова Е.П.

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

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

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

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

Ученый секретарь

диссертационного совета____Поляков В.В.

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

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

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

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

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

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

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

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

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

спективных направлений современного параллельного программирования. Актуальность выполненной работы состоит в создании и анализе ряда МЛП-алгоритмов для задач математической физики. В работе Бадман О.Л. для этих целей применяются модели клеточных автоматов.

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

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

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

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

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

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

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

На защиту выносятся

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Эта структура позволяет «масштабировать», сетку любой размерности, но не по подобластям, а по соответствующим кратным узлам (процессор с координатой (к, р) обрабатывает вычисления в узлах сетки с номерами (к+а!^, р+ЬМ), где (И, М)-размерность тора, a,ЬeZ). Такое распределение данных называется циклическим и сохраняет вычисления локальными и мелкозернистыми, так как данные, необходимые для расчета в каждом витке цикла, располагаются в ближайших связанных процессорах.

2. Известно, что тороидальная структура изоморфна решетке (сетке) про-

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

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

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

Для мелкозернистого распараллеливания трехмерных задач введена новая структура - процессорный тороидально связанный куб СхБхЕ. Эту структуру можно рассматривать как продолжение процессорного куба размерностью СхБхЕ. Каждый процессор обозначается где к _)', к - координаты узла, в

котором располагается процессор. Дополним процессорный куб следующими

...................-.....

I |

• 1 1?-»"■Ч'? »1 ^ I "П*» ! *

г I

С *

Рис. 1

Рс

/Хх'р^:. \ / р .>' \

\ ? / ( хГ^Х ^ (Р1>

ч»< ,4-——V

(РЛ (РГ)2 Рис.3

Рис. 2 9

связями: каждый процессор Р^ соединим регулярным каналом с процессором Pcj>, j=l- D, k=l..E; Pirlik соединим регулярным каналом с процессором Рцдь i=l..C, k=l..E; Руд соединим регулярным каналом с процессором Ру_Е , i=l..C, j=l..D. Получим новую структуру - тороидально связанный куб CxDxE, изображенный на рис. 1. Заметим, что каждая плоскость, параллельная плоскостям COD, СОЕ и DOE и содержащая процессорные узлы, представляет собой тороидальную структуру.

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

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

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

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

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

П = ОиГ={(х, у): 0<х<^ь 0<у</?2}.

1и = *п> (!) и-§(х,у), (х,у)еГ, 0<с1<ка<с2, а=1,2.

В области П введем равномерную но обеим переменным сетку га. Тогда задаче (1) на сетке та=соиу поставим в соответствие разностную задачу:

Ло = -((Я! (х, уУо- )х +(а2 (х, у)у- )у /(х, у), (х, у) е ю, (2)

и = у), (х, у) е у, а,(х, у)=к,(х-0,5Ьь у); а2(х, у)=к2(х, у-0,5Ь2).

Для решения задачи (2) явным чебышевским методом задают на ю начальное приближение 1>(0) и величину г, определяющую окончание итерационного процесса. Каждое последующее приближение вычисляется по формуле

рО*!)^) ^(г.л </«)•); ^ =§> (3)

где {тк}- оптимальный чебышевский набор параметров.

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

?ж:.2.3

ции в каждой а>: было примерно одинаковым. Расширим все подобласти , кроме а>1 и <а?, в обе стороны вдоль оси Ох на шаг сетки, а сеточные подобласти и шЦ, расширим на шаг сетки вправо и влево соответственно и обозначим их через га8. Множество внутренних узлов ш*обозначим со8. 1) Задаем начальное приближение и(0) в каждой подобласти Вводим в каждый ПП величину е. Вычисляем и храним во всех ПП {тк}- 2) В каждом ПП в узлах сетки ю! одновременно и независимо находим (к+1)-е приближение к решению по формуле (3). 3) Последовательно устанавливается два раза связь между ПП таким образом, чтобы в результате этого ПП, содержащие соседние подобласти, соединялись каждый раз попарно между собой. После каждого такта установления связи между ПП они обмениваются значениями 1>(|С+1), находящимися в приграничных узлах, прилегающих к дополнительным сеточным прямым. После этого переходим на шаг 2).

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

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

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

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

и1 = а^ию' +а! им' + и«/, (4)

где функции ию1 , и0|' ,Поо' полностью определены (через уравнения и граничные условия) и играют роль некоторого базиса, а значения искомой функции на границе О; - аЬ] и а; пока не известны. В результате такого разделения функции базиса могут быть определены независимо с помощью алгоритма скалярной («однопроцессорной») прогонки, то есть решаются три (или две) задачи для нахождения неизвестных ию', 1Д011, иоо' ■

Значения базисных функций в приграничных точках позволяют сформулировать задачу (путем вычисления коэффициентов новой системы уравнений также с трехдиагональной матрицей) для нахождения неизвестных а;, ([-0, ... , р-1).

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

В п.2.2.4 описываются параллельные алгоритмы решения двумерных и

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

Анализ на соответствие стилю МЛП11 показал, что все алгоритмы являются крупноблочными. Если в алгоритме при определенном распределении данных в структуре присутствует локальная связь по данным, то для него в главе 3 рассматривается МЛП- реализация.

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

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

е2{с,о}.

Распределим ячейки области © таким образом, чтобы каждому процессору тора Е2{С,0} с координатами (х,у) поставить в соответствие ячейки сетки (х+Ск,у+Бп), к,пеЗЧ, т.е. область га разбивается на (Р^1/С]+1)-([Н2/В]+1) подобластей (£>к* размерностью СхВ, где к=1,...,(|>(|/С]+1), п=1, ..., ([Ы2/В]т1), прямыми, параллельными обеим координатным осям.

Шаг 1. Задаем начальное приближение V(0). Вводим в каждый процессор счетчик итераций 1,1=0 в начале выполнения программы. Вычисляем и храним во всех процессорах параметры {тк}.

Шаг 2. Рассмотрим вычисление приближения г/1' в подобласти ш1,1. Чередуя сдвиги значений v ¡, j по регулярному каналу вправо, влево, вниз и вверх, процессоры получают необходимые для расчета значения. Граничные процессоры P(Cj) принимают данные процессоров P(lj), -они содержат значения vkC+1 аналогично процессоры P(i,D) принимают данные процессо-

ров P(i,l). Неиспользуемые данные будут теряться либо не учитываться.

Шаг 3. Каждый процессор вычисляет значение v)j в подобласти со1,1. Вычисление значения v}j в остальных подобластях œk'n, где k=l,... ([Ni/C]+1), п=1,

—. ([N2/D]+l), осуществляется аналогично (см. п. 2 и п.З.).

Шаг 4. ВМ увеличивает значение счетчика t на 1. Если t=N+l, ВМ посылает флажок Oij=l на магистральный канал.

Шаг 5. Как только все ВМ отправят на магистральный канал флажки, вычислительный процесс прерывается во всех ВМ и хост — машина через магистральный канал выводит вычисленные значения. Операция прерывания является единственной глобальной операцией.

Т

При ^дащлО коэффициент ускорения ky=—«CD и коэффициент эффектив-

Тр

ности кэ »1, т.е. параллелизм максимален.

Мелкозернистое распараллеливание задачи Дирихле для самосопряженного уравнения третьего порядка в тороидальном кубе (кэ »1) и точечного метода верхней релаксации при естественном упорядочении неизвестных основано (кэ»1/С) на том же подходе, что и распараллеливание явного чебышсвского метода.

Рассмотрим параллельный алгоритм решения разностной схемы для задачи Коши для двумерного уравнения теплопроводности на примере следующей разностной схемы:

Tí —w 1

=I {A"K" + }+f(x' y>tx

«L =¥(ж«»Уя)-

'тп

1

Преобразуем схему (5):

h2

х

(6)

С',, -2(1 + — +"

'Г

+ 2(1-— К,„ -итл_, т

Этап 1. Хост-машина рассчитывает х/Ъ2, 2(1+х/Ь2) и 2(1-т/Ь2), рассылает эти значения в каждый процессор тороидальной структуры; исходные данные и%п

числяет Хк и рассылает в процессоры (шо(1(к,С), тос1(п,0)) и (тос1(т,С), тос!(к,В)); т, п, к=1..(Ы-1).

Этап 2. В каждом горизонтальном кольце системы сначала сдвигом вправо, а затем влево передаются значения и^ соседним процессорам. Далее каждый процессор с рассчитывает правую часть первого уравнения (6)

~"ти.,.+ 2(1 ~~"")ит,„~~ ==С в подобласти со1,1. Аналогично вычисляются значения в остальных площадках шк'п.

Этап 3. В каждом вертикальном кольце процессоров, составляющем тор, рассчитываются и„ш, ш=1..С. Согласно методу прогонки в процессорах рассчитываются: р! в процессорах (тос1(т,С),1); в процессорах (тоё(т,С), тос!(К-1,В)). Значение р 1 передается параллельным сдвигом вверх в каждой кольцевой структуре для расчета р2 по формуле ркК^ы-РпоО^ь к=2..1Ч-2 в процессорах (тос1(к,С), шой(т,В)). Подобно расчету находятся остальные ръ к=2..ТЧ-2. Затем вычисляется +Кк_г р м-гУ (1 - X ьч • ^N-2) в процессорах (то<1(ш,С), то<1(Ы-1,0)) и сдвигом вниз пересылаются соседним про-

и h2-f£in рассылаются в процессоры (mod(m,C), mod(n,D)). Так же машина вы-

цессорам для расчета итм_2 по формуле и1Ш1=Хп- итп+1 + р„. Аналогично расчету и^находятся остальные и,,,,, п=(1Ч-2)..2. Подобным образом находится сле-

дующая партия итп, т=(С+1)..(2С); затем при т=(2С + 1)..(ЗС) и т.д., пока не бу-

ГМ-Г

дет рассчитана последняя партия при т=

.. (М-1)

С

Этап можно модернизировать, вычисляя прогоночные коэффициенты а затем и значения иш (11^,) «волной», т.е. каждая Ьая вертикальная кольцевая структура на третьем этапе одновременно вычисляет значения ц, „, й1+с „, и1+2с_„,

в-»,. ИТ-Д-

Этап 4. Каждый процессор в подобласти со1'1 сначала сдвигом вверх, а затем вниз передаются значения итд1 соседним процессорам и выполняет расчета правой части второго уравнения (6). Аналогично вычисляются значения в

остальных площадках сок,п.

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

Вычислительный процесс заканчивается, когда выполнен расчет последнего слоя ит. Цикл повторяется Т раз.

«Модернизированный» алгоритм на всех этапах (не связанных с глобальными операциями) отвечает требованиям локальности и мелкозернистости. При ^двж^О «модернизированный» вариант достигает максимального параллелизма, т. е.

В случае задачи Коши для трехмерного уравнения теплопроводности

т 8и д2и д2и д2и г. Л * гп

в _ _ = /(*,у,2,0,0< 1:<Т,-со<х, у,г<<х>

д1 ох2 о у2 дх2

и(х,у,7,0) = ^(х,у,г), Разностная схема для этой задачи имеет вид:

11 тпк "итпк

X

ъ'тпк ~утпк

тпк X ~'°тпк

X

~ £тпк

Л 2

/г 2

тяАч-1 . ^р •'тпк

Преобразуем каждое уравнение разностной схемы: ът+\лк ~ ('2 + й2 / т^д. + утАлк = -("Л2 /х)»^ =

~ С2 + А2 + гуи+и = -С^2 АЖед* = ^я

У тпк ~ 8тпк

Из последнего уравнения известны краевые условия 0, vvKa,v"w' у=0..М.

Разностная схема неявная, безусловно устойчивая и решается методом прогонки. Составим МЛН - алгоритм поиска решения задачи в тороидальном процессорном кубе.

Этап 1. Хост-машина рассчитывает X 1=Км_!=1/(2+Ь2/т), К,=1/(2+112/т-К1.1), и циклически рассылает эти значения в каждый процессор линейки, составляющей тороидально связанный куб.

Этап 2. Пусть вычисляется первая партия значений иКп к при п=1.ЛЭ к=1..Е. В каждом кольце, образованном процессорами с фиксированными координатами с1, е параллельно рассчитываются п к+ (Ь^Ои^ к)Ьч и

к)Км.! соответственно процессорами (1, <1, е) и

[то<1(М-1,С), с1, е], где (1=1..В, е=1..Е. Для расчета р2 значение р, передается параллельным сдвигом в направлении роста координаты с в каждой кольцевой

структуре [тос1(1,С), (1, е] (при фиксированных с! и е, где е=1.ЛЗ) по

формуле р^рц+^/т^^Кь 1=2..N-2. Подобно расчету р2 находятся остальные 1=2..М-2. Затем вычисляется ик_ид=(рм-1 +Ь!к-г р1«)/(1-Км-1-Км-2) в процессорах [тос!(?Ч-1,С), ё, е] и сдвигом в направлении убывания координаты с пересылаются соседним процессорам для расчета йк-2,п,к по формуле

Аналогично расчету и1ч2пк находятся остальные ¡=(N-2)..2 процессорами [mod(i,C)) б, е].

Подобным образом находится следующая партия и^к при к=1..Е, п=(Б + 1)..(2б); затем при п=(2В + 1)..(30) и т.д. до п=^-1)/В]..(К-1); аналогично при к=(Е + 1)..(2Е), пока не будет рассчитана последняя партия при п=[(1*-1)Я>]..(1*-1) и к=[(К -1)/Е]..(К -1).

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

Этап 3. Аналогично предыдущему этапу, в каждом кольце, образованном процессорами с фиксированными координатами с, е параллельно рассчитываются в направлении роста номеров <1 - р\, и ри а затем в противоположном направлении рассчитываются и^^. Исполнение этапа возможно в модифицированном варианте.

Этап 4. Аналогично второму этапу, в каждом кольце, образованном процессорами с фиксированными координатами с, с1 параллельно рассчитываются в направлении роста номеров е - рь ирь а затем в противоположном направлении рассчитываются и ^;. Результат и^; записывается в памяти соответствующего процессора.

Этапы 2-4 повторяется М раз до тех пор, пока не будут вычислены результаты последнего слоя.

Этап 5.Хост-машина собирает полученные данные и делает их доступными для пользователя.

При ^=0 параллелизм «модернизированного» алгоритма достигает максимального уровня: 8^ое=СБЕ, а На всех этапах «модернизированный»

алгоритм является локальным и мелкозернистым.

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

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

В заключении сформулированы основные результаты диссертации.

1. Дано описание мелкозернистого локально-параллельного программирования и определены специальные свойства для МШО-машин, для которых стиль МЛП-программирования будет наиболее эффективным.

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

3. Рассмотрены параллельные алгоритмы в методах сеток решения задач математической физики для МШП-машин с распределенной памятью, предложенные различными авторами, и проведен их анализ на соответствие стилю МЛПП.

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

5. Разработана программа «Решение задач математической физики в мето-

де сеток с вычислением оценок параллелизма для МЛП-алгоритмов». . .

Публикации по теме диссертации:

1. Заручевская Г.В. Реализация решения разностной схемы расщепления двумерного уравнепия теплопроводности в мелкозернистом локально-параллельном стиле программирования.// - Известия Волгоградского государственного технического университета: межвуз. сб. науч. ст. № 1(39) / ВолгГТУ. - Волгоград, 2008 - 120с. - (Сер. Актуальные проблемы управления, вычислительной техники и информатики в технических системах. Вып. 4), с.16-19.

2. Заручевская Г.В. Реализация решения разностной схемы расщепления трехмерного уравнения теплопроводности в мелкозернистом локально-параллельном стиле программирования.// - Системы управления и информационные технологии, 2007, N4(30), с. 91-94.

3. Воробьев В.А., Заручевская Г.В. Мелкозернистый локально-параллельный алгоритм для четырехточечной неявной разностной схемы уравнения теплопроводности.// Вестник Поморского Университета, серия «Естественные и точные науки» №2(4), 2003, с.94-102.

4. Лозинская Г.В. Мелкозернистый локально-параллельный алгоритм для четырехточечной явной разностной схемы управления теплопроводности. С именем Ломоносова. Сборник научных трудов студентов и аспирантов ПГУ. -Архангельск: изд-во ПГУ, 2002. с.263-266.

5. Лозинская Г.В., Кожин И.Н., Дербина Ю.В., Юфрякова О.А., Тесто-ва И.В. Мелкозернистый локально-параллельный алгоритм для решения разностной задачи Дирихле для уравнения Пуассона. XIV международные Ломоносовские чтения. Сборник научных трудов. - Архангельск: изд-во ПГУ, 2002.С.388-390

6. Воробьев В.А., Заручевская Г.В. Мелкозернистый локально-параллельный алгоритм для разностной схемы расщепления уравнения тепло-

проводности // Высокопроизводительные вычисления на кластерных системах. Материалы шестого Международного научно-практического семинара. Том 1 / Иод ред. проф. Р.Г. Стронгина. Санкт-Петербург, 2007. 281 с. С. 109-116.

7. Воробьев В .А., Заручевская Г.В. Реализация явного чебышевского метода решения задачи Дирихле для уравнения Пуассона в мелкозернистом локально-параллельном стиле // Вестник математического факультета. Вып. 8: межвуз. Сб. науч. трудов; Поморский гос. ун-т им. М.В. Ломоносова. - Архангельск: Поморский университет, 2007. - 155 с. С. 83-87.

8. Кожин И.Н., Воробьев В.А., Лозинская Г.В. Клеточная машина // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы четвертого Международного научно-практического семинара и Всероссийской молодежной школы. Самара, 2004 с. 116-120

9. Заручевская Г.В. Реализация явного чебышевского метода решения задачи Дирихле для уравнения Пуассона в мелкозернистом локально-параллельном стиле // Высокопроизводительные вычисления на кластерных системах. Материалы седьмой Международной конференции-семинара. - Нижний Новгород: Изд-во Нижегородского госуниверситета, 2007.443с. С.163-168.

10. Воробьев В.А., Заручевская Г.В. Реализация явного чебышевского метода решения задачи Дирихле для уравнения Пуассона в мелкозернистом локально-параллельном стиле // Вестник математического факультета. Вып. 8: межвуз. Сб. науч. трудов; Поморский гос. ун-т им. М.В. Ломоносова. - Архангельск: Поморский университет, 2007. - 155 с. С. 83-87.

Подписано в печать 30.10.2008 Бумага офсетная Усл. печ. л1 Заказ № 5548 тираж 100 экз.

Отпечатано в ООО «Типография Пресс-Принт» Архангельск, ул. Гагарина, 42, оф. 507 Тел./факс: 212-210,212-616*

Введение.

Глава 1. Основные положения стиля мелкозернистого локально-параллельного программирования и разработка соответствующей эффективной параллельной архитектуры MIMD-машины.

1.1. Многопроцессорные ЭВМ типа MIMD.

1.2. Коэффициенты, характеризующие эффективность параллельных алгоритмов. Типы MIMD-машин.

1.3. Мелкозернистое локально-параллельное программирование.

1.3.1. Архитектура однородной вычислительной системы

1.3.2. Концепция стиля мелкозернистого локально-параллельного программирования.

1.3.3. Эвклидовы структуры.

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

Глава 2. Параллельные алгоритмы задач математической физики для многопроцессорных систем: обзор и анализ на соответствие МЛПстилю программирования.

2.1. Эллиптические уравнения.

2.1.1. Постановка задачи.

2.1.2. Явный чебышевский метод.

2.1.3. Метод верхней релаксации.

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

2.1.3.2. Точечный метод верхней релаксации при красно—черном упорядочении неизвестных.

2.1.4. Многосеточный метод.

2.2. Параболические уравнения.

2.2.1. Постановка задач.

2.2.2. Явная схема.

2.2.3. Факторизованная схема.

2.2.3.1. Вычислительный алгоритм.

2.2.3.2. Параллельные вычисления с распараллеливанием прогонки

2.2.3.3. Параллельные вычисления с переформировкой массивов

2.2.4. Параллельные неявные методы переменных направлений.

2.2.4.1. Распараллеливание метода Писмена-Рэкфорда для двумерных задач.

2.2.4.2. Неявные алгоритмы переменных направлений для трехмерных задач.

2.2.4.3. Эффективность распараллеливания и коммуникационные проблемы.

Глава 3. Мелкозернистые локально- параллельные алгоритмы для задач математической физики, решаемых с помощью неявных разностных схем.

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

3.2. Метод верхней релаксации.

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

3.3. Мелкозернистый локально- параллельный алгоритм для четырехточечной неявной разностной схемы одномерного уравнения теплопроводности.

3.4. Мелкозернистый локально - параллельный алгоритм для разностной схемы расщепления двумерного уравнения теплопроводности.

3.4.1. Алгоритм 1.

3.4.2. Алгоритм 2.

3.4.3. Алгоритм 3.

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

Глава 4. Программная реализация некоторых задач математической физики в методе сеток с вычислением оценок параллелизма для МЛП -алгоритмов.

4.1. Реализация явного чебышевского метода решения задачи Дирихле для уравнения Пуассона.

4.1.1. Порядок создания приложения.

4.2. Реализация решения разностной схемы расщепления двумерного уравнения теплопроводности.

4.3. Реализация решения разностной схемы расщепления трехмерного уравнения теплопроводности.

Актуальность работы. ЭВМ первого и второго поколений вследствие низкого быстродействия не позволяли за приемлемое время решать многие важные научно-технические задачи. Так как имеющаяся к тому времени элементная база не позволяла существенно увеличить их быстродействие, один из возможных путей решения возникшей проблемы состоял в том, чтобы разбить задачу на отдельные независимые крупные блоки подзадач (фрагменты), каждую из которых можно было бы решать независимо от других. Это привело к необходимости разработки специальных численных методов, допускающих возможность такого разделения, развитие которых остается актуальным и в настоящее время [1, 2].

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

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

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

Практическая реализация данного подхода связана с появлением в 80-е годы сверхбольших интегральных схем (СБИС), схемотехнические ограничения которых определили требования, предъявляемые к алгоритмам для реализации на их базе:

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

- параллельно-поточная организация выполнения алгоритма, обеспечивающая высокое быстродействие и эффективность СБИС, а также локализацию связей элементов по принципу близкодействия;

- двумерность структуры алгоритма, отвечающая присущему на сегодняшний день требованию планарности физической реализация устройств на СБИС;

- асинхронность исполнения и взаимодействия различных частей алгоритма, предельно упрощающая задачи управления и синхронизации СБИС и делающая возможным построение устройств на СБИС, содержащих произвольно большое число элементов [4].

Все разработанные алгоритмы для ОВС были подчинены этим требованиям, в частности, требованиям планарности [5, 6, 7].

Однако в настоящий момент уже существуют разработки, позволяющие отойти от планарной технологии СБИС к объемной. Так, в декабре 2007 года появилась информация о том, что японская научно-исследовательская компания Unisantis Electronics в ближайшее время разработает "трехмерные" транзисторы, которые могут работать на частоте до 50 гигагерц, что почти в десять раз больше частоты, на которой могут работать современные микропроцессоры. "Трехмерный" транзистор, или, как его называют изобретатели, SGT (Surrounding Gate Transistor), отличается от обычного тем, что представляет собой кремниевый стержень, вокруг которого располагаются ячейки памяти, электрические контакты и другие компоненты. SGT позволяет сократить расстояние, которое проходят электроны, создает меньше тепла, а его производство дешевле современных "плоских" микросхем. По оценкам авторов технологии, ее потенциала хватит на развитие в течение трех десятков лет [7].

Параллельная интерпретация существующих методов решения задач требует выявления и использование пространственно-временных особенностей реализации алгоритмов. Время исполнения параллельных алгоритмов зависит не только от числа арифметических операций, но и от способа и количества пересылок данных как между процессорами системы, так и между процессором и памятью, а также от задержек, связанных с синхронизацией [4]. Так, в настоящее время многочисленные вычислительные ядра суперкомпьютеров обмениваются информацией по медным проводам. Исследователи из IBM надеются заменить их световыми импульсами, которые будут передавать ту же информацию. Беспроводная система будет требовать гораздо меньше места и потреблять в десятки раз меньше энергии, в то время как информация будет передаваться в сто раз быстрее. С использованием новой технологии удастся также существенно снизить энергопотребление современных суперкомпьютеров и уменьшить их габаритные размеры [7].

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

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

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

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

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

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

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

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

В работах Воеводина В.В.[1], Галба Е.Ф.[11], Ильина В. П.[12, 19], Марчука Г.Щ13, 14], Молчанова И.Н.[15,16], Ортега Дж.[17], Родрига Г.[18], Фета Я. И.[19] и др. рассматриваются исключительно крупноблочные алгоритмы решения задач математической физики, предназначенные для вычислительной техники со стандартной системой коммутаций типа линейка, решетка, кольцо, кольцо с хордами и т.п. Основная идея распараллеливания состоит в следующем: расчетная область (сетка) разбивается на несколько подобластей (по числу вычислительных модулей) так, чтобы каждая подобласть содержала примерно равное число узлов. Данные, необходимые для расчета в подобласти, загружаются в соответствующий вычислительный модуль. Каждый вычислительный модуль согласно алгоритму производит вычисления в расчетных ячейках подобласти сетки, а затем обменивается необходимыми расчетными данными с другими, связанными системой коммутации, вычислительными модулями. Этот процесс продолжается до получения необходимого результата. Таким образом, вычислительный модуль на каждом этапе обрабатывает крупный блок данных (подобласть сетки), а обмен данными происходит в потоке: вычислительный модуль отправляет и принимает большой объем данных.

В более поздних работах (Воеводин В.В.[1], Гергель В.Щ20], Кор-неев В.В.[21]) рассматривается структура под названием «решетка-тор». Эта структура появляется в технологии параллельного программирования MPI. Так, Корнеев В.В. приводит пример перемножения двух матриц больших размерностей в торе. В этом алгоритме элементы матрицы циклически распределены в узлах тора, число обменов минимизировано, обмен данными производится блоками. Такая реализация параллельного перемножения матриц относится к блочному типу. Если авторы упоминали об использовании решетки-тора для блочных алгоритмов решения сеточных задач математической физики (Гергель В.ГЦ20]), то на самом деле в алгоритме были задействованы только узлы и связи решетки, а связи противоположных сторон решетки не использовались. В своей работе [12] В.П. Ильин упоминает о «мелкозернистом распараллеливании» для решетки с числом процессоров, равным числу узлов сеточной области, но связи рассмотренного им алгоритма не являются локальными. Для повышения эффективности блочного алгоритма этот автор предлагает использовать новую структуру- двумерную бициклическую сеть. Заметим, что при распараллеливании сеточных задач математической физики (задача Дирихле для уравнения Пуассона) крупноблочными методами циклическое распределение узлов сеточной области менее удобно, чем разбиение области на подобласти, т.к. в этом случае значительно увеличивается объем передаваемых данных. При этом ни один из авторов МЛП-алгоритмы не рассматривает, ориентируясь на возможности реально существующей вычислительной техники.

Таким образом, разработка и исследование МЛП-алгоритмов для задач математической физики - одно из перспективных направлений современного параллельного программирования. Актуальность выполненной работы состоит в создании и анализе ряда МЛП-алгоритмов для задач математической физики. В [8] для этих целей применяются модели клеточных автоматов.

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

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

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

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

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

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

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

На защиту выносятся

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

Данная работа посвящена применению мелкозернистого локально-параллельного программирования (МЛПП) к некоторым задачам математической физики.

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

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

Определены специальные свойства для MIMD-машин (пп.1.2), для которых стиль мелкозернистого локально-параллельного программирования будет наиболее эффективным:

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

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

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

Показаны преимущества применения для решения задач математической физики в методе сеток такой редко используемой структуры, как тор.

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

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

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

Показано, что МЛП-алгоритмы задач математической физики для ОВС с распределенной памятью более эффективны по сравнению с аналогичными крупноблочными алгоритмами.

1. Воеводин В.В., Воеводин Вл. В. Параллельные вычисления. -Спб.: БХВ-Петербург, 2002. 608 с.

2. Воеводич В.В. Параллельные вычисления и математическое образование // Математика в высшем образовании. 2005. - №3. С.9 - 27.

3. Kung Н.Т. Why systolic architecture? // Computer. 1982. - 15. №1. - P.37 - 46.

4. Седухин С.Г. Систематический подход к проектированию вычислительных структур на базе сверхбольших интегральных схем.-Новосибирск, 1985. 46 с.

5. Молдован Д.И. О разработке алгоритмов для систолических матриц СБИС. ТИИЗР, 1983 т. 71, № I, с. 140 - 149.

6. Miranker W.L., Winkler A. Spacetime Kepresntatioas of Computational Structures. Computings 1984 №32,p. 93 - 114.7. http://lenta.ru/news/2007/12/10/fifty/

7. Бандман О.JI. Мелкозернистый параллелизм в математической физике // Программирование. 2001. - №4. С. 12 - 25.9. http://teamat.livejournal.com/

8. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука, 1986. - 296 с.

9. Молчанов И.Н., Галба Е.Ф. Параллельные вычисления в методах сеток решения задач математической физики на MIMD- машинах. -Киев, 1990.-41 с.

10. Ильин В.П. Параллельные неявные методы переменных направлений //Журн. выч. математики и мат. физ. 1997.-t.37, №8. - С.899-907.

11. Марчук Г.И. Методы вычислительной математики. М.: Наука, 1980.-535 с.

12. Марчук Г.И., Ильин В.П. Параллельные вычисления в сеточных методах решения задач математической физики. Новосибирск, АН СССР Сибирское отделение, Вычислительный центр, 1979. - 21 с.

13. Молчанов И.Н. Машинные методы решения прикладных задач. Дифференциальные уравнения. Киев: Наук, думка, 1988. - 344 с.

14. Молчанов И.Н. Введение в алгоритмы параллельных вычислений. Киев: Наук, думка, 1990. - 128 с.

15. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем.-М.:Мир,1991.- 367 с.

16. Параллельные вычисления / под ред. Г.Родрига.- М.: Наука, Гл. ред. физ.-мат. лит., 1986. -376 с.

17. Ильин В.П., Фет Я. И. Семейство параллельных процессоров для задач математической физики // Вычислительные процессы. 1986, вып. 1 с. 81-99.

18. Теория и практика параллельных вычислений: учебное пособие / В.П. Гергель -М.: Интернет-Университет Информационных технологий, БИНОМ: Лаборатория знаний, 2007. 423 с.

19. Корнеев В.Д. Параллельное программирование в MPI. -Новосибирск: Изд-во ИВМиМГ СО РАН, 2002. 215 с.

20. Воробьев В.А. Теория однородных вычислительных систем: однородные структуры. Архангельск, Поморский государственный университет имени М.В.Ломоносова, 2000. - 91 с.

21. Корнеев В.В. Архитектура вычислительных систем с программируемой структурой. Новосибирск: Наука, Сибирское отделение, 1985.

22. Воробьев В.А. Теоретические основы построения однородных вычислительных систем на неразрезных процессорных матрицах. Дис. . д-ра техн наук. Томск, 1999.

23. Мишин А.И., Седухин С.Г. Однородные вычислительные системы и параллельные вычисления // Автоматика и вычислительная техника, №1.- 1981.-С. 20-24.

24. Воробьёв В.А. О содержании теории однородных вычислительных систем // XXIV областная научно-техническая конференция, посвященная Дню радио: Тезисы докладов. -Новосибирск, 1981. С. 70-71.

25. Воробьёв В.А. Модель коллектива вычислителей, основанная на принципе близкодействия // Вычислительные системы с программируемой структурой: Вычислительные системы, 94. -Новосибирск: Институт математики СОАН СССР, 1982 . С. 103-119.

26. Воробьёв В.А., Лаходынова Н.В. Теория модели коллектива вычислителей, основанная на принципе близкодействия // Тезисы докладов XXV областной научно-технической конференции, посвященной 60-й годовщине образования СССР и Дню радио. -Новосибирск, 1982 .

27. Валиев М.К., Мишин А.И. Организация параллельных вычислений на системах с локальными взаимодействиями элементов // Автометрия, № 6. -1983. С. 88-96.

28. Завьялов Ю.С., Мишин А.И. Временная сложность алгоритмов задач гидро-аэродинамики и производительность параллельных вычислительных систем // Институт математики СО АН СССР, Препринт № 20. -Новосибирск, 1985.

29. Транспьютеры: архитектура и программное обеспечение. М.: Радио и связь, 1993.

30. Прангишвили И.В.Параллельные вычислительные системы с общим управлением / И.В. Прангишвили, С.Я. Виленкин, И.Л. Медведев-М. :Энергоиздат, 1983.

31. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999. 320 с.

32. Tanenbaum Andrew S. Structured Computer Organization. NJ: Prentice-Hall International, 1999. - 669 p.

33. Воробьев B.A. Об эффективности параллельных вычислений. // Автометрия. 2000. - № 1. С. 50-58.

34. Лаходынова Н.В., Воробьев В.А., Еремина Н.Л. Отказоустойчивость однородных процессорных матриц. Томск: Изд-во Томского архитектурно-строительного университета, 2002.-154 с.

35. Корячко В.П., Скворцов С.В., Телков И.А. Архитектуры многопроцессорных систем и параллельные вычисления: Учеб. пособие. -М.:Высш.шк., 1999.-235 с.

36. Немнюгин С.А., Стесик О.Л. Параллельное программирование для многопроцессорных вычислительных систем. СПб.:БХВ-Петербург, 2002. - 400 с.

37. Коровкин П.П. Математический анализ. Часть И.- М.: Просвещение, 1974.-463 с.

38. Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений М.: Наука, 1978. - 592 с.

39. Математическая энциклопедия: Гл. ред. И.М. Виноградов, т. 5 Слу-Я-М., «Советская Энциклопедия», 1984. -1248 стб., ил. С. 848-849.

40. Федоренко Р.П. Релаксационный метод решения разностных уравнений// Журн. выч. математики и мат. физ. 1961.-I, №5. - С. 922-927.

41. Лангер У. О выборе итерационных параметров в релаксационном методе на последовательности сеток // Вычислительные методы линейной алгебры. :ОВМ АН СССР, 1983. С. 238-246.

42. Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре. Кибернетика, 1977, №6, с. 28-40.

43. Федоренко Р.П. Релаксационный метод решения разностных уравнений // Журн. выч. математики и мат. физ.- 1961. -I, №5. -С.922-927.

44. Ильин В.П. Численные методы решения задач электрофизики. М.: Наука, 1985.

45. Яненко Н.Н., Коновалов А.Н., Бугров А.Н., Шустов Г.В. Об организации параллельных вычислений и «распараллеливании» прогон-ки.-Численные методы механики сплошной среды, 1979, т. 10, №6, стр. 139145.

46. Волков Е.А. Численные методы: Учеб. Пособие для вузов. -М.: Наука, 1987. -248 с.

47. А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.-535 с.

48. Воробьев В.А., Заручевская (Лозинская) Г.В., Севостьянова О.В. Мелкозернистый локально-параллельный алгоритм для четырехточечной неявной разностной схемы уравнения теплопроводности.- Сборник трудов молодых ученых школы семинара РаСТ-2003, с.200-203

49. Воробьев В.А., Заручевская Г.В. Мелкозернистый локально-параллельный алгоритм для четырехточечной неявной разностной схемыуравнения теплопроводности. // Вестник Поморского Университета, серия «Естественные и точные науки» №2(4), 2003, с. 94-102.

50. С.К. Годунов, B.C. Рябенький. Разностные схемы (введение в теорию): Учебное пособие-М.: Наука, 1977. 439 с.

51. Заручевская Г.В. Реализация решения разностной схемы расщепления трехмерного уравнения теплопроводности в мелкозернистом локально-параллельном стиле программирования. //-Системы управления и информационные технологии, 2007, №4(30), 104с., С. 91-94.

52. Бобровский С.И. Delphi 7. Учебный курс-СПб.: Питер, 2005.

53. Баженова И.Ю. Delphi 7. Самоучитель программиста. -М.: КУДИЦОБРA3. 2003. 448 с.

54. Бобровский С.И. Технологии Delphi 2006. Новые возможности. СПб.: Питер, 2006. -288 с.736 с.