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
courses:high_performance_computing:lectures [2019/09/25 19:20] – kelcourses:high_performance_computing:lectures [2026/01/22 00:12] (current) – kel
Line 1: Line 1:
 ====== Программа ====== ====== Программа ======
-===== 1. Введение =====+===== 0. Введение =====
   - Тенденции развития вычислительных систем, обуславливающие необходимость применения распределённых (параллельных) методов вычислений. Примеры вычислительно ёмких задач из разных областей науки.   - Тенденции развития вычислительных систем, обуславливающие необходимость применения распределённых (параллельных) методов вычислений. Примеры вычислительно ёмких задач из разных областей науки.
   - Классификация параллельных систем (SIMD, MISD..., SMP, MPP)   - Классификация параллельных систем (SIMD, MISD..., SMP, MPP)
-  - Современные высокопроизводительные системы: начиная от расширений SSE, через многоядерность к узлам кластеров+  - Расширения процессоров SSE/AVX...
   - Понятия ускорения, эффективности (закон Амдала)   - Понятия ускорения, эффективности (закон Амдала)
-  - Многопоточность или IPC 
   - План курса   - План курса
 +  - Старт потока (Java): реализация Runnable vs наследование от Thread
 +  - Напоминание о процессах и потоках: дерево процессов, демоны
  
-===== 2. Создание/завершение потоков ===== +===== 1. Многопоточность или IPC ===== 
-  - Механизм запуска потока+  - Виды IPC 
 +  - Преимущества многопоточности: 
 +    * Простота 
 +    * Скорость (TLB) 
 +  - Преимущества IPC: 
 +    * Безопасность 
 +    * Надёжность 
 +  - Сложности реализации shmem  
 + 
 +===== 2. Завершение потоков =====
   - Корректное завершение потоков:   - Корректное завершение потоков:
     * cancellation points     * cancellation points
     * interrupted exception     * interrupted exception
     * примеры кода в glibc     * примеры кода в glibc
-  - Сравнение различных потоков (POSIX, boost, java)+  - Сравнение различных потоков (POSIX, C++, Java) 
 +  - Разница pthread / kthread
   - Проброс исключений между потоками   - Проброс исключений между потоками
 +  - Напоминание о user space / kernel space и соответствующей стоимости syscall
  
 ===== 3. Примитивы синхронизации ===== ===== 3. Примитивы синхронизации =====
Line 30: Line 42:
     * использование wait/notify     * использование wait/notify
     * Spurious wakeups     * Spurious wakeups
 +  - Thread Local Storage (TLS) 
  
 ===== 4. Алгоритмы синхронизации ===== ===== 4. Алгоритмы синхронизации =====
Line 42: Line 55:
     * lock-free     * lock-free
     * wait-free      * wait-free 
-  - SWMR-регистры 
   - Lock-free snapshot   - Lock-free snapshot
   - Wait-free snapshot   - Wait-free snapshot
Line 56: Line 68:
     * Инверсия приоритетов      * Инверсия приоритетов 
  
-===== 7. Профилирование многопоточных приложений =====+===== 7. Модель памяти ===== 
 +  - Пример ошибки в ядре ОС 
 +  - Устройство кэшей процессора 
 +  - Пример на протоколе MESI 
 +  - Барьеры памяти (store/load) 
 +  - Модели памяти: Sequential consistency... 
 +  - Acquire/release семантика 
 + 
 +===== 8. Профилирование многопоточных приложений =====
   - Средства анализа производительности   - Средства анализа производительности
     * Утилита time     * Утилита time
-    * Intel Parallel Studio +    * Intel VTune 
-    * Valgrind (модули callgrind, cachegrind)     +    * Valgrind (модули callgrind)     
   - Пример поиска узких мест   - Пример поиска узких мест
 +  - Профилирование промашек по кэшу и метрика 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. Асинхронный ввод/вывод ===== 
 +  - Блокирующий/неблокирующий 
 +  - Синхронный (реактор)/асинхронный (проактор) 
 +  - Архитектура framework на примере boost::asio 
 +  - Особенности реализации callback 
 +  - Причины разницы производительности асинхронного i/o на примере простого сервера в классическом и coroutines-режиме 
 +  - Преимущества асинхронной работы и реализация со стороны операционной системы 
 +  - Мотивация к переходу на coroutines 
 +  - Преимущества по отношению к callback-программированию 
 +  - Примеры co_await и сравнение с синхронным кодом 
 + 
 +===== 15. Линеаризуемость ===== 
 +  - Понятие линеаризуемости 
 +  - Lock-free стек Trieber 
 +  - Пример на очередях 
 +  - Lock-free очередь Michael & Scott 
 +  - Точки линеаризации 
 +  - Relaxed SkipList 
 + 
 +===== 16. Оптимизации в компиляторах ===== 
 +  - Статические оптимизации 
 +  - Оптимизации циклов: 
 +    * Развёртывание 
 +    * Повторение 
 +    * Вынесение инварианта  
 +  - JIT-оптимизации 
 +    * Объединение захвата примитивов 
 +    * Оптимистичный захват 
 +    * Адаптивные блокировки  
 +    * Замена виртуального вызова 
  
-===== 10. Шаблоны || программирования =====+===== 17. Шаблоны || программирования ===== 
 +  - Общий взгляд на виды организации вычислений
   - Структурные шаблоны:   - Структурные шаблоны:
     * Декомпозиция по задачам     * Декомпозиция по задачам
Line 87: Line 150:
     * Recursive Data     * Recursive Data
     * Pipeline     * Pipeline
-  - Некоторые программные структуры: 
-    * Parallel loops 
-    * Boss/Worker 
   - Разное:   - Разное:
     * Double check     * Double check
     * Local Serializer     * Local Serializer
  
-===== 11. Кластерные вычисления =====+===== 18. OpenMP ===== 
 +  - Архитектура работы через директивы препроцессора 
 +  - Параллельные секции 
 +  - Области видимости переменных 
 +  - Ограничения 
 +  - Миграция вычислений 
 + 
 +===== 19. Intel TBB ===== 
 +  - Алгоритмы 
 +  - Аллокаторы: 
 +    * scalable 
 +    * cache_aligned (false sharing)  
 +  - Деревья задач 
 +  - Особенности планирования (work stealing...) 
 +  - flow graphs //(параллель с BPEL)// 
 + 
 +===== 20. Кластерные вычисления (MPI) =====
   - Виды кластерных систем:   - Виды кластерных систем:
     * Балансировки нагрузки     * Балансировки нагрузки
Line 113: Line 189:
     * Intel® Trace Analyzer и Intel® Trace Collector     * Intel® Trace Analyzer и Intel® Trace Collector
  
-===== 12. Консенсус. Сети Петри ===== +===== 21. Сопрограммы / Coroutines ===== 
-  - Консенсус: +  - Архитектурные особенности: 
-    * Консенсусное число RMW-регистров +    - stackless 
-    * Универсальность CAS-операций +    - stackfull 
-  - Верификация || программ (сети Петри)+    - fibers 
 +    - ... 
 +  - Способы интеграции в языки: 
 +    - C++ 
 +    - Go 
 +    - Kotlin 
 +    - ... 
 +  - Проблемы реализации примитивов и 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 230:
     * 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.1569428440.txt.gz · Last modified: 2019/09/25 19:20 by kel