最近のハードウェアに詳しい方はご存知だと思いますが、GeForceとかRADEONというグラフィックハードウェアがあります。
こうしたグラフィックハードウェアは、以前はリアルタイム3Dグラフィックに特化した機能のみを持つものでしたが、現在では高いプログラマビリティーと並列性を持つことからGPUと呼ばれ、汎用ベクトルプロセッサとしての応用が見込まれています。
具体的には、GPUはシェーダー(*1)と呼ばれるプログラムを実行可能な浮動小数点パイプラインを多数備えています。最新のGeForce 7800 GTXでは、32bit floatの処理やフロー制御が可能なパイプラインを24本持っています。
このように高い性能を持つGPUを汎用処理に利用しようというのがGPGPUです。
そのGPGPUのテーマの1つとして、ソートやサーチがあります。しかし、通常のCPUで使われるヒープソートやクイックソートのアルゴリズムは並列化が困難なので、いわゆる並列アルゴリズムと呼ばれるものを使うことになります。その代表的なものがバイトニックソートです。
バイトニックソートとは、比較器(Comparator)からなるソーティングネットワークで、ハーフクリーナーでバイトニックな系列からソートされた系列を作り、2つのソートされた系列を組み合わせて2倍のサイズのバイトニックな系列を作る、という繰り返して全体のソートを行うものです。
とりあえずGPGPUのさわりとして、このバイトニックソートをOpenGL 2.0とGLSLを使って実装してみました。
しかしながら、私はGeForce 5700という性能的にかなりプアなものしか持っていないため、ソートが可能であることが分かっただけでした。
あらかじめCで作ってみたものをCPUで実行したのよりは速かったけれど、STLのsortはおろかqsortを抜くのもかなり難しそうです。
性能のグラフとかはそのうち載せます。
*1 シェーダーとは、"トイストーリー"などで有名なピクサー社のレンダリングインターフェース、"RenderMan"で導入された、頂点やピクセルごとに実行される小規模なプログラムのこと。