© Самарский государственный
аэрокосмический университет, 2010
2
ОГЛАВЛЕНИЕ
Введение
4
1 Распараллеливание последовательных программ
7
1.1 Распараллеливание ациклических участков программ
7
1.2 Распараллеливание ациклических участков программ
15
1.3 Распараллеливание выражений
27
2 Синтез параллельных алгоритмов
34
2.1 Понятие параллельного алгоритма
34
2.1 Восходящий подход к синтезу параллельных алгоритмов
36
2.3 Нисходящий подход к синтезу параллельных алгоритмов
59
2.4 Характеристики параллельных вычислительных
процессов и алгоритмов <...> Параллельные алгоритмы решения разностных уравнений
65
74
3.1 Параллельные алгоритмы решения сеточных уравнений
явных разностных схем
74
3.2 Параллельные алгоритмы решения трехдиагональных
сеточных уравнений неявных разностных схем
84
Заключение
103
Литература
104
3
Введение
Способность производить вычисления является не только необходимым
навыком для большинства людей, но и фундаментальным признаком любой
цивилизации. <...> Последовательная программа разбивается на циклические и ациклические
фрагменты, к которым применяются известные методики распараллеливания. <...> В качестве
инструментов
распараллеливания
используются
два
подхода,
соответствующие известной гегелевской паре “тезис”, “антитезис”. <...> Рассмотрены как явные, так и неявные
схемы,
записанные
на
сеточных
областях
различной
размерности. <...> Последовательный алгоритм будет понят не скоро, соответственно не скоро
удастся создать из него параллельный. <...> Разумнее воспользоваться известной
последовательной программой, сконструировав параллельный алгоритм из
нее (распараллелив). <...> Сама по себе последовательная программа оперирует с
областью памяти, порождая вычисления. <...> 1.1 Стандартный граф
программы.
по введенным относительным индексам x и y массива вычисляет абсолютные
индексы v и z, используя базу массива c, распечатывает участок массива между
абсолютными индексами и выводит упорядоченные относительные индексы. <...>
Современные_методы_и_алгоритмы_решения_сложных_задач_на_суперкомпьютерах_[Электронный_ресурс]_.pdf
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ
УНИВЕРСИТЕТ ИМЕНИ АКАДЕМИКА С.П. КОРОЛЕВА
(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)»
Д. Л. Головашкин
Современные методы и алгоритмы
решения сложных задач
на суперкомпьютерах
Электронное учебное пособие
САМАРА
2010
Стр.1
УДК 681.324.006.3
ББК 39.65
Автор: Головашкин Димитрий Львович
Рецензенты: к.ф.-м.н., доцент С.И.Харитонов,
к.т.н. , доцент С.Б. Попов
В настоящей работе излагаются методики построения параллельных
алгоритмов, вычисления по которым могут быть реализованы на
системах с мультипроцессорной архитектурой. Рассматриваются
особенности, связанные с декомпозицией исходного численного метода,
организацией коммуникаций и объединением задач параллельного
алгоритма. Приведены примеры алгоритмов для задач математической
физики, решаемых посредством теории разностных схем.
Учебное пособие рекомендуется для магистрантов по курсу лекций
«Современные методы и алгоритмы решения сложных задач на
суперкомпьютерах» в рамках магистерской программы «Технологии
параллельного программирования и суперкомпьютинг» по направлению
01400.68 – «Прикладная математика и информатика» и может быть
полезно при выполнении курсовых работ, дипломных проектов и
подготовке к экзаменам.
Подготовлено на кафедре прикладной математики.
© Самарский государственный
аэрокосмический университет, 2010
2
Стр.2
ОГЛАВЛЕНИЕ
Введение
1 Распараллеливание последовательных программ
1.1 Распараллеливание ациклических участков программ
1.2 Распараллеливание ациклических участков программ
1.3 Распараллеливание выражений
2 Синтез параллельных алгоритмов
2.1 Понятие параллельного алгоритма
2.1 Восходящий подход к синтезу параллельных алгоритмов
2.3 Нисходящий подход к синтезу параллельных алгоритмов
2.4 Характеристики параллельных вычислительных
процессов и алгоритмов
3. Параллельные алгоритмы решения разностных уравнений
3.1 Параллельные алгоритмы решения сеточных уравнений
явных разностных схем
3.2 Параллельные алгоритмы решения трехдиагональных
сеточных уравнений неявных разностных схем
Заключение
Литература
4
7
7
15
27
34
34
36
59
65
74
74
84
103
104
3
Стр.3