Разработка и исследование экономичных алгоритмов решения сеточных задач на кластере распределенных вычислений тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Зорина, Дарья Алексеевна

• Зорина, Дарья Алексеевна
• кандидат технических наук
• 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

Список литературы диссертационного исследования кандидат технических наук Зорина, Дарья Алексеевна, 2008 год

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.