Инженерия параллельных алгоритмов

ОБЯЗАТЕЛЬНО

Разработчику Архитектору

Инженерный подход

Параллельная программа начинается с постановки и измерений, а директива #pragma omp parallel for — один из последних шагов. Это проектирование с измеримыми целями:

1. Корректность — тот же результат, что последовательная версия (бит-в-бит или в пределах ε для float).
2. Производительность — speedup, укладываемость в SLA.
3. Масштабируемость — поведение при росте p и объёма данных.
4. Сопровождаемость — читаемость, отладка, воспроизводимость.

Типичная ошибка новичка: распараллелить цикл, который занимает 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 (по данным)

Одна операция — много элементов:

#pragma omp parallel for
for (int i = 0; i < n; ++i)
    y[i] = a * x[i] + b;

Подходит: плотные массивы, BLAS, image processing, ML layers.

Task parallelism (по задачам)

Разные функции или этапы pipeline на разных workers:

Thread1: parse → Thread2: validate → Thread3: save

Подходит: разнородные стадии, разный I/O vs compute.

Pipelining

Перекрытие стадий на потоке данных (как конвейер CPU).

Divide and conquer

Рекурсивное разбиение (merge sort, quicksort, FFT) → подзадачи на разных процессорах.

Geometric / domain decomposition

Область (сетка, 2D/3D) режется на подобласти; каждый процессор считает свой блок, обменивается 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 процессоров:

rank r получает элементы [ r·⌈n/p⌉ , … )

2D block (матрицы)

Каждый процессор — подматрица; для умножения C = A·B — классическая схема.

Блочная декомпозиция с локализацией

Цель: данные, которые часто используются вместе, лежат на том же узле, что и вычисление.

• First-touch на NUMA: первый доступ выделяет страницу на текущем узле.
• Block size под L3 cache (например 64×64 double ≈ 32 KiB).
• Halo cells — ghost layer для обмена с соседями в сеточных методах.

┌───────┬───────┐
│ block │ halo→ │
│  mine │       │
├───────┼───────┤
│   ↓   │ block │
│ halo  │ neigh │
└───────┴───────┘

---

Общие рекомендации

1. Начинайте с coarse-grained — крупные задачи на поток; мелкий параллелизм убивает на overhead.
2. Minimize sharing — локальные переменные, reduction вместо lock на каждый элемент.
3. Избегайте false sharing — выравнивание структур по cache line (64 B).
4. Batch communications — одно большое MPI-сообщение лучше сотни мелких.
5. Overlap compute and comm — MPI_Isend + работа, пока данные в пути.
6. Deterministic reductions — фиксированный порядок суммирования для воспроизводимости.
7. Тестируйте на p=1 — regression против sequential.
8. Документируйте предположения — «требует n % p == 0», «только shared memory».

---

Связь с анализом графов

Матрица следования показывает легальные параллельные группы; временной анализ — сколько процессоров нужно и нижняя граница времени; Амдаль — потолок из-за последовательных участков.

---

---

MPI — row decomposition с halo (фрагмент)

// каждый rank — полоса строк; для 5-точечного stencil нужны ghost rows
int up = (rank > 0) ? rank - 1 : MPI_PROC_NULL;
int down = (rank < size-1) ? rank + 1 : MPI_PROC_NULL;

MPI_Sendrecv(&local[1], nx, MPI_DOUBLE, up, 0,
             &ghost_top, nx, MPI_DOUBLE, up, 1, comm, &st);
MPI_Sendrecv(&local[nlocal], nx, MPI_DOUBLE, down, 1,
             &ghost_bot, nx, MPI_DOUBLE, down, 0, comm, &st);

#pragma omp parallel for
for (int j = 1; j <= nlocal; ++j)
    update_stencil(j);

Паттерн: 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	Удалённая память

---

Что дальше

• Параллельное умножение матриц
• Fortran OpenMP/MPI
• Потоки C++

---