科学シミュレーションの負荷分散

なぜ負荷が「均等」でなくなるのか

格子ベースの数値シミュレーションを台数分のプロセスに割り当てるとき、最も単純な戦略は計算領域を格子点数で等分することです。しかし、この前提が崩れる場面が2つあります。

第一に適応格子細分化（Adaptive Mesh Refinement, AMR）です。衝撃波・燃焼面・重力崩壊など、解の変化が急峻な領域だけを細かい格子で解像し、滑らかな領域は粗い格子のまま残すことで計算量を節約します。この結果、格子は空間的に不均一な密度を持ち、しかも現象が移動すれば細分化領域そのものが時々刻々と動きます。

第二に粒子法（分子動力学、N体シミュレーション、SPH等）です。空間を固定領域で分割しても、粒子は時間とともに移動し、ある領域に粒子が密集すればそのプロセスの計算量だけが跳ね上がります。格子法と異なり「担当領域の計算量」がデータの物理的な移動によって刻々と変わるのが特徴です。

空間充填曲線によるパーティショニング

不均一な負荷を高速かつ局所性を保って分割する代表的手法が、**空間充填曲線（space-filling curve）**を使ったパーティショニングです。代表例はモートン順序（Z-order curve）とヒルベルト曲線（Hilbert curve）です。

考え方は次の通りです。多次元空間上に散らばる格子セルや粒子を、まず1次元の順序に並べ替えます。空間充填曲線は多次元座標を1本の連続した曲線でなぞる順序付けで、曲線上で近い位置にある要素は元の多次元空間でも近い位置にある、という局所性保存の性質を持ちます。

パーティショニングの手順（概念）

1. 各セル（または粒子）に「作業コスト」を割り当てる
   （AMRなら細分化レベルに応じた計算量、粒子法なら近傍粒子数など）
2. 空間充填曲線に沿って全セルを1次元に並べる
   （曲線上の位置を表すキー = モートンキー or ヒルベルトインデックス）
3. 1次元に並んだコストの累積和を計算し、
   総コストを P（プロセス数）等分する境界点を見つける
4. 曲線上で連続する区間を1つのプロセスに割り当てる

累積和を等分するだけなので、この分割は計算量がセル数に対してほぼ線形で済み、AMRの再細分化や粒子の移動のたびに再実行しても実用的な速さで収まります。

ヒルベルト曲線がモートン順序より好まれる理由は、局所性の保存性能の違いです。

静的分割と動的再分割のトレードオフ

負荷分散の設計における最大の分岐点は、分割を計算開始時に一度だけ決めるか（静的分割）、**実行中に負荷の偏りを検知して分割をやり直すか（動的再分割）**です。

静的分割は、初期状態の負荷分布に基づいて一度だけパーティショニングを行い、以降は固定します。再分割のコストはゼロですが、AMRで細分化領域が移動したり、粒子が偏在するように再配置されたりすると、初期に均等だった負荷が実行中にどんどん偏っていきます。

動的再分割は、実行中に各プロセスの負荷（計算時間や担当セル数）を監視し、偏りが一定の閾値を超えたら分割をやり直します。これは負荷の追従性を得る代わりに、次のコストを支払います。

動的再分割が発生させるコスト

1. 負荷の計測・集約（各プロセスの負荷情報を集める通信）
2. 新しい分割の計算（空間充填曲線の再構築など）
3. データ移行（migration）
   → 担当領域が変わったセル・粒子の実体データを
     旧プロセスから新プロセスへ転送する
   → 格子法ならセル変数一式、粒子法なら粒子の位置・速度・
     内部状態すべてが移動対象になる

とりわけ3番目のデータ移行は、境界のゴースト層交換のような「毎ステップ発生する小さな通信」とは性質が異なり、担当領域全体が入れ替わる大規模な一括通信になります。再分割を毎ステップ行えば追従性は上がりますが移行コストが支配的になり、逆に頻度を下げすぎれば偏りを溜め込んだまま計算を続けることになります。

この判断のために、多くの実装は再分割の要否そのものを推定するコスト関数を持ちます。「現在の負荷の分散」と「再分割にかかる推定コスト（主にデータ移行量に比例）」を比較し、再分割で得られる実行時間の短縮が移行コストを上回ると推定できた場合にのみ再分割を実行する、という判断です。

通信最小化との両立

負荷分散の目的関数を「計算量の均等化」だけに絞ると、パーティショニングの形状が細切れになり、境界面積（=通信量）が増えるという副作用が生じえます。実務では次の2つの目的関数を同時に扱う必要があります。

• 計算負荷の均等化: 最大負荷プロセスの実行時間を最小化する。
• 通信量の最小化: 担当領域の境界（表面積）を小さく保ち、隣接プロセス数も抑える。

空間充填曲線による分割は、コスト等分を優先しつつ曲線の局所性でこの2つをある程度両立させる設計です。これに対しグラフパーティショニング（計算セルをノード、隣接関係をエッジとみなし、エッジカット数を最小化しながらノード重みを均等分割する手法）は、通信量（エッジカット）を明示的な最小化対象にできる代わりに、分割自体の計算コストが高くつきます。空間充填曲線は「再計算が速いので高頻度の動的再分割に向く」、グラフパーティショニングは「分割の質は高いが再分割頻度が低い局面に向く」という住み分けが実務上の目安です。

まとめ

• AMRの細分化領域の移動や粒子法の粒子偏在により、計算負荷は時空間的に偏り続けるため、静的な等分割だけでは特定プロセスが全体の律速要因になる。
• 空間充填曲線（モートン順序・ヒルベルト曲線）は、多次元の不均一な負荷を1次元の累積和として高速に等分割しつつ、曲線の局所性によって境界通信の増加をある程度抑える手法である。
• 静的分割（再分割コストゼロだが偏りに弱い）と動的再分割（偏りに追従できるがデータ移行コストを伴う）は、偏りの進行速度と移行コストの見積もりで使い分ける。
• 負荷の均等化と通信量の最小化は独立した目的関数であり、空間充填曲線とグラフパーティショニングは再分割の速さと分割の質のどちらを優先するかで住み分ける。