performance - fadd - ¿Por qué el SSE escalar sqrt(x) es más lento que rsqrt(x)*x?

assembler float point

Question

He estado perfilando algunas de nuestras operaciones matemáticas centrales en un Intel Core Duo, y mientras observo varios enfoques de raíz cuadrada, he notado algo extraño: al usar las operaciones escalares SSE, es más rápido tomar una raíz cuadrada recíproca y multiplicarla para obtener el sqrt, de lo que es usar el código de operación sqrt nativo!

Lo estoy probando con un ciclo algo así como:

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() );
}

He intentado esto con algunos cuerpos diferentes para la función TestSqrtFunction, y tengo algunos tiempos que realmente me están rascando la cabeza. Lo peor de todo fue usar la función nativa sqrt () y dejar que el compilador "inteligente" "optimice". En 24ns / float, usando la FPU x87 esto fue patéticamente malo:

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

Lo siguiente que intenté fue utilizar un intrínseco para obligar al compilador a usar el código de operación sqlar escalar de SSE:

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
}

Esto fue mejor, a 11.9ns / flotante. También probé la absurda técnica de aproximación Newton-Raphson de Carmack , que funcionaba mejor que el hardware, a 4.3ns / flotante, aunque con un error de 1 en 2 ¹⁰ (que es demasiado para mis propósitos).

El doozy fue cuando probé la opción SSE para la raíz cuadrada recíproca , y luego utilicé un multiplicador para obtener la raíz cuadrada (x * 1 / √x = √x). A pesar de que esto requiere dos operaciones dependientes, fue la solución más rápida con diferencia, a 1.24ns / flotante y precisa a 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
}

Mi pregunta es básicamente ¿qué da ? ¿Por qué es más lento el código de operación de raíz cuadrada integrado en hardware de SSE que sintetizarlo en otras dos operaciones matemáticas?

Estoy seguro de que este es realmente el costo de la operación en sí, porque he verificado:

• Todos los datos se ajustan a la caché, y los accesos son secuenciales
• las funciones están en línea
• desenrollar el bucle no hace ninguna diferencia
• los indicadores del compilador están configurados para la optimización completa (y el ensamblaje es bueno, verifiqué)

( edit : stephentyrone señala correctamente que las operaciones en largas cadenas de números deben usar vectorizar operaciones empaquetadas SIMD, como rsqrtps , pero la estructura de datos de la matriz aquí solo tiene fines de prueba: lo que realmente estoy tratando de medir es el rendimiento escalar para su uso en código que no puede ser vectorizado.)

Answer 1

En lugar de proporcionar una respuesta, eso podría ser incorrecto (tampoco voy a verificar o discutir sobre el caché y otras cosas, digamos que son idénticas). Trataré de indicarle la fuente que puede responder a su pregunta.
La diferencia podría residir en cómo se calculan sqrt y rsqrt. Puede leer más aquí http://www.intel.com/products/processor/manuals/ . Sugiero que empiece leyendo sobre las funciones del procesador que está utilizando, hay algo de información, especialmente sobre rsqrt (la CPU está usando una tabla de búsqueda interna con gran aproximación, lo que hace que sea mucho más simple obtener el resultado). Puede parecer que rsqrt es mucho más rápido que sqrt, que una operación mul adicional (que no es costosa) podría no cambiar la situación aquí.

Editar: pocos hechos que valdría la pena mencionar:
1. Una vez hice algunas micro optimizaciones para mi biblioteca de gráficos y utilicé rsqrt para calcular la longitud de los vectores. (en lugar de sqrt, he multiplicado mi suma de cuadrado por rsqrt, que es exactamente lo que has hecho en tus pruebas), y funcionó mejor.
2. Computar rsqrt usando una tabla de búsqueda simple puede ser más fácil, como para rsqrt, cuando x va al infinito, 1 / sqrt (x) va a 0, entonces para valores pequeños la función no cambia (mucho), mientras que para sqrt - va al infinito, entonces es ese caso simple;).

Además, aclaración: no estoy seguro de dónde lo he encontrado en los libros que he vinculado, pero estoy bastante seguro de haber leído que rsqrt está usando alguna tabla de búsqueda, y debe usarse solo, cuando el resultado no necesita ser exacto, aunque - podría estar equivocado también, como lo fue hace un tiempo :).

Answer 2

Es más rápido porque estas instrucciones ignoran los modos de redondeo y no manejan las excepciones de punto floatin ni los números desnormalizados. Por estas razones, es mucho más fácil canalizar, especular y ejecutar otras instrucciones de fp Fuera de servicio.

Answer 3

Esto también es cierto para la división. MULSS (a, RCPSS (b)) es mucho más rápido que DIVSS (a, b). De hecho, es aún más rápido incluso cuando aumenta su precisión con una iteración Newton-Raphson.

Intel y AMD recomiendan esta técnica en sus manuales de optimización. En aplicaciones que no requieren el cumplimiento de IEEE-754, la única razón para usar div / sqrt es la legibilidad del código.

Answer 4

Newton-Raphson converge al cero de f(x) usando incrementos iguales a -f/f'' donde f'' es la derivada.

Para x=sqrt(y) , puedes intentar resolver f(x) = 0 para x usando f(x) = x^2 - y ;

Entonces el incremento es: dx = -f/f'' = 1/2 (x - y/x) = 1/2 (x^2 - y) / x que tiene una división lenta en él.

Puedes probar otras funciones (como f(x) = 1/y - 1/x^2 ) pero serán igualmente complicadas.

Miremos 1/sqrt(y) ahora. Puedes probar f(x) = x^2 - 1/y , pero será igualmente complicado: dx = 2xy / (y*x^2 - 1) por ejemplo. Una opción alternativa no obvia para f(x) es: f(x) = y - 1/x^2

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

Ah! No es una expresión trivial, pero solo se multiplica, no divide. => ¡Más rápido!

Y: el paso de actualización completo new_x = x + dx luego lee:

x *= 3/2 - y/2 * x * x que también es fácil.

Answer 5

sqrtss da un resultado correctamente redondeado. rsqrtss da una aproximación al recíproco, con una precisión de aproximadamente 11 bits.

sqrtss está generando un resultado mucho más preciso, cuando se requiere precisión. rsqrtss existe para los casos en que una aproximación es suficiente, pero se requiere velocidad. Si lee la documentación de Intel, también encontrará una secuencia de instrucciones (aproximación recíproca de raíz cuadrada seguida de un solo paso de Newton-Raphson) que proporciona una precisión casi completa (~ 23 bits de precisión, si mal no recuerdo), y todavía es un tanto más rápido que sqrtss .

editar: si la velocidad es crítica, y realmente está llamando a esto en un bucle para muchos valores, debe usar las versiones vectorizadas de estas instrucciones, rsqrtps o sqrtps , que procesan cuatro flotantes por instrucción.