Программа

0. Введение

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

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

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

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

План курса

Старт потока (Java): реализация Runnable vs наследование от Thread

Напоминание о процессах и потоках: дерево процессов, демоны

1. Многопоточность или IPC

Виды IPC

Преимущества многопоточности:

Простота

Скорость (TLB)

Преимущества IPC:

Безопасность

Надёжность

Сложности реализации shmem

2. Завершение потоков

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

cancellation points

interrupted exception

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

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

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

Напоминание о user space / kernel space и соответствующей стоимости syscall

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

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

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

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

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

read/write

spin

futex

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

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

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

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

Spurious wakeups

Thread Local Storage (TLS)

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

Грубая

Тонкая

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

Ленивая

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

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

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

lock-free

wait-free

Lock-free snapshot

Wait-free snapshot

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

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

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

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

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

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

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

Проблема ABA

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

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

Пример ошибки в ядре ОС

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

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

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

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

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

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

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

Утилита time

Intel Parallel Studio

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

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

Профилирование промашек по кэшу и метрика CPI

9. Flat-Combining

Схема Flat-Combining

Возможные оптимизации за счёт интерференции операций

Сравнение производительности с lock-free очередью Michael & Scott

10. RCU

Суть RCU и синхронизация на эпохах

Kernel-space RCU

User-space RCU

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

Идея transactional memory

Software transactional memory

Hardware transactional memory

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

Реализация HTM на линейках кэша

Lock teleportation

12. Сети Петри

Суть модели сетей Петри

Пример с обедающими философами

Верификация || программ

13. Консенсус

Консенсус:

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

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

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

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

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

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

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

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

Понятие линеаризуемости

Lock-free стек Trieber

Пример на очередях

Lock-free очередь Michael & Scott

Точки линеаризации

Relaxed SkipList

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

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

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

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

Повторение

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

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

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

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

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

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

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

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

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

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

Recursive Data

Pipeline

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

Parallel loops

Boss/Worker

Разное:

Double check

Local Serializer

18. OpenMP

Архитектура работы через директивы препроцессора

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

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

Ограничения

Миграция вычислений

19. Intel TBB

Алгоритмы

Аллокаторы

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

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

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

20. Кластерные вычисления (MPI)

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

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

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

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

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

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

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

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

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

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

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

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

Редукция

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

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

Jumpshot

Intel® Trace Analyzer и Intel® Trace Collector

21. Сопрограммы / Coroutines

Преимущества по отношению к callback-программированию

Примеры co_await и сравнение с синхронным кодом

Проблемы реализации примитивов и TLS

Архитектурная аналогия с асинхронными framework

22. Акторная модель

Суть модели:

Передача сообщений

Легковесные процессы

BEAM

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

Erlang

Elixir

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

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

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

CompletionStage и CompletableFuture

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

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

Google Thread Sanitizer

Intel Parallel Studio

Valgrind (модуль helgrind)

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

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

Feldman Multi Array

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

Tagged pointers

Hazard pointer

26. Системы потоковой обработки данных

Analytics vs Streaming

Гарантии обработкии данных:

Exactly once

At least once

At most once

Windows

Session

Sliding

Tumbling

Hopping

Linear scalability

Fault tolerance

Back pressure

Isolation

Qutoing

MillWheel/Checkpointing

Yandex Query