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

• Автор: Логанова, Лилия Владимировна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2015
• Место защиты: Самара
• Количество страниц: 205 с. : ил.

Оглавление
Введение

1 Математические модели параллельных алгоритмов решения сеточных уравнений

1.1 Обзор математических моделей параллельных вычислительных систем и

алгоритмов
1.1.1 Концепция математических моделей алгоритмов и вычислительных систем в работах Воеводина В. В. и Воеводина Вл. В
1.1.2 Концепция математических моделей алгоритмов и вычислительных систем в работах Гергеля В. П
1.1.3 Концепция математических моделей алгоритмов и вычислительных систем в работах Хорошевского В. Г
1.2 Методы решения сеточных уравнений трёхдиагонального вида для случая одномерных сеточных областей

1.2.1 Метод циклической редукции

1.2.2 Метод декомпозиции области
1.2.3 Метод прогонки
1.2.4 Метод Стоуна
1.2.5 Параллельный алгоритм метода прогонки
1.3 Параллельные алгоритмы метода прогонки для двумерных сеточных областей
1.4 Решение сеточных уравнений методом встречных циклических прогонок
1.5 Математическая модель алгоритмов, основанных на методе встречных циклических прогонок
Выводы главы
2 Параллельные алгоритмы метода встречных циклических прогонок
2.1 Параллельный алгоритм для одномерной сеточной области
2.2 Параллельный алгоритм для двумерной сеточной области с линейным разбиением
2.3 Векторизация алгоритма метода встречных циклических прогонок
2.4 Параллельный алгоритм с двумерным разбиением сеточной области
2.5 Параллельный алгоритм с циклическим разбиением сеточной области
Выводы главы
3 Реализация метода циклических прогонок на GPU
3.1 Модели CUDA
3.1.1 Аппаратно-архитектурная модель CUD А
3.1.2 Программная модель CUDA
3.2 Обзор алгоритмов решения сеточных уравнений трёхдиагонального вида
на GPU
3.2.1 Реализация на GPU метода редукции с использованием
быстрого преобразования Фурье
3.2.2 Реализация на GPU гибридных алгоритмов циклической редукции..
3.2.3 Гибридный алгоритм циклической редукции и метода Томаса
3.2.4 Сравнение алгоритмов, основанных на прямых методах
3.2.5 Сравнение библиотек для решения разреженных СЛАУ на GPU
3.2.6 Итог предложенного обзора
3.3 Математическая модель алгоритма циклической прогонки для GPU
3.4 Алгоритм циклической прогонки для одного GPU
3.5 Алгоритм циклической прогонки для двух GPU
3.6 Реализация алгоритма встречных циклических прогонок на
вычислительной системе с двумя графическими процессорами
Выводы главы
Заключение
Список использованной литературы
Приложение А
Приложение В
Приложение С
Приложение D
Приложение Е
Приложение F
Приложение G

Введение
Диссертация посвящена построению параллельных алгоритмов методов циклической и встречных циклических прогонок, согласованных с гетерогенной вычислительной средой, а также исследованию эффективности этих алгоритмов.
Актуальность темы
Решение дифференциальных уравнений (необходимое для моделирования физических процессов) с помощью методов конечных разностей и конечных элементов зачастую сводится к необходимости решения системы линейных алгебраических уравнений (СЛАУ) с матрицей ленточного вида. Причём круговые, сферические и цилиндрические физические подобласти характеризуются матрицами, содержащими, кроме ленты на центральных диагоналях, ненулевые элементы в верхнем правом и левом нижнем углах. Переход к многомерным задачам сопряжен с заметным ростом вычислительной сложности. Именно этот фактор определяет растущую потребность в применении параллельных вычислительных систем и, как следствие, в синтезе алгоритмов, учитывающих такую архитектуру.
На сегодняшний день для решения ленточных СЛАУ на кластерных ВС (вычислительных системах) традиционно применяются следующие программные комплексы: РЬАРАСК (пакет параллельных процедур линейной алгебры, включающий параллельные версии процедур решения систем линейных уравнений с помощью Ш и (^-разложений, разложения Холецкого и другие), ЗсаЬАРАСК (библиотека параллельных программ для решения систем линейных уравнений, обращения матриц, поиска собственных значений и другие), В1оск8о1уе95 (параллельная программная библиотека, предназначенная для решения СЛАУ с симметричными разреженными матрицами). Для систем с (ЗРИ (графическим процессором) используются ІчіУГОІА cuSPAR.SE (набор базовых подпрограмм линейной алгебры для разреженных матриц), МУГОІА сиВЕА8 (библиотека базовых подпрограмм линейной алгебры для КУГОІА С1ЮА), СиЬА

идеального последовательного алгоритма. Суть данного алгоритма заключается в следующем [ 37]:
Прямой ход состоит в определении прогоночных коэффициентов:
а, = —,а|+1 =■—— , 1 = 1,2,..., М-1,
с„ с,—а,а,
0 ' 1 ' (1.2.1)
Р1=Л,Р|+1=А±£Д , 1 = 1,2,...М, с0 с, - а,а,
где а0,а2,...,ам- элементы матрицы А, находящиеся под главной диагональю;
с0,с2,...,см - элементы главной диагонали А; Ь0,Ь2,...,ЬМ - элементы, расположенные над главной диагональю А.
Обратный ход позволяет найти решение:
Ум=Рм+1>У,=а,+1У1+1+Р1+Р 1 = М-1,М-2,..,0 (1.2.2)
Формулы (1.2.1), (1.2.2) также называют формулами правой прогонки.
Вычисления, производимые во время выполнения прямого хода, позволяют представить матрицу А как произведение нижней треугольной матрицы Ь и верхней унитреугольной матрицы И: А=Ы1 [35], где
|Ч 0 0 ^ Г1
-а, г, 0 0 1 - а2
0 -а2 хг 0 и = 0 0 1 -а3
0 °-ам-,2м_, 0 ч° 0 -ам ъи } 0 0 1 - ч0 0 1 J
г,=с1-а1а1,[ = 1,2,...,М
Тогда решение системы Ах=Гсостоит из 2 этапов: