Учебник Параллельные алгоритмы для начинающих

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

1. 1 Зачем и в каких моделях

   1. Зачем нужны параллельные алгоритмы

      Почему рост частоты CPU остановился, а будущее производительности — за многоядерностью, GPU и масштабом данных.

   2. Конкурентность против параллелизма

      Чёткое различие между конкурентностью (управление многими задачами) и параллелизмом (одновременное выполнение ради скорости).

   3. Модели параллельных вычислений: PRAM, память, SIMD/MIMD, BSP

      Обзор теоретических и практических моделей: PRAM, разделяемая и распределённая память, SIMD/MIMD, модель BSP.

2. 2 Метрики и законы масштабирования

   1. Метрики: ускорение, эффективность, масштабируемость

      Как измеряют успех параллельного алгоритма: speedup, эффективность, сильная и слабая масштабируемость.

   2. Закон Амдала: почему последовательная часть всё ограничивает

      Ключевая идея параллелизма: непараллелимая доля задаёт жёсткий потолок ускорения. Расчёт на исполнимом Python.

   3. Закон Густафсона: масштабирование задачи

      Оптимистичный взгляд: когда задача растёт вместе с числом процессоров, ускорение масштабируется почти линейно.

   4. Накладные расходы: почему 2 ядра не дают ровно 2x

      Коммуникация, синхронизация, создание потоков и дисбаланс — невидимые налоги, съедающие ускорение.

3. 3 Декомпозиция работы

   1. Декомпозиция данных против декомпозиции задач

      Два главных способа разрезать работу: по данным (одна операция на разные куски) и по задачам (разные операции).

   2. Гранулярность и баланс нагрузки

      Как выбрать размер кусков работы и распределить их ровно, чтобы ядра не простаивали.

4. 4 Параллельные примитивы

   1. Параллельные примитивы: map и reduce

      Map и reduce — два кирпича, из которых складывается большинство параллельных алгоритмов.

   2. Параллельная редукция: дерево сложения за O(log n)

      Как свернуть n чисел не за n-1 шагов, а за log n: схема дерева редукции с пошаговой эмуляцией.

   3. Параллельный scan: префиксные суммы (Hillis-Steele)

      Префиксная сумма выглядит строго последовательной, но считается параллельно за log n шагов. Алгоритм Hillis-Steele.

   4. Work-efficient scan: алгоритм Blelloch

      Экономный по работе scan за O(n) операций: фазы up-sweep и down-sweep по дереву.

5. 5 Сортировка, поиск и графы

   1. Битоническая сортировка: сортировочная сеть

      Сеть из компараторов, сортирующая за фиксированное число шагов независимо от данных — идеал для GPU.

   2. Чётно-нечётная сортировка слиянием

      Простая локальная сортировка для решёток процессоров: соседи обмениваются и упорядочиваются по фазам.

   3. Sample sort и почему quicksort плохо параллелится

      Sample sort масштабируется на кластерах: разбить диапазон по сэмплам, разложить по корзинам, отсортировать локально.

   4. Параллельный поиск, BFS и связные компоненты

      Поиск в массиве, обход графа в ширину по уровням и связные компоненты — что параллелится легко, а что трудно.

6. 6 Матрицы и разделяй-и-властвуй

   1. Параллельное умножение матриц

      Почему умножение матриц — образцовая параллельная задача: независимые элементы, блочное разбиение, отличная масштабируемость.

   2. Разделяй-и-властвуй параллельно: fork-join

      Модель fork-join: рекурсивно делим задачу, считаем половины параллельно, объединяем. Основа Cilk, OpenMP tasks, Java ForkJoinPool.

   3. Work stealing: как планировщик балансирует ветви

      Механизм, который сам выравнивает нагрузку fork-join: простаивающее ядро крадёт задачу из очереди занятого.

7. 7 Модели программирования

   1. Потоки и OpenMP: разделяемая память на директивах

      OpenMP позволяет распараллелить циклы C/C++ парой директив #pragma — обзор модели разделяемой памяти.

   2. MPI: передача сообщений для кластеров

      MPI — стандарт распределённой памяти: процессы на разных узлах обмениваются сообщениями. Обзор send/recv и коллективов.

   3. GPU и data-parallel: модель SIMT (CUDA)

      Тысячи лёгких потоков выполняют одно ядро над разными данными. Когда GPU выигрывает, а когда нет.

   4. MapReduce и Spark: параллелизм на кластере

      Модель MapReduce и Spark распределяют обработку больших данных по тысячам узлов, скрывая координацию от программиста.

8. 8 Паттерны, анализ и практика

   1. Паттерны: master-worker, pipeline, stencil

      Три повторяющихся структуры параллельных программ: пул заданий, конвейер стадий и обновление по соседям.

   2. Анализ параллельных алгоритмов: work и span

      Две меры алгоритма: общая работа и критический путь (span). Их отношение — потенциальный параллелизм.

   3. Типичные ошибки: false sharing, дисбаланс, лишняя синхронизация

      Скрытые убийцы производительности: ложное разделение кэша, перекос нагрузки, чрезмерные блокировки, неверная гранулярность.

   4. Гонки в параллельных алгоритмах и когда НЕ стоит параллелить

      Краткий разбор гонок данных и трезвый взгляд: задачи, где параллелизм не окупается или вредит.