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