Модели параллельных вычислений и топологии

ОБЯЗАТЕЛЬНО

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

Модели параллелизма - потоки, задачи и акторы

Реальное железо слишком сложно для доказательств и оценок. Модель вычислений — упрощённое правило игры: сколько процессоров, как они видят память, сколько стоит шаг. На модели строят верхние и нижние границы времени алгоритма и сравнивают стратегии обмена данными.

Зачем это вам: модель отвечает на вопросы вроде «сколько раундов нужно, чтобы просуммировать массив из миллиона элементов на миллионе процессоров?» — без привязки к конкретному серверу. Потом тот же алгоритм переносят в OpenMP, MPI или CUDA.

---

Модель PRAM (Parallel Random Access Machine)

PRAM — учебная shared-memory машина с p процессорами и одной общей RAM (как потоки OpenMP, но в идеализированных правилах):

• Все процессоры работают синхронно раундами (lock-step): за один раунд каждый выполняет одну операцию чтения/записи.
• Если два процессора хотят одну ячейку в один раунд — поведение задаёт вариант PRAM:

Вариант	Чтение	Запись
EREW	Exclusive	Exclusive
CREW	Concurrent	Exclusive
CRCW	Concurrent	Concurrent (нужно правило агрегации)

PRAM не реализуется напрямую — это теоретический этalon. Но алгоритмы на PRAM (prefix sum, list ranking) переносятся на реальные системы с барьерами и atomics.

Пример: parallel prefix sum (scan) за O(log n) раундов на n процессорах EREW — основа многих GPU-примитивов.

---

Message Passing (передача сообщений)

Модель распределённой памяти: процессы имеют локальное состояние и обмениваются сообщениями send/receive.

P0: send(data, dest=1)     P1: recv(buf, source=0)

Стандарт MPI (Message Passing Interface) — де-факто API для HPC-кластеров:

• Point-to-point — MPI_Send / MPI_Recv.
• Collective — MPI_Bcast, MPI_Reduce, MPI_Allreduce (оптимизированы под топологию сети).

Асинхронный обмен (MPI_Isend) позволяет перекрывать вычисления и коммуникации — ключ к масштабируемости.

Связь с ОС: IPC и очереди.

---

SPMD — Single Program, Multiple Data

SPMD (Single Program, Multiple Data) — одна программа, разные данные на каждом процессоре.

Вы пишете один файл main.c, запускаете его 100 раз (100 процессов MPI), и внутри каждый процесс знает свой rank (номер 0…99) и обрабатывает свой кусок массива. Код одинаковый, данные разные.

Один исходный код на всех процессорах, каждый со своим фрагментом данных (разный rank, разный индекс цикла):

int rank;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
for (int i = rank; i < N; i += num_procs)
    process(data[i]);

Это не то же самое, что SIMD: в SPMD ветвления могут расходиться (MIMD), но логика программы одна. Большинство MPI- и CUDA-приложений — SPMD.

Fortran coarray — языковая поддержка SPMD без явного MPI: array[i] = array[j] на удалённом образе.

---

Модель воркеров и actor model

Альтернативы для слабосвязанных задач:

• Worker pool — очередь задач, N воркеров забирают job (типичный thread pool).
• Actor model — изолированные акторы, только сообщения (микросервисы на уровне архитектуры).

Для HPC с плотными матрицами чаще SPMD + collective; для event-driven систем — actors.

---

Топологии сетей передачи данных

Физическая или логическая связность процессоров влияет на диаметр (макс. число hop) и bisection bandwidth (сколько данных можно перекинуть «пополам» кластера).

Линейка:  P0 — P1 — P2 — P3        (просто, плохо масштабируется)

Кольцо:   P0 — P1 — P2 — P3 —┐
              └───────────────┘

2D mesh:  P00 — P01 — P02
           |     |     |
          P10 — P11 — P12

Гиперкуб: 2^d узлов, d соседей (классика Intel nCube)

Топология	Процессоров	Диаметр	Применение
Полная связь	p	1	Малые SMP (шина)
Кольцо	p	⌊p/2⌋	Учебные модели
2D/3D mesh/torus	p	O(√p)	Многие суперкомпьютеры
Fat tree	p	O(log p)	InfiniBand в дата-центрах

Отображение логической решётки алгоритма на mesh/torus минимизирует число hop для nearest-neighbor обмена (например, в Jacobi-итерациях).

---

Диаграмма расписания (Schedule / Gantt)

Расписание показывает, какой процессор выполняет какой оператор и когда:

Время →  1    2    3    4    5
P0:      [A ] [C ] [E ]
P1:           [B ] [D ]
P2:                [F ]

Из расписания видно:

• Длину критического пути (минимальное время при бесконечных процессорах).
• Простои (idle) — где load imbalance.
• Возможность переупорядочить независимые операции.

Построение оптимального расписания — NP-трудная задача в общем случае; list scheduling и critical-path scheduling — практические эвристики (см. временной анализ).

Связь с диаграммой Ганта в управлении проектами та же: ось времени + ресурсы.

---

Сравнение моделей

Модель	Память	Синхронизация	Реальный аналог
PRAM	Shared	Lock-step раунды	Теория
Shared memory + threads	Shared	Barriers, locks	OpenMP, pthreads
Message passing	Distributed	Send/recv	MPI
SPMD	Любая	Rank + collectives	MPI, CUDA grids
Dataflow	Потоки данных	Готовность операндов	TensorFlow graph (концептуально)

---

---

Parallel prefix sum на PRAM (CREW)

Задача: prefix[i] = sum(a[0..i]). Последовательно O(n); на PRAM — O(log n) раундов.

Upsweep / downsweep (упрощённо, n = степень 2):

Раунд 0: a[1]+=a[0], a[3]+=a[2], a[5]+=a[4] …   (пары)
Раунд 1: a[3]+=a[1], a[7]+=a[5] …               (расстояние 2)
…
Раунд log n: prefix готов

Каждый раунд — барьер (в OpenMP #pragma omp barrier между фазами). На GPU тот же паттерн — scan в CUDA Thrust/cub.

Связь с HPC: prefix sum — building block для сжатия, сортировки, sparse linear algebra.

---

Стоимость MPI collective (модель)

Грубая оценка для Allreduce размера m на p процессах:

T ≈ α · log p + β · m

• α — latency (сек на hop/раунд).
• β — 1/bandwidth.

Пример: α = 2 µs, β = 0,01 µs/байт, m = 8 B (один double), p = 1024:

T ≈ 2·10 + 0,08 ≈ 20 µs   (latency-dominated)

При m = 1 MB: T ≈ 20 + 10⁴ = ~10 ms — уже bandwidth. Batch мелкие reduction в один большой буфер.

---

Stencil на 2D torus

5-point Jacobi: каждая ячейка обменивается с 4 соседями. Логическая 2D mesh/torus топология совпадает с алгорitmом → nearest-neighbor обмен, O(1) hop на InfiniBand fat tree при хорошем mapping.

     [i-1,j]
[i,j-1]─[i,j]─[i,j+1]
     [i+1,j]

Rank (rx, ry) владеет блоком; halo — одна строка/столбец ghost cells. Инженерия, практика MPI.

---

Что дальше

• Граф алгоритма и матрица следования — формальная основа для расписания.
• Временной анализ — ранние/поздние сроки, минимум процессоров.
• Сети Петри — альтернативная модель конкуренции за ресурсы.

---