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

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

Зорина Дарья Алексеевна

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ЭКОНОМИЧНЫХ

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

Специальность:

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

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

Таганрог - 2008

003461445

Работа выполнена в Технологическом институте Южного федерального университета на кафедре высшей математики.

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

профессор,

Сухинов Александр Иванович

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

Боженюк Александр Витальевич, г. Таганрог

кандидат технических наук, доцент, Никифоров Александр Николаевич, г. Новочеркасск

Ведущая организация: СевКавГТУ, г. Ставрополь

Защита состоится «25» декабря 2008 г. в 14-20 на заседании диссертационного совета Д 212.208.22 при Технологическом институте Южного федерального университета по адресу: пер. Некрасовский, 44, ауд. Д-406, ГСП17А, г. Таганрог, Ростовская область, 347928.

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

Южного федерального университета по адресу: ул. Пушкинская, 148, г. Ростов-на-Дону, 3444000.

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

Ученый секретарь диссертационного совета доктор технических наук, профессор

ВД^ ^ V Щх

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

Актуальность темы.

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

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

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

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

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

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

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

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

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

- разработка библиотеки параллельных алгоритмов для МВС с распределенной памятью на основе технологии MPI.

Основные научные результаты:

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

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

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

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

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

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

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

Методы проведения исследования. В диссертационной работе использованы теория разностных схем, методы решения сеточных уравнений, в 'частности, быстрые прямые методы решения сеточных уравнений, методы распараллеливания, основанные на технике domain decomposition.

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

Апробация результатов работы. Основные результаты докладывались и обсуждались на III Международной конференции по новым технологиям и приложениям современных физико-химических методов для изучения окружающей среды (Ростов-на-Дону, 2005); Международной научной конференции «Современные проблемы прикладной математики и математического моделирования» (Воронеж, 2005); VI Международной научно-практической конференции «Моделирование, теория, методы и средства» (Новочеркасск, 2006); VIII Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (Таганрог, 2006); V Школе-семинаре «Математическое моделирование, вычислительная механика и геофизика» для студентов, аспирантов и молодых ученых Юга России (Ростов-на-Дону, 2006); VII Международной научно-практической конференции «Методы и алгоритмы прикладной математики в технике, медицине и экономике» (Новочеркасск, 2007); Международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы» (Дивноморское, 2007); II Международной научной конференции «Современные проблемы прикладной математики и математического моделирования» (Воронеж, 2007); VIII Международной научно-практической конференции «Методы и алгоритмы прикладной математики в технике, медицине и экономике» (Новочеркасск, 2008).

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

Структура и объем работы. Диссертация содержит 158 страниц машинописного текста, включая введение, три раздела, заключение, список литературы из 100 наименований, 34 рисунка, 3 таблицы.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

В первом разделе ставится задача разработки библиотеки параллельных алгоритмов быстрых прямых методов эффективного решения сеточных эллиптических уравнений, возникающих при анализе задач математической физики, на кластере распределенных вычислений с использованием языка C/C++ и библиотеки MPI.

В настоящее время имеется множество методов решения уравнений матфи-зики, в том числе метод конечных элементов, конечных объемов, а также многие другие неклассические методы, основанные на LBM подходе (Lattice Boltz-

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

Пусть область изменения аргумента х есть отрезок [0,/]. Разобьем отрезок

[О,/] точками Xf-ih, / = 0,1,2, , h> 0, на N равных частей длины h = l/N. Множество точек х. называется разностной сеткой на отрезке [0,/] и обозначается юь = = ih, i = 0,1,..., jV} , а число h - расстояние между точками (узлами) сетки - называется шагом сетки.

Функцию у, = y(xj) дискретного аргумента х,, /' = 0,1,2,..., N, называют сеточной функцией, определенной на сетке <öh. Всякой непрерывной функции f(x) можно поставить в соответствие сеточную функцию f!".

Пусть область изменения аргументов (x,t) есть прямоугольник Z)=(xe[Q/], /е[0,7]). Сеткой в прямоугольнике D называется множество узлов (х;,^) с координатами лtj=jT и обозначается ¿^ ={(х, =ih,t] = jr), i=\%...,N, j=\%...,N0).

Непрерывной функции u(x,t), где (x,t) - точка из D, будем ставить в соответствие сеточную функцию и/ = и(х, ,tj).

Аналогично вводится понятие пространственной сетки äh, в которой шаг h = (/ij,/^,...,h4) выбирается по координатным направлениям.

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

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

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

Рассмотрим задачу для трехмерного уравнения теплопроводности с постоянными коэффициентами:

|у = £и + /(х,(), «С0, /е(0,/0], (1)

с начальными и граничными условиями:

"Ми^М' МеГх[0,/0], (2)

"(*> 0,.« = "«(*)' (3) .

Эги

где 1и = = + Ь2 Ьаи=—2> а-1,2,3;

дха

д0 = {0 < ха < 1а, а = 1,2,3} - параллелепипед с размерами /,, /2, /3;

Г - граница области Са, ¿?0 = С0 и Г, 10 - начальный момент времени.

В реальных задачах коэффициент теплопроводности может меняться по объему, что приводит к постановке задачи (1) с переменными коэффициентами, т.е.

д' ^

Lu=y\Lu, Lu =

X-w а ' а

а=I ОТ,

, / ч ди

ка (■*"!> *2> Х3 ' V а.

ka(x],x2,x3,t)>ca>0, аг = 1,2,3, са= const. Задача (1) - (3) может быть обобщена на р -мерный случай. Рассмотрим трехмерное уравнение теплопроводности в случае разделяющихся переменных. Пусть поставлена смешанная задача Коши для трехмерного уравнения теплопроводности

+ /(*,/), x = (x„x2,x3)eG, te(0,T]; (4)

dt ,=i дх,

f, диЛ к, — дхi

и(х, О) = гг0(х1,х2,х3), 1=0, (*,, х2, дг3) е (7; (5)

и(х],х2,х3,/) = //(х„х2,х3,1), хеГ, /е[0,Г], (6)

где Г - граница области б, С = П х {0 < х3 < /3}, П - двумерная (плоская) сеточная область ступенчатой формы, допускающая построение сетки, равномерной, по крайней мере, по одному направлению. В отношении входных данных задачи будем предполагать, что они таковы, что обеспечивают существование и единственность решения задачи (4) - (6). Будем считать, что коэффициенты уравнения (4) к, и к2 зависят только от одной переменной, т.е. = А, (х3),

к2 = к2 (х3), или, в общем случае, Л, = к^ (х3_а, х3), к2 = к2 (х3_а, х3), а = 1,2 .

Возможные обобщения постановки задачи заключаются в следующем: область С может представлять собой связное объединение областей указанного выше

типа; на границе области по одному из направлений возможно задание граничных условий 3-го рода. Тогда в области в построим равномерную пространственную сетку о)ъ с шагами = 1а ¡Ыа в направлении координатных направлений Оха, а = 1,2,3 соответственно. Пусть уЪа - узлы сетки, граничные по направлению Оха. Аппроксимируем задачу (4) - (6) локально-двумерной схемой. Используется известная аппроксимация дифференциальных выражений

cfcc.

■а К

, ди

к—

дх.

ка =ka(xl,x2,x3,t)>0, а = 1,2,3

а /

соответственно разностными

/г

Ух.

а = 1,2,3.

Рассмотрим частный случай А;, (х,, х2, х}, /) = const, , к2 (*,, х2, хг, t) = const2. Тогда имеем разностную задачу

л+1/2 _ п

У-— = (Л,+Л2)/+1,2+/;",

т

л+1_ п+иг

£--= A3/+,+/2\ х и = 1,2,..., и, — 1;

(7)

/(х) = м0(х), xeo}h,

ftll2=M{x,t), хеу^ u^; /+) = n{x,t), хеП>- (8)

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

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

В качестве системы для реализации вычислительных алгоритмов выбран кластер распределенных вычислений с топологией в виде полного графа. Каждый узел (процессор) характеризуется производительностью ЗГГц, объемом оперативной памяти 1Гб, работающий под управлением операционной системы ASPLinux на ядре 2.4.20-9asp. Предложено использовать методы распараллеливания, основанные на технике domain decomposition. Разработан метод определения характеристик параллельного алгоритма.

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

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

Каждый параллельный алгоритм оценивается по двум параметрам -ускорению Бр и эффективности Ер, которые определяются по формулам

5 =-Ч £„ = —-100%,

' и ' Р

где Г, - время решения исходной задачи на одном процессоре, / - время

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

Коэффициент эффективности передачи кЕ равен отношению скорости передачи полезной информации, вычисляемой как Б = пЬ, где / - время передачи сообщения размером п байт, к скорости передачи данных между узлами 8С. С его помощью можно получить время передачи, зная длину этой передачи в байтах или количество арифметических операций, выполняемых за передачу. Длительность передачи определяется как: г = V /(к Е8С), количество арифметических операций выполняемых за передачу: ()А = к * V / кЕ, где V - объем полезной информации в сообщении, к - коэффициент, характеризующий число обобщенных арифметических операций, выполняемых за время передачи 1 байт между узлами кластера.

Значение коэффициента эффективности передачи кЕ можно аппроксимировать

функциональной зависимостью: кЕ = V / (V + V * с, + с2), где V - длина сообщения

в байт, V * с, - объем служебной информации в пакете, с2 - коэффициент,

отражающий время на подготовку посылки. Тогда ускорение и эффективность алгоритма можно записать:

5 — £ __* Qлs_

где <2л5 - количество арифметических операций последовательного алгоритма, (¿ле - количество арифметических операций параллельного алгоритма, /а - время

10

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

( - ^

няемых узлов, !по1 — время, затраченное на обмены данных г = ^ V

1

Для коротких сообщений справедлива также формула

где Ус - объем служебных данных в каждом из пересылаемых пакетов.

Во втором разделе разработаны параллельные алгоритмы методов прогонки Коновалова-Яненко и циклической скалярной редукции, предназначенные для решения систем линейных алгебраических уравнений с трехдиагональной матрицей на кластерных системах с распределенной памятью. Получены оценки эффективности алгоритмов на основе анализа числа выполняемых операций. Выполнена практическая реализация разработанных алгоритмов на кластере распределенных вычислений и получены экспериментальные оценки, позволяющие сделать вывод об эффективности и целесообразности использования алгоритмов на МВС с распределенной памятью, где N = 29 (см. рис. 1, 2).

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

10 ч 15

Рис. 1. Практически и теоретически полученная эффективность параллельного алгоритма метода Коновалова-Яненко

1 - теоретическая оценка для р=4; 2-р=2: 3-р=4: 4 - р=8:

Рис. 2. Практически и теоретически полученная эффективность параллельного алгоритма метода циклической редукции

□ = {0,1,...,./V} на связные подмножества = (г,'"0,...,^"0}, (т = 0,...,р-1) соответствующие разбиению вектора неизвестных по процессорам. В результате такого разбиения процессор с номером т обрабатывает (4™) -1\"'] +1) точек. Реализованный параллельный алгоритм основан на принципе суперпозиции решений систем линейных алгебраических уравнений. ) Для достижения максимальной эффективности на двух узлах, используется реализованный алгоритм метода встречных прогонок.

I В третьем разделе разработаны параллельные алгоритмы методов решения I двумерных сеточных эллиптических уравнений: метода полной редукции, I метод Фурье, как составная часть алгоритма неполной редукции (метода типа 1 FЛC/?(/)), метода неполной редукции. Получены теоретические и | экспериментальные оценки эффективности алгоритмов с учетом затрат времени на обмены и получены области эффективности алгоритмов. Показано, что максимальная эффективность параллельной реализации комбинированного алгоритма неполной редукции может быть достигнута путем выбора количества 'шагов редукции, предшествующих разложению по базису, и приведены I соответствующие зависимости. Разработана библиотека параллельных алгоритмов для эффективного решения больших сеточных задач, в которой решается проблема выбора оптимальной параллельной реализации для данной задачи, что определяется числом узлов сетки, имеющимся количеством | процессоров р и коэффициентами к и кЕ .

Основным источником задач, решаемых методом полной редукции, являются разностные аппроксимации двумерных задач математической физики, например, разностная задача Дирихле для уравнения Пуассона в прямоугольнике или ' неявная разностная схема для двумерного уравнения теплопроводности. Метод полной редукции позволяет получать решения задач с затратой 0{ММ\а%2 М) ' арифметических действий, М, N - число узлов сетки по каждому направлению.

0 12 3 4 5 6 7 8 Э 10 11 12 13 К 15 16

0 4 1? 16

Рис. 3. Способ исключения неизвестных векторов из системы неизвестных

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

+ CYj ~ ^/+1 = Fj > 1<7<Л/-1, ro=F0, ' (9)

где J^ - вектор неизвестных, С - квадратная невырожденная матрица, F} -заданная правая часть, N есть степень двойки, т. е. N = 2", п > 0 - целое число.

В основе метода лежит специальный способ исключения неизвестных векторов из системы (9), продемонстрированный на рис. 3 для п = 4.

Каждый шаг процесса исключения уменьшает число неизвестных векторов, на последнем уровне редукции останется одно уравнение для вектора YNn. Обратный ход метода заключается в последовательном нахождении неизвестных Y сначала с номерами j, кратными NIA, затем N / 8 и т.д.

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

При параллельной реализации метода входная информация, то есть двумерный массив F, j, разрезается на «вертикальные» полосы и распределяется по узлам кластера (см. рис. 4). В процессор с номером m, где р - количество узлов кластера, 1 <т< р загружаются элементы исходных массивов со значениями индексов \N!р~)-(т-1) + 1 < ¡'<[N7р\т , Далее начинаются вычисления по

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

6)

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

Результаты реализованного параллельного алгоритма метода полной редукции приведены на рисунке 5.

Метод неполной редукции позволяет получать решения задач с затратой 0(МЫ\щ2 М) арифметических действий, М, N - число узлов сетки по каждому направлению. Метод разложения в однократный ряд позволяет ограничиться вычислением только двух сумм Фурье с затратой к^2 /У2)

действий и решением серии трехточечных краевых задач за 0(Л', Л'2) действий. Дальнейшее усовершенствование метода разделения переменных возможно по пути уменьшения числа слагаемых в вычисляемых суммах при сохранении возможности использовать алгоритм быстрого преобразования Фурье. Достигнуть этой цели можно, комбинируя метод разложения в однократный ряд и метод редукции. Рассмотрим задачу Дирихле на прямоугольной сетке а>. Ли = -/(х), хесо, и(х) = 0, х е у, Л = Л,+Л2, Ааи = иг , а = 1,2. (10)

Введем вектор неизвестных и] следующим образом:

11) = (к(1,у),и(2,у),...,«(//, -1,;')), 0 </< М2 и определим вектор правых частей ^ формулой В) = (/^/(1,у), ^7(2,7), l<j<N1-l.

Тогда разностную задачу (10) можно записать в виде следующей системы векторных уравнений:

1 < у < Лг2 -1, и0=иНг= о, где квадратная трехдиагональная матрица С определяется равенствами Си, =({2Е-%\)и{\,]),...,{2Е-%\)и{П1 -1 Л), Л,и = и^, и(0,у) = М0У„у>0.

Пусть Иг=2т. Напомним, что первый шаг процесса исключения в методе полной редукции состоит в выделении «укороченной» системы для неизвестных И1 с четными номерами у

-г/,_1+С(,)Е/,-1/у+2 = /*'>, 7 = 2,4,6,...,^-2, и0=и„2 =0 " (11)

и уравнений С(У; = Г)+ £/,_, у = 1,3,5,..., -1 для определения

неизвестных с нечетными номерами у . Здесь обозначено

у =2,4,6,'.,^-2, (12)

С(1) =[С]2-2£. (13)

Займемся системой (11). Введем обозначения Г;=(г(1,у),у(2,у),...,у(ЛГ,-1,у)),

Ф, =(Л2>(1,у)Л>(2,Л-Л>(Лг1 -1-7))

и положим

У]=игр 0 < у < Л^ / 2, Ф, 1<у<^2/2-1,

у(0,у) = у(^,У) = 0, 0 < у < ТУ2 /2. Эти обозначения позволяют записать систему (11) в виде

Ч + С0)К, _ У^ 1<1<мг-\,У0= Ущ = О, (14)

где 2Мг и в силу (12) Ф, = у = 1,2,..., М2-1.

Представим функции ^(/,у), у(/, у) в виде однократных рядов Фурье

• А/Н

У) = I Л3 (0< (У), 0 < /' < ЛА,, 0 < у < Л/ 2,

ЛГ,-1

= Е М'КЧу), 1 </<А^,-1, 1<у<м2-1,

Л/,-1

о < у < л/4,

.,(2)

М4-1

А„=|

(15)

где = А2 = \,2,...,Мг -1. (16)

л/4

Коэффициенты Фурье (/) функции $?(/', у) находятся по формулам

ЛГ, 1

2*г(0 = (^<')= I ^(ьуКЧУ), 1<А2 ¿М2-1, 1</<^,-1.

Из (15) получим для векторов и Фу следующие разложения:

(17)

Подставим (17) в (14), получим

к п мг-\

^ (Ст Е)Укг/Л2)(у') = Е откуда в силу ортонормиро-

*г=1 м2

ванности системы (16) будем иметь к п

(С(|) - 2сое£)К4 , 1<*2 <Л/2-1. Используем (13) и получим:

М, 2 2 -

С"» - 2 cos ^ Е = [С]2 - 2(1 + cos = (С - 2 cos -^Е. Е)(С + 2 cos Ai. £). ,. М2 МА 2 М2 , , 2Л/2

. " '■ fil -Для решения уравнения можно использовать алгоритм . .•

I (C-2cos-^£W = %Zk , \<к,<Мг-\, ... -Т • '^о-

| 2Л/2 2 2 .... : . . •• .

(С + 2cos E)Y. = Wk , "" ' .'■' " '.. " 1 '.'■'•' '

j где вспомогательный вектор Wki имеют компоненты w^ (/). Необходимые

формулы получены.

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

Быстрое преобразование Фурье реализовано как в последовательном, так и в параллельном вариантах метода при помощи алгоритма, предложенного А.А.Самарским и Е.С.Николаевым с затратой 0(N In N) арифметических действий. Эффективность алгоритма БПФ равномерно убывает с увеличением числа вычислителей и растёт при увеличении размерности задачи. Применяем для распараллеливания геометрическую декомпозицию. Так как БПФ выполняется по строкам матрицы данных, это делает необходимым взаимные обмены между вычислителями. Объем передаваемых данных при увеличении числа шагов редукции уменьшается.

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

Рис. 6. Теоретически и практически полученная эффективность реализованного алгоритма метода неполной редукции, / = 1

Далее рассматривается метод неполной редукции для / = 2,3, обобщается для / = /У,, проводится сравнительный анализ количества арифметических действий используемых методов для последовательных и параллельных реализаций.

Анализ оценок для числа действий в последовательном и параллельном варианте метода, содержащем / шагов редукции, дает оптимальное значение при / = 1 или 1 = 2, что показывают и практические результаты, демонстрируя минимальное время выполнения алгоритма для / = 1. Результаты теоретической и практически полученной эффективности алгоритма приведены на рис. 6.

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

Последовательная прогонка

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

Пара п пепьная прогонке на основе суперпозиции

Параллельная геометрическая редукция

Последовательная редукция Последовательная редукция — г Последовательный РАСЯ(1)

Параллельная редукция Хокни Параллельная редукция / Параллельный РАСИ(1)

Последов ательный РАСР(2)

Параллельный РАСК(2)

Скалярные задачи

Векторные задачи

Оболочка, осуществляющая выбор

Рис. 7. Структура библиотека параллельных алгоритмов

Относительной эффективностью алгоритма 1 по отношению к алгоритму 2 назовем величину е = Т2 /Т{, где 7], Т2 - время выполнения алгоритма 1 и 2 при постоянных характеристиках вычислительного устройства.

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

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

ч а

Рис. 8. Относительная эффективность параллельной прогонки и циклической редукции на разном количестве вычислителей

При сравнении алгоритмов методов неполной и полной редукций в качестве базового принят алгоритм полной редукции. На - рис. 9 приведены графики относительной эффективности алгоритма неполной редукции к алгоритму полной редукции для / = 1,2. В области перехода через значение е = 1 на графике алгоритмы будут иметь примерно одинаковые характеристики производительности. Размерность (число узлов ТУ) и число процессоров р на

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

на разном количестве вычислителей

Заключение содержит выводы о работе.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

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

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ

1. Сухинов А.И., Зорина Д.А. Библиотека параллельных алгоритмов для решения многомерных задач водной экологии на кластере распределенных вычислений. // Материалы III Международной конференции по новым технологиям и приложениям современных физико-химических методов для изучения окружающей среды, включая секции молодых Научно-образовательных центров России. - Ростов-на-Дону, 2005, с.73.

2. Сухинов А.И., Зорина Д.А. Параллельная реализация быстрых прямых методов решения сеточных эллиптических уравнений для решения двух и трехмерных задач математической физики. //■ Материалы международной -научной конференции «Современные проблемы прикладной математики и

математического моделирования». - Воронеж, 2005, с.215.

З.Зорина Д. А. Параллельная реализация метода прогонки на кластере распределенных вычислений. // Материалы VI Международной научно-практической конференции «Моделирование, теория, методы и средства»-часть 1 - Новочеркасск: ЮРГТУ, 2006, с. 19.

4. Зорина Д.А. О реализации скалярной циклической редукции на кластере распределенных вычислений. // Труды V Школы-семинара «Математическое моделирование, вычислительная механика и геофизика» для студентов, аспирантов и молодых ученых Юга России. - Ростов-на-Дону, 2006, с.71-73.

5. Сухинов А.И., Зорина Д.А. Параллельная реализация метода циклической редукции для трехточечных векторных уравнений на кластере распределенных вычислений. //«Математическое моделирование и информационные технологии». Сборник научных статей. - Новочеркасск: Изд-во ЮРГТУ (НПИ), 2007, с.10-16.

6. Зорина Д.А. Сравнительный анализ последовательных и параллельных алгоритмов прогонки и редукции. // Альманах современной науки и образования. - Тамбов: «Грамота», 2008. -№1(8), с.76-78.

7. Сухинов А.И., Зорина Д.А., Лапин Д.В. О параллельной реализации FACR(1). // Материалы VIII международной научно-практической конференции «Методы и алгоритмы прикладной математики в технике, медицине и экономике». - Новочеркасск: ЮРГТУ, 2008, с.71-73.

8. Сухинов А.И., Зорина Д.А. Реализация библиотеки параллельных алгоритмов быстрых прямых методов решения сеточных задач для МВС с распределенной памятью. Известия ЮФУ. Технические науки. Тематический выпуск «Управление в социальных и экономических системах». - Таганрог: Изд-во ТТИ ЮФУ, 2008, с. 12-16.

Лично автором в работах [1,2,5] построены быстрые прямые методы решения сеточных задач и реализованы параллельные алгоритмы на кластере распределенных вычислений, получены и проанализированы показатели эффективности алгоритмов; в работе [7] разработан параллельный алгоритм с варьируемым уровнем редукции I; в работе [8] разработана библиотека параллельных алгоритмов для решения вычислительно-трудоемких задач 1ермогидродинамики водоемов на кластерных системах.

Соискатель

Д.А.Зорина

ипография Технологического института Южного федерального университета, аказ № , тираж 100 экз. 2008 г.

ВВЕДЕНИЕ

1. ОСНОВНЫЕ ПОНЯТИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

И ПОСТАНОВКИ СЕТОЧНЫХ ЗАДАЧ

1.1. Параллельные системы и параллельные вычисления

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

1.3. Двумерные схемы расщепления, аппроксимирующие р-мерные (р> 3) уравнения параболического типа, приводящие к двумерным сеточным эллиптическим уравнениям

1.4. Выводы

2. ПОСТРОЕНИЕ И ТЕОРЕТИЧЕСКОЕ ИССЛЕДОВАНИЕ РЕАЛИЗАЦИИ ПРЯМЫХ МЕТОДОВ РЕШЕНИЯ ТРЕХТОЧЕЧНЫХ РАЗНОСТНЫХ УРАВНЕНИЙ

2.1. Алгоритм прогонки А.Н. Коновалова-Н.Н. Яненко решения систем линейных алгебраических уравнений с трехдиагональной матрицей

2.2. Алгоритм циклической скалярной редукции

2.3. Выводы

3. ПОСТРОЕНИЕ И ТЕОРЕТИЧЕСКОЕ ИССЛЕДОВАНИЕ ПАРАЛЛЕЛЬНЫХ РЕАЛИЗАЦИЙ ПРЯМЫХ МЕТОДОВ РЕШЕНИЯ ДВУМЕРНЫХ СЕТОЧНЫХ ЭЛЛИПТИЧЕСКИХ УРАВНЕНИЙ

3.1. Метод полной редукции

3.2. Метод неполной редукции

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

3.4. Выводы

Число научных работ, посвященных параллельным методам решения вычислительно-трудоемких научно-технических задач, составляет многие тысячи. Существенная часть этих работ посвящена построению и исследованию параллельных алгоритмов для решения задач вычислительной алгебры и математической физики. Это обусловлено тем, что к системам алгебраических уравнений, а также к сеточным задачам математической физики, как правило, сводятся все большие научно-технические задачи, особенно в прикладной математике, компьютерной механике, физике, гидродинамике, экологии и т.д. [1].

Вопросам построения и исследования разностных аппроксимаций задач математической физики посвящено множество работ отечественных и зарубежных ученых [2-15]. С другой стороны, происходит все более широкое* применение многопроцессорных систем и параллельных вычислений для решения больших научно-технических задач. Известно, что расширение возможностей в конструировании вычислительной техники всегда оказывало влияние на развитие вычислительной математики — в первую очередь численных методов и численного программного обеспечения.

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

В вычислительной математике разработаны мощные средства построения экономичных алгоритмов решения многомерных задач математической физики, базирующиеся на методе расщепления [18, 19]. Однокомпонентные схемы расщепления, при распараллеливании сохраняют свойство экономичности по числу арифметических операций, но теряют свойство экономичности по числу операций обмена. Оказалось, что в ряде случаев удается построить экономичные в суммарном смысле параллельные алгоритмы решения многомерных задач математической физики, если для аппроксимации использовать двухкомпонентные разностные схемы [7], а также быстрые прямые методы решения двумерных сеточных уравнений, адаптированные для реализации на многопроцессорных системах. Разработкой и исследованием параллельных алгоритмов на ранних этапах развития многопроцессорных систем занимались Е. Валях, Р. Хокни, Дж. Ортега, К. Джессхоуп, Р. Агарвал, Ф. Энслоу, В.В. Воеводин, А.Б. Барский, Н.Н. Миренков, В.А. Вальковский [4, 17, 20-28] и в наши дни - Вл.В.Воеводин, В.П. Гергель, Р.Г. Стронгин и др. [16, 29-34].

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

Прогресс в сетевых технологиях последних лет колоссален, что дает новый виток развития концепции распределенных систем и делает возможным метакомпьютинг или GRID концепцию [35-37], которая предполагает объединять распределенные вычислительные ресурсы глобальной (или какой-либо другой) сети и организовывать процесс вычислений сложных задач.

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

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

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

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

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

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

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

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

- разработка библиотеки параллельных алгоритмов для МВС с распределенной памятью на основе технологии MPI.

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

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

- теория разностных схем;

- методы решения сеточных уравнений, в частности, быстрые прямые методы решения сеточных уравнений;

- методы распараллеливания, основанные на технике domain decomposition.

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

Основными научными результатами диссертационной работы, выносимыми на защиту, являются:

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

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

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

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

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

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

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

Диссертационная работа состоит из трех разделов и заключения.

В первом разделе рассмотрены задачи математической физики, приводящие к многомерным параболическим уравнениям в частных производных. Определен класс задач, допускающих разделение переменных и использования быстрых прямых методов решения. Рассмотрены двумерные схемы расщепления для уравнений параболического типа и определена структура эллиптических сеточных задач, возникающих при разностной аппроксимации параболических уравнений. Определен класс многопроцессорных вычислительных систем, предназначенных для реализации параллельных алгоритмов решения сеточных задач. Сделан выбор средств распараллеливания, используемых при разработке параллельных алгоритмов и программ. Поставлена задача разработки и реализации в виде библиотеки программ на языке C/C++ эффективных универсальных алгоритмов решения указанных задач, предназначенных для реализации на кластерных системах с распределенной памятью на основе технологии MPI. Рассмотрены способы оценки эффективности разрабатываемых алгоритмов параллельных вычислений. Материал данного раздела позволяет перейти к построению и оценке параллельных алгоритмов решения сеточных уравнений, которые рассматриваются во втором и третьем разделах.

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

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

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

Основные результаты докладывались и обсуждались на III Международной конференции по новым технологиям и приложениям современных физико-химических методов для изучения окружающей среды (Ростов-на-Дону, 2005); Международной научной конференции «Современные проблемы прикладной математики и математического моделирования» (Воронеж, 2005); VI Международной научно-практической конференции «Моделирование, теория, методы и средства» (Новочеркасск, 2006); VIII Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (Таганрог, 2006); V Школе-семинаре «Математическое моделирование, вычислительная механика и геофизика» для студентов, аспирантов и молодых ученых Юга России (Ростов-на-Дону, 2006); VII Международной научно-практической конференции «Методы и алгоритмы прикладной математики в технике, медицине и экономике» (Новочеркасск, 2007); Международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы» (Дивноморское, 2007); II Международной научной конференции «Современные проблемы прикладной математики и математического моделирования» (Воронеж, 2007); VIII Международной научно-практической конференции «Методы и алгоритмы прикладной математики в технике, медицине и экономике» (Новочеркасск, 2008).

По теме диссертации опубликованы 4 статьи и тезисы 9 докладов на научных конференциях разного уровня.

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

Диссертация содержит 158 страниц машинописного текста, включая введение, три раздела, заключение, список литературы из 100 наименований на 9 страницах, 3 таблицы, 34 рисунка.

3.4. Выводы

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

Реализованы параллельные алгоритмы метода неполной редукции, с использованием библиотеки MPI. Исследованы особенности реализации алгоритмов быстрого преобразования Фурье в алгоритмах метода неполной редукции и получены оценки объема передаваемых данных и временных затрат.

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

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

150

1. Задачи для суперкомпьютеров, суперкомпьютерные приложения. -http.V/www.parallel.ru/research/challenges.html.

2. Тихонов А.Н., Самарский А.А. Уравнения математической физики. М: Изд-во Московского университета. 6-е изд., 1999. - 798с.

3. Владимиров B.C. Уравнения математической физики. М.: Наука, 1971. -512с.

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

5. Сухинов А.И. Двумерные схемы расщепления и некоторые их приложения. -М.: Изд-во «МАКС Пресс», 2005. 408с.

6. Самарский А.А. Введение в теорию разностных схем. — М.: Наука, 1971. -552с.

7. Самарский А.А., Гулин А.В. Численные методы. М.: «Наука», 1989. - 432с.

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

9. Марчук Г.И. Методы вычислительной математики. М.: «Наука», ГРФМЛ, 1977.-456с.

10. Самарский А.А., Гулин А.В. Устойчивость разностных схем. М.: Наука, 1973.-416с.

11. Самарский А.А. Введение в численные методы. М.: Наука, 1982. - 272с.

12. Вержбицкий В.М. Основы численных методов. М.: Высш.шк., 2002. -840с.

13. Калиткин Н.Н. Численные методы.—М.: Наука, 1978. — 512с.

14. Самарский А.А., Гулин А.В. Численные методы математической физики. -М.: Научный мир, 2000, 316с.

15. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы: Учеб. пособие для физ.-мат. спец. вузов. 2-е изд. - М.; СПб.: Физматлит, 2002. -630с.

16. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: Изд-во «БХВ-Петербург», 2004. - 608с.

17. Воеводин В.В. Математические модели и методы в параллельных процессах. -М.: «Наука», ГРФМЛ, 1986. -296с.

18. Самарский А.А., Вабищевич П.Н. Аддитивные схемы для задач математической физики. М.: Наука, 1999. - 319с.

19. Яненко Н.Н. Метод дробных шагов решения многомерных задач математической физики. Новосибирск: Изд-во СО АН СССР, 1967. - 197с.

20. Вальковский В.А. Распараллеливание алгоритмов и программ. Структурный подход. М.: Радио и связь, 1989. - 176с.

21. Валях Е. Последовательно-параллельные вычисления. Пер. с англ. — М.: «Мир», 1985.-456с.

22. Хокни Р., Джесхоуп К. Параллельные ЭВМ. Архитектура, программирование и алгоритмы. М.: «Радио и связь», 1986. - 392с.

23. Мультипорцессорные системы и параллельные вычисления/Под ред. Ф. Энслоу: Пер. с англ. М.:Мир, 1976. - 326с.

24. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация. — М.: «Радио и связь», 1990. — 256с.

25. Миренков Н.Н. Параллельное программирование для многомодульных вычислительных систем. М.: «Радио и связь», 1989. - 320с.

26. Параллельные вычисления/ Под ред. Г.Родрига. Пер. с англ. под ред. Ю.Г.Дадаева. М.: Наука, 1986. - 213с.

27. Головкин Б.А. Параллельные вычислительные системы. М.: Наука, 1980. -518с.

28. Системы параллельной обработки: Пер. с англ./ Под ред. Д.Ивенса. М.: Мир, 1985.-416с.

29. Богачев К.Ю. Основы параллельного программирования. — М.: Изд-во «БИНОМ. Лаборатория знаний», 2003. 342с.

30. Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. // Учебное пособие. Нижний Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2003. - 184с.

31. Гергель В.П., Стронгин Р.Г. Параллельные методы вычисления для поиска глобально оптимальных решений. // Материалы IV Международного семинара «Высокопроизводительные параллельные вычисления на кластерных системах». Самара, 2004, с.54-59.

32. Valkovskii V.A. Decomposition approach to parallelization and optimization of programs. // Informational technologies and systems. 1998. - V.l, No 1/2.p. 56-63.

33. Воеводин B.B. Информационная структура алгоритмов и программ. — М.: Изд-во МГУ, 1997. 139с.

34. EGEE::PNPI::NW::GRID технологии::Что такое GRID. -http://egee.pnpi.nw.m/cgi/index.cgi?ll=5&12=l.

35. The Globus Alliance. http://www.globus.org/.

36. Jose Cardoso Cunha, Omer Rana Grid Computing: Software Environments and Tools. Birkhauser, 2006. - 345p.

37. Яненко H.H. Вопросы модульного анализа и параллельных вычислений в задачах математической физики. // Избранные труды. М.: Наука, 1991. — с.292-296.

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

39. Xu Z., Hwang K. Scalable Parallel Computing Technology, Architecture, Programming. McGraw-Hill, Boston, 1998.

40. Шпаковский Г.И., Серикова H.B. Программирование для многопроцессорных систем в стандарте MPI. Мн.: БГУ, 2002. - 323с.

41. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. -М.: Мир, 1978.-453с.

42. Букатов А.А, Дацюк В.Н., Жегуло А.И. Программирование многопроцессорных вычислительных систем. Ростов-на-Дону: Изд-во, «ЦВВР», 2003. - 208с.

43. MPI: A Message-Passing Interface Standard. Message Passing Interface Forum. — Version 1.1. 1995. http://www-unix.mcs.anl.gov/mpi.

44. High Performance Fortran Language Specification. High Performance Fortran Forum. Version 2.0. 1997. - http://hpff.rice.edu/.

45. ADAPTOR. High Performance Fortran (HPF) Compilation System. -http://www.scai.fi-aunhofer.de/EP-CACHE/adaptor/www/adaptorhome.html.

46. Коновалов H.A., Крюков B.A., Погребцов A.A., Сазанов IO.JI. C-DVM -язык разработки мобильных параллельных программ. // Программирование. -1999, № 1, с.20-28.

47. Адуцкевич Е.В. Организация обмена данными на параллельных компьютерах с распределенной памятью. // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы пятого Международного научно-практического семинара. -2005, с. 12.

48. Кузюрин Н.Н., Фрумкин М.А. Параллельные вычисления: теория и алгоритмы // Программирование. — 1991. — №2. с.З—19.

49. Антонов А.С., Воеводин Вл.В. Эффективная адаптация последовательных программ для современных векторно-конвейерных и массивно-параллельных супер-ЭВМ. // Программирование. 1996. -№4. - с.37-51.

50. Воеводин В.В. Математические основы параллельных вычислений. -М.: МГУ, 1991.-345с.

51. Бицадзе А.В., Калиниченко Д.Ф. Сборник задач по уравнениям математической физики. М.: «Наука», ГРФМЛ, 1985. - 312с.

52. Арсенин В.Я. Методы математической физики и специальные функции. // Учебное пособие. -М.: Наука, 1984. -383с.

53. Годунов С.К., Рябенький B.C. Разностные схемы. 2-е изд. М.: Наука, 1977. -439с.

54. Самарский А.А. Теория разностных схем. М.: Наука, 1983. 616с.

55. Коновалов А.Н. Введение в вычислительные методы линейной алгебры. -Новосибирск: ВО «Наука», Сибирская издательская фирма, 1993. 159с.

56. Automatically Tuned Linear Algebra Software (ATLAS). -http://math-atlas.sourceforge.net/.

57. Aztec. http://www.cs.sandia.gov/CRF/aztecl .html.

58. BlockSolve95. Sofware for the efficient solution of large, sparse linear systems on massively parallel computers. -http://www-unix.mcs.anl.gov/sumaa3d/BlockSolve/.

59. NAMD Scalable Molecular Dynamics. -http://www.ks.uiuc.edu/Research/namd/.

60. ARPACK Software. http://www.caam.rice.edu/software/ARPACK/.

61. PBLAS. http://www.netlib.org/scalapack/litml/pblas qref.html.

62. PETSc: Home page. http://www-unix.mcs.anl.gov/petsc/petsc-as/

63. PLAPACIC: Parallel Linear Algebra Package. -http://www.cs.utexas.edu/users/plapack/.

64. ScaLAPACK. http://www.netlib.org/scalapack/.

65. Tabe Т., Stout Q. The use of the MPI communication library in the NAS parallel benchmark. // Tech. Rep. CSE-TR-3 86-99, Department of Computer Science, University of Michigan, Nov 1999, pp.57-64.

66. Турчак Л.И. Основы численных методов. М.: Наука, 1987. ~ 320с.

67. Wang Н.Н. A parallel method for tridiagonal equations. // ACM Trans.Math. Soft., 1981, vol. 7, no. 2, pp.170-183.

68. Swarztrauber P. A parallel algorithm for solving general tridiagonal equations. // Mathematics of Computation, 1979, vol. 33, no. 145, pp.185-199.

69. Ketelsen C. Ail efficient, numerically stable, and scalable parallel tridiagonal solver in nuclear weapons highlights. Los Alamos National Laboratory. (LALP-07-041), 2007.

70. Kadalbajoo M.K., Rao A.A. Parallel group explicit method for two-dimensional parabolic equations. // Parallel Computing, 1997, vol. 23, number 6, pp. 649-666.

71. Eunice E. Santos. Optimal and efficient parallel tridiagonal solvers using direct methods. // The Journal of Supercomputing, 2004, Vol. 30, Issue 2, pp. 97-115.

72. Комолкин A.B., Немнюгин C.A., Программирование для высокопроизводительных ЭВМ.-Учебно-методическое пособие. СПб: СпбГУ, 1998, 52с.

73. Bischof Н., Gorlatch S. Parallelizing a tridiagonal system solver by adjustment to a homomorphic skeleton. // in proc. of The Fourth International Workshop on Advanced Parallel Processing Technologies. Ilmenau, 2001.

74. Зорина Д.А. Параллельная реализация метода прогонки на кластере распределенных вычислений. // Материалы VI Международной научнопрактической конференции «Моделирование, теория, методы и средства» -часть 1 Новочеркасск: ЮРГТУ, 2006, с. 19.

75. Годунов С.К. Решение систем линейных уравнений. Новосибирск: Наука, 1980.- 177с.

76. Зорина Д.А. Сравнительный анализ последовательных и параллельных алгоритмов прогонки и редукции. // Альманах современной науки и образования. Тамбов: «Грамота», 2008. - №1(8), с.76-78.

77. Воеводин В.В. Вычислительные основы линейной алгебры. — М.: «Наука», ГРФМЛ, 1977.-304с.

78. Ситкевич Т.А., Сюрин В.Н. Параллельные вычислительные среды. // Уч.-метод. пособие Гродно: ГрГУ, 2001. - 114с.

79. Вентцель Е.С. Теория вероятностей: Учеб. для вузов. М.: Высш.шк., 2001.-575с.

80. Колемаев В.А., Калинина В.Н. Теория вероятностей и математическая статистика: Учебник. -М.: Инфра-М, 1997. 302с.

81. Воеводин Вл.В., Жуматий С.А. Вычислительное дело и кластерные системы. М.: Изд-во МГУ, 2007. - 150с.

82. Воеводин В.В. Линейная алгебра. М.: «Наука», ГРФМЛ, 1980, 400с.

83. Корнеев В.В. Параллельные вычислительные системы. — М.: «Гелиос» АРВ, 2004.-512с.

84. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. - 960с.

85. Сухинов А.И., Зорина Д.А., Лапин Д.В. О параллельной реализации . FACR(l). // Материалы VIII международной научно-практической конференции «Методы и алгоритмы прикладной математики в технике, медицине и экономике». Новочеркасск: ЮРГТУ, 2008, с.71-73.

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

87. Zhang W., Chen Z, Glowinski R, Tong W. Linux Cluster Based Parallel Simulation System of Power System. // Current Trends in High Performance Computing and Its Applications, Berlin Heidelberg, 2005, pp. 311-316.