No Such Blog or Diary

依存関係に循環構造を持たせてレイジーに評価することでデータの走査を一回にする...　まあ，ありだよねと．レイジーな評価をするといろいろトリッキーなことができるんだなぁと改めて感心．ということで，人生もレイジーに評価すると何かいいことがあるかも．

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秒程度で，スピードアップは２倍程度らしい．

とにかくすごい．

SACSIS2005 のポスターセッションでグリチャレの優勝者が展示発表されていたので質問をしにいってみた．ポスターの内容は自由課題でやったことだったけど，関係ない規定課題の質問にも答えてもらえた．で，速さの秘訣はなんだったかというと，シーケンシャルプログラムが速いことらしい．Morton 順序のまま RLE を展開せず連結成分を塗り分けていくと．RLE を展開しないってのが結構効いてそうだなあ．ちなみに，ネットワーク部分は何を使ったのかとたずねたら Socket のみとの回答が（スレッドもなし）．そして当然のごとく，どこかのノードが落ちたらアウトな設計らしい．Ninf-G とかは使う気にはならなかったのかとたずねたら，使い方がわからなかったとの回答が．とにもかくにも，下手なものを使わずものすごく素直にプログラムするが一番速かったんだなぁと思いましたとさ．

今日の最後にはグリチャレ実行委員会による報告と表彰式もあった．報告は実行委員長である田浦先生が行ったのだが，なかなかお茶目で会場を沸かしていた．報告の最終ページが「怪我人:0, 死亡者:0」とかだったのは気にしない．んで，優勝者は二回ほど壇上に上がり（初級と上級），表彰状と奨励金と副賞をたんまりもらっていた．グリチャレは来年もやるみたいだから，来年こそは奨励金をもらいたいものだ．

SACSIS２００５の参加のため今日からつくばへ出張．高速バスの終点であるつくばセンターから南に１キロ弱の国際会議場で行われた．で，何を間違えたか会議場が北にあると思い込み，少々道に迷ってみたり．でも，平木先生のEFLOPS/Tbps の話が適当に面白かったので気にしない．そのあとホテルまで５キロ弱歩いたけれど気にしない．あー，疲れた．

輪講発表用のスライド作成が一向に進まない．例を何パターンか導出して時間を食いすぎた．あと３４時間でスライドと資料をあげなければ．ちょっとやば目だ．

輪講の資料に提案する手法を適用する例を載せようと思うのだが，いかんせん複雑すぎる．問題は単純だけど効率化しにくい形なので導出過程が複雑にならざるを得ない．でもまあいいか．どうせ簡単なのでも分からんと思われるから．とりあえずさっさとスライドを作らないとやばいかも．