Лукьяненко Д.В. Практика параллельного программирования с использованием MPI

URSS. 2024. 330 с. ISBN 978-5-00237-034-4.

Серия: ФУНДАМЕНТ БУДУЩЕГО: Юбилейная серия в честь 270-летия МГУ имени М.В. Ломоносова

Серия: Классический учебник МГУ

Белая офсетная бумага

Аннотация

Целью учебного курса является знакомство читателей с практикой параллельного программирования при реализации параллельных алгоритмов решения вычислительно ёмких научных задач. Особенности программной реализации изучаемых алгоритмов демонстрируются с использованием языка программирования Python и пакета mpi4py, который для организации взаимодействия различных вычислительных процессов позволяет использовать технологию передачи сообщений MPI.... (Подробнее)

Оглавление

Предисловие				9
Лекция 1. Введение в основы MPI				14
1.1. Последовательная реализация умножения матрицы на вектор				16
1.2. Параллельный алгоритм умножения матрицы на вектор				18
1.3. Программная реализация параллельного алгоритма умножения матрицы на вектор				19
1.3.1. Модели и технологии параллельного программирования				19
1.3.2. Основы MPI — простейшая тестовая программа				19
1.3.3. Считывание из файла входных параметров и их распределение по различным процессам				22
1.3.4. Знакомство с базовыми функциями передачи/приёма сообщений между отдельными процессами Send и Recv				24
1.3.5. Знакомство с функцией коллективного взаимодействия процессов Bcast				29
1.3.6. Считывание из файла матрицы и её распределение по различным процессам				31
1.3.7. Считывание из файла вектора и распределение по различным процессам				34
1.3.8. Параллельное умножение матрицы на вектор				35
1.3.9. Сбор частей массива с разных процессов в единый массив				37
1.3.10. Оптимизация сбора информации с помощью функции Probe				38
1.3.11. Знакомство с функциями коллективного взаимодействия процессов Gather(v) и Scatter(v)				41
1.4. Обобщение программы на случай использования произвольного числа процессов				44
1.5. Возможные пути оптимизации программной реализации				50
1.5.1. Упоминание о функциях передачи сообщений Bsend и Rsend				51
Лекция 2. Введение в основы MPI. Продолжение				53
2.1. Последовательная реализация вычисления скалярного произведения векторов				53
2.2. Параллельный алгоритм вычисления скалярного произведения векторов				55
2.3. Программная реализация параллельного алгоритма вычисления скалярного произведения векторов				56
2.3.1. Знакомство с функциями коллективного взаимодействия процессов Reduce и Allreduce				61
2.4. Параллельный алгоритм умножения транспонированной матрицы на вектор				63
2.5. Программная реализация параллельного алгоритма умножения транспонированной матрицы на вектор				64
2.5.1. Знакомство с дополнительными полезными функциями коллективного взаимодействия процессов				68
2.5.2. Знакомство с функцией коллективного взаимодействия процессов Reduce_scatter				68
2.5.3. Знакомство с функцией коллективного взаимодействия процессов Allgatherv				68
2.6. Подведение промежуточных итогов				69
Лекция 3. Параллельная реализация метода сопряжённых градиентов для решения СЛАУ				70
3.1. Последовательная реализация метода сопряжённых градиентов				71
3.2. Параллельная реализация метода сопряжённых градиентов				74
3.2.1. Подготовка на процессах данных для вычислений				74
3.2.2. Вычислительная часть				81
3.2.3. Обсуждение преимуществ и недостатков предложенной программной реализации				85
3.3. Упрощённая параллельная реализация метода сопряжённых градиентов				87
3.3.1. Обсуждение преимуществ и недостатков предложенной программной реализации				91
Лекция 4. Эффективность и масштабируемость параллельных программ				93
4.1. Закон Амдала				93
4.1.1. Теоретический анализ реализованных на предыдущей лекции параллельных алгоритмов				95
4.2. Реальное ускорение программных реализаций параллельных алгоритмов, разобранных на предыдущей лекции				98
4.2.1. Способы определения времени работы параллельных программ				98
4.2.2. Характеристики используемой для тестирования параллельных программ многопроцессорной системы				99
4.2.3. Результаты тестовых вычислений				100
4.3. Эффективность и масштабируемость параллельных программ				104
4.4. Пути повышения эффективности и масштабируемости				107
Лекция 5. Операции с группами процессов и коммуникаторами				109
5.1. Параллельный алгоритм умножения матрицы на вектор в случае двумерного деления матрицы на блоки				110
5.2. Параллельный алгоритм умножения транспонированной матрицы на вектор в случае двумерного деления матрицы на блоки				113
5.3. Группы и коммуникаторы				115
5.3.1. Операции с группами процессов				116
5.3.2. Операции с коммуникаторами				118
5.4. Продвинутая параллельная реализация метода сопряжённых градиентов в случае двумерного деления матрицы системы на блоки				122
5.4.1. Подготовка на процессах данных для вычислений				123
5.4.2. Вычислительная часть				140
5.5. Оценка эффективности и масштабируемости параллельной программы				145
5.6. Обсуждение преимуществ и недостатков предложенной программной реализации				147
Лекция 6. Виртуальные топологии				149
6.1. Виртуальные топологии				149
6.1.1. Знакомство с базовыми функциями по работе с декартовой топологией				150
6.1.2. Знакомство с функциями передачи/приёма сообщений между отдельными процессами Sendrecv и Sendrecv_replace				155
6.2. Параллельная реализация метода сопряжённых градиентов с использованием виртуальной топологии типа двумерного тора				159
6.2.1. Подготовка на процессах данных для вычислений				161
6.2.2. Вычислительная часть				168
6.3. Оценка эффективности и масштабируемости параллельной программы				173
6.4. Обсуждение преимуществ и недостатков предложенной программной реализации				176
Лекция 7. Параллельный вариант метода прогонки для решения СЛАУ с трехдиагональной матрицей				177
7.1. Последовательная реализация метода прогонки				178
7.2. Параллельный вариант метода прогонки				180
7.2.1. Теоретический анализ параллельного алгоритма				185
7.3. Параллельная реализация метода прогонки				186
7.3.1. Подготовка на процессах данных для вычислений				187
7.3.2. Вычислительная часть				190
Лекция 8. Подходы к распараллеливанию алгоритмов решения задач для уравнений в частных производных. Часть 1				197
8.1. Последовательный алгоритм решения задачи для УрЧП, основанный на реализации явной схемы				197
8.2. Программная реализация последовательного алгоритма решения				200
8.3. Параллельный алгоритм решения, основанный на реализации явной схемы				203
8.4. Программная реализация параллельного алгоритма решения				205
8.5. Оценка эффективности и масштабируемости параллельной программы				212
8.6. Обсуждение путей усовершенствования программной реализации				214
Лекция 9. Подходы к распараллеливанию алгоритмов решения задач для уравнений в частных производных. Часть 2				216
9.1. Последовательный алгоритм решения задачи для УрЧП, основанный на реализации неявной схемы				216
9.2. Программная реализация последовательного алгоритма решения				221
9.3. Параллельный алгоритм решения, основанный на реализации неявной схемы				225
9.4. Программная реализация параллельного алгоритма решения				229
9.5. Оценка эффективности и масштабируемости параллельной программы				239
Лекция 10. Подходы к распараллеливанию алгоритмов решения задач для уравнений в частных производных. Часть 3				242
10.1. Последовательный алгоритм решения задачи для двумерного по пространству УрЧП, основанный на реализации явной схемы				242
10.2. Программная реализация последовательного алгоритма решения				245
10.3. Параллельный алгоритм решения, основанный на реализации явной схемы				249
10.4. Программная реализация параллельного алгоритма решения				253
10.5. Оценка эффективности и масштабируемости параллельной программы				265
10.6. Обсуждение путей усовершенствования программной реализации				267
Лекция 11. Асинхронные операции				270
11.1. Тупиковые ситуации и последовательный обмен сообщениями вместо одновременного				270
11.2. Знакомство с функциями передачи/приёма сообщений между отдельными процессами без блокировки Isend и Irecv				275
11.3. Пересылка сообщений на фоне вычислений				280
11.4. Возможности стандарта MPI-3: операции коллективного взаимодействия процессов без блокировки				285
Лекция 12. Отложенные запросы на взаимодействие				286
12.1. Многократная пересылка одинаково структурированных данных				286
12.2. Знакомство с функциями формирования отложенных запросов на взаимодействия Send_init и Recv_init				289
12.3. Усовершенствование программных реализаций решения задач для уравнений в частных производных				293
12.4. Усовершенствование одной из программных реализаций метода сопряжённых градиентов				297
12.5. Возможности стандарта MPI-4: коллективные отложенные запросы на взаимодействие				299
Лекция 13. Технологии гибридного параллельного программирования				301
13.1. Типовые конфигурации современных вычислительных систем				301
13.2. Тестовый пример				305
13.3. Модификация примера с использованием технологии OpenMP				306
13.4. Модификация примера с использованием технологии CUDA				308
13.5. Оценка эффективности и масштабируемости предложенных программных реализаций				311
Лекция 14. Основные причины плохой масштабируемости параллельных программ				315
14.1. Причины плохой масштабируемости параллельных программ				316
14.1.1. Точный порядок приёма данных				316
14.1.2. Одновременная пересылка большого количества данных				319
14.1.3. Разделение этапов счёта и пересылок				321
14.1.4. Плохое соответствие топологии вычислений и сетевой топологии				322
14.1.5. Недостаточная пропускная способность PCI для работы с GPU				323
14.1.6. Неправильные системные настройки при запуске гибридных программ				324
14.2. Итоговые общие рекомендации				324
Литература				326

Об авторе

Лукьяненко Дмитрий Витальевич

Кандидат физико-математических наук, доцент кафедры математики отделения прикладной математики физического факультета Московского государственного университета имени М. В. Ломоносова. Окончил физический факультет МГУ в 2007 г. (специальность — «физика», специализация — «математическая физика»). В 2011 г. защитил кандидатскую диссертацию по специальности «Математическое моделирование, численные методы и комплексы программ». Оставшись работать на кафедре математики, проводит активную научную и преподавательскую деятельность. Специалист в области разработки численных методов решения обратных и некорректно поставленных задач с использованием суперкомпьютерных технологий.