Параллельные и высокопроизводительные вычисления

Программа курса

Введение

  1. Тенденции развития вычислительных систем, обуславливающие необходимость применения распределённых (параллельных) методов вычислений
  2. Примеры вычислительно ёмких задач из разных областей науки
  3. Классификация параллельных систем (SIMD, MISD...). Краткая история параллельных систем
  4. Современные высокопроизводительные системы как аппаратно-программные комплексы: начиная от расширений SSE, через многоядерность к узлам кластеров

Параллелизм

  1. Способы распараллеливания программ: по данным; по управлению (операциям)
  2. Проблема автоматизации распараллеливания: текущее состояние средств, способных выявлять некоторые виды параллелизма. Обоснование невозможности полного решения проблемы на текущий момент
  3. Понятия ускорения, эффективности (закон Амдала), масштабируемости распараллеленного алгоритма
  4. Многопоточность или IPC
  5. Причины некоторых преимуществ потоков над процессами

Создание/завершение потоков

  1. Механизм запуска потока
  2. Корректное завершение потоков:
    • cancellation points
    • interrupted exception
    • примеры кода в glibc
  3. Сравнение различных потоков (POSIX, boost, java)
  4. Проброс исключений между потоками

Примитивы синхронизации

  1. Необходимость синхронизации: простые гонки данных
  2. Реализация примитивов синхронизации: алгоритм булочника
  3. Виды мьютексов:
    • рекурсивные/нерекурсивные
    • read/write
    • spin
    • futex
  4. Корректные захват/освобождение примитивов
  5. CAS-операции и атомики
  6. Условные переменные:
    • использование wait/notify
    • Spurious wakeups

Алгоритмы синхронизации

  1. Грубая
  2. Тонкая
  3. Оптимистичная
  4. Ленивая
  5. Неблокирующая (параллель с ORM)

Атомарные снимки регистров

  1. Классификация алгоритмов:
    • lock-free
    • wait-free
  2. SWMR-регистры
  3. Lock-free snapshot
  4. Wait-free snapshot

Ошибки || программирования

  1. Основные ошибки многопоточного программирования
    • Гонки данных (Data Race)
    • Взаимная блокировка (Deadlock)
    • Потерянный сигнал
  2. Специфические ошибки
    • Реакция потока на сигнал
    • Блокировки при fork многопоточных программ
    • Проблема ABA
    • Инверсия приоритетов

Профилирование многопоточных приложений

  1. Средства анализа производительности:
    • Утилита time
    • Intel Parallel Studio
    • valgrind (модули callgrind, cachegrind)
  2. Пример поиска узких мест

OpenMP и Intel TBB

  1. Обзор OpenMP:
    • параллельные секции
    • области видимости переменных
    • ограничения
  2. Обзор Intel TBB:
    • алгоритмы
    • аллокаторы
    • деревья задач
    • особенности планирования (work stealing...)
    • flow graphs (параллель с BPEL)

Java.util.concurrent

  1. Пулы потоков, корректное завершение пула
  2. Контроль задач через Future
  3. Потокобезопасные контейнеры
  4. Примитивы синхронизации

Шаблоны || программирования

  1. Структурные шаблоны:
    • Декомпозиция по задачам
    • Геометрическая декомпозиция
    • Recursive Data
    • Pipeline
  2. Некоторые программные структуры:
    • Parallel loops
    • Boss/Worker
  3. Разное:
    • Double check
    • Local Serializer

Кластерные вычисления

  1. Виды кластерных систем:
    • Балансировки нагрузки
    • Высокой надёжности
    • Вычислительные
  2. История и назначение стандарта MPI
  3. Обмен сообщениями:
    • С блокировкой
    • Без блокировки
    • Отложенные запросы на взаимодействие   
  4. Взаимодействие процессов:
    • Группы и коммуникаторы
    • Операции коллективного взаимодействия процессов
    • Редукция
    • Виртуальные топологии
  5. Средства анализа производительности:
    • Jumpshot
    • Intel® Trace Analyzer и Intel® Trace Collector

Консенсус. Сети Петри

  1. Линеаризуемость
  2. Атомарный регистр
  3. Консенсусное число
    • Консенсусное число RMW-регистров
    • Универсальность CAS-операций
  4. Верификация || программ (сети Петри)

Модель памяти

  1. Устройство кэшей процессора
  2. Пример на протоколе MESI
  3. Барьеры памяти (store/load)
  4. Модели памяти: Sequential consistency...
  5. Acquire/release семантика

Транзакционная память

  1. Идея transactional memory
  2. Software transactional memory
  3. Hardware transactional memory
  4. Преимущества и круг задач

Асинхронный ввод/вывод

  1. Блокирующий/неблокирующий
  2. Синхронный (реактор)/асинхронный (проактор)
  3. Преимущества асинхронной работы и реализация со стороны операционной системы
  4. Библиотеки асинхронного ввода/вывода

Wait-free MRMW снимок регистров

  1. Напоминание о MRSW алгоритме
  2. Переход к bounded версии на битовых handchake
  3. Расширание до MRMW

Lock-free изнутри

  1. User-space RCU
  2. Схемы управления памятью:
    • Tagged pointers
    • Hazard pointer