courses:high_performance_computing:lectures
This is an old revision of the document!
Table of Contents
Программа
1. Введение
- Тенденции развития вычислительных систем, обуславливающие необходимость применения распределённых (параллельных) методов вычислений. Примеры вычислительно ёмких задач из разных областей науки.
- Классификация параллельных систем (SIMD, MISD…, SMP, MPP)
- Современные высокопроизводительные системы: начиная от расширений SSE, через многоядерность к узлам кластеров
- Понятия ускорения, эффективности (закон Амдала)
- Многопоточность или IPC
- План курса
2. Создание/завершение потоков
- Механизм запуска потока
- Корректное завершение потоков:
- cancellation points
- interrupted exception
- примеры кода в glibc
- Сравнение различных потоков (POSIX, boost, java)
- Проброс исключений между потоками
3. Примитивы синхронизации
- Необходимость синхронизации: простые гонки данных
- Реализация примитивов синхронизации: алгоритм булочника
- Виды мьютексов:
- рекурсивные/нерекурсивные
- read/write
- spin
- futex
- Корректные захват/освобождение примитивов
- CAS-операции и атомики
- Условные переменные:
- использование wait/notify
- Spurious wakeups
4. Алгоритмы синхронизации
- Грубая
- Тонкая
- Оптимистичная
- Ленивая
- Неблокирующая (параллель с ORM)
5. Атомарные снимки регистров
- Классификация алгоритмов:
- lock-free
- wait-free
- SWMR-регистры
- Lock-free snapshot
- Wait-free snapshot
6. Ошибки || программирования
- Основные ошибки многопоточного программирования
- Гонки данных (Data Race)
- Взаимная блокировка (Deadlock)
- Специфические ошибки
- Реакция потока на сигнал
- Блокировки при fork многопоточных программ
- Проблема ABA
- Инверсия приоритетов
7. Профилирование многопоточных приложений
- Средства анализа производительности
- Утилита time
- Intel Parallel Studio
- Valgrind (модули callgrind, cachegrind)
- Пример поиска узких мест
8. Java.util.concurrent и Fork-Join Framework
- Пулы потоков, корректное завершение пула
- Контроль задач через Future
- Потокобезопасные контейнеры
9. OpenMP и Intel TBB
- Обзор OpenMP:
- параллельные секции
- области видимости переменных
- ограничения
- Обзор Intel TBB:
- алгоритмы
- аллокаторы
- деревья задач
- особенности планирования (work stealing…)
- flow graphs (параллель с BPEL)
10. Шаблоны || программирования
- Структурные шаблоны:
- Декомпозиция по задачам
- Геометрическая декомпозиция
- Recursive Data
- Pipeline
- Некоторые программные структуры:
- Parallel loops
- Boss/Worker
- Разное:
- Double check
- Local Serializer
11. Кластерные вычисления
- Виды кластерных систем:
- Балансировки нагрузки
- Высокой надёжности
- Вычислительные
- История и назначение стандарта MPI
- Обмен сообщениями:
- С блокировкой
- Без блокировки
- Отложенные запросы на взаимодействие
- Взаимодействие процессов:
- Группы и коммуникаторы
- Операции коллективного взаимодействия процессов
- Редукция
- Виртуальные топологии
- Средства анализа производительности:
- Jumpshot
- Intel® Trace Analyzer и Intel® Trace Collector
12. Консенсус. Сети Петри
- Линеаризуемость
- Консенсус:
- Консенсусное число RMW-регистров
- Универсальность CAS-операций
- Верификация || программ (сети Петри)
13. Оптимизации в компиляторах
- Статические оптимизации
- Оптимизации циклов:
- Развёртывание
- Повторение
- Вынесение инварианта
- JIT-оптимизации
- Объединение захвата примитивов
- Оптимистичный захват
- Адаптивные блокировки
- Замена виртуального вызова
14. Транзакционная память
- Идея transactional memory
- Software transactional memory
- Hardware transactional memory
- Преимущества и круг задач
- Реализация HTM на линейках кэша
- Lock teleportation
15. Асинхронный ввод/вывод
- Блокирующий/неблокирующий
- Синхронный (реактор)/асинхронный (проактор)
- Преимущества асинхронной работы и реализация со стороны операционной системы
- Библиотеки асинхронного ввода/вывода
16. Wait-free MRMW снимок регистров
- Напоминание о MRSW алгоритме
- Переход к bounded версии на битовых handchake
- Расширание до MRMW
17. Средства поиска ошибок
- Google Thread Sanitizer
- Intel Parallel Studio
- Valgrind (модуль helgrind)
- Пример использования
18. Модель памяти
- Устройство кэшей процессора
- Пример на протоколе MESI
- Барьеры памяти (store/load)
- Модели памяти: Sequential consistency…
- Acquire/release семантика
19. Lock-free изнутри
- User-space RCU
- Схемы управления памятью:
- Tagged pointers
- Hazard pointer
20. Модель акторов
- Суть модели
- Применение в современных языках
- Шаблоны применения
21. Системная архитектура
- Компонентный подход (Layers, DTO…)
- Сервисный подход (Services, ESB…)
- Логическая и физическая архитектуры
22. Линеаризуемость
- Понятие линеаризуемости
- Lock-free стек Trieber
- Пример на очередях
- Lock-free очередь Michael & Scott
- Точки линеаризации
23. Оптимизации в реализации контейнеров
- Relaxed SkipList
courses/high_performance_computing/lectures.1522577168.txt.gz · Last modified: 2018/04/01 13:06 by kel