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

• Овчаренко, Ольга Игоревна
• кандидат технических наук
• 1992

Оглавление диссертации кандидат технических наук Овчаренко, Ольга Игоревна

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ МЕТОДА

ЦИКЛИЧЕСКОЙ РЕДУКЦИИ

1.1. Постановка задачи. Основные понятия

1.1.1. Область применения быстрых прямых методов

1.1.2. Характеристики параллельных архитектур и алгоритмов

1.2. Параллельные алгоритмы метода циклической редукции

1.2.1. Параллельная реализация метода циклической редукции

Ф для решения систем скалярных трехточечных уравнений

1.2.2. Параллельная реализация метода циклической редукции для решения систем векторных трехточечных уравнений

1.3. Сравнение параллельных алгоритмов

1.4. В ы в о д ы

2. РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ МЕТОДА

РАЗЛОЖЕНИЯ ПО БАЗИСУ

2.1. Основные этапы метода разложения по базису

2.2. Алгоритмы быстрого преобразования Фурье

2.3. Параллельные алгоритмы метода разложения по базису

2.4. Сравнение характеристик параллельных алгоритмов

2.5. Выводы

3. РАЗРАБОТКА ПАРАЛЛЕЛЬШХ 5,А0Н(Ъ)-АЛГ0Р1ШЮВ

3.1. Основные этапы комбинированного метода

Фурье-алгоритма и редукции

3.2. Построение параллельных РАСЩЬ) - алгоритмов

3.3. Оптимизация РАСН(Ь) - алгоритмов

3.4. Выводы

4. РАЗРАБОТКА ПАРАЛЛЕЯЬШХ АЛГОРИТМОВ БЫСТРЫХ

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

4.1. Параллельные алгоритмы метода циклической редукции

4.2. Параллельные алгоритма метода разлогения по базису

4.3. Параллельные РАЙ*(Ь)-алгоритмы

4.4. фактическое использование результатов диссертационной работы

4.4.1. Реализация быстра прямых методов на вычислительном комплексе ЕС 1061 - ЕС 2703

4.4.2. Реализация быстрых прямых методов на транспьютерной системе

4.4.3. Использование полученных результатов в библиотеках

• параллельных алгоритмов

4.5. Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ 1

ПРИЛОЖЕНИЕ 2

Введение диссертации (часть автореферата) на тему «Исследование и разработка параллельных алгоритмов быстрых прямых методов для решения разностных задач математической физики»

ВВЕДЕНИЕ

Актуальность работы. Прогресс в численном моделировании важных прикладных задач теории поля, гидродинамики стал возможен благодаря появлению быстрых прямых методов решения сеточных уравнений. К числу этих методов следует, в первую очередь, отнести циклическую редукцию, метод разложения по базису и типа facr, предназначенных для решения сеточных эллиптических уравнений, с оценками количе ства арифметиче ских операций о (Niog0N) или, даже ошю^ио^Ю).

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

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

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

Значительный вклад в область исследований, связанной с совместным изучением параллельных вычислительных систем и алгоритмов, внесли работы Воеводина В.В., Ильина В.П., Котова В.Е., Кузнецова Ю.А., Марчука Г.И., Самарского A.A., Яненко H.H. и многих других ученых.

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

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

До появления параллельных вычислительных систем развитие быстрых прямых методов было обусловлено потребностью улучшить решение на однопроцессорных ЭВМ, что привело к алгоритмам, которые очень близки к оптимальным и дальнейшее их существенное улучшение практически неосуществимо /1-5/. Создание МВО открыло новый этап в развитии быстра прямых методов, характеризующийся совместным исследованием параллельных свойств данных методов и вычислительных систем /6-14/.

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

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

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

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

Однако исследования, проведенные в диссертации, показали, что временные затраты на обмены могут сильно влиять на эффективность параллельного алгоритма. Иллюстрацией данного факта является параллельный РАСЯ(Ь) - алгоритм, в котором время выполнения обменов влияет на выбор количества шагов циклической редукции.

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

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

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

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

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

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

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

Научная новизна работы состоит в следующем:

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

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

- получены1 оптимальные значения числа шагов циклической редукции I» (Ь={1 -6)) в ?АСН.(Ь)-алгоритме для различных значений размерности задачи Я, количества. процессоров р и параметра, характеризующего быстродействие каналов связи к, позволяющие по сравнению с использовавшимися ранее значениями повысить эффективность параллельных РАСЩЬ)1 - алгоритмов в среднем на 20%-50$ для МВС с универсальной коммутацией и на 50&-85& для МВС с

жесткой коммутацией;

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

Практическая ценность работы состоит:

- в разработке новых параллельных алгоритмов быстрых прямых методов, обеспечиваодих эффективность (Ер=3р/р) использования МВС в диапазоне С0.5 - 0.983 при решении разностных эллиптических уравнений;

в сокращении времени решения прикладных задач математической физики при использовании предложенных оптимальных значений параметра Ь;

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

На защиту выносятся следующие основные научные положения и практические результаты.

1. Параллельные алгоритмы быстрых прямых методоЕ (циклической редукции, разложения по базису и типа РАОН).

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

3. Оптимальные значения параметра 1 ( количества шагов циклической редукции ) в параллельных ЗРАСН (Ь) -алгоритмах для различных значений параметров и топологий МВС.

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

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

топологиями.

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

Теоретические и практические результаты диссертационной работы получены также при выполнении следующих научно-исследовательских работ:

"Разработка тестовых программных средств и оценка эффективности ЫВС" (А ГР 01824010461);

- "Разработка теории, принципов построения и организации универсальных и проблемно - ориентированных сверхвысокопроизводительных многопроцессорных вычислительных систем с программируемой архитектурой" (Л ГР 01870014199);

- "Разработка системной поддержки аппаратного компилятора с языка Фортран для многопроцессорной вычислительной системы с программируемой архитектурой" (* ГР 01900037567);

- "Разработка параллельных методов, алгоритмов и методик решения задач обработки спутниковой информации, САПР цифровой аппаратур! и методик моделирования в вычислительном эксперименте" <* ГР 01910053609).

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях и семинарах:

- Республиканской научно-технической конференции "Функционально-ориентированные вычислительные системы", Харьков, 1986;

- Всесоюзной конференции "Проблемы создания суперЭВМ и суперсистем и эффективность их применения", Минск, 1987;

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

- 43-ей Всесоюзной научной сессии ШЮ РЗС им. А.О.Попова, посвященной да радио, Москва, 1968;

- 2-м Всесоюзном совещании "Конвейерные вычислительные систеш", Киев, 1 Ж;

- Научно-технической конференции молодых ученых и специалистов "Архитектура ЭВМ и машинное моделирование", Таганрог, 1989;

- 33-ей Всесоюзной школы молодых ученых "Численные методы механики сплошнойсреды", Красноярск, 1991;

- научно - технических конференциях профессорско-преподавательского состава ТРТИ им. В.Д.Калмыкова, г.Таганрог, 1966-1988.

Публикации. По материалам диссертац®! опубликовано 16 печатных работ. Кроме того, результаты исследований отражены в 4 отчетах по НИР.

Отруктурз и объем работы. Диссертационная работа состоит из введения, четырех разделов* заключения и приложений. Она содержит 129 страниц машинописного "текста, 133 страницы графического материала, 88 нашенований литературных источников.

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

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

На основании анализа современных архитектур выделяются

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

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

Рассматриваются параллельные алгоритмы для решения систем скалярных и векторных уравнений и их характеристики при реализации на МВС.

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

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

Проводится сравнение построенных параллельных алгоритмов по способу распределения данных по процессорам, способам и методам решения трехдиагональных систем, а также способам и алгоритмам реализации БПФ.

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

В третьем разделе рассматриваются параллельные

расжю-алгоритмы представляющие • наибольший интерео в плане разнообразия вариантов.

Подробно описываются этапы поиска оптимальных

РАСй (Ь)-алгоритмов, характеристики/ которых зависят не только от размерности задачи числа процессоров и быстродействия каналов связи, но и от Ь - количества шагов редукции.

Определяются оптимальные значения параметра Ъ для различных значений остальных параметров.

На основе анализа коэффициентов абсолютного ускорения и

эффективности даются рекомендации по выбору оптимального РАОИ(Ь) -алгоритма.

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

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

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

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

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

1.1. Постановка задачи . Основные понятия 1.1.1. Область применения быстро: прямых методов

Исследование сложных процессов, допускающих математическое описание или математическое моделирование, приводит к .дифференциальным уравнениям в частных производила трех типов: эллиптического, параболического и гиперболического /15-18/.

Применение метода конечных разностей к решению дифференциальных уравнений приводит к системам линейных алгебраических уравнений (СЛАУ) /19/. В большинстве случаев разностная аппроксимация дифференциального уравнения на сетке приводит к СЛАУ с матрицами высокого порядка, ленточной структур! и плохой обусловленности.

В настоящее время для решения СЛАУ применяется два типа методов:

- прямые ("точте") метода;

- итерационные методы ( последовательных приближений).

Общие метода (как правило, итерационные) решения СЛАУ, не

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

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

Как правило, быстрые пряные методы применимы в том случав, если разностную схему можно свести ^ решению векторного уравнения

вида:

кин, Ы)

Уо - Ро , Ум ^ ,

где У^ .- вектор неизвестных, заданная правая часть, 0 -квадратная матрица и Я-разшрность векторов неизвестных.

Для более общего случая векторное уравнение {1.1) имеет вид:

Уо ~ Ро 7 Уы ~ Р N 7

где А и В - квадратные матрицы. Уравнения вида (1.3) возникают тфи

решении разностных задач повышенного порядка точности.

Прямые методы применимы также в случае краевых условий

второго и третьего рода:

(С + 2яЕ )Уо~2У1 =Я0 ,

~2Ум„<+(С+2рЕ)У„ = Рн ; лъо, $»,0 С*Ч)

различных их комбинаций, а также в случае, когда уравнение (1.1) является периодическим и задача имеет вид:

~Ун +СУЛ -У;Ч<-Р.Ь ^ КМН, {1Ъ)

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

К векторным уравнения вида (1.1) и (1.3) с краевыми условиями (1.2), (1.4) и (1.5) сводятся разностные схемы для эллиптических уравнений вида: /А л\

К ди — РСое), ^

(.11)

Ьи = - р(х),

где : т Эг

А з Е. ^ГГг. .

Разностные краевые задачи для уравнений эллиптического типа, согласно /1 /, помимо краевых условий на границе Г области С, различаются по следующим признакам:

- вид дифференциального оператора Ь;

- вид разностного оператора Л ;

- форш области в;

- тип сетки * в области

Примерами эллиптических операторов в уравнениях (1.6) и <1.7) могут быть оператор Лапласа:

Ьи =ди а^Д

и оператор с переменными коэффициентами общего вида:

Прямые методы, применимы для решения задач (1.6) , (1.7) с оператором Лапласа и не используются для операторов Ь вида (1.9) в общем случае. Так как основное требование к разностному оператору А для использования прямых методов состоит в возможности разделять переменные, то в качестве дифференциального оператора можно использовать оператор вида:

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

Рассмотрим типы разностных операторов -А- на примере операторов второго порядка, для которых разностная схема

Лу = х£сО

допускает разделение переменных.

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

У«,* "С ^1-2 -2У1 + У иг ;

А и. - ч-А -Уь-.^-^-'Л ("О

Л»Мг + Т2Г '

Разностные операторы А ( , А г и -Л 3 имеют пятиточечный шаблон, а шаблон для А ^ состоит иг девяти точек и используется для схем с повышенным порядком точности.

В случае равномерных сеток используются оператор! А1« А2 и Ац * а Аз - когда сетка неравномерна.

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

На свойства матрицы разностных уравнений сильно влияет форма области С, в которой ищется решение. Поэтому, применительно к прямым методам будем различать два вида областей. Простой формой в будем считать прямоугольник (при т=2) и параллелепипед (при п&З), а сложной - область, имеющую ступенчатую границу.

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

по одному направление для областей простой формы. Для областей ступенчатой Форш применение прямых методов возможно только в случае равномерных сеток. Неравномерность сетки хотя бы по одному направлению приводит к тому, что векторное уравнение (1.1) имеет вид: -

Yo = Fo , Yn ~ FM ,

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

К векторным уравнениям вида (1.1) и (1.3) с различными краевыми условиями сводятся также разностные схемы для параболических уравнений вида:

с #±=Lu t-i(x,i), с>о, ±>о, (ш)

a-t

с = K = c-const. (Ш)

at

Вид дифференциального оператора аналогичен выражениям (1.8) и (1.10). Разностная аппроксимация по неявной схеме позволяет искать решение исходной задачи в виде последовательности задач, решаемых на каждом временном слое. Так как параметр t (время) не изменяется в пределах одной задачи, их можно рассматривать как стационарные. Действительно, после аппроксимации уравнений (1.12) или (1.13) по неявной схеме получим -

с * г * -Ли + ).

Группируя неизвестные величины в левой части получим выражение:

в котором обозначая =• у, (х) , а правую часть - ?(х), получим уравнение, аналогичное (1.Т). Следовательно, системы уравнений, получавдиеся для каждого временного слоя, можно решать прямыми методами.

Типы используемых разностных операторов аналогичны (1.11), но они записываются для (п+1)-го временного слоя.

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

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

У (оС)=0,

Необходимо найти решение разностной задачи Дирихле для уравнения Пуассона (1.14) в прямоугольнике G={ О ^ >ok-1J2 >

на прямоугольной сетке 0-4 L N4 9

hi^ti/rii , Ь2 = £г/А/2} с границей Г.

Задача (1.14) может быть записана в виде векторного уравнения (1.1) с граничными условиями (1.2), где Y1 - вектор неизвестных

Типы ураёне-нио

Типы краевых условии

Эллиптический

л^и-- Р(х), к>о

1 рода рода 3 рода Периодические

параболический

С я* ¿V

Заключение диссертации по теме «Телекоммуникационные системы и компьютерные сети», Овчаренко, Ольга Игоревна

4.5. Выводы т. Построены эффективные реализации, методов циклической редукции, разложения по базису и типе РАСИСЬ), характеризующиеся различными способами решения ОЛАУ для размерностей задач N={64-4096}, числа процессоров р={4-4096} и параметра, характеризующего быстродействие каналов связи, к={0,25; 1; 4} на следующих топологиях МВС: "кольцо", "матрица" и "куб".

2. Получены оптимальные значения параметра Ь на различных топологиях, позволяющие по сравнению с использующимися ранее значениями повысить эффективность параллельных ?АСН(Ь) алгоритмов в среднем на 50Ж-85Ж.

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

- для топологии "кольцо" при использовании циклической редукции (OR,, GRg) и FACR(L) - алгоритмов (FAGR*, FACH!) количество процессоров следует выбирать в диапазоне {16-256} в зависимости от N, при использовании метода разложения по базису (FA*) в диапазоне (16-1024), а для Fa| - р - произвольно;

- для топологии "матрица", при использовании алгоритмов с параллельным решением СЛАУ (cr1, FA*, facr(l) *) p принимает значения из множества {16-1024}, а для алгоритмов (crg, Fa|), FAGR(L)|) р может принимать любые значения в зависимости от N;

- для топологии "куб" при использовании алгоритмов GRt, FAGR* р следует выбирать из диапазона {16-1024} только при медленных каналах (к-4), для других значений к и алгоритмов выбор р неограничен.

4. Рассмотрены вопросы практического применения полученных результатов на примере МВС с универсальной коммутацией (ЕС 2703) и с жесткой коммутацией (транспьютерная система с топологией "линейка"), а также возможности использования разработанных параллельных алгоритмов, рекомендаций и набора программ при создании функционального и системного наполнений библиотек параллельных алгоритмов.

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

261 ЗАКЛЮЧЕНИЕ

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

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

1. Разработаны параллельные алгоритмы быстрых прямых методов (циклической редукции, разложения по базису и типа РАОИ(Ь)), обеспечивающие значения коэффициента эффективности 0,5-0,98 в зависимости от Н, р и к.

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

3. О учетом временных затрат на выполнение арифметических операций и операций обменов, получены оптимальные значения параметра Ь для различных значений размерности задачи N. количества процессоров р и быстродействия каналов связи к, позволяющие по сравнению с использовавшимися ранее значениями параметра Ь={1 ;2) повысить эффективность использования параллельных РАСй (Ь)-алгоритмов: на МВС с универсальной коммутацией в среднем на 20%-50% и с жесткой коммутацией на 50%-85%.

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

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

Полученные в работе теоретические результаты нашли конкретное применение в созданных вычислительных системах: с универсальной коммутацией (ЕС 2703) и с жесткой коммутацией (транспьютерная система с топологией "линейка"), что подтверждается справками о внедрении.

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

Теоретические и практические результаты работы внедрены и использовались в разработках НИИ приборостроения (г.Москва), НИЦ ЭВТ (г.Москва), ВНИИ ПВТИ (г.Москва), НИИ ШС при ТРТИ им. В.Д.Калмыкова при выполнении научно-исследовательских работ по созданию математического обеспечения вычислительных систем высокой производительности, а также в учебный процесс при выполнении лабораторных, курсовых и дипломных работ, что подтверждается соответствующим! документами (приложение 2). Ожидаемый экономический эффект от внедрения результатов диссертационной работы составляет 12 тысяч рублей. гвз

Список литературы диссертационного исследования кандидат технических наук Овчаренко, Ольга Игоревна, 1992 год

СПИСОК ИСПОЛЬЗОВАННЫХ источников

1. Самарский A.A., Николаев E.G. Метода решения сеточных уравнений. - М.: Наука, 1978. - 592с.

2. Марчук Г.И. Методы вычислительной математики. - М.: Наука, 1980. - 536 с.

3. Ильин В.П. Численные методы решения задач электрофизики. - М. : Наука, 1985. - 336 с.

4. Swarztrauber P.H. : The Methods of Cyclic Reduction, Fourier Analysis, and the PACR Algorithm ior the Discrete Solution of Poisson*s Equation on the Rectangle// SIAM Rev. - 1977. - Vol 19. - P. 490-501.

5. HocJmey R.W. Rapid Elliptic solvers. - In: Numerical Methods in Applied Fluid Dynamics. London: Acad. Press Ltd., 1980.

6. Swarztrauber P.N. Multiprocessor FFTs // Parallel Oomput. -1987. - N5. - P. 197-210.

7. Briggs W.L., Turnbule T. Past Poisson solvers for MIMD computers// Parallel Comput. - 1988. - N6. - P. 265-274.

8. Кузнецов И.Б. Параллельный комбинированный метод быстрого преобразования Фурье и редукции// Препринт ВЦ СО АН СССР JM01 .-Новосибирск. - 1983. - 16с.

9. Потапов В.Н., Сухов Е.Г. Численное решение уравнения Пуассона на многопроцессорной вычислительной системе с общим потоком команд//В сб.: Многопроцессорные вычислительные системы с общим потоком команд. - М.: ИПУ. - 1978. - Вып. 19. - С. 54-64.

10. Седухин С.Г. Параллельная интерпретация прямых методов линейной алгебр!// Программирование. - 1984. - M. ~ С.57-68.

11. Высокоскоростные вычисления. Архитектура, производительность, прикладные алгоритмы и программы суперЭВМ// Пер. с англ./ Под ред. Я.Ковалика. - М. : Радио и связь, 1988. - 432с.

12. Sameh A.H. A fast Poisson solver for multiprocessor. In Elliptic Problem solvers II Proc., Oonf., Monterey, Calif., 10-12 Jan., 1983. Orlando e.a., 1964. - P. 175-186.

13. Saad J., Sameh. A., Saylor P. Solving elliptic difference equations on a linear array of processors// SIAM J. Sei. and Stat. Goiuput. - 1985. - Vol 6, N4. - P. 1049 - 1063.

14. Суханов A. й., Овчаренко О.И. Реализация быстрых прямых методов на матрично-конвейерной вычислительной системе// Тезисы докладов 2-го Всесозшого совещания "Конвейерные вычислительные системы". - Киев, 1988. - с. 50-51.

15. Сухинов А.И., Овчаренко О.И. Организация вычислений при решении многомерных уравнений параболического и гиперболического типов на МВС// Тезисы доклада Всесоюзной научно-технической конференции "Проблемы создания аппаратных средств вычислительной техники для машинного моделирования". -Москва, 1987. - С.66.

16. Николаев И.А., Сухинов А.И., Овчаренко О.И. Параллельные алгоритмы решения трехмерного уравнения теплопроводности на основе схем расщепления. - М., 1986. - 10с. - Деп. в ВИНИТИ

18.02.86,' JW146-B86.

17. Сухинов А.И., Овчаренко О.И., Нестерова Г.Г. Параллельный алгоритм задачи обтекания трансзвуковым потоком в потенциальном приближении. - М., 1987. - 11с. - Деп. в ВИНИТИ

16.09.87, Л 671Ö-B87.

18. Сухинов А.И., Овчаренко О.И. Об алгоритмах решения трехмерного уравнения теплопроводности на многопроцессорной вычислительной системе//Электронное моделирование. - 1988, JH.- С.22-25.

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

20. Хейгеман Л., Янг Д. Прикладные итерационные методы // Пер. с

англ. - M.: Мир, 1986. - 446 с.

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

22. Оухинов А.И., Нестерова Г.Г., Овчаренко О.И. Об одном подходе к распараллеливанию метода верхней релаксации (SOR) // Тезисы доклада научно-технической конференции молодых ученых и специалистов "Архитектура ЭВМ и машинное моделирование". -Таганрог, 1989. - С.44-45.

23. Самарский A.A., Андреев В.Б. Разностные методы для эллиптических уравнений. - М.: Наука, 1976.

24. Каляев A.B. Многопроцессорные системы с программируемой архитектурой. - М.: Радио и связь, 1985. - 240с.

25. Каляев A.B. Многопроцессорные системы с программируемой архитектурой сверхвысокой производительности// I Всесоюзная конференция "СуперЭВМ". Тезисы докладов. - Минск, 1987.- С. 49-51.

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

27. Состояние и перспективы развития вычислительных систем высокой производительности. Обзор. М.: НИИ КВАНТ. - 176с.

28. Christ N.H., Теггапо A.A. Very Past Parallel Processor// IEEE Trans. Comput. - 1984. - Vol. 33, N4. - P. 344-350.

29. Мануэль Т. Усовершенствование параллельные архитектуры как способ ускорения вычислений// Электроника.-1983,J612.- С.25-39.

30. Хорошевский В.Г. Инженерный анализ функционирования вычислительных машин и систем. - M.: Радио и связь,1987.-256с.

31. Iiipowski G.J., Malek. Parallel Computing theory and Comparisons. - John Willey Sons. - N.Y. 1987. - 315p.

32. Каляев A.B., Макаревич О.Б., Бабенко Л.К. Архитектура многопроцессорной ВС на базе ЕС ЭВМ и спецпроцессора,

гее

ориентированного на моделирование задач математической физики и линейной алгебры// в кн.: Комплексы программ математической физики. - Новосибирск: ИТПМ 00 АН СССР, 1984. - С. 40-43.

33. Бабенко Л.К., Макаревич Q.B., Максимов М.М., Овчаренко О.И., Рыбицкая Л.П., Сухинов А.И. Оценка производительности многопроцессорной вычислительной системы с программируемой архитектурой. - М., 1990. - 28с. - Деп. в ВИНИТИ 15.03.90, Ä1416-B90.

34. Бабенко Л.К., Макаревич О.Б., Сухинов А.И., Овчаренко О.И. Способы реализации базовых операций вычислительной алгебры в многопроцессорных вычислительных системах// Управляющие системы и машины, 1989, JK5. - С. 25-28.

35. Разработка теории, принципов построения и организации универсальных и проблемно - ориентированных сверхвысокопроизводительных многопроцессорных вычислительных систем с программируемой архитектурой: Отчет о НИР (промежуточный)/ Таганрогский радиотехнический институт им. В.Д.Калмыкова (ТРТИ); руководитель А.В.Каляев JfiTP 01870014 199, инв. * 0287.0222959. - 1987. - 163с.

36. Parkinson D. Organisational aspects of using parallel computers// Parallel Comput. - 1987. - N1-2. - P. 75-83.

37. Самарский A.A. Введение в численные методы. - M.: Наука, 1987.

- 288с.

38. Кучеров А.Б., Николаев Е.С. Параллельные и конвейерные алгоритмы попеременно-треугольного итерационного метода// В сб.: Разностные методы математической физики. - М.: МГУ, 1984.

— С.66—83.

39. Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре. Ч. 1,11. - Ленинград: ЛОМИ АН СССР, Препринт Р-6-77, 1977; Р-6-81, 1981.

40. Gannon D.B., Eosendale J.V. On the impact of communication complexity on the design oi parallel numerical algorithms// IKEE Trans . Gomput. - 1984. - 33, N12. - P. 1180 - 1194.

41. Воеводин В.В. Математические модели и методы в параллельных процессах. - М.: Наука, 1986. - 296с.

42. Sweet R.A. A cyclic reduction algorithm for solving block mridiagonal systems of arbitrary dimension// SIAM J. Numer. Anal. - 1977. - Vol 14. - P.706-719.

43. Сандер С.А. Некоторые варианты метода редукции// В кн.: Вычисления с разреженными матрицами; Под ред. Ю.А.Кузнецова. -Новосибирск: ВЦ СО АН СССР. - 1981. - С. 123-133.

44. Buzbee B.L., Golub G.H., Neilson G.ff. On direct methods for solving Poissons equation // SIAM J. Numer. Anal. - 1970, -vol. 7, N4. - P. 627 - 656.

45. Buneman 0. A compact non - iterative Poisson - Solver. - SUIPR report, N294, Stanford IMiversity.

46. Суханов A.M., Овчеренко О.И. Параллельный алгоритм метода циклической редукции для решения сеточных эллиптических уравнений // Тезисы доклада X Всесоюзной конференции "Проблеш создания суперЭВМ и эффективность их применения", Мн., 1987.-С. 51-52.

47. Макаревич О.Б., Бабенко JI-К., Сухинов А.И., Овчаренко О.И. Параллельные алгоритмы метода циклической редукции для решения сеточных эллиптических уравнений. - М., 1989. - 36с. - Деп. в ВИНИТИ 26.04.89, Л2802-В89.

48. Яненко Н.Н., Коновалов А.Н., Бугров А.Н., Шустов Г.В. Об организации параллельных вычислений и "распараллеливании" прогонки// В сб.: Численные методы механики сплошной среды. -1978, 9, т. - С.139-146.

49. Теренков В.И. О реализации прямых методов решения сеточных

уравнений на МВС// В сб.: Разностные методы математической Физики. - М.: МГУ, 1984. - С.97-105.

50. Ахмет Н. , Рао К.Р. Ортогональные преобразования при обработке цифровых сигналов/ Пер. с англ. - М.: Связь, 1980. - 248с.

51. Brigham E.G. The Past Fourier Transform. - Englewood Cliffs: Prentice - Hall, 19T4. - 252p.

52. Cooley J.W. and Tukey J.W.: An algorithm for the machine calculation of the complex Fourier series// Math. Comput. -

1965. - Vol 19. - P.297-301.

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

54. Pease M.G. An adaptation of the fast Fourier transform for parallel processing // J. Assoc. Comput. Math.- 1968. - Vol 15. - P.252 - 264.

55. Gocran W.T.// IEEE Trans. Audio Eiectroacoust., 1967. -Vol. 15. - P.45-55.

56. Gentleman W.M. and Sande G. Fast Fourier.Transform for fun and profit. AFIPS Conf. Proc. - Fall Joint Comput. Conf.,

1966. - Vol 29. - P.563-578.

57. Bergland G.D. A fast Fourier Transform algorithm for real -valued semies// Commun. Аззос. Comput. Mach., 1968. - Vol. 11. - P. 703-710.

58. Cooley J.W., Lewis P.A., Welch P.D. The fast Fourier transform algoritm and Its applications IBM Research Paper RC-1743. -Proc. IEEE. - 1967. - Vol.55. - P.1675-1677.

59. Введение в цифровую фильтрацию / Под ред. Р.Богнера, А.Константинидиса. - М.: Мир, 1976, 216с.

60. Beard S.J., Hockney R.W. A programm for the direct solution of Poisson's equation in complex geometries// Comput. Phys. Commun., 1985. - Vol. 36. - P. 25-57.

61. Бабенко Л.К., Лутай В.Н. Реализация алгоритма быстрого преобразования Фурье на многопроцессорной вычислительной системе с программируемой архитектурой// В кн.: Многопроцессорные вычислительные структура . - Таганрог ; 1386, вып. 8 (XVII). - С. 23-25.

62. Агарвал P.O., Кули Дж. J. Алгоритш дискретного преобразования Фурье по смешанным основаниям для векторных ЭВМ// ТИИЭР. -1987. - т.75, N9. - 0. 162-172.

63. ТЗоПЮюге J. - J. Inst. Math. Appl. - 1973. - Yol 12. - P. 115-117.

64. Бабенко Л.К., Макаревич О.Б., Сухинов А.И., Овчаренко О.И. Параллельные алгоритмы метода разложения по базису. - М., 1991. - 57с. - Деп. в ВИНИТИ 10.09.91, * 3666 - В91.

65. Hockney R.ff. A Past Direct solution of Poisson*s equation using Fourier Analysis// J.Assoc. Oomput. Mach.-1965.- Yol .12. - P.95-113.

66. Hockney R.W. The potential calculation and some applications// Methods Comput. Phys. - 1970. - Yol. 9. - P. 135-211.

67. Хокни P., Иствуд Дж. Численное моделирование методом частиц/ Пер. с англ. - М. : Мир, 1987. - 670с.

68. Хокни Р. Методы расчета потенциала и их приложения// В кн. : Вычислительные методы в физике плазмы/ Под ред. Б.Олдера, С.Фернбаха и М.Ротенберга. - М.: Мир, 1974, 143с.

69. Temperton С. On the PAOR(L) algorithm for the Discrete Poisson Equations//J. Oomput. Phys.- 1980. - Vol. 34. -P.314-329.

70. Бабенко Л.К., Макаревич О.Б., Сухинов А.И., Овчаренко О.И. Реализация FAGR(L) - алгоритмов на многопроцессорной вычислительной системе. - М., 1991.- 35с. - Деп. в ВИНИТИ 26.07.91, Ä32I3 - B9I.

г?о

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

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

73. Сухинов А.И., Овчаренко О.И. Об оценке производительности многопроцессорной вычислительной системы на задачах матричной алгебры и математической физики// Тезисы доклада XLIII Всесоюзной научной сессии НТО РЭС им. А.0.Попова, посвященной Дню радио. - Москва, 1988. - 0.35.

74. Разработка тестовых программных средств и оценка эффективности МВО: Отчет о НИР/ Таганрогский радиотехнический институт им. В.Д.Калмыкова (ТРТИ); Руководитель А.В.Каляев; * ГР 01824010461, инв. * 0285.0087655. - Таганрог, 1985. - 52с.

75. Разработка системной поддержки аппаратного компилятора с языка Фортран для МВС ПА: Отчет о НИР/НИИ многопроцессорных вычислительных систем; Руководитель Л.К-Бабенко; л ГР 01900037567, инв. J* 02900031119. - Таганрог, 1989. - 121с.

76. Разработка параллельных методов, алгоритмов и методик решения задач обработки спутниковой информации, САПР цифровой аппаратуры и методик моделирования в вычислительном эксперименте: Отчет о НИР/ НИИ многопроцессорных вычислительных систем; Руководитель О.Б.Макаревич; * ГР 01910053609, - Таганрог, 1991. - 162с.

77. Бабенко Л.К., Карпов Е.В., Макаревич О.Б., Чефранов А.Г. Управление параллельными процессами в многопроцессорной системе с программируемой архитектурой// Известия Северо-Кавказского научного центра высшей школы. Технические науки. - 1986. - М. - 0.73-76.

78. Бабенко Л.К., Карпов 1.В., Катаев Q.B. Средства реализации основных режимов работы многопроцессорной вычислительной

системы с программируемой архитектурой// Пятая Всесоюзная

* школа-семинар "Распараллеливание обработки информации". Тезисы докладов. - Львов, 1985. - Ч. 2. - С. 145-146.

79. Бабенко Л.К., Макаревич О.Б., Овчаренко О.И. Векторизация базовых крупных операций многопроцессорной вычислительной системы// Тезисы доклада 2-го Всесоюзного совещания "Конвейерные вычислительные системы". - Киев, 1988. - С.58-60.

80. Сухинов А.И., Овчаренко О.И. О реализации базового набора программ линейной алгебры на многопроцессорной системе// Тезисы доклада III Всесоюзной школы молодых ученых "Численные

• методы механики сплошной среды. - Красноярск, 1991. - 0.35-36.

81. Transputer reference manual. INMOS Limited. - 1988. - N 6-9. -P.213-293.

82. Dongarra J.J., J.R.Bunch, C.B.Moler, and G.W.Stewart. LINPACK users guióle. Soc. Indust. Appl. Math., Philadelphia.- 368p.

83. Denme 1 J., Dongarra J., Croz J.Du., Greenbaum A., Hammarling J. and Sorensen D. A projekt for developing a linear algebra library for high - performance computers// In: Aspects of Computation on Asyncronous Parallel Processors, IP IP WG 2.5. Working Conference 5, Angust 22-26, 1986, Stanford University,

I Stanford California, USA, p. 51-54.

84. McComb J., Schmidt S. Engineering and scientific subroutine library for the IBM 3090 Vector Facility// IBM Systems Journal. - 1988. - Vol. 27, N4. - P. 404-415.

85. Smith. B.T., Boyle J.M., Dongarra'J.J., Garbow B.S., IXebe J., Klema V.C. and Moler С.В. Matrix systems routines - EISPACK guide. Lecture notes in Computes Seines. - 1976. - Vol б (2d ed), Springer - Ver lag, Berlin, 551p.

86. Уилкинсон Дж.Х. Алгебраическая проблема собственных значений.

\

- М.: Наука, 1970.

87. Rice J.R., Boiavert R.P. Solving elliptic problems using ЕШАСК. Springer Series im Computational Mathematics, 2, New York, Berlin, Tokyo, 1988, p.497.

88. Овчаренко О.И., Сухинов А.И., Харина О.Д., Черкасов A.A., Целых А.Я. Структура библиотеки параллельных алгоритмов многопроцессорной вычислительной системы// Тезисы доклада Республиканской научно-технической конференции "Функционально-ориентированные вычислительные системы".

Харьков, 1986. - С. 57-58.

Личный вклад автора в работы, выполненные в соавторстве, состоит в следующем:

- работы /46, 47, 64/ - разработаны параллельные алгоритмы методов циклической редукции и разложения по базису;

- работы /14, 70/ - разработаны параллельные FACR(L) -алгоритмы и определены оптимальные значения параметра L;

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

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

- работа /15, 16, 18/ - получены оценки коэффициентов ускорения и эффективности при решении уравнения теплопроводности на МВС с различными типами топологий;

- работы /17, 22/ - получены выражения для оценки временных затрат на выполнение задачи обтекания трехмерным трансзвуковым потоком на МВС с универсальной коммутацией;

- работы /34 , 79, 80/ - предложены способы реализации базовых

операций, лежащих в основе быстрых прямых методов;

- работы /35, 74/ - получены оценки производительности МВС на задачах математической физики;

- работы /75, 76/ - разработаны алгоритмы и программы базовых операций вычислительной алгебры.