グリチャレ報告

SACSIS2005 の参加動機であるグリチャレ報告会を見てきた．

どうやら速かったチームは morton オーダーをそのまま，RLEを展開せずに使っていたらしい．ひとつのセルの左と上の連結をチェックしつつ色を塗っていき，上と左が別の色だったら同一の色とするためリンクをはる．大きなブロックをいっぺんに処理するのが基本らしい．

優勝者のプログラムは，そこらへんを処理するコードを吐くプログラムを作って生成したらしい．あと，さらに重要なのが NFS で，全てのプロセスがいっぺんにファイルを読みに行ったら NFS がボトルネックになることは明らか．できるだけローカルの上にファイルをキャッシュしておいて，二回目に走らせるときにそのキャッシュを使うようにすべきらしい．ただ，これをやろうと思うと毎回同じファイルをとくような静的割り当てをしておかないとだめだろうなと．優勝者のプログラムは割り当てを LP を解いて静的に求めていたらしく，キャッシュを有効に活用できていたみたい．

ちなみにLPは，

C(i) : クラスタ i の動作周波数の和
f(d) : d の立っている bit に対応するクラスタに存在するファイルの数
       （たとえば，f(10) はクラスタ 1 と 3 にマスタとレプリカ１つがあるファイルの総数）
w(i,d) : クラスタ i の d （上記）であるファイルの割り当て数
T(i) = ∑(d=0..511) w(i,d) / C(i) : クラスタ i の計算時間

として，クラスタ全体の計算時間を最小化する．

min. max T(i)
s.t. ∑(i=0..8) w(i,d) = f(d)    (ファイル数の制限)

実際にこの LP を解くには，次の小問題を i = 0..8 に対して9個解き，その最小値の解を使う．

min. T(i)
s.t. ∑(i=0..8) w(i,d) = f(d)    (ファイル数の制限)
     T(i) >= T(j)               (クラスタ i が一番遅い)

この割り当ての決定は 1/100秒程度で，スピードアップは２倍程度らしい．

とにかくすごい．