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

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

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

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

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

Мыслите параллельно....19

Что такое TBB....19

Структура книги и предисловия....19

Мыслите параллельно....20

Мотивы, стоящие за библиотекой TBB....20

Программирование с применением задач, а не потоков....21

Компонуемость: параллельное программирование необязательно должно быть запутанным....22

Масштабируемость, производительность и погоня за переносимой производительностью....23

Введение в параллельное программирование....24

Параллелизм вокруг нас....25

Конкурентность и параллелизм....25

Враги параллелизма....26

Терминология параллелизма....27

Сколько параллелизма в приложении?....34

Что такое потоки?....39

Что такое SIMD?....41

Безопасность в условиях конкурентности....42

Взаимное исключение и блокировки....42

Корректность....44

Взаимоблокировка....45

Состояния гонки....46

Нестабильность (недетерминированность) результатов....46

Уровень абстракции....47

Паттерны....47

Локальность и месть кешей....47

Аппаратное обоснование....48

Локальность ссылок....49

Строки кеша, выравнивание, разделение, взаимное исключение и ложное разделение....50

TBB помнит о кешах....54

Введение в векторизацию (SIMD)....54

Введение в средства C++ (в объеме, необходимом для работы с TBB)....56

Лямбда-функции....56

Обобщенное программирование....56

Контейнеры....57

Шаблоны....57

STL....57

Перегрузка....58

Диапазоны и итераторы....58

Резюме....59

Дополнительная информация....59

Приступаем: «Hello, TBB!»....61

Почему именно Threading Building Blocks?....61

Производительность: низкие накладные расходы, большое преимущество у C++....62

Эволюция поддержки параллелизма в TBB и C++....63

Недавние добавления в C++, относящиеся к параллелизму....64

Библиотека Threading Building Blocks (TBB)....64

Интерфейсы параллельного выполнения....65

Интерфейсы, не зависящие от модели выполнения....67

Использование строительных блоков в TBB....67

Да начнем же уже!....67

Получение библиотеки TBB....67

Получение кода примеров....68

Написание первого примера «Hello, TBB!»....68

Сборка простых примеров....71

Сборка в Windows в Microsoft Visual Studio....71

Сборка на платформе Linux из терминала....73

Более полный пример....75

Начинаем с последовательной реализации....76

Добавление уровня обмена сообщениями с помощью потокового графа....79

Добавление уровня разветвления-соединения с помощью parallel_for....81

Добавление уровня SIMD с помощью функции transform из Parallel STL....82

Резюме....85

Обобщенные параллельные алгоритмы....86

Функциональный параллелизм на уровне задач....89

Чуть более сложный пример: параллельная реализация быстрой сортировки....91

Циклы: parallel_for, parallel_reduce и parallel_scan....93

parallel_for: применение тела к каждому элементу диапазона....93

parallel_reduce: вычисление одного результата для всего диапазона....96

parallel_scan: редукция с промежуточными значениями....101

Как это работает?....103

Более сложный пример: линия прямой видимости....104

Варить до готовности: parallel_do и parallel_pipeline....106

parallel_do: применять тело, пока имеются элементы....107

parallel_pipeline: обработка несколькими фильтрами....114

Резюме....121

Дополнительная информация....121

Потоковые графы....123

Зачем использовать графы для выражения параллелизма?....124

Основы интерфейса потоковых графов в TBB....125

Шаг 1: создать объект графа....126

Шаг 2: создать узлы....127

Шаг 3: добавить ребра....129

Шаг 4: запустить граф....129

Шаг 5: ждать завершения выполнения графа....132

Более сложный пример потокового графа данных....132

Реализация примера в виде потокового графа TBB....134

Производительность потокового графа данных....135

Частный случай – графы зависимостей....137

Реализация графа зависимостей....139

Оценка масштабируемости графа зависимостей....144

Дополнительные сведения о потоковых графах в TBB....144

Резюме....145

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

Какое отношение библиотека STL имеет к этой книге?....146

Аналогия для осмысления политик выполнения в Parallel STL....148

Простой пример – алгоритм std::for_each....149

Какие алгоритмы предоставляет реализация Parallel STL?....152

Как получить и использовать копию библиотеки STL, в которой используется TBB....152

Алгоритмы в библиотеке Intel Parallel STL....153

Нестандартные итераторы открывают дополнительные способы использования....154

Некоторые наиболее полезные алгоритмы....157

std::for_each, std::for_each_n....157

std::transform....159

std::reduce....160

std::transform_reduce....161

Политики выполнения в деталях....163

sequenced_policy....163

parallel_policy....164

unsequenced_policy....164

parallel_unsequenced_policy....165

Какую политику выполнения использовать?....165

Другие способы ввести SIMD-параллелизм....166

Резюме....167

Дополнительная информация....167

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

Сквозной пример: гистограмма изображения....168

Небезопасная параллельная реализация....171

Первая безопасная параллельная реализация: крупнозернистая блокировка....174

Варианты мьютексов....179

Вторая безопасная параллельная реализация: мелкозернистая блокировка....181

Третья потокобезопасная параллельная реализация: атомарные переменные....185

Улучшенная параллельная реализация: приватизация и редукция....189

Поточно-локальная память....190

Класс enumerable_thread_specific....191

Тип combinable....193

Самая простая параллельная реализация: шаблон редукции....195

Подведем итоги....197

Резюме....201

Дополнительная информация....201

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

Основы важнейших структур данных....203

Неупорядоченные ассоциативные контейнеры....203

Отображение или множество....204

Несколько значений....204

Хеширование....204

Неупорядоченность....205

Конкурентные контейнеры....205

Конкурентные неупорядоченные ассоциативные контейнеры....207

Конкурентные очереди: обычные, ограниченные и с приоритетами....213

Конкурентный вектор....221

Резюме....224

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

Выделение памяти в современном C++....225

Масштабируемое выделение памяти: что....226

Масштабируемое выделение памяти: почему....227

Избежание ложного разделения с помощью дополнения....228

Альтернативы масштабируемому выделению памяти: какие....230

К вопросу о компиляции....231

Самый популярный способ использования (библиотека прокси для C/C++): как....231

Linux: использование библиотеки прокси....232

macOS: использование библиотеки прокси....233

Windows: использование библиотеки прокси....233

Тестирование библиотеки прокси....234

Функции C: масштабируемые распределителя памяти для C....235

Классы C++: масштабируемые распределители памяти для C++....236

Распределители с сигнатурой std::allocator....237

scalable_allocator....237

tbb_allocator....238

zero_allocator....238

cached_aligned_allocator....238

Поддержка пула памяти: memory_pool_allocator....239

Поддержка выделения памяти для массивов: aligned_space....239

Избирательная подмена new и delete....240

Настройка производительности: некоторые рычаги управления....243

Что такое большие страницы?....243

Поддержка больших страниц в TBB....243

scalable_allocation_mode(int mode, intptr_t value)....244

TBBMALLOC_USE_HUGE_PAGES....244

TBBMALLOC_SET_SOFT_HEAP_LIMIT....244

int scalable_allocation_command(int cmd, void ∗param)....245

TBBMALLOC_CLEAN_ALL_BUFFERS....245

TBBMALLOC_CLEAN_THREAD_BUFFERS....245

Резюме....245

TBB и параллельные паттерны....246

Параллельные паттерны и параллельные алгоритмы....246

Паттерны определяют классификацию алгоритмов, проектных решений и т. д.....248

Паттерны, которые работают....249

Параллелизм данных одерживает победу....250

Паттерн Вложенность....250

Паттерн Отображение....252

Паттерн Куча работ....253

Паттерны редукции (Редукция и Сканирование)....253

Паттерн Разветвление-соединение....254

Паттерн Разделяй и властвуй....257

Паттерн Ветви и границы....257

Паттерн Конвейер....258

Паттерн Событийно-управляемая координация (реактивные потоки)....259

Резюме....260

Дополнительная информация....260

Столпы компонуемости....262

Что такое компонуемость?....263

Вложенная композиция....264

Конкурентная композиция....266

Последовательная композиция....267

Благодаря каким особенностям библиотека TBB является компонуемой....269

Пул потоков TBB (рынок) и арены задач....269

Диспетчер задач в TBB: заимствование работ и не только....272

Соберем все вместе....278

Забегая вперед....282

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

Изоляция работ....282

Привязка задачи к потоку и потока к ядру....282

Приоритеты задач....282

Резюме....283

Дополнительная информация....283

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

Сквозной пример: вычисление последовательности....284

Высокоуровневый подход: parallel_invoke....286

Высший среди низших: task_group....288

Низкоуровневый интерфейс: часть первая – блокировка задач....290

Низкоуровневый интерфейс задач: часть вторая – продолжение задачи....294

Обход планировщика....300

Низкоуровневый интерфейс задач: часть третья – рециклинг задач....301

Контрольный список для интерфейса задач....303

И еще одно: FIFO-задачи (типа запустил и забыл)....304

Применение низкоуровневых средств на практике....305

Резюме....311

Дополнительная информация....312

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

Краткий обзор архитектуры планировщика TBB....314

Интерфейсы для управления количеством задач....315

Управление количеством потоков с помощью task_scheduler_init....315

Управление количеством потоков с помощью task_arena....316

Управление количеством потоков с помощью global_control....317

Сводка концепций и классов....317

Рекомендации по заданию количества потоков....318

Использование одного объекта task_scheduler_init в простом приложении....319

Использование нескольких объектов task_scheduler_init в простом приложении....321

Использование нескольких арен с разным числом слотов, чтобы подсказать TBB, куда направлять рабочие потоки....322

Использование global_control для управления количеством потоков, доступных для занятия слотов на аренах....325

Использование global_control с целью временно ограничить количество доступных потоков....327

Когда НЕ следует управлять количеством потоков....329

Что не так?....330

Резюме....331

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

Изоляция работ для обеспечения корректности....333

Создание изолированного региона с помощью this_task_arena::isolate....337

Использование арен задач для изоляции: обоюдоострый меч....342

Не поддавайтесь искушению использовать арены задач для изоляции ради корректности....345

Резюме....348

Дополнительная литература....348

Привязка потока к ядру и задачи к потоку....349

Создание привязки потока к ядру....350

Создание привязки задачи к потоку....352

Когда и как следует использовать средства привязки в TBB?....358

Резюме....359

Дополнительная информация....359

Приоритеты задач....360

Поддержка невытесняющих приоритетов в классе задач TBB....360

Задание статических и динамических приоритетов....362

Два простых примера....363

Реализация приоритетов без поддержки со стороны задач TBB....366

Резюме....368

Дополнительная информация....369

Отмена и обработка исключений....370

Как отменить коллективную работу....371

Отмена задач в деталях....372

Явное назначение TGC....374

Назначение TGC по умолчанию....376

Обработка исключений в TBB....380

Написание собственных классов исключений TBB....382

Соберем все вместе: компонуемость, отмена и обработка исключений....385

Резюме....387

Дополнительная информация....388

Настройка TBB-алгоритмов: зернистость, локальность, параллелизм и детерминированность....389

Зернистость задач: какой размер достаточен?....390

Выбор Диапазонов и Разбивателей для циклов....391

Обзор разбивателей....392

Выбирать ли степень детализации для управления зернистостью задач....393

Диапазоны, Разбиватели и производительность кеша данных....396

Использование static_partitioner....403

Ограничение планировщика ради детерминированности....405

Настройка конвейеров в TBB: количество фильтров, режимы и маркеры....407

Сбалансированный конвейер....408

Несбалансированный конвейер....410

Конвейеры, локальность данных и привязка к потоку....411

В глубоких водах....412

Создание собственного типа диапазона....412

Класс Pipeline и фильтры, привязанные к потоку....415

Резюме....419

Дополнительная информация....419

Потоковые графы: дополнительные сведения....420

Оптимизация зернистости, локальности и степени параллелизма....420

Зернистость узла: какой будет достаточно?....421

Потребление памяти и локальность данных....429

Арены задач и потоковый граф....442

Рекомендации по работе с потоковыми графами: что полезно, а что вредно....445

Полезно: использовать вложенный параллелизм....445

Вредно: использовать многофункциональные узлы вместо вложенного параллелизма....445

Полезно: использовать узлы join_node, sequencer_node или multifunction_node для восстановления порядка в потоковом графе, когда это необходимо....446

Полезно: использовать функцию isolate для вложенного параллелизма....449

Полезно: использовать отмену и обработку исключений в потоковых графах....451

Полезно: задавать приоритеты для графа, в котором используется task_group_context....455

Вредно: создавать ребро между узлами разных графов....455

Полезно: использовать try_put для передачи информации между графами....457

Полезно: использовать composite_node для инкапсуляции группы узлов....459

Введение в Intel Advisor: Flow Graph Analyzer....463

Процесс проектирования в FGA....463

Процесс анализа в FGA....466

Диагностика проблем производительности с помощью FGA....468

Резюме....471

Дополнительная информация....471

Дополнение потоковых графов асинхронными узлами....472

Пример из асинхронного мира....473

Зачем и когда использовать async_node?....477

Более реалистичный пример....479

Резюме....487

Дополнительная информация....488

Накачанные потоковые графы: узлы OpenCL....489

Пример «Hello OpenCL_Node»....490

Где исполняется наше ядро?....497

Возвращаясь к более реалистичному примеру из главы 18....503

Дьявол кроется в деталях....510

Концепция NDRange....512

Поиграем со смещением....516

Задание ядра OpenCL....517

Еще о выборе устройства....518

Предупреждение по поводу порядка....521

Резюме....524

Дополнительная информация....525

TBB в системах с архитектурой NUMA....526

Определение топологии платформы....528

Каковы затраты на доступ к памяти....531

Базовый пример....532

Мастерство размещения данных и привязки к процессору....534

Привлекаем hwloc и TBB к совместной работе....539

Более сложные альтернативы....544

Резюме....545

Дополнительная информация....546

История и предшественники....547

Десятилетие «от птенца к орлу»....547

1. Революция TBB внутри Intel....547

2. Первая революция TBB в сфере параллелизма....548

3. Вторая революция TBB в сфере параллелизма....549

4. Птички TBB....550

Источники идей TBB....552

Модель ослабленного последовательного выполнения....553

Библиотеки, оказавшие влияние....553

Языки, оказавшие влияние....555

Прагмы, оказавшие влияние....555

Влияние обобщенного программирования....556

Учет кешей....556

Учет стоимости квантования времени....557

Литература для дополнительного чтения....558

TBB в кратком изложении....561

Отладка и условный код....561

Макросы ознакомительных средств....563

Диапазоны....563

Разбиватели....564

Алгоритмы....565

Алгоритм: parallel_do....565

Алгоритм: parallel_for....568

Алгоритм: parallel_for_each....570

Алгоритм: parallel_invoke....572

Алгоритм: parallel_pipeline....573

Алгоритм: parallel_reduce и parallel_deterministic_reduce....575

Алгоритм: parallel_scan....579

Алгоритм: parallel_sort....582

Алгоритм: pipeline....584

Потоковый граф....586

Потоковый граф: класс graph....587

Потоковый граф: порты и ребра....588

Потоковый граф: узлы....588

Выделение памяти....598

Контейнеры....603

Синхронизация....621

Поточно-локальная память (TLS)....627

Хронометраж....635

Группы задач: использование планировщика с заимствованием задач....636

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

Настройки плавающей точки....648

Исключения....650

Потоки....652

Parallel STL....653

Глоссарий....656

Предметный указатель....669

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

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