Параллельное программирование
Санкт-Петербург, весна 2017
Описание
Курс рассматривает принципы и возможности многопоточного программирования в теории и на практике:
- многопоточное рограммирование
- теория || программирования
- иные методы повышения производительности систем
Преподаватели
Список лекций
Введение
- Задачи систем высокой производительности
- Современные высокопроизводительные системы: начиная от расширений SSE, через многоядерность к узлам кластеров
- Понятия ускорения, эффективности (закон Амдала -> влияние синхронизации)
- Многопоточность или IPC
Корректная работа с потоками
- Корректное завершение потоков:
- cancellation points (примеры кода в glibc)
- interrupted exception
- Реализация примитивов синхронизации для 2 и N потоков
- Виды мьютексов:
- рекурсивные/нерекурсивные
- read/write
Примитивы синхронизации
- Виды примитивов (продолжение):
- spin
- futex
- condition variables
- CAS-операции и атомики
- Проброс исключений между потоками
Алгоритмы синхронизации
- Алгоритмы синхронизации:
- Оптимистичная
- Ленивая
- Неблокирующая
- Классы алгоритмов:
- lock-free
- wait-free
Ошибки || программирования
- Гонки данных (Data Race)
- Взаимная блокировка (Deadlock)
- Блокировки при fork многопоточных программ
- Перекрёстный Deadlock
- Deadlock на нерекурсивном примитиве
- Проблема ABA
- Инверсия приоритетов
Модели памяти и проблемы видимости
- Устройство кэшей процессора
- Пример на протоколе MESI
- Барьеры памяти (store/load)
- Модели памяти: Sequential consistency...
- Acquire/release семантика
Профилирование многопоточных приложений
- Средства анализа производительности
- Утилита time
- Intel Parallel Studio
- Valgrind (модули callgrind, cachegrind)
- Пример поиска узких мест
Распределённые вычисления
- MapReduce
- Архитектура Hadoop
- Архитектура Spark
Атомарные снимки регистров. Сети Петри
- Атомарный снимок регистров
- Lock-free
- Wait-free
- Сети Петри
Java.util.concurrent. OpenMP
- Пулы потоков
- Контроль задач через Future
- Оптимизации JIT по синхронизации
- Обзор OpenMP:
- параллельные секции
- области видимости переменных
- ограничения
- применение к миграции вычислений
Intel TBB. Шаблоны || программирования
- Обзор Intel TBB:
- алгоритмы
- аллокаторы
- деревья задач
- особенности планирования (work stealing…)
- flow graphs
- Виды вычислений:
- Декомпозиция по задачам
- Декомпозиция по данным
- Управляемые потоком данных
- Шаблоны:
- Recursive Data
- Pipeline
- Double check
Транзакционная память
- Идея transactional memory:
- Software transactional memory
- Hardware transactional memory
- Преимущества и круг задач