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

Параллельное программирование на C++ с помощью библиотеки TBB (1)
Об авторах
Благодарности
Предисловие
Мыслите параллельно
Что такое TBB
Структура книги и предисловия
Мыслите параллельно
Мотивы, стоящие за библиотекой TBB
Программирование с применением задач, а не потоков
Компонуемость: параллельное программирование необязательно должно быть запутанным
Масштабируемость, производительность и погоня за переносимой производительностью
Введение в параллельное программирование
Параллелизм вокруг нас
Конкурентность и параллелизм
Враги параллелизма
Терминология параллелизма
Сколько параллелизма в приложении?
Что такое потоки?
Что такое SIMD?
Безопасность в условиях конкурентности
Взаимное исключение и блокировки
Корректность
Взаимоблокировка
Состояния гонки
Нестабильность (недетерминированность) результатов
Уровень абстракции
Паттерны
Локальность и месть кешей
Аппаратное обоснование
Локальность ссылок
Строки кеша, выравнивание, разделение, взаимное исключение и ложное разделение
TBB помнит о кешах
Введение в векторизацию (SIMD)
Введение в средства C++ (в объеме, необходимом для работы с TBB)
Лямбда-функции
Обобщенное программирование
Контейнеры
Шаблоны
STL
Перегрузка
Диапазоны и итераторы
Резюме
Дополнительная информация
Приступаем: «Hello, TBB!»
Почему именно Threading Building Blocks?
Производительность: низкие накладные расходы, большое преимущество у C++
Эволюция поддержки параллелизма в TBB и C++
Недавние добавления в C++, относящиеся к параллелизму
Библиотека Threading Building Blocks (TBB)
Интерфейсы параллельного выполнения
Интерфейсы, не зависящие от модели выполнения
Использование строительных блоков в TBB
Да начнем же уже!
Получение библиотеки TBB
Получение кода примеров
Написание первого примера «Hello, TBB!»
Сборка простых примеров
Сборка в Windows в Microsoft Visual Studio
Сборка на платформе Linux из терминала
Более полный пример
Начинаем с последовательной реализации
Добавление уровня обмена сообщениями с помощью потокового графа
Добавление уровня разветвления-соединения с помощью parallel_for
Добавление уровня SIMD с помощью функции transform из Parallel STL
Резюме
Обобщенные параллельные алгоритмы
Функциональный параллелизм на уровне задач
Чуть более сложный пример: параллельная реализация быстрой сортировки
Циклы: parallel_for, parallel_reduce и parallel_scan
parallel_for: применение тела к каждому элементу диапазона
parallel_reduce: вычисление одного результата для всего диапазона
parallel_scan: редукция с промежуточными значениями
Как это работает?
Более сложный пример: линия прямой видимости
Варить до готовности: parallel_do и parallel_pipeline
parallel_do: применять тело, пока имеются элементы
parallel_pipeline: обработка несколькими фильтрами
Резюме
Дополнительная информация
Потоковые графы
Зачем использовать графы для выражения параллелизма?
Основы интерфейса потоковых графов в TBB
Шаг 1: создать объект графа
Шаг 2: создать узлы
Шаг 3: добавить ребра
Шаг 4: запустить граф
Шаг 5: ждать завершения выполнения графа
Более сложный пример потокового графа данных
Реализация примера в виде потокового графа TBB
Производительность потокового графа данных
Частный случай – графы зависимостей
Реализация графа зависимостей
Оценка масштабируемости графа зависимостей
Дополнительные сведения о потоковых графах в TBB
Резюме
TBB и параллельные алгоритмы стандартной библиотеки шаблонов C++
Какое отношение библиотека STL имеет к этой книге?
Аналогия для осмысления политик выполнения в Parallel STL
Простой пример – алгоритм std::for_each
Какие алгоритмы предоставляет реализация Parallel STL?
Как получить и использовать копию библиотеки STL, в которой используется TBB
Алгоритмы в библиотеке Intel Parallel STL
Нестандартные итераторы открывают дополнительные способы использования
Некоторые наиболее полезные алгоритмы
std::for_each, std::for_each_n
std::transform
std::reduce
std::transform_reduce
Политики выполнения в деталях
sequenced_policy
parallel_policy
unsequenced_policy
parallel_unsequenced_policy
Какую политику выполнения использовать?
Другие способы ввести SIMD-параллелизм
Резюме
Дополнительная информация
Синхронизация – почему ее нужно избегать и как это сделать
Сквозной пример: гистограмма изображения
Небезопасная параллельная реализация
Первая безопасная параллельная реализация: крупнозернистая блокировка
Варианты мьютексов
Вторая безопасная параллельная реализация: мелкозернистая блокировка
Третья потокобезопасная параллельная реализация: атомарные переменные
Улучшенная параллельная реализация: приватизация и редукция
Поточно-локальная память
Класс enumerable_thread_specific
Тип combinable
Самая простая параллельная реализация: шаблон редукции
Подведем итоги
Резюме
Дополнительная информация
Структуры данных для конкурентного программирования
Основы важнейших структур данных
Неупорядоченные ассоциативные контейнеры
Отображение или множество
Несколько значений
Хеширование
Неупорядоченность
Конкурентные контейнеры
Конкурентные неупорядоченные ассоциативные контейнеры
Конкурентные очереди: обычные, ограниченные и с приоритетами
Конкурентный вектор
Резюме
Масштабируемое выделение памяти
Выделение памяти в современном C++
Масштабируемое выделение памяти: что
Масштабируемое выделение памяти: почему
Избежание ложного разделения с помощью дополнения
Альтернативы масштабируемому выделению памяти: какие
К вопросу о компиляции
Самый популярный способ использования (библиотека прокси для C/C++): как
Linux: использование библиотеки прокси
macOS: использование библиотеки прокси
Windows: использование библиотеки прокси
Тестирование библиотеки прокси
Функции C: масштабируемые распределителя памяти для C
Классы C++: масштабируемые распределители памяти для C++
Распределители с сигнатурой std::allocator
scalable_allocator
tbb_allocator
zero_allocator
cached_aligned_allocator
Поддержка пула памяти: memory_pool_allocator
Поддержка выделения памяти для массивов: aligned_space
Избирательная подмена new и delete
Настройка производительности: некоторые рычаги управления
Что такое большие страницы?
Поддержка больших страниц в TBB
scalable_allocation_mode(int mode, intptr_t value)
TBBMALLOC_USE_HUGE_PAGES
TBBMALLOC_SET_SOFT_HEAP_LIMIT
int scalable_allocation_command(int cmd, void ∗param)
TBBMALLOC_CLEAN_ALL_BUFFERS
TBBMALLOC_CLEAN_THREAD_BUFFERS
Резюме
TBB и параллельные паттерны
Параллельные паттерны и параллельные алгоритмы
Паттерны определяют классификацию алгоритмов, проектных решений и т. д.
Паттерны, которые работают
Параллелизм данных одерживает победу
Паттерн Вложенность
Паттерн Отображение
Паттерн Куча работ
Паттерны редукции (Редукция и Сканирование)
Паттерн Разветвление-соединение
Паттерн Разделяй и властвуй
Паттерн Ветви и границы
Паттерн Конвейер
Паттерн Событийно-управляемая координация (реактивные потоки)
Резюме
Дополнительная информация
Столпы компонуемости
Что такое компонуемость?
Вложенная композиция
Конкурентная композиция
Последовательная композиция
Благодаря каким особенностям библиотека TBB является компонуемой
Пул потоков TBB (рынок) и арены задач
Диспетчер задач в TBB: заимствование работ и не только
Соберем все вместе
Забегая вперед
Управление количеством потоков
Изоляция работ
Привязка задачи к потоку и потока к ядру
Приоритеты задач
Резюме
Дополнительная информация
Использование задач для создания собственных алгоритмов
Сквозной пример: вычисление последовательности
Высокоуровневый подход: parallel_invoke
Высший среди низших: task_group
Низкоуровневый интерфейс: часть первая – блокировка задач
Низкоуровневый интерфейс задач: часть вторая – продолжение задачи
Обход планировщика
Низкоуровневый интерфейс задач: часть третья – рециклинг задач
Контрольный список для интерфейса задач
И еще одно: FIFO-задачи (типа запустил и забыл)
Применение низкоуровневых средств на практике
Резюме
Дополнительная информация
Управление количеством потоков
Краткий обзор архитектуры планировщика TBB
Интерфейсы для управления количеством задач
Управление количеством потоков с помощью task_scheduler_init
Управление количеством потоков с помощью task_arena
Управление количеством потоков с помощью global_control
Сводка концепций и классов
Рекомендации по заданию количества потоков
Использование одного объекта task_scheduler_init в простом приложении
Использование нескольких объектов task_scheduler_init в простом приложении
Использование нескольких арен с разным числом слотов, чтобы подсказать TBB, куда направлять рабочие потоки
Использование global_control для управления количеством потоков, доступных для занятия слотов на аренах
Использование global_control с целью временно ограничить количество доступных потоков
Когда НЕ следует управлять количеством потоков
Что не так?
Резюме
Применение изоляции работы для обеспечения корректности и повышения производительности
Изоляция работ для обеспечения корректности
Создание изолированного региона с помощью this_task_arena::isolate
Использование арен задач для изоляции: обоюдоострый меч
Не поддавайтесь искушению использовать арены задач для изоляции ради корректности
Резюме
Дополнительная литература
Привязка потока к ядру и задачи к потоку
Создание привязки потока к ядру
Создание привязки задачи к потоку
Когда и как следует использовать средства привязки в TBB?
Резюме
Дополнительная информация
Приоритеты задач
Поддержка невытесняющих приоритетов в классе задач TBB
Задание статических и динамических приоритетов
Два простых примера
Реализация приоритетов без поддержки со стороны задач TBB
Резюме
Дополнительная информация
Отмена и обработка исключений
Как отменить коллективную работу
Отмена задач в деталях
Явное назначение TGC
Назначение TGC по умолчанию
Обработка исключений в TBB
Написание собственных классов исключений TBB
Соберем все вместе: компонуемость, отмена и обработка исключений
Резюме
Дополнительная информация
Настройка TBB-алгоритмов: зернистость, локальность, параллелизм и детерминированность
Зернистость задач: какой размер достаточен?
Выбор Диапазонов и Разбивателей для циклов
Обзор разбивателей
Выбирать ли степень детализации для управления зернистостью задач
Диапазоны, Разбиватели и производительность кеша данных
Использование static_partitioner
Ограничение планировщика ради детерминированности
Настройка конвейеров в TBB: количество фильтров, режимы и маркеры
Сбалансированный конвейер
Несбалансированный конвейер
Конвейеры, локальность данных и привязка к потоку
В глубоких водах
Создание собственного типа диапазона
Класс Pipeline и фильтры, привязанные к потоку
Резюме
Дополнительная информация
Потоковые графы: дополнительные сведения
Оптимизация зернистости, локальности и степени параллелизма
Зернистость узла: какой будет достаточно?
Потребление памяти и локальность данных
Арены задач и потоковый граф
Рекомендации по работе с потоковыми графами: что полезно, а что вредно
Полезно: использовать вложенный параллелизм
Вредно: использовать многофункциональные узлы вместо вложенного параллелизма
Полезно: использовать узлы join_node, sequencer_node или multifunction_node для восстановления порядка в потоковом графе, когда это необходимо
Полезно: использовать функцию isolate для вложенного параллелизма
Полезно: использовать отмену и обработку исключений в потоковых графах
Полезно: задавать приоритеты для графа, в котором используется task_group_context
Вредно: создавать ребро между узлами разных графов
Полезно: использовать try_put для передачи информации между графами
Полезно: использовать composite_node для инкапсуляции группы узлов
Введение в Intel Advisor: Flow Graph Analyzer
Процесс проектирования в FGA
Процесс анализа в FGA
Диагностика проблем производительности с помощью FGA
Резюме
Дополнительная информация
Дополнение потоковых графов асинхронными узлами
Пример из асинхронного мира
Зачем и когда использовать async_node?
Более реалистичный пример
Резюме
Дополнительная информация
Накачанные потоковые графы: узлы OpenCL
Пример «Hello OpenCL_Node»
Где исполняется наше ядро?
Возвращаясь к более реалистичному примеру из главы 18
Дьявол кроется в деталях
Концепция NDRange
Поиграем со смещением
Задание ядра OpenCL
Еще о выборе устройства
Предупреждение по поводу порядка
Резюме
Дополнительная информация
TBB в системах с архитектурой NUMA
Определение топологии платформы
Каковы затраты на доступ к памяти
Базовый пример
Мастерство размещения данных и привязки к процессору
Привлекаем hwloc и TBB к совместной работе
Более сложные альтернативы
Резюме
Дополнительная информация
История и предшественники
Десятилетие «от птенца к орлу»
1. Революция TBB внутри Intel
2. Первая революция TBB в сфере параллелизма
3. Вторая революция TBB в сфере параллелизма
4. Птички TBB
Источники идей TBB
Модель ослабленного последовательного выполнения
Библиотеки, оказавшие влияние
Языки, оказавшие влияние
Прагмы, оказавшие влияние
Влияние обобщенного программирования
Учет кешей
Учет стоимости квантования времени
Литература для дополнительного чтения
TBB в кратком изложении
Отладка и условный код
Макросы ознакомительных средств
Диапазоны
Разбиватели
Алгоритмы
Алгоритм: parallel_do
Алгоритм: parallel_for
Алгоритм: parallel_for_each
Алгоритм: parallel_invoke
Алгоритм: parallel_pipeline
Алгоритм: parallel_reduce и parallel_deterministic_reduce
Алгоритм: parallel_scan
Алгоритм: parallel_sort
Алгоритм: pipeline
Потоковый граф
Потоковый граф: класс graph
Потоковый граф: порты и ребра
Потоковый граф: узлы
Выделение памяти
Контейнеры
Синхронизация
Поточно-локальная память (TLS)
Хронометраж
Группы задач: использование планировщика с заимствованием задач
Планировщик задач: точный контроль над планировщиком с заимствованием задач
Настройки плавающей точки
Исключения
Потоки
Parallel STL
Глоссарий
Предметный указатель