Open Source & Linux Lab

It's better when it's simple

User Tools

Site Tools


courses:high_performance_computing:lectures

Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision
Previous revision
courses:high_performance_computing:lectures [2020/01/25 13:56] kelcourses:high_performance_computing:lectures [2024/01/25 00:04] (current) kel
Line 1: Line 1:
 ====== Программа ====== ====== Программа ======
-===== 1. Введение =====+===== 0. Введение =====
   - Тенденции развития вычислительных систем, обуславливающие необходимость применения распределённых (параллельных) методов вычислений. Примеры вычислительно ёмких задач из разных областей науки.   - Тенденции развития вычислительных систем, обуславливающие необходимость применения распределённых (параллельных) методов вычислений. Примеры вычислительно ёмких задач из разных областей науки.
   - Классификация параллельных систем (SIMD, MISD..., SMP, MPP)   - Классификация параллельных систем (SIMD, MISD..., SMP, MPP)
   - Современные высокопроизводительные системы: начиная от расширений SSE, через многоядерность к узлам кластеров   - Современные высокопроизводительные системы: начиная от расширений SSE, через многоядерность к узлам кластеров
   - Понятия ускорения, эффективности (закон Амдала)   - Понятия ускорения, эффективности (закон Амдала)
-  - Многопоточность или IPC 
   - План курса   - План курса
 +  - Старт потока (Java): реализация Runnable vs наследование от Thread
  
-===== 2. Создание/завершение потоков ===== +===== 1Многопоточность или IPC ===== 
-  - Механизм запуска потока+  - Виды IPC 
 +  - Преимущества многопоточности: 
 +    * Простота 
 +    * Скорость (TLB) 
 +  - Преимущества IPC: 
 +    * Безопасность 
 +    * Надёжность 
 +  - Сложности реализации shmem  
 + 
 +===== 2. Завершение потоков =====
   - Корректное завершение потоков:   - Корректное завершение потоков:
     * cancellation points     * cancellation points
Line 43: Line 52:
     * lock-free     * lock-free
     * wait-free      * wait-free 
-  - SWMR-регистры 
   - Lock-free snapshot   - Lock-free snapshot
   - Wait-free snapshot   - Wait-free snapshot
Line 57: Line 65:
     * Инверсия приоритетов      * Инверсия приоритетов 
  
-===== 7. Профилирование многопоточных приложений =====+===== 7. Модель памяти ===== 
 +  - Пример ошибки в ядре ОС 
 +  - Устройство кэшей процессора 
 +  - Пример на протоколе MESI 
 +  - Барьеры памяти (store/load) 
 +  - Модели памяти: Sequential consistency... 
 +  - Acquire/release семантика 
 + 
 +===== 8. Профилирование многопоточных приложений =====
   - Средства анализа производительности   - Средства анализа производительности
     * Утилита time     * Утилита time
Line 65: Line 81:
   - Профилирование промашек по кэшу и метрика CPI   - Профилирование промашек по кэшу и метрика CPI
  
-===== 8Java.util.concurrent и Fork-Join Framework ===== +===== 9Flat-Combining ===== 
-  - Пулы потоков, корректное завершение пула +  - Схема Flat-Combining 
-  - Контроль задач через Future +  - Возможные оптимизации за счёт интерференции операций 
-  - CompletionStage и CompletableFuture +  - Сравнение производительности с lock-free очередью Michael & Scott
-  - Потокобезопасные контейнеры+
  
-===== 9OpenMP и Intel TBB ===== +===== 10RCU ===== 
-  - Обзор 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 
 +  - Точки линеаризации 
 +  - Relaxed SkipList 
 + 
 +===== 16. Оптимизации в компиляторах ===== 
 +  - Статические оптимизации 
 +  - Оптимизации циклов
 +    * Развёртывание 
 +    * Повторение 
 +    * Вынесение инварианта  
 +  - JIT-оптимизации 
 +    * Объединение захвата примитивов 
 +    * Оптимистичный захват 
 +    * Адаптивные блокировки  
 +    * Замена виртуального вызова 
  
-===== 10. Шаблоны || программирования =====+===== 17. Шаблоны || программирования =====
   - Структурные шаблоны:   - Структурные шаблоны:
     * Декомпозиция по задачам     * Декомпозиция по задачам
Line 96: Line 148:
     * Local Serializer     * Local Serializer
  
-===== 11. Кластерные вычисления =====+===== 18. OpenMP ===== 
 +  - Архитектура работы через директивы препроцессора 
 +  - Параллельные секции 
 +  - Области видимости переменных 
 +  - Ограничения 
 +  - Миграция вычислений 
 + 
 +===== 19. Intel TBB ===== 
 +  - Алгоритмы 
 +  - Аллокаторы 
 +  - Деревья задач 
 +  - Особенности планирования (work stealing...) 
 +  - flow graphs //(параллель с BPEL)// 
 + 
 +===== 20. Кластерные вычисления (MPI) =====
   - Виды кластерных систем:   - Виды кластерных систем:
     * Балансировки нагрузки     * Балансировки нагрузки
Line 115: Line 181:
     * Intel® Trace Analyzer и Intel® Trace Collector     * Intel® Trace Analyzer и Intel® Trace Collector
  
-===== 12. Консенсус. Сети Петри ===== +===== 21. Сопрограммы / Coroutines ===== 
-  - Консенсус+  - Преимущества по отношению к callback-программированию 
-    * Консенсусное число RMWегистров +  - Примеры co_await и сравнение с синхронным кодом 
-    * Универсальность CASпераций +  Проблемы реализации примитивов и TLS 
-  - Верификация || программ (сети Петри)+  - Архитектурная аналогия с асинхронными framework
  
-===== 13Оптимизации в компиляторах ===== +===== 22Акторная модель ===== 
-  - Статические оптимизации +  - Суть модели: 
-  - Оптимизации циклов+    * Передача сообщений 
-    * Развёртывание +    * Легковесные процессы 
-    * Повторение +    * BEAM  
-    * Вынесение инварианта  +  - Применение в современных языках: 
-  - JIT-оптимизации +    * Erlang 
-    * Объединение захвата примитивов +    * Elixir 
-    * Оптимистичный захват +
-    * Адаптивные блокировки  +
-    * Замена виртуального вызова +
  
-===== 14Транзакционная память =====   +===== 23Java.util.concurrent и Fork-Join Framework ===== 
-  - Идея transactional memory +  - Пулы потоковкорректное завершение пула 
-    * Software transactional memory +  - Контроль задач через Future 
-    * Hardware transactional memory +  - CompletionStage и CompletableFuture 
-  - Преимущества и круг задач +  - Потокобезопасные контейнеры
-  - Реализация HTM на линейках кэша +
-  - Lock teleportation+
  
-===== 15. Асинхронный ввод/вывод ===== +===== 24. Средства поиска ошибок =====
-  - Блокирующий/неблокирующий +
-  - Синхронный (реактор)/асинхронный (проактор) +
-  - Преимущества асинхронной работы и реализация со стороны операционной системы +
-  - Библиотеки асинхронного ввода/вывода +
- +
-===== 16. Wait-free MRMW снимок регистров ===== +
-  - Напоминание о MRSW алгоритме +
-  - Переход к //bounded// версии на битовых //handchake// +
-  - Расширание до MRMW +
- +
-===== 17. Средства поиска ошибок =====+
   - Google Thread Sanitizer   - Google Thread Sanitizer
   - Intel Parallel Studio   - Intel Parallel Studio
   - Valgrind (модуль helgrind)   - Valgrind (модуль helgrind)
   - Пример использования   - Пример использования
- +  
-===== 18. Модель памяти ===== +===== 25. Lock-free изнутри =====
-  - Устройство кэшей процессора +
-  - Пример на протоколе MESI +
-  - Барьеры памяти (store/load) +
-  - Модели памяти: Sequential consistency... +
-  - Acquire/release семантика +
-   +
-===== 19. Lock-free изнутри =====+
   - Feldman Multi Array   - Feldman Multi Array
   - Схемы управления памятью:   - Схемы управления памятью:
Line 171: Line 214:
     * Hazard pointer     * Hazard pointer
  
-===== 20Линеаризуемость ===== +===== 26Системы потоковой обработки данных ===== 
-  - Понятие линеаризуемости +  - Analytics vs Streaming 
-  - Lock-free стек Trieber +  - Гарантии обработкии данных: 
-  - Пример на очередях +      * Exactly once 
-  - Lock-free очередь Michael & Scott +      * At least once 
-  - Точки линеаризации +      * At most once 
- +  - Windows 
-===== 21. Flat-Combining ===== +      * Session 
-  - Схема Flat-Combining +      * Sliding 
-  - Возможные оптимизации за счёт интерференции операций +      * Tumbling 
-  - Сравнение производительности с lock-free очередью Michael & Scott +      * Hopping 
- +  - Linear scalability 
-===== 22. Оптимизации в реализации контейнеров ===== +  - Fault tolerance 
-  - Relaxed SkipList +  - Back pressure 
- +  - Isolation 
-===== 23. Модель акторов ===== +  - Qutoing 
-  - Суть модели +  - MillWheel/Checkpointing 
-  - Применение в современных языках +  - Yandex Query
-  - Шаблоны применения +
- +
-===== 24. RCU ===== +
-  - Суть RCU и синхронизация на эпохах +
-  - Kernel-space RCU +
-  - User-space RCU+
  
courses/high_performance_computing/lectures.1579949777.txt.gz · Last modified: 2020/01/25 13:56 by kel