読者です 読者をやめる 読者になる 読者になる

Hack the Cell 終了

Program

結果としては 98.71 …ってなんかもう少し速かったと (98.88) 思うんだけどなんかほんの少し遅いの出したかなー。まぁもっと大袈裟に負けてる感が強いのでそのくらいの差は関係ないだろうというか、そもそも提出した際のメールに添付してなかったらしく期限切れで出したので失格だよボケ! とかそんなこんな。まぁ kik さんはやはりすごかったのでした。

もはや動作確認もできないけど提出物。

http://shinh.skr.jp/tmp/hamaji2.tgz

ORIGNAL:         sum=3c927c56, 293506386 ticks
MINE:            sum=3c927c56, 2973408 ticks
ORIGNAL:         sum=2e987a4d, 423399333 ticks
MINE:            sum=2e987a4d, 4282972 ticks
ORIGNAL:         sum=ef1b6aef, 311546265 ticks
MINE:            sum=ef1b6aef, 3155616 ticks
ORIGNAL:         sum=eedd2516, 289537880 ticks
MINE:            sum=eedd2516, 2933255 ticks
ORIGNAL:         sum=f7e967a8, 14341204 ticks
MINE:            sum=f7e967a8, 159210 ticks
ORIGNAL:         sum=1f37a7db, 213834232 ticks
MINE:            sum=1f37a7db, 2170192 ticks
ORIGNAL:         sum=c7d41f36, 294438278 ticks
MINE:            sum=c7d41f36, 2982720 ticks
ORIGNAL:         sum=aa9d2e9f, 259102247 ticks
MINE:            sum=aa9d2e9f, 2626891 ticks
ORIGNAL:         sum=8abd398a, 250396963 ticks
MINE:            sum=8abd398a, 2538880 ticks
ORIGNAL:         sum=a374bd58, 6099390 ticks
MINE:            sum=a374bd58, 76031 ticks

えーと最初にがーとやって提出したやつは、フルアセンブリで even は完全に埋めて odd も 93% 程度埋めて 62.405 倍とかだったらしいです。とにかく even でやってるけど odd でもできるよねー的な命令を odd に押し出していく感じだったと思います。この時はコードはまだ理解できる感じだったので手で命令スケジュールやってました。最後に自己書き換えコードとか調子に乗って入れてみたりした思い出が。端数の計算はメインループに ret 入れるのが一番速かったんですよね。

で1ヶ月間程度間を追いて、先月末あたりから他に思いつかなかったので、しょぼしょぼと配列 mt をそのまんま計算するんじゃなくて、 bit ごとに同じ要素にまとめてやれば、速くなるかは自信ないけど tempering は減るなーと思って変換していた。ぶっちゃけ 2ch で ZF(2) がどうこう書いてあって、あーそういう群の中の線型変換なのねコレ、じゃあ順番変えてもいいのかーという感じだったので、ヒント無しじゃわからんかった気もしないでもない。や、脳裏にはよぎってたけど、本当に完成するのかは自信がなかったので、単純な変換だとわかってなかったら始める決意ができたか、やりとげられたかは微妙だなーと思う。

でまぁなんかやりとげられて、色々やってるうちに bit 列は反転させて持った方が良いなーとか気付いてレイアウトはかなり違うものになったのでした。どう違ったかは説明しがたいので今度図でも書こうと思わないでもない。というか似たようなことやってる人は多そうなので誰か説明してくれるであろう。

まぁあとはコードが複雑になってるので、手でスケジューリングは無理っぽいし時間も無いしで、適当に機械でスケジュールするコードを書いたら、まぁそれなりにうまいこと動いた感じだった。最終的にはわけのわからない微調整をアレコレ入れてメインループ内に 2538 命令、 even 1269, odd 1242 で lnop 27 、 nop 0 という感じで、 98.94% の空間が埋まっていたらしい。まぁコードが複雑化して自由度が増えていたので、 even と odd の数を調整しやすかったという感じ。

感想としては、よくもまぁこんだけもりもり色んな並列化ができるもんだなーというのと、結果が完全に予測できる環境での最適化はなかなか面白いなーということ。入賞するご予定の KLab の方が書いてる感想に激しく同意。

http://dsas.blog.klab.org/archives/51368711.html

あと仕事でやるのも楽しそうだけど、やらされる人がいるとするとそれは不幸だなーとかも思った。

なんか参加した人とかで感想を述べる集まりとかできると良いなーとか思いました。

なにかあれば下記メールアドレスへ。
shinichiro.hamaji _at_ gmail.com
shinichiro.h