Syoyo Fujita's Blog

raytracing monte carlo

Month: April, 2008

Manga illustrates job career

(from 投資世代)

The Adventures of Johnny Bunko
http://www.amazon.com/Adventures-Johnny-Bunko-Career-Guide/
dp/1594482918

51f2hjr-gel_ss500_.jpg

This book seems the first career guide written with Manga.

Manga is now “invading” many fields including business field 🙂
I really feel that (Japanese-style) Manga is changing cultures in worldwide.

[Ja]

マンガで書かれた(あちらでは)初のキャリアガイド本だそうな.

ってか trailer の「ぱかっ」とか「どよーん」とか笑った。
日本人じゃないノンネイティブにわかるのだろうか。
かといって無理矢理英語にすると、
例えば「ゴゴゴゴ」は「Rmmmb」となんともスゴ味のない擬音になるわけで、
そう考えると日本語のままのほうがいいのかも.

Advertisements

Vol. 7

odaiba_1989air.jpg
(from wikipedia)

Prof. H による渾身の Vol. 7 が出版されていたので早速購入しました。

ぬおおぉーーーー、巻を重ねるごとに面白さが指数関数的に上昇している
件について〜〜〜〜!
いやー、日本人でほんとよかった…

「FKYK」
「ルマンド」
「闇鍋しよう」
「東京湾13号埋立地」
「アル中」

しかしあれだね、「I am legend」といったらやっぱこっちを想像するよね.
最初、おお、アノ Prof. H の「レジェンド」がなんとハリウッドで映画化されるのか!?
って思いましたもん.

Rendering misc.

Two interesting graphics things.

(from ompf.org)
glome : functional ray tracing
http://syn.cs.pdx.edu/~jsnow/glome/

glome-hs-demoscene.png

Raytracing in Haskell.

(from toku’s blog)
An Ivy Generator
http://graphics.uni-konstanz.de/~luft/ivy_generator/

ivy.jpg

Really amazing…

OoO 第二回開催予定

SIGGRAPH 2008 論文も公開され始めたようなので、
OoO 第二回を GW 空けの 5/10 あたりで開催したいと考えています.
現在日程を調整中.

Bee さんが SIGGRAPH に通ったようですね.
燃え尽きるほどヒーーート!
グラフィックスの王道であるレンダリング(光輸送)で日本人が
通ったのは、いったい何年ぶりでしょうか?(いや、ホントに. 十何年ぶり?)

他には, Parallel Poisson Disk Sampling とか興味深いですね.
自己相似性は無いものの、多次元でのサンプリング点が生成できるところがグッド.

GW 空けには Parallel Poisson Disk Sampling or
A Meshless Hierarchical Representation for Light Transport を
実装できて OoO で発表できるといいなと考えています.
もしくは今実装中の A first-order analysis of lighting, shading, and shadows の visibility gradient かな.

Understanding G80 behavior and performances

Understanding G80 behavior and performances
http://www.icare3d.org/GPU/CN08

Quite interesting analysis on G80 architecture has been investiaged.
There’s some comments on raytracing in G80.

After reading it, my suspicious on doing “something general purpose computation” in GPU has increased.
It’s supid to do some general computation on GPU such like ray tracing.

[Ja]

うぉ、こりゃすげぇ、よく解析されています.

CPU は内部仕様がある程度 CPU メーカーから提供されているとはいえ、
CPU 野郎もこれくらいできるようでないとダメですね.

とはいえ、読んでみれば GPU は汎用計算にはやっぱり向く訳ないなぁ
という確信が大きくなっただけですね.

Split Compilation: an Application to Just-in-Time Vectorization

Split Compilation: an Application to Just-in-Time Vectorization,
Piotr Lesnicki, Albert Cohen, Grigori Fursin, Marco Cornero, Andrea Ornstein, and Erven Rohou,
GREPS 2007 Workshop
http://sysrun.haifa.il.ibm.com/hrl/greps2007/

ポータブルな中間言語(CIL)を導入し、最適化指示子はアノテーションで CIL に仕込んでおき、
ランタイム時のプロファイルやアノテーションを参考にして、
JIT コンパイルでポータブルバイトコードから最適化ネイティブコードを生成するというもの.

バイトコードはポータブルなままにできるという特徴がある.

まあなんかポータブルな中間形式を用意して… というフレームワークとしては、
LLVM ですでに出来ているような感じがしますが、
著者らはいずれ gcc と統合して、 gcc -> CIL(CLI) -> JIT というのを考えているらしい.
http://gcc.gnu.org/projects/cli.html

将来的には、CIL から GPU などへの並列プロセッサへのバックエンドを作ったり、
アノテーション情報をつかって JIT コンパイル時のレジスタ割当ての高速化を考えているとのこと.

本論文にかぎらず、パフォーマンスのためにはアノテーションは有効だと思うので、
MUDA にもなにかしらアノテーションを仕込める仕組みを作りたいと思う.

MUDA: Vector type is not allowed as return type for external function.

今まで, MUDA では


// NG
vec func(vec a)
{
    return a + a;
}

という関数の戻り値に vector 型を指定できるようにしていたのですが、
C とのインターフェイスを考えると, これが以外とめんどくさい.
C 側にネイティブ型(__m128 とか)が見えてしまう.
かといって union or struct で隠すと union or struct 返しになって
面倒だし C コンパイラにとっても最適化しづらくなる.

そんなわけでスカラ型しか関数の戻り値の型として指定できないようにしました.

vector 型を返したい場合は、out 引数を使って以下のようにします.


void func(out vec ret, vec a)
{
    ret = a + a;
}

ただし、static や inline の付いた関数では vector 型はサポートされます.


// OK
static vec func(vec a)
{
    return a + a;
}

external な MUDA 関数(C から見える関数) でなければ、
C とのインターフェイスを考えなくていいので、
内部では void func(out vec ret, vec a) というような関数に変えて
コードエミットするということができるので.

Automated Dynamic Analysis of CUDA Programs

M. Boyer, K. Skadron, and W. Weimer.
“Automated Dynamic Analysis of CUDA Programs.”
In Third Workshop on Software Tools for MultiCore Systems (STMCS), Apr. 2008.
http://www.cs.virginia.edu/~mwb7w/

CUDA プログラムに自動でインストゥルメンテーションを仕込み、
レース競合の検出と、メモリアクセスのバンクコンフリクトの検出を行うという手法.

CPU で言えば、Intel thread checker(でスレッド競合検出) と valgrind(でキャッシュミス解析)
を組み合わせたような感じでしょうか.

バンクコンフリクトの検出は、
異なるスレッドからのグローバルメモリ(DRAM)(シェアードメモリでした. でもグローバルメモリもバンク構成になっているはず)への同じバンクへの
アクセスはシーケンシャルになってアクセスのパフォーマンスが落ちるので
なるべく減らしましょうね.
そのために自動でどれだけコンフリクトが発生しているか本手法で分かると
役に立つよ、という感じ.

論文に出てきた、CCured と呼ばれる, ランタイムチェックを自動でインストゥルメンテーション
してくれるツールは知りませんでした.
http://manju.cs.berkeley.edu/ccured/

こちらはレンダラプログラムのロバスト性向上に使えそうです.

Automatic Data Movement and Computation Mapping for Multi-level Parallel Architectures with Explicitly Managed Memories

M. Baskaran, U. Bondhugula, S. Krishnamoorthy, J. Ramanujam, A. Rountev and P. Sadayappan,
“Automatic Data Movement and Computation Mapping for Multi-level Parallel Architectures with Explicitly Managed Memories,”
in Proc. 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, (PPoPP 2008), Salt Lake City, UT, February 2008.
http://www.cse.ohio-state.edu/~saday/

PLUTO ツールのチームから.

ネストしたループをタイル化してメモリアクセスの局所性を高め、
またタイル内で処理するデータの転送を最適な場所に挿入してくれる手法.

データ転送命令の挿入位置は二次最適化問題に帰結され、
SQP(Sequential Quadtratic Programming, 逐次二次計画法)を解くことで
最小の転送オーバヘッドで最大の効果を得られる場所を見つけます.

デモでは本手法を CUDA に適用し、シェアードメモリを有効に使ってパフォーマンスが
改善された例を示しています.

CPU の場合でも本手法の考え方は有効で、
たとえばデータ転送部分はプリフェッチ命令などに
置き換えるようにすれば CPU の場合でも使えて、
メモリアクセスの効率化が図れると思います.

CUDA(GPU), CPU(x86) ともに、今もこれからもパフォーマンスで
重要になってくるのはメモリアクセスをどう最適化するかだと思います.

メモリアクセスの最適化は手作業でやらずに、
論文で提案されているような手法で自動的にできないかなぁと思っています.
メモリアクセスの最適化は、 SIMD 化みたいにコードを見ればなんとなく
直感的に分かるというものではないので、手作業では、
実行させてプロファイルとってみてパラメータを変えてもう一度試して…
と非効率になると思うのです.

ちなみに、グラフィックス(大域照明)だと、
ネストループでどうメモリアクセスの効率化を図るかという問題ではなくて、
木探索の効率化やプログラム実行の spatio-temporal プロファイルから
どうコヒーレンスを見つけるかという問題に帰結されるのが多いのですが、
このような分野に対するメモリアクセス最適化の研究は
(言語、コンパイラ野郎方面からは)まだまだやられていないような気がしています.
(私が既存研究を見つけられていないだけかもしれません)

PLuTo : An automatic parallelizer and locality optimizer for multicores

PLuTo – An automatic parallelizer and locality optimizer for multicores
http://www.cse.ohio-state.edu/~bondhugu/pluto/

複雑なループ処理でも、自動で処理をタイリング変換(メモリアクセスの局所化)したり、
自動で openmp ディレクティブを挿入して並列化してくれるというスグレモノツール.
すげー.

ツールはソース to ソースの変換を行うので、変換後のプログラムも普通の C コードのまま
扱うことができます.

たとえば、こんなコードが
(example/seidel/seidel.c より)


    /* pluto start (T,N) */
    for (t=0; t<=T-1; t++)  {
        for (i=1; i<=N-2; i++)  {
            for (j=1; j<=N-2; j++)  {
                a[i][j] = (a[i-1][j-1] + a[i-1][j] + a[i-1][j+1]
                        + a[i][j-1] + a[i][j] + a[i][j+1]
                        + a[i+1][j-1] + a[i+1][j] + a[i+1][j+1])/9.0;
            }
        }
    }
    /* pluto end */

pluto でタイリング変換すると


#define ceild(n,d)  ceil(((double)(n))/((double)(d)))
#define floord(n,d) floor(((double)(n))/((double)(d)))
#define max(x,y)    ((x) > (y)? (x) : (y))
#define min(x,y)    ((x) = 100);
    assert(N >= 100);
    int c1, c2, c3, c4, c5, c6;
    register int lbv, ubv;

#ifdef PERFCTR
    PERF_INIT;
#endif

    /* Generated from PLuTo-produced CLooG file by CLooG v0.14.1 64 bits in 0.03s. */
    for (c1=0;c1<=floord(T-1,10);c1++) {
        for (c2=max(ceild(10*c1-13,15),0);c2<=min(floord(T+N-3,15),floord(10*c1+N+7,15));c2++) {
            for (c3=max(max(max(max(ceild(10*c1+15*c2-13,15),ceild(15*c2-13,15)),0),ceild(20*c1-12,15)),ceild(30*c2-N-11,15));c3<=min(min(min(min(floord(2*T+2*N-6,15),floord(15*c2+T+N+11,15)),floord(20*c1+2*N+14,15)),floord(30*c2+N+25,15)),floord(10*c1+15*c2+N+21,15));c3++) {
                for (c4=max(max(max(max(ceild(15*c3-2*N+4,2),15*c2-N+2),0),-15*c2+15*c3-N-12),10*c1);c4<=min(min(min(min(10*c1+9,T-1),-15*c2+15*c3+13),15*c2+13),floord(15*c3+12,2));c4++) {
                    for (c5=max(max(15*c2,c4+1),15*c3-c4-N+2);c5<=min(min(c4+N-2,15*c3-c4+13),15*c2+14);c5++) {
                        for (c6=max(15*c3,c4+c5+1);c6<=min(15*c3+14,c4+c5+N-2);c6++) {
                            S1(c1,-c1+c2,-c1-c2+c3,c4,-c4+c5,-c4-c5+c6) ;
                        }
                    }
                }
            }
        }
    }
    /* End of CLooG code */

こんな感じになります.
なんだか出力されるコードはぐちゃぐちゃに見えますが、
メモリアクセスがタイリング(block 分割)されているので、
キャッシュヒット率が上がることが期待されます.
(ただ、アドレス算出のコストは上がるので、
ある程度大きなループでないと思ったほど効果が出ないかもしれません)

もう簡単なループ処理とかは、ツールで自動で最適化してくれる時代ですね.

pluto が想定しているプログラムは、行列計算などの配列処理が主になっているので、
レンダリングではどれくらい使い物になるかは分かりませんが、
テクスチャ処理のブロック化や一様グリッドのアクセスのブロック化などに使えそうでしょうか.

pluto のバックグラウンドで実行されている cloog や polylib で使われている、
Polyhedra(多胞体?)理論も参考になるので、いつか説明できればと思います.