Рекомендуем
Книга
Алгоритмы коллективных операций стандарта MPI
288 стр.
Формат 60х90/16 (145x215 мм)
Исполнение: в твердом переплете
ISBN ISBN 978-5-9912-1149-9
ББК 22.18
УДК 510.5:004.421
Аннотация
В монографии изложены алгоритмы коллективных операций стандарта MPI (Message Passing Interface), эффективность которых в значительной степени влияет на производительность параллельных программ для высокопроизводительных вычислительных систем с распределенной памятью. Основная часть включает описание архитектурно-независимых алгоритмов на базе примитивов двусторонних обменов. Изложены способы реализации неблокирующих коллективных операций: построение расписаний и продвижения их выполнения. Отдельный раздел посвящён подходам к построению алгоритмов для систем с общей памятью. Описаны методы реализации коллективных операций для иерархических систем с многоуровневой организацией памяти и коммуникационных сетей. Для гибридных систем, которые нашли широкое применение для распределенного машинного обучения, приведены способы построения структурно-ориентированных алгоритмов коллективных обменов.
Для специалистов, работающих в области архитектуры вычислительных систем и коммуникационных библиотек для систем параллельного программирования, будет полезна аспирантам, магистрантам и студентам старших курсов соответствующих специальностей.
В монографии изложены алгоритмы коллективных операций стандарта MPI (Message Passing Interface), эффективность которых в значительной степени влияет на производительность параллельных программ для высокопроизводительных вычислительных систем с распределенной памятью. Основная часть включает описание архитектурно-независимых алгоритмов на базе примитивов двусторонних обменов. Изложены способы реализации неблокирующих коллективных операций: построение расписаний и продвижения их выполнения. Отдельный раздел посвящён подходам к построению алгоритмов для систем с общей памятью. Описаны методы реализации коллективных операций для иерархических систем с многоуровневой организацией памяти и коммуникационных сетей. Для гибридных систем, которые нашли широкое применение для распределенного машинного обучения, приведены способы построения структурно-ориентированных алгоритмов коллективных обменов.
Для специалистов, работающих в области архитектуры вычислительных систем и коммуникационных библиотек для систем параллельного программирования, будет полезна аспирантам, магистрантам и студентам старших курсов соответствующих специальностей.
Оглавление
Предисловие
Введение
Глава 1. Основные понятия стандарта MP
1.1. Коммуникаторы
1.2. Блокирующие операции Send/Recv
1.3. Неблокирующие операции Isend/Irecv
1.4. Поиск поступивших сообщений
1.4.1. Протокол Eager
1.4.2. Протокол Randezvous
1.5. Структура библиотек MPI
1.6. Подходы к реализации алгоритмов коллективных операций
1.6.1. Aлгоритмы без учета топологии коммуникационной сети
1.6.2. Aлгоритмы для фиксированной сетевой топологии
1.6.3. Aлгоритмы с аппаратной реализацией
1.7. Классификация коллективных операций
1.7.1. Блокирующие коллективные операции
1.7.2. Неблокирующие коллективные операции
1.7.3. Коллективные операции с постоянными значениями аргументов
1.7.4. Коллективные операции для виртуальных топологий процессов
1.8. Модели параллельных вычислений
1.8.1. Модель вычислительной системы
1.8.2. Модель Хокни
1.8.3. Модель LogP
1.8.4. Модель LogGP
Глава 2. Широковещательная передача
2.1. Операция Bcast
2.2. Aлгоритмы с линейной сложность
2.3. Aлгоритм параллельных цепочек
2.4. Aлгоритм параллельных цепочек переменной длины
2.5. Aлгоритм бинарного дерева
2.6. Aлгоритм оптимального k-ичного дерева
2.7. Aлгоритм биномиального дерева
2.8. Aлгоритм k-номиального дерева
2.9. Конвейерный алгоритм с сегментацией сообщения
2.10. Aлгоритм бинарного дерева с сегментацией сообщения
2.11. Aлгоритм на основе Scatter и Allgather
2.12. Aлгоритмы оптимальные по пропускной способности
2.13. Операция Scatter
2.13.1. Линейный алгоритм
2.13.2. Aлгоритм биномиального дерева
Глава 3. Широковещательныйприем Gather
3.1. Aлгоритм плоского дерева
3.2. Aлгоритм биномиального дерева
Глава 4. Операция Allgather
4.1. Aлгоритм рекурсивного удваивания
4.2. Обобщенный алгоритм рекурсивного удваивания
4.3. Aлгоритм рекурсивного удваивания для произвольного чиcла процессов
4.4. Aлгоритм рекурсивного деления пополам
4.5. Aлгоритм Брука
4.6. Обобщение алгоритма Брука
4.7. Aлгоритм Sparbit
4.8. Кольцевой алгоритм
4.9. Обзор алгоритмов
Глава 5. Корневая редукция Reduce
5.1. Линейный алгоритм
5.2. Конвейерный алгоритм
5.3. Aлгоритм параллельных цепочек
5.4. Aлгоритм биномиального дерева для коммутативной операции
5.4.1. Структура дерева обменов
5.4.2. Aнализ эффективности алгоритма
5.4.3. Левостороннее дерево обменов
5.5. Aлгоритм биномиального дерева для некоммутативной операции
5.5.1. Структура дерева обменов
5.5.2. Aнализ эффективности алгоритма
5.6. Aлгоритм бинарного дерева
5.7. Aлгоритм Рабенсейфнера
Глава 6. Глобальная редукция Allreduce
6.1. Кольцевой алгоритм
6.2. Aлгоритм рекурсивного удваивания
6.3. Aлгоритм ReduceScatter-Allgather с рекурсивным удваиванием
6.4. Кольцевой алгоритм ReduceScatter-Allgather
6.5. Сравнение алгоритмов
6.6. Операция Exscan
6.6.1. Aлгоритм рекурсивного удваивания
6.7. Операция Scan
6.7.1. Aлгоритм рекурсивного удваивания
6.8. Операция Reduce-scatter
6.8.1. Aлгоритм деления пополам
6.8.2. Aлгоритм Butterfly
6.8.3. Aлгоритм попарных обменов
Глава 7. Операция Alltoall
7.1. Операция Alltoall Scatter/Gather
7.2. Линейный алгоритм
7.3. Aлгоритм попарных обменов
7.4. Aлгоритм Брука
Глава 8. Барьерная синхронизация
8.1. Операция Barrier
8.2. Линейный алгоритм c центральным счетчиком
8.3. Aлгоритм рекурсивного удваивания
8.4. Рассеивающий алгоритм
Глава 9. Aлгоритмы для систем с общей памятью
9.1. Операция Bcast
9.1.1. Формирование сегмента разделяемой памяти
9.1.2. Шаги алгоритма при вызове Bcast
9.1.3. Оценка времени выполнения алгоритма
9.2. Операция Barrier
9.2.1. Aлгоритм с глобальным счетчиком
9.2.2. Плоское дерево
9.2.3. Плоское дерево Gather/Release
9.2.4. Объединяющее дерево
9.2.5. MCS-барьер
9.2.6. Турнирный алгоритм
9.2.7. Рассеивающий алгоритм
9.2.8. Aлгоритм выбора корня операции Barrier
Глава 10. Иерархические алгоритмы коллективных операций
10.1. Иерархические алгоритмы на базе коммуникаторов
10.1.1. Иерархический алгоритм Bcast
10.1.2. Иерархический алгоритм Barrier
10.1.3. Иерархический алгоритм Reduce
10.1.4. Иерархический алгоритм Allreduce
10.1.5. Иерархический алгоритм Gather
10.1.6. Иерархический алгоритм Allgather
10.1.7. Иерархический алгоритм ReduceScatter
10.1.8. Иерархические алгоритмы Exscan и Scan
10.2. Иерархические алгоритмы с формированием групп процессов
10.2.1. Построение иерархии групп процессов
10.2.2. Aлгоритм операции Reduce
10.2.3. Aлгоритм операции Bcast
10.2.4. Aлгоритм операции Allreduce
10.3. Совмещение операций на разных уровнях иерархии
10.4. Динамическая оптимизация алгоритмов
10.4.1. Графы алгоритмов Allgather
10.4.2. Модель вычислительной системы
10.4.3. Метод оптимизации алгоритмов Allgather
Глава 11. Неблокирующие коллективные операции
11.1. Построение расписания коллективной операции
11.2. Продвижение выполнения операций расписания
11.3. Пути оптимизации расписаний
Глава 12. Коллективные операции для гибридных вычислительных систем
12.1. Aрхитектура гибридных вычислительных систем
12.2. Aлгоритм Allreduce для гибридной системы
12.3. Версия Allreduce с параллельным выполнения операций
Глава 13. Экспериментальная оценка эффективности коллективных операций
13.1. Измерение времени выполнения коллективных операций
13.2. Систематические ошибки измерений
13.3. Измерения с запуском операций по глобальным часам
13.4. Синхронизации показаний часов процессов
14. Приложение
14.1. Функции округления и операций с битами
14.1.1. Функции пол и потолок
14.1.2. Операции с битами
14.2. Деревья
14.2.1. Основные определения
14.2.2. Бинарные деревья
14.2.3. Обходы бинарных деревьев
14.2.4. Биномиальные деревья
Литература
