Cell Speed Challenge 2007

http://www.hpcc.jp/sacsis/2007/cell-challenge/
Cell Broadband Engineを使ったプログラムコンテスト。
規定課題部門はfloat値のキー + 値のソーティング。
最初見たときは簡単すぎでは? と思ったけど、よく考えてみると、
いろんな要素が絡んできて、意外と難しい。
特にSPEのLS容量、256KB内にデータを収める必要があるって点が。

限られたメモリで、並列ソートするってことで、
何らかのマージソート系アルゴリズムが有力だと思うけれどが、Cellの浮動小数点のデータ形式はIEEE754と同じらしいので、
RadixSortも選択肢に入ってくるかな、と思った。

http://www.radiumsoftware.com/0310.html#031028
http://www.stereopsis.com/radix.html

試しに、家のPC上でfloatのキー値のみをソート、実行時間を計測したところ

STL使ったクイックソートよりRadixSortの方が平均4〜5倍程度速い。
下手にSPE×8で並列マージソートを行うよりも、PPE1個だけ使ってRadixSortした方が速い、
といった間抜けなことになる可能性もあるんではないかと。