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

Санкт-Петербург, весна 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
Асинхронный ввод/вывод
  • Блокирующий/неблокирующий
  • Синхронный (реактор)/асинхронный (проактор)
  • Преимущества асинхронной работы и реализация со стороны операционной системы