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では再帰が使えないので、上のコードも非再帰版に変換する必要があります（優先キューも非再帰版にする）
あと、ちょこちょこ同期を取らないとモニタがブチっと切れたりして大変でした。
このあたりはメカウーサーさんに色々と教えてもらいました。