courses:high_performance_computing:lectures
Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revisionNext revisionBoth sides next revision | ||
courses:high_performance_computing:lectures [2019/09/25 19:20] – kel | courses:high_performance_computing:lectures [2022/01/03 21:00] – kel | ||
---|---|---|---|
Line 30: | Line 30: | ||
* использование wait/notify | * использование wait/notify | ||
* Spurious wakeups | * Spurious wakeups | ||
+ | - Thread Local Storage (TLS) | ||
===== 4. Алгоритмы синхронизации ===== | ===== 4. Алгоритмы синхронизации ===== | ||
Line 56: | Line 57: | ||
* Инверсия приоритетов | * Инверсия приоритетов | ||
- | ===== 7. Профилирование многопоточных приложений ===== | + | ===== 7. Модель памяти ===== |
+ | - Устройство кэшей процессора | ||
+ | - Пример на протоколе MESI | ||
+ | - Барьеры памяти (store/ | ||
+ | - Модели памяти: | ||
+ | - Acquire/ | ||
+ | |||
+ | ===== 8. Профилирование многопоточных приложений ===== | ||
- Средства анализа производительности | - Средства анализа производительности | ||
* Утилита time | * Утилита time | ||
Line 62: | Line 70: | ||
* Valgrind (модули callgrind, cachegrind) | * Valgrind (модули callgrind, cachegrind) | ||
- Пример поиска узких мест | - Пример поиска узких мест | ||
+ | - Профилирование промашек по кэшу и метрика CPI | ||
- | ===== 8. Java.util.concurrent и Fork-Join Framework | + | ===== 9. Flat-Combining |
- | - Пулы потоков, корректное завершение пула | + | - Схема Flat-Combining |
- | - Контроль задач через Future | + | - Возможные оптимизации за счёт интерференции операций |
- | - CompletionStage | + | - Сравнение производительности с lock-free очередью Michael & Scott |
- | - Потокобезопасные контейнеры | + | |
- | ===== 9. OpenMP и Intel TBB ===== | + | ===== 10. RCU ===== |
- | - Обзор | + | - Суть RCU и синхронизация на эпохах |
- | * параллельные секции | + | - Kernel-space RCU |
- | * области видимости переменных | + | - User-space RCU |
- | * ограничения | + | |
- | - Обзор | + | ===== 11. Транзакционная память ===== |
- | * алгоритмы | + | - Идея transactional memory |
- | * аллокаторы | + | * Software transactional memory |
- | * деревья задач | + | * Hardware transactional memory |
- | * особенности | + | - Преимущества и круг задач |
- | * flow graphs //(параллель с BPEL)// | + | - Реализация HTM на линейках кэша |
+ | - Lock teleportation | ||
+ | |||
+ | ===== 12. Сети Петри ===== | ||
+ | - Суть модели сетей Петри | ||
+ | - Пример с обедающими философами | ||
+ | - Верификация || программ | ||
+ | |||
+ | ===== 13. Консенсус ===== | ||
+ | - Консенсус: | ||
+ | * Консенсусное число RMW-регистров | ||
+ | * Универсальность CAS-операций | ||
+ | |||
+ | ===== 14. Асинхронный ввод/ | ||
+ | - Блокирующий/ | ||
+ | - Синхронный (реактор)/ | ||
+ | - Преимущества асинхронной работы | ||
+ | - Библиотеки асинхронного ввода/ | ||
+ | |||
+ | ===== 15. Линеаризуемость ===== | ||
+ | - Понятие линеаризуемости | ||
+ | - Lock-free стек Trieber | ||
+ | - Пример на очередях | ||
+ | - Lock-free очередь Michael & Scott | ||
+ | - Точки линеаризации | ||
+ | |||
+ | ===== 16. Оптимизации в компиляторах ===== | ||
+ | - Статические оптимизации | ||
+ | - Оптимизации циклов: | ||
+ | * Развёртывание | ||
+ | * Повторение | ||
+ | * Вынесение инварианта | ||
+ | - JIT-оптимизации | ||
+ | * Объединение захвата примитивов | ||
+ | * Оптимистичный захват | ||
+ | * Адаптивные блокировки | ||
+ | * Замена виртуального вызова | ||
- | ===== 10. Шаблоны || программирования ===== | + | ===== 17. Шаблоны || программирования ===== |
- Структурные шаблоны: | - Структурные шаблоны: | ||
* Декомпозиция по задачам | * Декомпозиция по задачам | ||
Line 94: | Line 138: | ||
* Local Serializer | * Local Serializer | ||
- | ===== 11. Кластерные вычисления ===== | + | ===== 18. OpenMP ===== |
+ | - Архитектура работы через директивы препроцессора | ||
+ | - Параллельные секции | ||
+ | - Области видимости переменных | ||
+ | - Ограничения | ||
+ | - Миграция вычислений | ||
+ | |||
+ | ===== 19. Intel TBB ===== | ||
+ | - Алгоритмы | ||
+ | - Аллокаторы | ||
+ | - Деревья задач | ||
+ | - Особенности планирования (work stealing...) | ||
+ | - flow graphs // | ||
+ | |||
+ | ===== 20. Кластерные вычисления | ||
- Виды кластерных систем: | - Виды кластерных систем: | ||
* Балансировки нагрузки | * Балансировки нагрузки | ||
Line 113: | Line 171: | ||
* Intel® Trace Analyzer и Intel® Trace Collector | * Intel® Trace Analyzer и Intel® Trace Collector | ||
- | ===== 12. Консенсус. Сети Петри ===== | + | ===== 21. Сопрограммы / Coroutines |
- | - Консенсус: | + | - Преимущества по отношению к callback-программированию |
- | * Консенсусное | + | - Примеры co_await и сравнение |
- | * Универсальность CAS-операций | + | |
- | - Верификация || программ (сети Петри) | + | - Архитектурная аналогия с асинхронными framework |
- | ===== 13. Оптимизации в компиляторах ===== | + | ===== 22. Акторная модель |
- | - Статические оптимизации | + | - Суть модели: |
- | - Оптимизации циклов: | + | * Передача сообщений |
- | * Развёртывание | + | * Легковесные процессы |
- | * Повторение | + | * BEAM |
- | * Вынесение инварианта | + | - Применение в современных языках: |
- | - JIT-оптимизации | + | * Erlang |
- | * Объединение | + | * Elixir |
- | * Оптимистичный захват | + | |
- | * Адаптивные блокировки | + | |
- | * Замена виртуального вызова | + | |
- | ===== 14. Транзакционная память | + | ===== 23. Java.util.concurrent |
- | - Идея transactional memory | + | - Пулы потоков, корректное завершение пула |
- | * Software transactional memory | + | - Контроль |
- | * Hardware transactional memory | + | - CompletionStage |
- | - Преимущества и круг задач | + | - Потокобезопасные контейнеры |
- | - Реализация HTM на линейках кэша | + | |
- | - Lock teleportation | + | |
- | ===== 15. Асинхронный ввод/ | + | ===== 24. Wait-free MRMW снимок регистров ===== |
- | - Блокирующий/ | + | |
- | - Синхронный (реактор)/ | + | |
- | - Преимущества асинхронной работы и реализация со стороны операционной системы | + | |
- | - Библиотеки асинхронного ввода/ | + | |
- | + | ||
- | ===== 16. Wait-free MRMW снимок регистров ===== | + | |
- Напоминание о MRSW алгоритме | - Напоминание о MRSW алгоритме | ||
- Переход к //bounded// версии на битовых // | - Переход к //bounded// версии на битовых // | ||
- Расширание до MRMW | - Расширание до MRMW | ||
- | ===== 17. Средства поиска ошибок ===== | + | ===== 25. Средства поиска ошибок ===== |
- Google Thread Sanitizer | - Google Thread Sanitizer | ||
- Intel Parallel Studio | - Intel Parallel Studio | ||
- Valgrind (модуль helgrind) | - Valgrind (модуль helgrind) | ||
- Пример использования | - Пример использования | ||
- | + | ||
- | ===== 18. Модель памяти ===== | + | ===== 26. Lock-free изнутри ===== |
- | - Устройство кэшей процессора | + | |
- | - Пример на протоколе MESI | + | |
- | - Барьеры памяти (store/ | + | |
- | - Модели памяти: | + | |
- | - Acquire/ | + | |
- | + | ||
- | ===== 19. Lock-free изнутри ===== | + | |
- Feldman Multi Array | - Feldman Multi Array | ||
- Схемы управления памятью: | - Схемы управления памятью: | ||
Line 169: | Line 209: | ||
* Hazard pointer | * Hazard pointer | ||
- | ===== 20. Линеаризуемость ===== | + | ===== 27. Оптимизации в реализации контейнеров ===== |
- | - Понятие линеаризуемости | + | |
- | - Lock-free стек Trieber | + | |
- | - Пример на очередях | + | |
- | - Lock-free очередь Michael & Scott | + | |
- | - Точки линеаризации | + | |
- | + | ||
- | ===== 21. Flat-Combining ===== | + | |
- | - Схема Flat-Combining | + | |
- | - Возможные оптимизации за счёт интерференции операций | + | |
- | - Сравнение производительности с lock-free очередью Michael & Scott | + | |
- | + | ||
- | ===== 22. Оптимизации в реализации контейнеров ===== | + | |
- Relaxed SkipList | - Relaxed SkipList | ||
- | |||
- | ===== 23. Модель акторов ===== | ||
- | - Суть модели | ||
- | - Применение в современных языках | ||
- | - Шаблоны применения | ||
- | |||
- | ===== 24. RCU ===== | ||
- | - Суть RCU и синхронизация на эпохах | ||
- | - Kernel-space RCU | ||
- | - User-space RCU | ||
courses/high_performance_computing/lectures.txt · Last modified: 2024/09/15 19:23 by kel