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

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

Описание

В курсе будет рассказано про

  • многопоточное программирование на примере
    • С++: POSIX threads, Boost, OpenMP, Intell TBB и
    • Java: threads, java.util.concurrent, Fork/Join framewok
  • теорию параллельных вычислений: алгоритмы консенсуса, атомарные регистры, lock-free и wait-free алгоритмы, шаблоны || программирования
  • вычислительные кластеры (на примере MPI)
  • другие способы повышения производительности (транзакционная память, асинхронный ввод/вывод...)

google-проект курса с репозиторием и wiki: http://code.google.com/p/hpcource.

Домашние задания: http://code.google.com/p/hpcource/wiki/Tasks_CS_Center.

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

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

Введение
  • Тенденции развития вычислительных систем
  • Классификация параллельных систем (SIMD, MISD..., SMP, MPP)
  • Современные высокопроизводительные системы: начиная от расширений SSE, через многоядерность к узлам кластеров
  • План курса
Корректная работа с потоками
  • Механизм запуска потока
  • Корректное завершение потоков
  • Сравнение различных потоков (POSIX, boost, java)
  • Обработка исключений
  • Необходимость синхронизации
Примитивы синхронизации
  • Необходимость синхронизации: гонки данных
  • Реализация примитивов синхронизации: алгоритмы Петерсона и Лампорта
  • Виды мьютексов: рекурсивные/нерекурсивные, читатели/писатели...
  • Корректные захват/освобождение примитивов
  • CAS-операции и атомики
Примитивы синхронизации — 2
  • Condition variables: использование wait/notify
  • Алгоритмы синхронизации: грубая, тонкая
Алгоритмы синхронизации
  • Алгоритмы синхронизации: оптимистичная, неблокирующая
  • Классы алгоритмов: lock-free, wait-free
  • Пулы потоков
Ошибки || программирования
  • Гонки данных (Data Race)
  • Взаимная блокировка (Deadlock)
  • Блокировки при fork многопоточных программ
  • Инверсия приоритетов
Атомарные снимки регистров
  • SWMR-регистры
  • Lock-free snapshot
  • Wait-free snapshot
OpenMP и Intel TBB
  • Обзор OpenMP: параллельные секции, области видимости переменных, ограничения
  • Обзор Intel TBB: алгоритмы, аллокаторы, деревья задач, планирование
Шаблоны || программирования
  • Структурные шаблоны
    • Декомпозиция по задачам
    • Геометрическая декомпозиция
    • Recursive Data
    • Pipeline
  • Некоторые программные структуры
    • Parallel loops
    • Boss/Worker
  • Разное
    • Double check
    • Local Serializer
Кластерные вычисления
  • История и назначение стандарта
  • Обмен сообщениями
    • С блокировкой
    • Без блокировки
    • Отложенные запросы на взаимодействие
    • Тупиковые ситуации (deadlock)
  • Взаимодействие процессов
    • Группы и коммуникаторы
    • Операции коллективного взаимодействия процессов
    • Редукция
    • Виртуальные топологии
  • Средства анализа производительности
Map/Reduce - теория и практика
  • Идея Map/Reduce
  • Hadoop
    • Обзор архитектуры
    • Примеры задач
    • Детали реализации
    • Популярные расширения
  • Другие реализации M/R: достоинства и недостатки
    • Проблемы Hadoop
    • Spark
    • Disco
  • Дополнительно
    • Что не надо использовать для построения M/R приложений
    • Отказоустойчивость M/R приложений
Консенсус. Сети Петри
  • Консенсус
    • Консенсусное число RMW-регистров
    • Универсальность CAS-операций
  • Верификация || программ (сети Петри)
Транзакционная память. Асинхронный ввод/вывод
  • Транзакционая память
    • Software transactional memory
    • Hardware transactional memory
    • Пример на протоколе MESI
    • Немного о барьерах (store/load)
  • Асинхронный ввод/вывод
    • Блокирующий/неблокирующий
    • Синхронный (реактор)/асинхронный (проактор)