Differences

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

--- high_performance_computing:lectures [2015/11/30 18:54] – created kel
+++ courses:high_performance_computing:lectures [2024/01/25 00:04] (current) – kel
@@ Line 1: / Line 1: @@
 ====== Программа ======
+===== 0. Введение =====
+  - Тенденции развития вычислительных систем, обуславливающие необходимость применения распределённых (параллельных) методов вычислений. Примеры вычислительно ёмких задач из разных областей науки.
+  - Классификация параллельных систем (SIMD, MISD..., SMP, MPP)
+  - Современные высокопроизводительные системы: начиная от расширений SSE, через многоядерность к узлам кластеров
+  - Понятия ускорения, эффективности (закон Амдала)
+  - План курса
+  - Старт потока (Java): реализация Runnable vs наследование от Thread
+===== 1. Многопоточность или IPC =====
+  - Виды IPC
+  - Преимущества многопоточности:
+    * Простота
+    * Скорость (TLB)
+  - Преимущества IPC:
+    * Безопасность
+    * Надёжность
+  - Сложности реализации shmem
+===== 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
+  - 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