courses:high_performance_computing:lectures
This is an old revision of the document!
Table of Contents
Программа
1. Введение
- Тенденции развития вычислительных систем, обуславливающие необходимость применения распределённых (параллельных) методов вычислений. Примеры вычислительно ёмких задач из разных областей науки.
- Классификация параллельных систем (SIMD, MISD…, SMP, MPP)
- Современные высокопроизводительные системы: начиная от расширений SSE, через многоядерность к узлам кластеров
- Понятия ускорения, эффективности (закон Амдала)
- Многопоточность или IPC
- План курса
2. Создание/завершение потоков
- Механизм запуска потока
- Корректное завершение потоков:
- cancellation points
- interrupted exception
- примеры кода в glibc
- Сравнение различных потоков (POSIX, boost, java)
- Проброс исключений между потоками
3. Примитивы синхронизации
- Необходимость синхронизации: простые гонки данных
- Реализация примитивов синхронизации: алгоритм булочника
- Виды мьютексов:
- рекурсивные/нерекурсивные
- read/write
- spin
- futex
- Корректные захват/освобождение примитивов
- CAS-операции и атомики
- Условные переменные:
- использование wait/notify
- Spurious wakeups
- Thread Local Storage (TLS)
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)
- Пример поиска узких мест
- Профилирование промашек по кэшу и метрика CPI
8. Java.util.concurrent и Fork-Join Framework
- Пулы потоков, корректное завершение пула
- Контроль задач через Future
- CompletionStage и CompletableFuture
- Потокобезопасные контейнеры
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
- Преимущества и круг задач
- Реализация HTM на линейках кэша
- Lock teleportation
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 изнутри
- Feldman Multi Array
- Схемы управления памятью:
- Tagged pointers
- Hazard pointer
20. Линеаризуемость
- Понятие линеаризуемости
- Lock-free стек Trieber
- Пример на очередях
- Lock-free очередь Michael & Scott
- Точки линеаризации
21. Flat-Combining
- Схема Flat-Combining
- Возможные оптимизации за счёт интерференции операций
- Сравнение производительности с lock-free очередью Michael & Scott
22. Оптимизации в реализации контейнеров
- Relaxed SkipList
23. Модель акторов
- Суть модели:
- Передача сообщений
- Легковесные процессы
- BEAM
- Применение в современных языках:
- Erlang
- Elixir
24. RCU
- Суть RCU и синхронизация на эпохах
- Kernel-space RCU
- User-space RCU
25. Сопограммы / Coroutines
- Преимущества по отношению к callback-программированию
- Примеры co_await и сравнение с синхронным кодом
- Проблемы реализации примитивов и TLS
- Архитектурная аналогия с асинхронными framework
courses/high_performance_computing/lectures.1638781237.txt.gz · Last modified: 2021/12/06 12:00 by kel