BBF-kd-tree探索 on GPU

先週にnVidiaのGT640というGPUを入手したのでGPGPUを勉強中。
性能は900MHz×384コア。CUDAという言語で書きます。


早速、kd-treeというデータ構造で、データベースの中から似たような要素を探すものをCUDAで作ってみた。
探索アルゴリズムはBest Bin Firstという方法。
この方法もよく理解できなかったけど以下のRob Hess氏のＨＰにあるコードが非常に参考になった。


blogs.oregonstate.edu/hess

SIFTライブラリのkd_treeとmin_pq(優先キュー)ですね。

内容的には

  1. 再帰を使わず、優先キューでkdノードを追加
  2. 優先キューは空間分割の軸とクエリーの距離で並び替える
  3. 探索はキューを取りだす回数が一定回数に達したら打ち切り

という感じです。３番目が高速化の秘訣です。当然、精度が落ちますけど。
ちなみに、Rob Hess氏のコードは洗練されていて見やすい。
kd木の構築時は、分散が大きな軸を分割軸に、
そのメディアンで再帰的に分割していきます。


実際にCUDAで組む場合は、木の構築はCPUに任せて、探索だけGPUで行います。
ただし、GPUでは再帰が使えないので、上のコードも非再帰版に変換する必要があります（優先キューも非再帰版にする）
あと、ちょこちょこ同期を取らないとモニタがブチっと切れたりして大変でした。
このあたりはメカウーサーさんに色々と教えてもらいました。

結果

128次元ベクトル×10000個の辞書データがあって、
65536個のベクトル（クエリー）の検索で、
CPU:9603msec
GPU:1379msec


大体、６〜７倍程度。CPUは3GHzの１コアの結果なので
６コア使うとあまり変わらないのかもしれない。
GPUももっといいものを使えば速くなるかも。
384コアもあるので100倍くらい速くなると思ったけど
そうでもなかった。ちょっと残念。
FFTも比較したけど良くて５倍程度ですね。


CUDAで多次元ベクトルの近似近傍探索は、色々調べた限りでは
コードがなかったので公開した方がいいのかな？

将棋 on GPU

将棋に使うとしたら、手の生成と３駒評価の部分をＧＰＵで
計算するといったようなＣＰＵとのハイブリッドがいいのかもしれない。
ただ、並列探索した場合、マルチコアのＣＰＵで１つのＧＰＵを
使えるのか（メモリ転送が競合して遅くならないのか？）、
かといってＧＰＵ４枚も差せるのか、電気代は大丈夫なのか、
とか思ってしまう。
３駒評価を毎回まともに計算するなら効果はでそうだけど
実際には差分評価なので効果が出にくいかもしれない。