Курс "Параллельные вычисления"  с одной стороны посвящён рассмотрению базовых параллельных алгоритмов решения вычислительно ёмких прикладных задач математической физики, а с другой стороны -  их практической программной реализации. При этом программной реализации в курсе уделяется подавляющая часть времени. Это связано с тем, что зачастую, даже если параллельный алгоритм решения какой-либо задачи является достаточно простым и интуитивно понятным, его программная реализация может содержать огромное количество различных нюансов. Их разбору и уделяется основное время в курсе. При этом, показывается, что возможности используемых для расчётов многопроцессорных систем зачастую требуют и существенной модификации параллельных алгоритмов с целью их наиболее эффективной практической программной реализации.

Особенности программной реализации изучаемых алгоритмов демонстрируются с использованием языка программирования Python и пакета mpi4py, который для организации взаимодействия различных вычислительных процессов позволяет использовать технологию передачи сообщений MPI. Технология MPI на данный момент является основным средством программирования в параллельных вычислениях с распределённой памятью. При этом примеры программ строятся таким образом, что они могут быть легко переписаны с использованием языков программирования C/С++/Fortran.

Структура курса следующая. В лекциях 1-3 на примере реализации одного итерационного метода решения систем линейных алгебраических уравнений (СЛАУ) разбираются простейшие параллельные алгоритмы умножения матрицы на вектор, транспонирования матрицы и скалярного произведения векторов. Изучаемые на этих лекциях MPI-функции предоставляют достаточно широкий базовый функционал, который позволяет реализовывать большинство параллельных алгоритмов, которые могут встретиться на практике. На лекции 4 обсуждаются вопросы эффективности и масштабируемости параллельных программ. На примере реализованных на лекции 3 программ решения СЛАУ делается вывод о необходимости существенной модификации уже реализованных параллельных алгоритмов с целью понижения накладных расходов по взаимодействию вычислительных узлов. На лекции 5 рассматриваются более продвинутый алгоритм умножения матрицы на вектор, который естественным образом приводит к необходимости использования дополнительных групп процессов и коммуникаторов.  В лекции 6 рассматриваются вопросы использования виртуальных топологий, которые в определённых ситуациях могут ещё более существенным образом понизить накладные расходы по взаимодействию вычислительных узлов. В лекции 7 рассматривается параллельный вариант метода прогонки для решения СЛАУ с трёхдиагональной матрицей, как пример распараллеливания алгоритма, базовая последовательная версия которого не распараллеливается, но после определённой модификации которой появляется возможность реализовать её параллельную версию. Лекции 8-10 посвящены базовым подходам распараллеливания алгоритмов решения задач для уравнений в частных производных. При программной реализации этих подходов активно используются уже изученные ранее в курсе инструменты (в частности, виртуальные топологии). На лекциях 11-12 обсуждаются более тонкие вопросы оптимизации – асинхронные операции и отложенные запросы на взаимодействие. Эти операции применяются для модификации некоторых ранее написанных программ, что ещё повышает эффективность параллельных программных реализаций. Лекция 13 посвящена основам гибридных технологий параллельного программирования MPI + OpenMP, MPI + CUDA и MPI + CUDA + OpenMP. В Лекции 14 подводятся итоги и обсуждаются наиболее распространённые причины плохой масштабируемости параллельных программ.

В итоге, демонстрируется, что комбинация всего множества рассмотренных в курсе инструментов позволяет создавать достаточно эффективные программные реализации алгоритмов параллельных вычислений.

Для проведения тестовых расчётов задач курса используется персональный компьютер с многоядерным процессором. Для обсуждения вопросов эффективности и масштабируемости программных реализаций используется суперкомпьютер «Ломоносов-2» Центра коллективного пользования сверхвысокопроизводительными вычислительными ресурсами МГУ имени М.В. Ломоносова.

ЛИСТИНГИ ПРОГРАММ: https://disk.yandex.ru/d/BNkYO...

Список всех тем лекций

Лекция 1. Введение в основы MPI на Python.
О курсе Об MPI на Python и пакете mpi4py Первая "большая" задача: итерационный метод решения огромной переопределённой системы линейных алгебраических уравнений с плотно заполненной матрицей План реализации параллельного алгоритма решения этой задачи на ближайшие занятия Первая подзадача: параллельный алгоритм умножения матрицы на вектор Модели и технологии параллельного программирования Основы MPI: простейшая тестовая программка Знакомство с простейшими функциями взаимодействия между отдельными процессами: Send и Recv Знакомство с функцией коллективного взаимодействия процессов Bcast для широковещательной рассылки данных Подготовка данных для расчётов на различных процессах Параллельная часть программы, реализующей параллельный алгоритм умножения матрицы на вектор Оптимизация сбора информации с помощью функции Probe Обобщение программы на случай несогласованного числа входных данных и числа процессов, использующихся при расчётов Знакомство с функцией коллективного взаимодействия процессов Gather для сбора информации на одном процессе Финальная версия программы, реализующей параллельный алгоритм умножения матрицы на вектор Знакомство с функциями коллективного взаимодействия процессов Scattter и Scatterv для распределения информации с одного процесса по всем остальным Функции передачи сообщений между отдельными процессами типа Bsend, Ssend и Rsend

Лекция 2. Введение в основы MPI на Python: продолжение.
План занятия Последовательная версия программы, реализующей скалярное произведение векторов Параллельный алгоритм скалярного произведения векторов Параллельная версия программы, реализующей скалярное произведение векторов Знакомство с функциями коллективного взаимодействия процессов Reduce и Allreduce для объединения элементов Параллельный алгоритм умножения транспонированной матрицы на вектор Параллельная версия программы, реализующей умножение транспонированной матрицы на вектор

Лекция 3. Параллельная реализация метода сопряжённых градиентов для решения СЛАУ.
Постановка задачи Последовательная версия программы, реализующей решение СЛАУ с помощью метода сопряжённых градиентов Параллельная версия программы, реализующей решение СЛАУ с помощью метода сопряжённых градиентов Параллельная версия функции, реализующей метод сопряжённых градиентов Знакомство с функциями коллективного взаимодействия процессов Allgatherv и Reduce_Scatter для сбора и объединения элементов массивов Обсуждение преимуществ и недостатков предложенной программной реализации Упрощённая параллельная версия программы, реализующей решение СЛАУ с помощью метода сопряжённых градиентов Замечание о версии алгоритма решения СЛАУ с регуляризацией

Лекция 4. Эффективность и масштабируемость параллельных программ.
Закон Амдала Оценки предельно возможного ускорения параллельных алгоритмов, разобранных на Лекции 3 Реальное ускорение программных реализаций параллельных алгоритмов, разобранных на Лекции 3 Эффективность параллельных программ Масштабируемость параллельных программ Проблемы оценки эффективности и масштабируемости Упоминание о самых проблемных MPI-функциях, использование которых снижает эффективность программной реализации рассмотренных ранее алгоритмов

Лекция 5. Операции с группами процессов и коммуникаторами.
Параллельный алгоритм умножения матрицы на вектор в случае двумерного деления матрицы на блоки Знакомство с функцией Split, позволяющей разбить коммуникатор на несколько новых коммуникаторов Особенности работы функций коллективного взаимодействия процессов в случае, когда процессы одновременно входят в различные коммуникаторы Базовые операции с группами процессов Программа, реализующая параллельный алгоритм умножения матрицы на вектор в случае двумерного деления матрицы на блоки Новая параллельная версия программы, реализующей решение СЛАУ с помощью метода сопряжённых градиентов

Лекция 6. Виртуальные топологии.
Декартовы топологии Базовые функции для работы с декартовой топологией Знакомство с функциями взаимодействия между отдельными процессами Sendrecv и Sendrecv_replace Применение декартовой топологии типа двумерного тора для оптимизации взаимодействия процессов в параллельной версии программы, реализующей решение СЛАУ с помощью метода сопряжённых градиентов

Лекция 7. Параллельный вариант метода прогонки для решения СЛАУ с трехдиагональной матрицей.
Последовательный алгоритм Параллельный алгоритм Особенности программной реализации К вопросу об эффективности распараллеливания

Лекция 8. Подходы к распараллеливанию алгоритмов решения задач для уравнений в частных производных.
Пример одномерной по пространству начально-краевой задачи для уравнения в частных производных параболического типа Последовательный алгоритм решения, основанный на реализации явной схемы Программная реализация последовательного алгоритма решения Параллельный алгоритм решения, основанный на реализации явной схемы Программная реализация параллельного алгоритма решения Другой вариант параллельного алгоритма решения Программная реализация другого параллельного алгоритма решения Сравнение эффективности реализованных алгоритмов

Лекция 9. Подходы к распараллеливанию алгоритмов решения задач для уравнений в частных производных.
Пример одномерной по пространству начально-краевой задачи для уравнения в частных производных параболического типа Последовательный алгоритм решения, основанный на реализации неявной схемы Программная реализация последовательного алгоритма решения Параллельный алгоритм решения, основанный на реализации неявной схемы Программная реализация параллельного алгоритма решения Обсуждение эффективности программной реализации

Лекция 10. Подходы к распараллеливанию алгоритмов решения задач для уравнений в частных производных.
Пример двумерной по пространству начально-краевой задачи для уравнения в частных производных параболического типа Последовательный алгоритм решения, основанного на реализации явной схемы Программная реализация последовательного алгоритма решения Параллельный алгоритм решения в случае одномерного деления пространственной области на блоки Программная реализация параллельного алгоритма решения Параллельный алгоритм решения в случае двумерного деления пространственной области на блоки Программная реализация параллельного алгоритма решения Особенности использования виртуальных топологий типа "декартова сетка" Обсуждение эффективности двух рассмотренных параллельных программных реализаций

Лекция 11. Тонкая оптимизация: асинхронные операции.
Пример тупиковой ситуации (deadlock) при использовании блокирующих функций приёма-передачи сообщений Знакомство с простейшими функциями асинхронного взаимодействия между отдельными процессами: Isend и Irecv Особенности работы с асинхронными операциями приема-передачи сообщений

Лекция 12. Тонкая оптимизация: отложенные запросы на взаимодействие.
Знакомство с функциями формирования отложенных запросов на взаимодействие Send_init и Recv_init Пример использования отложенных запросов на взаимодействие при реализации параллельного алгоритма решения задачи для уравнения в частных производных Обсуждение эффективности программной реализации Пример использования отложенных запросов на взаимодействие при реализации параллельного алгоритма решения СЛАУ с помощью метода сопряжённых градиентов Обсуждение эффективности программной реализации

Лекция 13. Технологии гибридного параллельного программирования.
О конфигурации распространённых многопроцессорных систем Конфигурация суперкомпьютера "Ломоносов-2" Самые распространённые технологии параллельного программирования Пример умножения матрицы на вектор в Python'е с помощью технологии OpenMP Реализация метода сопряжённых градиентов с помощью гибридной технологии MPI + OpenMP Об особенностях запуска на реальных суперкомпьютерах Обсуждение эффективности и масштабируемости программной реализации с помощью MPI + OpenMP Пример умножения матрицы на вектор в Python'е с помощью технологии CUDA (пакет cupy) Реализация метода сопряжённых градиентов с помощью гибридной технологии MPI + CUDA Реализация метода сопряжённых градиентов с помощью гибридной технологии MPI + CUDA + OpenMP Обсуждение эффективности и масштабируемости программной реализации с помощью MPI + CUDA + OpenMP

Лекция 14. Причины плохой масштабируемости параллельных программ.
Подведение итогов Наиболее распространённые причины плохой масштабируемости параллельных программ Поэлементная пересылка данных вместо блочной Последовательный обмен сообщениями вместо одновременного Неиспользование преимуществ асинхронных операций Одновременная пересылка большого количества данных Разделение этапов счёта и пересылок Плохое соответствие топологии вычислений и сетевой топологии Недостаточная пропускная способность системной шины для работы с GPU Работа не через общую память в рамках одного узла Общие рекомендации по написанию параллельных программ