MPIと集団通信

MPIの二層構造 ── point-to-pointと集団通信

MPI（Message Passing Interface）は、共有メモリを持たない複数プロセス間でデータをやり取りするための標準規格です。通信は大きく2層に分かれます。point-to-point通信（MPI_Send / MPI_Recv）は1対1でメッセージを送受信する最小単位で、送信先・タグ・データ型を指定して明示的にペアで呼び出します。一方、**集団通信（collective communication）**はコミュニケータに属する全プロセスが同じ呼び出しに参加する操作で、MPI_Bcast や MPI_Allreduce のように全員が同じ関数を呼んで初めて完了します。

集団通信の基本操作

代表的な集団通信は、データの流れる向きと集約の有無で整理できます。

AllreduceはReduceとBroadcastを合成した操作に見えますが、実装上は両者を素直に連結するより効率的なアルゴリズムが使われます。この点が集団通信アルゴリズムを学ぶ核心です。

通信アルゴリズムと計算量

集団通信の実測性能は、メッセージサイズとプロセス数の組み合わせでどのアルゴリズムが選ばれるかに左右されます。ここではプロセス数をP、転送する総データ量をNとして、代表的な3つの構造を見ます。

二分木（binary tree）アルゴリズム

Broadcastの基本形です。ルートプロセスがまず半分のプロセスへデータを送り、受け取った側がさらに半分へ転送する、という具合に段数ごとに参加者が倍増します。

二分木Broadcastの段数（P個のプロセス）

  段1: 1 → 1  （合計2プロセスがデータを持つ）
  段2: 2 → 2  （合計4プロセスがデータを持つ）
  段k: 2^(k-1) → 2^(k-1)

  全プロセスに行き渡るまでの段数 = log2(P)
  各段の通信は並列に行われるため、レイテンシ支配の項は log2(P) に比例

木構造の利点は段数がPの対数で済むことです。ただし各段で送るデータ量はNのままなので、大きなメッセージでは帯域幅（bandwidth）支配の項が効いてきます。

リング（ring）アルゴリズム ── Allreduceの主力

大きなメッセージのAllreduceでは、リングアルゴリズムが広く使われます。P個のプロセスを論理的な環状に並べ、データをP個のチャンクに分割し、隣接プロセスとだけ通信します。処理は2フェーズです。

Ring-Allreduceの2フェーズ（P プロセス、データを P チャンクに分割）

フェーズ1: Reduce-Scatter
  P-1 ステップかけて、各プロセスが隣から部分和を受け取り自分のチャンクに足し込む
  ステップ終了後、各プロセスは「担当チャンクの全プロセス分の合計」を1つずつ保持

フェーズ2: Allgather
  P-1 ステップかけて、完成した合計チャンクをリング上に回して全員が全チャンクを取得

合計ステップ数 = 2(P-1)
1プロセスあたりの送受信データ量 = 2 × (P-1)/P × N  ≒ 2N（Pが大きいとき）

リングアルゴリズムの本質は、1プロセスが送受信するデータ量がプロセス数Pにほぼ依存せず一定になる点です。木構造がレイテンシ（段数）をlog2(P)に抑えるのに対し、リングは帯域幅の使用効率を最大化します。このため、メッセージが大きく帯域幅がボトルネックになる場面（大規模数値シミュレーションの領域分割境界データ交換や、分散学習の勾配同期）ではリング型が有利です。

バタフライ（butterfly / recursive doubling）アルゴリズム

Allreduceの別解として、**再帰的倍加（recursive doubling）**とも呼ばれるバタフライ型があります。プロセス数がPのとき、通信相手との距離を1、2、4…と倍にしながらlog2(P)ステップで全交換を終えます。

バタフライAllreduceの段数（P = 2^m の場合）

  段1: 距離1のペアと全データ交換・演算
  段2: 距離2のペアと全データ交換・演算
  段k: 距離2^(k-1) のペアと全データ交換・演算

  段数 = log2(P)
  各段で送受信するデータ量 = N（全量、分割しない）
  総通信量（1プロセスあたり）= N × log2(P)

バタフライ型は段数が少なくレイテンシに強い一方、各段で送るデータ量を分割しないため、メッセージが大きいと総通信量がlog2(P)倍に膨らみます。したがって小さいメッセージ・多プロセスではバタフライ、大きいメッセージではリングが有利、という切り替えが成り立ちます。

ネットワークトポロジとの関係

集団通信アルゴリズムの理論段数はあくまで論理構造上の値で、実機性能は物理的なネットワークトポロジと接続段数（ホップ数）に強く依存します。

重要なのは、論理的なアルゴリズム構造（リング・木・バタフライ）と物理トポロジの接続関係が一致するほど性能が出るという点です。例えばトーラス型のスーパーコンピュータでは、MPIランクの物理ノードへの割り当て（ランク配置、rank mapping）をトーラスの隣接関係に合わせることで、論理リングの1ステップが物理的にも1ホップで済み、中継によるレイテンシ増加を避けられます。逆に割り当てが乱雑だと、論理的には隣接のはずのステップが物理的には何ホップも離れ、通信段数の理論値どおりの性能が出ません。

まとめ

• MPIはpoint-to-point（Send/Recvのペア通信）と集団通信（全プロセス参加のBroadcast/Reduce/Allreduce/Scatter/Gather）の二層で構成される。
• 集団通信の内部実装は二分木・リング・バタフライ（再帰的倍加）に大別され、段数（レイテンシ項）と1プロセスあたり通信量（帯域項）のトレードオフが異なる。
• リングはプロセス数によらず通信量がほぼ一定で大メッセージに強く、バタフライは段数が少なくレイテンシに強いが通信量がlog2(P)倍に増える。
• 実機性能はネットワークトポロジ（ファットツリー・トーラス等）とアルゴリズムの論理構造がどれだけ一致するかに左右され、ランク配置の設計次第で理論段数どおりの性能が出るかが決まる。