Параллельное программирование
Санкт-Петербург, весна 2019
Описание
Курс рассматривает принципы и возможности многопоточного программирования в теории и на практике:
- многопоточное рограммирование
- теория || программирования
- иные методы повышения производительности систем
Дополнительные задания:
- Реализация lock-free алгоритмов и доведение до ума Pull Request'ов из libcds
- Решение задач из различных открытых проектов, связанных с hpc, например:
Преподаватели
Список лекций
Введение. Процессы / потоки
- Задачи систем высокой производительности
- Современные высокопроизводительные системы: начиная от расширений SSE, через многоядерность к узлам кластеров
- Понятия ускорения, эффективности (закон Амдала -> влияние синхронизации)
- Многопоточность или взаимодействие процессов
Корректное завершение потоков
- Штатное ожидание через join
- Прерывание через pthread_cancel
- Cancellation points
- Защита от прерывания
- InterruptedException для Java
Примитивы синхронизации: kernel/user space, различные mutex
- Kernel / user space
- Виды mutex:
- mutex (рекурсивные / не рекурсивные)
- shared_mutex
- spin_mutex
- CAS-операции и атомики
Примитивы синхронизации: futex, condition variables
- Реализация примитивов на основе futex
- POSIX condition variables
- Wait/notify на java
- Spurious wakeups
Ошибки || программирования: Deadlock и Data Race
- Взаимная блокировка (Deadlock)
- Перекрёстный Deadlock
- Deadlock на нерекурсивном примитиве
- Deadlock при fork многопоточных приложениях
- Гонки данных (Data Race)
- Пример на записи 64-битного числа
- Пример с инкрементом, чтением и записью переменной
Алгоритмы синхронизации
- Грубая
- Тонкая
- Оптимистичная
- Ленивая
- Неблокирующая
Атомарные снимки регистров
- Классы алгоритмов:
- lock-free
- wait-free
- lock-free snapshot
- wait-free snapshot
Ограничения и обоснованность применения алгоритмов. Проблема ABA
- wait-free в система жёсткого реального времени
- Проблема с lock-free для перекладывания между структурами данных
- Проблема ABA и решения (LL / SC в том числе)
Проблема видимости переменных. Устройство процессора
Устройство процессора ** Store buffer ** Invalidate queue
Пример на протоколе MESI проблемы поздней видимости операций
Барьеры памяти. Модели памяти
- Барьеры памяти (store/load)
- Acquire/release семантика
- Модели памяти: Sequential consistency...
- Перечисление барьеров памяти в C++ atomic
- Необходимость volatile для Java
- Пример ошибки в ядре ОС из-за отсутствия одного из барьеров
- Случаи неявного применения барьеров памяти
Профилирование приложений
- Средства анализа производительности:
- Утилита time
- Intel Parallel Studio
- Valgrind (модуль callgrind)
- Пример поиска узких мест
- Пример оценки адекватноси синхронизации потоков
Транзакционная память
- Идея transactional memory:
- Software transactional memory
- Hardware transactional memory
- Преимущества и круг задач
- Способ реализации HTM на линейках кэша
- Техника
Lock teleportation
для тонкой синхронизации - Текущее состояние реализации HTM в C++
Java.util.concurrent. Профилирование Cache miss
- Пулы потоков на примере ExecutorService
- Контроль задач через Future
- Пример профилирования промашек по кэшу на суммировании матриц
Линеаризуемость. Lock-free очередь. Flat Combining
- Понятие линеаризуемости
- Lock-free стек Trieber
- Lock-free очередь Michael & Scott
- Точки линеаризации
- Flat combining
OpenMP и Intel TBB
- Обзор OpenMP:
- параллельные секции
- области видимости переменных
- ограничения
- применение к миграции вычислений
- Обзор Intel TBB:
- алгоритмы
- аллокаторы
- деревья задач
- особенности планирования (work stealing…)
- flow graphs