並列FFTアルゴリズム

なぜFFTを分散させると難しくなるのか

高速フーリエ変換（FFT）は1プロセス内であればO(N log N)で済む極めて効率の良いアルゴリズムです。しかし科学技術計算で扱う3次元格子は各軸1024〜8192点規模になることも珍しくなく、1台のメモリには収まりません。そこで格子を複数プロセスに分割し、分散環境でFFTを計算する必要が出てきます。

ここでの本質的な難しさは、FFTが「軸方向に閉じたデータ依存」を持つ点にあります。3次元FFTはX軸・Y軸・Z軸それぞれについて独立な1次元FFTの合成として計算できますが、ある軸に沿った1次元FFTを実行するには、その軸のデータ全体が1プロセスのメモリ上に連続して存在しなければなりません。格子をどの軸で分割しても、残りの軸方向には必ずデータがプロセスをまたいで散らばってしまいます。

分散転置というアプローチ

代表的な解法は次の3段構成です。

3次元分散FFT（Z-Y-X 格子、スラブ分割の例）

  1. 各プロセスが担当するZ軸方向にローカルFFTを実行
     （X, Y方向はプロセスをまたいで分割済み、Z方向はローカルに閉じている）

  2. 分散転置（all-to-all通信）
     データの分割軸をZ→Xに切り替える
     各プロセスは自分が持つデータの一部を全プロセスに送り、
     全プロセスから一部を受け取る

  3. 転置後の配置でX軸方向にローカルFFTを実行
     （同様にY軸についても転置とFFTを繰り返す）

この「ローカルFFT→転置→ローカルFFT」を軸の数だけ繰り返すのが分散FFTの標準形です。転置は単なるデータ移動であり浮動小数点演算を増やしませんが、ネットワーク帯域と遅延（レイテンシ）に直接依存するため、計算とは性質の異なるコストを持ち込みます。

all-to-all通信がボトルネックになる理由

転置の実体は集団通信のall-to-allです。プロセス数をPとすると、各プロセスは自分のデータをおよそP分の1ずつに分割し、残る全プロセスへ送り、全プロセスから受け取ります。通信ペア数はP×(P−1)のオーダーで増え、1メッセージあたりのサイズは総データ量をPで割った分だけ小さくなっていきます。

all-to-allのコスト傾向（概念）

  総通信量（全プロセス合計） ∝ N（データ量に比例、Pには依存しない）
  1プロセスあたりの送受信メッセージ数 ∝ P
  1メッセージあたりのサイズ ∝ N / P²

  → Pを増やすほどメッセージは小さく・多くなり、
     帯域より通信の立ち上がり遅延（レイテンシ）が支配的になっていく

計算量は演算資源を増やせば理屈の上では線形に近く縮みますが、通信は「小さなメッセージを大量に送る」形に近づくため、レイテンシに縛られて頭打ちになりやすいのです。これがFFTの弱スケーリングを難しくする核心であり、演算主体のアルゴリズム（例えば密行列積）と比べて並列化効率が伸びにくい理由でもあります。

分割方式の選択 ── スラブからピローへ

分散FFTの並列度は、格子をどう分割するかで大きく変わります。最も単純なスラブ分割（1次元分割、1軸だけをプロセス数で割る）は実装が容易な一方、並列度がその軸の格子点数を超えられません。格子が1024点なら、プロセス数も1024が上限です。

これに対しピロー分割（2次元分割、2軸を同時に分割）は、2軸それぞれを格子点数まで分割できるため、並列度の上限を格子点数の2乗のオーダーまで引き上げられ、より多いプロセス数まで有効に使えます。ただし転置の段数が増え、通信パターンも複雑になるため、実装と通信スケジューリングの難度は上がります。

分割方式と並列度の目安（格子サイズN×N×Nの場合）

  スラブ分割（1D）  : 最大プロセス数 ≈ N
  ピロー分割（2D）  : 最大プロセス数 ≈ N²

大規模系（数千〜数万プロセス）ではピロー分割が事実上の標準となっており、多くのHPC向けFFTライブラリがスラブとピローの両方、あるいはピローのみを提供する設計に移行しています。

科学技術計算での応用

分散FFTが実務で重要になる典型は、周期境界条件を持つ偏微分方程式をスペクトル法で解く場面です。

• 流体シミュレーション: 乱流の直接数値シミュレーション（DNS）では、非線形項の計算とポアソン方程式（圧力場を求める楕円型方程式）の求解にFFTを使い、微分演算を波数空間での積に置き換えて計算量を抑えます。
• 電磁気シミュレーション: プラズマ粒子法（Particle-in-Cell）における電場計算や、周期構造のマクスウェル方程式求解でも、ポアソン方程式を波数空間で解くためにFFTが使われます。

いずれの応用でも、時間発展の1ステップごとに複数回の3次元FFTを実行するため、転置通信のコストがシミュレーション全体の実行時間を左右します。格子解像度を上げるほど通信量が増える一方、利用可能なプロセス数にも限界があるため、通信を減らす分割方式の選択とネットワークトポロジに適した通信スケジューリングが、大規模科学技術計算の性能を決める実務上の焦点になっています。

まとめ

• 多次元FFTは軸ごとの1次元FFTに分解できるが、各軸のデータをローカルに揃えるための分散転置（all-to-all通信）が並列化の必須コストになる。
• 転置の通信量はプロセス数が増えるほどメッセージが細分化され、レイテンシに支配される領域に入りやすく、演算律速から通信律速への転換点が並列化効率の限界を決める。
• スラブ分割は実装が単純だが並列度が格子サイズに制限され、ピロー分割は並列度を平方のオーダーまで伸ばせる代わりに通信段数と実装難度が増す。
• 流体・電磁気シミュレーションのスペクトル法では、ポアソン方程式などの求解に毎ステップ複数回のFFTを要するため、転置通信の設計がシミュレーション全体の性能を左右する。