Syoyo Fujita's Blog

raytracing monte carlo

Month: December, 2007

Houdini 9 apprentice

http://www.sidefx.com/index.php?option=com_content&task=view&id=589&Itemid=221

Houdini apprentice … Free
Scripting … OK
HDK(dev sdk) … OK

Hmm… model a scene with this Houdini apprentice,
then dump a scene data with python script or file out chop,
render it with my lucille renderer,
would be possible?

[Ja]

無償,
python スクリプティング可能、
dev sdk も使える…
制約は、レンダリングだけ?

これってもしかして自分で RIB エクスポータ書けば、
モデリングデータをエクスポートして、
lucille でレンダリングさせることができるってこと?

file out chop も自由に使える?

もしそうなら、テストシーンデータ作成に houdini を
使うのを本気で考えたい.
それってつまり、シェーダ作成などの op ネットワークエディタが
タダで使えるということになるのだから.

Automatic SIMD optimization

I’ve started to carefully reading “Efficient Utilization of SIMD Extensions” [1].

This paper is a good starting point to survey automatic SIMD vectorization.

According to this papar, automaic SIMD vectorization is roughly separated into 3 layers.

1. Symbolic vectorization
Do vectorization in language or application context level.

2. Straight line code vectorization
Find a coherence in scalar code path and vectorize it?

3. Special purpose compiler for vectorized code.
Custom instruction scheduler and register allocator for vector instruction for fast binary code generation.

So far, MUDA doesn’t do any optimizations shown above.

I’d like to find a way to incorporate MUDA with optimization like layer (1).
For layer (2), I think there is nothing to do for MUDA, since MUDA is a vector language already.
Layer (3) is very low-level and seems machine-dependent technique, thus I’m left it for now.

Much more information on automatic SIMD vectorization this paper is discussing, especially (2) and (3), can be found at [2].

[Ja]

… [1] をきちんと読みはじめているのですが、、、[1] も [2] もすげぇや…
ほんと世界は広いなぁ、勝てねぇなぁ…

コンパイラ最適化の分野は新参者なので、
こういう情報が(じぶんがやろうとしていること)なかなか耳に入ってこないから、
手探りでやったり車輪の再発明ばっかりして、よくよく調べてみると n 年前に
もう誰々がやっていて論文になっていた、というのばかり…

こんなことで時間を無駄にしているから、インド人にどんどん越されていくのですね。

なんとか MUDA も形ができはじてきたので、これを掲げて、
論文の著者とかそれらしきものを知っていそうな人物に、こーゆーことやりたんだけど、
どうすればいいの?と聞いてまわっていくことにしてみようか。
あまり深入りすると、本質のレンダラ開発がおざなりになりそうなので、
そこは調整しないといけない。

[1] Efficient Utilization of SIMD Extensions
Franz Franchetti, Stefan Kral, Juergen Lorenz, Christoph W. Ueberhuber. Invited paper
http://www.ece.cmu.edu/~franzf/papers/ieee-si.pdf

[2] Automatic SIMD vectorization
Jourgen Lorenz, Ph.D thesis
ftp://ftp.vcpc.univie.ac.at/projects/aurora/reports/auroratr2004-03.ps.gz

Faust, Signal Processing Language

http://faust.grame.fr/

The name FAUST stands for Functional AUdio STream. Its programming model combines two approaches : functional programming and block diagram composition. You can think of FAUST as a structured block diagram language with a textual syntax.

– Functional programming
– block diagram composition

OMG, This is what I am thinking about core features necessary for coming GI era’s GI language(shader + raytracing + MC sampler).

Faust already did it for their DSP application… the World is wide…
I must investigate their language design to rethink about my GI language(possibly MUDA based) idea.

It seems that Faust supports SSE and AltiVec code output, and more,
are trying to implement LLVM backend. Cool!

http://www.grame.fr/~letz/faust_llvm.html

Apple shares hit $200

http://finance.google.com/finance?chdnp=1&chdd=1&chds=1&chdv=1&chvs=maximized&
chdeh=0&chfdeh=0&chdet=1198789200000&chddm=98141&q=NASDAQ:AAPL

ポカーン….

「天才数学者はこう賭ける」
http://www.seidosha.co.jp/index.php?%C5%B7%BA%CD%BF%F4%B3%D8%BC%D4%A4%CF%A4%B3%A4%A6%C5%D2%A4%B1%A4%EB

「ウォール街のランダム・ウォーカー」
http://www.amazon.co.jp/dp/4532350972

のような本に 2002 年ころに出会っていれば…
いままでの自分の financial literacy のなさが悔やまれる…

2008 年は、lucille 0.2 もそうですが、
レンダラ財団設立のための資産形成も考えていきたい。

Performance Counter Super-Resolution

Performance Counter Super-Resolution
http://www.spiral.net/software/perfcount.html

super-resolution.gif

This idea seems good.
Commodity CPUs has precise HW performance counter facility,
but when using it, it has a side effect on measured program.

Increasing the sampling rate also increases
system bus accesses, memory accesses, etc to transfer sampled data,
which affects behavior of application running(measuring),
resulting in poor and inaccurate profiling.

Intel’s VTune have a recommended lower bound of one millisecond as the minimum interval in between taking counter measurements to constrain the impact of these two types of error.

I wondered that VTune’s sampling interval is too sparse(msec order),
In such a coarse sampling rate case, short function are easily missed in result sampling data.
But I understand it should be so, according to quotes and the link info.

Usually we(performance eager) want to profile program’s behavior in
100~1000 cycle accurate order for such a profiling purpose.

The idea using super-resolution techniques may solve such a problem.

Super resolution profiling,
i.e. running your app(measured function) multiple times with low frequency but assign unique jittering,
then assembling it to get one high frequency profiling result,
may gives more accurate sampling using HW performance monitor facility.

I’m considering to support such a HW sampling techniques for MUDA optimization platform.
For example, running oprofile profiler multiple times with different start time jittering.

[Ja]

画像処理技術(というよりは信号処理技術か)の応用例がこんなところにもあるのですね。

lucille 0.2 plan

Here I wrote a plan for lucille 0.2, next version of luiclle.

lucillenext_pdf.png
lucille_next.pdf

In 2007, I tought really a lot and a lot about lucille.
How to make lucille faster, more robust and beautiful.

I’ve been collected building blocks for it,
and now I confirms I got all building blocks to realize
my new idea, as presented in the lucille 0.2 plan.

Coming 2008, I’ll turn my plan into the action, one by one, and steadily.

New MUDA developer!

I’m so glad to introduce new MUDA developer, Luca Barbato.

http://dev.gentoo.org/~lu_zero/

He is a cool SIMD-ist on PPC/AltiVec and did many SIMD optimization contribution for another projects.

Now he is contributing VMX(AltiVec) backend for MUDA language, and will contribute Cell/SPE as well.

Thanks a lot, Luca!

About MUDA

MUDA is a vector language for CPU.

MUDA site is here http://lucille.sourceforge.net/muda/

And for past posts on MUDA, see,

http://lucille.atso-net.jp/blog/?p=385

MUDA project on Launchpad

I’ve also launched MUDA project on Launchpad.

https://launchpad.net/muda

Launchpad provides some facility missing on sourceforge.net.
For example, managing translation and Q&A.

And also Launchpad provides cutting edge Bazaar VCS(Version Control System) for hosting codebase.

I’m considering to host MUDA codebase on this Bazaar VCS, instead of sourceforge’s svn.

How To Write Fast Numerical Code: A Small Introduction

How To Write Fast Numerical Code: A Small Introduction
Srinivas Chellappa, Franz Franchetti and Markus Püschel
to appear in Proc. Summer School on Generative and Transformational Techniques in Software Engineering, Lecture Notes in Computer Science, Springer, 2008

http://spiral.ece.cmu.edu:8080/pub-spiral/abstract.jsp?id=100

とりあえず MUDA という SIMD 言語を作ったりしているものの、
この article でも示されているように、最適化で一番重要なものを上から並べると、

– 効率的なアルゴリズム
– メモリアクセス(キャッシュまわり)
– 最後に、SIMD 化

になるわけです。結局のところ、小手先の SIMD 化というのは、実はあまり効果がないのです。

アルゴリズムの改善

まずアルゴリズムを改善することが一番重要。
悪いアルゴリズムをどんなに最適化しても、効率の悪いパフォーマンスしか実現できない。
効率の良いアルゴリズムは、どんな小手先の最適化にも勝ります。
そして効率の良いアルゴリズムをさらに SIMD 化などで最適化すれば、
大きな処理効率の飛躍が望めます。
ただ、アルゴリズムを考えだすのには頭をとっーーーても使う。
(でもインド人に勝つためには、こういう知的生産を行うべきなのです)

考えて考えて考えて、でも効率の良いアルゴリズムが見つからないか、
もうこれでいくと決めたら、次のメモリアクセスの最適化へ進みます。

メモリアクセスの最適化

最近の CPU は、キャッシュミスするとレジスタアクセスのサイクルにくらべて容易に
10~100 倍以上のサイクルストールしてしまうわけで、
SIMD 化で演算効率 4 倍に比べたら、メモリアクセス周りを最適化して
キャッシュミス率を減らしたりメモリアクセスの局所性を高めたほうが
よっぽど効果があります。

# ちなみにこれは x86 などの一般的な汎用 CPU でのお話です。

SIMD 化

で、アルゴリズムもメモリアクセスもどーしても改善できなかったら、
最後に SIMD 化です。

そう、本来なら最後に SIMD 化するべきなのです。

でも多くの場合、まずは SIMD 化から、というひとが多いのではないでしょうか?
(私もそうでした)

アルゴリズムやメモリアクセスに比べて、SIMD 最適化は直感的に分かりやすい(気がする)のと、
実現(コーディング)の障壁も低いからなのでしょうか。

しかし、CPU 依存性が大きいので、ポータブルでない。
コンパイラの自動ベクトル化も、十分ではない。
SIMD 化では、データ構造から根本的に変えないと、効果が出にくいから。
(私は将来の CPU では SIMD unit は無くなると思っています.
理由はスカラコード + マルチコア化のほうがやりやすいからです.
なので SIMD 化には拘らないほうが長期的にはよいと思います。
そんなことよりアルゴリズムを考えようということです)

それに、SIMD 化なんて、ちょっと覚えればあとはサルでもできるわけです。

こんな非生産的で知的生産性がないところでうろうろしていたら、
インド人に容易に追い越されちゃう。

なので MUDA ではそんな非生産的なコーディング時間を減らしたい、
という意味合いもあります。

かなり抽象的なお話になってしまいました。
個人的な経験則に基づく割合が多いので、あまり説得力はないかも。

いずれにせよ、そんなわけで、MUDA では、 SIMD 化をするだけではなく、
メモリアクセスの最適化もそれなりに自動に出来る仕組みに拡張したいなーと考えています。

さすがに汎用的に効率的なアルゴリズムを発見して最適化を行うみたいなことは無理だと思うので、
アルゴリズムの自動最適化というのは考えていませんが。

そしていまは手作業でトライアンドエラーでやっているような最適化のサイクルを、
automate できるフレームワークを作る、という方向性を目指したい。
いずれにせよ、インド人に勝つためには、我々日本人は生産性を上げるしかないわけで、
このような道を進むしかないのですから。

まずは SPRAL や ATLAS あたりの仕組みを調べてみるのが役に立ちそうでしょうか。

MUDA site opens!

http://lucille.sourceforge.net/muda/

I’ve launched MUDA project page! Check it.

MUDA is a vector language for CPU.
Yeah, not for GPU or (dead and gone) GPGPU 😉

I’m planning to use MUDA to code core computation part of my lucille renderer.

[Ja]

日本語のサイト(ドキュメント)も作るのはめんどくさいのでやりません.
そんなことして時間を浪費していると、インド人にどんどん越されるてしまうので。

Past posts on MUDA

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

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

[3] Work in progress: Initial Haskell version of MUDA
http://lucille.atso-net.jp/blog/?p=354