fiber(microthread)

by syoyo

シェーディング言語の Du(), Dv()
関数をどのように実装したらよいものかと
いろいろ調べています。

とあるプロダクションのレンダラでは、
シェーダコード(ネイティブコード)に Du()
が現れた時点で
カレントコンテキストを退避させるなどして微分値を計算しているとこのことでした。


http://lucille.atso-net.jp/blog/archives/2005/08/lucille.html

というわけで、まずは、そもそも OS
のコンテキストスイッチはどのように行われているのか
といろいろ調べていたところ、
fiber(micothread
などとも呼ばれている) というスレッドテクニック
があることを知りました。


http://d.hatena.ne.jp/shinichiro_h/20040106


http://www.sun-inet.or.jp/~yaneurao/yaneSDK3rd/chap0124.html
 (やねう先生)

基本的には、fiber とは、OS
のコンテキストスイッチがやっているような、
スタックの退避・復帰を自前で行う、
スレッドよりも軽量なしくみと捕らえることができます。

隣の(次の) fiber へ制御を移せたり、
任意場所でスレッドを止めたりなど、
Du() の実装にもっとも適していそうな気がします。

まだ実装にはトライしていませんが、fiber
を使っての実装は以下のようにできそうです。
微分計算のために、シェーディングの近隣点で 3 or 4 個の
fiber を走らせておき、
各スレッドで Du() が呼ばれた時点で、残りの Du()
が呼ばれるまでスレッド実行をサスペンド
(次の fiber へ処理を移す)、全部の fiber での Du()
の call が終わったところで、
数値微分で Du() への引数の微分値を計算、という手順です。

ただ、たとえば

if (oraora_desu_ka == yes) {
    N = x;
} else {
    N = Du(x);
}

のようなシェーダコードがあり、Du()
のコール回数が必ずしもすべての
シェーダ fiber
スレッドで一致しない場合があったりするときはどうするか、
というこを考えなくてはなりません。
(とはいえ、中間言語方式の prman や aqsis
でもこのことは問題になりそうなので、
aqsis や Pixie などでの Du()
自身の実装のしくみを調べてみる必要がありそうです)

スタックの退避・復帰

スタックの退避・復帰には、

o アセンブラで直接書く
o setjmp/longjmp を使う
o
getcontext()/setcontext()

を使う

などで実現可能のようです。setjmp を使うのが、
一番ポータビリティが高いようです。

__builtin_expect()

ところで、linux
のカーネルソースでコンテキストスイッチを行う部分を見ていたのですが、

結構コンテキストスイッチだけでも多くの処理が行われているのですね。
 

また、カーネルソースのいたるところで unlikely() や
likely() という関数を分岐部分に使っているのに
気がつきました。実際には、この関数は
__builtin_expect() へのマクロとして定義されています。

この __builtin_expect() は、
静的(コンパイル時)に分岐へのヒントを与える gcc の拡張機能です。

(gcc 2.96 くらいから在るみたい)


http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#Other-Builtins

最近の CPU は分岐ミスによるペナルティが大きくなっていますから、
分岐するときの判定として、
あらかじめあまり評価が真にならないことが期待できる場合には、
unlikely() を使い分岐予測の
ヒントを与えることで、分岐のペナルティをを減らすことができます。

(gcc のドキュメントでは、-fprofile-arcs
にて実際に分岐のプロファイルを
あらかじめ取っておくことを推奨しています)

/* else 文が実行される確率が高い */
if (unlikely(ひ... ひと思いに右で... やってくれ)) {
  ...
} else {
  /* No! No! No! */
  ...
}

/* else 文が実行される確率が高い */
if (unlikely(ひ... 左?)) {
  ...
} else {
  /* No! No! No! */
  ...
}

/* if 文が実行される確率が高い */
if (likely(りょ... りょうほーですかあああ~)) {
  /* Yes! Yes! Yes! */
} else {
  ...
}

/* if 文が実行される確率が高い */
if (likely(もしかしてオラオラですかーッ!?)) {
  /* Retire... */
} else {
  ...
}

結構レンダラの内部でも分岐処理を行っている部分がありますので、
この __builtin_expect() を
使って、
ボトルネックになりそうな分岐の部分を書き直すとパフォーマンスがアップしそうな気がします。

 

Advertisements