Параллельное программирование

Санкт-Петербург, весна 2018

Описание

Курс рассматривает принципы и возможности многопоточного программирования в теории и на практике:

  • многопоточное рограммирование
  • теория || программирования
  • иные методы повышения производительности систем

Полная программа курса

Дополнительные задания:

Преподаватели

Список лекций

Введение
  • Задачи систем высокой производительности
  • Современные высокопроизводительные системы: начиная от расширений SSE, через многоядерность к узлам кластеров
  • Понятия ускорения, эффективности (закон Амдала -> влияние синхронизации)
  • Многопоточность или IPC
Корректное завершение потоков
  • Штатное ожидание join
  • Прерывание через cancel на примере POSIX
  • cancellation points
  • InterruptedException для Java
Примитивы синхронизации
  • Виды примитивов:
    • mutex (рекурсивные / не рекурсивные)
    • shared_mutex
    • spin
    • futex
    • condition variables
  • CAS-операции и атомики
Условные переменные
  • POSIX condition variables
  • Wait/notify на java
  • Spurious wakeups
Алгоритмы синхронизации
  • Алгоритмы синхронизации:
    • Грубая
    • Тонкая
    • Оптимистичная
    • Ленивая
    • Неблокирующая
  • Flat Combining
Атомарные снимки регистров
  • Классы алгоритмов:
    • lock-free
    • wait-free
  • lock-free snapshot
  • wait-free snapshot
Ошибки || программирования
  • Гонки данных (Data Race)
  • Взаимная блокировка (Deadlock)
    • Блокировки при fork многопоточных программ
    • Перекрёстный Deadlock
    • Deadlock на нерекурсивном примитиве
  • Проблема ABA
  • Инверсия приоритетов
Модели памяти и проблемы видимости
  • Устройство процессора (кэши, очереди, буферы)
  • Пример на протоколе MESI
  • Барьеры памяти (store/load)
  • Acquire/release семантика
  • Модели памяти: Sequential consistency...
Применение барьеров памяти
  • Перечисление барьеров памяти в C++ atomic
  • Необходимость volatile для Java
  • Пример ошибки в ядре ОС из-за отсутствия одного из барьеров
  • Случаи неявного применения барьеров памяти
Транзакционная память
  • Идея transactional memory:
    • Software transactional memory
    • Hardware transactional memory
  • Преимущества и круг задач
  • Способ реализации HTM на линейках кэша
  • Техника Lock teleportation для тонкой синхронизации
Профилирование многопоточных приложений
  • Средства анализа производительности:
    • Утилита time
    • Intel Parallel Studio
    • Valgrind (модуль callgrind)
  • Пример поиска узких мест
  • Пример оценки адекватноси синхронизации потоков
OpenMP и Intel TBB
  • Обзор OpenMP:
    • параллельные секции
    • области видимости переменных
    • ограничения
    • применение к миграции вычислений
  • Обзор Intel TBB:
    • алгоритмы
    • аллокаторы
    • деревья задач
    • особенности планирования (work stealing…)
    • flow graphs
Шаблоны || программирования
  • Виды организации вычислений:
    • Разделение по данным
    • Разделение по задачам
    • Управление потоком данных
  • Шаблоны:
    • Recursive Data
    • Pipeline
    • Double check
    • Thread Pool (на примере java.util.concurrent)