Параллельное программирование
Санкт-Петербург, весна 2016
Описание
Курс рассматривает принципы и возможности многопоточного программирования в теории и на практике:
- многопоточное рограммирование
- теория || программирования
- иные методы повышения производительности систем
Страница курса: http://wiki.osll.ru/doku.php/courses:high_performance_computing:start
Преподаватели
Список лекций
Введение
- Тенденции развития вычислительных систем
- Классификация параллельных систем (SIMD, MISD…, SMP, MPP)
- Современные высокопроизводительные системы: начиная от расширений SSE, через многоядерность к узлам кластеров
- Понятия ускорения, эффективности (закон Амдала -> влияние синхронизации)
- План курса
Корректная работа с потоками
- Механизм запуска потока
- Корректное завершение потоков:
- cancellation points (примеры кода в glibc)
- interrupted exception
- Сравнение различных потоков (POSIX, boost/С++11, java)
- Проброс исключений между потоками
Примитивы синхронизации
- Необходимость синхронизации: простые гонки данных
- Реализация примитивов синхронизации: алгоритм булочника
- Виды мьютексов:
- рекурсивные/нерекурсивные
- read/write
- spin
- futex
- CAS-операции и атомики
Condition variables. Алгоритмы синхронизации
- Condition variables:
- Пример на POSIX
- Пример на Java
- Алгоритмы синхронизации:
- Грубая
- Тонкая
Алгоритмы синхронизации
- Алгоритмы синхронизации:
- Оптимистичная
- Ленивая
- Неблокирующая
- Классы алгоритмов:
- lock-free
- wait-free
- lock-free алгоритм снятия снэпшота атомарных регистров
Ошибки || программирования
- Основные ошибки многопоточного программирования
- Гонки данных (Data Race)
- Взаимная блокировка (Deadlock)
- Потерянный сигнал
- Специфические ошибки
- Реакция потока на сигнал
- Блокировки при fork многопоточных программ
- Проблема ABA
- Инверсия приоритетов
Атомарные снимки регистров
- Wait-free атомарный снимок регистров
- Решение проблемы ABA на tagged pointers
Java.util.concurrent
- Пример CAS и ORM
- Пулы потоков
- Контроль задач через Future
- Потокобезопасные контейнеры
OpenMP и Intel TBB
- Обзор OpenMP:
- параллельные секции
- области видимости переменных
- ограничения
- Обзор Intel TBB:
- алгоритмы
- аллокаторы
- деревья задач
- особенности планирования (work stealing…)
- flow graphs (параллель с BPEL)
Профилирование многопоточных приложений
- Средства анализа производительности
- Утилита time
- Intel Parallel Studio
- Valgrind (модули callgrind, cachegrind)
- Пример поиска узких мест
Модели памяти и проблемы видимости
- Устройство кэшей процессора
- Пример на протоколе MESI
- Барьеры памяти (store/load)
- Модели памяти: Sequential consistency...
- Acquire/release семантика
Шаблоны || программирования. Консенсус
- Структурные шаблоны:
- Декомпозиция по задачам
- Геометрическая декомпозиция
- Recursive Data
- Pipeline
- Разное:
- Double check
- Local Serializer
- Консенсус:
- Консенсусное число RMW-регистров
- Универсальность CAS-операций
Транзакционная память. Сети Петри
- Идея transactional memory:
- Software transactional memory
- Hardware transactional memory:
- Преимущества и круг задач
- Верификация || программ:
- Model Checking
Асинхронный ввод/вывод
- Блокирующий/неблокирующий
- Синхронный (реактор)/асинхронный (проактор)
- Преимущества асинхронной работы и реализация со стороны операционной системы