Message Passing: MPI

1993: 14 месяцев, которые объединили суперкомпьютеры

До MPI параллельное программирование напоминало разработку под разные платформы без единого SDK - только хуже. Cray T3D, Intel Paragon, nCUBE/2 - три машины, три несовместимых API, три параллельных вселенных. Переносимость кода между суперкомпьютерами не существовала как концепция. Апрель 1992, Williamsburg, Virginia: первая встреча того, что станет MPI Forum. 60 организаций, 14 месяцев работы. MPI 1.0 вышел в мае 1994. Через год - доминировал. Через 30 - все 500 быстрейших компьютеров планеты работают на MPI. Стандарт описывает интерфейс, не реализацию - поэтому Open MPI, MPICH, Cray MPI, IBM Spectrum MPI оптимизированы под своё железо и говорят одним языком.

MPI до сих пор - стандарт HPC. CERN (расчёты LHC), NOAA (прогнозы WRF), NASA (CFD-симуляции), DeepMind AlphaFold2 - все используют MPI или MPI-совместимые библиотеки. PyTorch NCCL для distributed training реализует те же collective communication паттерны.

MPI_Send и MPI_Recv: блокирующий обмен

1993 год. Конференц-зал в Техасе. Представители 60 организаций - IBM, Intel, Cray, университеты со всего мира - садятся за стол с одной целью: единый стандарт для параллельных вычислений. До этого момента каждый суперкомпьютер говорил на собственном диалекте. Cray T3D - один API, Intel Paragon - другой, nCUBE/2 - третий. Переносимость кода между машинами не существовала как концепция. MPI Forum работал 14 месяцев. Результат живёт в каждом из топ-500 суперкомпьютеров мира - 30 лет спустя.

В основе MPI - модель с распределённой памятью. Каждый процесс в изоляции: собственный адресный пространство, никакого общего heap. Единственный способ обменяться данными - явный обмен сообщениями. Это не ограничение, а дизайн-решение: масштабируется от 4 ядер до 4 миллионов (IBM Sequoia достигал 1.6M ядер).

MPI_Send - блокирующая операция. Вызов не вернётся пока данные не скопированы в системный буфер (или не приняты получателем - зависит от реализации и размера сообщения). Для малых сообщений (< 8 KB) - eager protocol: данные копируются в буфер немедленно, send возвращается. Для больших - rendezvous protocol: send блокируется до handshake с получателем. Эта невидимая разница порождает классы багов, которые не воспроизводятся на тестовых данных.

Неблокирующие MPI_Isend / MPI_Irecv инициируют операцию и немедленно возвращают request-handle. Данные передаются в фоне, пока CPU считает. Классический паттерн overlap computation and communication: пока граничные клетки отправляются соседним процессам, внутренние клетки уже обрабатываются. В климатических моделях MPAS-Ocean (используется Национальным центром атмосферных исследований США) это даёт 40% ускорения на тысячах ядер.

Bcast, Reduce, Scatter, Gather: дерево вместо цепочки

Задача: вычислить сумму миллиарда чисел на 1000 процессорах. Каждый считает свои миллион - локальную сумму. Дальше нужно собрать 1000 частичных сумм в одну глобальную. Через MPI_Send/Recv - 999 последовательных операций. Через MPI_Reduce - дерево редукции с глубиной $\log_2(1000) \approx 10$. Разрыв в 100 раз по числу шагов.

Дерево редукции - это не абстракция. Open MPI реализует несколько топологий: binomial tree (оптимально для latency-bound), binary tree (для bandwidth-bound). Для GPU-кластеров NCCL (библиотека NVIDIA) реализует Ring-Allreduce - именно этот алгоритм стоит за distributed training в PyTorch DDP. Каждая итерация backward pass при обучении BERT - это Allreduce градиентов по всем GPU. Без MPI-семантики под капотом - никакого масштабируемого обучения LLM.

MPI_Allreduce = MPI_Reduce + MPI_Bcast, объединённые в одну оптимизированную операцию. Результат доступен всем процессам, не только root. В ML-тренинге это критично: все GPU должны получить усреднённый градиент для синхронного обновления весов.

MPI_Scatter и MPI_Gather - инверсия друг друга. Scatter: root разрезает массив на N равных частей и раздаёт по одной каждому процессу. Gather: собирает куски обратно. Вместе они реализуют fork-join параллелизм - паттерн, который MapReduce, Apache Spark и Hadoop унаследовали у MPI в 2000-х. Scatter в научных вычислениях, Gather в сборке результатов - базовый ритм любого data-parallel кода.

MPI_Bcast - broadcast одного значения всем процессам. Применяется когда root загружает конфигурацию или гиперпараметры и должен синхронизировать их перед стартом. В DeepSpeed (Microsoft, инфраструктура обучения GPT-4 class моделей) MPI_Bcast используется при инициализации весов - чтобы все GPU-ноды начали с идентичного состояния.

MPI Deadlock: когда все ждут всех

Два процесса. Оба хотят обменяться данными. Оба вызывают MPI_Send первым. MPI_Send с rendezvous protocol блокируется - никто не вызвал MPI_Recv. Система застывает. Навсегда. Не гипотетический сценарий - одна из самых частых причин зависания реальных MPI-программ, особенно при больших размерах сообщений.

MPI_Sendrecv - атомарная двусторонняя операция. Реализация выстраивает send и recv так, чтобы не было circular wait. Та же логика, что в алгоритме банкира Дейкстры - только встроена в runtime MPI, без необходимости думать об упорядочивании вручную.

Коварный случай: deadlock появляется только при больших N из-за разницы eager/rendezvous protocol. Программа работает на тестах с малыми массивами и падает в продакшне. Инструменты обнаружения: MUST (Marmot MPI correctness tool) или Intel Trace Analyzer - перехватывают MPI-вызовы и строят граф ожидания.

Коллективные операции - MPI_Bcast, MPI_Reduce, MPI_Barrier - не дедлочатся, если вызваны на всех процессах коммуникатора. Правило простое: коллективная операция обязана быть вызвана на каждом процессе группы. Если хоть один процесс пропустит MPI_Barrier - остальные ждут вечно. Условные вызовы коллективных операций (`if (rank == 0) MPI_Barrier(...)`) - классический антипаттерн.

MPI_Barrier - синхронизационная точка: все процессы ждут пока последний не достигнет барьера. Аналог pthread_barrier_wait для distributed-memory среды. Полезен для разделения фаз вычислений, но каждый барьер - это latency самого медленного процесса. Лишние барьеры убивают масштабируемость.

Итог

• MPI - стандарт message passing для distributed-memory систем. 30 лет, 500 топ-суперкомпьютеров.
• MPI_Send/Recv - блокирующий point-to-point. Малые сообщения: eager (буфер). Большие: rendezvous (handshake с получателем).
• MPI_Isend/Irecv - неблокирующие. Overlap communication и computation - ключ к масштабируемости.
• Коллективные операции (Bcast, Reduce, Scatter, Gather, Allreduce) - дерево/ring топологии вместо цепочки. Ring-Allreduce в PyTorch DDP.
• MPI-deadlock: circular blocking send. Решение - MPI_Sendrecv или упорядочивание операций.
• Коллективная операция обязана быть вызвана на ВСЕХ процессах коммуникатора - иначе deadlock.

Связи с другими темами

MPI - фундамент HPC и распределённых вычислений. Понимание этих тем даёт полную картину параллелизма.

• Actor Model (Erlang, Akka) — Высокоуровневая абстракция message passing с те же принципами изоляции
• CSP и каналы (Go) — Альтернативный формализм для message passing с синхронными каналами
• Консенсус: Paxos и Raft — Распределённые протоколы строятся поверх message passing примитивов
• Deadlock, Livelock, Starvation — MPI-deadlock - специфика distributed-memory среды, те же причины

Вопросы для размышления

• PyTorch DDP использует Ring-Allreduce для синхронизации градиентов - алгоритм из мира MPI. При обучении LLaMA-3 на 2048 GPU каждая итерация backward pass требует Allreduce всех параметров (70B float16 = 140 GB). Какие трейдоффы возникают между частотой синхронизации (каждый batch против gradient accumulation на N шагов) и качеством сходимости модели?

Связанные уроки

• par-05 — Разделяемая память - антипод message passing
• par-04 — MPI-deadlock - частный случай классического deadlock
• par-07 — Actor Model строится на тех же принципах message passing
• ds-01-intro — MPI - основа для понимания распределённых систем
• ds-03-consensus — Paxos/Raft используют collective communication паттерны
• dist-03-fallacies
• net-53-distributed-intro