Syoyo Fujita's Blog

raytracing monte carlo

Month: September, 2008

Dow -777

dow-down-777-258.jpg

ダウ平均過去最大の下げ、777ドル安 金融安定化法案否決で
http://www.nikkei.co.jp/news/main/20080930AT2N2903R30092008.html

すげー!

でも下落率で考えると過去最大ではないのね. ブラックマンデーを越えていないのか.
(いや、いずれ近いうちに CDS が危なくなったらブラックマンデーを越える下落が発生しそうだけど)

# 今回はボラ低下のほうに bet していたので、レンダラ財団の資産は増えませんでした… 残念

必見

現在の金融状況を平易にしかし詳細に解説しています、必見です.

ウォールストリートの歴史的1ヶ月

http://wallstny.exblog.jp/8669144/

—-

harry_g さんのウォールストリート日記はいつもとても参考になります.
しかも常に内容のクオリティが高く維持されています.
私も見習わなければなりません.

Chocolate disco

2008-09-25-pefume-sbr2.jpg

う、うおおおおおおおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおおおおおお!!!!

こ、これはッ!!!
バフェットが GS に 50 億ドル出資よりもすごいことではッ!!

http://atmarkjojo.org/archives/2008/2008-09-25-001740.html

Optimizing noise function with MUDA

http://lucille.svn.sourceforge.net/svnroot/lucille/
angelina/haskellmuda/examples/noise/

mnoise2.jpg
(Turbulence by modified noise)

pnoise2.jpg
(Turbulance by Perlin noise)

After I wrote my first 4k raycasting demo(link), I found it is important to use procedural graphics technique, especially (Perlin) noise, for this area, so I decided to implement noise function in MUDA and optimize it.

Noise would be also important for shaders in offline renderer.

MUDAize noise function

Original Perlin noise is not suited for SIMD evaluation since it requires lookup of the permutation table.

Olano proposed fast, HW friendly, no-looup-table-is-required version of noise called modified noise [1].

My first attempt for optimizing noise function was SIMDizing this modified noise function by using MUDA language.

Memoizing

I don’t satisfy just implementing Olano’s modified noise function in MUDA. I am performance eager!

During I’ve been implementing modified noise in MUDA, I found one possible direction for further optimizing noise function is exploiting coherency.

Fortunatelly, I found there’s high probability that subsequent call of noise() has same integer part of input coordinate and most time consuming part is to getting gradient vector by hasing integer part of input coordiante. Thus getting rid of this coherency is good idea for further performance optimization.

Strategy is very simple. Storing previous result and reusing it unless integer part of input coordinate changes. This technique is called memoization in language community but it might be better to denote it cache which is well known word in graphics community.

Performance

I’ve measured performance for 4 versions of 2D noise function: Perlin noise(reference), modified noise(reference), modified noise(MUDA) and modified noise(MUDA + memoization) in 64bit environment in my Core2 Intel Mac(64bit binary is always faster than 32bit binary). Compiler used is llvm-gcc from LLVM 2.3.

mnoise2_perf.jpg

MUDA version of modified noise is about 2x fasther than reference non-SIMD vesion of modified noise. And adding memoization acheves about 2x performance boost further. In total, MUDA + memoization version is about 5x faster than reference version.

I’ve also compiled and measured previous work of SIMDized 2D noise function,

http://www.flipcode.com/archives/Perlin_Noise_Functions_SIMD.shtml

but unfortunately it is not so fast. SIMD version is as fast as it’s scalar version.
(33 M noise2/sec in my Core2 2.16 GHz single core, 64bit)

Think theoretically

MUDA version of modified noise in 2D case, mnoise2(), consists of 120 instructions per 4 noises(30 instructions/noise in average). If we assume one instruction is executed in one cycle, MUDA version of mnoise2() does not finish less than 120 cycles.

Under this assumption, let me calculate theoretical peak performance of noise function in my Core2 2.16 GHz machine.

2.16(GHz) / (120/4) = 72 M mnoise2/sec

MUDA + memoized version consists of 68 instructions, so in this case.

2.16(GHz/) / (68/4) = 127 M mnoise2/sec

Thus, compared with measured performance(51 M and 107 M respectively), performance of MUDA and MUDA + memoized version is not so different from theoretical peak performance.

To be honest, in x86 Core2, logical instruction(e.g. and, or) is executed with 0.5 cycles, so theoretical peak execution cycle is a bit lower.

Further optimization

Another direction of optimizing noise function is dynamically generate optimized noise function with Just-in-time compiling. This strategy would take effect when we optimize octaves of noise functions(e.g. turbulence).

This direction of optimization is TODO.

[Ja]

4k デモでは、どうしてもプロシージャルグラフィックスが必要になるので noise 関数を MUDA で最適化してみました. それにこれを最適化しておけば、オフラインレンダラのシェーダにも使えますし.

100 M noise2/sec 出るとはいえ…

MUDA + memo で 100 M noise2/sec 出せるといっても、1024×1024 画面全体で 4 octaves の turbulence を生成するだけけで 25 M noise2/sec = 25 M frames/sec となって、30 fps 出せないんだよね.

デモシーンとかでノイズをインタラクティブにレンダリングするなら、コアをさらに使うか、もっと別のアルゴリズムによる高速化手段を考えないといけないです.

あと、modified noise は perlin noise ほどランダム性がないですね. 結構周波数を高くすると repeatability が見えます. 周期を長くしてもダメみたい.

References

[1] Marc Olano. “Modified Noise for Evaluation on Graphics Hardware”. Graphics Hardware 2005.
http://www.csee.umbc.edu/~olano/papers/

MUDA 版 mnoise2 の objdump

大体 200 命令くらい(1 noise2 あたり 50 命令).

MUDA + memoize 版 mnoise2 の objdump

memo にヒットする場合は 100 命令くらいで実行できる(1 noise2 あたり 25 命令).

Language.C : A C99 library for Haskell

(via reddit.com)

http://www.sivity.net/projects/language.c/wiki/

Language.C is a C99 library for Haskell, and recent report says that Language.C can parse 18 million lines of pre-processed source without a hitch.


Parsing the Linux kernel with Haskell: experience with Language.C

[Ja]

Haskell の Language.C という C99 パーサ•解析モジュールが結構使えそう.

Linux カーネルのソースを、(プリプロセス後のソースに対して)問題なくパースできるほどの機能を持っている.
パーシングの速度は gcc の 3倍くらいかかる.

でも, たとえば C ベースのオレ言語作成とか、
C 言語になんらかの言語的ハックを加えたいという用途であれば、
速度はそんなに問題でないから、
これだけの C99 パース機能を持ったライブラリはとても役に立ちそうだと思う.

OCamler には, CIL という同じような C 言語をパースできるライブラリがあります.
これも結構良く出来ています.
ドキュメントを読むと、
「C99 パーサなんて二週間でできるべ、と思ってプロジェクトを始めたけれども甘かった、一年以上もかかってしまったよ、、、」
となんとも涙ぐましい.

さて Language.C ですが、
ちょっと試した感じではなんかパースした AST そのままをプリント(show)するのができないですねこれ.
ノードによっては Show できるのもあるけれども、すべてのノードが Show できるわけではない.
そのかわり pretty printer があるけれども、ほんとに pretty に表示するので元の C コードみたいなのが出力されるから解析目的のためのダンプに使えない.
AST そのまま表示というのがあればデバッグとか、C コードがどんな感じでパースされて木になっているのか分かりやすいのだと思うのだけれども.

ちなみに最近 Packrat parser や PEG(Parsing Expression Grammer) について調べていて、
Language.C がそのようなパース技法を使っていたら参考になるかなと思ったのですが、
Alex/Happy( C でいう lex/yacc) を使っていた(ので PEG の勉強の参考にならなかった).

—-

そういえば今更ながら hasell.org を見て知ったのですが、Haskell ってクレディ•スイスやドイチュバンクなどの金融で使われているのですね. ドイチュバンクはトレードソフトに使われているらしい.

OCaml も結構使われている( Caml trader ) し, だんだんと世の中関数型がやはり注目されてきているのかなぁと感じています.

VIX hits 42.16

いやー、またここ最近の金融方面は毎日がお祭りでした.
リーマン破綻、AIG 救済、メリル買収、GSE 救済、空売り規制、etc. etc
(どさくさにまぎれて?、NVDA は従業員 6.5% をリストラ)

VIX がなんと 9/18 日に 40 越えを記録しました!

vix.jpg

VIX は以下のページに解説があるように、投資家の恐怖心をインデックス(数値化)したものです.

http://chartpark.com/vix.html

http://www.option-dojo.com/column/2005_04_23.html

恐怖心といっても、たんに IV(implied volatility)を適当にコネコネして導出したものです.

http://www.cboe.com/micro/vix/VIXoptionsQRG.pdf

今はもう下がり始めているので、ひとまず嵐は収まったという感じでしょうか.

100 年に一回あるかないかの金融恐慌

グリーンスパン爺やが 100 年に一回あるかないかの金融恐慌と言ってますね.
(爺やは、サブプライムの原因の大きな部分を作ったと思うので、こうなることは分かりきっていたと思うのですが…)
http://mainichi.jp/select/today/archive/news/2008/08/01/20080801k0000e020015000c.html

まあ私としてはもう数ヶ月したらまたすごいお祭りがおきるんじゃないかなぁと思います.

いずれにせよ、今回の件により金融、マネーのありかたが決定的に変わると思います.
プッチ神父に言わせれば、株も資源もみーんな証券化で流動化して信用バブルになってしまった今の貨幣経済が一巡して、新しいマネーの定義による新世界に突入するという感じでしょうか.

# ボラが上がってくれたので、レンダラ財団用の資産もちょっとだけですが増えました 🙂

OoO 4th was over

OoO 第四回に参加いただいた皆様、ありがとうございました.
今回はいつもの二倍くらいの参加者で盛況でした.
bee さん効果 + SIGGRAPH 効果 + kioku さんデモシーン解説効果のおかげでしょうか.

kioku さん発表資料

kioku さんによる SIGGRAPH レポート + デモシーン解説の資料はこちらです.

http://kioku.sys-k.net/

とくに iq による4k デモの作り方は必見です.

↓これが 4k で出来ている. プロシージャル + シェーダで実現されている.
http://pouet.net/prod.php?which=51074

iq_4k.jpeg
(rgba_sidesix by Rgba)

My first 4k raycasting demo

4k.jpg

http://lucille.svn.sourceforge.net/viewvc/lucille/angelina/rt4k/

私からは、とりあえずやっつけで 1 日で作った 4k レイキャスデモを発表しました.
残念ながら反射までは手が回らなかった.
たんにレイキャスするのでは面白くないので、SIMD 言語である MUDA を使って高速処理できるようにしています.


-rwxr-xr-x   1 syoyo  syoyo  22972 Sep 15 23:24 a.out
-rwxr-xr-x   1 syoyo  syoyo   3903 Sep 14 01:18 exe4k

上が圧縮なしの実行バイナリで、下が muncho(バイナリパッカー) 適用後.
3903 バイトと、たしかに 4K 以内に収まっています.
mucho すげー.

しかし、これででも 4K に近いとなると、もうこれ以上機能は付けられないね…
どうがんばっても rgba_sidesix の品質まで持っていける気がしない.
4k デモシーナーの道はレンダラ野郎の道よりも険しいかもしれない.
iq のやつみたいにシェーダに走るしかないか…
(もしくは MUDA もシェーダみたいに、ランタイム別配布、4k 内には MUDA コードのみというのも手かも)

Reminder: OoO 4th

リマインダです.

9/14(日曜) 13:00-19:00 OoO 第四回 SIGGRAPH 2008 祭り
http://groups.google.co.jp/group/oooo_renderist/web/ooo–siggraph-08

今回、幾人かから、興味はあるけれども、「話についていけるか..」、「参加の条件がありますか…」 などの問い合わせをいただきました.
今回はオフラインレンダラに限ったネタでもないしそれほど硬派ではないので(bee さんの論文講演は硬派でありますが)、
通常の 3D グラフィックスに興味があれば誰でも参加できますし、楽しめると思います.
(それに硬派な内容でも「ボールグラフィックスは友達」と意識すれば十分なじめるはず)

逆に分からないことや質問, 進路相談(?)があればそれを持ってきていただけるのも welcome で、
世界最高峰(<- 日本最高峰でないことに注目)のグラフィックス野郎がお答えおよび手助けできると信じています.
(我々としてもレンダラ帝国建国のためにも、レンダラ、グラフィックスの裾野を広げるためにはどうするのがよいのか、どのように説明したら理解が容易になるのかなど、いろいろ広く意見を聞きたいのです)

4k demo at NVScene

OoO 第四回で kioku さんがデモシーンについて講演してくれます.
そのための予習をしておこう.
最近 nvscene というデモシーンが開催されました.
デモのリストはこちら.

http://www.pouet.net/party.php?which=1456&when=08

主に 4k demo(4096 byte のデモ) を予習(というか鑑賞).

1 位の Texas
http://pouet.net/prod.php?which=51448

こんなんどうやって 4k に押し込めているのかまったく理解不能(圧縮されているとはいえ).
しかもサウンドも 4k の中に含まれている! 人が作りし得るものとは到底思えない…

2 位の Receptor
プロシージャル.
http://www.pouet.net/prod.php?which=51449

3 位の Photon Race 2
これ SW リアルタイムレイトレだよなぁ. すげぇな.
http://www.pouet.net/prod.php?which=51443

4k demo オンリーじゃないけど、いろいろまとめ.

kioku さん率いる SystemK 作品

http://www.pouet.net/prod.php?which=51456

レイトレ反射? プロシージャルで無限ズーム?

http://www.pouet.net/prod.php?which=51438




はぁ、世界って広いなぁ…

おまけ

kioku さんに教えてもらった、mac 用 packer(バイナリ圧縮ツール) である muncho.

http://www.pouet.net/prod.php?which=51324

大体 1/10 くらいまでいけそうらしい. ~40kb くらいまでのコードが使えるということになる.
これなら私にも簡単なものなら作れそうだ.
OoO 第四回まで一日しかないけど、4k レイトレデモ作ってみようか…

Resolved: Curious x86 call instruction

the problem has been resolved.
call is used to get current PC(program counter, stored in eip register) address to access global symbol.

[Ja]

不思議な call 命令 ですが、幾人かの方からメールでご指導をいただけました.
ありがとうございます.

このような知りたい、答えたいをつなぐポータルみたいな仕組みがほしいなぁと常日頃思います.
Ask reddit みたいな感じかな.
たとえば私だったら GI だったらほぼなんでも答えられるので、
GI がよくわかんなくて困っているひとがそこで質問してくれれば、すぐさま見つけていつでも答えてあげられるし.
(そのやりとりをさらに他人が参考に見て知識が広がることにもなる)

さて、本題に戻って、call は PC(プログラムカウンタ)を取得するために利用されていました.
x86 では直接 PC(eip レジスタ)を読み出せません.
そこで call 命令で、スタックに call 命令のアドレス(に加えて call 命令の引数の値)をプッシュしてジャンプします.
ジャンプ先で pop ecx とかすれば、ecx レジスタに PC が入っているというわけ.
そして、大域変数へのアクセスのように、相対座標でしかアドレッシングできないような用途のための、
ベースアドレスとして使われます
(普通はバイナリは PIC なコードで、大域変数(bss, data)とプログラム(text)はメモリの自由なところに貼付けられることになるので、絶対座標ではアドレッシングできない).

gcc では、この call & pop で eip を得ることと同等のことを行う
__i686.get_pc_thunk という関数が用意されていて、場合によってはこれを呼ぶようになっている.
どのような基準で、この関数を呼び出すようになるのかそれとも call & pop を直接吐くのかは不明.
(-fPIC とかのオプションなのかなぁ)

ちなみに、今回の call は相対アドレスを引数にとる call 命令です.
Intel の x86 命令セットマニュアルを見ると、call は call でも絶対アドレスを取るものとかあって、
同じ call 命令でもやる内容が違うのでややこしい.

これを gcc -O2 -c でコンパイルします.ダンプしてみるとこんな感じ.

ecx には call & pop 後に 0x5 が入っているので,

movl 0x0000002b(%ecx),%eax

0x5 + 0x2b = 0x30 = data セクションの 0x40400000 = 3.0f = 変数 b

を eax にロードに、

movl %eax,0x0000002f(%ecx)

0x5 + 0x2f = 0x34 = data セクションの 0x40000000 = 2.0f = 変数 a

にストアになります.

実行バイナリを作って、gdb でも確認してみます.

ecx に、 call のアドレス 0x1fd0 に call の引数 0x5 を加えた 0x1fd5 が入っているのが確認できます.

しかしまだ不思議な点が.

プログラムカウンタ(eip)が基本的に不可視(明示的にアクセスできない)というのは x86 に限ったことではないのですが、
書き込みできるのはまずいとして、読み込みくらいならできてもいいと思うのですよね.
なんでできないのだろう…

さすがに x86 野郎もおかしいと思ったのか(?)、 この問題は x86-64 では改善されて、
プログラムカウンタレジスタをベースアドレスとして指定できるようになっています.
http://www.x86-64.org/documentation/assembly.html