Программа

1. Введение

Тенденции развития вычислительных систем, обуславливающие необходимость применения распределённых (параллельных) методов вычислений. Примеры вычислительно ёмких задач из разных областей науки.

Классификация параллельных систем (SIMD, MISD…, SMP, MPP)

Современные высокопроизводительные системы: начиная от расширений SSE, через многоядерность к узлам кластеров

Понятия ускорения, эффективности (закон Амдала)

План курса

2. Создание/завершение потоков

Механизм запуска потока

Корректное завершение потоков:

cancellation points

interrupted exception

примеры кода в glibc

Сравнение различных потоков (POSIX, boost, java)

Проброс исключений между потоками

3. Примитивы синхронизации

Необходимость синхронизации: простые гонки данных

Реализация примитивов синхронизации: алгоритм булочника

Виды мьютексов:

рекурсивные/нерекурсивные

read/write

spin

futex

Корректные захват/освобождение примитивов

CAS-операции и атомики

Условные переменные:

использование wait/notify

Spurious wakeups

4. Алгоритмы синхронизации

Грубая

Тонкая

Оптимистичная

Ленивая

Неблокирующая (параллель с ORM)

5. Атомарные снимки регистров

Классификация алгоритмов:

lock-free

wait-free

SWMR-регистры

Lock-free snapshot

Wait-free snapshot

6. Ошибки || программирования

Основные ошибки многопоточного программирования

Гонки данных (Data Race)

Взаимная блокировка (Deadlock)

Потерянный сигнал

Специфические ошибки

Реакция потока на сигнал

Блокировки при fork многопоточных программ

Проблема ABA

Инверсия приоритетов

7. Профилирование многопоточных приложений

Средства анализа производительности

Утилита time

Intel Parallel Studio

Valgrind (модули callgrind, cachegrind)

Пример поиска узких мест

8. Java.util.concurrent и Fork-Join Framework

Пулы потоков, корректное завершение пула

Контроль задач через Future

Потокобезопасные контейнеры

9. OpenMP и Intel TBB

Обзор OpenMP:

параллельные секции

области видимости переменных

ограничения

Обзор Intel TBB:

алгоритмы

аллокаторы

деревья задач

особенности планирования (work stealing…)

flow graphs (параллель с BPEL)

10. Шаблоны || программирования

Структурные шаблоны:

Декомпозиция по задачам

Геометрическая декомпозиция

Recursive Data

Pipeline

Некоторые программные структуры:

Parallel loops

Boss/Worker

Разное:

Double check

Local Serializer

11. Кластерные вычисления

Виды кластерных систем:

Балансировки нагрузки

Высокой надёжности

Вычислительные

История и назначение стандарта MPI

Обмен сообщениями:

С блокировкой

Без блокировки

Отложенные запросы на взаимодействие

Взаимодействие процессов:

Группы и коммуникаторы

Операции коллективного взаимодействия процессов

Редукция

Виртуальные топологии

Средства анализа производительности:

Jumpshot

Intel® Trace Analyzer и Intel® Trace Collector

12. Консенсус. Сети Петри

Линеаризуемость

Консенсус:

Консенсусное число RMW-регистров

Универсальность CAS-операций

Верификация || программ (сети Петри)

13. Оптимизации в компиляторах

Статические оптимизации

Оптимизации циклов:

Развёртывание

Повторение

Вынесение инварианта

JIT-оптимизации

Объединение захвата примитивов

Оптимистичный захват

Адаптивные блокировки

Замена виртуального вызова

14. Транзакционная память

Идея transactional memory

Software transactional memory

Hardware transactional memory:

Преимущества и круг задач

15. Асинхронный ввод/вывод

Блокирующий/неблокирующий

Синхронный (реактор)/асинхронный (проактор)

Преимущества асинхронной работы и реализация со стороны операционной системы

Библиотеки асинхронного ввода/вывода

16. Wait-free MRMW снимок регистров

Напоминание о MRSW алгоритме

Переход к bounded версии на битовых handchake

Расширание до MRMW

17. Средства поиска ошибок

Google Thread Sanitizer

Intel Parallel Studio

Valgrind (модуль helgrind)

Пример использования

18. Модель памяти

Устройство кэшей процессора

Пример на протоколе MESI

Барьеры памяти (store/load)

Модели памяти: Sequential consistency…

Acquire/release семантика

19. Lock-free изнутри

User-space RCU

Схемы управления памятью:

Tagged pointers

Hazard pointer

20. Модель акторов

Суть модели

Применение в современных языках

Шаблоны применения