optimization - resta - suma de vectores metodo grafico

La forma más rápida de hacer una suma de vector flotante horizontal en x86

Question

Tienes un vector de tres (o cuatro) carrozas. ¿Cuál es la forma más rápida de sumarlos?

¿Es SSE (movaps, shuffle, add, movd) siempre más rápido que x87? ¿Las instrucciones de suma horizontal en SSE4.2 valen la pena? ¿Cuánto cuesta mudarse a la FPU, luego a faddp, faddp? ¿Cuál es la secuencia de instrucción específica más rápida?

"Trate de arreglar las cosas para que pueda sumar cuatro vectores a la vez" no se aceptarán como respuesta. :-)

Answer 1

SSE2

Los cuatro:

const __m128 t = _mm_add_ps(v, _mm_movehl_ps(v, v));
const __m128 sum = _mm_add_ss(t, _mm_shuffle_ps(t, t, 1));

r1 + r2 + r3:

const __m128 t1 = _mm_movehl_ps(v, v);
const __m128 t2 = _mm_add_ps(v, t1);
const __m128 sum = _mm_add_ss(t1, _mm_shuffle_ps(t2, t2, 1));

He encontrado que tienen la misma velocidad que HADDPS dobles (pero no he medido demasiado de cerca).

Answer 2

Aquí hay algunas versiones ajustadas según la guía de microarch de Agner Fog y las tablas de instrucciones. Ver también la wiki de la etiqueta x86 . Deben ser eficientes en cualquier CPU, sin cuellos de botella importantes. (p. ej., evité cosas que ayudarían a uno a caminar un poco, pero sería lento en otro uarch). El tamaño del código también se minimiza.

La expresión idiomática 2x hadd común solo es buena para el tamaño del código, no para la velocidad en ninguna CPU existente. Hay casos de uso para él (ver abajo), pero este no es uno de ellos.

También incluí una versión de AVX. Cualquier tipo de reducción horizontal con AVX / AVX2 debe comenzar con una vextractf128 y una operación "vertical" para reducir hasta un vector XMM ( __m128 ).

Vea la salida de asm de todo este código en el Godbolt Compiler Explorer . Ver también mis mejoras a la biblioteca de clases de vectores en C ++ de Agner Fog funciones horizontal_add . ( hilo de tablero de mensajes y código en github ). Utilicé macros CPP para seleccionar combinaciones óptimas para el tamaño de código para SSE2, SSE4 y AVX, y para evitar movdqa cuando AVX no está disponible.

Hay compensaciones a considerar:

• tamaño de código: más pequeño es mejor para L1 I-caché y para obtención de código del disco (binarios más pequeños). El tamaño total del binario es importante para las decisiones del compilador realizadas repetidamente en todo el programa. Si te estás molestando en codificar manualmente algo con intrínsecos, vale la pena gastar unos pocos bytes de código si te da una aceleración para todo el programa (ten cuidado con las microbenchmarks que hacen que el desenrollado se vea bien).
• tamaño de la memoria caché uop: a menudo más precioso que L1 I $. 4 instrucciones single-uop pueden ocupar menos espacio que 2 haddps , por lo que esto es muy relevante aquí.
• latencia: a veces relevante
• rendimiento: usualmente irrelevantes, las sumas horizontales no deberían estar en el ciclo más interno.
• total de uops de dominio fusionado: si el código circundante no tiene un cuello de botella en el mismo puerto que usa el hsum, este es un proxy para el impacto del hsum en el rendimiento del todo.

Cuando un agregado horizontal es poco frecuente :

Las CPU sin uop-cache pueden favorecer 2x haddps : se ralentiza cuando se ejecuta, pero eso no ocurre con frecuencia. Siendo solo 2 instrucciones, se minimiza el impacto en el código circundante (tamaño I $).

Las CPU con uop-cache probablemente favorecerán algo que requiere menos uops, incluso si se trata de más instrucciones / más tamaño de código x86. El total de las líneas de caché uops utilizadas es lo que queremos minimizar, lo cual no es tan simple como minimizar el total de uops (las ramas tomadas y los límites de 32B siempre comienzan una nueva línea de caché uop).

De todos modos, dicho esto, las sumas horizontales surgen mucho , así que aquí está mi intento de elaborar cuidadosamente algunas versiones que se compilan muy bien. No se compara con ningún hardware real, o incluso se prueba cuidadosamente. Puede haber errores en las constantes de mezcla o algo así.

Si está haciendo una versión de respaldo / línea base de su código, recuerde que solo las CPU antiguas lo ejecutarán ; las CPU más nuevas ejecutarán su versión de AVX, o SSE4.1 o lo que sea.

Las antiguas CPU como K8 y Core2 (merom) y anteriores solo tienen unidades de mezcla de 64 bits . Core2 tiene unidades de ejecución de 128 bits para la mayoría de las instrucciones, pero no para las mezclas. (Pentium M y K8 manejan todas las instrucciones del vector 128b como dos mitades de 64 bits).

Los movhlps como los movhlps que mueven datos en fragmentos de 64 bits (sin mezcla dentro de las mitades de 64 bits) también son rápidos.

En CPUs antiguas con barajados lentos :

• movhlps (Merom: 1uop) es significativamente más rápido que shufps (Merom: 3uops). En Pentium-M, más barato que movaps . Además, se ejecuta en el dominio de FP en Core2, evitando los retrasos de derivación de otras mezclas.
• unpcklpd es más rápido que unpcklps .
• pshufd es lento, pshuflw / pshufhw son rápidos (porque solo mezclan una mitad de 64 bits)
• pshufb mm0 (MMX) es rápido, pshufb xmm0 es lento.
• haddps es muy lento (6uops en Merom y Pentium M)
• movshdup (Merom: 1uop) es interesante : es el único 1uop ins que se mezcla dentro de los elementos de 64b.

shufps en Core2 (incluido Penryn) trae datos al dominio entero, causando un retraso de derivación para regresarlo a las unidades de ejecución de FP para addps , pero movhlps está completamente en el dominio de FP. shufpd también se ejecuta en el dominio flotante.

movshdup ejecuta en el dominio entero, pero es solo un uop.

AMD K10, Intel Core2 (Penryn / Wolfdale) y todas las CPU posteriores ejecutan todos los cambios de xmm como un único uop. (Pero tenga en cuenta el retraso de bypass con shufps en Penryn, evitado con movhlps )

Sin AVX, evitar las instrucciones de movaps / movdqa desperdiciadas requiere una elección cuidadosa de las movdqa . Solo unas pocas modificaciones funcionan como copiar y mezclar, en lugar de modificar el destino. Las mezclas que combinan datos de dos entradas (como unpck* o movhlps ) se pueden usar con una variable tmp que ya no se necesita en lugar de _mm_movehl_ps(same,same) .

Algunos de ellos se pueden hacer más rápido (guardar un MOVAPS) pero más feo / menos "limpio" tomando un archivo ficticio para usarlo como destino de una mezcla aleatoria inicial. Por ejemplo:

// Use dummy = a recently-dead variable that vec depends on,
//  so it doesn''t introduce a false dependency,
//  and the compiler probably still has it in a register
__m128d highhalf_pd(__m128d dummy, __m128d vec) {
#ifdef __AVX__
    // With 3-operand AVX instructions, don''t create an extra dependency on something we don''t need anymore.
    (void)dummy;
    return _mm_unpackhi_pd(vec, vec);
#else
    // Without AVX, we can save a MOVAPS with MOVHLPS into a dead register
    __m128 tmp = _mm_castpd_ps(dummy);
    __m128d high = _mm_castps_pd(_mm_movehl_ps(tmp, _mm_castpd_ps(vec)));
    return high;
#endif
}

SSE1 (también conocido como SSE):

float hsum_ps_sse1(__m128 v) {                                  // v = [ D C | B A ]
    __m128 shuf   = _mm_shuffle_ps(v, v, _MM_SHUFFLE(2, 3, 0, 1));  // [ C D | A B ]
    __m128 sums   = _mm_add_ps(v, shuf);      // sums = [ D+C C+D | B+A A+B ]
    shuf          = _mm_movehl_ps(shuf, sums);      //  [   C   D | D+C C+D ]  // let the compiler avoid a mov by reusing shuf
    sums          = _mm_add_ss(sums, shuf);
    return    _mm_cvtss_f32(sums);
}
    # gcc 5.3 -O3:  looks optimal
    movaps  xmm1, xmm0     # I think one movaps is unavoidable, unless we have a 2nd register with known-safe floats in the upper 2 elements
    shufps  xmm1, xmm0, 177
    addps   xmm0, xmm1
    movhlps xmm1, xmm0     # note the reuse of shuf, avoiding a movaps
    addss   xmm0, xmm1

    # clang 3.7.1 -O3:  
    movaps  xmm1, xmm0
    shufps  xmm1, xmm1, 177
    addps   xmm1, xmm0
    movaps  xmm0, xmm1
    shufpd  xmm0, xmm0, 1
    addss   xmm0, xmm1

Informé de un error de clang sobre cómo pesimizar las mezclas . Tiene su propia representación interna para barajar, y la convierte en barajaduras. gcc más a menudo usa las instrucciones que coinciden directamente con el intrínseco que usaste.

A menudo, el clang es mejor que el gcc, en un código donde la elección de la instrucción no se ajusta a mano, o la propagación constante puede simplificar las cosas incluso cuando las características intrínsecas son óptimas para el caso no constante. En general, es bueno que los compiladores funcionen como un compilador adecuado para intrínsecos, no solo como ensambladores. Los compiladores a menudo pueden generar un buen asm a partir del escalar C que ni siquiera intenta funcionar como lo haría un buen asm. Finalmente, los compiladores tratarán los intrínsecos como solo otro operador C como entrada para el optimizador.

SSE3

float hsum_ps_sse3(__m128 v) {
    __m128 shuf = _mm_movehdup_ps(v);        // broadcast elements 3,1 to 2,0
    __m128 sums = _mm_add_ps(v, shuf);
    shuf        = _mm_movehl_ps(shuf, sums); // high half -> low half
    sums        = _mm_add_ss(sums, shuf);
    return        _mm_cvtss_f32(sums);
}

    # gcc 5.3 -O3: perfectly optimal code
    movshdup    xmm1, xmm0
    addps       xmm0, xmm1
    movhlps     xmm1, xmm0
    addss       xmm0, xmm1

Esto tiene varias ventajas:

• no requiere ninguna copia de movaps para evitar movaps destructivas (sin AVX): el movshdup xmm1, xmm2 es de solo escritura, por lo que crea tmp de un registro muerto para nosotros. Esta es también la razón por la que utilicé movehl_ps(tmp, sums) lugar de movehl_ps(sums, sums) .

• pequeño tamaño de código Las instrucciones de mezcla son pequeñas: movhlps es de 3 bytes, movshdup es de 4 bytes (lo mismo que shufps ). No se requiere byte inmediato, por lo que con AVX, vshufps tiene 5 bytes, pero vmovhlps y vmovshdup son 4.

Podría guardar otro byte con addps lugar de addss . Como esto no se usará dentro de los bucles internos, la energía extra para cambiar los transistores adicionales es probablemente insignificante. Las excepciones FP de los 3 elementos superiores no son un riesgo, ya que todos los elementos contienen datos FP válidos. Sin embargo, clang / LLVM realmente "entiende" el vector se mezcla, y emite un mejor código si sabe que solo importa el elemento bajo.

Al igual que la versión SSE1, agregar los elementos impares a sí mismos puede causar excepciones FP (como desbordamiento) que de otro modo no sucederían, pero esto no debería ser un problema. Los denormales son lentos, pero el IIRC que produce un resultado + Inf no está en la mayoría de los uarques.

Optimización SSE3 para tamaño de código

Si el tamaño del código es su mayor preocupación, dos haddps ( _mm_hadd_ps ) harán el truco (respuesta de Paul R). Este es también el más fácil de escribir y recordar. No es rápido , sin embargo. Incluso Intel Skylake todavía decodifica cada haddps a 3 uops, con una latencia de 6 ciclos. Por lo tanto, aunque ahorra bytes de código de máquina (L1 I-cache), ocupa más espacio en el uop-cache más valioso. Casos de uso reales para haddps : un problema de transposición y suma , o hacer algunas escalas en un paso intermedio en esta atoi() SSE atoi() .

AVX:

Esta versión guarda un byte de código frente a la respuesta de Marat a la pregunta de AVX .

#ifdef __AVX__
float hsum256_ps_avx(__m256 v) {
    __m128 vlow  = _mm256_castps256_ps128(v);
    __m128 vhigh = _mm256_extractf128_ps(v, 1); // high 128
           vlow  = _mm_add_ps(vlow, vhigh);     // add the low 128
    return hsum_ps_sse3(vlow);         // and inline the sse3 version, which is optimal for AVX
    // (no wasted instructions, and all of them are the 4B minimum)
}
#endif

 vmovaps xmm1,xmm0               # huh, what the heck gcc?  Just extract to xmm1
 vextractf128 xmm0,ymm0,0x1
 vaddps xmm0,xmm1,xmm0
 vmovshdup xmm1,xmm0
 vaddps xmm0,xmm1,xmm0
 vmovhlps xmm1,xmm1,xmm0
 vaddss xmm0,xmm0,xmm1
 vzeroupper 
 ret

Precisión doble:

double hsum_pd_sse2(__m128d vd) {                      // v = [ B | A ]
    __m128 undef  = _mm_undefined_ps();                       // don''t worry, we only use addSD, never touching the garbage bits with an FP add
    __m128 shuftmp= _mm_movehl_ps(undef, _mm_castpd_ps(vd));  // there is no movhlpd
    __m128d shuf  = _mm_castps_pd(shuftmp);
    return  _mm_cvtsd_f64(_mm_add_sd(vd, shuf));
}

# gcc 5.3.0 -O3
    pxor    xmm1, xmm1          # hopefully when inlined, gcc could pick a register it knew wouldn''t cause a false dep problem, and avoid the zeroing
    movhlps xmm1, xmm0
    addsd   xmm0, xmm1


# clang 3.7.1 -O3 again doesn''t use movhlps:
    xorpd   xmm2, xmm2          # with  #define _mm_undefined_ps _mm_setzero_ps
    movapd  xmm1, xmm0
    unpckhpd        xmm1, xmm2
    addsd   xmm1, xmm0
    movapd  xmm0, xmm1    # another clang bug: wrong choice of operand order


// This doesn''t compile the way it''s written
double hsum_pd_scalar_sse2(__m128d vd) {
    double tmp;
    _mm_storeh_pd(&tmp, vd);       // store the high half
    double lo = _mm_cvtsd_f64(vd); // cast the low half
    return lo+tmp;
}

    # gcc 5.3 -O3
    haddpd  xmm0, xmm0   # Lower latency but less throughput than storing to memory

    # ICC13
    movhpd    QWORD PTR [-8+rsp], xmm0    # only needs the store port, not the shuffle unit
    addsd     xmm0, QWORD PTR [-8+rsp]

Almacenar en la memoria y volver evita un ALU uop. Eso es bueno si la presión de puerto aleatorio, o UUP de ALU en general, es un cuello de botella. (Tenga en cuenta que no necesita sub rsp, 8 ni nada, porque x86-64 SysV ABI proporciona una zona roja que los manejadores de señal no pisarán).

Algunas personas almacenan en una matriz y suman todos los elementos, pero los compiladores generalmente no se dan cuenta de que el elemento bajo de la matriz todavía está allí en un registro de antes de la tienda.

Entero:

pshufd es una copia y reproducción conveniente. Los cambios de bit y byte están desafortunadamente en el lugar, y punpckhqdq pone la mitad alta del destino en la mitad baja del resultado, opuesto a la forma en que movhlps puede extraer la mitad alta en un registro diferente.

Usar movhlps para el primer paso puede ser bueno en algunas CPU, pero solo si tenemos un registro de scratch. pshufd es una opción segura, y rápido en todo después de Merom.

int hsum_epi32_sse2(__m128i x) {
#ifdef __AVX__
    __m128i hi64  = _mm_unpackhi_epi64(x, x);           // 3-operand non-destructive AVX lets us save a byte without needing a mov
#else
    __m128i hi64  = _mm_shuffle_epi32(x, _MM_SHUFFLE(1, 0, 3, 2));
#endif
    __m128i sum64 = _mm_add_epi32(hi64, x);
    __m128i hi32  = _mm_shufflelo_epi16(sum64, _MM_SHUFFLE(1, 0, 3, 2));    // Swap the low two elements
    __m128i sum32 = _mm_add_epi32(sum64, hi32);
    return _mm_cvtsi128_si32(sum32);       // SSE2 movd
    //return _mm_extract_epi32(hl, 0);     // SSE4, even though it compiles to movd instead of a literal pextrd r32,xmm,0
}

    # gcc 5.3 -O3
    pshufd xmm1,xmm0,0x4e
    paddd  xmm0,xmm1
    pshuflw xmm1,xmm0,0x4e
    paddd  xmm0,xmm1
    movd   eax,xmm0

int hsum_epi32_ssse3_slow_smallcode(__m128i x){
    x = _mm_hadd_epi32(x, x);
    x = _mm_hadd_epi32(x, x);
    return _mm_cvtsi128_si32(x);
}

En algunas CPU, es seguro usar mezclas FP en datos enteros. No hice esto, ya que en CPU modernas ahorraría como máximo 1 o 2 bytes de código, sin ganancias de velocidad (aparte de los efectos de tamaño / alineación de código).

Answer 3

Definitivamente probaría SSE 4.2. Si está haciendo esto varias veces (supongo que lo es si el rendimiento es un problema), puede precargar un registro con (1,1,1,1), y luego hacer varios dot4 (my_vec (s), one_vec) en eso. Sí, hace una multiplicación superflua, pero estos son bastante baratos en la actualidad y es probable que esa operación esté dominada por las dependencias horizontales, que pueden estar más optimizadas en la nueva función del producto punto SSE. Debe probar para ver si supera el doble agregado horizontal que publicó Paul R.

También sugiero compararlo con código escalar recto (o SSE escalar). Curiosamente, a menudo es más rápido (generalmente porque internamente se serializa pero se canaliza firmemente mediante el uso de la derivación de registro, donde las instrucciones horizontales especiales no se pueden aplicar rápidamente) a menos que están ejecutando un código similar a SIMT, que parece que no lo es (de lo contrario, harías productos de cuatro puntos).

Answer 4

Puede hacerlo en dos instrucciones HADDPS en SSE3:

v = _mm_hadd_ps(v, v);
v = _mm_hadd_ps(v, v);

Esto pone la suma en todos los elementos.