Syoyo Fujita's Blog

raytracing monte carlo

Month: August, 2008

The Radium SDK: A real-time global illumination SDK

(via levelofdetail)

corridor.jpg

http://www.fantasylab.com/Radium/RadiumSDK.html

ポイントベースで GI 計算して、GI 効果をテクスチャベイク?とかできるゲーム向けツール。
作ったのは 元 N 社のひとが立ち上げた FantasyLab という会社.
基本的な考え方は GPU gems 2 で同氏が書いている手法らしい。

このようなビジネスモデル(ゲーム用 GI 計算ツール)はちょっと考えていたのですが、すでにやっているとこがあったのね。
まあこれでビジネスが成り立っているんだったら、私の…でも十分ビジネスとして成り立ちそうだなぁ.
先行例ということで参考にしよう.

ついでに lod さんのこの記事のコメントで知った会社と, Meridian と呼ばれるレンダラ.

http://www.sunfishstudio.com/software.htm

マイクロポリゴンでなくて、ポイントサンプリングでもなくて、エイリアスフリーでレンダリング可能、
ということで、まあビームのたぐいかなとおもって特許とか見てみたら、Interval Arithmetic を使ったやつでした.

たしかに Interval Arithmetic だったらそれなりにエイリアスフリーにできるけど、
いまだったらエイリアスフリーを目指すならビームや frequency analysis を使ったやつのほうがいいんじゃないかなぁと思う。
いずれにせよ patent が issued されてしまっているので、interval arithmetic レンダラは(特に商用では)うかつに書かないほうがよさそうだ。

Advertisements

LLVM 勉強会第一回参加ありがとうございました.

LLVM 勉強会第一回を開催させていただきました。

参加いただいた方、ありがとうございました.

当日の発表資料は、以下の URL にあります.

http://groups.google.co.jp/group/llvm_study/web/第一回+llvm+勉強会

第二回も、数ヶ月後あたりに開催したいと思います.
(第一回で蒔いた種が出てくるあたりに).

その後は、だんだんと LLVM を使った自動最適化(使わないのもありだけど)や JIT 技術などの方向にすすんでいきたいと思います.
(TraceMonkey とか出てきて JIT 技術もまた進んできていることですし。というか Andreas Gal すごすぎ)

formula: Social math equation service

Genki created amazing web service: formula.

http://formula.s21g.com/

With formula service, you can share your math equation, and more imporantly you can use beautiful LaTeX math equation in your blog, your site and wherever you want!
This is what I am long awaiting ever(Beautiful LaTeX math in my blog without tweaking the web server).

Here’s some sample equations shared by formula.

The rendering equation

The path integral formulation of light transport

Course notes on Beyond Programmable Shading

(via ompf.org)

SIGGRAPH 2008: Beyond Programmable Shading
http://s08.idav.ucdavis.edu/

Extra infos on Larrabee, and next-gen graphics techs(parallel computing framework, raycasting, etc)

Here’s my impression on these slides.

Interactive Cinematic Lighting

It’s a just review of previous works. There’s no impressive things.
I know existing research has a serious drawback(to be solved in the future work), but Fabio doesn’t talks on it.

Next Generation Parallelism in Games.

Raycasting seems interesting. I am also thinking about efficient ray traversal using octree.
I believe raytracing(ray traversal) could be done in much more faster using brilliant new data structure, compared to using current hierarchical-based traversal algorithm(e.g. kd-tree, BVH).

For example, review exising BVH raytraversal.
1 BVH – 1ray packet traversal requires 100~300 cycles on CPU.
And moderately complex scene requires 50-100 traversals for each ray(or ray packet).
5,000 ~ 30,000 cycles is too much, isn’t it?

Larrabee Graphics Architecture: Software is the New Hardware

Main memory is thousands of clocks away

Thousands of clocks!!!

When we assume texture miss rate was 5%(95% of hit rate), At least texturing requires 50 cycles.
The miss rate significantly raises when multi-texturing was used(10 ~ 30% of miss rate I guess).

Fiber can hide latency of texuring, but number of fibers are limited to size of L2.
So I don’t think Larrabee core hold many fibers to completely hide latency of texturing.

Beyond Data Parallel: Advanced Rendering on Larrabee

I am a bit disappointing on this course note. There’s no new insight on the future(beyond data-parallel). Pharr just reviews current problem & situation.

Compiler tech become more important beyond progarammable shading

I think compiler optimization technique is the most important thing in the future of graphics.

Thus now I am intensively doing a research on compiler technology.
Research focus on automatic parallelization and optimized use of memory hierarchy automatically, and found some quite impressive previous works.

I’d like to list up some of previous works which is not yet imported or unveiled to graphics community, but is much valuable.

Global Multi-Threaded Instruction Scheduling
GREMIO, the proposed method in this paper, automatically partition the sequential program and execute it on multi-cores or multi-threads.
You don’t need to write paralell code!

Efficient dynamic heap allocation of scratch-pad memory
Memory Allocation for Embedded Systems with a Compile-Time-Unknown Scratch-Pad Size

Effectively using scratchpad memory but programmers can write their code without knowing memory hierarchy explicitly. This will greatly reduce programmer’s effort.

PLuTo – An automatic parallelizer and locality optimizer for multicores

Application where PLuTo is applicable(nested loops) might not helpful for graphics apps, but with PLuTo, you no longer need to blockize data to improve memory access. PLuTo automatically do it!

Automatic Pool Allocation: Improving Performance by Controlling Data Structure Layout in the Heap

This is good for optimizing tree data structure for example ray traversal.
With this method, you now don’t need to think about optimal packing for BVH & Kd tree node for optimial cache usage!

Reorganizing lucille project management

It’s not yet finished completely but I’d like let you know I’m been reorganizing lucille project management.

lucille’s git repository

Firstly, I am moving source tree repository of lucille from subversion to git.
And git master tree of lucille is now hosted at github.

http://github.com/syoyo/lucille/tree/master

git repository is the newest source snapshot of lucille codebase.
You can clone(checkout) recent lucille source code from this site.

lucille project management with redmine

Secondly, we are launching the project management site for lucille with redmine project management tool.
Genki kindly hosts redmine on his site. I’d appreciate for his help.

http://redmine.s21g.com/projects/show/lucille

We are adding tickes, roadmaps, notes and documents of lucille to this site.
You can see our activity of lucille project much, much more clearer than ever.

lucille top site?

Finally, we are planning to launch new top site of lucille which is hosted on lucillerender.org at this time, but not soon.

Recently I am now busy implementing higly efficient beam tracing to lucille renderer core for noise free global illumination rendering: A big change which will be included into next release of lucille: 0.2(Plucinella).

You can browse&chase current implementation of beam tracing from here.
(Another good idea is to add lucille to your watch list on github)

beam.c
raster.c
bvh.c (beam-BVH traversal)

Once I’ve finished implementing beam tracing into lucille, I’ll design new top site of lucille, so that we can completely reorganize&renew lucille project management.

Intel AVX simulator is now available

http://softwarecommunity.intel.com/articles/eng/3848.htm

http://softwareblogs.intel.com/2008/08/11/emulation-of-new-instructions/

http://softwarecommunity.intel.com/articles/eng/3849.htm
(download)

Intel has released the functional simulator(i.e., not a cycle-aculate simulator) for AVX, which can also simulate full x86 instruction sets.

The emulator, Intel SDE(Software Development Emulator) is built on top of Pin: A binary instrumentation tool for x86.

Any realtime raytracing program targeting for x86 SIMD should use this simulator to accurately and statistically analyze the efficiency of the algorithm.

You can see some of my trials about the tool among the following Japanese text.

[Ja]

Intel から x86 シミュレータである SDE がリリースされました.
既存の x86 命令すべてに加えて、AVX 命令もシミュレーションすることができます.
SSE 命令ももちろんシミュレートすることができますので、既存の SSE アプリの解析にも使うことができます.
ただし、シミュレータは機能シミュレータです(サイクルアキュレートシミュレータではない).

SDE は Pin と呼ばれる x86 用のバイナリインストゥルメンテーションツールを利用して構築されていて、Pin だけでも役に立ちそうなツールです.

たとえばインストラクション数をカウントする命令を x86 バイナリに挿入して、実行時にトレースし、いくらインストラクションが実行されるか調べたり、ブランチの taken, not taken の率をカウントする命令を挿入することができます(試してないけどできるはず).
また、キャッシュシミュレーションなどもできるみたい.
drace のような仕組みのバイナリ版みたいな感じと言えるでしょうか.

使ってみる

まずはこんなコードを用意し、シミュレータにかけてみました.


#include 

void
mudatest()
{
    __m128 a, b, c;

    a = _mm_set_ps(1.0f, 2.0f, 3.0f, 4.0f);
    b = _mm_set_ps(0.1f, 0.2f, 0.3f, 0.4f);

    c = _mm_add_ps(a, b);
}

int
main()
{
    mudatest();
    return 0;
}


$ gcc -msse main.c
$ sde -mix -- ./a.out
$ cat mix.out

...
# TID 0
#       opcode                 count-unpredicated    count-predicated
#
     5 ADC                                     31                0
     6 ADD                                  11989                0
     8 ADDPS                                    1                0
    19 AND                                   1613                0
...

addps 命令が 1 個カウントされています.
これは期待どうりなのですが、つづいてログファイルにはアセンブラのトレース結果が記録されているのだけれども、そこには mudatest() の部分が見当たらない. どうもバイナリ実行のブートストラップ部分の命令数が多すぎて、そこでトレースするインストラクション数を越えてしまったようだ(デフォルトは 0xffff 個の命令をトレースするみたい).

mudatest 関数のアドレスを objdump で求めて、トレースを始める場所を指定するようにしてみる.


$ sde -mix -start-address 0x08048344 -- ./a.out
$ cat mix.out
...
XDIS 080483a6:  SSE 0F294588                 movaps xmmword ptr ss[ebp-0x78], xm
m0
XDIS 080483aa:  SSE 0F284D88                 movaps xmm1, xmmword ptr ss[ebp-0x7
8]
XDIS 080483ae:  SSE 0F284598                 movaps xmm0, xmmword ptr ss[ebp-0x6
8]
XDIS 080483b2:  SSE 0F58C1                   addps xmm0, xmm1
XDIS 080483b5:  SSE 0F2945C8                 movaps xmmword ptr ss[ebp-0x38], xmm0
...

今度はトレースの結果に mudatest() 部分がきちんと記録されている.

-debugtrace を指定すると、より詳細なインストラクショントレースができる.



$ spe -debugtrace -- ./a.out
...
0x080483ae /home/syoyo/src/sde-avx/a.out:mudatest+0x006a movaps xmm0, xmmword pt
r ss[ebp-0x68]
                XMM0 := 3f800000_40000000_40400000_40800000
                XMM0 (doubles) := 0.0078125 32
                XMM0 (floats)  := 1 2 3 4
0x080483b2 /home/syoyo/src/sde-avx/a.out:mudatest+0x006e addps xmm0, xmm1
                XMM0 := 3f8ccccd_400ccccd_40533333_408ccccd
                XMM0 (doubles) := 0.0140625 76.8
                XMM0 (floats)  := 1.1 2.2 3.3 4.4
...

レジスタの中身まで記録してくれる. これは便利ですね.
たとえば数値計算コードで、どこで Inf や NaN に計算結果が陥ってしまうかのデバッグに役立つと思います(gdb でもできるけどね).

AVX 命令のシミュレーション

では実際に AVX 命令のシミュレーションをやってみます.
現状まともに AVX 命令を吐ける C コンパイラはないので(gcc は svn から引っ張れば使えるかもしれない. icc は Q1/’09 リリース予定らしい),アセンブラ命令を書くことに.
最新 yasm は AVX 命令をサポートするので、yasm でアセンブルすることにしました.

1 からアセンブラを書くのもめんどくさいので、こんなコードをでっちあげました.


typedef double double4 __attribute__((vector_size(32)));

void
mudatest()
{
    double4 a, b, c;

    a = (double4){1.0, 2.0, 3.0, 4.0};
    b = (double4){0.1f, 0.2f, 0.3f, 0.4f};

    c = a + b;
}

int
main()
{
    mudatest();
    return 0;
}


これだと gcc が 2 個の addpd を吐くようにしてくれます. これを gcc でアセンブラに落としてから addpd の該当部分を vaddpd に書き換えるようにしてみました.


$ gcc -S avxtest.c
$ cat avxtest.s
...

...	movapd	-40(%ebp), %xmm1
	movapd	-72(%ebp), %xmm0
	movapd	%xmm1, %xmm2
	addpd	%xmm0, %xmm2
	movapd	-24(%ebp), %xmm1
	movapd	-56(%ebp), %xmm0
	addpd	%xmm1, %xmm0
	movapd	%xmm2, -104(%ebp)
	movapd	%xmm0, -88(%ebp)
...
$ vi avxtest.s      <- edit
$ cat avxtest.s
...
	vmovupd	-40(%ebp), %ymm1
	vmovupd	-72(%ebp), %ymm0
	vaddpd	%ymm0, %ymm1, %ymm1
	vmovupd	%ymm1, -104(%ebp)
...

これを yasm を通して elf 実行バイナリを作ります.


$ yasm -f elf -p gas -o avxtest.o avxtest.s
$ gcc avxtest.o

シミュレータでデバッグトレースさせてみます.


$ sde -debugtrace -- ./a.out
...
0x0804842a /home/syoyo/src/sde-avx/a.out:mudatest+0x00da vmovupd ymm1, ymmword p
tr ss[ebp-0x28]
                YMM1 := 40100000_00000000_40080000_00000000_40000000_00000000_3f
f00000_00000000
                YMM1 (doubles) := 4 3 2 1
                YMM1 (floats)  := 2.25 0 2.125 0 2 0 1.875 0
                                 Read 3fd99999_a0000000_3fd33333_40000000_3fc999
99_a0000000_3fb99999_a0000000 = *(UINT256)0xbf8711c0
0x0804842f /home/syoyo/src/sde-avx/a.out:mudatest+0x00df vmovupd ymm0, ymmword p
tr ss[ebp-0x48]
                YMM0 := 3fd99999_a0000000_3fd33333_40000000_3fc99999_a0000000_3f
b99999_a0000000
                YMM0 (doubles) := 0.4 0.3 0.2 0.1
                YMM0 (floats)  := 1.7 -1.0842e-19 1.65 2 1.575 -1.0842e-19 1.45
-1.0842e-19
0x08048434 /home/syoyo/src/sde-avx/a.out:mudatest+0x00e4 vaddpd ymm1, ymm1, ymm0
                YMM1 := 40119999_9a000000_400a6666_68000000_40019999_9a000000_3ff19999_9a000000
                YMM1 (doubles) := 4.4 3.3 2.2 1.1
                YMM1 (floats)  := 2.275 -2.64698e-23 2.1625 2.41785e+24 2.025 -2.64698e-23 1.8875 -2.64698e-23
...

ロードのアドレスを間違っているみたいで数値の並びがちょっとおかしい気がしますが、とりあえず add の値は期待するものなのでシミュレーション成功ということで.

まとめ

– 現状 C から AVX 命令を使うツールチェインがまだ確立されていないので、今 AVX 命令を試すならアセンブラで書くことに.
– AVX 以外でも、既存の x86 命令ももちろんシミュレートできるので、既存アプリのプロファイルツールとしても使える.
– リアルタイムレイトレとかで x86 実装をターゲットとしているのはこのようなシミュレータが提供されたことですから、シミュレータできちんとアルゴリズムの性能を測定すべきでしょう.

Larrabee paper review

http://softwarecommunity.intel.com/UserFiles/en-us/File/larrabee_manycore.pdf

読みました.
結論. 性能は微妙. レイトレアクセラレータロジックはなしのよう. 開発は楽なのが唯一の救いか.

Larrabee 構成概要

なんとも普通. そりゃ CPU メニーコアなので普通になりますね.

gather/scatter

VPU のインストラクションは L1 のアドレスをソースオペランドに取ることができる.

非連続アドレスからのロード(gather)と非連続アドレスへのストア(scatter)をサポートしている。
ただしキャッシュの速度に制限されるので、たとえばすべての要素が異なる場所を示していれば(データが L1 にキャッシュされているとして)最悪 16 サイクルはかかることになる。
ただし実際はそれなりにコヒーレンスがあるのでそれより少なくなるとのこと.

大域アドレス(仮想アドレス)に対する gather/scatter はできそうな記述ですが、atomic 操作とか考えるととても複雑になって実装が難しい気がしていますがどうでしょうか.

ベクトル演算命令は masked 実行あり。まあこれは普通ですね。ベクトルデータの load/store 命令でもベクトル要素ごとに mask をかけることができて, mask された要素はアップデートされないようにすることができるよう.こちらはたしかにあると便利.

GFLOPS

コア数は可変みたいだけど、たぶん製品として最初に出てくるのを考えると 16 コアの構成あたりが妥当そうでしょうか.
16 cores、1GHz, madd が 1cycle でできるとして、 

16(cores) * 16(vector width) * 1(GHz) * 2(madd) = 512 gflops

微妙なところですね(スカラ ALU の flops は dominant でないのでカウントしていません).

HWラスタライザ撤廃

この判断はいいと思うというか自然な流れですね。いまや HW ラスタライザ(とそれがあるためにレンダリングパイプラインが分断されてしまっている状況)は GPU の最大のネックですから。
ゲームなどは GPU レンダリングのパフォーマンスを出すために CPU で軽く
レンダリングしてから visibile なポリゴンを投入とか、deferred shading したりとラスタライザをなるべく経由しないようになっていますしね.

さらにポリゴンの密度がピクセルに近くなってきているのもラスタライザがネックになっている原因です. そろそろピクセルセントリックで処理したほうが効率的になりつつあります(その流れでレイトレ化という風にもなっています).

テクスチャは HW

テクスチャ処理は機能が決まっているわりに演算量が多い処理なので HW で提供というのは正しい判断です。Aniso filtering とか SW でやったらベラボーに時間がかかるしね.
 
ただ、演算コアから HW テクスチャユニットを使うには L2 を介して texturing コマンド(か特殊メモりアドレスへのアクセス?)を発行しないといけないので、テクスチャリングのレイテンシがでかそうなのが気になりますね。スレッディングとかで隠蔽はできますが、テクスチャリングのパフォーマンスを出すにはそのようなプログラミングが明示的に必要になりそうです.
テクスチャキャッシュは L1 相当の 32KB でその先はいきなり DRAM なのかな?
それだとマルチテクスチャリングしたときにキツいので、4MB のシェアードメモリの一部を L2 テクスチャキャッシュとして使えたりするのだろうか. でもそれだと 16 コア/4MB L2 の構成ができないから(256 KB x 16 = 4MB)、やはり 10 コア/4MB で一セットの構成になるんでしょうか.

半透明

フレキシブルな演算パイプライン構成だから半透明とかやりやすくなるとありますが、
帯域を考えるとよほど制約を与えないと使い物にはならない気がしています.

とはいえ、いずれにせよこれからのグラフィックスでは半透明、屈折, アンチエイリアスなどのなめらかで潤いのあるグラフィックス効果が重要になってくるはずなので、その流れを実現する一歩としてはいいかのかもしれません. 

レイトレ

1k x 1k, 4 Mray(eye ray + reflection) が、16 コアで 40 fps.
同じシーンを octa core CPU だと 12 fps.

レイトレ専用の HW ロジックも搭載しないみたいですし、
16 コア版で 4 倍程度(Larrabee 8 core なら 2 倍しかない)ということで
思ったほど Larrabee でレイトレというのはアドバンテージはないですね.

これだと普通に Larrabee 製品化時期の次世代の CPU で達成できなくもないレベルです.

Larrabee のレイトレ性能を理論値から計算してみますと、

512 Gflps / (41.16[fps] * 4 [Mray]) = 3,000 flops/ray

とレイあたり 3,000 flops. まあ RTRT の普通の CPU 実装だとだいたい数千 flops くらいでできると期待されますから(トラバース込みで)、flops レベルでは CPU 実装とあまり変わらないことになります。CPU が演算コアなので同等になるのは当然といえば当然でしょうか.

視覚的にリッチなリアルタイムレイトレを実現するためには 3T flops が必要と 10 年前にすでに予測されていますが[1]、私も [1] との計算方法は異なりますが 3T flops くらいが必要だと思っています.

たとえば 2k x 1k pixels, 60 fps 実現するとして, 120 Mpixels/sec 処理する必要があり,

3 [Tflops] / 120 [Mpixels] = 25,000 flops/sec

これだと 1 レイの処理に 2,500 flops をかけたとして, レイを pixel あたり 10 本処理することができます. これだけ処理できれば既存のラスタライズグラフィックス品質+αをレイトレで実現できるでしょう.

そんなわけで、3T flops を実現してレイトレプロセッサを謳うには Larrabee は 48 cores @ 2 GHz の構成にする必要があります. 第一世代でここまでの構成は、どうでしょうかね、なんとか実現可能かもしれませんが難しいところだと思います.

金融

たとえば単純な BlackScholes option pricing だと算術関数が一番のネックなので、これがアクセラレートされないとベクタ長やコア数のスケール以外ではさほど CPU との違いはない気がしています.

開発環境

既存の C/C++ 開発スタイルで開発できます. Larrabee Native というプログラミングモデルと呼ばれています.
それ以外でも、DX の compute shader とか Ct, SPMD スタイルも利用可能.
プログラマブルパイプラインの利点ですね.
また、演算コアでの printf とかもサポートするようなのでデバッグが楽にできます
(ただし printf などは host と通信する必要があるのでベラボーに遅くなるはず.
使うとしてもデバッグ用途だけにするのがよさそうです)

まとめ

性能は微妙ですが、開発が既存のモデルをそのまま大体使えそうという利点は大きい.

Larrabee がいきなり既存の GPU を置き換えるとかリアルタイムレイトレプロセッサとして使えるほどにはなれそうにありませんが(しかも実際に製品として出てくるにはあと 1,2 年かかることを考えると、さらに性能に疑問があります)、
たとえばオフラインレンダラの高速化などの、単なるプログラミングしやすい演算アクセラレータとして使うにはいいかもしれ
ません。

MUDA や lucille で Larrabee をサポートするのはどうするかなぁ… Intel の SDK の出来次第でしょうか. ’08 末あたりにはシミュレータが提供されはじめるみたいなので、それから考えることにします.

おまけ

しかし、論文はいかにもやっつけな感じですねぇ、、、特に図が.

Refernces

[1] 並列画像処理
http://www.amazon.co.jp/dp/4339025933

レンダラファンド設立のためのお勉強

レンダラ財団を設立•運営していくためにも、資産運用が必要だ.

投資•資産運用としてレンダラファンドを考えていて、これは
人材教育、レンダラ関連ビジネスへの投資、コンテンツへの投資、株•債券•証券への投資、etc..
などを行う予定でいる。

でも、ファンドってどうやって作るの?

そんなわけでファンドはどう作ればいいのか、どんなやりかたがあるのか、ということで
こんな本を読んでみました。

51wp3rlsvhl_ss500_.jpg

最新投資組合の基本と仕組みがよ~くわかる本
http://www.tokumeikumiai.com/news/book.php

投資組合というのはひとつのしくみだけで成り立っているのではなく、
投資の目的によって何種類かの投資組合の構成があることがわかりました.

今回のレンダラファンドをやろうとするなら、リスク回避(無限責任)を考えると、
たぶん匿名組合 + LLC を投資ビークルとしての構成にするのがよさそうだ 。

ただ、この組み合わせだと法人税を払わないといけないので、
投資組合の利点であるパススルー課税
(投資家の手元に行くまで利益に課税されない)
の恩恵を得られないという大きな問題がある.

もう少しハードルをあげれば SPC(特別目的会社)を使って
有限責任 + パススルー課税が実現できるみたいなんだけど、
これだとファンドの規模が大きくないといけないのでいきなり実現するのは難しそうだ.

あとは無限責任のリスクをとって任意組合にしてみるとか.

財団の運用母体なので, 利益を目的としないわけであって、
(利益を出さないという意味ではなくて、
利益を出しつつもそれを寄付や教育など社会的な目的に使うという意味)
その場合は上記以外の方法があるみたいで、
それだとパススルー課税化しやすいようだけど、
この一冊だけではちょっと解決できなかった。もっと調べる必要がある.

ちなみに、著者は投資組合の専門サイトもつくっています.
http://www.tokumeikumiai.com/

例のページにあるけど、
この投資組合のしくみは、企画ものへの投資とか、研究開発への投資とかにも使える。
レンダラ技術リサーチセンターみたいなのの設立にも使えそうですね.