Producir bucles sin instrucción cmp en GCC

11 minutos de lectura

Producir bucles sin instruccion cmp en GCC
bosón z

Tengo una serie de bucles estrechos que intento optimizar con GCC e intrínsecos. Considere por ejemplo la siguiente función.

void triad(float *x, float *y, float *z, const int n) {
    float k = 3.14159f;
    int i;
    __m256 k4 = _mm256_set1_ps(k);
    for(i=0; i<n; i+=8) {
        _mm256_store_ps(&z[i], _mm256_add_ps(_mm256_load_ps(&x[i]), _mm256_mul_ps(k4, _mm256_load_ps(&y[i]))));
    }
}

Esto produce un bucle principal como este

20: vmulps ymm0,ymm1,[rsi+rax*1]
25: vaddps ymm0,ymm0,[rdi+rax*1]
2a: vmovaps [rdx+rax*1],ymm0
2f: add    rax,0x20
33: cmp    rax,rcx
36: jne    20 

Pero el cmp la instrucción es innecesaria. En vez de tener rax comienza en cero y termina en sizeof(float)*n podemos establecer los punteros base (rsi, rdiy rdx) hasta el final de la matriz y establecer rax para -sizeof(float)*n y luego probar para cero. Puedo hacer esto con mi propio código ensamblador como este

.L2  vmulps          ymm1, ymm2, [rdi+rax]
     vaddps          ymm0, ymm1, [rsi+rax]
     vmovaps         [rdx+rax], ymm0
     add             rax, 32
     jne             .L2

pero no puedo lograr que GCC haga esto. Tengo varias pruebas ahora donde esto hace una diferencia significativa. Hasta hace poco, GCC y los intrínsecos me han separado bien, así que me pregunto si hay un cambio de compilador o una forma de reordenar/cambiar mi código para que el cmp la instrucción no se produce con GCC.

Intenté lo siguiente pero todavía produce cmp. Todas las variaciones que he probado todavía producen cmp.

void triad2(float *x, float *y, float *z, const int n) {
    float k = 3.14159f;
    float *x2 = x+n;
    float *y2 = y+n;
    float *z2 = z+n;    
    int i;
    __m256 k4 = _mm256_set1_ps(k);
    for(i=-n; i<0; i+=8) {
        _mm256_store_ps(&z2[i], _mm256_add_ps(_mm256_load_ps(&x2[i]), _mm256_mul_ps(k4, _mm256_load_ps(&y2[i]))));
    }
}

Editar: estoy interesado en maximizar el paralelismo de nivel de instrucción (ILP) para estas funciones para matrices que caben en el caché L1 (en realidad para n=2048). Aunque el desenrollado se puede utilizar para mejorar el ancho de banda, puede disminuir el ILP (suponiendo que se pueda alcanzar el ancho de banda completo sin desenrollar).

Editar: aquí hay una tabla de resultados para un sistema Core2 (antes de Nehalem), un IvyBridge y un sistema Haswell. Intrínsecos son los resultados del uso de intrínsecos, unroll1 es mi código ensamblador que no usa cmp, y unroll16 es mi código ensamblador que se desenrolla 16 veces. Los porcentajes son el porcentaje del rendimiento máximo (frequency*num_bytes_cycle donde num_bytes_cycle es 24 para SSE, 48 para AVX y 96 para FMA).

                 SSE         AVX         FMA
intrinsic      71.3%       90.9%       53.6%      
unroll1        97.0%       96.1%       63.5%
unroll16       98.6%       90.4%       93.6%
ScottD         96.5%
32B code align             95.5%

Para SSE obtengo un resultado casi tan bueno sin desenrollar como con desenrollar, pero solo si no uso cmp. En AVX obtengo el mejor resultado sin desenrollar y sin usar cmp. Es interesante que en IB el desenrollado sea peor. En Haswell obtengo, con mucho, el mejor resultado al desenrollar. Por eso hice esta pregunta. El código fuente para probar esto se puede encontrar en esa pregunta.

Editar:

Según la respuesta de ScottD, ahora obtengo casi el 97 % con intrínsecos para mi sistema Core2 (modo anterior a Nehalem de 64 bits). No estoy seguro de por qué el cmp importa en realidad ya que debería tomar 2 ciclos de reloj por iteración de todos modos. Para Sandy Bridge, resulta que la pérdida de eficiencia se debe a la alineación del código, no al extra cmp. De todos modos, en Haswell solo funciona el desenrollado.

  • Algo me dice que probablemente deberías estar desenrollando el bucle más de lo que estás ahora.

    – Místico

    18/09/2014 a las 20:24

  • @Zboson: ah, sí, ahora lo veo. no tengo idea de como decir gcc para evitar el cmp. Clang reemplazó el cmp en el segundo con un tst, pero eso no es de mucha ayuda. (¿No debería ser la condición de terminación i < 0?)

    – rico

    18/09/2014 a las 21:32

  • ¿Has comprobado el rendimiento? Dudo que puedas detectar la diferencia entre las dos versiones ya que el número de accesos a datos es el mismo. El acceso a la memoria es casi siempre el cuello de botella del rendimiento, a menos que tenga un caso de uso muy especializado.

    – Dwayne Towell

    18/09/2014 a las 22:04

  • Para ser claros, comparé el rendimiento de la primera versión de GCC con la versión que escribí en ensamblador (con NASM).

    – bosón Z

    19 de septiembre de 2014 a las 8:34


  • Solo un aviso, encontré una manera de hacerlo de manera óptima en gcc sin elementos intrínsecos (solo elementos integrados, que es obviamente mejor, ¿no?).

    – FEO

    23 de septiembre de 2014 a las 14:12

Qué tal esto. El compilador es gcc 4.9.0 mingw x64:

void triad(float *x, float *y, float *z, const int n) {
    float k = 3.14159f;
    intptr_t i;
    __m256 k4 = _mm256_set1_ps(k);

    for(i = -n; i < 0; i += 8) {
        _mm256_store_ps(&z[i+n], _mm256_add_ps(_mm256_load_ps(&x[i+n]), _mm256_mul_ps(k4, _mm256_load_ps(&y[i+n]))));
    }
}

gcc -c -O3 -march=corei7 -mavx2 tríada.c

0000000000000000 <triad>:
   0:   44 89 c8                mov    eax,r9d
   3:   f7 d8                   neg    eax
   5:   48 98                   cdqe
   7:   48 85 c0                test   rax,rax
   a:   79 31                   jns    3d <triad+0x3d>
   c:   c5 fc 28 0d 00 00 00 00 vmovaps ymm1,YMMWORD PTR [rip+0x0]
  14:   4d 63 c9                movsxd r9,r9d
  17:   49 c1 e1 02             shl    r9,0x2
  1b:   4c 01 ca                add    rdx,r9
  1e:   4c 01 c9                add    rcx,r9
  21:   4d 01 c8                add    r8,r9

  24:   c5 f4 59 04 82          vmulps ymm0,ymm1,YMMWORD PTR [rdx+rax*4]
  29:   c5 fc 58 04 81          vaddps ymm0,ymm0,YMMWORD PTR [rcx+rax*4]
  2e:   c4 c1 7c 29 04 80       vmovaps YMMWORD PTR [r8+rax*4],ymm0
  34:   48 83 c0 08             add    rax,0x8
  38:   78 ea                   js     24 <triad+0x24>

  3a:   c5 f8 77                vzeroupper
  3d:   c3                      ret

Al igual que su código escrito a mano, gcc usa 5 instrucciones para el bucle. El código gcc usa scale=4 donde el tuyo usa scale=1. Pude hacer que gcc usara scale=1 con un ciclo de 5 instrucciones, pero el código C es incómodo y 2 de las instrucciones AVX en el ciclo crecen de 5 bytes a 6 bytes.

  • ¡Lo hiciste! Eso produce un código casi idéntico al de mi ensamblaje.

    – bosón Z

    22 de septiembre de 2014 a las 7:09

  • Ahora solo necesito descubrir cómo hacer que GCC alinee mi código y luego no necesitaré ensamblaje para esto.

    – bosón Z

    22 de septiembre de 2014 a las 8:53

  • creo que debería intentarlo -falign-loops=32.

    – bosón Z

    22 de septiembre de 2014 a las 9:04

  • Hmm… la alineación aún no funciona. Bueno, de todos modos, ese es otro problema. ¡Gracias por arreglar esto!

    – bosón Z

    22 de septiembre de 2014 a las 9:16

  • Tengo la alineación funcionando usando -falign-labels=32. Ahora, la versión intrínseca y mi ensamblaje están dentro del 0,5 % uno del otro en aproximadamente el 95,5 % del pico.

    – bosón Z

    22 de septiembre de 2014 a las 9:32

El decodificador de instrucciones en Intel Ivy Bridge o posterior puede fusionar cmp y jne en una sola operación en la canalización (llamada fusión macro-op), por lo que en estos procesadores recientes el cmp debería desaparecer de todos modos.

  • Sí, pero no pueden fusionar el add, cmpy jne instrucción en “una sola operación”. ¡Ese es todo el punto! Antes de SB no era posible fusionar add y jne. Pero desde SB lo es. Utilizando cmp requiere un μop más.

    – bosón Z

    19/09/2014 a las 10:51


  • Y para ser más precisos, todos los procesadores Core2 pueden fusionarse cmp y jne en modo de 32 bits. Y todos los procesadores desde Nehalem pueden fusionarlos en modo de 64 bits. Y todos ellos desde Sandy Bridge pueden fusionarse add y jne. Sin embargo, hay varios casos que pueden causar que la fusión falle.

    – bosón Z

    19/09/2014 a las 11:00

Producir bucles sin instruccion cmp en GCC
fin de semana

Código definitivo:

#define SF sizeof(float)
#ifndef NO                   //floats per vector, compile with -DNO = 1,2,4,8,...
#define NO 8                 //MUST be power of two
#endif

void triadfinaler(float const *restrict x, float const *restrict y,   \
                  float *restrict z, size_t n)
{
  float *restrict d = __builtin_assume_aligned(z, NO*SF);       //gcc builtin,
  float const *restrict m = __builtin_assume_aligned(y, NO*SF); //optional but produces
  float const *restrict a = __builtin_assume_aligned(x, NO*SF); //better code
  float const k = 3.14159f;
  n*=SF;
  while (n &= ~((size_t)(NO*SF)-1))    //this is why NO*SF must be power of two
    {
      size_t nl = n/SF;
      for (size_t i = 0; i<NO; i++)
        {
          d[nl-NO+i] = k * m[nl-NO+i] + a[nl-NO+i];
        }
      n -= (NO*SF);
    }
}

Prefiero dejar que el compilador elija las instrucciones, en lugar de usar intrínsecos (sobre todo porque usó intel-intrinsics, que a gcc realmente no le gusta). De todos modos, el siguiente código produce un buen ensamblaje para mí en gcc 4.8:

void triad(float *restrict x, float *restrict y, float *restrict z, size_t n)
//I hope you weren't aliasing any function arguments... Oh, an it's void, not float
{
  float *restrict d = __builtin_assume_aligned(z, 32);  // Uh, make sure your arrays
  float *restrict m = __builtin_assume_aligned(y, 32);  // are aligned? Faster that way
  float *restrict a = __builtin_assume_aligned(x, 32);  //
  float const k = 3.14159f;
  while (n &= ~((size_t)0x7))       //black magic, causes gcc to omit code for non-multiples of 8 floats
    {
      n -= 8;                       //You were always computing on 8 floats at a time, right?
      d[n+0] = k * m[n+0] + a[n+0]; //manual unrolling
      d[n+1] = k * m[n+1] + a[n+1];
      d[n+2] = k * m[n+2] + a[n+2];
      d[n+3] = k * m[n+3] + a[n+3];
      d[n+4] = k * m[n+4] + a[n+4];
      d[n+5] = k * m[n+5] + a[n+5];
      d[n+6] = k * m[n+6] + a[n+6];
      d[n+7] = k * m[n+7] + a[n+7];
    }
}

Esto produce un buen código para mi corei7avx2, con -O3:

triad:
    andq    $-8, %rcx
    je  .L8
    vmovaps .LC0(%rip), %ymm1

.L4:
    subq    $8, %rcx
    vmovaps (%rsi,%rcx,4), %ymm0
    vfmadd213ps (%rdi,%rcx,4), %ymm1, %ymm0
    vmovaps %ymm0, (%rdx,%rcx,4)
    andq    $-8, %rcx
    jne .L4
    vzeroupper
.L8:
    rep ret
    .cfi_endproc

.LC0:
    .long   1078530000
    .long   1078530000
    .long   1078530000
    .long   1078530000
    .long   1078530000
    .long   1078530000
    .long   1078530000
    .long   1078530000

Editar: Me decepcionó un poco que el compilador no optimizara este código hasta la última instrucción, así que me metí un poco más en él. Simplemente cambiando el orden de las cosas en el ciclo se deshizo del AND emitido por el compilador, que me puso en el camino correcto. Entonces solo tenía que hacer que no hiciera cálculos innecesarios de direcciones en el bucle. Suspiro.

void triadtwo(float *restrict x, float *restrict y, float *restrict z, size_t n)
{
  float *restrict d = __builtin_assume_aligned(z, 32);
  float *restrict m = __builtin_assume_aligned(y, 32);
  float *restrict a = __builtin_assume_aligned(x, 32);
  float const k = 3.14159f;
  n<<=2;
  while (n &= -32)
    {
      d[(n>>2)-8] = k * m[(n>>2)-8] + a[(n>>2)-8];
      d[(n>>2)-7] = k * m[(n>>2)-7] + a[(n>>2)-7];
      d[(n>>2)-6] = k * m[(n>>2)-6] + a[(n>>2)-6];
      d[(n>>2)-5] = k * m[(n>>2)-5] + a[(n>>2)-5];
      d[(n>>2)-4] = k * m[(n>>2)-4] + a[(n>>2)-4];
      d[(n>>2)-3] = k * m[(n>>2)-3] + a[(n>>2)-3];
      d[(n>>2)-2] = k * m[(n>>2)-2] + a[(n>>2)-2];
      d[(n>>2)-1] = k * m[(n>>2)-1] + a[(n>>2)-1];
      n -= 32;
    }
}

¿Código feo? Si. Pero la Asamblea:

triadtwo:
    salq    $2, %rcx
    andq    $-32, %rcx
    je  .L54
    vmovaps .LC0(%rip), %ymm1

.L50:
    vmovaps -32(%rsi,%rcx), %ymm0
    vfmadd213ps -32(%rdi,%rcx), %ymm1, %ymm0
    vmovaps %ymm0, -32(%rdx,%rcx)
    subq    $32, %rcx
    jne .L50
    vzeroupper
.L54:
    rep ret
    .cfi_endproc
.LC0:
    .long   1078530000
    .long   1078530000
    .long   1078530000
    .long   1078530000
    .long   1078530000
    .long   1078530000
    .long   1078530000
    .long   1078530000

Mmmmmhhhgloriosas cinco instrucciones en el bucle, resta y ramificación fusibles macro-op…

  • Ese es un enfoque interesante (+1). Lograste deshacerte de cmp reemplazándolo con and. Pero no creo que eso sea mejor.

    – bosón Z

    20 de septiembre de 2014 a las 14:57


  • @Zboson: Sí, el AND no debería ser necesario, pero gcc no entiende que cuando (n%8 == 0) también se sigue que ((n-8)%8 == 0). No me preguntes por qué. n &= -8 funciona, y macro-op fusion debería hacerlo prácticamente gratis.

    – FEO

    20/09/2014 a las 19:45


  • Buena llamada en el regreso. Sí, debe ser nulo en lugar de flotante. Es una resaca de algunas pruebas de reducción que volvían a flotar. Eso me pasa por no usar -Wall. Lo intenté n &-8 y todavía produce el and. Macro-op fusion funcionaría en and y jump (pero no en los procesadores pre SB) pero no en el sub. Reduce los micros de 3 a 2. Pero sin el cmp o and son solo 2 de todos modos.

    – bosón Z

    21 de septiembre de 2014 a las 7:48


  • En cuanto a restrict no es necesario cuando se usan intrínsecos. Cualquiera de las dos es la especificidad de la alineación. Por eso no usé ninguno. Si observa mi código intrínseco, puede ver que ya asume que las matrices no se superponen y que las matrices están alineadas. Sin embargo, es necesario especificar restrict y alineación cuando no se usan intrínsecos.

    – bosón Z

    21 de septiembre de 2014 a las 7:50


  • Impresionante que hayas conseguido que esto funcione sin elementos intrínsecos. Si fuera posible tener dos respuestas aceptadas, este sería un candidato perfecto para ello.

    – bosón Z

    23 de septiembre de 2014 a las 14:23

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad