Параллельное программирование
Санкт-Петербург, весна 2022
Описание
Курс рассматривает принципы и возможности многопоточного программирования в теории и на практике:
- многопоточное рограммирование (принципы, ошибки, технологии)
- элементы теории || программирования (алгоритмы)
- иные методы повышения производительности систем
Из полной программы выбираются избранные темы в зависимости от скорости освоения материала
Преподаватели
Список лекций
Введение. Многопоточность или IPC
- Примеры вычислительно ёмких задач из разных областей науки
- Процессы и потоки
- Деревья процессов
- План курса
- Многопоточность или IPC
Создание/завершение потоков
- Ожидание через join
- POSIX:
- Прерывание через pthread_cancel
- Cancellation points
- Защита от прерывания
- Java:
- InterruptedException
- Обход отсутствия запрета на прерывание
Примитивы синхронизации
Обоснование необходимости
Kernel / user space
Связь ресурса и примитива синхронизации
Виды mutex:
mutex (рекурсивные / не рекурсивные)
read / write mutex
Примитивы синхронизации - 2 (spin, conditional). Обработка сигналов
- CAS-операции
- Spin lock
- AtomicInteger
- Condition variables
- Обработка сигналов
Ошибки || программирования
- Взаимная блокировка (Deadlock)
- Перекрёстный Deadlock
- Deadlock на нерекурсивном примитиве
- Deadlock при fork многопоточных приложениях
- Инверсия приоритетов
Алгоритмы синхронизации
- Грубая
- Тонкая
- Оптимистичная
- Ленивая
- Неблокирующая
Атомарные снимки регистров
- Классификация алгоритмов:
- lock-free
- wait-free
- Lock-free snapshot
- Wait-free snapshot
Модель памяти: поиск ошибки, базовая модель процессора
- gdb
- strace
- VFS
- Модель процессора
- Устройство процессора и MESI
Модель памяти: барьеры памяти, модели памяти
- Барьеры памяти (store/load)
- Acquire/release семантика
- Модели памяти: Sequential consistency...
- volatile для Java
Профилирование
- Средства анализа производительности:
- Утилита time
- Valgrind (модуль callgrind)
- Intel OneAPI
- Поиск узких мест по утилизации процессора
- Анализ ожиданий и блокировок
- Профилирование промашек по кэшу
Проблема ABA. TLS. Линеаризуемость
- Проблема ABA
- TLS и его применение
- Понятие линеаризуемости
- Lock-free стек Trieber
Асинхронный ввод/вывод. Coroutines
- Блокирующий/неблокирующий
- Синхронный (реактор)/асинхронный (проактор)
- Преимущества асинхронной работы и реализация со стороны операционной системы
- Преимущества по отношению к callback-программированию
- Примеры co_await и сравнение с синхронным кодом
Шаблоны || программирования
- Структурные шаблоны:
- Декомпозиция по задачам
- Геометрическая декомпозиция
- Recursive Data
- Pipeline
Некоторые программные структуры:
Parallel loops
Boss/Worker
Принцип работы OpenMP
Принцип работы Intel TBB
- Единый планировщик
- pipline
- flow graph
Транзакционная память
- Идея transactional memory:
- Software transactional memory
- Hardware transactional memory
- Преимущества и круг задач
- Способ реализации HTM на линейках кэша
- Техника
Lock teleportation
для тонкой синхронизации - Текущее состояние реализации HTM