Syoyo Fujita's Blog

raytracing monte carlo

Month: June, 2007

align.vim

http://mysite.verizon.net/astronaut/vim/align.html#Examples

うわ、こ、これはすごい… vim 用の整形プラグインです。
いままで ‘=’ や変数定義の整列とか手作業でちくちくやっていて、
めんどいなぁ、uncrustify とかの整形ツール使ってみたけどいまいち思い通りにならないなぁと思っていました。

試してみたところ、いくつかはうまく動いてくれない機能があったりしましたが、概ね満足した動作。
vim 上でのコードの整形について、積年のもやもやが一気に解決されたきがします。
このプラグインでソースコード整形はすべて事足りそうかも。

こんなすごいプラグインがあるなんてつゆ知らず… vim プラグインも探すともっとすごいのがあったりするでしょうか。

Advertisements

EXOCHI

EXOCHI: Architecture and Programming Environment for A Heterogeneous Multi-core Multithreaded System
Perry H. Wang, Jamison D. Collins, Gautham N. Chinya, Hong Jiang, Xinmin Tian, Milind Girkar, Nick Y. Yang, Guei-Yuan Lueh, and Hong Wang
PLDI 2007.
http://portal.acm.org/citation.cfm?doid=1250734.1250753

まだ abstract くらいしか見ていませんが、Intel が、Core2 と、 GMA(Graphics Media Accelerator) を演算プロセッサに見立てた?ものとの、異種混合環境むけのコンパイラとデバッグ環境を作ってみました、という感じの論文です。

基本的には OpenMP 指示文を拡張して、子コア(GMA)での実行コードは GMA のアセンブラを記述します、という感じのようです。で、fat binary 化すると。これは CUDA とも似たようなものですね。デモプラグラムは画像フィルタなど並列化しやすいものばかりですが、1.4x ~ 10x ほどの高速化を実現するようです。

こういう成果がフリーで出てくれるとうれしいところですが、Intel のことですからそれはなさそうでしょうか。
Larrabee 向けにも作っているとされる?コンパイラも、こんな感じで OpenMP 指示文で並列化とか指定するのかな?

Atomic ops in CUDA 1.1

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

[En]

Atomic operation is now supported in CUDA 1.1 profile.
1.1 profile is supported on G84 or G86 chip.

I think various CPU method can be now easily mapped into GPU by this atomic op facility.

[Ja]

CUDA 1.1 で、待望の? アトミック処理がサポートされています。
ただしグローバルメモリに対してのみ, 扱えるデータ型が int32 のみとなります。
1.1 のプロファイルは、G84 or G86 で使えるようです(なぜか G80 では使えないようです)。

これで、かなり CPU の手法を自然と GPU へとマッピングできるようになるのではないかと思います。

stackless kd-tree, 短い命だったなぁ… まあまだグローバルメモリに対するアトミック命令が
どれだけ遅いのか分からないので、普通 kd-tree on CUDA 1.1 より高速な可能性も無きにしもあらずですが…

CUDA のサンプルではいくつか option pricing のサンプルがありますが、
どれも基礎的な option pricing であまり実用性がなさそうですね。
ここは日本人として、藤田先生の edokko option [1] などが GPU で計算できたら面白い気がします。

[1] Edokko Options:A New Framework of Barrier Options
http://db.cm.hit-u.ac.jp/servlet/commerce.SelectProfile?pid=3100

ANTLR v3 book

http://www.amazon.co.jp/Definitive-Antlr-Reference-Domain-specific-Programmers/dp/0978739256

どうにも ANTLR のサイトにある v3 のドキュメントはまとまりがないので、購入してみました。

タイトルに reference にある通り、多くのページがリファレンスに割かれていますが、
ANTLR v3 入門も最初のほうに少し書いてあります。
入門はサイトにあるこまぎれなチュートリアルよりはまとまりがある、という程度の体裁ですが、
それでも初学者がひととおり全体を理解するのには十分な感じです。

これで効率的にシェーダコンパイラが書けるようになる… かな…

ただ、java 以外のランタイム、たとえば C ランタイムや python ランタイムの
使い方の説明がないのがちょっと残念。オンラインマニュアルにもほとんどそれらの解説がないし…

Coherent Metropolis Light Transport with Multiple-Try Mutations

from ompf.org.

Coherent Metropolis Light Transport with Multiple-Try Mutations
Benjamin Segovia, Jean-Claude Iehl and Bernard Péroche
http://bat710.univ-lyon1.fr/~bsegovia/papers/cmlt.html

[En]
Then proposed the MLT variant method combined with Coherent raytracing for accerelated MLT rendering.
They used MTMH(Multiple-Try Metropolis-Hasting, which is also used in MIR paper) for lens subpath perturbation. Points generated are distributed locally so coherent raytracing method can be used to sample it.

MLT based rendering is becoming practical year by year,
thus I belive MLT based rendering method will be definitely default algorithm for future offline renderers.

[Ja]

MLT と coherent レイトレの組み合わせの提案。

MIR(Metropolis Instant Radiosity) [1] でも使われていた MTMH(Multiple-Try Metropolis-Hastings) を lens subpath mutation に使って、どうせ lens subpath の mutation なら localicity ができるから ray packet で処理できるじゃん、という感じです。

しかもなんと、著者による CMLT の実装が、氏のレンダラ yacort に実装されています。yacort は他にも MIR の実装があります。すげー。

http://liris.cnrs.fr/~bsegovia/yacort/

結局のところ、もともと lens subpath などの localicity のできやすい部分経路だけを coherent にしただけで、
経路全体の mutation は incoherent になっちゃうので MTMH は使えないから、
フツーに MH で bidirectional mutation をしています。
それでも MLT と coherent レイトレの組み合わせができて、
MLT が実践的なものになりそうだというのを提案したという点は大きいと思います。

オリジナルの MLT が提案されてからちょうど今年で 10 年ですが、だんだんと MLT は使えそうだと脚光を
あびつつある気がしています。
将来的に、商用/プロダクションのオフラインレンダラは MLT ベースのモンテカルロレイトレになりそうで楽しみです。

ちなみに論文では並列化が MLT のアルゴリズム上まだ困難であることを指摘していますが、
これには skit 先生のレプリカ交換モンテカルロ法が使えるでしょう。
MTMH とレプリカ交換モンテカルロ法の組み合わせが両立するかどうかは… たぶんできると思いますので、
そうなるとかなり MLT も実用的になっていくのではないかと思います。

# それにしても ompf.org はすごいなぁ、レンダラ野郎がほとんどいるし、
# レイトレ研究者も最近かなり多く参加しているみたいだし。
# 下手な学会よりはクオリティが高いと思います。

[1] Metropolis Instant Radiosity
http://lucille.atso-net.jp/blog/?p=290

ばね

今年の 5 月から, Prof. F が戻ってこられて, バネにまつわるアツい講義をしてくださっていました。
毎週講義を楽しみにしていたのですが…

ええええっ!! Prof. F のバネの講義ってもう終わりなの!?

てっきり 200 年に渡るバネを巡る確執にまつわる講義を末永くしてくれるものだと思ったのに…
明日から誰に師事して生きていけばいいのだろうか…

malloc performance

[En]

I’m now tring to write high performance BVH(Bouding Volume Hierarchy) raytracer combined with Intel’s recently proposed approximate SAH construction method [1].
I’ve started from writing efficient memory allocator.

http://lucille.atso-net.jp/svn/angelina/spatial/dynamic_bvh/

System’s default malloc() does not guarantee 16 byte aligned memory allocation(glibc: 8 byte, darwin: 16 byte) for SSE data manipulation.
And more, we might need 32 byte or 64 byte aligned memory allocation for efficient L1 cache behavior.

posix_memalign(), provided in linux, can allocate arbitrarily aligned memory but it is not cross platform and it is slow(see below).

Thus if we need high perfomance computation(SSE and better L1 cache behavior), we must write our custom memory allocator.

Kilauea style pooled memory allocator

I wrote Kilauea style pooled memory allocator [2] which is simple and efficient for small memory allocation. It is well suited for constructing spatial data structure.

Here is the perfomance of malloc, posix_memalign and Kilauea style pooled memory allocator.

malloc() uniform: 0.210081 (sec)
posix_memalign() uniform: 0.533821 (sec)
mem_pool_alloc() uniform: 0.064749 (sec)

The performance test is performed by sequentially allocating 32 byte data 1048576(1024*1024) times and no free() operatin in this test.
(align is 32 byte exept for malloc() ).

posix_memalign() is 2.5x worser than malloc().
mem_pool_alloc() is fastest, but it should be so since malloc() and posix_memalign() is general-purpose memory allocator.

[1] Highly Parallel Fast KD-tree Construction for Interactive Ray Tracing of Dynamic Scenes
http://lucille.atso-net.jp/blog/?p=303

[2] Practical Parallel Rendering
http://books.google.com/books?id=_iT7AFTb96MC&pg=PP1&ots=giZTxWM6wN&
dq=Practical+Parallel+Rendering&sig=UDL8g0o3Gy8LNlk4tUG-Lqoxl7E

Wow, we can see all content of the book!

Highly Parallel Fast KD-tree Construction for Interactive Ray Tracing of Dynamic Scenes

Highly Parallel Fast KD-tree Construction for Interactive Ray Tracing of Dynamic Scenes,
Maxim Shevtsov, Alexei Soupikov and Alexander Kapustin.
EUROGRAPHICS 2007.

[En]

http://graphics.cs.uni-sb.de/Courses/ss07/sem/index.html

When I posted the article about “stackless kd-tree traversal” [1], I felt `kd-tree has no future’.
But I must take back what I have just felt and I have to say `kd-tree is still alive’.

The presented method in Intel’s kd-tree paper is mainly about fast SAH evalution,
thus it is not limited to kd-tree spatial data strucutre.

I think proposed method could be easily adapted to BVH or BIH method,
and more if it is combined with selective reconstruction [2], there might become
the fastest dynamic raytracer in the world(as of 2007).

[Ja]

kd-tree の構築が遅くて、kd-tree を動的シーンのレイトレに使えないのなら、
構築そのものを早くすればいいじゃない、というなんとも漢気な論文。

基本は SAH(Surface Area Heuristics) で分割面位置を求める計算を、
Havran の手法をベースに高速化して、並列化もしやすいようにしたよ、というもの。
近似手法なので、最適に構築された kd-tree に比べれば fps は 70% ほど落ちるものの、
構築時間は既存手法に比べて 100-300 倍を実現しています。

4 cores 使っているとはいえ、1000 万ポリゴンの Thai Statue の kd-tree 構築時間が
2.5 secs とはすごいなぁ…

タイトルでは kd-tree とありますが、提案している手法は SAH 計算の高速化なので、
これはそのまま SAH-BVH, SAH-BIH にも持っていけると思います。

提案手法によりこれだけ構築時間が高速されたとはいえ、やはり私としては kd-tree には未来を感じないので、
BVH ベースに本手法を適用したほうがよい結果を得られるような気がします。

Intel もそれなりにレイトレに投資しているようですね。

現状、GPU と比べてリアルタイムレイトレは destuctive innovation になりつつあるのかもしれません。
しばらくはまだまだ使いものにはならないでしょうが、ラスタライザでごにょごにょよりもリアルタイムレイトレの
ほうが将来性がありそうです。

[1] Stackless KD-Tree Traversal for High Performance GPU Ray Tracing
http://lucille.atso-net.jp/blog/?p=300

[2] Ray Tracing Dynamic Scenes using Selective Restructuring
http://lucille.atso-net.jp/blog/?p=298

RSL grammer for ANTLR v3

[En]

I’ve finished writing grammer for RSL(RenderMan Shading Language) with ANTLR v3 parser generator.
It’s my first step and trial of ANTLR and LLVM based shader compiler & shader VM for lucille.

http://lucille.atso-net.jp/svn/angelina/shaderlang/

The grammer is checked by a few dozen of primitive shaders.

I’m been familiar with BNF style(bison/flex) to write grammer,
so I’ve little confused to write grammer with EBNF style.
Especially how to write operator priority in EBNF.
In EBNF(of ANTLR), this is done in recursively defining rules.

Anyway, overall, EBNF can write grammer more clean than BNF.
I’m falling in love to use ANTLR v3.

Next step is to writing syntax checker and walker for generated AST tree of RSL to convert AST to LLVM code.

LLVM Developers’ Meeting Proceedings

http://llvm.org/devmtg/2007-05/

ちょっと前に開かれた、LLVM 開発者ミーティングの video や slide が公開されています。
あまり濃ゆい内容ではないものの、Apple’s OpenGL での LLVM の利用のされかたがなんとなく
わかるスライドがあります。

あと、gcc だけじゃオレらの要求を満たせんので、オレら LLVM 向けに新しい
C フロントエンドである clang つくることにしたっぺよ、というプロジェクトも紹介されていたり。
この clang は、open source で Mac 以外のプラットフォームでも提供されるようだと面白くなりそうな気がします。

# しかし youtube video の view の少なさが気になります。
# 実は LLVM ってまだあんまり人気ないんだろうか?