2009年03月31日

そろそろCell Challenge 2009について一言言っておくか

前のエントリで書いたとおりCell Challenge 2009で優勝しました。優勝と言っても正直予選のスコア差を生かしてハナ差で逃げ切ったので微妙な線ではありますが、まぁ勝ちは勝ちと言うことで。真の優勝者(と僕が勝手に思っている)たるRunSeptetチームさんにはどうやって高速化したのか、是非SACSIS2009で聞きたいと思います。もしここを見ていたらよろしくお願いします。>RunSeptetのみなさん

元々アルバイト先曖昧マッチングのソフトウェアを書いていたこともあって、課題を見た瞬間に「これは入賞できる」とふんでスタートしました(もちろん会社に許可は取りました)。正直なところ一人で申し込んだ時点では「入賞すればいいや」だったのですが、oxy君が加わったのでこれは優勝せねばなぁという感じになりました。既にx86で試し書きしたビット並列の編集距離計算のプログラムを持っていたので、それを128bit化するだけで--ここはかなり大変でしたが--動きました。この最初に動くプログラムを持っていたというのが良かったと思います。これが結局早く動くコードに繋がり、予選でのスコアに繋がり、優勝に繋がったので。

予選は最初にツールキット0.5が出た時点で1 SPEを使った128 bit parallelのコードが動きました。速度的には今と比較して4*7倍ぐらい遅かったと思います。この後でSPEでの並列化をどうしよう、とかメモリ制限的にいまのアルゴリズムだと動かないよね、と考えていました。ツールキット1.03が出た時点でコードががらりと変わったので、しょうがない全部書き直すかという感じで7 SPE並列化したプログラムを書きました。このときのプログラムは原因不明の低速化にいろいろと苦しめられました。最初のプログラムは時々10秒を超えることがあったのです。後で分かったのは、未使用ページへのDMAアクセスが異様に重いとか、DMAはどうもスケジューリングが公平じゃないとかそんな感じでした。ページングをPPE側で行い、signalなどで通信を整理すると安定し、速度も劇的に向上しました。後はoxy君が関数内の高速化をほぼすべてやってくれ、僕自身は最適化を全く行うことなく予選への提出となりました。

予選終了→本選はほとんど僕が手を付けることなく終わってしまいました。政治家先生の「秘書が、秘書が」ならぬ「oxy君が、oxy君が」状態です。予選が終わった段階で自明な枝刈りが出題に含まれることが分かったのですが、内容を把握する前にoxy君が高速化コードを書き上げていて僕はチェックぐらいしかすることがありませんでした。ループ内部についても、ありのままいま起こったことを話すぜ、oxy君があれから25%高速化したよって言ってきた、何を言っているのかわからねーが、です。まぢで。僕はというとDMAをダブルバッファリングに置き換えようかといろいろ測定してみたんですが、最終的に1.5%以下だったので無視することになりました。そのほか、SPE-SPE直接転送とか、通信周りではいろいろ試しましたがどれも遅くなってしまい、結局コミット量はほぼ0でした。なので、予選→本選の高速化は(というか高速化そのものは)ほとんどoxy君の功績です。
posted by chun at 00:00| 日記