Параллельное программирование для мультиядерных и кластерных систем

Томас Раубер, Гудула Рюнгер
Параллельное  
программирование  
для мультиядерных  
и кластерных систем

Thomas Rauber • Gudula Rünger
Parallel  
Programming  
for Multicore  
and Cluster Systems
Third Edition

Томас Раубер • Гудула Рюнгер
Параллельное 
программирование 
для мультиядерных 
и кластерных систем
Москва, 2024

УДК	 004.42:004.272
ББК 32.973
Р25
Раубер Т., Рюнгер Г.
Р25 	 Параллельное программирование для мультиядерных и кластерных систем / 
пер. с англ. А. В. Снастина. – М.: ДМК Пресс, 2024. – 632 с.: ил. 
ISBN 978-5-93700-261-7
В книге представлены методы, необходимые для разработки эффективных 
программ для мультиядерных процессоров, для параллельных кластерных систем 
или суперкомпьютеров как с распределенным, так и с совместно используемым 
адресным пространством. Книга охватывает все области параллельных вычислений. Для каждого алгоритма обсуждаются разные варианты распараллеливания 
с использованием различных методов и стратегий. В конце глав приведены 
упражнения для закрепления изученной темы.
Издание предназначено разработчикам параллельных архитектур, а также 
может быть полезно преподавателям и студентам.
УДК  004.42:004.272
ББК  32.973
First published in English under the title Parallel Programming; for Multicore and Cluster 
Systems by Thomas Rauber and Gudula Rünger, edition: 3 This edition has been translated 
and published under licence from Springer Nature Switzerland AG. Springer Nature Switzerland 
AG takes no responsibility and shall not be made liable for the accuracy of the translation.
Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения 
владельцев авторских прав.
ISBN 978-3-031-28923-1 (англ.) 	
©  Thomas Rauber, Gudula Rünger, 
Springer Nature Switzerland AG, 
2023
ISBN 978-5-93700-261-7 (рус.) 	
©  Перевод, оформление, издание,  
ДМК Пресс, 2024

Содержание
От издательства.......................................................................................................10
Предисловие.............................................................................................................11
Глава 1. Введение....................................................................................................14
1.1. Традиционное использование параллелизма.................................................14
1.2. Параллелизм в современном аппаратном обеспечении...............................16
1.3. Основные концепции параллельного программирования...........................18
1.4. Краткий обзор содержания книги.....................................................................20
Глава 2. Архитектура параллельного компьютера......................................23
2.1. Архитектура процессора и тенденции развития технологии.......................24
2.2. Потребление электроэнергии в процессорах..................................................29
2.3. Время доступа к памяти......................................................................................32
2.3.1. Время доступа к DRAM.................................................................................33
2.3.2. Многопоточность для сокрытия времени доступа к памяти.................34
2.3.3. Кеши для уменьшения среднего времени доступа к памяти................35
2.4. Классификация параллельных архитектур Флинна.......................................36
2.5. Организация памяти параллельных компьютеров........................................38
2.5.1. Компьютеры с распределенной памятью.................................................39
2.5.2. Компьютеры с совместно используемой памятью..................................43
2.6. Параллелизм на уровне потоков.......................................................................47
2.6.1. Одновременная многопоточность.............................................................48
2.6.2. Мультиядерные процессоры.......................................................................49
2.6.3. Архитектура мультиядерных процессоров...............................................51
2.7. Соединительные сети..........................................................................................57
2.7.1. Свойства соединительных сетей................................................................59
2.7.2. Сети прямого соединения............................................................................61
2.7.3. Варианты встраивания.................................................................................67
2.7.4. Динамические соединительные сети........................................................70
2.8. Маршрутизация и коммутация..........................................................................76
2.8.1. Алгоритмы маршрутизации.......................................................................77
2.8.2. Маршрутизация в сети омега......................................................................85
2.8.3. Коммутация...................................................................................................88
2.8.4. Механизмы управления потоком...............................................................96
2.9. Иерархия кешей и памяти..................................................................................97
2.9.1. Характеристики кешей................................................................................99
2.9.2. Стратегии записи........................................................................................108
2.9.3. Согласованность кеша................................................................................110

6    Содержание
2.9.4. Согласованность памяти............................................................................120
2.10. Примеры аппаратного параллелизма...........................................................126
2.10.1. Архитектуры Intel Cascade Lake и Ice Lake............................................127
2.10.2. Список Top500...........................................................................................131
2.11. Упражнения к главе 2......................................................................................132
Глава 3. Модели параллельного программирования...............................137
3.1. Модели для параллельных систем...................................................................138
3.2. Параллельный режим в программах...............................................................141
3.3. Уровни распараллеливания..............................................................................144
3.3.1. Распараллеливание на уровне машинных инструкций........................144
3.3.2. Распараллеливание по данным................................................................146
3.3.3. Распараллеливание цикла.........................................................................148
3.3.4. Функциональное распараллеливание.....................................................151
3.3.5. Явное и неявное представление распараллеливания...........................153
3.3.6. Паттерны параллельного программирования.......................................156
3.4. SIMD-вычисления..............................................................................................162
3.4.1. Выполнение векторных операций...........................................................162
3.4.2. SIMD-инструкции.......................................................................................164
3.5. Распределения данных для массивов.............................................................166
3.5.1. Распределение данных для одномерных массивов..............................167
3.5.2. Распределение данных для двумерных массивов.................................169
3.5.3. Параметризованное распределение данных..........................................170
3.6. Обмен информацией.........................................................................................171
3.6.1. Совместно используемые переменные...................................................171
3.6.2. Операции обмена данными......................................................................173
3.7. Вычисление произведения матрицы на вектор в параллельном  
режиме........................................................................................................................181
3.7.1. Параллельное вычисление скалярных произведений..........................182
3.7.2. Параллельное вычисление линейных комбинаций..............................185
3.8. Процессы и потоки............................................................................................186
3.8.1. Процессы......................................................................................................188
3.8.2. Потоки..........................................................................................................189
3.8.3. Механизмы синхронизации......................................................................194
3.8.4. Разработка эффективных и корректных потоковых программ..........197
3.9. Перспективные методики параллельного программирования..................200
3.10. Упражнения к главе 3......................................................................................203
Глава 4. Анализ производительности параллельных программ..........207
4.1. Оценка производительности компьютерных систем..................................208
4.1.1. Оценка производительности ЦП..............................................................209
4.1.2. MIPS и MFLOPS............................................................................................211
4.1.3. Производительность процессоров в иерархии памяти........................213
4.1.4. Программы эталонных тестов..................................................................215
4.2. Метрики производительности для параллельных программ.....................221
4.2.1. Время выполнения в параллельном режиме и затраты.......................221

Содержание    7
4.2.2. Коэффициент ускорения вычислений и эффективность.....................222
4.2.3. Слабая и сильная масштабируемость......................................................226
4.3. Измерение энергозатрат и метрики энергии................................................232
4.3.1. Методики измерения производительности и потребления  
энергии...................................................................................................................233
4.3.2. Моделирование потребления мощности и энергии для DVFS............239
4.3.3. Метрики энергопотребления для параллельных программ................240
4.4. Асимптотическое время для глобальных операций обмена данными.....243
4.4.1. Реализация глобальных операций обмена данными............................244
4.4.2. Операции обмена данными в гиперкубе................................................251
4.4.3. Операции обмена данными в полном двоичном дереве.....................260
4.5. Анализ времени параллельного выполнения...............................................264
4.5.1. Скалярное произведение в параллельном режиме...............................264
4.6. Параллельные вычислительные модели........................................................269
4.6.1. Модель PRAM...............................................................................................269
4.6.2. Модель BSP...................................................................................................273
4.6.3. Модель LogP.................................................................................................275
4.7. Планирование и разделение на блоки цикла.................................................278
4.7.1. Планирование цикла..................................................................................279
4.7.2. Разбиение цикла на блоки.........................................................................290
4.8. Упражнения.........................................................................................................293
Глава 5. Программирование передачи сообщений..................................299
5.1. Введение в MPI...................................................................................................300
5.1.1. MPI-операции двухточечного обмена данными...................................303
5.1.2. Взаимоблокировки при двухточечном обмене данными....................308
5.1.3. Неблокирующие операции двухточечного обмена данными.............311
5.1.4. Режимы обмена данными.........................................................................315
5.2. Групповые операции обмена данными..........................................................318
5.2.1. Групповые операции обмена данными в MPI........................................318
5.2.2. Взаимоблокировки при выполнении групповых операций  
обмена данными...................................................................................................334
5.2.3. Неблокирующие групповые операции обмена данными....................337
5.3. Группы процессов и коммуникаторы.............................................................339
5.3.1. Группы процессов в MPI............................................................................340
5.3.2. Топологии процессов.................................................................................345
5.3.3. Хронометраж и удаление процессов.......................................................350
5.4. Дополнительные темы......................................................................................351
5.4.1. Динамическая генерация и управление процессами...........................351
5.4.2. Односторонний обмен данными..............................................................354
5.5. Упражнения к главе 5........................................................................................364
Глава 6. Многопоточное программирование..............................................369
6.1. Программирование с использованием Pthreads...........................................370
6.1.1. Создание и объединение потоков............................................................372
6.1.2. Согласование потоков с по-мощью Pthreads...........................................376

8    Содержание
6.1.3. Условные переменные...............................................................................384
6.1.4. Расширенный механизм блокировки......................................................388
6.1.5. Однократная инициализация...................................................................390
6.2. Паттерны параллельного программирования с использованием  
Pthreads.......................................................................................................................391
6.2.1. Реализация пула задач...............................................................................391
6.2.2. Распараллеливание методом конвейеризации.....................................397
6.2.3. Реализация модели клиент–сервер.........................................................404
6.3. Дополнительные функциональные возможности Pthreads........................409
6.3.1. Атрибуты потока и отмена его выполнения...........................................409
6.3.2. Планирование потоков с по-мощью Pthreads.........................................416
6.3.3. Инверсия приоритета................................................................................420
6.3.4. Специализированные данные потоков...................................................424
6.4. Java Threads.........................................................................................................426
6.4.1. Создание потоков в Java............................................................................426
6.4.2. Синхронизация потоков Java....................................................................430
6.4.3. Ожидание и оповещение...........................................................................439
6.4.4. Расширенные паттерны синхронизации................................................445
6.4.5. Планирование потоков в Java...................................................................450
6.4.6. Пакет java.util.concurrent......................................................................451
6.5. OpenMP................................................................................................................458
6.5.1. Директивы компилятора...........................................................................460
6.5.2. Подпрограммы среды выполнения.........................................................468
6.5.3. Согласование и синхронизация потоков................................................469
6.5.4. Модель задач OpenMP................................................................................475
6.6. Упражнения к главе 6........................................................................................481
Глава 7. Программирование GPU общего назначения.............................486
7.1. Архитектура графических процессоров..........................................................487
7.2. Введение в программирование с использованием CUDA............................494
7.3. Синхронизация и совместно используемая память.....................................500
7.4. Планирование потоков в CUDA........................................................................505
7.5. Эффективный доступ к памяти и методика тайлинга..................................507
7.6. Введение в OpenCL.............................................................................................513
7.7. Упражнения к главе 7.........................................................................................516
Глава 8. Алгоритмы решения систем линейных уравнений..................518
8.1. Метод исключения Гаусса.................................................................................519
8.1.1. Метод исключения Гаусса и LU-разложение матрицы.........................520
8.1.2. Параллельная реализация с циклическим по строкам  
распределением данных......................................................................................523
8.1.3. Параллельная реализация с распределением в шахматном  
порядке...................................................................................................................527
8.1.4. Анализ времени выполнения в параллельном режиме........................534
8.2. Прямые методы решения систем линейных уравнений с ленточной 
структурой..................................................................................................................539

Содержание    9
8.2.1. Дискретизация уравнения Пуассона.......................................................539
8.2.2. Трехдиагональные системы......................................................................545
8.2.3. Обобщение для ленточных матриц.........................................................557
8.2.4. Решение дискретизированного уравнения Пуассона...........................559
8.3. Итеративные методы решения систем линейных уравнений....................562
8.3.1. Стандартные итеративные методы.........................................................563
8.3.2. Параллельная реализация итерационного метода Якоби....................567
8.3.3. Параллельная реализация итерационного метода Гаусса–Зейделя....569
8.3.4. Итерационный метод Гаусса–Зейделя для разреженных систем.......571
8.3.5. Красно-черное упорядочение...................................................................574
8.4. Метод сопряженных градиентов.....................................................................580
8.4.1. Последовательный метод сопряженных градиентов............................581
8.4.2. Параллельная реализация метода сопряженных градиентов.............583
8.5. Разложение Холецкого для разреженных матриц........................................588
8.5.1. Последовательный алгоритм....................................................................588
8.5.2. Схема хранения для разреженных матриц.............................................594
8.5.3. Реализация для совместно используемых переменных.......................596
8.6. Упражнения к главе 8........................................................................................602
Список литературы...............................................................................................606
Предметный указатель........................................................................................618

От издательства
Отзывы и пожелания
Мы всегда рады отзывам наших читателей. Расскажите нам, что вы ду-маете 
об этой книге – что понравилось или, может быть, не понравилось. Отзывы 
важны для нас, чтобы выпускать книги, которые будут для вас максимально 
полезны.
Вы можете написать отзыв на нашем сайте www.dmkpress.com, зайдя на 
страницу книги и оставив комментарий в разделе «Отзывы и рецензии». 
Также можно послать письмо главному редактору по адресу dmkpress@gmail.
com; при этом укажите название книги в теме письма. 
Если вы являетесь экспертом в какой-либо области и заинтересованы в написании новой книги, заполните форму на нашем сайте по адресу http://
dmkpress.com/authors/publish_book/ или напишите в издательство по адресу 
dmkpress@gmail.com.
Список опечаток
Хотя мы приняли все возможные меры для того, чтобы обеспечить высокое качество наших текстов, ошибки все равно случаются. Если вы найдете 
ошибку в одной из наших книг, мы будем очень благодарны, если вы сообщите о ней главному редактору по адресу dmkpress@gmail.com. Сделав это, 
вы избавите других читателей от недопонимания и поможете нам улучшить 
последующие издания этой книги. 
Нарушение авторских прав
Пиратство в интернете по-прежнему остается насущной проблемой. Издательство «ДМК Пресс» очень серьезно относится к вопросам защиты авторских прав 
и лицензирования. Если вы столкнетесь в интернете с незаконной публикацией 
какой-либо из наших книг, пожалуйста, пришлите нам ссылку на интернет-ресурс, чтобы мы могли применить санкции.
Ссылку на подозрительные материалы можно прислать по адресу электронной почты dmkpress@gmail.com.
Мы высоко ценим любую помощь по защите наших авторов, благодаря 
которой мы можем предоставлять вам качественные материалы.