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
high_performance_computing:lectures [2015/11/30 21:14] 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)
Line 6: Line 6:
   - Понятия ускорения, эффективности (закон Амдала)   - Понятия ускорения, эффективности (закон Амдала)
   - План курса   - План курса
 +  - Старт потока (Java): реализация Runnable vs наследование от Thread
  
-===== 2. Создание/завершение потоков ===== +===== 1Многопоточность или IPC ===== 
-  - Механизм запуска потока+  - Виды IPC 
 +  - Преимущества многопоточности: 
 +    * Простота 
 +    * Скорость (TLB) 
 +  - Преимущества IPC: 
 +    * Безопасность 
 +    * Надёжность 
 +  - Сложности реализации shmem  
 + 
 +===== 2. Завершение потоков =====
   - Корректное завершение потоков:   - Корректное завершение потоков:
     * cancellation points     * cancellation points
Line 29: Line 39:
     * использование wait/notify     * использование wait/notify
     * Spurious wakeups     * Spurious wakeups
 +  - Thread Local Storage (TLS) 
  
 ===== 4. Алгоритмы синхронизации ===== ===== 4. Алгоритмы синхронизации =====
Line 41: Line 52:
     * lock-free     * lock-free
     * wait-free      * wait-free 
-  - SWMR-регистры 
   - Lock-free snapshot   - Lock-free snapshot
   - Wait-free snapshot   - Wait-free snapshot
Line 49: Line 59:
     * Гонки данных (Data Race)     * Гонки данных (Data Race)
     * Взаимная блокировка (Deadlock)     * Взаимная блокировка (Deadlock)
-    * Потерянный сигнал  
   - Специфические ошибки   - Специфические ошибки
     * Реакция потока на сигнал     * Реакция потока на сигнал
Line 56: Line 65:
     * Инверсия приоритетов      * Инверсия приоритетов 
  
-===== 7. Профилирование многопоточных приложений =====+===== 7. Модель памяти ===== 
 +  - Пример ошибки в ядре ОС 
 +  - Устройство кэшей процессора 
 +  - Пример на протоколе MESI 
 +  - Барьеры памяти (store/load) 
 +  - Модели памяти: Sequential consistency... 
 +  - Acquire/release семантика 
 + 
 +===== 8. Профилирование многопоточных приложений =====
   - Средства анализа производительности   - Средства анализа производительности
 +    * Утилита time
     * Intel Parallel Studio     * Intel Parallel Studio
-    * Valgrind (модули callgrind, cachegrind)  +    * Valgrind (модули callgrind, cachegrind)     
-    * Google Profiler+
   - Пример поиска узких мест   - Пример поиска узких мест
 +  - Профилирование промашек по кэшу и метрика CPI
  
-===== 8Java.util.concurrent и Fork-Join Framework ===== +===== 9Flat-Combining ===== 
-  - Пулы потоков, корректное завершение пула +  - Схема Flat-Combining 
-  - Контроль задач через Future +  - Возможные оптимизации за счёт интерференции операций 
-  - Потокобезопасные контейнеры+  - Сравнение производительности с 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 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-программированию 
-  - Консенсус: +  - Примеры co_await и сравнение с синхронным кодом 
-    * Консенсусное число RMWегистров +  Проблемы реализации примитивов и TLS 
-    * Универсальность CASпераций +  - Архитектурная аналогия с асинхронными 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 
-    * Пример на протоколе MESI +  - Потокобезопасные контейнеры
-    * Немного о барьерах (store/load) +
-  - Преимущества и круг задач+
  
-===== 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)
-  - Пример использвоания +  - Пример использования 
 +  
 +===== 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
  
courses/high_performance_computing/lectures.1448907241.txt.gz · Last modified: 2015/11/30 21:14 by kel