一筆書きとロードバランス

とある研究会で知ったことのメモ．



不均一なメッシュを均等に領域分割してノードに割り振ると，
各ノードが担当するメッシュが等しくなくロードバランスが良くない．
そこでなんとかメッシュ数が一定(計算負荷が一定)になるように領域分割したい．

そこでまず一筆書きについて考える．今

(1,2) (2,2) (3,2) (4,2)
(1,1) (2,1) (3,1) (4,1)

というグリッドがあるとする．これを一筆書きしたいとする．

それには，まず座標を二進数で表現し，先頭から交互に並べる．

それを十進数で書き直し，小さい順に並べる．

つまり
(4,2)→(100,010)→(100100)→36
(4,1)→(100,001)→(100001)→33
(3,2)→(011,010)→(001110)→14
(3,1)→(011,000)→(001010)→11
(2,2)→(010,010)→(001100)→12
(2,1)→(010,001)→(001001)→9
(1,2)→(001,010)→(000110)→6
(1,1)→(001,001)→(000011)→3
 となるので
(1,1)→(1,2)→(2,1)→(2,2)→(3,1)→(3,2)→(4,1)→(4,2)
と一筆書きすればよいことになる．
これを修正モートン順序則というらしい．

肝なのは，二進数で表現してシャッフルしているので，
x方向に二個進んでからyへ行くということ．
n進数で同じことをすると，x方向にn個進んでy方向へ行くことになるらしい．


以上のような一筆書きを不均一なメッシュに対して行い，
メッシュ数が一定になるようにノードに割り振ると良いらしい．
(一筆書きをしてから領域分割をしているので，メッシュが散らばらない）

不均一メッシュが激しく切り替わる場合にモートン順序則で領域を決定すると，
担当する領域が不安定になるらしい．
(通信をさけるにはドラスティックな領域変更は避けたいところ)

これを避けるには，ヒルベルト曲線を使うといいとか．


幾何学がこんなところで役に立つとは．．．