110

Intel Core Duo でコア数学の一部をプロファイリングしてきましたが、平方根へのさまざまなアプローチを見ていると、奇妙なことに気付きました: SSE スカラー演算を使用すると、逆数の平方根を取得して乗算する方が高速ですネイティブの sqrt オペコードを使用するよりも、sqrt を取得するには!

次のようなループでテストしています：

inline float TestSqrtFunction( float in );

void TestFunc()
{
  #define ARRAYSIZE 4096
  #define NUMITERS 16386
  float flIn[ ARRAYSIZE ]; // filled with random numbers ( 0 .. 2^22 )
  float flOut [ ARRAYSIZE ]; // filled with 0 to force fetch into L1 cache

  cyclecounter.Start();
  for ( int i = 0 ; i < NUMITERS ; ++i )
    for ( int j = 0 ; j < ARRAYSIZE ; ++j )
    {
       flOut[j] = TestSqrtFunction( flIn[j] );
       // unrolling this loop makes no difference -- I tested it.
    }
  cyclecounter.Stop();
  printf( "%d loops over %d floats took %.3f milliseconds",
          NUMITERS, ARRAYSIZE, cyclecounter.Milliseconds() );
}

TestSqrtFunction のいくつかの異なるボディでこれを試してみましたが、本当に頭を悩ませているタイミングがいくつかありました。何よりも最悪だったのは、ネイティブの sqrt() 関数を使用し、「スマート」コンパイラに「最適化」させたことです。24ns/float で、x87 FPU を使用すると、これは非常に悪かった:

inline float TestSqrtFunction( float in )
{  return sqrt(in); }

次に試したのは、組み込み関数を使用して、コンパイラに SSE のスカラー sqrt オペコードを使用させることでした。

inline void SSESqrt( float * restrict pOut, float * restrict pIn )
{
   _mm_store_ss( pOut, _mm_sqrt_ss( _mm_load_ss( pIn ) ) );
   // compiles to movss, sqrtss, movss
}

これは 11.9ns/float で、より優れていました。また、 Carmack の風変わりな Newton-Raphson 近似手法も試しました。これはハードウェアよりもさらに優れた 4.3ns/float で実行されましたが、誤差は 2 10分の 1 でした (これは私の目的には多すぎます)。

逆数平方根の SSE 演算を試した後、乗算を使用して平方根 ( x * 1/√x = √x ) を取得したとき、おかしなことになりました。これには 2 つの依存する操作が必要ですが、1.24ns/float で 2 -14の正確さで、群を抜いて最速のソリューションでした。

inline void SSESqrt_Recip_Times_X( float * restrict pOut, float * restrict pIn )
{
   __m128 in = _mm_load_ss( pIn );
   _mm_store_ss( pOut, _mm_mul_ss( in, _mm_rsqrt_ss( in ) ) );
   // compiles to movss, movaps, rsqrtss, mulss, movss
}

私の質問は基本的に何を与えるのですか？SSE の組み込みのハードウェア平方根オペコードが、他の 2 つの数学演算から合成するよりも遅いのはなぜですか?

私が確認したので、これは実際には操作自体のコストであると確信しています:

  • すべてのデータはキャッシュに収まり、アクセスはシーケンシャルです
  • 関数はインライン化されています
  • ループを展開しても違いはありません
  • コンパイラフラグは完全最適化に設定されています（アセンブリは良好です、私はチェックしました）

(編集: stephentyrone は、数値の長い文字列に対する演算は、ベクトル化 SIMD パック演算を使用する必要があることを正しく指摘していますrsqrtps— しかし、ここでの配列データ構造はテスト目的のみです: 私が実際に測定しようとしているのは、コードで使用するためのスカラーパフォーマンスですこれはベクトル化できません)。

4

6 に答える 6

222

sqrtss正しく丸められた結果が得られます。 約 11 ビットの精度で逆数rsqrtssの近似値を返します。

sqrtss精度が必要な場合に備えて、はるかに正確な結果を生成しています。 rsqrtss近似で十分だが速度が必要な場合のために存在します。Intel のドキュメントを読むと、ほぼ完全な精度 (私の記憶が正しければ ~23 ビットの精度) を提供する命令シーケンス (逆数の平方根近似とそれに続く単一のニュートン ラフソン ステップ) も見つかります。より速いsqrtss。

編集:速度が重要であり、多くの値のループで実際にこれを呼び出している場合は、これらの命令のベクトル化されたバージョンrsqrtpsまたはを使用する必要がsqrtpsあります。どちらも命令ごとに 4 つの float を処理します。

于 2009-10-06T23:52:07.290 に答える
8

これは、分割にも当てはまります。MULSS(a,RCPSS(b)) は、DIVSS(a,b) よりも高速です。実際、Newton-Raphson 反復で精度を上げても、まだ高速です。

Intel と AMD はどちらも、最適化マニュアルでこの手法を推奨しています。IEEE-754 への準拠を必要としないアプリケーションで div/sqrt を使用する唯一の理由は、コードの読みやすさです。

于 2011-07-12T14:32:14.897 に答える
6

答えを提供する代わりに、それは実際には間違っている可能性があります（キャッシュやその他のものについても確認したり議論したりするつもりはありません。それらが同一であるとしましょう）あなたの質問に答えることができる情報源を紹介します.
違いは、sqrt と rsqrt の計算方法にある可能性があります。詳細については、http://www.intel.com/products/processor/manuals/を参照してください。使用しているプロセッサ関数について読むことから始めることをお勧めします。特にrsqrtに関する情報があります（cpuは内部ルックアップテーブルを巨大な概算で使用しているため、結果を取得するのがはるかに簡単になります）。rsqrt は sqrt よりもはるかに高速であるように思われるかもしれませんが、1 つの追加の mul 操作 (それほどコストはかかりません) は、ここでの状況を変えないかもしれません。

編集: 言及する価値のあるいくつかの事実:
1. グラフィックス ライブラリのマイクロ最適化を行っていたとき、ベクトルの長さを計算するために rsqrt を使用しました。(sqrt の代わりに、2 乗の合計に rsqrt を掛けました。これはまさにテストで実行したことです)、パフォーマンスが向上しました。
2. 単純なルックアップ テーブルを使用して rsqrt を計算する方が簡単な場合があります。rsqrt の場合、x が無限大になると 1/sqrt(x) は 0 になるため、x が小さい場合、関数値は (あまり) 変化しません。 sqrt - 無限大になるので、単純なケースです ;)。

また、明確化:リンクした本のどこでそれを見つけたのかわかりませんが、rsqrtがいくつかのルックアップテーブルを使用していることを読んだことは確かであり、結果がただし、正確である必要はありません-少し前のように、私も間違っている可能性があります:)。

于 2009-10-06T23:55:34.477 に答える
4

Newton-Raphson converges to the zero of f(x) using increments equals to -f/f' where f' is the derivative.

For x=sqrt(y), you can try to solve f(x) = 0 for x using f(x) = x^2 - y;

Then the increment is: dx = -f/f' = 1/2 (x - y/x) = 1/2 (x^2 - y) / x which has a slow divide in it.

You can try other functions (like f(x) = 1/y - 1/x^2) but they will be equally complicated.

Let's look at 1/sqrt(y) now. You can try f(x) = x^2 - 1/y, but it will be equally complicated: dx = 2xy / (y*x^2 - 1) for instance. One non-obvious alternate choice for f(x) is: f(x) = y - 1/x^2

Then: dx = -f/f' = (y - 1/x^2) / (2/x^3) = 1/2 * x * (1 - y * x^2)

Ah! It's not a trivial expression, but you only have multiplies in it, no divide. => Faster!

And: the full update step new_x = x + dx then reads:

x *= 3/2 - y/2 * x * x which is easy too.

于 2012-08-02T22:20:35.850 に答える
-3

これらの命令は丸めモードを無視し、浮動小数点例外や非正規化数を処理しないため、高速です。これらの理由から、他の fp 命令をアウトオブオーダーでパイプライン化し、推測し、実行する方がはるかに簡単です。

于 2016-07-05T14:17:12.570 に答える