Differences

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

--- high_performance_computing:lectures [2015/11/30 21:14] – kel
+++ courses:high_performance_computing:lectures [2023/11/06 14:45] – kel
@@ Line 1: / Line 1: @@
 ====== Программа ======
-===== 1. Введение =====
+===== 0. Введение =====
   - Тенденции развития вычислительных систем, обуславливающие необходимость применения распределённых (параллельных) методов вычислений. Примеры вычислительно ёмких задач из разных областей науки.
   - Классификация параллельных систем (SIMD, MISD..., SMP, MPP)
@@ Line 6: / Line 6: @@
   - Понятия ускорения, эффективности (закон Амдала)
   - План курса
+  - Старт потока (Java): реализация Runnable vs наследование от Thread
-===== 2. Создание/завершение потоков =====
+===== 1. Многопоточность или IPC =====
-  - Механизм запуска потока
+  - Виды IPC
+  - Преимущества многопоточности:
+    * Простота
+    * Скорость (TLB)
+  - Преимущества IPC:
+    * Безопасность
+    * Надёжность
+  - Сложности реализации shmem
+===== 2. Завершение потоков =====
   - Корректное завершение потоков:
     * cancellation points
@@ Line 29: / Line 39: @@
     * использование wait/notify
     * Spurious wakeups
+  - Thread Local Storage (TLS)
 ===== 4. Алгоритмы синхронизации =====
@@ Line 41: / Line 52: @@
     * lock-free
     * wait-free
-  - SWMR-регистры
   - Lock-free snapshot
   - Wait-free snapshot
@@ Line 49: / Line 59: @@
     * Гонки данных (Data Race)
     * Взаимная блокировка (Deadlock)
-    * Потерянный сигнал
   - Специфические ошибки
     * Реакция потока на сигнал
@@ Line 56: / Line 65: @@
     * Инверсия приоритетов
-===== 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:
+===== 11. Транзакционная память =====
-    * алгоритмы
+  - Идея transactional memory
-    * аллокаторы
+    * Software transactional memory
-    * деревья задач
+    * Hardware transactional memory
-    * особенности планирования (work stealing...)
+  - Преимущества и круг задач
-    * flow graphs //(параллель с BPEL)//
+  - Реализация HTM на линейках кэша
+  - Lock teleportation
+===== 12. Сети Петри =====
+  - Суть модели сетей Петри
+  - Пример с обедающими философами
+  - Верификация || программ
+===== 13. Консенсус =====
+  - Консенсус:
+    * Консенсусное число RMW-регистров
+    * Универсальность CAS-операций
+===== 14. Асинхронный ввод/вывод =====
+  - Блокирующий/неблокирующий
+  - Синхронный (реактор)/асинхронный (проактор)
+  - Преимущества асинхронной работы и реализация со стороны операционной системы
+  - Библиотеки асинхронного ввода/вывода
+===== 15. Линеаризуемость =====
+  - Понятие линеаризуемости
+  - Lock-free стек Trieber
+  - Пример на очередях
+  - Lock-free очередь Michael & Scott
+  - Точки линеаризации
+===== 16. Оптимизации в компиляторах =====
+  - Статические оптимизации
+  - Оптимизации циклов:
+    * Развёртывание
+    * Повторение
+    * Вынесение инварианта
+  - JIT-оптимизации
+    * Объединение захвата примитивов
+    * Оптимистичный захват
+    * Адаптивные блокировки
+    * Замена виртуального вызова
-===== 10. Шаблоны || программирования =====
+===== 17. Шаблоны || программирования =====
   - Структурные шаблоны:
     * Декомпозиция по задачам
@@ Line 93: / Line 147: @@
     * Local Serializer
-===== 11. Кластерные вычисления =====
+===== 18. OpenMP =====
+  - Архитектура работы через директивы препроцессора
+  - Параллельные секции
+  - Области видимости переменных
+  - Ограничения
+  - Миграция вычислений
+===== 19. Intel TBB =====
+  - Алгоритмы
+  - Аллокаторы
+  - Деревья задач
+  - Особенности планирования (work stealing...)
+  - flow graphs //(параллель с BPEL)//
+===== 20. Кластерные вычисления (MPI) =====
   - Виды кластерных систем:
     * Балансировки нагрузки
@@ Line 112: / Line 180: @@
     * 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