Параллельное программирование
Санкт-Петербург, весна 2015
Описание
В курсе будет рассказано о многопоточном программировании на примере:
- С++: POSIX threads, Boost, OpenMP, Intel TBB
- Java: threads, java.util.concurrent, Fork/Join framewok
А также немного из теории параллельных вычислений
- алгоритмы консенсуса
- атомарные регистры
- lock-free и wait-free алгоритмы
- шаблоны || программирования
И другие способы повышения производительности (кластеры, транзакционная память, асинхронный ввод/вывод...)
google-проект курса с репозиторием и wiki: http://code.google.com/p/hpcource
Преподаватели
Список лекций
Введение в || вычисления
- Современные высокопроизводительные системы: от SSE к Cloud Computing
- Краткий обзор технологий по уровням абстракции:
- Native OS Threads (Posix, Windows...)
- Threads (Boost, Java...)
- OpenMP
- Java.util.concurrent
- Intel TBB, Fork/Join framework
- Transactional memory
- План курса
Корректная работа с потоками
- Корректное завершение потоков (с примерами реализации pthreads в glibc)
- Ожидание
- Принудительное прерывание
- Завершение потока через сигнал
- Механизм interruption points - InterruptedException
- Параллели API работы с потоками (Posix - Boost/C++11 - Java)
Примитивы синхронизации
- Необходимость синхронизации
- Алгоритмы Лампорта и булочника
- Основные примитивы:
- Мьютексы рекурсивные/нерекурсивные
- Read/Write мьютексы
- Spin-мьютекс
Примитивы синхронизации - 2
- CAS-операции
- Атомики
- Корректное освобождение ресурсов (locks/finally)
- Условные переменные (wait/notify)
- Пулы потоков
P.S. Слайды - продолжение предыдущей лекции
Ошибки || программирования
- Гонки данных (Data Race)
- Взаимная блокировка (Deadlock)
- Блокировки при fork многопоточных программ
- Инверсия приоритетов
Предполагается показать как некоторые виды ошибок можно найти при помощи: * Valgrind * Intel || Studio * Google Thread Sanitizer
Пулы потоков. Начало алгоритмов синхронизации
- Устройство пула потоков на примере FixedThreadPool
- Концепция Future
- Обработка исключений
- Thread Local Storage (TLS)
- Алгоритмы синхронизации:
- Грубая
- Тонкая
Алгоритмы синхронизации
- Алгоритмы синхронизации:
- Оптимистичная
- Ленивая
- Lock-free
- Понятие Wait-free алгоритмов
- Проблема ABA
Технологии: OpenMP, Intel TBB
- OpenMP:
- параллельные секции
- области видимости переменных
- ограничения
- Intel TBB:
- алгоритмы планирования
- аллокаторы
- деревья задач
- граф исполнения задач
Атомарные снимки регистров
- SWMR-регистры
- Lock-free snapshot
- Wait-free snapshot
- SWMR
P.S. Из слайдов на лекции рассматривался только первый
Шаблоны || программирования
- Классификация шаблонов
- Декомпозиция по задачам
- Геометрическая декомпозиция
- Управление потоком данных
- Шаблоны:
- Recursive Data
- Pipeline
- Boss/Worker
- Double check
- Local Serializer
- ...
- Асинхронный ввод/вывод:
- Проактор
- Реактор
Транзакционая память
- Software transactional memory
- Hardware transactional memory
- Пример на протоколе MESI
- Немного о барьерах (store/load)
Анализ производительности и верификация
- Средства профилирования на практике:
- Valgrind
- Intel || Studio
- Google Thread Sanitizer
- Виды профилирования
- Сети Петри
- Идея
Model checking
Консенсус. Кластерные вычисления
- Консенсус
- Функция консенсуса
- Консенснусное число примитивов
- Кластерые вычисления
- Виды кластеров
- Стандарт MPI