Практика — OpenMP, MPI и профилирование
Практика — от идеи к эталонному коду
Теория из графов и законов становится инженерной, когда вы можете записать параллельный алгоритм и проверить его на железе. Эта статья устроена в два слоя —
- Алгоритмический псевдокод на русском — переносимый план, понятный до изучения C, C++ или Fortran.
- Справочные фрагменты на C/C++ — как те же идеи выглядят в OpenMP и MPI, с разбором ключевых слов и синтаксиса.
Если вы ещё не проходили базовую информатику и алгоритмы, вернитесь к ним за определением алгоритма, цикла и ветвления. Здесь мы применяем те же правила к нескольким исполнителям одновременно.
Выбор технологии — OpenMP, MPI, GPU
Задача CPU-bound?
├─ Да → Данные помещаются на одном сервере?
│ ├─ Да → OpenMP / потоки (ниже в этой статье)
│ └─ Нет → MPI или MPI+OpenMP ([память и системы](./3.md))
└─ Массовый однотипный цикл по массиву?
└─ GPU / SIMD ([архитектуры](./2.md), [умножение матриц](./9.md))
Красные флаги перед параллелизацией —
- Последовательная доля f > 10 % без плана её сжать (законы производительности).
- Каждая итерация читает «весь мир» (replicate all-to-all).
- Размер задачи на поток < 10⁴ операций — overhead съест выигрыш.
Один сервер, общая память — OpenMP или потоки. Несколько узлов кластера — MPI (часто MPI + OpenMP внутри узла). Массовый параллелизм по данным на GPU — CUDA/SYCL — см. GPU.
Соглашения псевдокода в этой статье
| Конструкция | Смысл |
|---|---|
АЛГОРИТМ имя … КОНЕЦ | Именованный фрагмент логики |
для i от A до B | Цикл с включёнными границами |
если … то … иначе … | Ветвление |
параллельно | Несколько исполнителей работают одновременно в описанном блоке |
параллельно для i от … | Итерации цикла распределяются между потоками |
синхронизация | Все исполнители ждут друг друга (барьер) |
локально на исполнителе | Переменная своя у каждого потока/процесса |
редукция(+: S) | Каждый складывает в свою копию S, в конце — общая сумма |
отправить буфер процессу P | Сообщение в модели распределённой памяти (MPI) |
получить буфер от процесса P | Приём сообщения |
Исполнитель в псевдокоде OpenMP — поток (thread) внутри одной программы на одном сервере. В MPI — процесс (process) со своей памятью; процессов может быть несколько на разных машинах.
OpenMP — параллелизм по данным на одном узле
OpenMP — стандарт для C, C++ и Fortran на одной машине, где процессы видят общую оперативную память. Программист помечает участки кода директивами; среда выполнения создаёт потоки и распределяет работу.
Модель fork-join (развилка и слияние)
Главный поток выполняет программу последовательно
↓
Достигает метки "параллельный регион"
↓
Создаётся команда из P потоков (fork)
↓
Все потоки выполняют тело региона (часто — разные итерации цикла)
↓
Синхронизация (барьер) — все ждут друг друга (join)
↓
Снова работает в основном один главный поток
Это соответствует параллелизму по данным — одна и та же формула для разных элементов массива.
Пример 1 — SAXPY (масштабирование и сложение векторов)
Задача. Даны длина n, коэффициент a, массивы x и y. Для каждого индекса i нужно выполнить y[i] := a * x[i] + y[i]. Итерации независимы — классический кандидат на параллельный цикл.
Псевдокод
АЛГОРИТМ SAXPY(n, a, x, y)
параллельно для i от 0 до n − 1
y[i] := a * x[i] + y[i]
конец параллельно
КОНЕЦ
Построчный разбор псевдокода
| Строка | Что происходит |
|---|---|
АЛГОРИТМ SAXPY(...) | Имя операции; параметры — размер и ссылки на массивы в памяти |
параллельно для i от 0 до n − 1 | Среда делит диапазон индексов между потоками; каждый i обрабатывает ровно один поток |
y[i] := a * x[i] + y[i] | Чтение x[i] и y[i], умножение, сложение, запись в y[i]; разные i пишут в разные ячейки — конфликта записи нет |
конец параллельно | Неявная синхронизация перед выходом из региона |
Почему это быстрее. При P потоках и равной нагрузке время близко к T₁/P, если задача memory-bound и данные лежат локально (см. NUMA).
Справочно на C++ (OpenMP)
Код ITЗагрузка примера кода…
| Элемент | Роль |
|---|---|
#include <omp.h> | Подключение заголовка OpenMP (объявления, таймеры, число потоков) |
void saxpy(...) | Функция на языке C++; const double* x — указатель на массив только для чтения |
int n | Целое число элементов; в C++ индексация с 0 |
#pragma omp parallel for | Директива препроцессора/компилятора — "создай команду потоков и распредели итерации цикла for" |
#pragma | Специальная строка для компилятора; не обычный код |
parallel | Режим "несколько потоков" |
for | Привязка к следующему циклу for |
for (int i = 0; i < n; ++i) | Классический цикл; ++i увеличивает счётчик на 1 после каждой итерации |
y[i] = ... | Оператор присваивания (в C++ один знак =) |
Сборка (GCC/Clang) — g++ -fopenmp -O3 saxpy.cpp. Без -fopenmp директива игнорируется и цикл останется последовательным.
Поведение runtime. По умолчанию используется schedule(static) — поток 0 получает блок индексов в начале, поток 1 — следующий блок и т.д. Подходит, когда все итерации одинаково тяжёлые.
Пример 2 — сумма элементов массива (редукция)
Задача. Вычислить S = a[0] + a[1] + … + a[n−1]. Наивный параллельный цикл с общей переменной S даст гонку данных — несколько потоков одновременно читают и пишут S, результат недетерминирован.
Псевдокод
АЛГОРИТМ СУММА_МАССИВА(a, n)
S := 0
параллельно для i от 0 до n − 1
редукция(+: S)
S_локально := S_локально + a[i] // у каждого потока своя копия
конец параллельно
// среда складывает локальные копии в общее S (дерево суммирования)
вернуть S
КОНЕЦ
Построчный разбор
| Строка | Смысл |
|---|---|
S := 0 | Начальное значение до параллельного региона |
редукция(+: S) | Объявление операции свёртки — в конце региона все частичные суммы складываются в одно S |
S_локально | У каждого потока своя копия; во время цикла потоки не делят одну ячейку памяти |
| Дерево в конце | Реализация паттерна из временного анализа — параллельные частичные суммы + логарифмическая стадия слияния |
Справочно на C++
double sum = 0.0;
#pragma omp parallel for reduction(+:sum)
for (int i = 0; i < n; ++i)
sum += a[i];
| Элемент | Смысл |
|---|---|
double sum | Вещественное число двойной точности |
reduction(+:sum) | OpenMP создаёт локальные sum на поток, в конце выполняет + |
sum += a[i] | Сокращённая запись sum = sum + a[i] |
Другие операции редукции — *, max, min, побитовые — с тем же шаблоном.
Пример 3 — неравная нагрузка (динамическое расписание)
Задача. Время обработки элемента i сильно зависит от i (например, больше простых чисел в факторизации). Статическое разбиение оставит одни потоки простаивающими.
Псевдокод
АЛГОРИТМ ТЯЖЁЛЫЕ_ИТЕРАЦИИ(n)
параллельно для i от 0 до n − 1
расписание(динамическое, порция = 64)
ТЯЖЁЛАЯ_ОБРАБОТКА(i)
конец параллельно
КОНЕЦ
| Конструкция | Смысл |
|---|---|
расписание(динамическое, порция = 64) | Поток, освободившийся, берёт следующие 64 индексов из очереди; баланс нагрузки улучшается ценой накладных расходов |
ТЯЖЁЛАЯ_ОБРАБОТКА(i) | Заменитель вашей функции |
Справочно на C++
#pragma omp parallel for schedule(dynamic, 64)
for (int i = 0; i < n; ++i)
heavy(i);
См. введение про load imbalance.
NUMA — привязка потоков к ядрам
На сервере с несколькими сокетами память физически разнесена. Без привязки потоки "переезжают" между ядрами, доступ к "чужой" RAM медленнее — см. память и NUMA.
Настройка среды (shell, не псевдокод) —
export OMP_PROC_BIND=close
export OMP_PLACES=cores
| Переменная | Эффект |
|---|---|
OMP_PROC_BIND=close | Потоки держатся рядом с ядрами, где стартовали |
OMP_PLACES=cores | Места привязки — логические ядра |
MPI — распределённая память и обмен сообщениями
MPI (Message Passing Interface) — библиотека для нескольких процессов. У каждого процесса своя память; общие переменные между узлами кластера отсутствуют. Любой обмен — явная отправка и приём сообщения. Термины rank, size, communicator — в терминологии раздела.
Программа обычно SPMD — один и тот же текст main, разные данные в зависимости от rank (модели).
Пример 4 — инициализация и приветствие
Псевдокод
АЛГОРИТМ ГЛАВНАЯ
ИНИЦИАЛИЗИРОВАТЬ_MPI()
rank := НОМЕР_МОЕГО_ПРОЦЕССА()
size := ЧИСЛО_ПРОЦЕССОВ()
вывести("Привет от процесса", rank, "из", size)
ЗАВЕРШИТЬ_MPI()
КОНЕЦ
Запуск в оболочке — mpirun -np 4 ./hello создаёт четыре копии программы; каждая печатает свой rank.
Справочно на C
Код ITЗагрузка примера кода…
| Строка | Разбор |
|---|---|
int main(int argc, char** argv) | Точка входа в программу на C; argc — число аргументов командной строки, argv — массив строк |
MPI_Init(&argc, &argv) | Старт среды MPI; может изменить аргументы |
int rank, size | Целые переменные для номера и размера |
MPI_Comm_rank(MPI_COMM_WORLD, &rank) | Записать в rank номер этого процесса; &rank — адрес переменной (указатель в C) |
MPI_Comm_size(..., &size) | Записать общее число процессов |
printf("...", rank, size) | Форматированный вывод; %d — место для целого |
MPI_Finalize() | Корректное завершение MPI |
return 0 | Код успеха операционной системе |
Пример 5 — точечный обмен (один отправитель, один получатель)
Псевдокод
АЛГОРИТМ ОБМЕН_42
ИНИЦИАЛИЗИРОВАТЬ_MPI()
rank := НОМЕР_МОЕГО_ПРОЦЕССА()
если rank = 0 то
данные := 42
отправить буфер(данные, 1 целое) процессу 1, метка 0
иначе если rank = 1 то
получить буфер(буфер, 1 целое) от процесса 0, метка 0
// в буфере значение 42
конец если
ЗАВЕРШИТЬ_MPI()
КОНЕЦ
Справочно на C
Код ITЗагрузка примера кода…
| Вызов | Параметры по смыслу |
|---|---|
MPI_Send | Адрес буфера, число элементов, тип MPI_INT, номер получателя 1, метка 0, группа |
MPI_Recv | Буфер приёма, ожидаемый отправитель 0, остальное аналогично |
MPI_STATUS_IGNORE | Статус приёма нас не интересует в учебном примере |
Блокировка. Send и Recv в простейшем виде блокирующие — процесс ждёт завершения операции. Для перекрытия с вычислениями — неблокирующий режим (пример 7).
Пример 6 — глобальная сумма (коллективная операция)
Псевдокод
АЛГОРИТМ ГЛОБАЛЬНАЯ_СУММА
локальная_сумма := ЧАСТИЧНАЯ_СУММА_НА_ЭТОМ_ПРОЦЕССЕ()
ВСЕ_РЕДУКЦИЯ(локальная_сумма → глобальная_сумма, операция СЛОЖЕНИЕ)
// у каждого процесса в глобальная_сумма — один и тот же итог
КОНЕЦ
Писать вручную "каждый шлёт каждому" хуже по latency; библиотека реализует дерево или топологию сети.
Справочно на C
double local_sum = partial_sum();
double global_sum;
MPI_Allreduce(&local_sum, &global_sum, 1, MPI_DOUBLE, MPI_SUM, MPI_COMM_WORLD);
| Параметр | Смысл |
|---|---|
&local_sum | Входное значение на этом rank |
&global_sum | Выход — результат на всех |
1 | Один элемент типа MPI_DOUBLE |
MPI_SUM | Операция — суммирование |
Пример — один шаг Гаусса (MPI_Bcast)
Связь с параллельным методом Гаусса: на шаге k все процессы должны видеть одну и ту же нормированную опорную строку. Вместо ручной цепочки Send/Recv используют коллектив MPI_Bcast — корень рассылает буфер, остальные получают копию.
Упрощение учебного фрагмента — глобальная строка k лежит у процесса owner_k (например, тот, кому достались строки с индексом k при блочном разбиении).
Псевдокод (один шаг k)
АЛГОРИТМ ШАГ_ГАУССА_K(k, n, A_лок, b_лок, rank, size)
owner_k := процесс_владеющий_глобальной_строкой(k)
если rank = owner_k то
p := индекс_pivot_в_столбце_k_среди_локальных_строк
MPI_Bcast(p, корень = owner_k)
если нужна_перестановка_строк(k, p) то
ОБМЕН_СТРОКАМИ_МЕЖДУ_ПРОЦЕССАМИ(k, p) // учебно — редко вручную; в проде — ScaLAPACK
конец если
если rank = owner_k то
НОРМИРОВАТЬ_СТРОКУ(k)
собрать_буфер := [A[k,k..n-1], b[k]]
MPI_Bcast(собрать_буфер, корень = owner_k)
для i в локальных_строках, i > k
ИСКЛЮЧИТЬ_PIVOT_ИЗ_СТРОКИ(i, k, собрать_буфер)
конец для
КОНЕЦ
После цикла по k от 0 до n−1 матрица на всех узлах согласована в верхнетреугольном виде (при корректном обмене строк).
Справочно на C (фрагмент шага k)
Код ITЗагрузка примера кода…
| Вызов | Роль в Гауссе |
|---|---|
MPI_Bcast(&pivot_row, …) | Все узлы знают, какую строку считать опорной |
MPI_Bcast(row_buf, …) | Все узлы получают одинаковую нормированную строку k |
| Локальный цикл по i | Параллельная фаза исключения на своих строках |
Профилирование. На малых n и большом size два Bcast на шаг × n шагов дают заметный MPI time — это ожидаемо и совпадает с ограничениями масштабирования.
Пример 7 — обмен "ореолом" (halo) для сеточных задач
При геометрической декомпозиции каждый процесс считает свой блок сетки, но для шаблона (например, 5-точечный stencil) нужны значения с соседней полосы — ghost cells, halo.
Псевдокод
АЛГОРИТМ STENCIL_С_HALO
сосед_верх := rank − 1 (или "нет", если rank = 0)
сосед_низ := rank + 1 (или "нет", если rank = size − 1)
ОТПРАВИТЬ_И_ПОЛУЧИТЬ(
отправка: нижняя_граница_локального_блока,
приём: буфер_ghost_снизу,
партнёр: сосед_низ
)
ОТПРАВИТЬ_И_ПОЛУЧИТЬ(
отправка: верхняя_граница_локального_блока,
приём: буфер_ghost_сверху,
партнёр: сосед_верх
)
параллельно для j от 1 до n_локально
ОБНОВИТЬ_ЯЧЕЙКИ_СТЕНСИЛА(j, ghost_сверху, ghost_снизу)
конец параллельно
КОНЕЦ
Правило инженерии — одно крупное сообщение на направление лучше десятков мелких; иначе доминирует задержка сети, а не пропускная способность.
Справочно на C (фрагмент)
MPI_Sendrecv(halo_send_buf, count, MPI_DOUBLE, neighbor, send_tag,
halo_recv_buf, count, MPI_DOUBLE, neighbor, recv_tag,
MPI_COMM_WORLD, &status);
Sendrecv — один вызов "отправить соседу и принять от соседа"; удобен для симметричного halo без взаимной блокировки.
Пример 8 — перекрытие вычислений и обмена
Псевдокод
АЛГОРИТМ ПЕРЕКРЫТИЕ
начать_асинхронную_отправку(буфер, получатель)
ВЫПОЛНИТЬ_ЛОКАЛЬНЫЕ_ВЫЧИСЛЕНИЯ() // пока сеть работает
дождаться_завершения_отправки()
КОНЕЦ
Справочно на C
MPI_Request req;
MPI_Isend(buf, count, MPI_DOUBLE, dest, tag, MPI_COMM_WORLD, &req);
compute_locally();
MPI_Wait(&req, MPI_STATUS_IGNORE);
| Вызов | Отличие от блокирующего |
|---|---|
MPI_Isend | Отправка начата, управление возвращается сразу |
MPI_Wait | Дождаться завершения перед повторным использованием буфера |
Гибрид MPI + OpenMP
На суперкомпьютере часто запускают один MPI-процесс на сокет или NUMA-узел, внутри — OpenMP на физических ядрах.
Псевдокод
АЛГОРИТМ ГИБРИД
rank, size := номер и число MPI-процессов
мой_диапазон := РАЗБИТЬ_ИНДЕКСЫ_0..N_ПО_ПРОЦЕССАМ(rank, size)
параллельно для i от мой_диапазон.начало до мой_диапазон.конец
ОБРАБОТАТЬ(i)
конец параллельно
КОНЕЦ
Меньше MPI-процессов — меньше копий данных и сообщений; следите, чтобы OMP_NUM_THREADS не превышал число физических ядер на узел.
Справочно на C
#pragma omp parallel for
for (int i = my_start; i < my_end; ++i)
process(i);
Соответствие идей — псевдокод, OpenMP, MPI
| Идея | Псевдокод | OpenMP (один узел) | MPI (кластер) |
|---|---|---|---|
| Независимые итерации | параллельно для i | #pragma omp parallel for | Разные i на разных rank |
| Общая сумма | редукция(+: S) | reduction(+:sum) | MPI_Allreduce |
| Синхронизация всех | синхронизация | неявный барьер конца региона | MPI_Barrier (осторожно в hot path) |
| Обмен данными | отправить / получить | не нужен (shared memory) | MPI_Send / MPI_Recv |
| Опорная строка Гаусса | рассылают_строку_k_всем | барьер + shared буфер | MPI_Bcast |
| Соседние данные сетки | halo в псевдокоде | копия в shared буфер + барьер | MPI_Sendrecv |
Пошаговая отладка параллельного кода
| Шаг | Действие |
|---|---|
| 1 | Эталон последовательно на малых данных (псевдокод или однопоточный запуск) |
| 2 | OpenMP с одним потоком (OMP_NUM_THREADS=1) — результат должен совпасть |
| 3 | Рост числа потоков / rank; сравнение с эталоном (для float — допуск ε) |
| 4 | Профилирование — где реально тратится время |
| 5 | Графики strong/weak scaling — законы |
Инструменты
| Инструмент | Назначение |
|---|---|
perf, VTune | CPU, промахи кэша, NUMA |
gprof, -pg | Грубый профиль по функциям |
mpiP, TAU | Объём и время MPI-сообщений |
| Valgrind Helgrind | Гонки в pthreads |
| ThreadSanitizer | -fsanitize=thread в GCC/Clang |
Типичная находка профиля — 80 % времени в одном последовательном цикле. Сначала параллелят его (в псевдокоде — параллельно для), затем проверяют ускорение.
Чек-лист перед запуском на кластере
- Результат совпадает с последовательным эталоном (или задокументирован ε).
- Измерены
T₁,T_p, speedup, efficiency на нескольких p. - В горячем цикле нет лишних
barrier/MPI_Barrier. - Размер сообщений — от нескольких KB (или осознанно мелкие).
- На сервере настроены NUMA и affinity.
- Зафиксированы последовательная доля f, критический путь, strong и weak scaling.
Что дальше
| Тема | Куда |
|---|---|
| Декомпозиция, halo, антипаттерны | Инженерия алгоритмов |
| Матрицы, Cannon, SUMMA | Умножение матриц |
Гаусс, MPI_Bcast на шаге | Параллельный метод Гаусса |
| Синтаксис Fortran OpenMP/MPI | Fortran HPC |
| Потоки, mutex в C++ | Потоки C++ |
| Алгоритмы и блок-схемы | Базовая информатика |