Open Source & Linux Lab

It's better when it's simple

User Tools

Site Tools

You are here: О нас » Курсы » || программирование » Программа
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
Next revisionBoth sides next revision
courses:high_performance_computing:lectures [2019/09/25 19:20] – kelcourses:high_performance_computing:lectures [2023/11/06 14:33] – kel
Line 1: Line 1:
 ====== Программа ====== ====== Программа ======
-===== 1. Введение =====+===== 0. Введение =====
   - Тенденции развития вычислительных систем, обуславливающие необходимость применения распределённых (параллельных) методов вычислений. Примеры вычислительно ёмких задач из разных областей науки.   - Тенденции развития вычислительных систем, обуславливающие необходимость применения распределённых (параллельных) методов вычислений. Примеры вычислительно ёмких задач из разных областей науки.
   - Классификация параллельных систем (SIMD, MISD..., SMP, MPP)   - Классификация параллельных систем (SIMD, MISD..., SMP, MPP)
   - Современные высокопроизводительные системы: начиная от расширений SSE, через многоядерность к узлам кластеров   - Современные высокопроизводительные системы: начиная от расширений SSE, через многоядерность к узлам кластеров
   - Понятия ускорения, эффективности (закон Амдала)   - Понятия ускорения, эффективности (закон Амдала)
-  - Многопоточность или IPC 
   - План курса   - План курса
 +  - Старт потока (Java): реализация Runnable vs наследование от Thread
 +
 +===== 1. Многопоточность или IPC =====
 +  - Виды IPC
 +  - Преимущества многопоточности:
 +    * Простота
 +    * Скорость (TLB)
 +  - Преимущества IPC:
 +    * Безопасность
 +    * Надёжность
 +  - Сложности реализации shmem 
  
 ===== 2. Создание/завершение потоков ===== ===== 2. Создание/завершение потоков =====
Line 30: Line 40:
     * использование wait/notify     * использование wait/notify
     * Spurious wakeups     * Spurious wakeups
 +  - Thread Local Storage (TLS) 
  
 ===== 4. Алгоритмы синхронизации ===== ===== 4. Алгоритмы синхронизации =====
Line 42: Line 53:
     * lock-free     * lock-free
     * wait-free      * wait-free 
-  - SWMR-регистры 
   - Lock-free snapshot   - Lock-free snapshot
   - Wait-free snapshot   - Wait-free snapshot
Line 56: Line 66:
     * Инверсия приоритетов      * Инверсия приоритетов 
  
-===== 7. Профилирование многопоточных приложений =====+===== 7. Модель памяти ===== 
 +  - Пример ошибки в ядре ОС 
 +  - Устройство кэшей процессора 
 +  - Пример на протоколе MESI 
 +  - Барьеры памяти (store/load) 
 +  - Модели памяти: Sequential consistency... 
 +  - Acquire/release семантика 
 + 
 +===== 8. Профилирование многопоточных приложений =====
   - Средства анализа производительности   - Средства анализа производительности
     * Утилита time     * Утилита time
Line 62: Line 80:
     * Valgrind (модули callgrind, cachegrind)          * Valgrind (модули callgrind, cachegrind)     
   - Пример поиска узких мест   - Пример поиска узких мест
 +  - Профилирование промашек по кэшу и метрика CPI
  
-===== 8. Java.util.concurrent и Fork-Join Framework ===== +===== 9. Flat-Combining ===== 
-  - Пулы потоков, корректное завершение пула +  - Схема Flat-Combining 
-  - Контроль задач через Future +  - Возможные оптимизации за счёт интерференции операций 
-  - CompletionStage и CompletableFuture +  - Сравнение производительности с 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 94: Line 148:
     * Local Serializer     * Local Serializer
  
-===== 11. Кластерные вычисления =====+===== 18. OpenMP ===== 
 +  - Архитектура работы через директивы препроцессора 
 +  - Параллельные секции 
 +  - Области видимости переменных 
 +  - Ограничения 
 +  - Миграция вычислений 
 + 
 +===== 19. Intel TBB ===== 
 +  - Алгоритмы 
 +  - Аллокаторы 
 +  - Деревья задач 
 +  - Особенности планирования (work stealing...) 
 +  - flow graphs //(параллель с BPEL)// 
 + 
 +===== 20. Кластерные вычисления (MPI) =====
   - Виды кластерных систем:   - Виды кластерных систем:
     * Балансировки нагрузки     * Балансировки нагрузки
Line 113: 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. Транзакционная память =====   +===== 23. Java.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 169: Line 214:
     * Hazard pointer     * Hazard pointer
  
-===== 20. Линеаризуемость ===== +===== 26. Оптимизации в реализации контейнеров =====
-  - Понятие линеаризуемости +
-  - Lock-free стек Trieber +
-  - Пример на очередях +
-  - Lock-free очередь Michael & Scott +
-  - Точки линеаризации +
- +
-===== 21. Flat-Combining ===== +
-  - Схема Flat-Combining +
-  - Возможные оптимизации за счёт интерференции операций +
-  - Сравнение производительности с lock-free очередью Michael & Scott +
- +
-===== 22. Оптимизации в реализации контейнеров =====+
   - Relaxed SkipList   - Relaxed SkipList
  
-===== 23. Модель акторов ===== +===== 27. Системы потоковой обработки данных ===== 
-  - Суть модели +  - Analytics vs Streaming 
-  - Применение в современных языках +  - Гарантии обработкии данных: 
-  - Шаблоны применения +      * Exactly once 
- +      * At least once 
-===== 24. RCU ===== +      * At most once 
-  - Суть RCU и синхронизация на эпохах +  - Windows 
-  - Kernel-space RCU +      * Session 
-  - User-space RCU+      * Sliding 
 +      * Tumbling 
 +      * Hopping 
 +  - Linear scalability 
 +  - Fault tolerance 
 +  - Back pressure 
 +  - Isolation 
 +  - Qutoing 
 +  - MillWheel/Checkpointing 
 +  - Yandex Query
  
courses/high_performance_computing/lectures.txt · Last modified: 2024/01/25 00:04 by kel