Параллельное программирование
Санкт-Петербург, весна 2020
Описание
Курс рассматривает принципы и возможности многопоточного программирования в теории и на практике:
- многопоточное рограммирование
- теория || программирования
- иные методы повышения производительности систем
Преподаватели
Список лекций
Введение. Процессы / потоки
- Задачи систем высокой производительности
- Расширения SSE
- Многопоточность или взаимодействие процессов
- Краткий обзор технологий многопоточного программирования
- Закон Амдала -> влияние синхронизации
Примитивы синхронизции
- Kernel / user space
- Виды mutex:
- mutex (рекурсивные / не рекурсивные)
- read / write mutex
- spin mutex
- CAS-операции и AtomicInteger
- Condition variables
Механизмы завершения потоков
- Ожидание через join
- Прерывание через pthread_cancel
- Cancellation points
- Защита от прерывания
- InterruptedException
- Запрет на прерывание на POSIX и Java
- Внимание на блокирующем IO
Алгоритмы синхронизации. TLS
Алгоритмы на примере односвязного списка:
- Грубая
- Тонкая
- Оптимистичная
- Ленивая
- Неблокирующая
Thread Local Storage:
- Принцип работы
- Пример использования с DbAccessor
Ошибки || программирования
- Взаимная блокировка (Deadlock)
- Перекрёстный Deadlock
- Deadlock на нерекурсивном примитиве
- Deadlock при fork многопоточных приложениях
- Гонки данных (Data Race)
- Пример на записи 64-битного числа
- Пример с инкрементом, чтением и записью переменной
- Инверсия приоритетов
- Проблема ABA
Snapshot атомарных регистров
- Классы алгоритмов:
- lock-free
- wait-free
- lock-free snapshot
- wait-free snapshot
Модели памяти и проблемы видимости
- Барьеры памяти (store/load)
- Acquire/release семантика
- Модели памяти: Sequential consistency...
- Необходимость volatile для Java
- Пример ошибки в ядре ОС из-за отсутствия одного из барьеров
Профилирование приложений
- Средства анализа производительности:
- Утилита time
- Intel Parallel Studio
- Valgrind (модуль callgrind)
- Пример поиска узких мест
- Пример профилирования промашек по кэшу
Очередь Michael-Scott. Flat-combining
- Понятие линеаризуемости
- Lock-free стек Trieber
- Lock-free очередь Michael & Scott
- Точки линеаризации
- Flat combining
Транзакционная память
- Идея transactional memory:
- Software transactional memory
- Hardware transactional memory
- Преимущества и круг задач
- Способ реализации HTM на линейках кэша
- Техника
Lock teleportation
для тонкой синхронизации - Текущее состояние реализации HTM в C++ и Java
RCU
- Суть RCU и синхронизация на эпохах
- Kernel-space RCU
- User-space RCU
OpenMP и Intel TBB
- Обзор OpenMP:
- параллельные секции
- области видимости переменных
- применение к миграции вычислений
- Обзор Intel TBB:
- алгоритмы
- аллокаторы
- деревья задач
- особенности планирования (work stealing…)
- flow graphs