Vectorizar con almacenamientos intermedios no alineados: usar VMASKMOVPS: ¿generar una máscara a partir de un recuento de desalineación? O no usar ese nombre en absoluto

gcc 5.3 con -O3 -mavx -mtune=haswell para x86-64 hace un código sorprendentemente voluminoso para manejar entradas potencialmente desalineadas para código como:

 // convenient simple example of compiler input // I'm not actually interested in this for any real program void floatmul(float *a) { for (int i=0; i<1024 ; i++) a[i] *= 2; } 

clang usa instrucciones de carga / almacenamiento desalineadas, pero gcc hace una introducción / outro escalar y un bucle de vector alineado: pela las primeras iteraciones sin alinear de hasta 7, desenrollando completamente eso en una secuencia de

  vmovss xmm0, DWORD PTR [rdi] vaddss xmm0, xmm0, xmm0 ; multiply by two vmovss DWORD PTR [rdi], xmm0 cmp eax, 1 je .L13 vmovss xmm0, DWORD PTR [rdi+4] vaddss xmm0, xmm0, xmm0 vmovss DWORD PTR [rdi+4], xmm0 cmp eax, 2 je .L14 ... 

Esto parece bastante terrible, esp. para CPU con una memoria caché uop. Informé de un error de gcc al respecto, con una sugerencia de código más pequeño / mejor que gcc podría usar al pelar iteraciones desalineadas. Sin embargo, probablemente aún no sea óptimo.

Esta pregunta es sobre lo que realmente sería óptimo con AVX . Estoy preguntando sobre las soluciones de casos generales que gcc y otros comstackdores podrían / ​​deberían usar. (No encontré ninguna lista de correo gcc hits con discusión sobre esto, pero no pasó mucho tiempo buscando).


Probablemente haya múltiples respuestas, ya que lo óptimo para -mtune=haswell probablemente sea diferente de lo que es óptimo para -mtune=bdver3 ( -mtune=bdver3 ). Y luego está la cuestión de qué es lo óptimo al permitir extensiones de conjuntos de instrucciones (por ejemplo, AVX2 para cosas enteras de 256b, BMI1 para convertir un conteo en una máscara de bits en menos instrucciones).

Conozco la guía Optimizing Assembly de Agner Fog, Sección 13.5. Acceso a datos no alineados y vectores parciales . Sugiere usar accesos no alineados, hacer una escritura solapada al inicio y / o al final, o mezclar datos de accesos alineados (pero PALIGNR solo toma un recuento imm8, por lo que 2x pshufb / por ). VMASKMOVPS como no útil, probablemente por lo mal que funciona en AMD. Sospecho que si está afinando Intel, vale la pena considerarlo. No es obvio cómo generar la máscara correcta, de ahí el título de la pregunta.


Podría resultar que es mejor simplemente usar accesos no alineados, como clang. Para los buffers cortos, la sobrecarga de la alineación puede eliminar cualquier beneficio de evitar divisiones de caché para el bucle principal. Para los buffers grandes, la memoria principal o L3 como el cuello de botella pueden ocultar la penalización por divisiones de caché. Si alguien tiene datos experimentales para respaldar esto con cualquier código real que haya ajustado, esa también es información útil.


VMASKMOVPS parece útil para los objectives de Intel. (La versión SSE es horrible, con una pista implícita no temporal, pero la versión AVX no tiene eso. Incluso hay una nueva intrínseca para asegurarse de no obtener la versión SSE para los operandos 128b: _mm128_maskstore_ps ) La versión AVX solo es un poco lento en Haswell :

  • 3 uops / 4c de latencia / 1 por 2c de rendimiento como carga.
  • 4 uops / 14c de latencia / 1 por 2c de rendimiento como una tienda 256b.
  • 4 uops / 13c de latencia / 1 por cada 1c como una tienda 128b.

La forma de la tienda sigue siendo inusualmente lenta en las CPU AMD, tanto Jaguar (1 por 22 c tput) como Bulldozer-family: 1 por 16c en Steamroller (similar en Bulldozer), o 1 por ~ 180c en Piledriver.

Pero si queremos usar VMASKMOVPS , necesitamos un vector con el bit alto establecido en cada elemento que realmente debe ser cargado / almacenado. PALIGNR y PSRLDQ (para usar en un vector de todos) solo toman recuentos de tiempo de comstackción.

Tenga en cuenta que los otros bits no importan: no tiene que ser todos, por lo que es posible dispersar algunos bits en los bits más altos de los elementos.

Cargue una máscara para VMOVMASKPS desde una ventana a una tabla. AVX2 o AVX1 con algunas instrucciones adicionales o una tabla más grande.

La máscara también se puede usar para ANDPS en registros en una reducción que necesita contar cada elemento exactamente una vez. Como señala Stephen Canon en los comentarios sobre el OP, las cargas de canalización pueden permitir que las tiendas desalineadas superpuestas funcionen incluso para una función de reescritura en el lugar como el ejemplo que elegí, por lo que VMASKMOVPS NO es la mejor opción aquí.


Esto debería ser bueno en las CPU Intel, especialmente Haswell y más tarde para AVX2.

El método de Agner Fog para obtener una máscara pshufb en realidad proporcionó una idea que es muy eficiente: hacer una carga desalineada tomando una ventana de datos de una tabla. En lugar de una tabla gigante de máscaras, use un índice como una forma de hacer un cambio de byte en los datos en la memoria.


Máscaras en orden de bytes LSB-first (según se almacenan en la memoria), no la notación habitual para los elementos {X3,X2,X1,X0} en un vector. Tal como está escrito, se alinean con una ventana alineada que incluye el inicio / final de la matriz de entrada en la memoria.

  • iniciar el recuento de desalineación = 0: máscara = todos-uno (caso alineado)
  • start desaline count = 1: máscara = {0,-1,-1,-1,-1,-1,-1,-1} (omita uno en los primeros 32B)
  • start desaline count = 7: máscara = {0, 0, 0, 0, 0, 0, 0,-1} (omita todos menos uno en los primeros 32B)

  • recuento de desalineación final = 0: sin elementos finales. mask = all-ones (caso alineado).
    este es el caso extraño, no similar a count = 1 . Un par de instrucciones adicionales para este caso especial vale la pena evitar una iteración de bucle adicional y una limpieza con una máscara de ceros al cien por cien.

  • recuento de desalineación final = 1: un elemento final. máscara = {-1, 0, 0, 0, 0, 0, 0, 0}
  • recuento de desalineación final = 7: siete elems finales. máscara = {-1,-1,-1,-1,-1,-1,-1, 0}

Código no probado, suponga que hay errores

 section .data align 32 ; preferably no cache-line boundaries inside the table ; byte elements, to be loaded with pmovsx. all-ones sign-extends DB 0, 0, 0, 0, 0, 0, 0, 0 masktable_intro: ; index with 0..-7 DB -1, -1, -1, -1, -1, -1, -1, -1 masktable_outro: ; index with -8(aligned), or -1..-7 DB 0, 0, 0, 0, 0, 0, 0, 0 ; the very first and last 0 bytes are not needed, since we avoid an all-zero mask. section .text global floatmul ; (float *rdi) floatmul: mov eax, edi and eax, 0x1c ; 0x1c = 7 << 2 = 0b11100 lea rdx, [rdi + 4096 - 32] ; one full vector less than the end address (calculated *before* masking for alignment). ;; replace 4096 with rsi*4 if rsi has the count (in floats, not bytes) and rdi, ~0x1c ; Leave the low 2 bits alone, so this still works on misaligned floats. shr eax, 2 ; misalignment-count, in the range [0..7] neg rax vpmovsxbd ymm0, [masktable_intro + rax] ; Won't link on OS X: Need a separate LEA for RIP-relative vmaskmovps ymm1, ymm0, [rdi] vaddps ymm1, ymm1, ymm1 ; *= 2.0 vmaskmovps [rdi], ymm0, ymm1 ;;; also prepare the cleanup mask while the table is still hot in L1 cache ; if the loop count known to be a multiple of the vector width, ; the alignment of the end will be the same as the alignment of the start ; so we could just invert the mask ; vpxor xmm1, xmm1, xmm1 ; doesn't need an execution unit ; vpcmpeqd ymm0, ymm1, ymm0 ; In the more general case: just re-generate the mask from the one-past-the-end addr mov eax, edx xor ecx, ecx ; prep for setcc and eax, 0x1c ; sets ZF when aligned setz cl ; rcx=1 in the aligned special-case, else 0 shr eax, 2 lea eax, [rax + rcx*8] ; 1..7, or 8 in the aligned case neg rax vpmovsxbd ymm0, [masktable_outro + rax] .loop: add rdi, 32 vmovups ymm1, [rdi] ; Or vmovaps if you want to fault if the address isn't 4B-aligned vaddps ymm1, ymm1, ymm1 ; *= 2.0 vmovups [rdi], ymm1 cmp rdi, rdx ; while( (p+=8) < (start+1024-8) ) jb .loop ; 5 fused-domain uops, yuck. ; use the outro mask that we generated before the loop for insn scheduling / cache locality reasons. vmaskmov ymm1, ymm0, [rdi] vaddps ymm1, ymm1, ymm1 ; *= 2.0 vmaskmovps [rdi], ymm0, ymm1 ret ; vpcmpeqd ymm1, ymm1, ymm1 ; worse way to invert the mask: dep-chain breaker but still needs an execution unit to make all-ones instead of all-zeros. ; vpxor ymm0, ymm0, ymm1 

Esto requiere una carga de una tabla, que puede fallar en la caché L1, y 15B de datos de la tabla. (O 24B si el conteo del ciclo también es variable, y tenemos que generar la máscara final por separado).

De cualquier manera, después de las 4 instrucciones para generar el recuento de desalineación y la dirección de inicio alineada, obtener la máscara solo requiere una sola instrucción vpmosvsxbd. (El ymm, la forma mem no puede microfusionarse, entonces son 2 uops). Esto requiere AVX2.


Sin AVX2:

  • 2x vpmovsxbd en dos registros 128b ( [masktable_intro + rax] y [masktable_intro + rax + 4] )
  • vinsertf128

O bien: (más insns, y más presión de puerto aleatorio, pero menos presión de puerto de carga)

  • vpmovsxbw en un registro 128b
  • vpunpcklwd / vpunpckhwd en dos regs xmm (src1 = src2 para ambos)
  • vinsertf128

O:

  • vmovdqu de una tabla 60B de DWORD ( DD ) en lugar de Bytes ( DB ). Esto realmente ahorraría una entrada relativa a AVX2: address & 0x1c es el índice, sin necesidad de un desplazamiento a la derecha por dos. Toda la tabla todavía cabe en una línea de caché, pero sin espacio para otras constantes que el algoritmo pueda usar.

Gastos generales:

  • Operaciones enteras: 5 uops al inicio para obtener un índice y alinear el puntero de inicio. 7 uops para obtener el índice de la máscara final. Total de 12 GP de registro de GPU más allá de simplemente usar sin alinear, si el recuento de elementos de ciclo es un múltiplo del ancho del vector.

  • AVX2: Dos insns vectoriales de 2 dominios fusionados para pasar del índice [0..7] en un registro GP a una máscara en un registro YMM. (Uno para la máscara de inicio, otro para la máscara final). Utiliza una tabla de 24B, a la que se accede en una ventana de 8B con granularidad de bytes.

  • AVX: Seis insns vectoriales de 1 dominio fusionado-uop (tres al principio, tres al final). Con el direccionamiento relativo de RIP para la tabla, cuatro de esas instrucciones serán [base+index] y no micro fusibles, por lo que un par adicional de dos enteros podría ser mejor.

El código dentro del ciclo se replica 3 veces.


TODO: escriba otra respuesta generando la máscara sobre la marcha, tal vez como bytes en un reg 64b, luego desempaquetarlo en 256b. ¿Tal vez con un cambio de bit, o BZHI de BMI2 (-1, recuento)?

AVX-only: accesos desalineados al inicio / finalización, encadenando cargas para evitar problemas al reescribir en su lugar.

Gracias a @StephenCanon por señalar que esto es mejor que VMASKMOVPS para cualquier cosa que VMASKMOVPS pueda hacer para ayudar con el bucle sobre búferes no alineados.

Esto es quizás demasiado esperar que un comstackdor lo haga como una transformación de bucle, esp. ya que la forma obvia puede hacer que Valgrind se sienta infeliz (ver más abajo).

 section .text global floatmul ; (float *rdi) floatmul: lea rdx, [rdi + 4096 - 32] ; one full vector less than the end address (calculated *before* masking for alignment). ;; replace 4096 with rsi*4 if rsi has the count (in floats, not bytes) vmovups ymm0, [rdi] vaddps ymm0, ymm0, ymm0 ; *= 2.0 ; don't store yet lea rax, [rdi+32] and rax, ~0x1c ; 0x1c = 7 << 2 = 0b11100 vmovups ymm1, [rax] ; first aligned vector, for use by first loop iteration vmovups [rdi], ymm0 ; store the first unaligned vector vmovups ymm0, [rdx] ; load the *last* unaligned vector .loop: ;; on entry: [rax] is already loaded into ymm1 vaddps ymm1, ymm1, ymm1 ; *= 2.0 vmovups [rax] ; vmovaps would fault if p%4 != 0 add rax, 32 vmovups ymm1, [rax] cmp rax, rdx ; while( (p+=8) < (endp-8) ); jb .loop ; discard ymm1. It includes data from beyond the end of the array (aligned case: same as ymm0) vaddss ymm0, ymm0, ymm0 ; the last 32B, which we loaded before the loop vmovups [rdx], ymm0 ret ; End alignment: ; a[] = XXXX XXXX ABCD E___ _ = garbage past the end ; ^rdx ; ^rax ^rax ^rax ^rax(loop exit) ; ymm0 = BCDE ; ymm1 loops over ..., XXXX, ABCD, E___ ; The last load off the end of the array includes garbage ; because we pipeline the load for the next iteration 

Hacer una carga desde el final de la matriz al comienzo del ciclo parece un poco extraño, pero con suerte no confunde a los buscadores anticipados de hardware o ralentiza el inicio de la transferencia de la matriz desde la memoria.

Gastos generales:

  • 2 enteros extra enteros totales (para configurar el inicio alineado). Ya estamos usando el puntero final para la estructura de bucle normal, entonces eso es gratis.

  • 2 copias adicionales del cuerpo del bucle (cargar / calc / almacenar). (Primera y última iteración peladas).


Es probable que los comstackdores no estén contentos de emitir un código como este cuando se auto-vectorizan. Valgrind informará los accesos fuera de los límites de la matriz , y lo hará mediante instrucciones de paso único y deencoding para ver a qué están accediendo. Por lo tanto, simplemente permanecer dentro de la misma página (y la línea de caché) como el último elemento de la matriz no es suficiente. También tenga en cuenta que si el puntero de entrada no está alineado con 4B, podemos leer potencialmente en otra página y segfault.

Para mantener feliz a Valgrind, podríamos detener el bucle dos anchos de vector antes, para hacer la carga de caso especial del último ancho de vector sin alinear de la matriz. Eso requeriría duplicar el cuerpo del bucle en un tiempo extra (insignificante en este ejemplo, pero es trivial a propósito). O tal vez evitar el pipeline haciendo que el código de introducción salte al centro del bucle. (Sin embargo, eso puede ser subóptimo para el uop-cache: (partes del) cuerpo del bucle pueden terminar en la memoria caché uop dos veces).

TODO: escriba una versión que salte al ciclo a mitad de camino.