Cell Challenge 1人反省会
今年もCell (Spped) Challengeの規程課題に参加してました。去年はあまり貢献できなかったけれど今年はほぼ全て自分で取り組みました。結果はアレでしたが貴重な体験になったと思います。
取り組み
取り組むに当たって、自分はまずレーベンシュタイン距離を知らなかったのでwikipediaで参照してDP解法で手で解いてみるところから始めました。んでプログラムを書いてみて、次にsonyのサイトからマニュアルを落として読みました。
んで、その次にツールキットプログラムをコメントを付加しながら読んで理解し、それからどこをどう高速化できるかを見ました。そして、ブロック計算のメイン部分で部分文字列が一致しているかどうかを調べるif文をループの外に出して、ループにはいる前にその結果を128x128のchar配列に納めるようにして、ループ中はその配列を参照するだけにしました。そして、配列に値を格納するコードはspu_selとspu_cmpeqを使ってSIMD化しました。実は、自分がsubmitしたコードでやったのはこれと、あとはデータが小さいときはPPEだけで計算するようにしただけです。本当は他にもやってみたけれどどれも早くならなかったので結局それだけ。ツールキットから大体1.7倍位早くなってました。make run*では。
この他に、
- ブロック計算をSIMD化してみたり（データの並び替えに時間かかりすぎて30%程遅くなった）
- 部分文字列をキャッシュしてみたり(線形探索、2分探索、2分探索木、どれも早くならず)
- mailboxで同期させてみたり(早くならず)
- その他いろいろ
を試したけれど早くならなかったなあ・・。
ところで、spu_timingとかasmVisを使えばパイプラインがどの程度ストールしているかは分かる。けれど、そこからC言語のどのステートメントを書き換えれば改善されるのかが分からないので使えねーと思っている。ニーモニックが理解できないとフィードバックできないとか勘弁してください。
