[performance] SSE 스칼라 sqrt (x)가 rsqrt (x) * x보다 느린 이유는 무엇입니까?

저는 Intel Core Duo에서 핵심 수학의 일부를 프로파일 링했으며 제곱근에 대한 다양한 접근 방식을 살펴보면서 이상한 점을 발견했습니다. SSE 스칼라 연산을 사용하면 역 제곱근을 취하고 곱하는 것이 더 빠릅니다. 기본 sqrt opcode를 사용하는 것보다 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 opcode를 사용하도록하는 것입니다.

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에서 더 좋았습니다. 나는 또한 시도 카맥의 엉뚱한 뉴턴 – 랩슨 근사 기법 비록 2 1의 오류, 4.3ns / 플로트에서, 더 나은 하드웨어보다는 실행, ¹⁰ (내 목적을 위해 너무 많이).

doozy는 역수 제곱근에 대한 SSE 연산을 시도한 다음 곱셈을 사용하여 제곱근을 얻었습니다 (x * 1 / √x = √x). 이 두 개의 의존하는 작업을한다하더라도, 그것은 가장 빠른 솔루션으로까지 1.24ns / 플로트에서 정확한 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의 내장 하드웨어 제곱근 opcode가 다른 두 가지 수학 연산에서 합성하는 것보다 느린 이유는 무엇 입니까?

다음을 확인했기 때문에 이것이 실제로 작업 자체의 비용이라고 확신합니다.

• 모든 데이터는 캐시에 들어가며 액세스는 순차적입니다.
• 함수는 인라인됩니다
• 루프를 풀면 차이가 없습니다.
• 컴파일러 플래그가 전체 최적화로 설정되어 있으며 어셈블리가 양호하며 확인했습니다.

( 편집 : stephentyrone 올바르게 벡터화 SIMD를 사용해야 숫자의 긴 문자열에 대한 작업처럼 작전을 포장 지적 rsqrtps-하지만 여기에 배열에만 목적을 테스트하기위한 것입니다 : 내가 정말 측정하려고하는 것은 스칼라 코드에서 사용하기에 성능 벡터화 할 수 없습니다.)

답변

x' = 0.5 * x * (3 - n*x*x);

x[n] = b[0] * Y[0] * Y[1] * ... * Y[n]
y[n] = Y[0] * Y[1] * ... * Y[n]

b[i] = b[i-1] * Y[i-1]^2
Y[i] = 0.5 * (3 - b[i])

x[0] = n Y[0]
x[i] = x[i-1] * Y[i]

y[0] = Y[0]
y[i] = y[i-1] * Y[i]

Y[i] = 0.5 * (3 - x[i-1] * y[i-1])
     = 1 + 0.5 * (1 - x[i-1] * y[i-1])

x[i] = x[i-1] * (1 + 0.5 * (1 - x[i-1] * y[i-1]))
     = x[i-1] + x[i-1] * 0.5 * (1 - x[i-1] * y[i-1]))
y[i] = y[i-1] * (1 + 0.5 * (1 - x[i-1] * y[i-1]))
     = y[i-1] + y[i-1] * 0.5 * (1 - x[i-1] * y[i-1]))

r = 0.5 * (1 - x * y)
x' = x + x * r
y' = y + y * r

Y = approx_rsqrt(n)
x = Y * n
h = Y * 0.5

r = 0.5 - x * h
x' = x + x * r
h' = h + h * r