Stackless KD-Tree Traversal for High Performance GPU Ray Tracing

by syoyo

Stackless KD-Tree Traversal for High Performance GPU Ray Tracing
Stefan Popov, Johannes Günther, Hans-Peter Seidel, and Philipp Slusallek.
http://graphics.cs.uni-sb.de/Publications/

ひとことでいうと、教授選を通って、リアルタイムレイトレの巨塔を登りつめるのは Ingo で決まりか…
というのが感想です。

kd-tree と GPU という、私があまり好きでないもののコンボなので、今回はかなり批判的な内容になることをご了承ください。

Conference Scene(1024×1024, 1st ray, shading) で CPU 実装が 2 fps でしかない

MLRTA, Benthin06, Ingo’s Dynamic BVH では x86 1 core で 6-10 fps を達成している。

これは fair な比較をするのであれば、 stackless kd-tree の cycles per 1 traversal などから
理論値を推定する必要が本来はあります。

が、数字が論文に書かれていない無い以上、著者に確認を取る以外に知るすべはありませんが、
いずれにせよ stackless kd-tree traversal そのもののコストが大きいかと思われます。

stack を保持しなくてよい代わりに、rope 情報によりストレージコストが三倍になる。

本論文では、traverse 時に stack を保持しなくてよい代わりに、rope 情報を kd-tree 構造に付加する
必要があります。これは論文では理論的には 4 倍、実際は 3 倍程度、とレポートされていますが、
明らかにデータ量が増え過ぎです。CPU 実装ではデータ量が増えることで、キャッシュヒット率が低下
するでしょうし、GPU の場合は MMU を考えなければ、GPU 内のメモリに格納できるシーンのサイズが
小さくなるので、大規模向けにできません。

CUDA/CTM では、shared or global メモリを使って stack のようなものを実現できるはずです。
stack 情報は、レイ or パケットあたり 1 要素がたかだか 16 bytes のものが 100 段くらいで固定で
確保しておけば問題ないでしょう。つまり多く見積もって、 1 shader core あたり 10
ray が同時に走ることを考えたとしても、最大で 20 M くらいあれば十分になります。
シーンサイズに比例して kd-tree サイズが三倍肥大化するよりは、
レイ数に比例したほうが望ましいでしょう。

無理して stakless にする代わりに、払う代償が大きすぎます。

CPU 実装にくらべて GPU 実装はよくて最大 8 倍のパフォーマンス

論文では、GPU 実装(G80)は CPU 実装(opteron 2.6GHz 1 core)に比べて最大でも
8 倍程度のパフォーマンスにとどまっています。
(ただし GPU 実装はリードバックなども含む)

G80 の理論 GFLOPS は 1.3*(GHz) * 128(shader core) = 166 Gflops,
Opteron 2.6 GHz の理論 GFLOPS は 2.6(GHz) * 2(fmul and fadd ALUs) * 2(1 SIMD op per 2 cycle) = 10.4 GHz

であり、GFLOPS 比較でいえば 15 倍であるので、それくらいのパフォーマンスの差が欲しいところ。
これでは今出始めている 8 core CPU(quad x 2) でトントンですからね。

chip 価格の違いも考える必要はありますが、GFLOPS 換算の比較で差がない以上、
無理して GPU を使う理由が見つかりません。

Intel は本気なのか、ほかにネタがないからかなのかどうかはわかりませんが、raytracing を
Larrabee や many-core のキラーアプリとして挙げています。

http://www.beyond3d.com/content/news/242
http://www.beyond3d.com/content/news/234
http://bt.pa.msu.edu/TM/BocaRaton2006/talks/davis.pdf

プログラムの容易性や普及性から考えると、GPU を使うよりはこちらを
使ってなにか考えるほうが将来性があるでしょう。

無理して GPU でなにか CPU より早くなるものを、と研究する(GPGPU(ぐぴぐぴゅー))よりは、
将来 CPU のパワーが追いつくことを考えて、もっと本質的でアルゴリズムに近いところで
研究をしたほうが、ためになると思うんですけどね。
# 論文の”質”ではなくて”本数”が大事なんです、というひとは別ですが…

Advertisements