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/06/08 17:43] – 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 +  - Возможные оптимизации за счёт интерференции операций 
-  - Потокобезопасные контейнеры+  - Сравнение производительности с 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 148:
     * Local Serializer     * Local Serializer
  
-===== 11. Кластерные вычисления =====+===== 18. OpenMP ===== 
 +  - Архитектура работы через директивы препроцессора 
 +  - Параллельные секции 
 +  - Области видимости переменных 
 +  - Ограничения 
 +  - Миграция вычислений 
 + 
 +===== 19. Intel TBB ===== 
 +  - Алгоритмы 
 +  - Аллокаторы 
 +  - Деревья задач 
 +  - Особенности планирования (work stealing...) 
 +  - flow graphs //(параллель с BPEL)// 
 + 
 +===== 20. Кластерные вычисления (MPI) =====
   - Виды кластерных систем:   - Виды кластерных систем:
     * Балансировки нагрузки     * Балансировки нагрузки
Line 112: 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 изнутри ===== 
-  - Устройство кэшей процессора +  - Feldman Multi Array
-  - Пример на протоколе MESI +
-  - Барьеры памяти (store/load) +
-  - Модели памяти: Sequential consistency... +
-  - Acquire/release семантика +
-   +
-===== 19. Lock-free изнутри ===== +
-  - Kernel-space RCU +
-  - User-space RCU+
   - Схемы управления памятью:   - Схемы управления памятью:
     * Tagged pointers     * Tagged pointers
     * Hazard pointer     * Hazard pointer
  
-===== 20. Линеаризуемость ===== +===== 26. Оптимизации в реализации контейнеров ===== 
-  - Понятие линеаризуемости +  - Relaxed SkipList
-  - Lock-free стек Trieber +
-  - Пример на очередях +
-  - Lock-free очередь Michael & Scott +
-  - Точки линеаризации+
  
-===== 21. Flat-Combining ===== +===== 27. Системы потоковой обработки данных ===== 
-  - Схема Flat-Combining +  - Analytics vs Streaming 
-  - Возможные оптимизации за счёт интерференции операций +  - Гарантии обработкии данных: 
-  - Сравнение производительности с lock-free очередью Michael & Scott +      * Exactly once 
- +      * At least once 
-===== 22. Оптимизации в реализации контейнеров ===== +      * At most once 
-  - Relaxed SkipList+  - Windows 
 +      * Session 
 +      * Sliding 
 +      * Tumbling 
 +      * Hopping 
 +  - Linear scalability 
 +  - Fault tolerance 
 +  - Back pressure 
 +  - Isolation 
 +  - Qutoing 
 +  - MillWheel/Checkpointing 
 +  - Yandex Query
  
-===== 23. Модель акторов ===== 
-  - Суть модели 
-  - Применение в современных языках 
-  - Шаблоны применения 
courses/high_performance_computing/lectures.txt · Last modified: 2024/01/25 00:04 by kel