Differences

This shows you the differences between two versions of the page.

--- high_performance_computing:lectures [2015/11/30 20:53] – kel
+++ courses:high_performance_computing:lectures [2023/06/26 13:07] – odoronin
@@ Line 5: / Line 5: @@
   - Современные высокопроизводительные системы: начиная от расширений SSE, через многоядерность к узлам кластеров
   - Понятия ускорения, эффективности (закон Амдала)
+  - Многопоточность или IPC
   - План курса
@@ Line 29: / Line 30: @@
     * использование wait/notify
     * Spurious wakeups
+  - Thread Local Storage (TLS)
 ===== 4. Алгоритмы синхронизации =====
@@ Line 41: / Line 43: @@
     * lock-free
     * wait-free
-  - SWMR-регистры
   - Lock-free snapshot
   - Wait-free snapshot
@@ Line 49: / Line 50: @@
     * Гонки данных (Data Race)
     * Взаимная блокировка (Deadlock)
-    * Потерянный сигнал
   - Специфические ошибки
     * Реакция потока на сигнал
@@ Line 56: / Line 56: @@
     * Инверсия приоритетов
-===== 7. Профилирование многопоточных приложений =====
+===== 7. Модель памяти =====
+  - Пример ошибки в ядре ОС
+  - Устройство кэшей процессора
+  - Пример на протоколе MESI
+  - Барьеры памяти (store/load)
+  - Модели памяти: Sequential consistency...
+  - Acquire/release семантика
+===== 8. Профилирование многопоточных приложений =====
   - Средства анализа производительности
+    * Утилита time
     * Intel Parallel Studio
     * Valgrind (модули callgrind, cachegrind)
-    * Google Profiler
   - Пример поиска узких мест
+  - Профилирование промашек по кэшу и метрика CPI
-===== 8. Java.util.concurrent и Fork-Join Framework =====
+===== 9. Flat-Combining =====
-  - Пулы потоков, корректное завершение пула
+  - Схема Flat-Combining
-  - Контроль задач через Future
+  - Возможные оптимизации за счёт интерференции операций
-  - Потокобезопасные контейнеры
+  - Сравнение производительности с lock-free очередью Michael & Scott
-===== 9. OpenMP и Intel TBB =====
+===== 10. RCU =====
-  - Обзор OpenMP:
+  - Суть RCU и синхронизация на эпохах
-    * параллельные секции
+  - Kernel-space RCU
-    * области видимости переменных
+  - User-space RCU
-    * ограничения
-  - Обзор Intel TBB:
-    * алгоритмы
-    * аллокаторы
-    * деревья задач
-    * особенности планирования (work stealing...)
-    * flow graphs //(параллель с BPEL)//
-===== 10. Шаблоны || программирования =====
+===== 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
+  - Точки линеаризации
+===== 16. Оптимизации в компиляторах =====
+  - Статические оптимизации
+  - Оптимизации циклов:
+    * Развёртывание
+    * Повторение
+    * Вынесение инварианта
+  - JIT-оптимизации
+    * Объединение захвата примитивов
+    * Оптимистичный захват
+    * Адаптивные блокировки
+    * Замена виртуального вызова
+===== 17. Шаблоны || программирования =====
   - Структурные шаблоны:
     * Декомпозиция по задачам
@@ Line 93: / Line 138: @@
     * Local Serializer
-===== 11. Кластерные вычисления =====
+===== 18. OpenMP =====
+  - Архитектура работы через директивы препроцессора
+  - Параллельные секции
+  - Области видимости переменных
+  - Ограничения
+  - Миграция вычислений
+===== 19. Intel TBB =====
+  - Алгоритмы
+  - Аллокаторы
+  - Деревья задач
+  - Особенности планирования (work stealing...)
+  - flow graphs //(параллель с BPEL)//
+===== 20. Кластерные вычисления (MPI) =====
   - Виды кластерных систем:
     * Балансировки нагрузки
@@ Line 112: / Line 171: @@
     * Intel® Trace Analyzer и Intel® Trace Collector
-===== 12. Консенсус. Сети Петри =====
+===== 21. Сопрограммы / Coroutines =====
-  - Линеаризуемость
+  - Преимущества по отношению к callback-программированию
-  - Консенсус:
+  - Примеры co_await и сравнение с синхронным кодом
-    * Консенсусное число RMW-регистров
+  - Проблемы реализации примитивов и TLS
-    * Универсальность CAS-операций
+  - Архитектурная аналогия с асинхронными framework
-  - Верификация || программ (сети Петри)
-===== 13. Оптимизации в компиляторах =====
+===== 22. Акторная модель =====
-  - Статические оптимизации
+  - Суть модели:
-  - Оптимизации циклов:
+    * Передача сообщений
-    * Развёртывание
+    * Легковесные процессы
-    * Повторение
+    * BEAM
-    * Вынесение инварианта
+  - Применение в современных языках:
-  - JIT-оптимизации
+    * Erlang
-    * Объединение захвата примитивов
+    * Elixir
-    * Оптимистичный захват
-    * Адаптивные блокировки
-    * Замена виртуального вызова
-===== 14. Транзакционная память =====
+===== 23. Java.util.concurrent и Fork-Join Framework =====
-  - Идея transactional memory
+  - Пулы потоков, корректное завершение пула
-  - Software transactional memory
+  - Контроль задач через Future
-  - Hardware transactional memory:
+  - CompletionStage и CompletableFuture
-    * Пример на протоколе MESI
+  - Потокобезопасные контейнеры
-    * Немного о барьерах (store/load)
-  - Преимущества и круг задач
-===== 15. Асинхронный ввод/вывод =====
+===== 24. Средства поиска ошибок =====
-  - Блокирующий/неблокирующий
-  - Синхронный (реактор)/асинхронный (проактор)
-  - Преимущества асинхронной работы и реализация со стороны операционной системы
-  - Библиотеки асинхронного ввода/вывода
-===== 16. Wait-free MRMW снэпшот =====
-  - Напоминание о MRSW алгоритме
-  - Переход к //bounded// версии на битовых //handchake//
-  - Расширание до MRMW
-===== 17. Средства поиска ошибок =====
   - Google Thread Sanitizer
   - Intel Parallel Studio
   - Valgrind (модуль helgrind)
-  - Пример использвоания
+  - Пример использования
+===== 25. Lock-free изнутри =====
+  - Feldman Multi Array
+  - Схемы управления памятью:
+    * Tagged pointers
+    * Hazard pointer
+===== 26. Оптимизации в реализации контейнеров =====
+  - Relaxed SkipList
+===== 27. Системы потоковой обработки данных =====
+  - 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