courses:high_performance_computing:lectures
Table of Contents
Программа
0. Введение
- Тенденции развития вычислительных систем, обуславливающие необходимость применения распределённых (параллельных) методов вычислений. Примеры вычислительно ёмких задач из разных областей науки.
- Классификация параллельных систем (SIMD, MISD…, SMP, MPP)
- Расширения процессоров SSE/AVX…
- Понятия ускорения, эффективности (закон Амдала)
- План курса
- Старт потока (Java): реализация Runnable vs наследование от Thread
- Напоминание о процессах и потоках: дерево процессов, демоны
1. Многопоточность или IPC
- Виды IPC
- Преимущества многопоточности:
- Простота
- Скорость (TLB)
- Преимущества IPC:
- Безопасность
- Надёжность
- Сложности реализации shmem
2. Завершение потоков
- Корректное завершение потоков:
- cancellation points
- interrupted exception
- примеры кода в glibc
- Сравнение различных потоков (POSIX, C++, Java)
- Разница pthread / kthread
- Проброс исключений между потоками
- Напоминание о 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
courses/high_performance_computing/lectures.txt · Last modified: 2024/09/15 19:23 by kel