Параллельное программирование на C++ с помощью библиотеки TBB

Майкл Восс, Рафаэль Асенхо, Джеймс Рейндерс

Параллельное программирование  
на C++ с помощью библиотеки TBB

Pro TBB: C++ Parallel 
Programming with Threading 
Building Blocks

Michael Voss
Rafael Asenjo
James Reinders

Параллельное  
программирование на C++  
с помощью библиотеки TBB

Майкл Восс
Рафаэль Асенхо
Джеймс Рейндерс

Москва, 2020

УДК 004.4
ББК 32.973.202
В76

Восс М., Асенхо Р., Рейндерс Дж.
В76 
Параллельное программирование на C++ с помощью библиотеки TBB / 
пер. с англ. А. А. Слинкина. – М.: ДМК Пресс, 2020. – 674 с.: ил. 

ISBN 978-5-97060-864-7

Эта книга представляет собой современное руководство для всех пишущих на 
C++ программистов, которые хотят научиться работать с библиотекой Threading 
Building Blocks (TBB). Написанная экспертами по TBB и параллельному программированию, она вобрала в себя их многолетний коллективный опыт разработки 
и преподавания параллельного программирования с помощью TBB. Излагаемый 
материал представлен в доступной форме. В книге имеются многочисленные 
примеры и рекомендации, которые помогут вам в полной мере овладеть TBB 
и задействовать всю мощь параллельных систем.
Книга начинается с описания базовых параллельных алгоритмов и средств 
распараллеливания, имеющихся в стандартной библиотеке шаблонов C++. Вы 
узнае те об основах управления памятью, работе со структурами данных и решении типичных проблем синхронизации. Затем эти идеи применяются к более 
сложным системам, на примере которых объясняются компромиссы во имя производительности, общеупотребительные паттерны параллельного программирования, управление потоками и накладные расходы, а также применение TBB 
к программированию гетерогенных систем и систем на кристалле.

УДК 004.4
ББК 32.973.202

First published in English under the title «Pro TBB; C++ Parallel Programming with Threading 
Building Blocks» by Michael Voss, Rafael Asenjo and James Reinders, edition: 1.
This edition has been translated and published under licence from APress Media, LLC, part 
of Springer Nature. 
APress Media, LLC, part of Springer Nature takes no responsibility and shall not be made 
liable for the accuracy of the translation. 
Russian language edition copyright © 2020 by DMK Press. All rights reserved.

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

ISBN 978-1-4842-4397-8 (англ.)  
Copyright © Intel Corporation, 2019
ISBN 978-5-97060-864-7 (рус.)  
©  Оформление, издание, перевод, 
ДМК Пресс, 2020

Содержание

От издательства ......................................................................................................... 14

Об авторах .................................................................................................................... 15

Благодарности ............................................................................................................ 16

Предисловие ............................................................................................................... 18

Мыслите параллельно ........................................................................................................ 18
Что такое TBB ...................................................................................................................... 18
Структура книги и предисловия ........................................................................................ 18
Мыслите параллельно .................................................................................................... 19
Мотивы, стоящие за библиотекой TBB.............................................................................. 19
Программирование с применением задач, а не потоков ........................................... 20
Компонуемость: параллельное программирование необязательно  
должно быть запутанным .............................................................................................. 21
Масштабируемость, производительность и погоня за переносимой  
производительностью ................................................................................................... 22
Введение в параллельное программирование ................................................................. 23
Параллелизм вокруг нас ................................................................................................ 24
Конкурентность и параллелизм .................................................................................... 24
Враги параллелизма ....................................................................................................... 25
Терминология параллелизма ........................................................................................ 26
Сколько параллелизма в приложении? ........................................................................ 33
Что такое потоки? .......................................................................................................... 38
Что такое SIMD? .............................................................................................................. 40
Безопасность в условиях конкурентности ................................................................... 41
Взаимное исключение и блокировки ........................................................................... 41
Корректность .................................................................................................................. 43
Взаимоблокировка ......................................................................................................... 44
Состояния гонки ............................................................................................................. 45
Нестабильность (недетерминированность) результатов ............................................ 45
Уровень абстракции ....................................................................................................... 46
Паттерны ........................................................................................................................ 46
Локальность и месть кешей ............................................................................................... 46
Аппаратное обоснование .............................................................................................. 47
Локальность ссылок ....................................................................................................... 48
Строки кеша, выравнивание, разделение, взаимное исключение  
и ложное разделение ..................................................................................................... 49
TBB помнит о кешах ....................................................................................................... 53
Введение в векторизацию (SIMD) ...................................................................................... 53
Введение в средства C++ (в объеме, необходимом для работы с TBB) ............................ 55
Лямбда-функции ............................................................................................................ 55
Обобщенное программирование .................................................................................. 55
Контейнеры .................................................................................................................... 56

 Содержание

Шаблоны ......................................................................................................................... 56
STL ................................................................................................................................... 56
Перегрузка ...................................................................................................................... 57
Диапазоны и итераторы ................................................................................................ 57
Резюме ................................................................................................................................. 58
Дополнительная информация ........................................................................................... 58

ЧАСТЬ I
Глава 1. Приступаем: «Hello, TBB!» ............................................................... 60

Почему именно Threading Building Blocks? ...................................................................... 60
Производительность: низкие накладные расходы, большое преимущество у C++ .. 61
Эволюция поддержки параллелизма в TBB и C++ ....................................................... 62
Недавние добавления в C++, относящиеся к параллелизму ....................................... 63
Библиотека Threading Building Blocks (TBB) ..................................................................... 63
Интерфейсы параллельного выполнения .................................................................... 64
Интерфейсы, не зависящие от модели выполнения ................................................... 66
Использование строительных блоков в TBB ................................................................ 66
Да начнем же уже! .............................................................................................................. 66
Получение библиотеки TBB ........................................................................................... 66
Получение кода примеров ............................................................................................. 67
Написание первого примера «Hello, TBB!» .................................................................. 67
Сборка простых примеров ............................................................................................ 70
Сборка в Windows в Microsoft Visual Studio .................................................................. 70
Сборка на платформе Linux из терминала ................................................................... 72
Более полный пример ........................................................................................................ 74
Начинаем с последовательной реализации ................................................................. 75
Добавление уровня обмена сообщениями с помощью потокового графа ................ 78
Добавление уровня разветвления–соединения с помощью parallel_for .................... 80
Добавление уровня SIMD с помощью функции transform из Parallel STL ................. 81
Резюме ................................................................................................................................. 84

Глава 2. Обобщенные параллельные алгоритмы ................................ 85

Функциональный параллелизм на уровне задач ............................................................. 88
Чуть более сложный пример: параллельная реализация быстрой сортировки ........ 90
Циклы: parallel_for, parallel_reduce и parallel_scan ............................................................ 92
parallel_for: применение тела к каждому элементу диапазона .................................. 92
parallel_reduce: вычисление одного результата для всего диапазона ........................ 95
parallel_scan: редукция с промежуточными значениями ..........................................100
Как это работает? ..........................................................................................................102
Более сложный пример: линия прямой видимости ...................................................103
Варить до готовности: parallel_do и parallel_pipeline ......................................................105
parallel_do: применять тело, пока имеются элементы ...............................................106
parallel_pipeline: обработка несколькими фильтрами ...............................................113
Резюме ................................................................................................................................120
Дополнительная информация ..........................................................................................120

Глава 3. Потоковые графы .................................................................................122

Зачем использовать графы для выражения параллелизма? ..........................................123
Основы интерфейса потоковых графов в TBB.................................................................124
Шаг 1: создать объект графа .........................................................................................125

Содержание  7

Шаг 2: создать узлы .......................................................................................................126
Шаг 3: добавить ребра ...................................................................................................128
Шаг 4: запустить граф ...................................................................................................128
Шаг 5: ждать завершения выполнения графа .............................................................131
Более сложный пример потокового графа данных .........................................................131
Реализация примера в виде потокового графа TBB ...................................................133
Производительность потокового графа данных .........................................................134
Частный случай – графы зависимостей ...........................................................................136
Реализация графа зависимостей .................................................................................138
Оценка масштабируемости графа зависимостей .......................................................143
Дополнительные сведения о потоковых графах в TBB ...................................................143
Резюме ................................................................................................................................144

Глава 4. TBB и параллельные алгоритмы стандартной  
библиотеки шаблонов C++ ................................................................................145

Какое отношение библиотека STL имеет к этой книге? .................................................145
Аналогия для осмысления политик выполнения в Parallel STL .....................................147
Простой пример – алгоритм std::for_each ........................................................................148
Какие алгоритмы предоставляет реализация Parallel STL? ............................................151
Как получить и использовать копию библиотеки STL, в которой  
применяется TBB ..........................................................................................................151
Алгоритмы в библиотеке Intel Parallel STL .................................................................152
Нестандартные итераторы открывают дополнительные способы использования ......153
Некоторые наиболее полезные алгоритмы .....................................................................156
std::for_each, std::for_each_n..........................................................................................156
std::transform .................................................................................................................158
std::reduce ......................................................................................................................159
std::transform_reduce .....................................................................................................160
Политики выполнения в деталях .....................................................................................162
sequenced_policy ............................................................................................................162
parallel_policy .................................................................................................................163
unsequenced_policy ........................................................................................................163
parallel_unsequenced_policy ..........................................................................................164
Какую политику выполнения использовать? ..................................................................164
Другие способы ввести SIMD-параллелизм .....................................................................165
Резюме ................................................................................................................................166
Дополнительная информация ..........................................................................................166

Глава 5. Синхронизация – почему ее нужно избегать  
и как это сделать .....................................................................................................167

Сквозной пример: гистограмма изображения ................................................................167
Небезопасная параллельная реализация .........................................................................170
Первая безопасная параллельная реализация: крупнозернистая блокировка .............173
Варианты мьютексов ....................................................................................................178
Вторая безопасная параллельная реализация: мелкозернистая блокировка ...............180
Третья потокобезопасная параллельная реализация: атомарные переменные ..........184
Улучшенная параллельная реализация: приватизация и редукция ..............................188
Поточно-локальная память ..........................................................................................189
Класс enumerable_thread_specific ..................................................................................190
Тип combinable ..............................................................................................................192

 Содержание

Самая простая параллельная реализация: шаблон редукции ........................................194
Подведем итоги .................................................................................................................196
Резюме ................................................................................................................................200
Дополнительная информация ..........................................................................................200

Глава 6. Структуры данных для конкурентного  
программирования ................................................................................................201

Основы важнейших структур данных ..............................................................................202
Неупорядоченные ассоциативные контейнеры .........................................................202
Отображение или множество .......................................................................................203
Несколько значений ......................................................................................................203
Хеширование .................................................................................................................203
Неупорядоченность.......................................................................................................204
Конкурентные контейнеры ...............................................................................................204
Конкурентные неупорядоченные ассоциативные контейнеры ................................206
Конкурентные очереди: обычные, ограниченные и с приоритетами ......................212
Конкурентный вектор ...................................................................................................220
Резюме ................................................................................................................................223

Глава 7. Масштабируемое выделение памяти ......................................224

Выделение памяти в современном C++ ...........................................................................224
Масштабируемое выделение памяти: что .......................................................................225
Масштабируемое выделение памяти: почему ................................................................226
Избежание ложного разделения с помощью дополнения .........................................227
Альтернативы масштабируемому выделению памяти: какие .......................................229
К вопросу о компиляции ...................................................................................................230
Самый популярный способ использования (библиотека прокси для C/C++): как ........230
Linux: использование библиотеки прокси ..................................................................231
macOS: использование библиотеки прокси ................................................................232
Windows: использование библиотеки прокси .............................................................232
Тестирование библиотеки прокси ...............................................................................233
Функции C: масштабируемые распределители памяти для C .......................................234
Классы C++: масштабируемые распределители памяти для C++ ...................................235
Распределители с сигнатурой std::allocator<T> ..........................................................236
scalable_allocator ................................................................................................................236
tbb_allocator ........................................................................................................................237
zero_allocator ......................................................................................................................237
cached_aligned_allocator .....................................................................................................237
Поддержка пула памяти: memory_pool_allocator ........................................................238
Поддержка выделения памяти для массивов: aligned_space .....................................238
Избирательная подмена new и delete ..............................................................................239
Настройка производительности: некоторые рычаги управления .................................242
Что такое большие страницы? .....................................................................................242
Поддержка больших страниц в TBB .............................................................................242
scalable_allocation_mode(int mode, intptr_t value) ........................................................243
TBBMALLOC_USE_HUGE_PAGES ....................................................................................243
TBBMALLOC_SET_SOFT_HEAP_LIMIT ...........................................................................243
int scalable_allocation_command(int cmd, void ∗param) ...............................................244
TBBMALLOC_CLEAN_ALL_BUFFERS ..............................................................................244
TBBMALLOC_CLEAN_THREAD_BUFFERS ......................................................................244
Резюме ................................................................................................................................244

Содержание  9

Глава 8. TBB и параллельные паттерны ....................................................245

Параллельные паттерны и параллельные алгоритмы ....................................................245
Паттерны определяют классификацию алгоритмов, проектных решений и т. д. ........247
Паттерны, которые работают ...........................................................................................248
Параллелизм данных одерживает победу .......................................................................249
Паттерн Вложенность ........................................................................................................249
Паттерн Отображение .......................................................................................................251
Паттерн Куча работ ............................................................................................................252
Паттерны редукции (Редукция и Сканирование) ...........................................................252
Паттерн Разветвление–соединение .................................................................................253
Паттерн Разделяй и властвуй ...........................................................................................256
Паттерн Ветви и границы .................................................................................................256
Паттерн Конвейер ..............................................................................................................257
Паттерн Событийно-управляемая координация (реактивные потоки) ........................258
Резюме ................................................................................................................................259
Дополнительная информация ..........................................................................................259

ЧАСТЬ II
Глава 9. Столпы компонуемости .....................................................................261

Что такое компонуемость? ................................................................................................262
Вложенная композиция ................................................................................................263
Конкурентная композиция ..........................................................................................265
Последовательная композиция....................................................................................266
Благодаря каким особенностям библиотека TBB является компонуемой ....................268
Пул потоков TBB (рынок) и арены задач .....................................................................268
Диспетчер задач в TBB: заимствование работ, и не только .......................................271
Соберем все вместе ............................................................................................................277
Забегая вперед ...................................................................................................................281
Управление количеством потоков ...............................................................................281
Изоляция работ .............................................................................................................281
Привязка задачи к потоку и потока к ядру .................................................................281
Приоритеты задач .........................................................................................................281
Резюме ................................................................................................................................282
Дополнительная информация ..........................................................................................282

Глава 10. Использование задач для создания  
собственных алгоритмов ...................................................................................283

Сквозной пример: вычисление последовательности .....................................................283
Высокоуровневый подход: parallel_invoke .......................................................................285
Высший среди низших: task_group ...................................................................................287
Низкоуровневый интерфейс: часть первая – блокировка задач ....................................289
Низкоуровневый интерфейс задач: часть вторая – продолжение задачи ....................293
Обход планировщика ....................................................................................................299
Низкоуровневый интерфейс задач: часть третья – рециклинг задач ............................300
Контрольный список для интерфейса задач ...................................................................302
И еще одно: FIFO-задачи (типа запустил и забыл) .........................................................303
Применение низкоуровневых средств на практике .......................................................304
Резюме ................................................................................................................................310
Дополнительная информация ..........................................................................................311

 Содержание

Глава 11. Управление количеством потоков ..........................................312

Краткий обзор архитектуры планировщика TBB ............................................................313
Интерфейсы для управления количеством задач ...........................................................314
Управление количеством потоков с помощью task_scheduler_init ............................314
Управление количеством потоков с помощью task_arena .........................................315
Управление количеством потоков с помощью global_control ....................................316
Сводка концепций и классов ........................................................................................316
Рекомендации по заданию количества потоков .............................................................317
Использование одного объекта task_scheduler_init в простом приложении ............318
Использование нескольких объектов task_scheduler_init в простом приложении ...320
Использование нескольких арен с разным числом слотов, чтобы  
подсказать TBB, куда направлять рабочие потоки .....................................................321
Использование global_control для управления количеством потоков,  
доступных для занятия слотов на аренах ....................................................................324
Использование global_control с целью временно ограничить количество  
доступных потоков .......................................................................................................326
Когда НЕ следует управлять количеством потоков .........................................................328
Что не так? ..........................................................................................................................329
Резюме ................................................................................................................................330

Глава 12. Применение изоляции работы для обеспечения  
корректности и повышения производительности .............................331

Изоляция работ для обеспечения корректности .............................................................332
Создание изолированного региона с помощью this_task_arena::isolate ...................336
Использование арен задач для изоляции: обоюдоострый меч ......................................341
Не поддавайтесь искушению использовать арены задач для изоляции  
ради корректности ........................................................................................................344
Резюме ................................................................................................................................347
Дополнительная литература .............................................................................................347

Глава 13. Привязка потока к ядру и задачи к потоку .......................348

Создание привязки потока к ядру ....................................................................................349
Создание привязки задачи к потоку ................................................................................351
Когда и как следует использовать средства привязки в TBB? ........................................357
Резюме ................................................................................................................................358
Дополнительная информация ..........................................................................................358

Глава 14. Приоритеты задач .............................................................................359

Поддержка невытесняющих приоритетов в классе задач TBB ......................................359
Задание статических и динамических приоритетов ......................................................361
Два простых примера ........................................................................................................362
Реализация приоритетов без поддержки со стороны задач TBB ...................................365
Резюме ................................................................................................................................367
Дополнительная информация ..........................................................................................368

Глава 15. Отмена и обработка исключений ............................................369

Как отменить коллективную работу ................................................................................370
Отмена задач в деталях .....................................................................................................371
Явное назначение TGC..................................................................................................373