Syoyo Fujita's Blog

raytracing monte carlo

Month: July, 2008

Are you still parallelizing your code by hand?

If so, look at this. This is a promising research which makes your sequential program into multi-threaded program automatically.

Matthew J. Bridges, Neil Vachharajani, Yun Zhang, Thomas Jablin, David I. August.
“Revisiting the Sequential Programming Model for Multi-Core”.
Proceedings of the 40th IEEE/ACM International Symposium on Microarchitecture (MICRO), December, 2007.
http://liberty.princeton.edu/Publications/index.php
?abs=1&setselect=micro40_scale

http://liberty.princeton.edu/Publications/index.php
?abs=1&setselect=ieeemicro08_scale

(easy to read version)

[Ja]

えっ?このマルチコア時代に対応するために、逐次プログラムの並列化をまだ手作業でやっているって? で、お決まりのデッドロックやレース競合に苦しんでいる?…
ナンセンス!いまや逐次プログラムでも並列化はコンパイラが自動でやってくれる時代だよ?

という印象を受けた論文.

この論文では、逐次プログラムから、並列に実行可能な部分を解析して抜き出して複数スレッド化するのをコンパイラで自動にやる方法を提案しています。
(ただし、自動並列化をしやすくするために少しアノテーションを加えたりする作業がいります)

たとえば、以下のようなコードを考えてみます.


while (done) {
    line = load();
    result = exec(line);
    store(result);
}

このような逐次コードは、たとえば load(), exec(), store() がそれぞれの処理に依存していなければ、下図のように load(), exec(), store() の処理をそれぞれスレッド化させて 3 スレッドで同時実行し、パフォーマンスの向上を図ることができます.

text2451.png

自動最適化の程度ですが、結果を見るかぎり概ねよい感じです。

とくに gzip 処理を行う 164.gzip ベンチマークでは、すこし並列化しやすくするためにコードを修正した上でこの自動並列化手法を適用していますが、ほぼスレッド数に比例したパフォーマンス向上を達成しています.
もちろん, gzip 処理は本質的に上のような load, exec, store スタイルのプログラムなのでしょうから(予測なのは最後のおまけの部分参照)並列化しやすかったし並列化の恩恵が受けやかったというのもあると思います.

汎用的なプログラムに適用するには難しいかもしれませんが、MUDA のような DSL 的なプログラムにならこの自動並列化処理の導入も容易な気がしています。
データフロー解析が必要なので、自前でやるにはちょっと実装が大変そうですが。
(MLton みたいなコンパイラフレームワークみたいなのの Haskell 版があれば簡単にできるかなぁ…)
MUDA は Erlang みたいにメッセージングベースの並列化を取り入れようかと考えていましたが、
これ(逐次プログラムを自動並列化)ができるなら、こっちのほうがいいとおもいます。

この研究がやっていることのより詳細である、
自動スレッド抽出を行うために使っている
DSWP(Decoupled Software Pipelining)
という技法についてはまたいずれ取り上げたいと思います.

Abstract 日本語訳

シングルスレッドプログラミングはすでに複雑な作業であると理解されている.
マルチスレッドプログラミングへの移行は、
既存コードの書き直し、プログラマのトレーニング、
プログラムのデバッグ作業の増加、レース条件、
デッドロック、その他の並列プログラミングに固有の問題、、、
を回避するための努力に関連する複雑度とコストが上がるにすぎない.

このコストを減らすために自動スレッド抽出などのアプローチが研究されてきた.
しかしながら、自動で抽出される並列度の量は複数のコアをビジーにするには不十分であった.

本論文では、この並列度の不足が逐次プログラミングモデルの本質的な制約からくるものではなく、次の2つの理由から発生するものであることについて論じる.

一つは、核となる既存の最新コンパイラとハードウェア技法を伴う自動スレッド抽出のフレームワークがないことである.
本論文ではそのようなフレームワークがあればいくつかの SPEC CINT2000 のベンチマークプログラムに対してスケーラブルな並列化が可能であることを示す.

もう一つは、既存の逐次プログラミング言語はプログラマにひとつの正しいプログラム結果を強制させており、複数の正しい結果は認めていないことである.
本論文では逐次プログラミングモデルの自然な拡張が、(上記の一つ目の理由の解決方法では解決できなかった)残りの SPEC CINT2000 ベンチマークスイートの並列化を可能にすることを示す.

実験結果では、ソースコードを 60 行変更するだけで, SPEC CINT2000 スイートの C ベンチマークすべてが自動スレッド抽出により並列可能になった. この手法では 454% の高速化を実現し、制約となるのはコンパイラの最適化の制限だけである.

—-

おまけ

しかし SPEC CPU(CINT2000) のベンチマークプログラムってどんなものかなって見ようとしたら、お金払って買わないとダメとは!なんだそりゃ.
ベンチマークプログラムなのにいったい金を取るとはどういう理由なのだろうか.
(テクニカルサポートが云々というのがありますが、個人コンパイラ野郎にはそんなの必要ないのだけれど…)

Advertisements

Bitcasting float to uint in Haskell

MUDA の LLVM IR のバックエンドを書いていて float の即値のあつかいでハマりました.

float の値によってはアセンブラ(llvm-as)がエラーを出す.
なぜかと思って、LLVM IR のドキュメント(LangLef.html)を見たことろ、

Floating point constants use standard decimal notation (e.g. 123.421), exponential notation (e.g. 1.23421e+2), or a more precise hexadecimal notation (see below). The assembler requires the exact decimal value of a floating-point constant. For example, the assembler accepts 1.25 but rejects 1.3 because 1.3 is a repeating decimal in binary. Floating point constants must have a floating point type.

とあり、123.45 とかの表記はできるけど、
1.3 みたいに正確に表現できない値は NG だよ、
その場合は Hex 値で正確に与えてねとかかれています.

うーむややこしい.

これは文字列表現の数値のリード/ライトで
数値誤差がでないようにするためにするためなんだろうけど、
不正確な数値はアセンブルで跳ねてしまうのはちょっと厳格ですね。

さすが LLVM, ポータブルな浮動小数点表現を実現するために
APFloat を作ってしまうほどの漢気のあるライブラリだ。

—-

さて、MUDA は Haskell で書かれているので、
Haskell で float 値を hex 値にビットキャスト、
つまりメモリ上の値を変更せずに型だけ変える、
をする必要が出てくるのですが、
これがなかなか調べてもうまいやりかたが見つかりません。
結局半日くらいかけて Foreign モジュールの with, peek を使う方法が
一番簡潔にできることが分かりました。


import Numeric
import Foreign
import Foreign.Marshal.Alloc
import Foreign.C.Types

floatAsUInt :: Ptr CFloat -> IO CUInt
floatAsUInt p = do
  ui  IO (CUInt)
bitcastFloatToUInt f = do
  r <- with f floatAsUInt
  return r

main = do
  u  3fa66666

やっていることはこんな感じ。

– float の値を with を使って内部でメモリを確保して float 値を書き込む
– floatAsUInt を使って UInt 値でそのメモリの値を読み戻す

bitcastFloatToUInt はもう少し簡略化(難読化)することができて、


bitcastFloatToUInt :: CFloat -> IO (CUInt)
bitcastFloatToUInt f = with f $ \\p -> peek (castPtr p)

とできます.

これで float -> uint のビットキャストができました.
ただ、型のキャストなのに IO がからむのがちょっと嫌ですね.
unsafePerformIO で消してしまうのも手ですが.

LLVM 勉強会第一回開催通知 8/23(土)

LLVM は実務的かつ新進的なコンパイラインフラです.
いずれ gcc を駆逐し(?)、LLVM 帝国が建国されるのは時間の問題と言われていいます。

そんな機運の中、LLVM の 勉強会第一回の日程を設定しました.
8/23(土)、恵比寿にて開きます.

詳細はこちら.

http://groups.google.co.jp/group/llvm_study/
web/%E7%AC%AC%E4%B8%80%E5%9B%9E+llvm+%E5%8B%89%E5%BC%B7%E4%BC%9A

– LLVM に興味があるけどどんなのかしっかり知りたい
– オレ様の LLVM 利用例をぜひ発表したい
– LLVM で○○やりたいけどどーすればいいかわからん。行ってやるから教えろ。

などなど、LLVM 野郎、LLVM 野郎になりたい!と思う方はぜひともご参加ください.

—-

グラフィックス野郎もコンパイラとは無縁でいられなくなってきている

最近はプロセッサのマルチコア化で、並列化コンパイラが重要と言われていますね.

グラフィックス野郎にとっても、近年はシェーダ言語や、アルゴリズムを言語化して自動最適化などが進んできていて、
これらを効率的に処理するためにもますますコンパイラやコンパイラ技術が重要になってきています。
世の中には多くのコンパイラツールがありますが、
グラフィックスにも十分利用できるだけの機能と最適化機能を含んだものとしては、
私は LLVM がコンパイラのインフラ/ツールとして一番可能性がある思っています.
しかも LLVM は BSD ライセンス, 依存ライブラリは全くナシ(C++ STL のみ利用)という超漢気なライブラリです.
(C++ で書かれているのがちょっと私としては減点ですが)

Future of GPU makers

gpu_market_shares.jpg

gpu_shares_small.jpg
full

Intel, NVIDIA, AMD(ATI) といえばラスタライザ GPU の三大メーカーである。
過去 5 年の株価の推移を見て、皆さんはどう思う(この先どうなると予測する)だろうか?

– 今は市況が悪いからしょうがないさ…
– 今は投資する時期(実質マイナス金利だし投資しなきゃ〜)、次の波への準備中なのさ.
– 株価に一喜一憂してもしょうがなくね?
– etc…

以下は私の意見である.

ラスタライズグラフィックス繁栄の時代は終わったと言っていいだろう。株価は正直だ。
(そもそも Intel は繁栄すらしていないけどね)

この先この状況を大きく変えるにはパラダイムシフトを起こすしかない。
私はそれを担うのがレイトレだと思う(その先は GI)。

もちろん Intel, NVIDIA, AMD はこの危機的状況(?)を打破すべく、
どこもレイトレに莫大な投資をし始めている。
ただ、大手がこういうのに動く場合は Winner’s curse に陥ることが多い。
つまり、新興企業や後発企業に十分マーケットを取得するチャンスがあるということ。

そんな予測を元に、レイトレをコアとしたビジネス(そしてその先の GI も見据えて)を立ち上げるのに、
今はとてつもなくよいタイミングではないかと思っている。

OoO 3rd follow-up

twic.jpg

[En]

I’ve held a OoO 3rd, a gathering for offline renderer enthuasists.

This time I’ve reviewed some EGSR08 papers
(Follow the link to see the presentation slide)


http://groups.google.com/group/oooo_renderist/files

egsr08.pdf

A common thing among the papers I’ve reviewed is coherency: Exploit a coherency to accelerate rendering.
Yes, coherency is a key for any graphics algorithm.

The authors(of the paper I’ve reviewed) are trying to find a coherency from single mono ray tracing, but I don’t think this is a good idea.
I believe beam tracing(or something like a finite aperture ray tracing) naturally collect coherency, so their algorithm could be much more efficient.

[Ja]

OoO 第三回に参加していただいたかた、ありがとうございました.
こんかいの EGSR08 祭りで解説された EGSR08 論文はこんな感じです.

Exploiting Visibility Correlation in Direct Illumination(by syoyo)
Irradiance Gradients in the Presence of Participating Media and Occlusions(by syoyo)
Shallow Bounding Volume Hierarchies for Fast SIMD Ray Tracing of Incoherent Rays(by syoyo)
Sequential Monte Carlo Integration in Low-Anisotropy Participating Media(by genki)
Feature-guided Image Stippling(by kishimoto)
Compact, Fast and Robust Grids for Ray Tracing(by ototoi. 加えてわずか 1 日で実装まで!)
ボーナスステージ: 4k レイトレメガデモ解説(by kioku)

50068.jpg

私の発表ぶんは


http://groups.google.com/group/oooo_renderist/files

egsr08.pdf

にあげておきました.

しかし 4k レイトレデモ(地形はプロシージャル生成)はすごいね。
4k とは、4k シネマの 4k(画面サイズ 4096 pixel)ではなくて、バイナリサイズがたったの 4 キロバイトという意味.
でも解説を聞いたらなんだか私にもできそうな気がしてきました。
時間があったら 4k パストレデモとか作ってみたいなぁ.

LLVM 勉強会を予定しています

(追記: 8/23 に LLVM 勉強会やります)

前回 の反応がよかったので(メールを送ってくれた方々ありがとうございます), LLVM 勉強会を東京近辺で開きたいと思います.

まだ具体的な日時はきめていませんが、8 月頃を予定しています.
内容は、まずは最初なので LLVM の紹介を私から主に行うという感じになると思います.
(ネタがあるかたは歓迎)

あと、LLVM 勉強会をフォローする group を作りました.
http://groups.google.co.jp/group/llvm_study

登録すると、勉強会開催通知とか届くようになります。ご活用ください。

ホントはその次につながる自動最適化についても勉強会を開きたいのですが、
しばらくは LLVM 周りのネタでいっぱいになりそうなので、
自動最適化の勉強は LLVM 勉強会をひとまずこなしてから、にしたいと思います.

LLVM および自動最適化の勉強会を開きたいなと考えています

(追記: LLVM 勉強会,やります)

LLVM の勉強会、また自動最適化の勉強会みたいなのを開こうかなぁと考えています.

LLVM 勉強会

LLVM については、まずはなんだかみんなまだよく知らないようだしちょっと誤解しているみたいなので,
これを機会にしっかりと知るといいんじゃないかな、というのがある。
(ただ、私は LLVM コミッタとかではなくて、外野にいる一ユーザです)

加えて、私としては自動最適化ともからんでくるけど実行時最適化(JIT, partial evaluation)を
自分のプログラムに取り入れたいときに LLVM コンパイラインフラがすでにある物としては
practical で十分な feature を持っているので使っていこうかなと思っていて、
そのためにそこらへんをもう少しよく知って共有したいから.

次に自動最適化の勉強会.

もう手作業で最適化の時代ではない(時間がかかるし)。
もっと賢くなろうぜ、つまりなにかしら自動最適化フレームワークを作って、コンピュータに最適化させようぜ。
というモチベーションから.
で、今の世の中どういう研究が行われてンのよというのをサーベイしていきたいなと.

なぜ自動最適化というと、

– いまの CPU は複雑だ. アセンブリ結果がそのままパフォーマンスを決めるわけではない(OoO 実行, uOP などのせいで)
– プロセッサも多様化している, CPU, GPU, GPGPU. 個々のアーキティクチャに手作業で最適化することのコストが高い
とくにマルチコア化の時代でメモリアクセスの最適化が重要になってきているが、これの手作業最適化は大変.
– ハンドオプティマイズを過信していないか. 多くの場合コンパイラの最適化の方が早いし優秀である.
– ハンドオプティマイズのコストが高すぎる. 自動最適化なら数秒で終わるところに、数日 〜 数ヶ月人手をかけるだけの価値があるか(その間によりよいアルゴリズムが見つかったり、新しいアーキティクチャのプロセッサが発売されたら?).

汎用プログラムを自動最適化というのはハードルが高いので無理としても、
なんからの特定アルゴリズムを DSL(ドメイン固有言語)で記述し、
あとは DSL コンパイラがターゲットアーキティクチャに自動で最適なコードを出力してくれる、
ということができると思っている。
コード生成は静的(コンパイル時決定)にかぎらず、ランタイム時の入力データ分布に応じて動的にやったり、
実行結果の統計からフィードバックさせる(if の予測指示, キャッシュサイズの設定など)というのもあり.

既存研究でいえば、FFTW, Spiral, DSL からの SIMD 最適化あたりがやっていること.
(ここに少しまとめてる.
http://lucille.atso-net.jp/blog/?p=323
)

学会でいえば CGO がやっていること、みたいな感じといえば伝わるひとには伝わるだろうか.

ただ、私はコンパイラ屋でもなくコンパイラが専門でもないので、日本のコンパイラコミュニティを知らない。
LLVM や、自動最適化の勉強会の招集をかけたら(日本で)どれくらいのひとが興味をもち, 集まるのかが不安だ.
(レンダラコンサルを通じて、海外では LLVM や自動最適化に興味を持っているひとは何人か知っていますが)

いまのところ日本のコンパイラコミュニティからこのような企画がない所を見ると、
やっぱり興味があるひとはいないのかなぁ?…

まあちょっと身の回りに聞いてみて、4,5 人くらいあつまりそうだったら企画してみようかと思います.
(もしくは興味があるかたはメールでおしらせください)

リスクが世界を駆け巡る: 2008 年 7 月 12 日時点

うおおおおお!

米住宅ローン会社が破綻しました.

http://jp.reuters.com/article/marketsNews/idJPnJT820929120080711?rpc=144

liquidity の枯渇の波がしっかりと波及しています。

ファニーメイ、フレディマックは大きすぎて潰せないそうだ。国有化という話もでている.
http://www.bloomberg.com/apps/news?pid=newsarchive&sid=ae5sxNLn0HFk

株価の下落もすごいですね. FNM, FRE

ここ最近の AMD の株価の下落もすごい. ここ 16 年来の安値.

AMD shares hit 16-year low as debt burden takes toll on strategy
http://www.ft.com/cms/s/0/eef8db26-4fb5-11dd-b050-000077b07658.html

AMD は売り上げ $6 bn に対して $5 bn の負債があるんだよね、
景気悪化で経営が悪くなったらどうなることやら…

NVDA の株価下落もすごいし、GPU メーカーはどうなりますかね.
まあやっぱ(ラスタライザベースの) GPU は終わりだよね, という予測が着実に実現していると思います.

> GPU は私は 6 年前に将来性が無いと判断したのですが、それがやっと実現しようとしています。
> (原因の一つがサブプライムショックひいては消費バブル崩壊によるものになるとは思いませんでしたが)
http://lucille.atso-net.jp/blog/?p=437

過去記事:

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

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

AMD’s cinema 2.0 demo is rendered by server-side graphics

otoy14.jpg

http://www.techcrunch.com/2008/07/09/
otoy-developing-server-side-3d-rendering-technology/
[En]

http://jp.techcrunch.com/archives/
20080709otoy-developing-server-side-3d-rendering-technology/
[Ja]

TechCrunch が OTOY(AMD の cinema 2.0 デモで使われた技術)を取り上げています.
ふむふむ、なるほどね、あのデモはサーバサイドグラフィックスだったわけね.

– サーバ側には CPU, GPU がいっぱいあって、頑張ってレンダリングしている
(デモではどれくらい使われているかは分からない)

– ネットワーク上の画像転送のために、独自の圧縮コーデックも作った(GPU で lzo 圧縮とかやってそう)

– OTOY とは別に、LightStage 社も立ち上げている。これは Devebec が開発した LightStage 技術をベースにしており、 LightStage 社はその技術を商用展開しようとしているようだ.

– (from ompf.org) OTOY では、独自の高速レイトレ、ボクセルレンダラのアルゴリズムも開発したらしい。まあ GPU とか CPU が複数あれば、フルシーンをボクセルレンダリングも不可能ではないよね.

現在、これくらいの CG が表現できているということは、
web 3.0 はサーバサイド 3D レンダリングになる、というのもありえるかもしれない。
(Prof. Hanazawa が提唱する超リアルな仮想現実であるアンリアル構想も現実のものになりつつありますね)

今回 AMD が技術協力(資本協力も?)しているわけだけど、
たとえばサーバサイドグラフィックスがモノになると彼らは高性能な CPU, GPU が
個人クライアント向けに売れなくなるということを意味するわけで、
ビジネスとしてなんだかジレンマに陥っている気がするんだけどどうなんだろう。
このジレンマを克服するなにかしら違ったアイデアでもあるのかしらん。
(ハイエンドはあきらめてローエンドに注力しバジェットを広げるとか、
帯域/サーバ利用時間に課金するとか)

そういえば昔(今も?)、たとえば SGI がサーバサイドグラフィックスの製品をつくっていましたね。

ompf の常連って人間なのだろうか?

ompf.org に最近書き込みしたりしているんですが、
(今日はなぜか 4 件もポストしてしまった)
常連(特に名前の色が違う野郎)のヤツから返信がある場合は、
だいたいいつも 10 分くらいすると返信がつくんだよね。
返信の早さが尋常じゃない.

暇なのか!?(学業や仕事があるだろうに)
レイトレの情熱がありあまっているのか!?
それともネットのコミュニケーションではこれが普通なのか!?

最近、実はコイツらは生身の人間じゃなくて、
レイトレに超絶 train された AI が動いていて機械的に
返信しているなのじゃないかと思い始めています.
(それくらい常連のアクティビティがすごい)