optimizacion - Ayuda de optimización de bucle C para la asignación final(con la optimización del compilador deshabilitada)

optimizacion del codigo modularidad

Question

Entonces, para mi tarea final en mi clase de Sistemas informáticos, necesitamos optimizarlos para que los bucles sean más rápidos que el original.

La calificación básica es inferior a 7 segundos y la calificación completa es inferior a 5 segundos con nuestro servidor Linux. Este código que tengo aquí tiene aproximadamente 5,6 segundos. Estoy pensando que es posible que necesite usar punteros con esto de alguna manera para que funcione más rápido, pero no estoy realmente seguro. ¿Alguien podría ofrecer algún consejo u opciones que tengo?

El archivo debe permanecer 50 líneas o menos y estoy ignorando esas líneas comentadas que el instructor ha incluido.

#include <stdio.h>
#include <stdlib.h>

// You are only allowed to make changes to this code as specified by the comments in it.

// The code you submit must have these two values.
#define N_TIMES     600000
#define ARRAY_SIZE   10000

int main(void)
{
    double  *array = calloc(ARRAY_SIZE, sizeof(double));
    double  sum = 0;
    int     i;

    // You can add variables between this comment ...
    register double sum1 = 0, sum2 = 0, sum3 = 0, sum4 = 0, sum5 = 0, sum6 = 0, sum7 = 0, sum8 = 0, sum9 = 0;
    register int j;
    // ... and this one.

    printf("CS201 - Asgmt 4 - /n");

    for (i = 0; i < N_TIMES; i++)
    {
        // You can change anything between this comment ...
        for (j = 0; j < ARRAY_SIZE; j += 10)
        {
            sum += array[j];
            sum1 += array[j + 1];
            sum2 += array[j + 2];
            sum3 += array[j + 3];
            sum4 += array[j + 4];
            sum5 += array[j + 5];
            sum6 += array[j + 6];
            sum7 += array[j + 7];
            sum8 += array[j + 8];
            sum9 += array[j + 9];
        }
        // ... and this one. But your inner loop must do the same
        // number of additions as this one does.
    }                   

    // You can add some final code between this comment ...
    sum += sum1 + sum2 + sum3 + sum4 + sum5 + sum6 + sum7 + sum8 + sum9;
    // ... and this one.

    return 0;
}

Answer 1

Antes que nada, intente cambiar la configuración del compilador para producir un código más rápido. Existe una optimización general, y el compilador podría hacer una vectorización automática.

Lo que siempre haría es probar varios enfoques y verificar cuál es el más rápido. Como objetivo, trate de llegar a un ciclo por adición o mejor.

Número de iteraciones por ciclo: sumas 10 sumas simultáneamente. Puede ser que su procesador no tenga suficientes registros para eso, o que tenga más. Mediría el tiempo para 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 ... sumas por ciclo.

Número de sumas: Tener más de una suma significa que la latencia no te muerde, solo el rendimiento. Pero más de cuatro o seis podrían no ser útiles. Pruebe cuatro sumas, con 4, 8, 12, 16 iteraciones por ciclo. O seis sumas, con 6, 12, 18 iteraciones.

Almacenamiento en caché: está ejecutando una matriz de 80,000 bytes. Probablemente más que el caché L1. Divida la matriz en 2 o 4 partes. Haga un bucle externo iterando sobre las dos o cuatro submatrices, el siguiente bucle de 0 a N_TIMES - 1 y el bucle interno sumando valores.

Y luego puede intentar usar operaciones vectoriales, o multiprocesar su código, o usar la GPU para hacer el trabajo.

Y si se ve obligado a utilizar ninguna optimización, entonces la palabra clave "registrarse" podría funcionar.

Answer 2

Puede que esté en el camino correcto, aunque necesitará medirlo para estar seguro (mi consejo normal para medir, no adivinar, parece un poco superfluo aquí ya que el objetivo de la tarea es medir).

Los compiladores de optimización probablemente no verán una gran diferencia ya que son bastante inteligentes sobre ese tipo de cosas, pero, dado que no sabemos en qué nivel de optimización se compilará, puede obtener una mejora sustancial.

Usar punteros en el bucle interno es una simple cuestión de agregar primero una variable de puntero:

register double *pj;

luego cambiando el ciclo a:

for (pj = &(array[0]); pj < &(array[ARRAY_SIZE]); j++) {
        sum += *j++;
        sum1 += *j++;
        sum2 += *j++;
        sum3 += *j++;
        sum4 += *j++;
        sum5 += *j++;
        sum6 += *j++;
        sum7 += *j++;
        sum8 += *j++;
        sum9 += *j;
    }

Esto mantiene la cantidad de adiciones igual dentro del ciclo (suponiendo que esté contando += y ++ como operadores de suma, por supuesto) pero básicamente usa punteros en lugar de índices de matriz.

Sin la optimización ¹ en mi sistema, esto lo reduce de 9.868 segundos (tiempo de CPU) a 4.84 segundos. Su experiencia puede ser diferente.

¹ Con el nivel de optimización -O3 , se informa que ambos toman 0.001 segundos, por lo que, como se mencionó, los optimizadores son bastante inteligentes. Sin embargo, dado que está viendo más de 5 segundos, sugeriría que no se haya compilado con la optimización activada.

Por otro lado, esta es una buena razón por la que generalmente es aconsejable escribir su código de manera legible y dejar que el compilador se encargue de que funcione más rápido. Si bien mis escasos intentos de optimización duplicaron aproximadamente la velocidad, el uso de -O3 hizo que corriera unas diez mil veces más rápido :-)

Answer 3

Volver a publicar una versión modificada de mi respuesta a partir de la suma optimizada de una matriz de dobles en C , ya que esa pregunta se votó a -5. El OP de la otra pregunta lo expresó más como "qué más es posible", así que lo tomé en su palabra y lo volví de información sobre la vectorización y el ajuste para el hardware actual de la CPU. :)

El OP de esa pregunta finalmente dijo que no se le permitía usar opciones de compilación superiores a -O0 , lo que supongo que también es el caso aquí.

Resumen:

• Por qué usar -O0 distorsiona las cosas (penaliza injustamente las cosas que están bien en el código normal para un compilador normal). Usar -O0 (el valor predeterminado de gcc / clang) para que sus bucles no se optimicen no es una excusa válida o una forma útil de descubrir qué será más rápido con la optimización normal habilitada.

• Cosas que están mal con la tarea.

• Tipos de optimizaciones. Latencia FP vs. rendimiento y cadenas de dependencia. Enlace al sitio de Agner Fog. (Lectura esencial para la optimización).

• Experimentos que consiguen que el compilador lo optimice (después de arreglarlo para que no se optimice). El mejor resultado con auto-vectorización (sin cambios de fuente): gcc: la mitad de rápido que un ciclo vectorizado óptimo. Clang: misma velocidad que un bucle vectorizado a mano.

• Algunos comentarios más sobre por qué las expresiones más grandes son un triunfo solo con -O0 .

• La fuente cambia para obtener un buen rendimiento sin -ffast-math , acercando el código a lo que queremos que haga el compilador. También algunas ideas de reglas de abogacía que serían inútiles en el mundo real.

• Vectorizando el bucle con vectores de arquitectura neutral de GCC, para ver qué tan cerca estuvieron los compiladores de vectorización automática para igualar el rendimiento del código ASM ideal (ya que verifiqué la salida del compilador).

Creo que el objetivo de la tarea es enseñar las optimizaciones de rendimiento en lenguaje ensamblador utilizando C sin optimizaciones del compilador. Esto es tonto. Está mezclando cosas que el compilador hará por usted en la vida real con cosas que requieren cambios a nivel de fuente.

Vea ¿Por qué el sonido metálico produce asm ineficiente con -O0 (para esta simple suma de coma flotante)?

-O0 no solo "no optimiza", hace que el compilador almacene variables en la memoria después de cada declaración en lugar de mantenerlas en los registros. Hace esto para obtener los resultados "esperados" si establece un punto de interrupción con gdb y modifica el valor (en la memoria) de una variable C. O incluso si jump a otra línea en la misma función. Por lo tanto, cada instrucción C debe compilarse en un bloque independiente de asm que comienza y termina con todas las variables en la memoria. Para un compilador portátil moderno como gcc que ya se transforma a través de múltiples representaciones internas del flujo del programa en el camino desde el origen hasta el asm , esta parte de -O0 requiere des-optimizar explícitamente su gráfico del flujo de datos en declaraciones C separadas. Estas tiendas / recargas alargan cada cadena de dependencia transportada por bucle, por lo que es horrible para pequeños bucles si el contador de bucles se mantiene en la memoria. (por ejemplo, 1 ciclo por iteración para inc reg vs. 6c para inc [mem] , creando un cuello de botella en las actualizaciones de contador de bucles en bucles cerrados).

Con gcc -O0 , la palabra clave de register permite a gcc mantener una var en un registro en lugar de memoria, y por lo tanto puede hacer una gran diferencia en los bucles cerrados ( Ejemplo en el explorador del compilador Godbolt ). Pero eso es solo con -O0 . En el código real, el register tiene sentido: el compilador intenta utilizar de manera óptima los registros disponibles para variables y temporales. register ya está en desuso en ISO C ++ 11 (pero no en C11), y hay una propuesta para eliminarlo del lenguaje junto con otras cosas obsoletas como los trigrafos.

Con variables adicionales involucradas, -O0 daña la matriz de indexación un poco más que el incremento de puntero.

La indexación de matrices generalmente hace que el código sea más fácil de leer. Los compiladores a veces no pueden optimizar cosas como la array[i*width + j*width*height] , por lo que es una buena idea cambiar la fuente para hacer la optimización de reducción de fuerza de convertir las multiplicaciones en += adiciones.

A nivel asm, la indexación de matriz frente al incremento del puntero se asemejan al mismo rendimiento. (x86, por ejemplo, tiene modos de direccionamiento como [rsi + rdx*4] que son tan rápidos como [rdi] . excepto en Sandybridge y versiones posteriores ). Es el trabajo del compilador optimizar su código utilizando incrementos de puntero incluso cuando la fuente usa indexación de matriz. , cuando eso es más rápido.

Para un buen rendimiento, debe ser consciente de lo que los compiladores pueden y no pueden hacer. Algunas optimizaciones son "frágiles", y un pequeño cambio aparentemente inocente en la fuente evitará que el compilador realice una optimización que era esencial para que algún código se ejecute rápidamente. (p. ej., sacar un cálculo constante de un bucle o probar algo acerca de cómo se relacionan las diferentes condiciones de ramificación entre sí y simplificar).

Además de todo eso, es una muestra de porquería porque no tiene nada que impida que un compilador inteligente optimice todo. Ni siquiera imprime la suma. Incluso gcc -O1 (en lugar de -O3 ) gcc -O1 algunos de los bucles.

(Puede solucionar esto imprimiendo la sum al final. Gcc y clang no parecen darse cuenta de que calloc devuelve la memoria puesta a cero y la optimiza a 0.0 . Vea mi código a continuación).

Normalmente pondría su código en una función y lo llamaría en un bucle desde main() en otro archivo. Y compílelos por separado, sin la optimización de archivos cruzados de todo el programa, por lo que el compilador no puede hacer optimizaciones basadas en las constantes de tiempo de compilación con las que lo llama. El bucle de repetición que está tan apretado alrededor del bucle real sobre la matriz está causando estragos con el optimizador de gcc (ver más abajo).

Además, la otra versión de esta pregunta tenía una variable no inicializada dando vueltas. Parece que el OP de esa pregunta introdujo la long int help , no el prof. Así que tendré que rebajar mi "sinsentido absoluto" a simplemente "tonto", porque el código ni siquiera imprime el resultado al final. Esa es la forma más común de conseguir que el compilador no optimice todo en un microbenchmark como este.

Supongo que su profesor mencionó algunas cosas sobre el rendimiento. Hay un crapton de diferentes cosas que podrían entrar en juego aquí, muchas de las cuales supongo que no fueron mencionadas en una clase de CS de segundo año.

Además de multihilo con openmp, hay vectorización con SIMD. También hay optimizaciones para las CPU modernas canalizadas: específicamente, evite tener una larga cadena de dependencia.

Lectura esencial adicional:

• Las guías de Agner Fog para optimizar C y asm para x86. Parte de esto se aplica a todas las CPU.
• Lo que todo programador debe saber sobre la memoria

Su manual del compilador también es esencial, especialmente. para el código de coma flotante El punto flotante tiene una precisión limitada y no es asociativo. La suma final depende del orden en el que realice las adiciones. Por lo general, la diferencia en el error de redondeo es pequeña, por lo que el compilador puede obtener una gran aceleración al reordenar las cosas si usa -ffast-math para permitirlo.

En lugar de simplemente desenrollar, mantenga múltiples acumuladores que solo sume al final , como lo está haciendo con sum0 .. sum9 -by-10. Las instrucciones de FP tienen latencia media pero alto rendimiento, por lo que debe mantener múltiples operaciones de FP en vuelo para mantener saturadas las unidades de ejecución de coma flotante.

Si necesita que el resultado de la última operación se complete antes de que pueda comenzar la siguiente, está limitado por la latencia. Para FP add, eso es uno por cada 3 ciclos. En Intel Sandybridge, IvB, Haswell y Broadwell, el rendimiento de FP add es uno por ciclo. Por lo tanto, debe mantener al menos 3 operaciones independientes que pueden estar en vuelo a la vez para saturar la máquina. Para Skylake , son 2 por ciclo con latencia de 4 relojes . (En el lado positivo de Skylake, FMA tiene una latencia de 4 ciclos).

En este caso, también hay cosas básicas como sacar cosas del ciclo, por ejemplo, help += ARRAY_SIZE .

opciones del compilador

Comencemos por ver lo que el compilador puede hacer por nosotros.

Comencé con el bucle interno original, con solo help += ARRAY_SIZE extraído, y agregando un printf al final para que gcc no optimice todo. Probemos algunas opciones de compilación y veamos qué podemos lograr con gcc 4.9.2 (en mi i5 2500k Sandybridge . 3.8GHz max turbo (ligero OC), 3.3GHz sostenido (irrelevante para este breve punto de referencia)):

• gcc -O0 fast-loop-cs201.c -o fl : el rendimiento de 16.43s es una broma total. Las variables se almacenan en la memoria después de cada operación y se vuelven a cargar antes de la siguiente. Este es un cuello de botella y agrega mucha latencia. Sin mencionar perder las optimizaciones reales. El código de sincronización / ajuste con -O0 no es útil.
• -O1 : 4.87s
• -O2 : 4.89s
• -O3: 2.453s (usa SSE para hacer 2 a la vez. Por supuesto, estoy usando un sistema de 64 bits, por lo que el soporte de hardware para -msse2 es básico).
• -O3 -ffast-math -funroll-loops : 2.439s
• -O3 -march=sandybridge -ffast-math -funroll-loops : 1.275s (usa AVX para hacer 4 a la vez).
• -Ofast ... : sin ganancia
• -O3 -ftree-parallelize-loops=4 -march=sandybridge -ffast-math -funroll-loops : 0m2.375s real, 0m8.500s usuario. Parece que el bloqueo por encima lo mató. Solo genera los 4 hilos en total, pero el bucle interno es demasiado corto para que sea una ganancia: recoge las sumas cada vez, en lugar de dar a cada hilo 1/4 de las iteraciones del bucle externo.

• -Ofast -fprofile-generate -march=sandybridge -ffast-math , ejecútelo, luego
  -Ofast -fprofile-use -march=sandybridge -ffast-math : 1.275s . La optimización guiada por perfil es una buena idea cuando puede ejercer todas las rutas de código relevantes, de modo que el compilador pueda tomar mejores decisiones de desenrollado / en línea.

• clang-3.5 -Ofast -march=native -ffast-math : 1.070s . (clang 3.5 es demasiado antiguo para admitir -march=sandybridge . Debería preferir usar una versión del compilador que sea lo suficientemente nueva como para saber acerca de la arquitectura de destino para la que está ajustando, especialmente si usa -march para crear código que no necesita para ejecutarse en arquitecturas más antiguas).

gcc -O3 vectoriza de una manera hilarante: el bucle interno realiza 2 (o 4) iteraciones del bucle externo en paralelo, transmitiendo un elemento de matriz a todos los elementos de un registro xmm (o ymm) y haciendo un addpd sobre eso. Por lo tanto, ve que los mismos valores se agregan repetidamente, pero incluso -ffast-math no permite que gcc simplemente lo convierta en una multiplicación. O cambia los lazos.

clang-3.5 vectoriza mucho mejor: vectoriza el bucle interno, en lugar del externo, por lo que no necesita transmitir. Incluso utiliza 4 registros vectoriales como 4 acumuladores separados. Sin embargo, no supone que calloc devuelva memoria alineada, y por alguna razón cree que la mejor apuesta es un par de cargas de 128b.

vmovupd -0x60(%rbx,%rcx,8),%xmm4`
vinsertf128 $0x1,-0x50(%rbx,%rcx,8),%ymm4,%ymm4

En realidad, es más lento cuando le digo que la matriz está alineada. (con un truco estúpido como array = (double*)((ptrdiff_t)array & ~31); que en realidad genera una instrucción para enmascarar los 5 bits bajos, porque clang-3.5 no admite __builtin_assume_aligned de gcc.) Creo que el La forma en que el lazo cerrado de 4x vaddpd mem, %ymmX,%ymmX está alineado pone cmp $0x271c,%rcx cruzando un límite de 32B, por lo que no puede fusionarse con jne . Sin embargo, el rendimiento de uop no debería ser un problema, ya que este código solo obtiene 0.65insns por ciclo (y 0.93 uops / ciclo), según perf .

Ahh, verifiqué con un depurador, y calloc solo devuelve un puntero alineado con 16B. Entonces, la mitad de los accesos de memoria 32B están cruzando una línea de caché, causando una gran desaceleración. Es un poco más rápido hacer dos cargas de 16B separadas cuando su puntero está alineado con 16B pero no con 32B, en Sandybridge. (gcc habilita -mavx256-split-unaligned-load y ...-store para -march=sandybridge , y también para el ajuste predeterminado = genérico con -mavx , que no es tan bueno especialmente para Haswell o con memoria que generalmente está alineada por el compilador no lo sabe)

Cambios a nivel de fuente

Como podemos ver en el sonido de golpes de gcg, los acumuladores múltiples son excelentes. La forma más obvia de hacer esto sería:

for (j = 0; j < ARRAY_SIZE; j+=4) {  // unroll 4 times
    sum0 += array[j];
    sum1 += array[j+1];
    sum2 += array[j+2];
    sum3 += array[j+3];
}

y luego no junte los 4 acumuladores en uno hasta después del final del bucle externo.

Su cambio de origen (de la otra pregunta) de

sum += j[0]+j[1]+j[2]+j[3]+j[4]+j[5]+j[6]+j[7]+j[8]+j[9];

en realidad tiene un efecto similar, gracias a la ejecución fuera de orden. Cada grupo de 10 es una cadena de dependencia separada. Las reglas de orden de operaciones dicen que los valores j se suman primero y luego se suman a la sum . Por lo tanto, la cadena de dependencia transportada por el bucle sigue siendo solo la latencia de una adición de FP, y hay mucho trabajo independiente para cada grupo de 10. Cada grupo es una cadena de dependencia separada de 9 adiciones, y toma pocas instrucciones suficientes para la salida -ordenar hardware de ejecución para ver el inicio de la siguiente cadena y encontrar el paralelismo para mantener alimentadas esas unidades de ejecución FP de latencia media y alto rendimiento.

Con -O0 , como aparentemente requiere su tonta asignación, los valores se almacenan en la RAM al final de cada declaración. Escribir expresiones más largas sin actualizar ninguna variable, incluso temporales, hará que -O0 ejecute más rápido, pero no es una optimización útil. No pierdas tu tiempo en cambios que solo ayudan con -O0 , especialmente. no a expensas de la legibilidad.

El uso de 4 variables de acumulador y no sumarlas hasta el final del bucle externo derrota el vectorizador automático de clang. Todavía funciona en solo 1.66s (vs. 4.89 para el -O2 no vectorizado de -O2 con un acumulador). Incluso gcc -O2 sin -ffast-math también obtiene 1.66s por este cambio de fuente. Tenga en cuenta que se sabe que ARRAY_SIZE es un múltiplo de 4, por lo que no incluí ningún código de limpieza para manejar los últimos elementos de hasta 3 (o para evitar leer más allá del final de la matriz, que sucedería como está escrito ahora) . Es realmente fácil equivocarse y leer más allá del final de la matriz al hacer esto.

gcc, por otro lado, vectoriza esto, pero también pesimiza (no optimiza) el bucle interno en una sola cadena de dependencia. Creo que está haciendo múltiples iteraciones del bucle externo, nuevamente.

Utilizando las extensiones vectoriales independientes de la plataforma de gcc , escribí una versión que se compila en un código aparentemente óptimo:

// compile with gcc -g -Wall -std=gnu11 -Ofast -fno-tree-vectorize -march=native fast-loop-cs201.vec.c -o fl3-vec

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <assert.h>
#include <string.h>

// You are only allowed to make changes to this code as specified by the comments in it.

// The code you submit must have these two values.
#define N_TIMES     600000
#define ARRAY_SIZE   10000

int main(void)
{
    double  *array = calloc(ARRAY_SIZE, sizeof(double));
    double  sum = 0;
    int     i;

    // You can add variables between this comment ...
    long int help = 0;

    typedef double v4df __attribute__ ((vector_size (8*4)));
    v4df sum0={0}, sum1={0}, sum2={0}, sum3={0};

    const size_t array_bytes = ARRAY_SIZE*sizeof(double);
    double *aligned_array = NULL;

    // this more-than-declaration could go in an if(i == 0) block for strict compliance with the rules
    if ( posix_memalign((void**)&aligned_array, 32, array_bytes) ) {
        exit (1);
    }
    memcpy(aligned_array, array, array_bytes);  // In this one case: faster to align once and have no extra overhead for N_TIMES through the loop

    // ... and this one.

    // Please change ''your name'' to your actual name.
    printf("CS201 - Asgmt 4 - I. Forgot/n");

    for (i = 0; i < N_TIMES; i++) {

        // You can change anything between this comment ...
    /*
    #if defined(__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__) >= 407 // GCC 4.7 or later.
        array = __builtin_assume_aligned(array, 32);
    #else
        // force-align for other compilers.  This loop-invariant will be done outside the loop.
        array = (double*) ((ptrdiff_t)array & ~31);
    #endif
    */

        assert ( ARRAY_SIZE / (4*4) == (ARRAY_SIZE+15) / (4*4) );  // We don''t have a cleanup loop to handle where the array size isn''t a multiple of 16


        // incrementing pointers can be more efficient than indexing arrays
        // esp. on recent Intel where micro-fusion only works with one-register addressing modes
        // of course, the compiler can always generate pointer-incrementing asm from array-indexing source
        const double *start = aligned_array;

        while ( (ptrdiff_t)start & 31 ) {
            // annoying loops like this are the reason people use aligned buffers
            sum += *start++;        // scalar until we reach 32B alignment
            // in practice, this loop doesn''t run, because we copy into an aligned buffer
            // This will also require a cleanup loop, and break our multiple-of-16 doubles assumption.
        }

        const v4df *end = (v4df *)(aligned_array+ARRAY_SIZE);
        for (const v4df *p = (v4df *)start ; p+3 < end; p+=4) {
            sum0 += p[0];   // p+=4 increments the pointer by 4 * 4 * 8 bytes
            sum1 += p[1];       // make sure you keep track of what you''re incrementing
            sum2 += p[2];
            sum3 += p[3];

        }

        // the compiler might be smart enough to pull this out of the inner loop
        // in fact, gcc turns this into a 64bit movabs outside of both loops :P
        help+= ARRAY_SIZE;

            // ... and this one. But your inner loop must do the same
            // number of additions as this one does.

        /* You could argue legalese and say that
         if (i == 0) {
             for (j ...)
                 sum += array[j];
             sum *= N_TIMES;
         }
         * still does as many adds in its *INNER LOOP*, but it just doesn''t run it as often
         */
    }

    // You can add some final code between this comment ...
    sum0 = (sum0 + sum1) + (sum2 + sum3);
    sum += sum0[0] + sum0[1] + sum0[2] + sum0[3];
    printf("sum = %g; help=%ld/n", sum, help);  // defeat the compiler.

    free (aligned_array);
    free (array);  // not strictly necessary, because this is the end of main().  Leaving it out for this special case is a bad example for a CS class, though.
    // ... and this one.

    return 0;
}

El bucle interno se compila para:

  4007c0:       c5 e5 58 19             vaddpd (%rcx),%ymm3,%ymm3
  4007c4:       48 83 e9 80             sub    $0xffffffffffffff80,%rcx   # subtract -128, because -128 fits in imm8 instead of requiring an imm32 to encode add $128, %rcx
  4007c8:       c5 f5 58 49 a0          vaddpd -0x60(%rcx),%ymm1,%ymm1   # one-register addressing mode can micro-fuse
  4007cd:       c5 ed 58 51 c0          vaddpd -0x40(%rcx),%ymm2,%ymm2
  4007d2:       c5 fd 58 41 e0          vaddpd -0x20(%rcx),%ymm0,%ymm0
  4007d7:       4c 39 c1                cmp    %r8,%rcx  # compare with end with p
  4007da:       75 e4                   jne    4007c0 <main+0xb0>

(Para obtener más información, consulte la salida del compilador en línea en el explorador del compilador godbolt . La opción del compilador -xc compila como C, no como C ++. El bucle interno es de .L3 a jne .L3 . Consulte el wiki de etiquetas x86 para enlaces asm x86. Consulte también Estas preguntas y respuestas acerca de la micro fusión no suceden en la familia SnB , que las guías de Agner Fog no cubren).

actuación:

$ perf stat -e task-clock,cycles,instructions,r1b1,r10e,stalled-cycles-frontend,stalled-cycles-backend,L1-dcache-load-misses,cache-misses ./fl3-vec 
CS201 - Asgmt 4 - I. Forgot
sum = 0; help=6000000000

 Performance counter stats for ''./fl3-vec'':

       1086.571078      task-clock (msec)         #    1.000 CPUs utilized          
     4,072,679,849      cycles                    #    3.748 GHz                    
     2,629,419,883      instructions              #    0.65  insns per cycle        
                                                  #    1.27  stalled cycles per insn
     4,028,715,968      r1b1                      # 3707.733 M/sec  # unfused uops
     2,257,875,023      r10e                      # 2077.982 M/sec  # fused uops.  lower than insns because of macro-fusion
     3,328,275,626      stalled-cycles-frontend   #   81.72% frontend cycles idle   
     1,648,011,059      stalled-cycles-backend    #   40.47% backend  cycles idle   
       751,736,741      L1-dcache-load-misses     #  691.843 M/sec                  
            18,772      cache-misses              #    0.017 M/sec                  

       1.086925466 seconds time elapsed

Todavía no sé por qué recibe instrucciones tan bajas por ciclo. El bucle interno está usando 4 acumuladores separados, y verifiqué con gdb que los punteros están alineados. Entonces, los conflictos del banco de caché no deberían ser el problema. El caché Sandybridge L2 puede soportar una transferencia de 32B por ciclo, lo que debería mantenerse al día con la adición de un vector FP de 32B por ciclo.

Las cargas 32B de L1 toman 2 ciclos (no fue hasta Haswell que Intel hizo que las cargas 32B fueran una operación de ciclo único). Sin embargo, hay 2 puertos de carga, por lo que el rendimiento sostenido es de 32B por ciclo (que no estamos alcanzando).

¿Quizás las cargas necesitan ser canalizadas antes de cuando se usan, para minimizar que el ROB (reordenar el búfer) se llene cuando una carga se detiene? Pero los contadores de rendimiento indican una tasa de aciertos de caché L1 bastante alta, por lo que la captación previa de hardware de L2 a L1 parece estar haciendo su trabajo.

Las instrucciones de 0.65 por ciclo son solo la mitad del camino para saturar el sumador vectorial FP. Esto es frustrante. Incluso IACA dice que el ciclo debería ejecutarse en 4 ciclos por iteración. (es decir, saturar los puertos de carga y el puerto 1 (donde vive el sumador FP)): /

Actualización: supongo que el ancho de banda L2 fue el problema después de todo . No hay suficientes amortiguadores de llenado de línea para mantener suficientes fallas en vuelo para mantener el rendimiento máximo en cada ciclo. El ancho de banda sostenido L2 es menor que el pico en las CPU Intel SnB / Haswell / Skylake .

Consulte también Ancho de banda de memoria de subproceso único en Sandy Bridge (hilo del foro de Intel, con mucha discusión sobre qué limita el rendimiento y cómo la latency * max_concurrency es un posible cuello de botella. Consulte también la parte "Plataformas enlazadas de latencia" de la respuesta a Enhanced REP MOVSB ​​para memcpy ; la concurrencia de memoria limitada es un cuello de botella tanto para las cargas como para las tiendas, pero para la captación previa de cargas en L2 significa que es posible que no esté limitado únicamente por los buffers de Line Fill para fallas pendientes de L1D .

Reducir ARRAY_SIZE a 1008 (múltiplo de 16) y aumentar N_TIMES en un factor de 10, redujo el tiempo de ejecución a 0.5s. Eso es 1.68 insns por ciclo. (El bucle interno consta de 7 instrucciones en total para 4 adiciones de FP, por lo tanto, finalmente estamos saturando la unidad de adición de FP de vector y los puertos de carga).

Las CPU Intel solo tienen 32k de cada caché de datos L1 e instrucciones L1. Creo que su matriz apenas cabía en el 64kiB L1D en una CPU AMD K10 (Estambul) , pero no en la familia Bulldozer (16kiB L1D) o Ryzen (32kiB L1D).

El intento de Gcc de vectorizar transmitiendo el mismo valor en una suma paralela no parece tan loco. Si hubiera logrado hacer esto bien (usando múltiples acumuladores para ocultar la latencia), eso le habría permitido saturar el sumador vectorial FP con solo la mitad del ancho de banda de la memoria. Tal como está, fue casi un lavado, probablemente debido a la sobrecarga en la transmisión.

Además, es bastante tonto. N_TIMES es solo una repetición de trabajo. En realidad, no queremos optimizar para hacer el mismo trabajo varias veces. A menos que queramos ganar en tareas tontas como esta. Una forma de hacer esto a nivel de fuente sería incrementar i en la parte del código que podemos modificar:

for (...) {
    sum += a[j] + a[j] + a[j] + a[j];
}
i += 3;  // The inner loop does 4 total iterations of the outer loop

De manera más realista, para lidiar con esto, podría intercambiar sus bucles (bucle sobre la matriz una vez, agregando cada valor N_TIMES veces). Creo que he leído que el compilador de Intel a veces lo hará por usted.

Una técnica más general se llama bloqueo de caché o mosaico de bucles . La idea es trabajar en sus datos de entrada en pequeños bloques que quepan en la memoria caché. Dependiendo de su algoritmo, puede ser posible hacer varias etapas de una cosa en un fragmento, luego repetir para el siguiente fragmento, en lugar de hacer que cada etapa repita toda la entrada. Como siempre, una vez que conoces el nombre correcto para un truco (y que existe), puedes buscar en Google una tonelada de información.

Podrías abogarte por las reglas para poner un bucle intercambiado dentro de un bloque if (i == 0) en la parte del código que puedes modificar. Seguiría haciendo el mismo número de adiciones, pero en un orden más óptimo de caché.