Syoyo Fujita's Blog

raytracing monte carlo

Month: May, 2008

Dubai, the boiled city.

palmisland.jpg

沸騰都市 : ドバイ 砂漠にわき出た巨大マネー
http://www.nhk.or.jp/special/onair/080518.html

観た。
ドバイすげー.
スケールがすげー.
情熱と欲望がすげー.
「○○○○○○くん」のスケールの比じゃないね.

ホントに砂漠の上に都市ができてるよ.

「親が 10 年 20 年かけて貯めたお金を、私はすぐに稼いでしまった」

こういうのを見ると、やっぱり流れに乗った者勝ちだと思いますよね。

今なら金融と(資源)投資か。
それでいっきに稼いで、あとは道楽で自分のやりたいことを徹底的にやる
(レンダラ書き)をやるというのが、
やっぱり一番合理的だなぁと改めて認識。
Time is money.

「技術を貫く」
「好きなことを貫く」
「額に汗して働く」

は、financial literacy をすこしかじれば分かりますが、
非合理的で遠回りでしかないわけです。

そんなわけで、
投資による利益で将来のレンダラ野郎を金銭的にサポートするために、
レンダラ財団とレンダラファンドを本格的に稼働させたいと思っています。
こちらについては、いずれ詳しく。

ちなみに、「サブプライムとは何か」でおなじみの春山先生によれば、
ドバイはもうバブルが崩壊しているらしい.

http://www.doblog.com/weblog/myblog/17202/2621688

次のバブルに続く「流れ」はなんでしょうね。
ヒントは、インドとインドの人口、インフラビジネスにあると思う。

次回の沸騰都市はロンドンですか。こちらも楽しみ。

Advertisements

Weekly progress: ~11, May 2008

I’d like to report this week’s progress of syoyo’s activilty

– E-mail discussion with renderer writers in worldwide(almost everyday).

– Read few SIGGRAPH 2008 papers

– Played with Pure language
Pure is a functional language with LLVM backend.
I like it’s syntax and interoperavility of C language.

rsl2llvm
RenderMan Shading Language to LLVM compiler prototype project started.
rsl2llvm is written in Python.

– Implementing beam tracing
I’m continueing to write beam tacing and trying to combine it with visibility gradient.
Beam and analytic rendering will be the next-gen rendering tech(next to Monte Carlo rendering).

– held OoO(Offline meeting for Offline renderer writers)
It’s a secret meeting 🙂
We’ve discussed many offline rendering tech.

OoO 第二回参加ありがとうございました.

OoO 第二回に参加いただいた皆様、
ありがとうございました。

次回は 6 or 7 月を予定しています.

その頃にはそろそろ
– 今年の EG/SG 論文実装とか,
– ○○言語でレンダラ
– レンダラコンサルのアウトソース先
が本格的にできてくる頃になりそうだと感じています.

rsl2llvm, RSL to LLVM IR compiler

After some discussion with renderer writers in the world(All is done in English, indeed!),
I’ve decied to launch a prototype RSL(RenderMan Shading Language) to LLVM compiler project, rsl2llvm.

rsl2llvm is the prototype project to quickly find what will be the problem when we use LLVM as a shader VM and translate RSL to LLVM IR.

For quickly investigate the problem, rsl2llvm is implemented in Python: simple but powerful and productive language :). Initial rsl2llvm script code was written just in 3 days.

rsl2llvm is a prototype project, thus it’s goal is not to implement full-featured RSL compiler.
The goal is investigating LLVM’s potential for using LLVM as a shader VM, and summarize it into the document.

svn tree for rsl2llvm can be accessed at

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

(for browsing)

svn co http://lucille.svn.sourceforge.net/svnroot/lucille/angelina/rsl2llvm rsl2llvm
(for checking out)

I’ve also setup a discussion forum for rsl2llvm,

http://lucille.lefora.com/2008/05/06/rsl-llvm-compiler-project-started/

Any comments are welcome.

Another discussion of using LLVM for RSL is available at aqsis forum.
http://www.aqsis.org/xoops/modules/newbb/viewtopic.php?viewmode=flat&topic_id=1580&forum=2

[Ja]

レンダラコンサルの続きにもからんで、方々から、
「LLVM, シェーダの VM にいいんじゃね?」
「最適化 RSL interpreter の性能なめんな」
「LLVM の JIT には期待している.
lightspeed は制約が多いんだよ.
ぜひ lightspeed を上回ってほしい」
「こーすっといいんじゃね?でもやってみないとわからんね。」
というようなやりとりがあり、
「…じゃあやってみんべ」
という感じで rsl2llvm は生まれました.

うーん、しかしどんどんやることがたまっていくなぁ、
誰かにアウトソースしたいけど、
まあでもコイツならできそう、というアテが今の所は無いから、
(世界中のレンダラ野郎の誰もまだやっていないことばかりなので, 候補がいない)
結局はしばらくは自分が音頭を取ってやるしかない.

# というわけで OoO とかでどんどんレンダラ野郎を育成していきたいと
# いう思いだけは大きくなります.

Playing with Pure

http://pure-lang.sourceforge.net/

コンパイルが通ったのでちょっと遊んでみました.

Pure 言語とはなんぞや

Pure とは、和○○○○主演のドラマで,,, と
信頼関係のコントのネタに出てきそうですが、
そうではなくて、
項書換え(term rewriting)ベースの関数型言語です。
Pure 言語の開発者は、同じような特徴の言語として、
Q 言語をすでに開発していますが、
Pure 言語はそれの後継を目論んでいるようです.

Pure 言語が Q 言語と異なるところは、
先進的な言語的特徴を取り入れているところと、
LLVM バックエンドの採用で高速に実行できるところです.
(どんだけ高速に実行できるのかは不明)
また LLVM バックエンドを採用していることで、
C 言語との親和性も高いです.

とりあえず使ってみる

pure 言語は、かなり C 言語に似ています.
コメントは C/C++ と同じ //, /* ~ */ になっています.
また、式の終わりには ; が必要です.

PURELIB の環境変数が通っていないと、
式を評価してくれなかったり、サンプルが動かないので注意です.


$ pure
> square x = x * x;
> square 5;
5 * 5

$ export PURELIB=/path/to/pure/lib
$ pure
> square x = x * x;
> square 5;
25

system.pure 標準モジュールを使うことで、
標準 C 関数を使うことができます.


> using system;
> puts "The world!"
The world!
11
> puts "Time stops"
Time stops
11

最後の 11 は文字数でしょうか.


fact n  = n*fact (n-1) if n>0;
        = 1 otherwise;

if や otherwise のようなガードが後ろに記述され、
Pure では数式に近い書き方になっています。
Haskell などだと前の方に記述されますね。


fib 0 = 0;
fib 1 = 1;
fib n = fib (n-2) + fib (n-1) if n > 1;

まじめな再帰ベースの fibonacci コード。

python, Haskell でもおなじ再帰ベースの fibonacci を記述し、
fib 35 で速度を計ってみたところ,

Pure: 51 sec(JIT 込み)
Python: 16 sec
Python(+psyco): 1 sec
Haskell(runhaskell): 4 sec

でした、うむむ、fib では LLVM の恩恵はないようです.


> diff x (u+v)    = diff x u + diff x v;
> diff x (u*v)    = u*diff x v + v*diff x u;
> diff x y        = 1 if str x==str y;
>                 = 0 otherwise;
> diff x (5*x*x+2*x+10);
5*x*1+x*(5+x*0)+(2+x*0)+0

シンボリックな微分処理もお手のもの.

system.pure を見てみる

標準ライブラリである system.pure を見てみると、
以下のような定義を見つけることができます.


extern FILE* fopen(char* name, char* mode);
extern FILE* popen(char* cmd, char* mode);
...

うわっ、まんま C 言語だ.

list command

list というインタプリタの組込みコマンドで、
シンボルの情報がいろいろ見られる.
-d でLLVM IR のディスアセンブルコードも見れる.


> square x = x * x;
> list square
square x = x*x;
> list -d square
square x = x*x;

define internal fastcc ...

まとめ

– できたてほやほや. うぶうぶ.
– LLVM バックエンド
– C 言語との親和性
– 実装がコンパクト
– 数学的な書き方がしやすいと思う

言語的な特徴がよさげなのと、LLVM バックエンドということで、
しばらく注目してみたいと思います.

MCUDA: An Efficient Implementation of CUDA Kernels on Multi-cores

MCUDA: An Efficient Implementation of CUDA Kernels on Multi-cores
John Stratton, Sam Stone, Wen-mei Hwu
http://www.gigascale.org/pubs/1278.html

最近お気に入りの gigascale.org から

CUDA を CPU でも動くようにフレームワークを作ってみたよ、
CPU でも効率的にコードが動くことがわかったよ、
という論文。

効率は、チューンされた CPU コードを 1 とすると、
MCUDA でコードした同等のプログラムは 1/2 であったとのこと。
このパフォーマンスのロスは、データの局所化のセットアップなどの
余計な処理が原因のようです。

CUDA は G80 にべったりな仕様ですが、まあ言語自体は複雑ではないので
CPU にマップするのはさほど難しくないでしょう。
ただし論文が言うように、最適化の方向性は CPU と GPU では
すこし変わってきますね. でもそこはコンパイラで吸収できるでしょう。

ただ、CUDA の実行モデル自体がプロセッサでの実行に適しているわけで、
CUDA にうまくマッピングできるプログラムなら、
まあべつに MCUDA を使わなくても CPU でも効率に実行できるわけです.

とはいえ、同じコードで CPU でも GPU でも動くというのは
プログラムを書く方にとってはうれしいですね。
それにどうせ (GP)GPU はなくなるんですから、MCUDA があれば
GPU がなくなっても CPU にそのままスイッチできるという利点があります.

うーん、でも CUDA 化しやすいプログラムなんて、
実世界から見れば 1 割にも満たないと思うんですよね。
残りの 9 割のうちいくつかは、とても労力を使えば CUDA に合う
ようにはできると思いますが、投資に見合うリターンが得られる
とは思えません。

どんなアプリでも、とまでは必要ありませんが、
レイトレ, GI あたりのプログラム(二分木探索、incoherent 処理)
が自動で複数コアに効率よく実行してくれるような
並列プログラミングモデルが出てきてほしいところ.
(そんなわけで gigascale.org の他の研究に注目しています)

Abst 日本語訳

CUDA プログラミングモデルは、拡張 ANSI C 言語とランタイム環境であり、プログラマが明示的にデータ並列計算を行うことができるモデルです。

NVIDIA は、自社のグラフィックスアクセラレータのアーキティクチャを、より汎用的なアプリにも提供するために、CUDA を開発しました。

しかし、他のアーキティクチャでこのプログラミングモデルを効率的に適用することは行われていません。

本文では、効率的に CUDA プログラミングモデルをマルチコア CPU にマップする、Muticode-CUDA(MCUDA) について解説します。

本研究のおもな寄与は、、CUDA コードを標準 C 言語にソース-ソース変換し、並列実行向けのランタイムライブラリとリンクできるようにするプロセスです。

我々は MCUDA フレームワークを、GPU では高パフォーマンスに実行されることが示されているいくつかの CUDA アプリに適用し、マルチコア CPU のアーキティクチャでもこれらのアプリが高効率に実行できることを示します。
CUDA モデルで示されているコードのスレッドレベルの並列性、データ局所性、計算の等質性というものが、CPU アーキティクチャ向けにアプリケーションを手作業でチューニングしたときの利益の多くを実現することができます。

MCUDA フレームワークにより、データ並列のコードを単一のプログラミングモデルで記述し、CPU でも GPU でも効率的に実行できるようになります。

OoO 第二回開催通知

OoO グループの方には既に通知済みですが、
オフラインレンダラ野郎のためのオフライン勉強会、
通称 OoO の第二回を、以下のように開催します.

日時: 5 / 10 (土) 13:00 – 19:00
場所 : 恵比寿ガーデンプレイス SGI 株式会社様(31F)
集合: 13:00 B1F ホール(マックの隣)
http://www.sgi.co.jp/company_info/map1.html

お時間のある方はご参加ください.

「えっ!アレがアレするって!?」
というオフラインレンダラ界隈の動向が聞けたりするやもよ.

詳細はこちらへ.

http://groups.google.com/group/oooo_renderist/
web/ooo%20%E7%AC%AC%E4%BA%8C%E5%9B%9E%E9%96%8B%E5%82%AC%E9%80%9A%E7%9F%A5

Black-Scholes option calculation in MUDA

MUDA で Black-Scholes オプションプライシングの計算をやってみました.

http://lucille.svn.sourceforge.net/viewvc/lucille/angelina/haskellmuda/examples/BlackScholes/

参考にしたのは CUDA の SDK から.


static always_inline vec cndMUDA(vec d)
{
        vec A1 = 0.31938153f;
        vec A2 = -0.356563782f;
        vec A3 = 1.781477937f;
        vec A4 = -1.821255978f;
        vec A5 = 1.330274429f;
        vec RSQRT2PI = 0.3989422804f;

        vec K = 1.0f /. (1.0f + 0.2316419f * abs(d));

        vec cnd = RSQRT2PI * exp(-0.5f * d * d) * (K * (A1 + K * (A2 + K * (A3 + K * (A4 + K * A5)))));

        vec one_minus_cnd = 1.0f - cnd;

        vec ret = sel(cnd, one_minus_cnd, d > 0.0);

        return ret;
}

void BlackScholesMUDA(
        out vec retCall,
        out vec retPut,
        vec S,                  // Stock price
        vec X,                  // Option strike
        vec T,                  // Option years
        vec R,                  // Riskfree rate
        vec V)                  // Volatility rate
{

        vec sqrtT = sqrt(T);
        vec d1 = (log(S /. X) + (R + 0.5f * V * V) * T) /. (V * sqrtT);
        vec d2 = d1 - V * sqrtT;

        vec cnd_d1 = cndMUDA(d1);
        vec cnd_d2 = cndMUDA(d2);

        vec expRT = exp(-1.0f * R * T);

        retCall = S * cnd_d1 - X * expRT * cnd_d2;
        retPut  = X * expRT * (1.0f - cnd_d2) - S * (1.0f - cnd_d1);

}


[Perf] CPU = 57.740000 (msec) 13.855213 MOps/sec
[Perf] MUDA = 23.450000 (msec) 34.115139 MOps/sec

(on Core2 2.16 GHz, 64bit, using 1 core)

うーん、SIMD 化(MUDA 化)しても 3 倍程度ですね.

この BlackScholes 関数は put と call を同時に計算するので、関数は

34.11M / 2 = 17 M 回/sec

呼ばれていることになります.

理論 GFLOPS と比べると、

2.16 GHz * 4(SIMD) * 2(add/mul) / 17 M = 1016.5 flops / function

となります.

関数の disassemble 結果は約 560 instruction なので、
実行効率はピークの 1/2 程度ということになります.

ただ、今回の BlackScholes 関数は、1つの put & call の計算に必要な
演算子数(exp や log も 1 とカウント)はおよそ 67 個なので、
インストラクション数と大きなへだたりがあります.

この原因は、exp や log などの特殊関数によります.
CPU(SSE) ではこれらに相当する関数がないので、
SW で対応しなければりません.

MUDA では, ほぼ libm の結果と一致する特殊関数の実装を使っていて、
だいたい 1 関数あたり 100 ~ 160 インストラクションくらいかかります.

特殊関数を除いた BlackScholesMUDA 関数は、
およそ 135 instructions になり,
Mops/sec も 130 Mops/sec になります
(結果はもちろんリファレンスと一致しませんが)

つまり 3/4 ほどが、exp, log などの演算に費やされていることになります.
精度が必要なければ、特殊関数はより演算量の少ない近似計算に置き換えることもできますが、
すこし試してみたところでは誤差がひどかったので、今回は考えないことにしました.
(金融分野での利用ということもあり、そこそこの精度が必要だろうし)

特殊関数を除くと

特殊関数を除いたバージョンでも、265.85 flops/function となり、
135 instructions / function と比較すると、
理論ピークの半分くらいのパフォーマンスしか出せていません.
add/mul/mov 同時実行を考慮して、
ピーク値の 2/3 くらいは出るかなと思ったのですが.
演算部分ではなく、デコーダや帯域の部分がネックなのかもしれません.

GPU では

対して、g80 では 4.7 Gops/sec できると報告されています.
(ここでも、put & call を同時に計算するので ops の値は 2 倍)

1.35(GHz) * 128(SP) / (4.7 / 2) = 147 flops / function

SFU の flops も考慮する必要が本当はある(SPU はまた mul も可能)が、
ここでは考えないことにした.

対応する .ptx のコードは約 138 instructions.
SFU の演算量を考慮したとしても、
ほぼ理論ピーク値で実行できていると言えるだろう.

まとめ

– exp や log などの特殊関数の計算は、CPU ではネック.

今回の BS 計算の例題においては、特殊関数の計算は 3/4 を占める.
対して、GPU では HW 実装されているので効率的に処理できている.
(latency はちょっと大きいですが、pipeline 実行で隠蔽できているようだ)
ここが GPU が x100 とか x400 早いなどと、
理論 GFLOPS 以上の乖離が出来る原因と言えよう.

特殊関数がネックというのは、これは

Application Optimization and Performance Evaluation of a Multithreaded GPU Using CUDA

でも指摘されている.

– CPU は、理論 FLOPS に対して 1/2 程度のパフォーマンス

add/mul 同時実行はきちんと実行できるているのだろうか?
やはりインストラクションシミュレータがほしい.

– BlackScholes 計算が早いことの有益度は?

で、結局のところ、このような多量のインプットに対して classic な Black-Scholes
を計算する需要というのはベンチマーク以外にどれくらいあるのだろうか?

front トレーダーはたぶん financial cad とか使うだろうし,
algorithm trading や back office で使うにしても、
classic な Black-Scholes analysic 解なんていまさら dominant に使わないだろうし.

近年だと analysic に求められない option pricing のほうが
主要だと思う(バリアオプションとかね).

そんなわけで次やるとしたら, プレインバニラじゃなくて、
もうちょっとエキゾチックなやつとか、
MC(monte carlo) option pricing かな.

おまけ

金融 IT フォーカス 2008 年 4 月号
交通渋滞と株式投資
http://www.nri.co.jp/opinion/kinyu_itf/index.html

交通渋滞の理論と株式投資の理論には関連性があるのではないか、
というエッセイ.

日本も金融立国が叫ばれて久しい, というかそうしていかないとヤバいわけですが、
レンダラ(大域照明)と金融の融合ももっとあっていいような気がします.
すでに LDS とか関連項目はありますが, まだまだあっていいかなと.

大域照明が扱う関数は discontinuity ありまくりで、
株価でいえば $100 だった株価が次の日には $0.1 に、
その次の日には $100 などというような極端な株価推移をすることに
相当します(一方は関数は spatial, 他方は temporal という違いはありますが).

このような関数に対する研究は、金融方面にもなにか役立つと思うんですよね.
一応 jump を考慮した 株価モデルや option 計算モデルとか提案されているようですが、
まだまだ大域照明が扱っている関数はそんなヤワなもんじゃないよ、と.

The Pure Programming Language

The Pure Programming Language
http://pure-lang.sourceforge.net/

Pure is a functional programming language based on term rewriting. It has a modern syntax featuring curried function applications, lexical closures and equational definitions with pattern matching, and thus is somewhat similar to languages of the Haskell and ML variety. But Pure is also a very dynamic and reflective language, and is more like Lisp in this respect. The interpreter has an LLVM backend to do JIT compilation, hence programs run blazingly fast and interfacing to C modules is easy.

Seemingly quite impressive language.

– Can naturally describe symbolic computation
– LLVM backend! faster execution.
– The author from computer music field

I’d like to play with pure, but I’m get stuck in compilation err…

[Ja]

数学的なアルゴリズムをきれいに記述できそうな関数型言語.
symbolic な微分も記述可能(大体の関数型は記述できますが).

モダンな関数型言語の機能は大体取り入れているようで、
しかも LLVM バックエンドを採用.
コードは高速に JIT 実行できる(可能性).

うーむ、先進的だ.

実装コードサイズもそんなに多くなくてコンパクト(いまのところは).

グラフィックス用途においても、
アルゴリズム記述や関数型なシェーダの記述に
使っていけそうな気がする.

試してみたいけど、わたしの環境ではコンパイルがうまくいきませんでした.
ちょっとおあずけになりそう.

それにしても LLVM はだんだんと LLVM 帝国を築きつつある感がする.
XCode 3.1 beta (iPhone SDK) では llvm-gcc が提供されるようになり、
デフォルトの gcc コンパイラも llvm-gcc へのリンクになっている.
Leopard(と iPhone)の開発環境は全面的に LLVM に移行するようだ.

Adobe の flash も将来 VM には LLVM を使いそうな雰囲気がある.

スクリプト言語も、最初から LLVM への変換をネイティブで
行うことを考えて作られたものがそろそろ出てきそうな気がします.

Python の pypy とか, 既存のスクリプト言語を LLVM に変換する取り組みは
ありますが、いまいち無理している感があるんですよね.

ついでに、RSL(RenderMan SL) も LLVM にコンパイルするのどうよ、
という discussion も今しています.

http://www.aqsis.org/xoops/modules/newbb/viewtopic.php?
viewmode=flat&topic_id=1580&forum=2