.../ПУБЛИКАЦИИИ/МОНОГРАФИИ

ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ РЕШЕНИЯ СЕТОЧНЫХ УРАВНЕНИЙ Под редакцией Н.Л. Казанского Авторский коллектив: Д.Г. Воротникова, Д.Л. Головашкин, Н.Л. Казанский, А.В. Кочуров, Л.В. Логанова, С.А. Малышева ISBN: 978-5-88940-115-5 146 стр. Федеральное государственное бюджетное учреждение науки Институт систем обработки изображений Российской академии наук, 2001, 2003гг. Отпечатано в типографии ООО «Предприятие «Новая техника»

Аннотация:
Предлагаемая монография посвящена разработке и реализации параллельных алгоритмов решения сеточных уравнений явных и неявных разностных схем. Основное внимание уделяется различным алгоритмам метода прогонки, наиболее популярного в вычислительной практике. Рассматриваются параллельные реализации правой, циклической и встречных прогонок, характеризующиеся одномерным, двумерным и циклическим разбиением сеточной области.
Особенностью издания является рассмотрение проблемы организации вычислений на графических процессорах. Приводятся алгоритмы реализации разностных схем Кранка – Николсон (на примере BPM-метода) и Yee (FDTD-метод). Для преодоления ограничений на размер видеопамяти предлагается метод пирамид.
Изложение алгоритмов сопровождается примерами программ, теоретическими оценками эффективности и представлением результатаов вычислительных экспериментов. Авторы рассчитывают на полезность работы для обучающихся и специалистов в области параллельных вычислений.

Рецензенты:
д.т.н., профессор В.П. Гергель, д.т.н., профессор С.В. Востокин

Оглавление

	ВВЕДЕНИЕ		6
Глава 1	ОБЗОР ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ РЕШЕНИЯ ЛЕНТОЧНЫХ СЛАУ		9
	1.1	Сеточные уравнения трёхдиагонального вида	10
	1.2	Метод циклической редукции	13
	1.3	Метод декомпозиции области	17
	1.4	Метод Томаса	20
Глава 2	ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ МЕТОДА ПРОГОНКИ		25
	2.1	Параллельный алгоритм метода правой прогонки с линейной декомпозицией сеточной области	25
	2.2	Параллельный алгоритм метода правой прогонки с циклической декомпозицией сеточной области	27
	2.3	Параллельный алгоритм метода встречных прогонок для одномерной сеточной области	29
	2.4	Параллельный алгоритм метода встречных прогонок для двумерной сеточной области, линейное разбиение	32
	2.5	Параллельный алгоритм метода встречных прогонок для двумерной сеточной области, циклическое разбиение	37
	2.6	Сравнение параллельных алгоритмов прямых методов решения сеточных уравнений	45
Глава 3	ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ МЕТОДА ВСТРЕЧНЫХ ЦИКЛИЧЕСКИХ ПРОГОНОК		48
	3.1	Метод встречных циклических прогонок	48
	3.2	Параллельный алгоритм для одномерной сеточной области	52
	3.3	Параллельный алгоритм для двумерной сеточной области с линейным разбиением	54
	3.4	Параллельный алгоритм для двумерной сеточной области с двумерным разбиением	57
	3.5	Параллельный алгоритм для двумерной сеточной области с циклическим разбиением	59
	3.6	Векторно-параллельный алгоритм метода встречных циклических прогонок	63
Глава 4	РЕАЛИЗАЦИЯ МЕТОДА ЦИКЛИЧЕСКОЙ ПРОГОНКИ НА ГРАФИЧЕСКИХ ВЫЧИСЛИТЕЛЬНЫХ УСТРОЙСТВАХ		68
	4.1	Алгоритм циклической прогонки для одного GPU	75
	4.2	Алгоритм циклической прогонки для двух GPU	77
	4.3	Постановка вычислительных экспериментов  для метода циклической прогонки	78
	4.4	Алгоритм встречных циклических прогонок для вычислительной системы с двумя GPU	82
	4.5	Постановка вычислительных экспериментов  для метода встречных циклических прогонок	83
Глава 5	РЕШЕНИЕ РАЗНОСТНЫХ УРАВНЕНИЙ НА GPU МЕТОДОМ ПИРАМИД		85
	5.1	Основы метода пирамид	87
	5.2	Декомпозиция одномерной сеточной области	89
	5.3	Декомпозиция двумерной сеточной области	93
	5.4	Программная реализация	95
	5.5	Вычислительный эксперимент	97
	5.6	Разностное решение уравнений Максвелла на графическом процессоре методом пирамид	103
Глава 6	ПАРАЛЛЕЛЬНО-ПОСЛЕДОВАТЕЛЬНЫЙ АЛГОРИТМ РЕШЕНИЯ ТРЕУГОЛЬНЫХ СИСТЕМ НА ПРОЦЕССОРНОМ КОЛЬЦЕ		106
	6.1	Векторный столбцово-ориентированный алгоритм решения треугольных систем	107
	6.2	Параллельный алгоритм решения треугольных систем на кольце	108
	6.3	Параллельно-последовательный алгоритм	111
Глава 7	ДЕКОМПОЗИЦИЯ СЕТОЧНОЙ ОБЛАСТИ ПРИ РАЗНОСТНОМ РЕШЕНИИ УРАВНЕНИЙ МАКСВЕЛЛА		113
	7.1	Декомпозиция одномерной сеточной области	114
	7.2	Декомпозиция двумерной сеточной области	124
	7.3	Реализация декомпозиции вычислительной области на графическом вычислительном устройстве	127
Глава 8	ВЕКТОРНАЯ РЕАЛИЗАЦИЯ МЕТОДА РАСПРОСТРАНЯЮЩЕГОСЯ ПУЧКА ПРИ ПОМОЩИ ТЕХНОЛОГИИ CUDA		130
	8.1	Векторный алгоритм для разностной схемы Кранка–Николсон	131
	8.2	Реализация векторного алгоритма по технологии CUDA	134
	ЗАКЛЮЧЕНИЕ		139
	ЛИТЕРАТУРА		140