floating point. part 1 : 非正規化数の恐怖

by syoyo

浮動小数点演算(IEEE 754)のことを調べていると、
いろいろと今まで lucille などでの浮動小数点計算コードが実はダメダメで、
一から考え直す必要があることが分かってきました。
(MUDA 用の libm ももっと fp の仕組みを知ってから書き始める必要がありそう)

そんなわけで、グラフィクス野郎が知っておくべき浮動小数点演算シリーズ.

第一回は、非正規化数の恐怖です。

非正規化数(denormal number, subnormal number)は、演算がアンダーフローしたときに、
いきなりアンダーフローの結果がゼロになると困るような計算のために IEEE 754 に導入されたようです。
しかし、非正規化数は、基本的にはソフトウェアで処理されるので、実はとてもパフォーマンスに影響があることが知られています。
(x86 OS では、基本的に非正規化数の扱いはデフォルトで有効になっている)

アンダーフローはそんなに滅多に起こるものではない。
しかし一度起きてしまうと、アンダーフローは一気にやってくる。
一回でもアンダーフローを生じさせるような計算は、通常何度もアンダーフローを発生させるようになるからだ。
そのため、プログラムは時々アンダーフローの嵐に見舞われる。これがプログラムの実行を遅くするのだ。

W. Kahan
IEEE 754R minutes from September 19, 2002

アンダーフロー(非正規化数)は通常あんまり起こらないが、
起こってしまうとずっとそれは生じてしまう、ということになる。

つまりは、今の金融市場と同じですね。
大きく指数が下落すると、ヘッジ(or 損切り)のための売りがでて、
その売りがさらに他の売りを誘発するという流動性の罠みたいな感じ。

では実際どれくらい、演算に非正規化数があると効率が悪くなるのだろう?
[1] によると、非正規化数の処理のコストは 1000~ サイクルである!

世の中は広い。なんとすでに非正規化数の演算がどれくらい効率が悪いかのベンチマークプログラムが存在する [2]。
(私が一日がかりで x86 の denormal の振る舞いや fp control register の仕様と
格闘しながら作ったプログラム [5] よりも遥かに出来がいいなぁ)

私の環境(gcc 4.0.1, core 2 intel mac) では約 25 くらいのベンチ結果となった。
(これは [5] を実行したときのパフォーマンス比ともほぼ一致する)

[2] のベンチは [3,4] で解説されているように、至極単純である。


slow:
a <- [1, 0, 0, 0, 0...]
for i <- 1 to ITER
  for n <- 3 to SIZE
    a[n] <- (a[n] + a[n-1] + a[n-2]) / 3

fast:
tiny <- small normalized value
a <- [1, tiny, tiny, tiny, tiny...]
for i <- 1 to ITER
  for n <- 3 to SIZE
    a[n] <- (a[n] + a[n-1] + a[n-2]) / 3

time = slow / fast

という感じで、どんどん平均を取っていくコードを繰り返して実行する。
最初の slow ループは、a[0] だけ 1 で、残りの a[] の配列の要素の値は 0 である。
これはつまり、n が増えるにつれて、どんどんと a[] の配列の値は小さくなっていっていき、ある時点で
計算された a[n] は非正規化数の領域へと突入する。

それに対して、 fast のループでは 0 を小さな正規化数である tiny に置き換えることで、
計算結果が非正規化数にならないように防いでいる。

パフォーマンスの差は、この slow と fast のループの処理時間から割り出される。

[2, 3, 4] によれば、大きな傾向として、最新の CPU アーキティクチャほど
非正規化数の処理パフォーマンスが悪いという結果が読み取れる。

対応策

プログラムがアンダーフローを引き起こすか、演算結果が非正規化数になるかどうかは、
Prof. Kahn の引用のように、これはアルゴリズムに起因する部分が大きいと思う
(たとえば行列計算や, 物理計算での time integration などでは生じやすいと思う)。

対応としては、演算結果がアンダーフロー(非正規化数)になるかどうか演算のコードをチェックして、
回避策を探すのがよい。

– 非正規化数による漸進的アンダーフローがアルゴリズムに
それほど影響を与えないのであれば、非正規化数を無効にする
(x86 では DAZ(Denormals are zero), FZ(Flash to zero) flag を設定)
基本的にグラフィックス野郎にとっては非正規化数の精度は必要ないだろうから、
とりあえず非正規化数は off にしておくのがよいだろう。

– 計算コードがアンダーフローしないように入力の値の定義域を制限したり、
アルゴリズムの見直しを行う
(値域、定義域のチェックには gappa などが使えるだろう)

ちなみに、ゲーム機などのプロセッサでは非正規化数は通常サポートされていません。

おわりに

というわけで、知らずのうちにあなたのプログラムが非正規化数の演算を引き起こしていて、
そのせいで実は本来の 1/10 のパフォーマンスしか出ていなかったかもしれない、
という身の震えるような(?) 浮動小数点計算の落とし穴を紹介しました。

[1] SSE Performance Programming
http://developer.apple.com/hardwaredrivers/ve/sse.html

[2] Subnormal Floating-Point Degradation in Parallel Applications
http://charm.cs.uiuc.edu/subnormal/

[3] Performance Degradation in the Presence of Subnormal Floating-Point Values
Hari Govind, Isaac Dooley, Michael Breitenfeld, Orion Lawlor and Laxmikant Kale
http://research.ihost.com/osihpa/
[PPT]

[4] Quantifying the Interference Caused by Subnormal Floating-Point Values.
Isaac Dooley, Laxmikant Kale
http://osihpa.eng.utep.edu/2006/DooleySubnormal06.pdf

[5] http://lucille.svn.sourceforge.net/viewvc/lucille/angelina/fp/denormal/

[6] x86 では、演算結果が非正規化数になる時点でパフォーマンスダウンが発生する模様。
非正規化数になったかどうかの判定に、浮動小数点例外が使える。
しかし denormal 例外は、オペランドに denormal が与えられたときでないと発生しない。
つまり非正規化数になったかどうかを例外で捉えるには denormal 例外だけではだめで、
underflow 例外を使うことになる。
しかし、underflow したら非正規化数の領域をすっ飛ばしてすぐに 0 になるケースでは、
パフォーマンスダウンは発生しない。つまり underflow 例外を補足したからといって、
それが denormal が発生したとは言えないことになる。ややこしい。

Advertisements