x86 vectorization sse simd absolute-value

x86 - La forma más rápida de calcular el valor absoluto utilizando SSE



vectorization simd (1)

Conozco 3 métodos, pero que yo sepa, solo se usan los primeros 2:

  1. Enmascarar el bit de signo con andps o andnotps .

    • Pros: Una instrucción rápida si la máscara ya está en un registro, lo que la hace perfecta para hacer esto muchas veces en un bucle.
    • Contras: la máscara puede no estar en un registro o peor, ni siquiera en un caché, lo que provoca una recuperación de memoria muy larga.

  2. Reste el valor de cero a negar, y luego obtenga el máximo del original y negado.

    • Pros: Costo fijo porque no se necesita nada para buscar, como una máscara.
    • Contras: siempre será más lento que el método de máscara si las condiciones son ideales, y tenemos que esperar a que se subps los subps antes de usar la instrucción maxps .

  3. Similar a la opción 2, reste el valor original de cero para negar, pero luego "bit a bit" y el resultado con el original usando andps . Realicé una prueba comparando esto con el método 2, y parece comportarse de manera idéntica al método 2, aparte de cuando se trata de NaN s, en cuyo caso el resultado será un NaN diferente al resultado del método 2.

    • Pros: debe ser un poco más rápido que el método 2 porque andps suele ser más rápido que maxps .
    • Contras: ¿Esto puede dar lugar a un comportamiento no deseado cuando los NaN están involucrados? Tal vez no, porque un NaN sigue siendo un NaN , incluso si es un valor diferente de NaN , ¿verdad?

Pensamientos y opiniones son bienvenidos.

TL; DR: en casi todos los casos, use pcmpeq / shift para generar una máscara y andps para usarla. Tiene la ruta crítica más corta de lejos (vinculada con constante de memoria), y no puede fallar en caché.

Cómo hacer eso con intrínsecos

Conseguir que el compilador emita pcmpeqd en un registro no inicializado puede ser complicado. (godbolt) . La mejor manera para gcc / icc parece ser

__m128 abs_mask(void){ // with clang, this turns into a 16B load, // with every calling function getting its own copy of the mask __m128i minus1 = _mm_set1_epi32(-1); return _mm_castsi128_ps(_mm_srli_epi32(minus1, 1)); } // MSVC is BAD when inlining this into loops __m128 vecabs_and(__m128 v) { return _mm_and_ps(abs_mask(), v); } __m128 sumabs(const __m128 *a) { // quick and dirty no alignment checks __m128 sum = vecabs_and(*a); for (int i=1 ; i < 10000 ; i++) { // gcc, clang, and icc hoist the mask setup out of the loop after inlining // MSVC doesn''t! sum = _mm_add_ps(sum, vecabs_and(a[i])); // one accumulator makes addps latency the bottleneck, not throughput } return sum; }

clang 3.5 y posterior "optimiza" el set1 / shift para cargar una constante desde la memoria. Sin pcmpeqd usará pcmpeqd para implementar set1_epi32(-1) . TODO: encuentra una secuencia de intrínsecos que produce el código de máquina deseado con el sonido metálico . Cargar una constante desde la memoria no es un desastre de rendimiento, pero hacer que cada función use una copia diferente de la máscara es bastante terrible.

MSVC: VS2013:

  • _mm_uninitialized_si128() no está definido.

  • _mm_cmpeq_epi32(self,self) en una variable no inicializada emitirá un movdqa xmm, [ebp-10h] en este caso de prueba (es decir, cargar algunos datos no inicializados de la pila. Esto tiene menos riesgo de una pérdida de caché que simplemente cargar la constante final de Sin embargo, Kumputer dice que MSVC no logró izar el pcmpeqd / psrld fuera del bucle (supongo que al vecabs ), por lo que esto no se puede usar a menos que usted mismo inline y eleve la constante de un bucle.

  • El uso de _mm_srli_epi32(_mm_set1_epi32(-1), 1) da como resultado un movdqa para cargar un vector de todos -1 (izado fuera del bucle) y un psrld dentro del bucle. Entonces eso es completamente horrible. Si vas a cargar una constante de 16B, debería ser el vector final. Tener instrucciones enteras que generan la máscara en cada iteración del ciclo también es horrible.

Sugerencias para MSVC: Renunciar a generar la máscara sobre la marcha, y simplemente escribir

const __m128 absmask = _mm_castsi128_ps(_mm_set1_epi32(~(1<<31));

Probablemente obtendrá la máscara almacenada en la memoria como una constante de 16B. Esperemos que no esté duplicado para cada función que lo use. Tener la máscara en una memoria constante es más probable que sea útil en el código de 32 bits, donde solo tiene 8 registros XMM, por lo que las vecabs solo pueden ANDPS con un operando de fuente de memoria si no tiene un registro libre para mantener una constante por ahí .

TODO: descubra cómo evitar duplicar la constante en todas partes donde está en línea. Probablemente usar una constante global, en lugar de un conjunto set1 , sería bueno. Pero luego debe inicializarlo, pero no estoy seguro de que los intrínsecos funcionen como inicializadores para las variables globales __m128 . Desea que vaya a la sección de datos de solo lectura, que no tenga un constructor que se ejecute al inicio del programa.

Alternativamente, use

__m128i minus1; // undefined #if _MSC_VER && !__INTEL_COMPILER minus1 = _mm_setzero_si128(); // PXOR is cheaper than MSVC''s silly load from the stack #endif minus1 = _mm_cmpeq_epi32(minus1, minus1); // or use some other variable here, which will probably cost a mov insn without AVX, unless the variable is dead. const __m128 absmask = _mm_castsi128_ps(_mm_srli_epi32(minus1, 1));

El PXOR extra es bastante barato, pero sigue siendo un uop y aún tiene 4 bytes en el tamaño del código. Si alguien tiene una mejor solución para superar la renuencia de MSVC a emitir el código que queremos, deje un comentario o edite. Sin embargo, esto no es bueno si está alineado en un bucle, porque pxor / pcmp / psrl estarán todos dentro del bucle.

Cargar una constante de 32 bits con movd y transmitir con shufps podría estar bien (una vez más, sin shufps , es probable que deba levantarlo manualmente de un bucle). Esas son 3 instrucciones (mov-inmediato a un GP reg, movd, shufps), y movd es lento en AMD donde la unidad vectorial se comparte entre dos núcleos enteros. (Su versión de hyperthreading).

Elegir la mejor secuencia asm

Ok, echemos un vistazo a esto, digamos Intel Sandybridge a través de Skylake, con un poco de mención de Nehalem. Vea las guías de microarquitectura de Agner Fog y los tiempos de instrucción para saber cómo resolví esto. También usé los números de Skylake a alguien vinculado en una publicación en los foros de http://realwordtech.com/ .

Digamos que el vector que queremos abs() está en xmm0 , y es parte de una larga cadena de dependencia como es típico para el código FP.

Así que supongamos que cualquier operación que no dependa de xmm0 puede comenzar varios ciclos antes de que xmm0 esté listo. He probado, y las instrucciones con operandos de memoria no agregan latencia adicional a una cadena de dependencia, suponiendo que la dirección del operando de memoria no es parte de la cadena dep (es decir, no es parte de la ruta crítica).

No tengo muy claro qué tan temprano puede comenzar una operación de memoria cuando es parte de una unidad de fusión con micro fusión. Según tengo entendido, el Re-Order Buffer (ROB) funciona con uops fusionados y rastrea los uops desde la emisión hasta la jubilación (168 (SnB) a 224 (SKL) entradas). También hay un programador que funciona en el dominio no fusionado, que solo contiene uops que tienen listos sus operandos de entrada pero que aún no se han ejecutado. uops puede emitir en el ROB (fusionado) y el planificador (no fusionado) al mismo tiempo cuando se decodifican (o cargan desde el caché de uop). Si entiendo esto correctamente, son 54 a 64 entradas en Sandybridge a Broadwell , y 97 en Skylake. Hay algunas especulaciones infundadas sobre que ya no es un planificador unificado (ALU / load-store) .

También se habla de que Skylake maneja 6 uops por reloj. Según tengo entendido, Skylake leerá líneas completas de uop-cache (hasta 6 uops) por reloj en un búfer entre el uop cache y el ROB. El problema con el ROB / planificador sigue siendo de 4 puntos. (Incluso nop sigue siendo 4 por reloj). Este búfer ayuda donde los límites de la línea de alineación de código / uop cache causan cuellos de botella para diseños anteriores de Sandybridge-microarch. Anteriormente pensé que esta "cola de problemas" era este búfer, pero aparentemente no lo es.

Sin embargo, funciona, el planificador es lo suficientemente grande como para tener los datos de la caché listos a tiempo, si la dirección no está en la ruta crítica .

1a: máscara con un operando de memoria

ANDPS xmm0, [mask] # in the loop

  • bytes: 7 insn, 16 datos. (AVX: 8 insn)
  • Uops de dominio fusionado: 1 * n
  • latencia agregada a la ruta crítica: 1c (suponiendo que el caché L1 se acierta)
  • rendimiento: 1 / c. (Skylake: 2 / c) (limitado por 2 cargas / c)
  • "latencia" si xmm0 estaba listo cuando se emitió esta información: ~ 4c en un acierto de caché L1.

1b: máscara de un registro

movaps xmm5, [mask] # outside the loop ANDPS xmm0, xmm5 # in a loop # or PAND xmm0, xmm5 # higher latency, but more throughput on Nehalem to Broadwell # or with an inverted mask, if set1_epi32(0x80000000) is useful for something else in your loop: VANDNPS xmm0, xmm5, xmm0 # It''s the dest that''s NOTted, so non-AVX would need an extra movaps

  • bytes: 10 insn + 16 datos. (AVX: 12 bytes insn)
  • Uops de dominio fusionado: 1 + 1 * n
  • latencia agregada a una cadena de dep: 1c (con la misma advertencia de caché-miss para principios del ciclo)
  • rendimiento: 1 / c. (Skylake: 3 / c)

PAND tiene un rendimiento de 3 / c en Nehalem a Broadwell, pero latencia = 3c (si se usa entre dos operaciones de dominio FP, y aún peor en Nehalem). Supongo que solo el puerto 5 tiene el cableado para reenviar operaciones bit a bit directamente a las otras unidades de ejecución FP (pre Skylake). Pre-Nehalem, y en AMD, las operaciones de FP bit a bit se tratan de manera idéntica a las operaciones de FP enteras, por lo que pueden ejecutarse en todos los puertos, pero tienen un retraso de reenvío.

1c: genera la máscara sobre la marcha:

# outside a loop PCMPEQD xmm5, xmm5 # set to 0xff... Recognized as independent of the old value of xmm5, but still takes an execution port (p1/p5). PSRLD xmm5, 1 # 0x7fff... # port0 # or PSLLD xmm5, 31 # 0x8000... to set up for ANDNPS ANDPS xmm0, xmm5 # in the loop. # port5

  • bytes: 12 (AVX: 13)
  • Uops de dominio fusionado: 2 + 1 * n (sin operaciones de memoria)
  • latencia agregada a una cadena dep: 1c
  • rendimiento: 1 / c. (Skylake: 3 / c)
  • rendimiento para los 3 uops: 1 / c saturando los 3 puertos ALU vectoriales
  • "latencia" si xmm0 estaba listo cuando se emitió esta secuencia (sin bucle): 3c (+1c posible retraso de derivación en SnB / IvB si ANDPS tiene que esperar a que estén listos los datos enteros. Agner Fog dice que en algunos casos no hay retraso adicional para entero-> FP-booleano en SnB / IvB.)

Esta versión todavía requiere menos memoria que las versiones con una constante de 16B en la memoria. También es ideal para una función llamada con poca frecuencia, porque no hay carga para sufrir una pérdida de caché.

El "retraso de derivación" no debería ser un problema. Si xmm0 es parte de una larga cadena de dependencia, las instrucciones de generación de máscara se ejecutarán con mucha anticipación, por lo que el resultado entero en xmm5 tendrá tiempo de llegar a ANDPS antes de que xmm0 esté listo, incluso si toma el carril lento.

Haswell no tiene retraso de derivación para resultados enteros -> FP booleano, según las pruebas de Agner Fog. Su descripción para SnB / IvB dice que este es el caso con las salidas de algunas instrucciones enteras. Entonces, incluso en el caso de inicio de una cadena de "inicio permanente" donde xmm0 está listo cuando se emite esta secuencia de instrucciones, es solo 3c en * bueno, 4c en * Puente. La latencia probablemente no importa si las unidades de ejecución están limpiando la acumulación de Uops tan rápido como se emiten.

De cualquier manera, la salida de ANDPS estará en el dominio FP y no tendrá retraso de derivación si se usa en MULPS o algo así.

En Nehalem, las demoras de bypass son 2c. Por lo tanto, al comienzo de una cadena de dep (por ejemplo, después de una predicción errónea de una sucursal o una falta de $) en Nehalem, "latencia" si xmm0 estaba listo cuando esta secuencia emitida es 5c. Si le importa mucho Nehalem, y espera que este código sea lo primero que se ejecute después de predicciones erróneas frecuentes de la rama o paradas de tuberías similares que dejan a la maquinaria OoOE incapaz de comenzar a calcular la máscara antes de que xmm0 esté listo, entonces esto podría no ser La mejor opción para situaciones sin bucle.

2a: AVX max (x, 0-x)

VXORPS xmm5, xmm5, xmm5 # outside the loop VSUBPS xmm1, xmm5, xmm0 # inside the loop VMAXPS xmm0, xmm0, xmm1

  • bytes: AVX: 12
  • Uops de dominio fusionado: 1 + 2 * n (sin operaciones de memoria)
  • latencia agregada a una cadena dep: 6c (Skylake: 8c)
  • rendimiento: 1 por 2c (dos puertos1 uops). (Skylake: 1 / c, suponiendo que MAXPS use los mismos dos puertos que SUBPS ).

Skylake deja caer la unidad de adición de vector-FP por separado, y hace adiciones de vector en las unidades de FMA en los puertos 0 y 1. Esto duplica el rendimiento de adición de FP, a un costo de 1c más de latencia. La latencia de FMA ha bajado a 4 (de 5 en * pozo) . x87 FADD todavía tiene una latencia de 3 ciclos, por lo que todavía hay un sumador escalar de 80 bits-FP de 3 ciclos, pero solo en un puerto.

2b: igual pero sin AVX:

# inside the loop XORPS xmm1, xmm1 # not on the critical path, and doesn''t even take an execution unit on SnB and later SUBPS xmm1, xmm0 MAXPS xmm0, xmm1

  • bytes: 9
  • Uops de dominio fusionado: 3 * n (sin operaciones de memoria)
  • latencia agregada a una cadena dep: 6c (Skylake: 8c)
  • rendimiento: 1 por 2c (dos puertos1 uops). (Skylake: 1 / c)
  • "latencia" si xmm0 estaba listo cuando se emitió esta secuencia (sin bucle): igual

Poner a cero un registro con un idioma de xorps same,same cero que el procesador reconoce (como xorps same,same ) se maneja durante el cambio de nombre del registro en las microarquitecturas de la familia Sandbridge, y tiene una latencia cero y un rendimiento de 4 / c. (Igual que los movimientos reg-> reg que IvyBridge y posteriores pueden eliminar).

Sin embargo, no es gratis: todavía toma una uop en el dominio fusionado, por lo que si su código solo tiene un cuello de botella por la tasa de emisión de 4uop / ciclo, esto lo ralentizará. Esto es más probable con hyperthreading.

3: ANDPS (x, 0-x)

VXORPS xmm5, xmm5, xmm5 # outside the loop. Without AVX: zero xmm1 inside the loop VSUBPS xmm1, xmm5, xmm0 # inside the loop VANDPS xmm0, xmm0, xmm1

  • bytes: AVX: 12 no AVX: 9
  • Uops de dominio fusionado: 1 + 2 * n (sin operaciones de memoria). (Sin AVX: 3 * n)
  • latencia agregada a una cadena dep: 4c (Skylake: 5c)
  • rendimiento: 1 / c (saturar p1 y p5). Skylake: 3 / 2c: (3 vectores uops / ciclo) / (uop_p01 + uop_p015).
  • "latencia" si xmm0 estaba listo cuando se emitió esta secuencia (sin bucle): igual

Esto debería funcionar, pero IDK tampoco lo que sucede con NaN. Buena observación de que ANDPS tiene una latencia más baja y no requiere el puerto de agregar FPU.

Este es el tamaño más pequeño con no AVX.

4: desplazamiento a izquierda / derecha:

PSLLD xmm0, 1 PSRLD xmm0, 1

  • bytes: 10 (AVX: 10)
  • Uops de dominio fusionado: 2 * n
  • latencia agregada a una cadena dep: 4c (2c + retardos de derivación)
  • rendimiento: 1 / 2c (saturado p0, también utilizado por FP mul). (Skylake 1 / c: rendimiento de desplazamiento de vector duplicado)

  • "latencia" si xmm0 estaba listo cuando se emitió esta secuencia (sin bucle): igual

    Este es el más pequeño (en bytes) con AVX.

    Esto tiene posibilidades donde no puede ahorrar un registro, y no se usa en un bucle. (En bucle sin reglas de sobra, prob. andps xmm0, [mask] ).

Supongo que hay un retraso de derivación de 1c desde FP a cambio de número entero, y luego otro 1c en el camino de regreso, por lo que esto es tan lento como SUBPS / ANDPS. Ahorra un uop sin puerto de ejecución, por lo que tiene ventajas si el rendimiento del uop de dominio fusionado es un problema, y ​​no puede extraer la generación de máscara de un bucle. (por ejemplo, porque esto está en una función que se llama en un bucle, no en línea).

Cuándo usar qué: cargar la máscara desde la memoria simplifica el código, pero tiene el riesgo de perder el caché. Y ocupa 16B de datos de ro en lugar de 9 bytes de instrucciones.

  • Necesario en un bucle: 1c : generar la máscara fuera del bucle (con pcmp / shift); use un solo andps adentro. Si no puede ahorrar el registro, andps xmm0, [rsp + mask_local] en la pila y 1a : andps xmm0, [rsp + mask_local] . (Generar y almacenar es menos probable que provoque un error de caché que una constante). Solo agrega 1 ciclo a la ruta crítica de cualquier manera, con 1 instrucción de un solo impulso dentro del bucle. Es un puerto 5 uop, por lo que si su bucle satura el puerto aleatorio y no está ligado a la latencia, PAND podría ser mejor. (SnB / IvB tienen unidades de barajado en p1 / p5, pero Haswell / Broadwell / Skylake solo puede barajar en p5. Skylake aumentó el rendimiento de (V)(P)BLENDV , pero no otras operaciones de puertos de barajado. Si el AIDA numera son correctos, no AVX BLENDV es 1c lat ~ 3 / c tput, pero AVX BLENDV es 2c lat, 1 / c tput (sigue siendo una mejora de tput sobre Haswell)

  • Necesario una vez en una función frecuentemente llamada sin bucle (por lo que no puede amortizar la generación de máscaras en múltiples usos):

    1. Si el rendimiento de uop es un problema: 1a : andps xmm0, [mask] . La pérdida ocasional de caché se debe amortizar sobre los ahorros en uops, si ese fue realmente el cuello de botella.
    2. Si la latencia no es un problema (la función solo se usa como parte de cadenas dep cortas no transportadas en bucle, p. Ej. arr[i] = abs(2.0 + arr[i]); ), y desea evitar la constante en memoria: 4 , porque solo son 2 uops. Si los abs aparecen al inicio o al final de una cadena de dep, no habrá un retraso de derivación de una carga o una tienda.
    3. Si el rendimiento de uop no es un problema: 1c : generar sobre la marcha con entero pcmpeq / shift . No se puede perder el caché, y solo agrega 1c a la ruta crítica.

  • Necesario (fuera de cualquier bucle) en una función llamada con poca frecuencia: solo optimice para el tamaño (ninguna versión pequeña usa una constante de memoria). no AVX: 3 . AVX: 4 . No son malos y no pueden fallar en caché. La latencia de 4 ciclos es peor para la ruta crítica de la que obtendría con la versión 1c, por lo que si no cree que 3 bytes de instrucciones es un gran problema, elija 1c . La versión 4 es interesante para situaciones de presión de registro cuando el rendimiento no es importante y desea evitar derramar cualquier cosa.

  • CPU AMD: hay un retraso de derivación hacia / desde ANDPS (que por sí solo tiene una latencia de 2c), pero creo que sigue siendo la mejor opción. Todavía supera la latencia de 5-6 ciclos de SUBPS . MAXPS es latencia 2c. Con las altas latencias de las operaciones de FP en las CPU de la familia Bulldozer, es aún más probable que la ejecución fuera de orden pueda generar su máscara sobre la marcha a tiempo para que esté lista cuando el otro operando para ANDPS esté . Supongo que Bulldozer a través de Steamroller no tiene una unidad de adición de FP separada, y en su lugar hace adiciones y multiplicaciones de vectores en la unidad FMA. 3 siempre será una mala elección en las CPU de la familia Bulldozer de AMD. 2 se ve mejor en ese caso, debido a un retraso de derivación más corto del dominio fma al dominio fp y viceversa. Consulte la guía de microarquitectura de Agner Fog, página 182 ( 15.11 Retraso de datos entre diferentes dominios de ejecución ).

  • Silvermont: Latencias similares a SnB. Todavía vaya con 1c para bucles, y prob. También para un solo uso. Silvermont está fuera de servicio, por lo que puede preparar la máscara con anticipación para agregar solo 1 ciclo a la ruta crítica.