Параллельное программирование
Санкт-Петербург, весна 2018
Описание
Курс рассматривает принципы и возможности многопоточного программирования в теории и на практике:
- многопоточное рограммирование
- теория || программирования
- иные методы повышения производительности систем
Дополнительные задания:
- Реализация lock-free алгоритмов и доведение до ума Pull Request'ов из libcds
- Решение задач из различных открытых проектов, связанных с hpc, например:
Преподаватели
Список лекций
Введение
- Задачи систем высокой производительности
- Современные высокопроизводительные системы: начиная от расширений SSE, через многоядерность к узлам кластеров
- Понятия ускорения, эффективности (закон Амдала -> влияние синхронизации)
- Многопоточность или IPC
Корректное завершение потоков
- Штатное ожидание join
- Прерывание через cancel на примере POSIX
- cancellation points
- InterruptedException для Java
Примитивы синхронизации
- Виды примитивов:
- mutex (рекурсивные / не рекурсивные)
- shared_mutex
- spin
- futex
- condition variables
- CAS-операции и атомики
Условные переменные
- POSIX condition variables
- Wait/notify на java
- Spurious wakeups
Алгоритмы синхронизации
- Алгоритмы синхронизации:
- Грубая
- Тонкая
- Оптимистичная
- Ленивая
- Неблокирующая
- Flat Combining
Атомарные снимки регистров
- Классы алгоритмов:
- lock-free
- wait-free
- lock-free snapshot
- wait-free snapshot
Ошибки || программирования
- Гонки данных (Data Race)
- Взаимная блокировка (Deadlock)
- Блокировки при fork многопоточных программ
- Перекрёстный Deadlock
- Deadlock на нерекурсивном примитиве
- Проблема ABA
- Инверсия приоритетов
Модели памяти и проблемы видимости
- Устройство процессора (кэши, очереди, буферы)
- Пример на протоколе MESI
- Барьеры памяти (store/load)
- Acquire/release семантика
- Модели памяти: Sequential consistency...
Применение барьеров памяти
- Перечисление барьеров памяти в C++ atomic
- Необходимость volatile для Java
- Пример ошибки в ядре ОС из-за отсутствия одного из барьеров
- Случаи неявного применения барьеров памяти
Транзакционная память
- Идея transactional memory:
- Software transactional memory
- Hardware transactional memory
- Преимущества и круг задач
- Способ реализации HTM на линейках кэша
- Техника
Lock teleportation
для тонкой синхронизации
Профилирование многопоточных приложений
- Средства анализа производительности:
- Утилита time
- Intel Parallel Studio
- Valgrind (модуль callgrind)
- Пример поиска узких мест
- Пример оценки адекватноси синхронизации потоков
OpenMP и Intel TBB
- Обзор OpenMP:
- параллельные секции
- области видимости переменных
- ограничения
- применение к миграции вычислений
- Обзор Intel TBB:
- алгоритмы
- аллокаторы
- деревья задач
- особенности планирования (work stealing…)
- flow graphs
Шаблоны || программирования
- Виды организации вычислений:
- Разделение по данным
- Разделение по задачам
- Управление потоком данных
- Шаблоны:
- Recursive Data
- Pipeline
- Double check
- Thread Pool (на примере java.util.concurrent)