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