fma(a,b,c)
a*b+c
中間結果を丸めないこと以外は と同等です。
この丸めを回避することで大きなメリットが得られるアルゴリズムの例をいくつか教えてください。
回避する乗算後の丸めは、回避しない加算後の丸めよりも問題が少ない傾向があるため、明らかではありません。
fma(a,b,c)
a*b+c
中間結果を丸めないこと以外は と同等です。
この丸めを回避することで大きなメリットが得られるアルゴリズムの例をいくつか教えてください。
回避する乗算後の丸めは、回避しない加算後の丸めよりも問題が少ない傾向があるため、明らかではありません。
1 つの重要な例にたどり着きました。より一般的には、FMA を使用すると、ライブラリの作成者は、正しい丸めを使用して他の多くの浮動小数点演算を効率的に実装できます。
たとえば、FMA を備えたプラットフォームは、FMA を使用して正しく丸められた除算と平方根を実装できます (PPC と Itanium はこのアプローチを採用しました)。これにより、FPU は基本的に単一目的の FMA マシンになります。Peter Tang と John Harrison (Intel)、および Peter Markstein (HP) は、この使用法について説明している論文をいくつか持っています。
tawが示した例は、エラー境界を追跡するだけでなく、より広く役立ちます。これにより、丸め誤差なしで、2 つの浮動小数点数の積を 2 つの浮動小数点数の合計として表すことができます。これは、正しく丸められた浮動小数点ライブラリ関数を実装するのに非常に役立ちます。Jean-Michel Muller の本または論文は、crlibm
これらの使用法についてさらに学ぶための出発点として適しています。
FMA は、特定のタイプの引数に対する math-library スタイル ルーチンの引数削減にも広く役立ちます。引数の削減を行う場合、計算の目的はしばしば の形式の項になります(x - a*b)
。ここで、(a*b)
は x 自体にほぼ等しいです。(a*b)
特に、これが FMA なしで計算された場合、結果は項の丸め誤差のオーダーになることがよくあります。ミュラーも彼の本でこれについていくつか書いていると思います。
これまでに見つけたのは、「エラーのない変換」だけです。a+b
、a-b
、およびからの浮動小数点数エラーa*b
も浮動小数点数です(最も近いモードに丸められ、オーバーフロー/アンダーフローなどがないことを前提としています)。
加算 (および明らかに減算) エラーは簡単に計算できます。の場合abs(a) >= abs(b)
、エラーは正確ですb-((a+b)-a)
(2 フロップ、またはどちらが大きいかわからない場合は 4-5)。乗算誤差は簡単に計算できますfma
- それは簡単fma(a,b,-a*b)
です。それがなければfma
、かなり厄介なコードの 16 フロップです。そして、正しく丸められた完全に一般的なエミュレーションは、fma
それよりもさらに遅くなります。
実際の計算のフロップごとに追加の 16 フロップのエラー追跡は非常にやり過ぎですが、わずか 1 ~ 5 のパイプラインに適したフロップで、それは非常に合理的であり、エラー追跡と補償の 50% ~ 200% のオーバーヘッドに基づく多くのアルゴリズムでは、すべての計算がビット数の 2 倍で行われたかのように誤差が小さく、多くの場合、悪条件を回避できます。
興味深いことに、fma
はこれらのアルゴリズムで結果を計算するために使用されることはありません。エラーを見つけるためだけに使用されfma
ますfma
。
検索に関連するキーワードは、「補償されたホーナー方式」と「補償された内積」であり、ホーナー方式はより多くの利益をもたらします。
いくつかの例: ベクトル内積。フーリエ変換。デジタル信号処理。多項式。いろいろ。
それは、何よりも最適化とハードウェアの活用の問題です。積和は、数値計算法では非常に一般的な要件であり、この方法を使用すると、処理を高速に、おそらくもう少し正確に実行する方法について、コンパイラに明示的な指示を与えることができます。私が間違っていない限り、コンパイラは a=b*c+d を FMA 命令に自由に置き換えることができますが、そうしないことも自由です。(丸めの標準的な呼び出しを除きますが、実際のコンパイラは日常的に小さな方法で標準に違反しています)。
FMA の主な利点は、速度が 2 倍になることです。乗算に 1 サイクル、次に加算に 1 サイクルかかるのではなく、FPU は両方の演算を同じサイクルで発行できます。明らかに、ほとんどのアルゴリズムは、より高速な操作の恩恵を受けます。
頭のてっぺんから - 行列の乗算、ニュートンの法則、多項式の評価、数値法
FMA のウィキペディアのエントリで、製品の蓄積に関係するアルゴリズムが FMA を使用することで最も恩恵を受けることがかなりよく説明されています。
A fast FMA can speed up and improve the accuracy of
many computations that involve the accumulation of products:
* Dot product
* Matrix multiplication
* Polynomial evaluation (e.g., with Horner's rule)
* Newton's method for evaluating functions.