gcc - Vectorización con buffers no alineados: usando VMASKMOVPS: ¿generando una máscara a partir de un recuento de desalineación? O no usar esa información en absoluto

assembly x86

Question

gcc 5.3 con -O3 -mavx -mtune=haswell para x86-64 -O3 -mavx -mtune=haswell 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 utiliza instrucciones de carga / almacenamiento no alineadas, pero gcc realiza una introducción / salida escalar y un bucle de vector alineado: despega las primeras iteraciones no alineadas de hasta 7, desenrollando completamente 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, especialmente. para CPU con un caché uop. Informé un error de gcc sobre esto, con una sugerencia para un código más pequeño / mejor que gcc podría usar al pelar iteraciones no alineadas. Sin embargo, probablemente todavía no sea óptimo.

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

Probablemente habrá múltiples respuestas, ya que lo que es óptimo para -mtune=haswell probablemente será diferente de lo que es óptimo para -mtune=bdver3 (apisonadora). Y luego está la cuestión de qué es óptimo cuando se permiten extensiones de conjunto 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 de optimización de ensamblaje de Agner Fog, Sección 13.5 Acceso a datos no alineados y vectores parciales . Sugiere usar accesos no alineados, hacer una escritura superpuesta al inicio y / o finalizar, o barajar datos de accesos alineados (pero PALIGNR solo toma un recuento imm8, entonces 2x pshufb / por ). Él descarta VMASKMOVPS como no útil, probablemente debido a lo mal que funciona en AMD. Sospecho que si está sintonizando 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 lo hace el ruido metálico. Para buffers cortos, la sobrecarga de la alineación podría matar cualquier beneficio al evitar divisiones de línea de caché para el bucle principal. Para grandes buffers, memoria principal o L3 como el cuello de botella puede ocultar la penalización por divisiones de la línea de caché. Si alguien tiene datos experimentales para respaldar esto para cualquier código real que haya ajustado, también es información útil.

VMASKMOVPS parece utilizable para objetivos de Intel. (La versión SSE es horrible, con una indirecta no temporal implícita, pero la versión AVX no tiene eso. Incluso hay una nueva intrínseca para asegurarse de que no obtienes la versión SSE para operandos de 128b: _mm128_maskstore_ps ) La versión AVX es un poco lento para 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 de 256b.
• 4 uops / 13c de latencia / 1 por 1c de rendimiento como una tienda de 128b.

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

Pero si queremos usar VMASKMOVPS , necesitamos un vector con el bit alto establecido en cada elemento que realmente debería cargarse / almacenarse. PALIGNR y PSRLDQ (para usar en un vector de todos) solo toman conteos constantes de tiempo de compilación.

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

Answer 1

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 Stephen Canon señala en los comentarios sobre el OP, las cargas de canalización pueden permitir que las tiendas no alineadas 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 no alineada 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 bytes en los datos en la memoria.

Máscaras en orden de primer byte LSB (ya que están almacenadas en la memoria), no la notación habitual para 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 recuento de desalineación = 0: máscara = todos-unos (caso alineado)
• iniciar el recuento de desalineación = 1: máscara = {0,-1,-1,-1,-1,-1,-1,-1} (omita uno en el primer 32B)
• ...

• iniciar el recuento de desalineación = 7: máscara = {0, 0, 0, 0, 0, 0, 0,-1} (omita todos menos uno en el primer 32B)

• recuento de desalineación final = 0: sin elementos finales. máscara = todos-unos (caso alineado).
  Este es el caso extraño, no similar a contar = 1 . Vale la pena evitar un par de instrucciones adicionales para este caso especial, una iteración de bucle adicional y una limpieza con una máscara de todos ceros.

• final cuenta de desalineación = 1: un elemento final. máscara = {-1, 0, 0, 0, 0, 0, 0, 0}
• ...
• cuenta de desalineación final = 7: siete elementos 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 faltar en la caché L1, y 15B de datos de la tabla. (O 24B si el recuento de bucles 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. (La forma ymm, mem no puede fusionarse, entonces son 2 uops). Esto requiere AVX2.

Sin AVX2:

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

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

• vpmovsxbw en un registro de 128b
• vpunpcklwd / vpunpckhwd en dos registros 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 información 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 podría 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. Un total de 12 Uops de registro GP más allá simplemente usando sin alinear, si el recuento de elementos de bucle es un múltiplo del ancho del vector.

• AVX2: dos insns de vector de uop de dominio fusionado 2 para pasar del índice [0..7] en un registro GP a una máscara en un registro YMM. (Uno para la máscara inicial, uno para la máscara final). Utiliza una tabla 24B, a la que se accede en una ventana 8B con granularidad de bytes.

• AVX: Seis insns de vector 1-fused-domain-uop (tres al principio, tres al final). Con el direccionamiento relativo a RIP para la tabla, cuatro de esas instrucciones serán [base+index] y no se fusionarán, por lo que podrían ser mejores dos números enteros adicionales.

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

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

Answer 2

Solo AVX: accesos no alineados al inicio / final, canalizando 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 a VMASKMOVPS buffers no alineados.

Esto es quizás demasiado esperar que un compilador haga una transformación de bucle, especialmente. ya que la forma obvia puede hacer que Valgrind sea 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 bucle parece un poco extraño, pero es de esperar que no confunda a los prefetchers de hardware o ralentice el inicio de la transmisión de la matriz desde la memoria.

Gastos generales:

• 2 números enteros adicionales en total (para configurar el inicio alineado). Ya estamos usando el puntero final para la estructura de bucle normal, por lo que es gratis.

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

Los compiladores probablemente no estarán contentos con la emisión de código como este, cuando se auto vectorice. Valgrind informará los accesos fuera de los límites de la matriz , y lo hace mediante un solo paso y decodificando las instrucciones para ver a qué están accediendo. Por lo tanto, simplemente permanecer dentro de la misma página (y línea de caché) que 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, potencialmente podemos leer 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 casos especiales del último ancho de vector no alineado de la matriz. Eso requeriría duplicar el cuerpo del bucle un tiempo extra (insignificante en este ejemplo, pero es trivial a propósito). O tal vez evite la canalización haciendo que el código de introducción salte a la mitad del bucle. (Sin embargo, eso puede ser subóptimo para el caché uop: (partes del) cuerpo del bucle puede terminar en el caché uop dos veces).

TODO: escribe una versión que salte al bucle a mitad de camino.