Параллельные и высокопроизводительные вычисления

Роберт Роби и Джулиана Замора

Параллельные  
и высокопроизводительные  
вычисления

Parallel and  
High Performance  
Computing

SECOND EDITION

ROBERT (BOB) ROBEY
and YULIANA (YULIE) ZAMORA

Параллельные  
и высокопроизводительные  
вычисления

РОБЕРТ РОБИ  
и ДЖУЛИАНА ЗАМОРА

Москва, 2022

УДК004.421
ББК32.972
Р58

РобиР.,ЗамораДж.
Р58Параллельныеи высокопроизводительныевычисления/пер.с англ.А. В. Логунова. –М.:ДМКПресс,2022. –800 с.:ил.ISBN978-5-97060-936-1

Параллельноепрограммированиепозволяетраспределятьзадачиобработкиданныхмеждунесколькимипроцессорами,существенноповышаяпроизводительность.В книгерассказывается,какс минимальнымитрудозатратамиповыситьэффективностьвашихпрограмм.Вынаучитесьоцениватьаппаратныеархитектурыи работатьсостандартнымиинструментамиотрасли,такимикакOpenMPи MPI,освоитеструктурыданныхи алгоритмы,подходящиедлявысокопроизводительныхвычислений,узнаете,какэкономитьэнергиюнамобильныхустройствах,и дажезапуститемасштабнуюсимуляциюцунаминабатарееизGPU-процессоров.
Изданиепредназначенодляопытныхпрограммистов,владеющихязыкомвысокопроизводительныхвычислений,такимкакC,C++илиFortran.

УДК004.421
ББК32.972

OriginalEnglishlanguageeditionpublishedbyManningPublicationsUSA.Russian-languageeditioncopyright©2021byDMKPress.Allrightsreserved.

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

ISBN978-1-6172-9646-8(англ.)©ManningPublications,2021
ISBN978-5-97060-936-1(рус.)©Перевод,оформление,издание,ДМКПресс,2021

Моей жене Пегги, которая поддерживала не только мой путь в области  
высокопроизводительных вычислений, но и нашего сына Джона и дочь Рейчел.  
Научное программирование далеко от ее медицинских знаний,  
но она сопровождала меня и совершила это наше путешествие с самого начала.
Моему сыну Джону и дочери Рейчел, которые вновь разожгли во мне пламя,  
и за ваше многообещающее будущее.
– Боб Роби

Моему мужу Рику, который поддерживал меня всю дорогу,  
спасибо, что брал на себя утренние смены и позволял мне работать по ночам.  
Ты никогда не позволял мне отказываться от самой себя.
Моим родителям и родственникам, спасибо за всю вашу помощь и поддержку.
И моему сыну Дереку за то, что он был одним из моих самых больших  
вдохновителей; ты – вся причина, почему я не просто живу,  
я наслаждаюсь жизнью.
– Джули Замора

Оглавление

 Часть I  ВВЕДЕНИЕ В ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ ................................ 36
 
1  Зачем нужны параллельные вычисления? ................................................ 38

 
2  Планирование под параллелизацию ........................................................... 75

 
3  Пределы производительности и профилирование ............................... 102

 
4  Дизайн данных и модели производительности ..................................... 134

 
5  Параллельные алгоритмы и шаблоны ...................................................... 179

 Часть II  CPU: ПАРАЛЛЕЛЬНАЯ РАБОЧАЯ ЛОШАДКА .................................. 233
 
6  Векторизация: флопы забесплатно ........................................................... 236

 
7  Стандарт OpenMP, который «рулит» .......................................................... 273

 
8  MPI: параллельный становой хребет ........................................................ 328

 Часть III  GPU: РОЖДЕНЫ ДЛЯ УСКОРЕНИЯ ...................................................... 385
 
9  Архитектуры и концепции GPU.................................................................. 389

 
10  Модель программирования GPU ................................................................ 430

 
11  Программирование GPU на основе директив ......................................... 458

 
12  Языки GPU: обращение к основам ............................................................. 510

 
13  Профилирование и инструменты GPU ..................................................... 558

 Часть IV  ЭКОСИСТЕМЫ ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ  
 
    ВЫЧИСЛЕНИЙ.............................................................................................. 590

 
14  Аффинность: перемирие с вычислительным ядром ............................. 592

 
15  Пакетные планировщики: наведение порядка в хаосе ........................ 633

 
16  Файловые операции для параллельного мира ....................................... 654

 
17  Инструменты и ресурсы для более качественного исходного кода ..... 691

Содержание

Оглавление ................................................................................................................6
Предисловие ............................................................................................................ 19
Благодарности ....................................................................................................... 24
О книге ..................................................................................................................... 26
Об авторах ............................................................................................................. 33
Об иллюстрации на обложке ............................................................................... 35

Часть I 
ВВЕДЕНИЕ В ПАРАЛЛЕЛЬНЫЕ 
ВЫЧИСЛЕНИЯ .............................................................................. 36

1 

Зачем нужны параллельные вычисления? ............................ 38

1.1 
Почему вы должны изучить параллельные вычисления? .............. 41
1.1.1 
Каковы потенциальные преимущества параллельных  

 
вычислений? ...................................................................................... 44
1.1.2 
Предостережения, связанные с параллельными вычислениями ....... 47

1.2 
Фундаментальные законы параллельных вычислений .................. 48
1.2.1 
Предел на параллельные вычисления: закон Амдала ........................ 48
1.2.2 
Преодоление параллельного предела: закон Густафсона–Барсиса .... 49
1.3 
Как работают параллельные вычисления? ...................................... 52
1.3.1 
Пошаговое ознакомление с примером приложения .......................... 54
1.3.2 
Аппаратная модель для современных гетерогенных  

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

 
гетерогенных параллельных систем ................................................ 64

1.4 
Классифицирование параллельных подходов ................................... 68

1.5 
Параллельные стратегии ......................................................................... 69

1.6 
Параллельное ускорение против сравнительного ускорения:  

 
две разные меры ....................................................................................... 70

1.7 
Чему вы научитесь в этой книге? .......................................................... 72
1.7.1 
Дополнительное чтение ................................................................... 73
1.7.2 
Упражнения ....................................................................................... 73

Резюме .................................................................................................................... 74

Содержание
2 

Планирование под параллелизацию .......................................... 75
2.1 
На подступах к новому проекту: подготовка ..................................... 77
2.1.1 
Версионный контроль: создание безопасного хранилища  

 
для своего параллельного кода .......................................................... 78
2.1.2 
Комплекты тестов: первый шаг к созданию устойчивого  

 
и надежного приложения .................................................................. 80
2.1.3 
Отыскание и исправление проблем с памятью ................................ 90
2.1.4 
Улучшение переносимости кода ....................................................... 92

2.2 
Профилирование: определение разрыва между  

 
способностями системы  и производительностью приложения .... 94

2.3 
Планирование: основа успеха ................................................................ 94
2.3.1 
Разведывательный анализ с использованием сравнительных  

 
тестов и мини-приложений ............................................................. 95
2.3.2 
Дизайн стержневых структур данных и модульность кода ............ 96
2.3.3 
Алгоритмы: редизайн для параллельности ..................................... 96

2.4 
Имплементация: где все это происходит ............................................ 97

2.5 
Фиксация: качественное завершение работы ................................... 98

2.6 
Материалы для дальнейшего изучения ............................................... 99
2.6.1 
Дополнительное чтение ................................................................... 99
2.6.2 
Упражнения ..................................................................................... 100

Резюме .................................................................................................................. 100

3 

Пределы производительности и профилирование ..... 102
3.1 
Знание потенциальных пределов производительности  

 
вашего приложения ................................................................................ 103

3.2 
Определение возможностей своего оборудования:  

 
сравнительное тестирование ............................................................... 106
3.2.1 
Инструменты для сбора характеристик системы ....................... 107
3.2.2 
Расчет теоретических максимальных флопов .............................. 110
3.2.3 
Иерархия памяти и теоретическая пропускная способность  

 
памяти ............................................................................................ 111
3.2.4 
Эмпирическое измерение пропускной способности и флопов ........ 112
3.2.5 
Расчет машинного баланса между флопами и пропускной  

 
способностью  ................................................................................. 116

3.3 
Характеризация вашего приложения: профилирование .............. 117
3.3.1 
Инструменты профилирования ..................................................... 117
3.3.2 
Эмпирическое измерение тактовой частоты  

 
и энергопотребления процессора.................................................... 129
3.3.3 
Отслеживание памяти во время выполнения ................................ 130

3.4 
Материалы для дальнейшего изучения ............................................. 131
3.4.1 
Дополнительное чтение ................................................................. 131
3.4.2 
Упражнения ..................................................................................... 131

Резюме .................................................................................................................. 132

4 

Дизайн данных и модели производительности ............ 134
4.1 
Структуры данных для обеспечения производительности :  

 
дизайн с ориентацией на данные ....................................................... 136
4.1.1 
Многомерные массивы .................................................................... 138
4.1.2 
Массив структур (AoS) против структур из массивов (SoA) ....... 144

Содержание

4.1.3 
Массив структур из массивов (AoSoA) .......................................... 150

4.2 
Три категории неуспешных обращений к кешу :  

 
вынужденное, емкостное и конфликтное ......................................... 152

4.3 
Простые модели производительности: тематическое  

 
исследование ............................................................................................ 157
4.3.1 
Полноматричные представления данных ...................................... 160
4.3.2 
Представление сжато-разреженного хранения............................. 164

4.4 
Продвинутые модели производительности ..................................... 169

4.5 
Сетевые сообщения ................................................................................ 173

4.6 
Материалы для дальнейшего изучения ............................................. 176
4.6.1 
Дополнительное чтение ................................................................. 176
4.6.2 
Упражнения ..................................................................................... 177

Резюме .................................................................................................................. 177

5 

Параллельные алгоритмы и шаблоны .................................. 179
5.1 
Анализ алгоритмов для приложений параллельных  

 
вычислений .............................................................................................. 180

5.2 
Модели производительности против алгоритмической  

 
сложности.................................................................................................. 181

5.3 
Параллельные алгоритмы: что это такое? ........................................ 186

5.4 
Что такое хеш-функция? ....................................................................... 187

5.5 
Пространственное хеширование: высокопараллельный  

 
алгоритм .................................................................................................... 189
5.5.1 
Использование идеального хеширования для пространственных  

 
операций с сеткой ........................................................................... 192
5.5.2 
Использование компактного хеширования  

 
для пространственных операций на сетке .................................... 208

5.6 
Шаблон префиксного суммирования (сканирования)  

 
и его важность в параллельных вычислениях ................................. 217
5.6.1 
Операция параллельного сканирования с эффективностью  

 
шагов ............................................................................................... 218
5.6.2 
Операция параллельного сканирования с эффективностью  

 
работы ............................................................................................ 219
5.6.3 
Операции параллельного сканирования для крупных массивов ..... 220

5.7 
Параллельная глобальная сумма: решение проблемы  

 
ассоциативности ..................................................................................... 221

5.8 
Будущие исследования параллельных алгоритмов ........................ 229

5.9 
Материалы для дальнейшего изучения ............................................. 229
5.9.1 
Дополнительное чтение ................................................................. 230
5.9.2 
Упражнения ..................................................................................... 231

Резюме .................................................................................................................. 231

Часть II 
CPU: ПАРАЛЛЕЛЬНАЯ РАБОЧАЯ  
ЛОШАДКА ....................................................................................... 233

6 

Векторизация: флопы забесплатно ....................................... 236
6.1 
Векторизация и обзор SIMD (одна команда, несколько  

 
элементов данных) ................................................................................. 237

Содержание

6.2 
Аппаратные тренды векторизации .................................................... 239

6.3 
Методы векторизации ........................................................................... 240
6.3.1 
Оптимизированные библиотеки обеспечивают  

 
производительность за счет малых усилий ................................... 240
6.3.2 
Автоматическая векторизация: простой способ ускорения  

 
векторизации (в большинстве случаев) ......................................... 241
6.3.3 
Обучение компилятора посредством подсказок: прагмы  

 
и директивы .................................................................................... 246
6.3.4 
Дрянные циклы, они у нас в руках: используйте внутренние  

 
векторные функции компилятора ................................................. 253
6.3.5 
Не для слабонервных: применение ассебмлерного кода  

 
для векторизации ............................................................................ 259

6.4 
Стиль программирования для более качественной  

 
векторизации ........................................................................................... 261

6.5 
Компиляторные флаги, относящиеся к векторизации ,  

 
для различных компиляторов ............................................................. 262

6.6 
Директивы OpenMP SIMD для более качественной  

 
переносимости ........................................................................................ 268

6.7 
Материалы для дальнейшего изучения ............................................. 271
6.7.1 
Дополнительное чтение ................................................................. 271
6.7.2 
Упражнения ..................................................................................... 271

Резюме .................................................................................................................. 272

7 

Стандарт OpenMP, который «рулит» ................................. 273
7.1 
Введение в OpenMP ................................................................................ 274
7.1.1 
Концепции OpenMP ......................................................................... 275
7.1.2 
Простая программа стандарта OpenMP ...................................... 278

7.2 
Типичные варианты использования OpenMP : уровень цикла,  

 
высокий уровень и MPI плюс OpenMP ............................................... 285
7.2.1 
OpenMP уровня цикла для быстрой параллелизации ..................... 285
7.2.2 
OpenMP высокого уровня для улучшенной параллельной  

 
производительности ...................................................................... 286
7.2.3 
MPI плюс OpenMP для максимальной масштабируемости ........... 286

7.3 
Примеры стандартного OpenMP уровня цикла ............................... 287
7.3.1 
OpenMP уровня цикла: пример векторного сложения ................... 288
7.3.2 
Пример потоковой триады ............................................................ 292
7.3.3 
OpenMP уровня цикла: стенсильный пример ................................. 293
7.3.4 
Производительность примеров уровня цикла................................ 295
7.3.5 
Пример редукции на основе глобальной суммы  

 
с использованием потокообразования OpenMP ............................. 296
7.3.6 
Потенциальные трудности OpenMP уровня цикла ....................... 297

7.4 
Важность области видимости переменной для правильности  

 
в OpenMP ................................................................................................... 298

7.5 
OpenMP уровня функции: придание всей функции целиком  

 
свойства  поточной параллельности ................................................... 300

7.6 
Усовершенствование параллельной масштабируемости  

 
с помощью OpenMP  высокого уровня................................................ 302
7.6.1 
Как имплементировать OpenMP высокого уровня ........................ 303
7.6.2 
Пример имплементирования OpenMP высокого уровня ................ 306