Syoyo Fujita's Blog

raytracing monte carlo

Month: August, 2007

It’s time to move haskell to code MUDA?

[En]

MUDA compiler uses Ocaml and BNF Converter [1].
I found today that BNF Converter for Ocaml output lacks user defined `token’ rules.
This is critical for MUDA.

I’d like to write a patch for BNF Converter to support this lacking feature,
but BNF Converter is written in Haskell, so I must learn Haskell 🙂

Anyway, I had a plan that coding MUDA compiler with Haskell in the future.
(because Haskell seems much elegant than Ocaml)

So I’ve decided to shift to Haskell from Ocaml for writing MUDA compiler from now.

[Ja]

今日、BNF Converter で、カスタムルール(16 進数のパースとか)が
ocaml 出力のときだけサポートされていないのが分かりました。
これはちょっと致命的です。しょうがねーパッチでも書くべかなーと思ったのですが、
BNF Converter は Haskell で書かれているので、Haskell を習得しなければなりません。

また、BNF Converter はもともと Haskell 出力(Alex, Happy)がメインなようですし、
いずれ MUDA コンパイラも Haskell で書き直そうと考えていたので、
(なんとなく Haskell のほうがエレガントそうなので 🙂 )
パッチを書く時間があったらとっとと Haskell への移行を前倒ししたほうがよいと判断しました。

というわけで Haskell 移行に伴い少し MUDA の機能開発は停滞します。

[1] http://www.cs.chalmers.se/~markus/BNFC/

G80 performance

[En]

TODO…

[Ja]

G80 での数学関数のパフォーマンスはどんなものかと少し調べてみました [1,2]。
(G80 の場合サイクル数 = レイテンシ = throughput のようです)

– floating point mul/add などの基本演算は 4 サイクル
– log は 16 サイクル
– その他の逆数、exp, sin などは 32 サイクル

以外と個々の演算はサイクル数がかかりますね。
ただ、サイクル数はベースクロックでの値のようで、ALU は内部で2倍のクロックで動いているため、
この半分になると見るとよいみたい。
(さらに SP には 2 器 ALU が搭載されているので、
基本演算なら実質 SP あたり 1 サイクルでできることになります)

そして、ピークパフォーマンスの比較は [2] によれば、

– G80(GTX): 345 GFLOPS
– Core2(X6800): 46.9 GFLOPS
– Core2(Q6800): 85.3 GFLOPS

となります。GPU は Dual core で x8, Quad core で x4 早いと。
G90 が出れば Quad core でも x8 くらいの開きになるでしょうか。

G80 は個々の演算のサイクル数の遅さを物量でカバーしている、といえるでしょうか。

とりあえず、今回の結果から、(近似の)数学関数を 1 要素あたり 16~32 以下のサイクル数で SSE で計算
できるようにしてみようという目標ができました。

そうすれば、Quad core で x4 程度の開きなら無理して GPU を使わずに
MUDA 使いなよ、と言えるんじゃないかなぁと思います。

もちろん、
MUDA は今は SSE コードを吐いていますが、
GPU で実行することの価値が十分あることが分かれば、
MUDA コンパイラのバックエンドで *UDA や CTM なコードを吐いて
GPU で実行という手もあります。

要は MUDA は各種ターゲット向けの SIMD 最適なコードを自動で吐けること、
というのが目標なわけです。

[1] http://developer.download.nvidia.com/compute/cuda/1_0/NVIDIA_CUDA_Programming_Guide_1.0.pdf

[2] http://www.behardware.com/art/imprimer/659/

Sony Vector Math library and SIMD math library

Sony Vector Math library and SIMD math library open sourced
http://bulletphysics.com/Bullet/phpBB2/viewtopic.php?p=4884

[En]

TODO

[Ja]

MUDA で数学関数(log とか sin とか)どうするかな、と web をあさって見つけました。
PPU と SPU 向けですが、4 要素同時の logf, sinf とかがあります。
license は BSD と緩いので、これを SSE 版に porting しようかと思います。
というかこれこそコードを MUDA で書くのがいいかも。

経緯

精度はそれほど正確でなくていいので SSE 使って早い数学関数ルーチンはないかなぁと探していたのですが、
見つかるのはベンダが提供している SIMD Math Library(Accelerate.framework on Mac とか)とかばかり。
これらはみんな closed source なのでどの環境でも使えないという問題がある。

コードが公開されているものをと探したのですが、なかなか見つからず、
しょうがねー newlib の libm コードを MUDA(SSE) で書きなおすかなーと思っていたところに
Sony のライブラリを見つけました。

経緯にいたるまでの経緯

MUDA で数学関数どうすっぺかなーと考えていて、とりあえずまずは普通に gcc とかが吐くコードを試してみました。
ひとまず対象は logf() でこんな感じのコードを書いてみて、

http://lucille.svn.sourceforge.net/viewvc/lucille/angelina/muda/bora/log/

測定に AMD simulation utilities を使ってサイクル数を計ってみました。
(一部落ちるケースもあったけど、そのときは AMD のドキュメントでレイテンシを確認とかで推定しました)

普通の logf() (linux libm)

1000 サイクル以上かかりました。げげげー…
こりゃ MUDA では使えないね(デバッグ時とか以外は)。

gcc の -ffast-math で生成される logf()

100 ~ 150 サイクルくらい。げげー。
FYL2X っていう x87 インストラクションを使うようになるのですが、これが AMD では 100 以上サイクルがかかる。
(Intel でもそれくらいかかるみたい)
4 要素同時になって 100 サイクルならなんとか許容できるけど、1 スカラで 100 サイクルはかかりすぎ。

gcc の -mfpmath=sse とか cl.exe がリンクする数学関数

-mfpmath=sse だと普通に libm の logf() を呼ぶようです。
libm とかの実装次第ですが、私の環境では SSE は使われずに普通の logf() の振る舞い(1000~ サイクル)でした。

Visual C++ がリンクする数学関数は、Win 版の AMD Codeanalyst の結果を見ると
SSE2 サポートな CPU では SSE 版ルーチン(double 精度)が呼び出されていました。
これは 100 サイクルくらい。

-mfpmath=sse & -ffast-math

で 4 要素同時な SSE 近似数学関数が呼ばれることを期待したいが、、、
まぁ無いことは分かっています。
このコンパイラオプションの組み合わせだと gcc は FYL2X ではなくて
遅い方(精度がある(?) libm のほう)の logf() を呼ぶコードを吐くようです。

まとめとか

– 基本的には ojbdump でどんなコードになっているのか確認する。
– AMD SImulation utilities(linux), Codeanalyst(win) でインストラクションシミュレーションさせてサイクル数を確認
– mul や add が 1 cycle とかで処理できる世界なのに, 数学関数が 100~ というのは耐えられない。
これでは gpgpu とか *UDA をツブせないではないか。
– newlib とか [1] からの数学関数の近似計算ルーチンを SIMD に移植しようかと考えていたら、
Sony から 4 要素同時の数学関数の PPE, SPE 版が open source で出ていた。なんていいタイミング。
(内容は newlib’s libm の実装とはちょっと違うみたい)
– Sony のを参考にして MUDA なり SSE で書き直してみる
– たとえば logf なら 4 要素で 100 サイクルくらいでできると見込む(1 要素 25 cycle)。これならまあ耐えられる。
それ以上のようなら [2] とあまり差がなさそう。ちなみに glibc の結果は私の環境の logf() のサイクル数と大きな違いがありますね。
libm のバージョンや AMD と Intel の違いとかでしょうか。
– MUDA で書くなら、アノテーション機能を MUDA に追加したりして、精度を指定とかして精度に従ったコードが生成されるようにしてみる.
(さらにいうとたとえば Interval arithmetic なコードを吐くとか)

[1] Faster Math Functions
http://www.research.scea.com/gdc2003/fast-math-functions.html

[2] Accurate Math Functions on the Intel IA-32 Architecture: A Performance-Driven Design
http://rnc7.loria.fr/astafiev.pdf

MUDA note

[En]

I wrote initial documents for MUDA by using google notebook, as Prof. nyaxt is using it for his renderer.

`MUDA note’ provides thoughts and implementation notes for MUDA.
You may feel inconvinience since `MUDA note’ is written in Japanese.
I’ll write English version in the future, but not for now.

[Ja]

nyaxt 先生に見習って、私も google notebook で MUDA note をつけてみました。
ついでに svn にも MUDA のカッパバージョンを登録しました。まぁまだまともに動きません。
試してみる程度にとどめてください。
動かなかったら治癒能力を持つスタンド能力で治してください。

MUDA note に書いたことは 13 日以内に実現される… といいですね…

http://www.google.com/notebook/public/13822895759654633739/BDQGMIgoQqM7xlMki

Faster Ray Packets – Triangle Intersection through Vertex Culling

Faster Ray Packets – Triangle Intersection through Vertex Culling
Alexander Reshetov
http://kesen.huang.googlepages.com/rt2007Papers.htm

[En]

This is quite interesting paper and I think VC(vertex culling) would be a promising method for future realtime/offline ray tracing.

To summarize,

– Calculate ray frustrum for each leaf node when the ray packet enteres it.
– VC can reject 90% or more potential ray-triangle intersection.
— VC computation is fairly less. Just 2 adds and 1 mul for each triangle vertex.
– In average, ray-triangle intesection computation is done with just 1 or 2 cycles!
– Acceleration structure can be simplified to 1/10 with just 20-30 % performance loss against non VC algorithm.
— This means we could eliminate much traversal operations which causes random accessing for memory.

And as a bounus(?), The complete VC source code is attached in the paper!

I’m considering to implement this method to lucille raytracing core(and if possible with MUDA).

[Ja]

いやーこれもマジすごい。レイ-三角形の交差判定が平均たったの 1,2 サイクルでできる!

手法としては、レイパケットが葉ノードに到達するたびにレイ錐体を毎度つくるということをやります。
このとき葉ノードを実際に通るレイだけでレイ錐体をつくる。
そしてレイ錐体と三角形でまずは交差しそうかどうか軽く判定してから、
交差すると分かれば正確な交点位置を計算する。

で、解析によればレイ錐体にくらべて葉ノードの AABB が大きかったり、
その AABB に対して AABB に含まれている三角形の大きさが小さければ、
ほとんどレイ錐体と三角形は交差しないとのこと。
AABB がそれなりの大きさなら 90 % 以上は交差しない。

レイ錐体と三角形が交差するかどうかの判定は三角形の頂点あたりわずか 1 mul + 2 add でできる。
SIMD 化も容易。

これにより、レイ-三角形の交差判定を平均的にわずか 1,2 サイクルで達成する
(既存手法は 10 サイクルくらいになる)

VC を使えば、葉ノードの AABB が大きいほうが効果があるのだから
(ただしあまり大きすぎるとポリゴン数に比例する処理オーダーになってしまうので、パフォーマンスが落ちる)
それほど空間データ構造を細かく作る必要がない。
論文によれば VC を使わないときの 1/10 の空間データ構造のサイズで済みながら、
2,30% 程度のパフォーマンスロスにしかならないこと。

これはよい性質ですね。
空間データ構造が粗くて済むということは、メモリ使用量が少なくて済むし、
動的構築したいときも構築の手間が少なくてすむ。
そしてなによりトラバースによる予測困難なランダムアクセスが減る。
三角形リストは葉ノードの AABB に配列で入っているのでこれもコヒーレンスが稼げる。
つまり CPU にとっては空間データ構造のメモリ使用量も減るしキャッシュミス率が減るという特典がある。
(これは GPU で実装するのにもよい特性ではありますが)

VC はかなり実用的なレイトレ手法な気がします。
すくなくとも VC によって、ゲームのレイトレ化に一歩近づいたと感じています。

lucille のようなオフラインのレイトレにも効果が大きいですね。
VC を LBVH[1] や 4 分岐 BVH[2] と組み合わせると、
更なる省メモリ、SIMD の効率的な利用で最強のオフラインレイトレエンジン
になるんじゃないかなぁと思います。

うーむ、VC 実装してみなければですね(とくに MUDA を使って).

# それにしても, れしぇとふも ompf.org に出没してるのね…
# まじ ompf すげぇなぁ…

[1] David Cline, Kevin Steele and Parris K. Egbert, “Lightweight Bounding Volumes for Ray Tracing” to appear in Journal of Graphics Tools.
http://rivit.cs.byu.edu/a3dg/publications.php
[2] 木村秀敬. 並列演算に適したバウンディングボリューム階層
によるレイトレーシングの高速化
http://www.jaist.ac.jp/library/thesis/ks-master-2007/paper/h-kimura/paper.pdf

clang, C frontend for LLVM

http://clang.llvm.org/

[En]

Wow!, clang(though it’s in very early stage) is released as open-source.
I must play with it.

[Ja]

LLVM の C/C++ フロントエンドである clang がいつの間にやら公開されはじめていました。
まだまだ開発初期段階のようですが、結構よさそう。

サンプルを見てみましたが、gcc には vector_size という__attribute__ があるのですね。
clang はそれにも対応していて、ちゃんとベクトル要素の LLVM code を吐くようになっています。
そしてあとは LLVM バックエンドが勝手に AltiVec や SSE に変換してくれています。

うーん、SIMD コード生成は clang + LLVM でいいかも。
MUDA の存在意義がなくなりつつあるか?…

RTSL: a Ray Tracing Shading Language

RTSL: a Ray Tracing Shading Language
Steven G. Parker, Solomon Boulos, James Bigler, and Austin Robinson.
To appear IEEE Symposium on Interactive Ray Tracing 2007
http://www.cs.utah.edu/~boulos/research.htm

[En]

Wow, this is a good paper…
and what I am trying to do with my MUDA language [1] is already almost achieved by RTSL paper!

For instance,

– DSL(Domain Specific Language)
– SIMD code gen
– Can emit a code as efficient as hand-optmized low level code
– App specific optimization(In their case, ray packet optimization).

Although, I’ll continue to develop my MUDA language since I’m considering to use MUDA
to describe lucille core engine and also thinking to extend MUDA for shading language
and GI language in the future.

Anyway, DSL or something about language level thinkgs seems one of the hot topic in the recent CG reseach.
(There are Lpics, lightspeed, RSL for RPU, and this RTSL)

I think some people(including RTSL guys) are already combating to develop unified language system
for GI rendering(i.e. unified language to describe raytracing, pathtracing, bi-pathtracing, MLT and so on).

[Ja]

げー、なにこれ RTSL すごいよ。trace() が追加されているだけじゃなかったのね。

– GLSL ベースの DSL
– SIMD コード生成、リアルタイムレイトレにもオフラインレイトレにも使える
– ハンドオプティマイズされたコードと同じくらい効率的なコードを吐く
– 通常のコンパイラでは出来ないアプリレベルの最適化
(この後者ふたつがやっぱり DSL のうま味ですね)

ほとんど MUDA でやろうとしていることが達成されているし…

ただ、いずれにせよ彼らのシステムが open-source になろうと、
MUDA には MUDA の道があるし、 lucille のコアを MUDA で書き直そうとも考えて MUDA を
作ることにしたので、あと 196 年オレ言語を作り込んでいきたい気持ちもあるから
MUDA の開発は続けることになります。
(lucille は 200 年の長きに渡るプロジェクトです. 今年で 4 年がたちました)

また、MUDA は一度ある程度完成してきたら、ちょろっとシンタックスを変えて
lucille 向けのシェーダ言語や GI 言語(integrate とか cdf とかあったりするのですよ)
にも発展させていきたいところ。

Lpics, lightspeed などを見ていると、DSL(or 言語的なアプローチ)での効率化の追求はここ 2,3 年先の
グラフィックス研究のホットなトピックになりそうな予感がしています。

もちろん何度かグラフィックスの世界にも言語的な研究の波はあったわけで、ちょろっとまとめると

最初の言語的アプローチは 80 年代の shade tree,
次は 90 年代の shader specialization,
その次は 00 年代前半の multipass partitioning,
そして 00 年後半の lightspeed, RTSL などに見られるアプリレベルの最適化

という感じでしょうか。今は第四世代?

RTSL にもちょろっと書かれていますが、DSL から interval arithmetic(or affine arithmetic)なコードを
吐いてロバストな数値計算をするのも一つのよい DSL の利用例だなぁと思います。

[1] Load to MUDA. SIMD code generation, domain specific language, automatic optimization, functional programming, etc.
http://lucille.atso-net.jp/blog/?p=323

Fed Cuts Discount Rate, Recognizing Need to Stem Credit Crisis

Fed Cuts Discount Rate, Recognizing Need to Stem Credit Crisis
http://www.bloomberg.com/apps/news?pid=20601087&sid=aE1A7RkmKsag&refer=home

[En]

Wow, Bernanke finally did it!(although he decided to cut interest rate off, not FF rate).
I suppose this might be the beginning of the recession in worldwide.

[Ja]

いやー、ついにきました。今回はマジホンモノだ。
Fed による 0.5 % の緊急利下げです(FF rate ではなく公定歩合ですが)。

1987 年のブラックマンデー、1998 年の LTCM[1] 破綻よりもひどいと言われる今回の
subprime lending 問題を発端とした credit crunch.
subprime 問題は北京五輪まではがんばって先延ばしすんだろーなーと思っていましたが、
まさかこんなに早く来るとは思いませんでした。

メリケンにとっては今回の件は住宅バブルと消費バブル(credit バブル)の崩壊につながるでしょうから、
メリケン景気への影響が必死です。

GS 様の(計量ファイナンス理論を駆使した) quant 系旗艦ファンド global alpha ですら
年初来で 30 % 以上の損失を被ったらしいとのことですから、
結局 liquidity trap や fat tail への対処方法は LTCM 以降の quantitative finance
の発展を持ってしてもまだまだだったのでしょうか。
(ヘッジファンドがバタバタと倒れているらしい今、
マトモな(?) quant 系ファンドだったからこれだけの損失で押さえられたと言うべきかもしれませんが)

# それにしても金融(計量ファイナンス)の世界はこんなことがあるから面白いですね。
# サブプライム問題はメリケンだけかの問題かと思ったら、めぐりめぐっておいもの国の銀行が
# 5000 億以上の損失出しましたとか、ECB が買いオペとかしちゃうし。
# N スペで LTCM を取り上げるのと、LTCM の破綻があと 1 年早かったら、
# たぶんクオンツ[2, 3]への道を歩んでいただろうなぁと思う今日この頃です。

レンダラの世界で例えるならば…

レンダラの世界で例えるならば、今回の件は以下のような感じとなる。

これからの時代は unbiased だ! GI だ! renderman is obsolete !、
といって Maxwell や vray などの新興レンダラが人気を博して
なんとなーくみんながそんな新興レンダラでイケイケになりつつあったところに、
lightspeed + renderman(prman) による Transformers を見せつけられて、

「なんだよこのプレビューの鬼早さは!
コンボイ(optimus prime)のクオリティは!
これだったら unbiased レンダラも GI もいらねーじゃん! [4]」

となって結局 renderman ですべてをかっさわれてしまいましたとさ、
というそんな感じです。

# おまけ
# http://blog.transformers-movie.jp/
# で言葉を入力してみましょう。カタカナって言われたらオラとかボラとかアリとかですよね。

[1] http://ja.wikipedia.org/wiki/LTCM
[2] 金融工学者フィッシャー・ブラック
http://www.amazon.co.jp/dp/482224511X
[3] 物理学者、ウォール街を往く。—クオンツへの転進
http://www.amazon.co.jp/dp/4492653600
[4] 実際には transformers でも GI は使われているのかもしれませんが、すくなくとも lightspeed ではサポートされていない.

BNF Convereter

http://www.cs.chalmers.se/~markus/BNFC/

[En]

I found a very nice generator tool for parser/lexer generator. BNF Converter.
It supports a lot of outputs, at least,

– C/C++ with yacc, lex
– Ocaml with Ocamlyacc, Ocamllex
– Haskell with Happy, Alex

I’m considering to use this BNF Convereter for my MUDA language compiler.

I could say, with BNF Converter + FP language, “Anyone can cook write a compiler!”

[Ja]

各パーサ/レキサジェネレータ用のコードを出力してくれる BNF ジェネレータ。
BNF ルールを記述する量も少なくて済みます。
まったくコンパイラの分野は便利なものばかりですね。

これらさえあれば、「誰でも名シェフコンパイラ書き」になれるのではないでしょうか。

少なくともコンパイラフロントエンドの作成はかなり楽になると思います。
RSLtoLLVM も ANTLR + JAVA でなくて BNFC + Ocaml or Haskell で書き直すことを考えています。

Min-Caml

http://min-caml.sourceforge.net/index7.html
http://min-caml.sourceforge.net/paper.pdf (tech paper)

[En]
Min-Caml is a simple, small, clean and efficient compiler for minimal ML language.
It is composed of just 2k lines, but many compiler features are included. Quite nice!

Min-Caml is implemented by ocaml, thus studying Min-Caml’s code is much useful for me to
implemente my MUDA language compiler(since MUDA compiler is implemented with ocaml for now).

[Ja]

Min-Caml すげぇ、MUDA は ML な言語ではなく GLSL な言語ですが、
Min-Caml のコードは MUDA を実装する上でとても役に立ちます。


vec f = a + b + c
if ((f + d).x < 0.0) {
    ...
}

な式を


vec tmp0 = a + b
vec f = tmp0 + c
float tmp1 = (f + d).x
if (tmp1 < 0.0) {
    ...
}

な感じにするのを、コンパイラの分野では K-正規化(K-Normal form) と言うことが分かっただけでも収穫です。