Syoyo Fujita's Blog

raytracing monte carlo

Month: February, 2007

WSCG 2007

WSCG 2007 の論文も公開されていました。
というかもうカンファレンスも開かれていました…

http://wscg.zcu.cz/wscg2007/wscg2007.htm

まったくまだ手を付けられていませんが、タイトルからだけで判断すると、、、

Light Octree: Global Illumination Fast Reconstruction and Realtime Navigation
A study of Incremental Update of Global Illumination Algorithms
Robust Diffuse Final Gathering on the GPU
Fast Filtering and Tone Mapping using Importance sampling
あたりが面白そう

最後は、おなじみ? ブタペスト工科大の Szirmay チームです。
タイトルだけみるとシブいねぇ、まったくおたくシブいぜ。

I3D 2007 Papers list

毎度おなじみ?, Ke-Sen Huang 氏により、I3D 2007 の論文リストが公開され始めています。


http://myweb.hinet.net/home7/hks/Papers2007/i3d2007Papers.htm

とりあえず軽く読んだ上での感想です。
精読していないので誤読もあると思うので参考までにとどめてください。

Multi-Fragment Effects on the GPU using the k-Buffer

各フラグメントごとに RMW(Read-Modify-Write) 可能な k 個の
フラグメントバッファ(k 個のデプスなど)を持たせる。
現状 MRT(multi render target)とかあるけど、あれは書くだけしかできない。
A-buffer や R-buffer のようなもの。
半透明効果などを 1 パスで実現する。

が、これって自動(or プログラマブル)でソートできるのかな?
読む限りストリームの投入は結局ソート済みを投入するような感じで書かれているようです….
勝ってにソートしないなら、そんなに新規性があるわけではないと思うし、
k 個に制限というのは、汎用的な処理に持っていくのには物足りない。

とはいえ、半透明処理などのグラフィックス効果には有益度が大きそうなので、
将来の GPU には搭載されそうな雰囲気です。

次世代のリアルタイムグラフィックスのキモは、
水、草木、毛、皮膚などで、いかにうるうる感、みずみずしさを表現できるかだと思いますので。
(「反射と屈折のハーモニー」っつーんですか〜、「スキャタリングの調和」っつーんですか〜)

ROP に効率的かつプログラマブルな RMW を実装するのは結構コストがかかる気がしますが、
cuda では shared memory or local memory で on chip な RMW バッファ
を実現しているようなので、実はもう G80 には HW に組み込まれている?

4D Compression and Relighting with High-Resolution Light Transport Matrices
いわゆる wavelet ベースの PRT. 既存手法に比べて 1/3 くらいにメモリ量を圧縮できる。
まだまだゲームで使うにはもう少し時間がかかりそうかな?

Interactive k-D Tree GPU Raytracing
ピーク性能を実現するなら kd 木もよいと思いますが、静的シーン限定というのがやはり kd 木の弱点か。
今のトレンドは動的シーン対応ですよね。kd 木ベースで効率的な動的シーン対応
アルゴリズムが出るまでは、BVH ベースのほうが未来があると思います。
現状 cuda で BVH で paketized ray でひとまず GPU リアルタイムレイトレは
完成か?

OpenSPW may have the chance to recieve a technical academy award in the future?

HDRI フォーマット形式である OpenEXR がアカデミー技術賞を
受賞したことを masuo さんの日記で知りました。

….
画像フォーマットが受賞できるなら、ということは、
スペクトルデータのフォーマット形式の標準を目指す OpenSPW も
いずれアカデミー技術賞を受けることも無きにしもあらず?

これは早急に OpenSPW の中身の策定と実装をきちんとすべきか!?…

OpenSPW: Spectrum Data format proposal

Hardware Accelerated Ambient Occlusion on GPUs

Shanmugam, P., Arikan, O.,
Hardware Accelerated Ambient Occlusion Techniques on GPUs
ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games.
Seattle, WA, April 30 – May 2, 2007
http://www.cs.utexas.edu/~perumaal/

動的シーン対応のアンビエントオクルージョン計算を GPU でリアルタイムにやっちゃおうという論文。
I3D 採択論文。そろそろ I3D の論文が出回り始めています。

共著者には Pixie レンダラと共に最近のアンビエントオクルージョン近似手法で
有名な Okan Arikan 氏もいます。というか I3D 三本って…
http://www.cs.utexas.edu/~okan/

さて、今回の論文のアンビエントオクルージョン計算は、基本的な仕組みは非常に簡単です。
手法はイメージベースです。

カメラからまず物体を描画し、法線画像とデプス画像を作ります。
デプスが分かれば位置 P が分かりますので、各ピクセルを仮想的な球とみなすことができます。
(球の半径はデプスに比例して求めたりできる)
あとは、各ピクセルにつき、周りのピクセルのその仮想球からの寄与の和をとるだけ。

欠点としては、帯域を多く使うのと、
画面からちょっと外れたところに大きな occluder が配置されてしまうと、
画面内のピクセルに影響を与えることができないので、ある程度画面のマージンをとらないと
ダメだというくらいでしょうか。

まあ見た目にはそんなリファレンス(レイトレベース)は変わらないですし、
ポストプロセスフィルタ的な感じで実装できるので実用性は高いと思います。
Anbient Occlusion Fields の頃に比べると、大きなアルゴリズムの進化ですね。

これからゲーム系には、じょじょにこの動的アンビエントオクルージョン手法が
取り込まれていきそうな気がします。

ところで、我らが愛しの? Szirmay 先生の
Efficient Approximate Visibility Testing Using Occluding Spheres
も cite すべきだと思うんですが…

http://citeseer.ist.psu.edu/szecsi04efficient.html

NVIDIA cuda beta released

NVIDIA の cuda のベータ SDK がリリースされています。

http://developer.nvidia.com/object/cuda.html

仕組みをちらりと見てみましたが、いくらか特殊なキーワードがあるものの、
大体は C 言語の体裁に収まっていますね。
cuda のフロントエンドが、キーワードに応じて
コードを GPU で処理する部分と CPU で処理する部分にまず分けて、
CPU 処理部分は通常の gcc などのコンパイラに渡される構成になっています。

オフラインレンダリングのアクセラレーションには、、、
うーんどうでしょう?どれくらいコード書き換えが必要になるのかによりますかね。

そのうち gcc などのコンパイラコードも cuda に移植して、
コンパイラを GPU で走らせコンパイルを高速化、
なんてものも出てくるかもですね。

double をサポートする GPU

ところで、cuda よりも気になるものが cuda のドキュメントに書かれていました。
2007 年末には倍精度浮動小数点(double)をサポートする GPU をリリースする
予定だとのこと。

これが出てきたら、本格的に演算を cuda でアクセラレートする
というのが現実的なものになってきそうですね。

64-bit Lock-free queue implementation

http://lucille.atso-net.jp/svn/angelina/algo/lock-free/

[EN] Here’s my implementation of

Simon Doherty, Maurice Herlihy, Victor Luchangco and Mark Moir,
Bringing practical lock-free synchronization to 64-bit applications.
PODC 2004. pp. 31–39.
http://www.cs.brown.edu/research/projects/transactional_memory.html


[JP]

64-bit 対応な lock-free queue を実装してみました。

この論文の特徴は、

o 64-bit 対応
o スレッド数をあらかじめ知らなくても OK (population-oblivious)
o O(m+n) のメモリ領域しか使わない(m = LL/SC でアクセスが必要な変数の数, n = スレッド数)

な lock-free queue アルゴリズムの提案です。これらすべてを実現するのは、この論文のアルゴリズムが初らしい。論文には疑似コードが豊富でだいたいそのまま実装もできちゃうのがいい(CAS のインラインアセンブラ実装で手こずりましたが)。

lock-free アルゴリズム

lock-free とは、ロックを必要としないで同期処理を行うアルゴリズムです。

http://ja.wikipedia.org/wiki/Lock-freeとWait-freeアルゴリズム

nyaxt 先生の日記でこの言葉を知りましたが、
10 年以上前からずっと研究されてきた仕組みなんですね。

スレッド間での同期や排他処理などには、
ミューテックスとかで排他区間を実現するくらいしか知らなかったので、
ちょっと目から鱗でした。

今は linux やら windows などのカーネルでも、この lock-free なアルゴリズムが使われています。

lock-free に関係の深いものとして、wait-free アルゴリズムというのもあります(wikipedia 参照)。

web で調べた限りではあまりよい説明が無かったのですが、
要は、通常のロックベースだと、誰かがロックを取っている間は
他のスレッドは資源にアクセスできないので、(最悪無制限に)待たざるを得ないのですが、
wait-free であれば、最大でも待ちはスレッド数に比例するが、
有限時間内に自分に資源が回ってくる、という感じでしょうか。

既存のロックベースのアルゴリズムは、
while とかでループをまわして資源がとれるまで待ちますが、
しかし wait-free だからと言って、
そのような while でループを回すという仕組みが無くなるというわけではないようです。

ループで回る回数がロックベースに比べると少なくなったり、
無制限にループしてしまう(デッドロック)ということが起きなくなるという感じのようです。

アトミック命令

さて、実際に lock-free アルゴリズムを実現するには、アトミック命令と呼ばれる、
特定のメモリ位置を不可分(atomic)に操作する命令が必要になります。

アトミック命令には、CAS(Compare and Swap) もしくは
LL/SC(Load-Linked/Store-Conditional)命令があります。
x86 では、CAS のみがサポートされ、LL/SC 命令はサポートされていませんが、
通常 LL/SC は CAS で実装することが可能です。

アトミック命令といっても、プロセッサによってそのサポートには細かい違いがあり、
たとえば一度に不可分に操作できるバイト数などに違いがあります。

また、アトミック命令は、Java などではそれらのインターフェイスが提供されていますが、
C 言語ではインラインアセンブラを使って呼び出す必要があります。

今回の実装では、64-bit 環境における 64-bit 幅の CAS 命令が必要です。
x86-64 な環境では、64-bit 幅の CAS 命令は、cmpxchgq 命令が用意されています。

static inline uint64_t cmpxchg64(void *ptr, uint64_t oldv, uint64_t newv)
{
        uint64_t out;

        uint64_t v = *((uint64_t *)ptr);

        // newline after `lock' for the work around of apple's gas(?) bug.
        __asm__ __volatile__(
                "lock\\n cmpxchgq %2,%1"
                : "=a" (out), "+m" (*(volatile uint64_t *)ptr)
                : "q" (newv), "0" (oldv)
                : "cc");

        return out;
}

Intel Mac の場合、コンパイラのバグらしきもののせいで、
lock の後には newline が必要になります。
(二行に分けて書くのが問題ないかも)

cmpchg8b 命令も 64-bit 幅の CAS 命令で、これは 32-bit 環境でサポートされています。
atomic_ops ライブラリ [1] より。

static inline int
cas64(volatile double_var_t *addr, unsigned long old1, unsigned long old2,
     unsigned long new1, unsigned long new2)
{
  char result;
  __asm__ __volatile__("lock\\n cmpxchg8b %0; setz %1"
                       : "=m"(*addr), "=q"(result)
                       : "m"(*addr), "d" (old1), "a" (old2),
                         "c" (new1), "b" (new2) : "memory");
  return (int) result;
}

ただ、このコード、Linux ではうまくいくのですが、
Intel Mac のコンパイラだと BREG に割当てられないとか変なエラーがでてコンパイルできません。
うーん、インラインアセンブラをしっかり勉強しないとかな。

その他、x86_64 環境では、cmpxchg16b という 128-bit 幅のアトミック命令があります。
(AMD64 環境では、最近になりサポートされたようです [2] )
他プロセッサでのアトミック命令を扱うコードは、atomic_ops [1] などが参考になります。

パフォーマンス

通常のロックベースのキュー(リポジトリの TowLockConcurrentQueue/ にある)と、
今回の 64-bit clean な lock-free キューの実装とのパフォーマンスを比較してみました。

result.png
horizontal: # of threads. vertical: time(secs).

横軸がスレッド数で、縦軸が処理時間(秒)です。
ロックベース(pthread_mutex 使用)では、2 スレッド以上でガクンと処理時間がかかっています。

測定のプログラムはキューの処理中に malloc/free を呼んでいたりするので、あまり fair な
パフォーマンス測定プログラムではないと思います。

pthread_mutex を利用したロックベースの手法も、スレッド数が増えていく割には
処理時間が O(n^2) とかで増えて行く訳ではないので、単純に pthread_mutex コールの
オーバヘッドの差だけなのかもしれません。

それでも絶対的な処理時間は lock-free が短いので利用価値はある、と言えそうです。

キュー構造とレンダラ

マルチスレッド対応(MT safe)なキュー構造は、現状の lucille ではあまりプログラムが高度にスレッド化もされているわけではないので、利用部分は今のところないと思います。

しかし、kilauea の解説をみると MT safe キューは至る所で使われたとあります。
これからのマルチコア時代に、1 CPU 内の中で kilauea のような複雑なスレッドレンダリング処理を行うことを考えると、MT safe なキュー構造の必要性が大きいと思います。

そういう訳で、今回の lock-free queue の実装に至りました。

ただ、NVIDIA の cuda や Intel の 80 cores プロセッサをみると、
スレッドへの仕事の割り振りやスレッド間の同期とかはコンパイラが
うまーく処理してくれそうな雰囲気がします。
なので、いずれ lock-free なアルゴリズム(に限らず並列プログラムも?)を
ユーザが実装するというのは必要無くなっていくのかもしれませんね…

[1] The atomic_ops project
[2] http://www.marbacka.net/asm64/arkiv/amd64_em64t_difference.html