Real-Time KD-Tree Construction on Graphics Hardware

by syoyo

Real-Time KD-Tree Construction on Graphics Hardware
Kun Zhou; Qiming Hou; Rui Wang; Baining Guo
http://research.microsoft.com/research/pubs/view.aspx?
0rc=p&type=technical+report&id=1468

My impression: TOO BAD!
The comparison against CPU is not fair.
And much worser, when analyzing the result the GPU implementation is 4-5 times inefficient than CPU.

これはひどい.

– レイトレのトラバーサルパフォーマンス

Core2 CPU 4 core にたいして GF8800 Ultra で、差が良くて GPU が1.5 倍.
複雑なシーンでは 10 % 程度の向上しかない.
理論値で比較すると、GFLOPS が 1/4, メモリ帯域が 1/4 ~ 1/5 の CPU と competitive って…
最新 8 core CPU に負けるじゃん.

– kd-tree construction
なぜパフォーマンス比較に [Wald & Havran 2006] を使うのだろうか? そりゃ勝てるだろ.
構築 Quality が低いからと言っているが、[Shevtov et al 2007] と比較すべき.

– stackless kd-tree は遅いので使わなかった
これは良い判断というか当たり前ですね. 帯域と演算量が増えるのだから.
いまの時代 GPU でも local メモリがあるのだから、stackless を使う必要はもうないだろう.
(stackless が stack 版に比べて 10% 程度のオーバヘッドにしかならないなどの効率のよい
stackless アルゴリズムが提案されない限り)

– kNN search
> プライオリティベースの手法は GPU では効率が悪いので使わなかった.

と言っておきながら、でもパフォーマンス比較では CPU 実装には
この効率が悪いプライオリティベースと比較して、GPU が 10 倍以上早いと言っている.

CPU 実装のほうも提案手法でやって比較するべきだろう.たぶん差はもっと縮まるはずである.

– パフォーマンスについては観測値しかのせていない
bandwidth, トラバース回数, 評価したノード数なども載せないと、fair な比較ができないし、
分かる人間が読めば、観測値では(ねつ造で) GPU が早いように見えるが、
実際は GPU のほうが効率がわるいのが分かる.
(提案手法を CPU で再実装したほうが効率がよい)

まとめ

しかしなんでしょうね、GPU 系の論文はなんで相変わらずこんなにも粗悪なのでしょうか.

– 無理矢理勝てる相手を見つけての比較
– 観測値だけ見てほら早くなったでしょ
– 十分でない考察
– こーすっと並列度がまして GPU で処理しやすくなるかもしれネ
– -> やってみたらなんかいい感じだったよ.

なんか GPGPU が出てから、このような粗悪な論文がとても多くなったような気がします.
GPU メーカーからお金でも流れているのかなぁ
研究者がこんな論文を嬉々として書いているのだったら、なんか悲しいです.

おまけ:
FLOPS もそうだけど、帯域がこれからのレイトレではネックになりそうですね.
http://www.cs.utexas.edu/~pnav/papers/utcs-tr-06-40/utcs-tr-06-40.pdf

もうひとつおまけ:
http://pc.watch.impress.co.jp/docs/2008/0402/tawada138.htm
> メモリクロックが引き上げられて多少カバーされているものの、GeForce 9800 GTXのメモリ帯域幅は70.4GB/sec。GeForce 8800 GTXは86.4GB/secとなるので、この部分ではダウングレードしている。

これから重要になる要素が帯域なのに、そこがダウングレードはまずいでしょ.
GPU もシングルチップでの性能アップはもう無理そうですね.
マルチコア化 or 廉価版拡大でインド、ブラジル、ロシアなどの新興国向けに焦点を絞っていくかでしょうか.

—-

私はもう GPU (で何かやる)のは終わりだと思っているので、
GPU ネタ論文とかに感想を書くのはこれで最後にしたいと思います.

Advertisements