Разработка и исследование экономичных алгоритмов решения сеточных задач на кластере распределенных вычислений
На правах рукописи
Зорина Дарья Алексеевна
РАЗРАБОТКА И ИССЛЕДОВАНИЕ ЭКОНОМИЧНЫХ
АЛГОРИТМОВ РЕШЕНИЯ СЕТОЧНЫХ ЗАДАЧ
НА КЛАСТЕРЕ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛЕНИЙ
Специальность:
05.13.18 «Математическое моделирование, численные методы и
комплексы программ»
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата технических наук
Таганрог – 2008
Работа выполнена в Технологическом институте Южного федерального университета на кафедре высшей математики.
Научный руководитель: доктор физико-математических наук,
профессор,
Сухинов Александр Иванович
Официальные оппоненты: доктор технических наук, доцент,
Боженюк Александр Витальевич, г. Таганрог
кандидат технических наук, доцент,
Никифоров Александр Николаевич, г. Новочеркасск
Ведущая организация: СевКавГТУ, г. Ставрополь
Защита состоится «25» декабря 2008 г. в 14-20 на заседании диссертационного совета Д 212.208.22 при Технологическом институте Южного федерального университета по адресу: пер. Некрасовский, 44, ауд. Д-406, ГСП17А, г. Таганрог, Ростовская область, 347928.
С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: ул. Пушкинская, 148, г. Ростов-на-Дону, 3444000.
Автореферат разослан «21» ноября 2008 г.
Ученый секретарь
диссертационного совета
доктор технических наук, профессор А.Н. Целых
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы.
К сеточным задачам математической физики и системам алгебраических уравнений, возникающим при их решении, как правило, сводятся все большие научно-технические задачи, особенно в прикладной математике, гидродинамике, экологии. Особенности адаптации широко известных численных алгоритмов к вычислениям на многопроцессорных вычислительных системах (МВС) все еще слабо освещены в литературе. Основной причиной сложившейся ситуации была быстрая смена архитектуры МВС. В настоящее время в связи с приближением к физическим пределам быстродействия вычислительной и коммуникационной аппаратуры ситуация стабилизировалась и появилась возможность сосредоточиться на исследовании алгоритмов и концепций параллельных вычислений.
В вычислительной математике разработаны мощные средства построения экономичных алгоритмов решения многомерных задач математической физики, базирующиеся на методе расщепления. Однокомпонентные схемы расщепления, при распараллеливании сохраняют свойство экономичности по числу арифметических операций, но теряют свойство экономичности по числу операций обмена. Оказалось, что в ряде случаев удается построить экономичные в суммарном смысле параллельные алгоритмы решения многомерных задач математической физики, если для аппроксимации использовать двухкомпонентные разностные схемы, а также быстрые прямые методы решения двумерных сеточных уравнений, адаптированные для реализации на МВС.
При разработке параллельных программ для МВС требуется, чтобы структура алгоритма и программы соответствовала особенностям архитектуры вычислительной системы. Только в этом случае может быть достигнуто максимальное значение показателей производительности. Выбор системы с распределенной памятью в качестве архитектуры МВС для решения больших сеточных задач обусловлен такими преимуществами как наилучшее соотношение производительность/цена, гибкая конфигурируемость в зависимости от имеющегося бюджета и потребностей в вычислительной мощности.
Тема диссертационной работы является актуальной, так как она посвящена разработке параллельных алгоритмов быстрых прямых методов решения сеточных уравнений, получаемых в результате использования семейства двумерных схем расщепления, которые имеют лучшую точность и требуют меньших временных затрат на обмены информацией при реализации на многопроцессорных вычислительных системах с распределенной памятью.
Цель диссертационной работы состоит в развитии методов эффективного решения многомерных задач математической физики на системах распределенных вычислений.
Основные задачи исследования. Для достижения поставленной цели решены следующие задачи:
- разработка методов теоретической оценки параллельных алгоритмов решения сеточных задач с учетом вычислительных затрат и затрат на операции обмена;
- разработка параллельных алгоритмов быстрых прямых методов решения систем скалярных трехточечных уравнений, требующих минимальных суммарных временных затрат, включающих вычислительные затраты и затраты на обмены информацией;
- разработка параллельных алгоритмов быстрых прямых методов решения систем векторных трехточечных уравнений, требующих минимальных суммарных временных затрат;
- разработка библиотеки параллельных алгоритмов для МВС с распределенной памятью на основе технологии 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 Boltzmann Models). В ряде случаев использование вышеупомянутых методов позволяет получить физически более мотивированное решение исходной задачи, обладающее лучшей реальной точностью по сравнению с решением методом конечных разностей. Однако универсальным методом приближенного решения дифференциальных уравнений, применимым для широкого класса уравнений математической физики, является метод конечных разностей (или метод сеток).
Пусть область изменения аргумента 
есть отрезок 
. Разобьем отрезок 
точками 
, 
, 
, на 
равных частей длины 
. Множество точек 
называется разностной сеткой на отрезке 
и обозначается 
, а число 
– расстояние между точками (узлами) сетки – называется шагом сетки.
Функцию 
дискретного аргумента 
, 
, называют сеточной функцией, определенной на сетке 
. Всякой непрерывной функции 
можно поставить в соответствие сеточную функцию 
.
Пусть область изменения аргументов 
есть прямоугольник 
. Сеткой в прямоугольнике 
называется множество узлов 
с координатами 
, 
и обозначается 
.
Непрерывной функции 
, где 
– точка из 
, будем ставить в соответствие сеточную функцию 
.
Аналогично вводится понятие пространственной сетки 
, в которой шаг 
выбирается по координатным направлениям.
Оператор 
, преобразующий сеточную функцию 
в сеточную функцию 
, называют сеточным или разностным оператором. Дифференциальный оператор 
, заданный в классе функций непрерывного аргумента, может быть приближенно заменен (аппроксимирован) разностным оператором 
, заданным на сеточных функциях. Для этого каждая из производных заменяется разностным отношением, содержащим значения сеточной функции в нескольких узлах сетки.
Рассмотрим практически важные задачи математической физики, приводящие к многомерным параболическим уравнениям. Система дифференциальных уравнений в частных производных параболического типа описывает процессы типа диффузии или распространения тепловой энергии, где скорость процесса зависит от интенсивности распределенных полей. Это класс наиболее простых динамических уравнений, для которых хорошо отработаны вычислительные задачи в применении к нестационарным процессам, в том числе протекающим в сплошных средах с анизотропными свойствами. Однако и для параболических уравнений обычно не получается наглядных и явных вычислительных схем (даже в одномерных случаях), но зато и не возникает непреодолимых трудностей с вычислительной устойчивостью или аппроксимационной гладкостью пространственных решений.
Рассмотрим задачу для трехмерного уравнения теплопроводности с постоянными коэффициентами:
1 2
с начальными и граничными условиями:
34
5 6
где 
– параллелепипед с размерами 
, 
, 
;
– граница области 
, 
, 
– начальный момент времени.
В реальных задачах коэффициент теплопроводности может меняться по объему, что приводит к постановке задачи (1) с переменными коэффициентами, т.е.
Задача (1) – (3) может быть обобщена на 
-мерный случай.
Рассмотрим трехмерное уравнение теплопроводности в случае разделяющихся переменных. Пусть поставлена смешанная задача Коши для трехмерного уравнения теплопроводности
7 8
910
11 12
где Г – граница области 
, 
, П – двумерная (плоская) сеточная область ступенчатой формы, допускающая построение сетки, равномерной, по крайней мере, по одному направлению. В отношении входных данных задачи будем предполагать, что они таковы, что обеспечивают существование и единственность решения задачи (4) – (6). Будем считать, что коэффициенты уравнения (4) 
и 
зависят только от одной переменной, т.е. 
, 
, или, в общем случае, 
, 
, 
.
Возможные обобщения постановки задачи заключаются в следующем: область 
может представлять собой связное объединение областей указанного выше типа; на границе области по одному из направлений возможно задание граничных условий 3-го рода. Тогда в области 
построим равномерную пространственную сетку 
с шагами 
в направлении координатных направлений 
соответственно. Пусть 
– узлы сетки, граничные по направлению 
. Аппроксимируем задачу (4) – (6) локально-двумерной схемой. Используется известная аппроксимация дифференциальных выражений
соответственно разностными
.
Рассмотрим частный случай 
, 
.
Тогда имеем разностную задачу
13 14
,
15 16
Построенная схема равномерно устойчива по начальным и граничным данным и по правой части, обладает свойством суммарной аппроксимации, равномерно сходится к решению задачи (4) – (6).
Двумерная разностная задача (7), (8), решаемая на каждом временном слое, допускает использование быстрых прямых методов решения сеточных эллиптических задач и их параллельных реализаций.
В качестве системы для реализации вычислительных алгоритмов выбран кластер распределенных вычислений с топологией в виде полного графа. Каждый узел (процессор) характеризуется производительностью 3ГГц, объемом оперативной памяти 1Гб, работающий под управлением операционной системы ASPLinux на ядре 2.4.20-9asp. Предложено использовать методы распараллеливания, основанные на технике domain decomposition. Разработан метод определения характеристик параллельного алгоритма.
Для определения времени выполнения параллельного алгоритма необходимо построить модель выполнения алгоритма в виде ориентированного графа, вершинами которого являются отдельные арифметические операции или блоки операций, выполняемых непрерывно на одном процессоре, а дуги представляют собой связи между вычислительными блоками. Далее определяется максимальная длина вычислительного пути алгоритма с учетом блокировок процессоров при выполнении обменов данными. На выделенном пути максимальной длины подсчитывается количество обобщенных арифметических операций, операций обмена данными и объемы передаваемых данных. Для рассматриваемой вычислительной системы определяется соотношение скорости обмена данными и времени выполнения обобщенной арифметической операции. На основе полученных данных рассчитываются теоретические значения ускорения и эффективности алгоритма.
Каждый параллельный алгоритм оценивается по двум параметрам – ускорению 
и эффективности 
, которые определяются по формулам
где 
– время решения исходной задачи на одном процессоре, 
– время решения исходной задачи по параллельному алгоритму на 
процессорах. Так как в системе с распределенной памятью присутствуют коммуникации, то время выполнения коммуникаций входит в общее время выполнения параллельного алгоритма, поэтому оценки ускорения и эффективности необходимо скорректировать. Введем ряд коэффициентов, характеризующих быстродействие вычислителей и коммуникаций конкретной системы и избавляющих нас от необходимости знать протоколы обмена данными.
Коэффициент эффективности передачи 
равен отношению скорости передачи полезной информации, вычисляемой как 
, где 
– время передачи сообщения размером 
байт, к скорости передачи данных между узлами 
. С его помощью можно получить время передачи, зная длину этой передачи в байтах или количество арифметических операций, выполняемых за передачу. Длительность передачи определяется как: 
, количество арифметических операций выполняемых за передачу: 
, где 
– объем полезной информации в сообщении, 
– коэффициент, характеризующий число обобщенных арифметических операций, выполняемых за время передачи 1 байт между узлами кластера.
Значение коэффициента эффективности передачи 
можно аппроксимировать функциональной зависимостью: 
, где 
– длина сообщения в байт, 
– объем служебной информации в пакете, 
– коэффициент, отражающий время на подготовку посылки. Тогда ускорение и эффективность алгоритма можно записать:
где 
– количество арифметических операций последовательного алгоритма, 
– количество арифметических операций параллельного алгоритма, 
– время выполнения одной обобщенной арифметической операции, 
– количество исполняемых узлов, 
– время, затраченное на обмены данных 
.
Для коротких сообщений справедлива также формула
,
где 
– объем служебных данных в каждом из пересылаемых пакетов.
Во втором разделе разработаны параллельные алгоритмы методов прогонки Коновалова-Яненко и циклической скалярной редукции, предназначенные для решения систем линейных алгебраических уравнений с трехдиагональной матрицей на кластерных системах с распределенной памятью. Получены оценки эффективности алгоритмов на основе анализа числа выполняемых операций. Выполнена практическая реализация разработанных алгоритмов на кластере распределенных вычислений и получены экспериментальные оценки, позволяющие сделать вывод об эффективности и целесообразности использования алгоритмов на МВС с распределенной памятью, где 
(см. рис. 1, 2).
Для исследования параллельного алгоритма метода прогонки была составлена программа для кластера распределенных вычислений. Предполагая использование МВС с 
процессорами, в реализованном алгоритме вводилось равномерное линейное разбиение множества узлов сетки 
Рис. 1. Практически и теоретически полученная эффективность
параллельного алгоритма метода Коновалова-Яненко
Рис. 2. Практически и теоретически полученная эффективность
параллельного алгоритма метода циклической редукции
на связные подмножества 
соответствующие разбиению вектора неизвестных по процессорам. В результате такого разбиения процессор с номером 
обрабатывает 
точек. Реализованный параллельный алгоритм основан на принципе суперпозиции решений систем линейных алгебраических уравнений.
Для достижения максимальной эффективности на двух узлах, используется реализованный алгоритм метода встречных прогонок.
В третьем разделе разработаны параллельные алгоритмы методов решения двумерных сеточных эллиптических уравнений: метода полной редукции, метод Фурье, как составная часть алгоритма неполной редукции (метода типа 
), метода неполной редукции. Получены теоретические и экспериментальные оценки эффективности алгоритмов с учетом затрат времени на обмены и получены области эффективности алгоритмов. Показано, что максимальная эффективность параллельной реализации комбинированного алгоритма неполной редукции может быть достигнута путем выбора количества шагов редукции, предшествующих разложению по базису, и приведены соответствующие зависимости. Разработана библиотека параллельных алгоритмов для эффективного решения больших сеточных задач, в которой решается проблема выбора оптимальной параллельной реализации для данной задачи, что определяется числом узлов сетки, имеющимся количеством процессоров 
и коэффициентами 
и 
.
Основным источником задач, решаемых методом полной редукции, являются разностные аппроксимации двумерных задач математической физики, например, разностная задача Дирихле для уравнения Пуассона в прямоугольнике или неявная разностная схема для двумерного уравнения теплопроводности. Метод полной редукции позволяет получать решения задач с затратой 
арифметических действий, 
– число узлов сетки по каждому направлению.
Рис. 3. Способ исключения неизвестных векторов из системы неизвестных
Рассмотрим первую краевую задачу для трехточечных векторных уравнений, решение которых можно найти по методу полной редукции. Требуется найти решение уравнения
17 18
где 
– вектор неизвестных, 
– квадратная невырожденная матрица, 
– заданная правая часть, 
есть степень двойки, т. е. 
– целое число.
В основе метода лежит специальный способ исключения неизвестных векторов из системы (9), продемонстрированный на рис. 3 для 
.
Каждый шаг процесса исключения уменьшает число неизвестных векторов, на последнем уровне редукции останется одно уравнение для вектора 
. Обратный ход метода заключается в последовательном нахождении неизвестных 
сначала с номерами 
, кратными 
, затем 
и т.д.
Для избежания таких трудоемких операций как обращение полных матриц, умножение матрицы на вектор используются матричные полиномы Чебышева первого и второго рода, которые помогают свести алгоритм к операциям сложения векторов, умножения вектора на число и обращения трехдиагональных матриц. Для обращения трехдиагональных матриц используется метод последовательной прогонки.
При параллельной реализации метода входная информация, то есть двумерный массив 
, разрезается на «вертикальные» полосы и распределяется по узлам кластера (см. рис. 4). В процессор с номером 
, где 
– количество узлов кластера, 
загружаются элементы исходных массивов со значениями индексов 
. Далее начинаются вычисления по алгоритму метода на отдельных процессорах. Вычисления на очередном уровне редукции начинаются с передач данных между процессорами кластера.
Рис. 4. Прямой ход метода полной редукции на кластере
а) с двумя узлами
, б) с четырьмя узлами
Результаты реализованного параллельного алгоритма метода полной редукции приведены на рисунке 5.
Рис. 5. Практически и теоретически полученная эффективность
параллельного алгоритма метода полной редукции
Метод неполной редукции позволяет получать решения задач с затратой 
арифметических действий, 
– число узлов сетки по каждому направлению. Метод разложения в однократный ряд позволяет ограничиться вычислением только двух сумм Фурье с затратой 
действий и решением серии трехточечных краевых задач за 
действий. Дальнейшее усовершенствование метода разделения переменных возможно по пути уменьшения числа слагаемых в вычисляемых суммах при сохранении возможности использовать алгоритм быстрого преобразования Фурье. Достигнуть этой цели можно, комбинируя метод разложения в однократный ряд и метод редукции. Рассмотрим задачу Дирихле на прямоугольной сетке 
.
. 19 20
Введем вектор неизвестных 
следующим образом:
и определим вектор правых частей 
формулой 
Тогда разностную задачу (10) можно записать в виде следующей системы векторных уравнений:
где квадратная трехдиагональная матрица 
определяется равенствами 
Пусть 
Напомним, что первый шаг процесса исключения в методе полной редукции состоит в выделении «укороченной» системы для неизвестных 
с четными номерами 
21 22
и уравнений 
для определения неизвестных с нечетными номерами 
. Здесь обозначено
23 24
25 26
Займемся системой (11). Введем обозначения
и положим
Эти обозначения позволяют записать систему (11) в виде
27 28
где 
и в силу (12) 
Представим функции 
,
в виде однократных рядов Фурье
29 30
где 
31 32
Коэффициенты Фурье 
функции 
находятся по формулам
Из (15) получим для векторов 
и 
следующие разложения:
33 34
Подставим (17) в (14), получим
откуда в силу ортонормированности системы (16) будем иметь
Используем (13) и получим:
Для решения уравнения можно использовать алгоритм
где вспомогательный вектор 
имеют компоненты 
. Необходимые формулы получены.
Параллельный алгоритм состоит из двух основных этапов: решение системы уравнений методом прогонки и быстрое преобразование Фурье. В зависимости от количества шагов редукции количество указанных этапов изменяется.
Быстрое преобразование Фурье реализовано как в последовательном, так и в параллельном вариантах метода при помощи алгоритма, предложенного А.А.Самарским и Е.С.Николаевым с затратой 
арифметических действий. Эффективность алгоритма БПФ равномерно убывает с увеличением числа вычислителей и растёт при увеличении размерности задачи. Применяем для распараллеливания геометрическую декомпозицию. Так как БПФ выполняется по строкам матрицы данных, это делает необходимым взаимные обмены между вычислителями. Объем передаваемых данных при увеличении числа шагов редукции уменьшается.
В основе алгоритма метода прогонки лежат вычисления по столбцам матрицы данных, что идеально для распараллеливания с использование геометрической декомпозиции, так как входные данные «разрезаются» на начальном этапе выполнения метода по вычислителям.
Рис. 6. Теоретически и практически полученная эффективность
реализованного алгоритма метода неполной редукции, 
Далее рассматривается метод неполной редукции для 
, обобщается для 
, проводится сравнительный анализ количества арифметических действий используемых методов для последовательных и параллельных реализаций.
Анализ оценок для числа действий в последовательном и параллельном варианте метода, содержащем 
шагов редукции, дает оптимальное значение при 
или 
, что показывают и практические результаты, демонстрируя минимальное время выполнения алгоритма для 
. Результаты теоретической и практически полученной эффективности алгоритма приведены на рис. 6.
Разработанные алгоритмы реализованы в виде структурированной библиотеки программ(см. рис. 7), основная цель которой – максимально эффективно решить поставленную задачу, зная ее размерность и параметры кластера распределенных вычислений. Для выбора оптимального алгоритма на основе данных о входной задаче была разработана оболочка, которая производит определение характеристик используемой вычислительной системы для вычисления коэффициента 
и последующий анализ по выбору оптимального алгоритма решения задачи.
Рис. 7. Структура библиотека параллельных алгоритмов
Относительной эффективностью алгоритма 1 по отношению к алгоритму 2 назовем величину 
, где 
– время выполнения алгоритма 1 и 2 при постоянных характеристиках вычислительного устройства.
Выполнен сравнительный анализ разработанных алгоритмов и определены области эффективного применения каждого алгоритма в зависимости от характеристик быстродействия вычислительной системы. На рис. 8 приведены графики относительной эффективности параллельных алгоритмов прогонки и редукции к последовательному алгоритму прогонки. В качестве базового рассматривается алгоритм последовательной прогонки для того, чтобы можно было провести сравнительный анализ параллельных алгоритмов и определить какой из них имеет оптимальное время решения задачи, для какой размерности и количества вычислителей. Последовательная прогонка была выбрана по причине минимального времени решения задачи по сравнению с алгоритмом последовательной циклической редукции.
Из графиков видно, что параллельная прогонка обладает лучшим ускорением по сравнению с параллельной редукцией, хотя их показатели и очень близки. В интервале размерности задачи 
оптимальное ускорение достигается на двух вычислителях, после этого интервала размерности – на максимальном количестве вычислителей. Для данной системы 
.
Рис. 8. Относительная эффективность параллельной прогонки
и циклической редукции на разном количестве вычислителей
При сравнении алгоритмов методов неполной и полной редукций в качестве базового принят алгоритм полной редукции. На рис. 9 приведены графики относительной эффективности алгоритма неполной редукции к алгоритму полной редукции для 
. В области перехода через значение 
на графике алгоритмы будут иметь примерно одинаковые характеристики производительности. Размерность (число узлов 
) и число процессоров 
на плоскости параметров 
определяет выбор того или иного алгоритма при заданных коэффициентах быстродействия вычислительной системы. Для системы с большим значением 
эта область смещается в сторону увеличения размерности задачи, для системы с меньшим значением 
– в сторону уменьшения размерности задачи. С учетом характеристик МВС и размерности задачи, осуществляется выбор оптимального алгоритма для решения задачи.
Рис. 9. Относительная эффективность алгоритма неполной редукции
на разном количестве вычислителей
Заключение содержит выводы о работе.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ
1. Предложен способ теоретической оценки производительности прямых параллельных алгоритмов решения сеточных задач математической физики, дающие оценки ускорения и эффективности, хорошо согласующиеся с реальными значениями.
2. Получена методика учета временных затрат на коммуникации при выполнении параллельного алгоритма на МВС с распределенной памятью, использующая экспериментально определяемые коэффициенты быстродействия.
3. Разработаны и реализованы параллельные алгоритмы решения систем скалярных трехточечных уравнений, основанные на прогонке и циклической редукции, и теоретически определены границы эффективного их применения в зависимости от размерности задачи, количества вычислителей и соотношения между временными затратами на выполнение операций обмена и вычислительных операций.
4. Разработаны и реализованы параллельные алгоритмы решения систем векторных трехточечных уравнений, основанные на векторной редукции и методе неполной редукции, и теоретически определены границы их эффективного применения в зависимости от размерности задачи, количества вычислителей и соотношения между временными затратами на выполнение операций обмена и собственно вычислительных операций.
5. Реализована библиотека параллельных программ эффективного решения сеточных уравнений методами прогонки на основе суперпозиции, скалярной редукции, векторной редукции, неполной редукции на кластере распределенных вычислений.
ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ
1. Сухинов А.И., Зорина Д.А. Библиотека параллельных алгоритмов для решения многомерных задач водной экологии на кластере распределенных вычислений. // Материалы III Международной конференции по новым технологиям и приложениям современных физико-химических методов для изучения окружающей среды, включая секции молодых Научно-образовательных центров России. – Ростов-на-Дону, 2005, с.73.
2. Сухинов А.И., Зорина Д.А. Параллельная реализация быстрых прямых методов решения сеточных эллиптических уравнений для решения двух и трехмерных задач математической физики. // Материалы международной научной конференции «Современные проблемы прикладной математики и математического моделирования». – Воронеж, 2005, с.215.
3. Зорина Д.А. Параллельная реализация метода прогонки на кластере распределенных вычислений. // Материалы VI Международной научно-практической конференции «Моделирование, теория, методы и средства» – часть 1 – Новочеркасск: ЮРГТУ, 2006, с.19.
4. Зорина Д.А. О реализации скалярной циклической редукции на кластере распределенных вычислений. // Труды V Школы-семинара «Математическое моделирование, вычислительная механика и геофизика» для студентов, аспирантов и молодых ученых Юга России. – Ростов-на-Дону, 2006, с.71-73.
5. Сухинов А.И., Зорина Д.А. Параллельная реализация метода циклической редукции для трехточечных векторных уравнений на кластере распределенных вычислений. //«Математическое моделирование и информационные технологии». Сборник научных статей. – Новочеркасск: Изд-во ЮРГТУ (НПИ), 2007, с.10-16.
6. Зорина Д.А. Сравнительный анализ последовательных и параллельных алгоритмов прогонки и редукции. // Альманах современной науки и образования. – Тамбов: «Грамота», 2008. – №1(8), с.76-78.
7. Сухинов А.И., Зорина Д.А., Лапин Д.В. О параллельной реализации FACR(l). // Материалы VIII международной научно-практической конференции «Методы и алгоритмы прикладной математики в технике, медицине и экономике». – Новочеркасск: ЮРГТУ, 2008, с.71-73.
8. Сухинов А.И., Зорина Д.А. Реализация библиотеки параллельных алгоритмов быстрых прямых методов решения сеточных задач для МВС с распределенной памятью. Известия ЮФУ. Технические науки. Тематический выпуск «Управление в социальных и экономических системах». – Таганрог: Изд-во ТТИ ЮФУ, 2008, с.12-16.
Лично автором в работах [1, 2, 5] построены быстрые прямые методы решения сеточных задач и реализованы параллельные алгоритмы на кластере распределенных вычислений, получены и проанализированы показатели эффективности алгоритмов; в работе [7] разработан параллельный алгоритм с варьируемым уровнем редукции 
; в работе [8] разработана библиотека параллельных алгоритмов для решения вычислительно-трудоемких задач термогидродинамики водоемов на кластерных системах.
Соискатель Д.А.Зорина
Типография Технологического института Южного федерального университета, заказ №, тираж 100 экз. 2008 г.
