Параллельные и высокопроизводительные вычисления
Покупка
Тематика:
Программирование на C и C++
Издательство:
ДМК Пресс
Перевод:
Логунов А. В.
Год издания: 2022
Кол-во страниц: 801
Дополнительно
Вид издания:
Практическое пособие
Уровень образования:
Дополнительное образование
ISBN: 978-5-97060-936-1
Артикул: 833976.01.99
Параллельное программирование позволяет распределять задачи обработки данных между несколькими процессорами, существенно повышая производительность. В книге рассказывается, как с минимальными трудозатратами повыситьэффективность ваших программ. Вы научитесь оценивать аппаратные архитектуры и работать со стандартными инструментами отрасли, такими как OpenMP и MPI, освоите структуры данных и алгоритмы, подходящие для высокопроизводительных вычислений, узнаете, как экономить энергию на мобильных устройствах, и даже запустите масштабную симуляцию цунами на батарее из GPU-процессоров. Издание предназначено для опытных программистов, владеющих языком высокопроизводительных вычислений, таким как C, C++ или Fortran.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 02.03.02: Фундаментальная информатика и информационные технологии
- 09.03.01: Информатика и вычислительная техника
- 09.03.02: Информационные системы и технологии
- 09.03.03: Прикладная информатика
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Роберт Роби и Джулиана Замора Параллельные и высокопроизводительные вычисления
Parallel and High Performance Computing SECOND EDITION ROBERT (BOB) ROBEY and YULIANA (YULIE) ZAMORA
Параллельные и высокопроизводительные вычисления РОБЕРТ РОБИ и ДЖУЛИАНА ЗАМОРА Москва, 2022
УДК 004.421 ББК 32.972 Р58 Роби Р., Замора Дж. Р58 Параллельные и высокопроизводительные вычисления / пер. с англ. А. В. Ло ISBN 978-5-97060-936-1 Параллельное программирование позволяет распределять задачи обработки данных между несколькими процессорами, существенно повышая производительность. В книге рассказывается, как с минимальными трудозатратами повысить эффективность ваших программ. Вы научитесь оценивать аппаратные архитектуры и работать со стандартными инструментами отрасли, такими как OpenMP и MPI, освоите структуры данных и алгоритмы, подходящие для высокопроизводительных вычислений, узнаете, как экономить энергию на мобильных устройствах, и даже запустите масштабную симуляцию цунами на батарее из GPU-процессоров. Издание предназначено для опытных программистов, владеющих языком высокопроизводительных вычислений, таким как C, C++ или Fortran. УДК 004.421 ББК 32.972 Original English language edition published by Manning Publications USA. Russian-language edition copyright © 2021 by DMK Press. All rights reserved. Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. ISBN 978-1-6172-9646-8 (англ.) © Manning Publications, 2021 ISBN 978-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
Планирование под параллелизацию.......................................... 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
Аппаратные тренды векторизации..................................................... 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