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

• Автор: Овчаренко, Ольга Игоревна
• Шифр специальности: 05.13.13, 05.13.16
• Научная степень: Кандидатская
• Год защиты: 1992
• Место защиты: Таганрог
• Количество страниц: 315 с.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

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. Выводы................................................. . 121'
3. РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ PACR(L)-АЛГОРИТМОВ
3.1. Основные этапы комбинированного метода
Фурье-алгоритма и редукции ... . . . . . ... . . . . . .
3.2. Построение параллельных PACR(Xi) - алгоритмов . . . . . .
3.3. Оптимизация FACR(L) - алгоритмов
3.4. Выводы
4. РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ БЫСТРЫХ
* ПРЯМЫХ МЕТОДОВ ДЛЯ НЕКОТОРЫХ ТОПОЛОГИЙ МВС

4.1. Параллельные алгоритмы метода циклической редукции
4.2. Параллельные алгоритмы метода разложения по базису
4.3. Параллельные РДОН(Ь)-алгоритш
4.4. Практическое использование результатов диссертационной работы
4.4.1. Реализация быстра прямых методов на вычислительном комплексе ЕС 1061 - ЕС 2
4.4.2. Реализация быстрых прямых методов на транспьютерной системе
4.4.3. Использование полученных результатов в библиотеках
• параллельных алгоритмов
4.5. Выводы
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
ПРИЛОЖЕНИЕ
ПРИЛОЖЕНИЕ
ВВЕДЕНИЕ
Актуальность работы. Прогресс в численном моделировании занных прикладных задач теории поля, гидродинамики стал возможен благодаря появлению быстрых прямых методов решения сеточных уравнений. К числу этих методов следует, в первую очередь, отнести циклическую редукцию, метод разложения по базису и типа facr, предназначенных для решения сеточных эллиптических уравнений, с оценками количества арифметических операций 0(NiogoN) или, даже OdilogodoggN)).
Повышение требований к точности численного моделирования приводит к необходимости использования сеток с большим числом узлов, а, следовательно, к быстрому росту трудоемкости задач.
Создание многопроцессорных вычислительных систем (МВС) с производительностью 103-!О10 операций в секунду определило один из важнейших путей повышения скорости решения крупномасштабных задач и открыло ноше возможности для проведения вычислительного эксперимента в фундаментальных и научных исследованиях.
Проблемы параллелизма в архитектуре вычислительных систем и комплексов в программном обеспечении и методах вычислений являются взаимосвязанными. Поэтому, чтобы воспользоваться преимуществами параллельных вычислительных систем и обеспечить максимальную эффективность их использования, необходимо разрабатывать ноше параллельные алгоритмы, ориентированные на параллельную структуру МВС-.
Значительный вклад в область исследований, связанной с совместным изучением параллельных вычислительных систем и алгоритмов, внесли работы Воеводина В.В., Ильина В.П., Котова
В.E., Кузнецова Ю.А., Марчука Г.И., Самарского A.A., Яненко H.H. и многих других ученых.

р/2-1, р/2+1, на шаге 1=п-2 от Пр с номерами р/4 и Зр/
• процессорам с номерами, соответственно р/8, Зр/8,...,р/4-1 и 5р/8; ?р/8,...,Зр/4-1, Зр/4+1 и так далее. Число шагов 1, требующих обменов информацией, есть функция от числа процессоров, поэтому время, необходимое для выполнения обменов меаду Пр на обратном ходе, зависит только от р и не зависит от размерности задачи N. Выражение для расчета временных затрат на выполнение обменов для случая №>р имеет вид:
Теи °= 8Ьа-'К ^N-1) + Ъа • К • бо^р,
щ где первое слагаемое характеризует временные затраты на обмены на
прямом ходе алгоритма, а второе - на обратном.
В качестве примера, иллюстрирующего распределение информации по процессорам, последовательность расчета величин и выполнения обменов на рисунке 1.4 приведена схема решения задачи для случая N=16 и р=4. Квадратами обозначены величины , определяемые на каждом шаге. Сплошные линии характеризуют передачи данных внутри процессоров, а пунктирные - меаду процессорами.Стрелки указывают, какие значения, определяемые на предыдущих шагах, используются для расчета новых данных.
Отдельно рассмотрим ситуацию, когда Н=р, так как в этом случае организация обменов отличается от предыдущего. При прямом ходе, на каждом шаге, обмен информацией проводится в два этапа.
1 этап: Передача информации от Цр^+21-1 к Цр^;
2 этап: Передача информации от Пр^_21-1 к Пр^,
1=гг,г 2х,з г1,...^1, з=1,2,...,п-1.
Механизм выполнения обменов на обратном ходе аналогичен предыдущему случаю (для Н>р), с той лишь разницей, что обмены выполняются на кавдом шаге. Поэтому выражение для определения
* временных затрат на обмены при прямом и обратном ходах алгоритма