No Such Blog or Diary

よくわからん．IEEE の Style に従えといわれても LaTeX のスタイルファイル見つからないし．ガイドラインに沿っていれば細かいことは気にしないということだろうか...　細かいこと気にしないでさっさと投げることにしよう．

宣言どおり来年も Grid Challenge が行われるらしい．前回の問題はスケジューリング云々よりも如何にシーケンシャル部分を速くするか，ファイルのキャッシュをうまく効かせられるかにかかっていたのだけど，来年の問題はグラフの分割の最適化問題ということでこのウェイトが変わることを期待．とはいえ，シーケンシャルがある程度速いことは前提であるけれど…　このシーケンシャルの速度差をアルゴリズムでカバーする余地がありそうな気がする．やるとすればGAで新世代の生成を farmer/worker で投げてやるってのが一番シンプルかな．どっかで聞いた気がするけど…　交叉や判定なんかを調節すれば何とかなるのかも．でも，やっぱ離散最適化の手法でどうにかできてしまうことを期待したいなぁ．

scan を機械的に build form にもっていったら型がうまくつかず...　ああ，面倒．別のルートで変形してみるか．

オートマトンの話が出たときにふと思い出したので．問題の確認をば．これは1957年頃に Myhill によって提起された問題で，内容は以下のとおり．

とりあえず兵士が一列に並んでいて，端以外の兵士は全部同じである．右端の兵士を将軍として，将軍が時刻 t = 0 に隣の兵士に射撃命令を下す．各兵士は有限の状態（記憶）を持っており，時刻 t における両隣の兵士の状態によって自身の時刻 t+1 の状態を決定する．ただし，初めは待機状態にいるものとする．これらの条件の下で，全兵士がある時刻 T において一斉にある特定の状態（射撃状態）に移行するように，兵士たちの状態遷移関数を構成せよ．

この問題の解は，兵士の人数を n とすると最小時間である 2n-2 （伝令が往復する）の解が存在し，87年に Mazoyer が 6 状態の最小時間解を与えている: Mazoyer. A six-state minimal time solution to the firing squad synchronization problem: Theoretical Computer Science, Vol. 50, Issue 2, pp. 183-238, 1987.

並列プロセッサの同期とか生物細胞の成長同期とかの応用問題があるらしい．

scan の実装を縦横順番にやらずブロックで同時に通信・計算するようにしたらだいぶ速くなった．予想通りの出来でよいかもしれない．

論文の英訳して寝ようと思います．