METISで領域分割する の続きです。
概要
- METISで空間分割する際に重み付けを行います
- 重み付けを行うことで分割をある程度制御出来ます
- 細かいことを気にしなければ手元では使えてるよというサンプルです
- 詳細な指定は公式マニュアルを見ることをおすすめします
例1：体積で重み付けする
仮に「計算量がセルの体積に比例する」ような計算手法があったとします。この場合、セル数を基準に分割するだけでは各rankの計算量が均等になるとは限らないので並列処理してもいずれかのrankが律速になります。このような対象では体積に応じた重みをnodeに指定することで適切に分割出来る可能性があります。
例として、適当な非構造格子を考えます。例によってこちらで作成した格子です。
前回と同じくgpmetisに渡すデータを作成します。ほぼ同じですが、重みの情報を追加しています。
graph_volume_weighted.dat
912 1325 010 ←総node数、総edge数、重み付けの種類
23 53 97 100 ←node 1の重みは23。node 53、97、100に隣接する
31 25 69 ←node 2の重みは31。node 25、69に隣接する...
パラメータの意味：
- 010：3つのパラメータのON/OFFを0/1で示しています。先頭からvertex sizes、vertex weights、edge weightsです。ここではnodeに重みを設定したいので2つ目のvertex weightsを1にします。
- nodeの重み：整数で指定します。今回は体積Vを使用したいので適当に V[m3]×10^9 として整数にキャストした値を使用しました。これは指定した重みがV[mm3]オーダーでの指標となることを期待しています。
作成したデータをgpmetisに渡し、5分割してもらいます。
gpmetis graph_volume_weighted.dat 5
返ってくるデータの書式は重みの有無に関わらず同じです。rankの割り当てが記述されているので最初の非構造格子に適用します。
graph_volume_weighted.part.5
4 ← cell 1はrank 4
1 ← cell 2はrank 1
3 ← cell 3はrank 3...
これを元にrank分けすると以下のようになります。右は参考までに重み無しでの結果です。
これだけだと何が変わったのかよく分かりません。
どの程度均等に分割されたかセル数と体積の観点から確認してみます。
| Rank | 0 | 1 | 2 | 3 | 4 | |
| 重み有り | Vol[%] | 20.13 | 20.05 | 19.49 | 20.22 | 20.12 |
| Cell[%] | 22.59 | 23.36 | 16.34 | 16.67 | 21.05 | |
| 重み無し | Vol[%] | 16.67 | 17.79 | 21.13 | 21.21 | 23.20 |
| Cell[%] | 19.52 | 20.39 | 20.07 | 19.74 | 20.29 |
体積に応じた重みを指定することで体積がほぼ均等に分割されていることが確認出来ました。反面セル数はバラつきが大きくなっています。
例2：複数のセルを塊として扱いながら分割する
次のような問題設定を考えます：
- 複数のセルを塊(ブロック)として処理する計算手法を並列化したい
- ブロックに属さない孤立したセルがある
具体的には以下のような問題です。白いセルはどのブロックにも属さない孤立したセルであることを表しています。
計算量が同程度になるようにこれらを2分割したい場合、次のような分け方が考えられます。
このような問題設定にも重み付けで対応することが出来ます。
実際にやってみます。下の図では非構造格子にブロックが定義され色分けされています。ここでも白いセルはどのブロックにも属さず孤立していることを表します。
この情報をMETISに渡すためには、各ブロックにそれが包含するセル数に応じた重みを与えれば良さそうです(計算量がセル数に依存する場合)。さらに各ブロックをnode 1, 2,...と数え、最後に孤立した各セルにもnode番号を割り振ります。
Block 1 ←node 1
Block 2 ←node 2
...
Block n ←node n
Isolated cell 1 ←node n+1
...
Isolated cell m ←node n+m
gpmetisに渡すファイルは次のようになります。
graph_block_weighted.dat
38 52 010 ←総node数、総edge数、重み付けの種類
38 2 ←node 1の重みは38(セル)。node 2(=block 2)に隣接する...
38 23 28 ←node nの重みは38(セル)。node 23、28に隣接する
1 15 14 27 ←node n+1の重みは1(セル)。node 15、14、27に隣接する
...
1 21 ←node n+mの重みは1(セル)。node 21に隣接する
ここでは4分割してもらいます。
gpmetis graph_block_weighted.dat 4
返ってきた結果でrank分けしてみます。
| Rank | 0 | 1 | 2 | 3 |
| Cell[%] | 25.00 | 25.00 | 25.00 | 25.00 |
綺麗に4等分してくれました！
