Инженерия параллельных алгоритмов
Инженерный подход
Перенос последовательной программы на кластер без переработки редко даёт ускорение — остаются глобальные массивы, лишние синхронизации и зависимости, которые один поток "проглатывал" бесплатно. Параллельная программа начинается с постановки и измерений, а запись на конкретном языке — один из последних шагов. Сначала — последовательный прототип на русском псевдокоде или блок-схеме (базовая информатика), затем граф зависимостей (статья 5), и только потом — OpenMP, MPI или GPU.
Это проектирование с измеримыми целями:
- Корректность — тот же результат, что последовательная версия (бит-в-бит или в пределах ε для float).
- Производительность — speedup, укладываемость в SLA.
- Масштабируемость — поведение при росте p и объёма данных.
- Сопровождаемость — читаемость, отладка, воспроизводимость.
Распараллеливание цикла, который занимает 2 % времени профиля, даёт сложность и риск гонок без заметного ускорения. Порядок работы — профиль (perf, VTune) → граф зависимостей → псевдокод → код (практика).
Постановка задачи
Перед кодом зафиксируйте:
| Вопрос | Зачем |
|---|---|
| Какой объём данных сейчас и через год? | Выбор weak vs strong scaling |
| CPU-bound или memory/network-bound? | OpenMP vs MPI vs GPU |
| Какое железо (узлы, NUMA, GPU)? | Mapping |
| Допустима ли погрешность? | Аппроксимация, mixed precision |
| Есть ли детерминизм для воспроизводимости? | Порядок reduction, RNG |
Классификация по типу параллелизма
Data parallelism (по данным)
Одна и та же операция применяется к многим элементам данных независимо.
Псевдокод
АЛГОРИТМ МАСШТАБИРОВАТЬ_ВЕКТОР(n, a, x, y)
параллельно для i от 0 до n − 1
y[i] := a * x[i] + y[i]
конец параллельно
КОНЕЦ
| Строка | Зависимости |
|---|---|
y[i] := … | Индекс i уникален у итерации — нет гонки записи между потоками |
x[i], y[i] | Чтение и запись только "своей" ячейки |
Подходит для плотных массивов, BLAS, обработки изображений, слоёв нейросетей.
Справочно на C++ (OpenMP)
#pragma omp parallel for
for (int i = 0; i < n; ++i)
y[i] = a * x[i] + b;
#pragma omp parallel for — директива компилятора: создать потоки и раздать итерации i. Подробный разбор — в статье 11.
Task parallelism (по задачам)
Разные роли или этапы выполняются разными исполнителями.
Псевдокод (конвейер из трёх стадий)
АЛГОРИТМ КОНВЕЙЕР_ОБРАБОТКИ
запустить поток А: пока есть записи
запись := РАЗОБРАТЬ(вход)
передать в очередь1(запись)
запустить поток Б: пока есть записи в очередь1
запись := ПРОВЕРИТЬ(очередь1)
передать в очередь2(запись)
запустить поток В: пока есть записи в очередь2
СОХРАНИТЬ(очередь2)
дождаться завершения А, Б, В
КОНЕЦ
Схема потоков —
Поток1: разбор → Поток2: проверка → Поток3: сохранение
Подходит, когда стадии разнородны (I/O и вычисления), а не когда одна формула на миллион одинаковых ячеек.
Pipelining
Перекрытие стадий на непрерывном потоке данных — пока итерация k на стадии "считать", итерация k−1 уже на стадии "записать" (аналогия с конвейером CPU).
для k от 1 до K
// на такте t разные k одновременно на разных стадиях
стадия1(k); стадия2(k−1); стадия3(k−2)
Divide and conquer
Рекурсивное разбиение задачи (сортировка слиянием, быстрая сортировка, FFT) — подзадачи уходят на разные процессоры, затем слияние результатов.
АЛГОРИТМ СОРТИРОВКА_РАЗДЕЛЯЙ(n, массив)
если n ≤ порог то
ПОСЛЕДОВАТЕЛЬНО_ОТСОРТИРОВАТЬ(массив)
иначе
(лево, право) := РАЗДЕЛИТЬ(массив)
параллельно
СОРТИРОВКА_РАЗДЕЛЯЙ(лево)
СОРТИРОВКА_РАЗДЕЛЯЙ(право)
конец параллельно
СЛИТЬ(лево, право, массив)
конец если
КОНЕЦ
Geometric / domain decomposition
Область (сетка 2D/3D) режется на подобласти. Каждый процессор владеет блоком; для соседних ячеек нужны значения с границы — halo (ghost layer).
для каждого процессора P с блоком B
ОБНОВИТЬ_ВНУТРЕННОСТЬ(B)
ОБМЕНЯТЬ_HALO_С_СОСЕДЯМИ(P)
ОБНОВИТЬ_ГРАНИЦЫ(B, halo)
Этапы разработки
1. Последовательный прототип (корректность)
2. Профилирование — где 90% времени
3. Граф зависимостей — что параллелить
4. Выбор модели (OpenMP / MPI / GPU)
5. Декомпозиция + минимизация обмена
6. Параллельная реализация
7. Верификация (сравнение с эталоном)
8. Benchmark на разных p
9. Tuning (affinity, block size, overlap)
Не пропускайте шаг 2: правило 90/10 работает и здесь.
Декомпозиция при параллелизме по данным
1D block decomposition
Массив длины n на p процессоров.
Псевдокод
АЛГОРИТМ РАЗБИТЬ_1D(n, p, rank)
размер_блока := ⌈n / p⌉
начало := rank * размер_блока
конец := min(начало + размер_блока, n) − 1
вернуть диапазон [начало .. конец]
КОНЕЦ
Процесс с номером rank обрабатывает только свой диапазон индексов.
2D block (матрицы)
Каждый процессор — подматрица; для умножения C = A·B — классическая схема.
Блочная декомпозиция с локализацией
Локализация подобластей — каждый процессор владеет своим блоком данных и по возможности считает только над ним, подгружая тонкий слой границы (halo) у соседей.
Цель: данные, которые часто используются вместе, лежат на том же узле, что и вычисление.
- First-touch на NUMA: первый доступ выделяет страницу на текущем узле.
- Block size под L3 cache (например 64×64 double ≈ 32 KiB).
- Halo cells — ghost layer для обмена с соседями в сеточных методах.
┌───────┬───────┐
│ block │ halo→ │
│ mine │ │
├───────┼───────┤
│ ↓ │ block │
│ halo │ neigh │
└───────┴───────┘
Общие рекомендации
- Начинайте с coarse-grained — крупные задачи на поток; мелкий параллелизм убивает на overhead.
- Minimize sharing — локальные переменные, reduction вместо lock на каждый элемент.
- Избегайте false sharing — выравнивание структур по cache line (64 B).
- Batch communications — одно большое MPI-сообщение лучше сотни мелких.
- Overlap compute and comm —
MPI_Isend+ работа, пока данные в пути. - Deterministic reductions — фиксированный порядок суммирования для воспроизводимости.
- Тестируйте на p=1 — regression против sequential.
- Документируйте предположения — "требует n % p == 0", "только shared memory".
Связь с анализом графов
Матрица следования показывает легальные параллельные группы; временной анализ — сколько процессоров нужно и нижняя граница времени; Амдаль — потолок из-за последовательных участков.
MPI — полосы строк и halo (гибрид с OpenMP)
Каждый MPI-процесс (rank) владеет полосой строк двумерной сетки. Для 5-точечного stencil (значение ячейки зависит от соседей сверху и снизу) нужны ghost rows — копии граничных строк соседних процессов.
Псевдокод
АЛГОРИТМ STENCIL_1D_ПО_СТРОКАМ
rank, size := номер и число MPI-процессов
сосед_верх := rank − 1 // если rank = 0 — соседа нет
сосед_низ := rank + 1 // если rank = size−1 — соседа нет
ОТПРАВИТЬ_И_ПОЛУЧИТЬ(нижняя_строка_блока → ghost_снизу, сосед_низ)
ОТПРАВИТЬ_И_ПОЛУЧИТЬ(верхняя_строка_блока → ghost_сверху, сосед_верх)
параллельно для j от 1 до n_локально
для каждого столбца i
новое[j,i] := f(старое[j,i], ghost_сверху, ghost_снизу, соседи по i)
конец параллельно
КОНЕЦ
| Шаг | Зачем |
|---|---|
| Halo-обмен | Без соседних строк формула stencil неполная на границе блока |
параллельно для j | Внутри одного rank — OpenMP по строкам локального блока |
Справочно на C (MPI + OpenMP)
Код ITЗагрузка примера кода…
| Элемент | Смысл |
|---|---|
rank > 0 ? rank - 1 : MPI_PROC_NULL | Тернарный оператор C: если соседа нет, MPI "пропускает" сторону обмена |
MPI_PROC_NULL | Константа "процесс-получатель отсутствует" |
&local[1] | Адрес второй строки локального массива — граница для отправки |
MPI_DOUBLE | Тип элементов — вещественное double |
#pragma omp parallel for | Потоки внутри одного MPI-процесса |
Паттерн — Sendrecv с соседями, затем OpenMP внутри rank; типичный гибрид на кластере (практика).
Дерево reduction
rank 0: sum0 ──┐
rank 1: sum1 ──┼──► local on pairs ──► MPI_Allreduce ──► global
rank 2: sum2 ──┤
rank 3: sum3 ──┘
Не суммируйте через rank 0 в цикле Send — latency O(p); MPI_Allreduce — O(log p) по глубине дерева на большинстве реализаций.
Антипаттерны
| Антипаттерн | Проблема |
|---|---|
| Parallel for на 100 элементов | Overhead > выигрыш |
| Lock на каждый increment | Contention |
| Barrier каждую итерацию | Сериализация |
| "Параллелить всё" без профиля | Сложность без speedup |
| Игнор NUMA | Удалённая память |