Syoyo Fujita's Blog

raytracing monte carlo

Month: July, 2007

Load to MUDA. SIMD code generation, domain specific language, automatic optimization, functional programming, etc.

[En]

To realize my MUDA lanuage idea[1], I started research on portable SIMD code generation.
And I found a lot of and good previous work about it, and also find a keyoword to express such a research topic in that field.

The keyword to express MUDA is Domain Specific Language.

Domain Specific Language(DSL, from wikipedia)

DSL is a problem specific langauge. It isn’t a generic language, but useful for some problem to express it.
Usually DSL is implemented with LEX/YACC, ANTLR and functional programming langauges such like Haskell or Ocaml.

Here is some lists of previous works of SIMD code generation with DSL(or dynamic code generation) I found.

A Domain-Specific Language for the Generation of Optimized SIMD-Parallel Assembly Code
Christopher Kumar Anand, Wolfram Kahl.
SQRL Report No. 43.
http://www.cas.mcmaster.ca/~anand/papers/preprints.html

They reported how optimized tanh(hyperbolic tangent) function can be mapped to native codes
with DSL enbedded in Haskell.
They doesn’t uses SSE, but the idea can be valuable to code MUDA.

Page linked also contains a lot of interesting papers.

Efficient Utilization of SIMD Extensions
Franchetti, F. Kral, S. Lorenz, J. Ueberhuber, C.W.
Proceedings of the IEEE Special Issue on “Program Generation, Optimization, and Adaptation,” Vol. 93, No. 2, 2005, pages 409-425.
http://www.ece.cmu.edu/~franzf/publications.htm

This paper is a summary/survey paper on SIMD code geneation and automatic optimzation.
It includes a lot of pointers for this research topic, thus it’s a good paper to start with doing reaserch on
SIMD code genration and automatic optimzation.

CorePy
http://www.corepy.org/
CorePy doesn’t support SSE, but their design are useful for me to code MUDA language.
Writing efficient SIMD code with script language seems good.

FFTW
http://www.fftw.org/

Instead of statically optimized code, FFTW uses their FFT language and compiler for dynamic code generation and automatic optimizer for high perfomance FFT computation on various platform.
Performance of produced codes are comparable or overcomes vendor tuned FFT code.
Their FFT language and compiler is implemented with Ocaml.

Their technique is also published as below(see FFTW’s site).
Matteo Frigo and Steven G. Johnson, “The Design and Implementation of FFTW3,” Proceedings of the IEEE 93 (2), 216–231 (2005). Invited paper, Special Issue on Program Generation, Optimization, and Platform Adaptation.

SAC(Single Assignment C)
http://www.sac-home.org

SaC is an array programming language predominantly suited for application areas such as numerically intensive applications and signal processing. Its distinctive feature is that it combines high-level program specifications with runtime efficiency similar to that of hand-optimized low-level specifications

SAC provides their prerelease compiler for array based application and hosts a lot of research papers.

Conclusions at present

Playing with FFTW’s genfft might be a good point to start with
learning SIMD code generation technique.

And more, common language used in this research topic seem functional programming(FP) language, especially Haskell and Ocaml.
It would be a good time for me to learn FP language.
thus I decided, in front of playing with FFTW, I must learn about FP language. Ocaml for first, then Haskell.
(Because FFTW’s genfft uses Ocaml 😉 )

[Ja]

詳細は英語の方を見てもらうとして、まとめますと以下の通り。

– FFTW すげぇ。中身は結構 cutting edge なことやっているのね。FFTW の code は必読だ。
– MUDA に限らず自分の頭の中にあるアイデアを実現するには、やっぱオレ様言語(DSL)を作るのがよさそうだ。
一番費用対コストが高いのと、トータルでみたときの coding 時間の節約になる、気がする。
今まで何でもなるべく C で書いてきたが、実はいままでとても効率が悪いことをやっていたのではなかっただろうか。
– とにもかくにも Ocaml や Haskell を習う必要を感じた。論文のいたるところで関数型言語が出てくるし、
FFTW の FFT compiler が ocaml だし。
– というわけでまずは関数型言語の習得から…

[1] Idea: MUDA, MUltiple Data Accelerator language for high performance computing
http://lucille.atso-net.jp/blog/?p=322

Idea: MUDA, MUltiple Data Accelerator language for high performance computing

[En]

Note that this is just in idea phase.

Since I started to code my renderer lucille(it goes back to 2003), I’ve been lived a lot in SIMD world(AltiVec, then SSE).
I think most of my coding time for lucille was spent for coding SIMD(AltiVec, SSE) part(ray-triangle intersection, data reorganization for SIMD friendly manner and so on), not for writing light transport algorithm.
SIMDizing was needed for efficient rendering.

I tried to portablize SIMD part of my renderer lucille as many as possible.
I.e. cross-platform safe(win, linux, darwin), cross-compiler safe(vc, gcc), SIMD engine-safe(SSE, AltiVec).
but making that portable and maintaining it is terribly non productive and was a lot of waste of my time.
(But, at least, knowing SIMD architecture raised my skills for CPU architecture and optimzation)

After I scratched the surface of great compiler tools such like LLVM, ANTLR and Elsa/Elkhound,
One idea have struck to my mind.

How about to write my own vector language which generates portable SIMD code?
It would save a lot of my SIMD coding time.

The idea of my own vector language codenamed MUDA(MUltiple Data Accelerator) language is as follows.

– C like language

First of all, MUDA is just like a generator which emits native C code with SIMD intrinsics from GLSL like vector language,
so that it can be easily combinable to non-SIMDized C/C++ languge.


// MUDA code
// input.mu

struct {
    int    i;
    vec4 a;
    vec4 b;
    vec4 c;
} mystruct;

mystruct s;
s.c = s.a + s.b;

is translated to native C code


$ # mudah is the MUDA High performance compiler
$ mudah -engine=SSE2 input.mu

#ifdef __GNUC__
#define MUDA_ATTRIB_ALIGN(x) __attribute__((aligned(x)))
#define MUDA_DECL_ALIGN(x)
#else  // VC
#define MUDA_ATTRIB_ALIGN(x)
#define MUDA_DECL_ALIGN(x) __declspec(align(x))
#endif

// structs and members are properly aligned.
typedef struct MUDA_DECL_ALIGN(16) _mystruct {
    // all variables are aligned to 16 bytes aligned address
    // regardress of its data size.
    int i; int pad0[3];
    __m128 a;
    __m128 b;
    __m128 c;
}  mystruct MUDA_ATTRIB_ALIGN(16);

mystruct s;

s.c = _mm_add_ps(s.a, s.b);

In the future, it would be a good idea to convert MUDA code directly to native asm code(to ensure alignment more robustly than C code),
but It would require deep knowledge of compiler backend technique(scheduling, register allocation, etc.)
I have no such a knowledge for now, thus MUDA -> C code is the shortest way to realize my idea.
# MUDA -> LLVM would be another possible solution.

– NOT a parallel language

MUDA is targetting to generate portable SIMD code more easily and does not consider automatic workload distribution over multi-core and multi-thread.

For now, MUDA is just one of my idea to code portable SIMD code more easily.
There is a risk that this idea doesn’t come true or accomplished because of my lackness of compiler skills ,
but… wouldn’t you think MUDA is a good idea?

[Ja]

MUDA とは?

2003 年から lucille を書いている間、ずーっと、SIMD 部分のコードをなるべくクロスプラットフォームに、gcc, vc どちらでもコンパイルできるようにし、そしてうまく SIMD エンジンの違いはマクロなどでラッピングして SIMD を使うコードはポータブルになるように、としてきました。そしてほとんどの lucille のコーディングの時間はレンダラのアルゴリズムを書くよりも SIMD 化にかけてきた気がします(SIMD 化しようとするとデータ構造から設計しなおしになりますし、アラインの保証もしなければなりません)。

が、正直もうめんどいです。こんなことをするのは生産的でありません。しかもいずれどうせ SIMD は一時的なもので、さらなる multicore 時代ではスカラに戻るでしょうから、直接 SIMD コードを書くのは将来のことを考えると得策ではありません。
(CPU のアーキティクチャを知るという意味では、SIMD コーディングは有益な経験でしたが)

しかも、VC では関数の引数に __m128 を含んだ構造体(or union)を値渡しできないので、ポインタで渡すしかありません。ri_vector_add みたいな単純な関数でもそれを呼んでいるコードの引数には`&’ がいっぱいです。
あまりコードがエレガントでありません。
(AltiVec とか float[4] でも使えるようにしたいので、ri_vector_t という union を定義して SIMD 型を隠蔽している)

そこで、LLVM, ANTLR, Elsa/Elkhound を一通り知った後、GLSL みたいなオレ仕様 vector 言語をつくって、そこから SIMD intrinsics を含んだ C コードを吐くコンパイラ(ジェネレータ)を作ればいいのでは、と思うようになりました。

そのオレ様仕様 vector 言語を MUDA と名付けることにしました。

ポータブルな SIMD のコードを出力に特化しているので、
*UDA みたいに自動でワークを並列化するとか GPU で走るとかはしません。

まだアイデア段階なので、実装するかどうかも怪しいですが(RSLtoLLVM もまだ完成してませんしね)、
vec4 -> __m128 にするとか構造体にアラインマクロとかつけるくらいなら、
プリプロセスレベルでそんなに労力もいらなそうなので(それにいまのところその程度の機能で十分じゃないかなと思っています)、
そこくらいまではやるかも。

Distributed rendering project

[En]

‘Cell computing’ recently launched distributed rendering project called ‘sekigahara’.


http://www.cellcomputing.net/simple/index.php

(Written in Japanese)

They uses BOINC platform to distribute workloads to PCs over the internet.
Their renderer named “himawari” is written in Java and is a java ported version of an open source renderer.
The renderer seems distributed with workloads each time.

Distributed rendering on internet is exciting and challenging.

There is a problem to be overcomed(security, content protection, network traffic, etc),
but I think, in the future, studios and indivisuals might migrate to use such a distributed rendering platform as
fast and cheap render farm.

RT07 papers

http://www.uni-ulm.de/rt07/Program.html

[En]

Now list of RT07 papers is released!

There seems a lot of interesting papers. I can’t wait to read papers 🙂

[Ja]

RT07 の論文リストが発表されています。
今年もなかなか面白そうな論文が多そうです。

タイトルだけみて、気になった論文を挙げておきます。

– RTSL: a Ray Tracing Shading Language
おおついにレイトレ言語ですか。GLSL に trace() が追加されただけ、とかじゃないですよね…

– Sampling and Shading
セッション自体は RT^2 とあまり関係なさそうですが、リストされている論文自体は興味深そう。

– Towards Hardware Ray Tracing using Fixed Point Arithmetic
固定小数点にすることで、10倍高速化される、みたいな展開でも無い限り、
今どきハードウェアだからってわざわざ固定小数点を使うこともないような気もします。

– Realtime Ray Tracing on GPU with BVH-based Packet Traversal
BVH on GPU ですね。stackless kd-tree で地位を失った Slusallek 復権なるか?…

– Faster Ray Packets – Triangle Intersection through Vertex Culling
頂点カリングで交差判定? Reshetov なので、ラスタライザの機能は使わなそう?

– Deep Coherent Ray Tracing
もっとコヒーレンスを出す何かか?

PTLsim : a cycle accurate x86 simulator

http://www.ptlsim.org/

[En]

Wow, I found a very nice tool. An cycle acculate x86 simulator!
Except for AMD simulation tools(and this is closed source),
PTLsim is the only tool with full x86 cycle accurate simulation on the earth [1].

Many RTRT(RealTime RayTracing) papers should use this tool for their method for
*FAIR* and *ACCURATE* performance comparison.

I tried to compile this tool with my linux box, but I encounted some compilation errors such like
PAGE_SIZE define problem.
I’m combatting it …

[Ja]

なんと、x86 サイクルシミュレータを見つけました!

Intel はインハウスでは持っているだろうに、公にはこーゆーツールをださないし、
AMD は simlation tools を出していて太っ腹だけど、シミュレーションできる CPU は AMD 系だけなのと、
クローズドソースなので hack が出来ないというのが少し不満でした。

最新の Core2 などのシミュレーションはサポートしていないようですが、
とりあえず SSE 系がサポートされているのはうれしいところ。

これをレンダラなどの最適化の解析に使う以外にも、
たとえばコンパイラのオプティマイザを作るときに、
コンパイルしたコードをこのシミュレータで走らせて解析を取るとか、
時間をかけてもいいのでコンパイル時に裏でシミュレータを走らせて GA や
線形計画法などで最適なインストラクションスケジューリングをして最適なバイナリを作るする、
などできそう。

RSLtoLLVM でも、どれだけコンバートされた LLVM コードが最適に走るのかの解析にも
役立ちそうです。

# ちなみに、web を調べていると、どうもシミュレータ(やプロセッサ理論)の世界では
# alpha processor のシミュレータがよく作られたり使われたりするようです。

[1] There are other x86 simulators such like Qemu and Bocks, but they aren’t *CYCLE ACCURATE* simulator.

A Comparison of Methods for Generating Poisson Disk Distributions

A Comparison of Methods for Generating Poisson Disk Distributions
http://www.cs.kuleuven.ac.be/publicaties/rapporten/cw/CW459.abs.html

タイルサンプラー野郎 Ares Lagae [1] による貴重な Poisson disk サンプリング手法の比較レポートを読みました。

まずレポートでは、結論として、

– 一様密度なら著者が提案した corner based poisson disk tiles が最強!
– インポータンスサンプリングするならしょうがねー、 recursive wang tiles に軍配をやるよ
(RWT を一様密度に使うと corner based より分布は悪いけどね)

です[2]。

以下、各種比較した手法に対する著者の主張をまとめると以下の通り。

– ダーツ投げ(dart throwing)ç³»
遅いのでインタラクティブ系には使えない。[Jones 06], [Dunbar and Humphreys 06] は高速化手法を提案
しているが、それでも tile ベースの手法に比べれば遅い。また品質(半径)を上げようとすると Lloyd の緩和法
を使うことになってしまい、やっぱり遅くなってしまう。

– Tiled blue noise sampler [Hiller et al 2001]

品質が悪い(半径が小さい、スペクトル分布が悪い)ので勧めない。
タイルの境界と境界でないところで半径に差がある。

# 個人的には当時はこれ最強の blue noise sampler じゃね?と思っていましたが、
# 手法は常に古くなって新しいもので改善されていくものだなぁと実感。

– Penrose tile sampler [Ostromoukhov et al 2004]
– Recursive Wang Tiles [Kopf et al 2006]

どちらもスペクトルの品質は平均以下。
また、RWT の半径はおどろくほど低い。
RWT は一様密度に対しては使うべきでない。

私は [Hiller et al 01] でブルーノイズに出会ってから、Penrose tile sampler で衝撃を受けて、RWT, SWP で
さらに衝撃を受けてきました。

このサンプラーの分野はことごとく新発の手法が既存手法の欠点を明らかにし、それらを改善する手法が提案されてきました。
この分野ほど、毎年のようにその当時まで最強のサンプラーだったものが、
差分レベルではなくほとんど完全に新しい提案手法で更なる最強のサンプラーに
ドラマティックに塗り替えられていくのは、なかなか他の CG 分野でもなかったのではないか思います。
(SHexp までの PRT はこれに近いものがありますが)
この激動の(?)最強サンプラー合戦時代をリアルタイムで目の当たりにすることができて、
私はとても運がよかったと思います。

[1] http://www.cs.kuleuven.be/~ares/
[2] このレポートが出たのは Sampling with Polyominoes が発表されるまえであることに注意。
一様分布の場合に SWP と corner based ではどちらがよいかは調べてみる必要がある。

[Jones 06] Thouis Jones, Efficient Generation of Poisson-Disk Sampling Patterns.
http://people.csail.mit.edu/thouis/

[Dunbar and Humphreys 06] Daniel Dunbar and Greg Humphreys, A Spatial Data Structure for Fast Poisson-Disk Sample Generation.
http://www.cs.virginia.edu/~gfx/pubs/antimony/

[Hiller et al 2001] Stefan Hiller, Oliver Deussen and Alexander Keller, Tiled blue noise samples.
http://citeseer.ist.psu.edu/493970.html

[Ostromoukhov et al 04] Victor Ostromoukhov, Charles Donohue and Pierre-Marc Jodoin 2004, Fast Hierarchical Importance Sampling With Blue Noise Properties.
http://www.iro.umontreal.ca/~ostrom/publications/

[Kopf et al 2006] Johannes Kopf, Daniel Cohen-Or, Oliver Deussen and Dani Lischinski, Recursive Wang Tiles for Real-Time Blue Noise
http://johanneskopf.de/publications/blue_noise/

compiler things 1

Recently I’m seeking, finding and reading compiler things(tools, tech docs, papers and so on)
for constructing my (to be quite efficient) shader compiler.

I’ll list compiler thinks I found last week.

最近は効率的に、かつ効率的な RSLtoLLVM シェーダコンパイラを作るためと [1]、
それができるんだったらついでにシェーダに限らずなんか gi 言語とかハイパフォーマンス重視の SIMD 用に特化した
言語とかのコンパイラも作れそうだなと考えて、コンパイラねたでいろいろ web を漁っています。
紹介程度ですいませんが、先週みつけた役に立ちそうなコンパイラねたやツールとか。

– Sequoia : Programming the Memory Hierarchy
http://www.stanford.edu/group/sequoia/cgi-bin/

Hmm… the next of brook?
Explicitly specify memory hierarchy seems good, but the task should be self contained is still inconvienient.

メモリ階層を考慮したプログラミング言語らしい。ただしコアな処理の単位は独立していなければならないという点でいままでの GPGPU 言語とかと同じ。これだったら正直 CUDA の方が global メモリでランダムアクセスできる分、楽でいいと思う。

– Elkhound : A GLR Parser Generator
– Elsa: An Elkhound-based C++ Parser
http://www.cs.berkeley.edu/~smcpeak/elkhound/

For those who want to write C/C++ based custom language?
It convertes C/C++ to AST, quite good.

Sequoia is implemented using Elsa.

Sequoia が実装に使っていると書いてあったので知りました。Elsa は C/C++ のパーサ。AST を作ってくれる。
C/C++ ベースのコンパイラを作りたくなったら、 elsa を持ってきてちょこちょこっといじればいい?

# C/C++ フロントエンドに gcc を使うのも手ですが、あそこまで巨大になられると
# 軽い程度に手を加えるのは困難な気がする…

しかもなんと! 裏技?で型チェックや C/C++ の整形(足りないものも追加)もしてくれる.すげー.



$ cat test.cpp

class Mudah
{
  public:

        Mudah() {}
        ~Mudah() {}

};

$ ~/src/oink-stack-2006-08-31/elsa/ccparse -tr prettyPrint test.cpp

typechecking results:
  errors:   0
  warnings: 0
%%% progress: 0ms: dsw pretty print...
---- START ----
// -*-c++-*-
class Mudah {
  public:
inline Mudah() {}
  inline ~Mudah(/*m: class Mudah & */ ) {}
  inline Mudah(class Mudah const &__other) {}
  inline class Mudah &operator=(/*m: class Mudah & */
                                  class Mudah const &__other) {
    return (* (this));
}
};
---- STOP ----
%%% progress: 1ms: dsw pretty print... done
parse=2ms tcheck=4ms integ=0ms elab=0ms

プリプロセッサは実装されていないようなので、
プリプロセッシングは別途既存のコンパイラで行う必要があることに注意。

– Cqual : A tool for adding type qualifiers to C
http://www.cs.umd.edu/~jfoster/cqual/

いろいろ静的型チェックをしてくれるらしい。

– Oink : a Collaboration of C++ Static Analysis Tools.
http://www.cubewano.org/oink/

elsa/elkhound/cqual seems merged to this oink project.

elsa/elkhound/cqual はこの oink に統合されたようです。

[1] LLVM IR(中間言語) は実は SSA 形式だったので、ANTLR の tree grammar のアクションとテンプレートで
お気楽に LLVM 出力するべ、という手法が使えないことが発覚しました。
そこで AST をどううまく SSA のコードに書き直すのがいいのか調べているところです。

Will most video games be ray traced in 2012?

Let’s vote at Pete’s blog!

Will most video games be ray traced in 2012?
http://psgraphics.blogspot.com/

The Japanese book published at 1999 [1] analyzed that real time raytracing
for moderately realistic(i.e. not only for eye rays and 2ndary reflection rays!) and
large scale scene needs 3T FLOPS computer.

3T FLOPS CPU(or CPGPU?) on commodity PC could be easily available at 2012, thus
ray traced games by 2012 seems make sense.

But by reading recently publishied RT^2(real time ray tracing) papers, I think
there needs more FLOPS. I suppose it should be 10x’ed. i.e. 30T FLOPS.

Recent papers show RTRT can render moderate dynamic scene with 1024×1024@30 fps
on 100~200 GFLOPS CPU or GPU.
But it renders just eye rays or a bit more(specular reflection) and no enough
indirect illumination.

I estimate that moderately high quality RTRT(and thus it can be used for video games)
will require 100x boost against current RTRT performance, without
any drastic innovation of RTRT algorithm.

“high quality” includes anti-aliasing, indirect illumination and so on.

I must apologize that I can’t prove this magic number(100x and 30 TFLOPS) concretely [2],
but I think I’m not missing the point.

[1] 並列画像処理
http://www.coronasha.co.jp/np/detail.do?goods_id=1282
たしか 3T flops だったと思う。

[2] とりあえず サイクル数 per 1 交差判定, サイクル数 per 1 ノードトラバーサルは分かるはずなので、それが分かればあとはだいたいどれくらいの FLOPS が必要かの予想はできます。

bakefile

http://www.bakefile.org/

XML で記述されたルールから、GNU Makefile, autoconf, nmake, VC project などの
各種メイクファイルを生成するツールです。

lucille は主にビルドツールは autoconf/automake を使っていますが、
コンパイルオプションをちょこっと変えて再ビルドするときでも毎度アホみたいに遅い configure
(キャッシュを使っても)を走らせなければならないのがイケてないので、
手書きの Makefile に変えようと思っていました。

ただ、Makefile は直接手で書くと依存関係の記述がめんどくさいので、なにかいいツールは
ないかと探していたときに、この bakefile を見つけました。

bakefile を使えば、windows でビルドするときの nmake なども別途書かずに済むので
よさそうです。

バージョンは 0.2.2 ですが、wxWidgets などの大きめのアプリケーションでもこの bakefile が
採用されているので、機能面では問題なさそう。

少し試してみて、よさそうなら lucille のビルドツールに採用したいと思います。

Tile-Based Methods in Computer Graphics

Tile-Based Methods in Computer Graphics
Ares Lagae.
PhD thesis.

http://www.cs.kuleuven.be/~ares/

[En]

I’ve found another tile sampler guy(you know, most famous tile sampler guy is Prof. Ostromoukhov[1]).
I don’t yet read this Ph.D. thesis, but I *COULD* feel it would be great thesis.

[Ja]

タイルサンプラー野郎といえば大御所ビクター先生 [1] ですが、さらなるタイルサンプラー野郎を見つけました [2]。
タイルサンプリングで Ph.D. thesis か、、、
まだ読んでいませんが、これはすごそうな雰囲気を感じとることができます。

ポワソンディスクサンプリング方法の比較の章が特に興味深そうです。

[1] http://www.iro.umontreal.ca/~ostrom/
[2] オリバー先生もいますね。