グラフ分割とメッシュ分割

なぜメッシュ分割がグラフ分割になるのか

有限要素法や有限体積法で使う非構造メッシュを並列計算するには、要素（またはノード）をプロセスへ割り当てる必要があります。規則格子なら座標で機械的に短冊やブロックに切れますが、非構造メッシュは要素の隣接関係が座標から自明でないため、この割り当てをグラフ分割問題として定式化します。

対応づけは単純です。計算単位（要素やメッシュ節点）をグラフのノードに、計算で値を交換し合う隣接関係をエッジに写します。すると「メッシュをP個のプロセスへ分ける」ことは「グラフのノードをP個の部分集合に分ける」ことに一致します。この抽象化のおかげで、規則格子・非構造メッシュ・疎行列（疎行列の格納形式と演算 の隣接構造）を、同じ分割アルゴリズムで扱えるようになります。

k-way分割とエッジカット最小化の定式化

グラフ G=(V,E) を考えます。各ノード v は計算コストを表す重み w(v) を持ち、各エッジは通信量を表す重みを持てます。これをk個の部分集合 {V1,...,Vk} に、重複なく分割します。満たすべき条件は次の2つです。

• バランス制約: 各部分集合の重み合計が、ほぼ均等になること。理想は総重み/k ですが、厳密な均等は難しいため許容不均衡率 ε を設け、どの部分集合も (1+ε)×平均以下に収める、という緩和条件を課すのが一般的です。
• 目的関数: 異なる部分集合に端点を持つエッジ（カットエッジ）の重み合計、すなわちエッジカットを最小化すること。

このように部分集合数 k を任意に指定して同時に分ける定式化をk-way分割と呼びます。実装上は「2分割を再帰的にlog k回繰り返す（再帰二分）」方法と、「最初からk個へ直接分ける（ダイレクトk-way）」方法があります。再帰二分は各段が独立で単純ですが、段ごとの局所最適が積み重なり全体最適から離れやすい欠点があります。ダイレクトk-wayはk個の部分集合の境界を同時に最適化できるため、通常こちらの方が高品質なカットを得ます。

多層グラフ分割（METISの中核アルゴリズム）

METISに代表される現代のグラフ分割器は、多層グラフ分割（multilevel graph partitioning）という3段構成を採ります。巨大なグラフを直接分割せず、いったん小さく畳んでから分割し、元のサイズへ戻す、という発想です。

横にスクロール

多層グラフ分割の3フェーズ

1. 粗視化（coarsening）
   隣接ノードをマッチングでペアにし、1つのノードへ統合する。
   統合ノードの重み = 元2ノードの重みの和、
   統合エッジの重み = まとめられたエッジ重みの和。
   これを数十回繰り返し、数百ノード程度まで段階的に縮小する。

2. 初期分割（initial partitioning）
   最小まで縮んだグラフは十分小さいので、
   ここで初めて k-way 分割を計算する。
   小規模なので多少重いアルゴリズムを使っても速い。

3. 詳細化を伴う逆写像（uncoarsening + refinement）
   粗視化を逆にたどり、統合したノードを1段ずつ展開する。
   各段で境界ノードを隣の部分集合へ移す局所改善
   （KL/FM 系のヒューリスティック）を適用し、
   カットとバランスを詰め直しながら元のサイズへ戻す。

このアプローチが効く理由は2つあります。第一に、粗いグラフ上での1ノードの移動が元グラフの多数ノードの一括移動に相当するため、局所改善だけでは越えられない大域的な谷を、粗い階層でまたいで探索できます。第二に、初期分割を小さいグラフに対してだけ行うので、全体の計算量がノード数・エッジ数に対してほぼ線形に収まります。空間充填曲線ほどではないものの、数百万ノードを秒単位で分割できる速度は、この線形性から来ています。

エッジカットは通信量の近似にすぎない

多層グラフ分割は「エッジカット」を最小化しますが、実際の並列性能を決めるのはエッジカットそのものではありません。ここに理論と実測の乖離が生まれます。

第一に、通信は本数ではなくメッセージ回数とレイテンシに強く影響されます。2つの部分集合の間でカットエッジが100本あっても、それらが1回の通信にまとめられるなら、コストは1メッセージ分です。したがって効くのは通信相手（隣接部分集合）の数であり、これはエッジカットとは別の量です。第二に、バリア同期のもとでは全体の所要時間は最も重い1プロセスで決まるため、総エッジカットより1プロセスあたりの最大通信量が律速になります。

さらに、標準のグラフ分割はエッジを「2ノードを結ぶ辺」としてしか表せないため、1つのデータが3プロセス以上で共有される状況（1つの節点が複数部分領域の境界に接する等）の通信量を正確に数えられません。これを厳密に扱うのがハイパーグラフ分割で、1本のハイパーエッジが任意個数のノードを束ねられます。ハイパーグラフのカット（何個の部分集合にまたがったか）は通信ボリュームを正しく数えられる代わりに、分割の計算コストはグラフ分割より重くなります。実務では「まず高速なグラフ分割（METIS系）で足りるか試し、通信が支配的で相手数の最適化が必要な場面でハイパーグラフ分割を検討する」のが定石です。

静的分割としての位置づけ

本記事が扱うのは、計算開始前に一度だけ質の高い分割を作る静的分割です。多層グラフ分割は高品質なカットを出せる反面、空間充填曲線による分割ほど再計算が軽くないため、科学シミュレーションの負荷分散 で扱う動的再分割（実行中に負荷が偏るたびに分割し直す）には必ずしも向きません。負荷分布が時間変化しない、または変化が遅い問題では、初期に一度だけ念入りにグラフ分割してカットを最小化しておくのが最も費用対効果が高くなります。逆に負荷が刻々と動く問題では、分割の質を多少犠牲にしても再分割の速い手法（空間充填曲線）や、前回の分割からの差分を小さく保つ並列版分割器（ParMETIS等）が選ばれます。

まとめ

• メッシュ分割は、計算単位をノード・データ交換をエッジとみなすことでグラフのk-way分割へ抽象化でき、規則格子・非構造メッシュ・疎行列を同じアルゴリズムで扱えるようになる。
• 分割の目的はバランス制約（ノード重みの均等化＝負荷分散）を守りつつエッジカット（＝通信量）を最小化することだが、この定式化はNP困難である。
• METISに代表される多層グラフ分割は、粗視化で畳んで小さくしてから分割し、KL/FMの局所改善を伴いながら展開することで、ほぼ線形時間かつ高品質な近似解を得る。
• エッジカットは通信の本数を数えるだけで、メッセージ回数・通信相手数・最大通信量という真に効く量とはずれる。通信ボリューム目的やハイパーグラフ分割はこの乖離を埋める手段であり、質の高い静的分割として動的再分割とは役割を分ける。