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

Число научных работ, посвященных параллельным методам решения вычислительно-трудоемких научно-технических задач, составляет многие тысячи. Существенная часть этих работ посвящена построению и исследованию параллельных алгоритмов для решения задач вычислительной алгебры и математической физики. Это обусловлено тем, что к системам алгебраических уравнений, а также к сеточным задачам математической физики, как правило, сводятся все большие научно-технические задачи, особенно в прикладной математике, компьютерной механике, физике, гидродинамике, экологии и т. д. [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. Исследованы особенности реализации алгоритмов быстрого преобразования Фурье в алгоритмах метода неполной редукции и получены оценки объема передаваемых данных и временных затрат.

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

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