¿Cómo logro el máximo teórico de 4 FLOP por ciclo?

643

¿Cómo se puede lograr el máximo rendimiento teórico de 4 operaciones de punto flotante (doble precisión) por ciclo en una CPU Intel x86-64 moderna?

Según tengo entendido, toma tres ciclos para un SSE add y cinco ciclos para mulcompletar en la mayoría de las CPU Intel modernas (ver, por ejemplo, las 'Tablas de instrucciones' de Agner Fog ). Debido a la canalización, se puede obtener un rendimiento de uno addpor ciclo si el algoritmo tiene al menos tres sumas independientes. Como eso es cierto tanto para addpdlas addsdversiones empaquetadas como para las escalares y los registros SSE pueden contener dos double, el rendimiento puede ser de hasta dos flops por ciclo.

Además, parece (aunque no he visto ninguna documentación adecuada sobre esto) add's y mul' s pueden ejecutarse en paralelo dando un rendimiento máximo teórico de cuatro flops por ciclo.

Sin embargo, no he podido replicar ese rendimiento con un simple programa C / C ++. Mi mejor intento resultó en alrededor de 2.7 flops / ciclo. Si alguien puede contribuir con un simple programa C / C ++ o ensamblador que demuestre un rendimiento máximo que sería muy apreciado.

Mi intento:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sys/time.h>

double stoptime(void) {
   struct timeval t;
   gettimeofday(&t,NULL);
   return (double) t.tv_sec + t.tv_usec/1000000.0;
}

double addmul(double add, double mul, int ops){
   // Need to initialise differently otherwise compiler might optimise away
   double sum1=0.1, sum2=-0.1, sum3=0.2, sum4=-0.2, sum5=0.0;
   double mul1=1.0, mul2= 1.1, mul3=1.2, mul4= 1.3, mul5=1.4;
   int loops=ops/10;          // We have 10 floating point operations inside the loop
   double expected = 5.0*add*loops + (sum1+sum2+sum3+sum4+sum5)
               + pow(mul,loops)*(mul1+mul2+mul3+mul4+mul5);

   for (int i=0; i<loops; i++) {
      mul1*=mul; mul2*=mul; mul3*=mul; mul4*=mul; mul5*=mul;
      sum1+=add; sum2+=add; sum3+=add; sum4+=add; sum5+=add;
   }
   return  sum1+sum2+sum3+sum4+sum5+mul1+mul2+mul3+mul4+mul5 - expected;
}

int main(int argc, char** argv) {
   if (argc != 2) {
      printf("usage: %s <num>\n", argv[0]);
      printf("number of operations: <num> millions\n");
      exit(EXIT_FAILURE);
   }
   int n = atoi(argv[1]) * 1000000;
   if (n<=0)
       n=1000;

   double x = M_PI;
   double y = 1.0 + 1e-8;
   double t = stoptime();
   x = addmul(x, y, n);
   t = stoptime() - t;
   printf("addmul:\t %.3f s, %.3f Gflops, res=%f\n", t, (double)n/t/1e9, x);
   return EXIT_SUCCESS;
}

Compilado con

g++ -O2 -march=native addmul.cpp ; ./a.out 1000

produce la siguiente salida en un Intel Core i5-750, 2.66 GHz.

addmul:  0.270 s, 3.707 Gflops, res=1.326463

Es decir, alrededor de 1.4 flops por ciclo. Mirar el código del ensamblador con g++ -S -O2 -march=native -masm=intel addmul.cppel bucle principal me parece óptimo:

.L4:
inc    eax
mulsd    xmm8, xmm3
mulsd    xmm7, xmm3
mulsd    xmm6, xmm3
mulsd    xmm5, xmm3
mulsd    xmm1, xmm3
addsd    xmm13, xmm2
addsd    xmm12, xmm2
addsd    xmm11, xmm2
addsd    xmm10, xmm2
addsd    xmm9, xmm2
cmp    eax, ebx
jne    .L4

Cambiar las versiones escalares con versiones empaquetadas ( addpdymulpd ) duplicaría el conteo de flops sin cambiar el tiempo de ejecución y, por lo tanto, obtendría poco menos de 2.8 flops por ciclo. ¿Hay un ejemplo simple que logre cuatro fracasos por ciclo?

Pequeño y agradable programa de Mysticial; Aquí están mis resultados (ejecute solo por unos segundos):

  • gcc -O2 -march=nocona: 5.6 Gflops de 10.66 Gflops (2.1 flops / ciclo)
  • cl /O2, openmp eliminado: 10.1 Gflops de 10.66 Gflops (3.8 flops / ciclo)

Todo parece un poco complejo, pero mis conclusiones hasta ahora:

  • gcc -O2cambia el orden de las operaciones independientes de coma flotante con el objetivo de alternar addpdy mulpd's si es posible. Lo mismo se aplica a gcc-4.6.2 -O2 -march=core2.

  • gcc -O2 -march=nocona parece mantener el orden de las operaciones de coma flotante como se define en la fuente de C ++.

  • cl /O2, el compilador de 64 bits del SDK para Windows 7 se desenrolla en bucle automáticamente y parece intentar organizar las operaciones para que grupos de tres se addpdalternen con tres mulpd(bueno, al menos en mi sistema y para mi programa simple) .

  • Mi Core i5 750 ( arquitectura Nehalem ) no le gusta alternar add's y mul's y parece incapaz de ejecutar ambas operaciones en paralelo. Sin embargo, si se agrupa en 3, de repente funciona como magia.

  • Parece que otras arquitecturas (posiblemente Sandy Bridge y otras) pueden ejecutar add / mul en paralelo sin problemas si se alternan en el código de ensamblaje.

  • Aunque es difícil de admitir, pero en mi sistema cl /O2hace un trabajo mucho mejor en operaciones de optimización de bajo nivel para mi sistema y logra un rendimiento cercano al pico para el pequeño ejemplo de C ++ anterior. Medí entre 1.85-2.01 flops / ciclo (he usado clock () en Windows, lo cual no es tan preciso. Supongo que necesito usar un mejor temporizador, gracias Mackie Messer).

  • Lo mejor que logré gccfue desenrollar manualmente el bucle y organizar adiciones y multiplicaciones en grupos de tres. Con lo g++ -O2 -march=nocona addmul_unroll.cpp que obtengo en el mejor de los casos, 0.207s, 4.825 Gflopsque corresponde a 1.8 flops / ciclo con el que estoy bastante contento ahora.

En el código C ++ he reemplazado el forbucle con

   for (int i=0; i<loops/3; i++) {
       mul1*=mul; mul2*=mul; mul3*=mul;
       sum1+=add; sum2+=add; sum3+=add;
       mul4*=mul; mul5*=mul; mul1*=mul;
       sum4+=add; sum5+=add; sum1+=add;

       mul2*=mul; mul3*=mul; mul4*=mul;
       sum2+=add; sum3+=add; sum4+=add;
       mul5*=mul; mul1*=mul; mul2*=mul;
       sum5+=add; sum1+=add; sum2+=add;

       mul3*=mul; mul4*=mul; mul5*=mul;
       sum3+=add; sum4+=add; sum5+=add;
   }

Y la asamblea ahora parece

.L4:
mulsd    xmm8, xmm3
mulsd    xmm7, xmm3
mulsd    xmm6, xmm3
addsd    xmm13, xmm2
addsd    xmm12, xmm2
addsd    xmm11, xmm2
mulsd    xmm5, xmm3
mulsd    xmm1, xmm3
mulsd    xmm8, xmm3
addsd    xmm10, xmm2
addsd    xmm9, xmm2
addsd    xmm13, xmm2
...
usuario1059432
fuente
15
Confiar en el tiempo del reloj de pared es probablemente parte de la causa. Suponiendo que esté ejecutando esto dentro de un sistema operativo como Linux, es libre de reprogramar su proceso en cualquier momento. Ese tipo de evento externo puede afectar sus mediciones de rendimiento.
tdenniston
¿Cuál es su versión de GCC? Si está en una Mac con el valor predeterminado, se encontrará con problemas (es un viejo 4.2).
Semisight
2
Sí, ejecuta Linux pero no hay carga en el sistema y repetirlo muchas veces hace pequeñas diferencias (por ejemplo, rangos 4.0-4.2 Gflops para la versión escalar, pero ahora con -funroll-loops). Intenté con gcc versión 4.4.1 y 4.6.2, pero la salida de asm parece estar bien?
user1059432
¿Intentaste -O3con gcc, que permite -ftree-vectorize? Quizás combinado con -funroll-loopsaunque no lo hago si eso es realmente necesario. Después de todo, la comparación parece un poco injusta si uno de los compiladores realiza la vectorización / desenrollado, mientras que el otro no lo hace porque no puede, sino porque también se le dice que no.
Grizzly
44
@ Grizzly -funroll-loopses probablemente algo para probar. Pero creo que -ftree-vectorizeestá más allá del punto. El OP está tratando de sostener solo 1 mul + 1 agregar instrucción / ciclo. Las instrucciones pueden ser escalares o vectoriales; no importa, ya que la latencia y el rendimiento son los mismos. Entonces, si puede mantener 2 / ciclo con SSE escalar, puede reemplazarlos con SSE vectorial y obtendrá 4 flops / ciclo. En mi respuesta, hice exactamente eso desde SSE -> AVX. Reemplacé todos los SSE con AVX: las mismas latencias, el mismo rendimiento, el doble de los flops.
Mysticial

Respuestas:

518

He hecho esta tarea exacta antes. Pero fue principalmente para medir el consumo de energía y las temperaturas de la CPU. El siguiente código (que es bastante largo) logra casi óptimo en mi Core i7 2600K.

Lo clave a tener en cuenta aquí es la enorme cantidad de desenrollado manual de bucles, así como el intercalado de multiplicaciones y sumas ...

El proyecto completo se puede encontrar en mi GitHub: https://github.com/Mysticial/Flops

Advertencia:

¡Si decides compilar y ejecutar esto, presta atención a las temperaturas de tu CPU!
Asegúrate de no sobrecalentarlo. ¡Y asegúrese de que la aceleración de la CPU no afecte sus resultados!

Además, no me responsabilizo por el daño que pueda resultar de ejecutar este código.

Notas:

  • Este código está optimizado para x64. x86 no tiene suficientes registros para que esto se compile bien.
  • Este código ha sido probado para que funcione bien en Visual Studio 2010/2012 y GCC 4.6.
    ICC 11 (Intel Compiler 11) sorprendentemente tiene problemas para compilarlo bien.
  • Estos son para procesadores pre-FMA. Para lograr el máximo FLOPS en los procesadores Intel Haswell y AMD Bulldozer (y posteriores), se necesitarán instrucciones FMA (Fused Multiply Add). Estos están más allá del alcance de este punto de referencia.

#include <emmintrin.h>
#include <omp.h>
#include <iostream>
using namespace std;

typedef unsigned long long uint64;

double test_dp_mac_SSE(double x,double y,uint64 iterations){
    register __m128d r0,r1,r2,r3,r4,r5,r6,r7,r8,r9,rA,rB,rC,rD,rE,rF;

    //  Generate starting data.
    r0 = _mm_set1_pd(x);
    r1 = _mm_set1_pd(y);

    r8 = _mm_set1_pd(-0.0);

    r2 = _mm_xor_pd(r0,r8);
    r3 = _mm_or_pd(r0,r8);
    r4 = _mm_andnot_pd(r8,r0);
    r5 = _mm_mul_pd(r1,_mm_set1_pd(0.37796447300922722721));
    r6 = _mm_mul_pd(r1,_mm_set1_pd(0.24253562503633297352));
    r7 = _mm_mul_pd(r1,_mm_set1_pd(4.1231056256176605498));
    r8 = _mm_add_pd(r0,_mm_set1_pd(0.37796447300922722721));
    r9 = _mm_add_pd(r1,_mm_set1_pd(0.24253562503633297352));
    rA = _mm_sub_pd(r0,_mm_set1_pd(4.1231056256176605498));
    rB = _mm_sub_pd(r1,_mm_set1_pd(4.1231056256176605498));

    rC = _mm_set1_pd(1.4142135623730950488);
    rD = _mm_set1_pd(1.7320508075688772935);
    rE = _mm_set1_pd(0.57735026918962576451);
    rF = _mm_set1_pd(0.70710678118654752440);

    uint64 iMASK = 0x800fffffffffffffull;
    __m128d MASK = _mm_set1_pd(*(double*)&iMASK);
    __m128d vONE = _mm_set1_pd(1.0);

    uint64 c = 0;
    while (c < iterations){
        size_t i = 0;
        while (i < 1000){
            //  Here's the meat - the part that really matters.

            r0 = _mm_mul_pd(r0,rC);
            r1 = _mm_add_pd(r1,rD);
            r2 = _mm_mul_pd(r2,rE);
            r3 = _mm_sub_pd(r3,rF);
            r4 = _mm_mul_pd(r4,rC);
            r5 = _mm_add_pd(r5,rD);
            r6 = _mm_mul_pd(r6,rE);
            r7 = _mm_sub_pd(r7,rF);
            r8 = _mm_mul_pd(r8,rC);
            r9 = _mm_add_pd(r9,rD);
            rA = _mm_mul_pd(rA,rE);
            rB = _mm_sub_pd(rB,rF);

            r0 = _mm_add_pd(r0,rF);
            r1 = _mm_mul_pd(r1,rE);
            r2 = _mm_sub_pd(r2,rD);
            r3 = _mm_mul_pd(r3,rC);
            r4 = _mm_add_pd(r4,rF);
            r5 = _mm_mul_pd(r5,rE);
            r6 = _mm_sub_pd(r6,rD);
            r7 = _mm_mul_pd(r7,rC);
            r8 = _mm_add_pd(r8,rF);
            r9 = _mm_mul_pd(r9,rE);
            rA = _mm_sub_pd(rA,rD);
            rB = _mm_mul_pd(rB,rC);

            r0 = _mm_mul_pd(r0,rC);
            r1 = _mm_add_pd(r1,rD);
            r2 = _mm_mul_pd(r2,rE);
            r3 = _mm_sub_pd(r3,rF);
            r4 = _mm_mul_pd(r4,rC);
            r5 = _mm_add_pd(r5,rD);
            r6 = _mm_mul_pd(r6,rE);
            r7 = _mm_sub_pd(r7,rF);
            r8 = _mm_mul_pd(r8,rC);
            r9 = _mm_add_pd(r9,rD);
            rA = _mm_mul_pd(rA,rE);
            rB = _mm_sub_pd(rB,rF);

            r0 = _mm_add_pd(r0,rF);
            r1 = _mm_mul_pd(r1,rE);
            r2 = _mm_sub_pd(r2,rD);
            r3 = _mm_mul_pd(r3,rC);
            r4 = _mm_add_pd(r4,rF);
            r5 = _mm_mul_pd(r5,rE);
            r6 = _mm_sub_pd(r6,rD);
            r7 = _mm_mul_pd(r7,rC);
            r8 = _mm_add_pd(r8,rF);
            r9 = _mm_mul_pd(r9,rE);
            rA = _mm_sub_pd(rA,rD);
            rB = _mm_mul_pd(rB,rC);

            i++;
        }

        //  Need to renormalize to prevent denormal/overflow.
        r0 = _mm_and_pd(r0,MASK);
        r1 = _mm_and_pd(r1,MASK);
        r2 = _mm_and_pd(r2,MASK);
        r3 = _mm_and_pd(r3,MASK);
        r4 = _mm_and_pd(r4,MASK);
        r5 = _mm_and_pd(r5,MASK);
        r6 = _mm_and_pd(r6,MASK);
        r7 = _mm_and_pd(r7,MASK);
        r8 = _mm_and_pd(r8,MASK);
        r9 = _mm_and_pd(r9,MASK);
        rA = _mm_and_pd(rA,MASK);
        rB = _mm_and_pd(rB,MASK);
        r0 = _mm_or_pd(r0,vONE);
        r1 = _mm_or_pd(r1,vONE);
        r2 = _mm_or_pd(r2,vONE);
        r3 = _mm_or_pd(r3,vONE);
        r4 = _mm_or_pd(r4,vONE);
        r5 = _mm_or_pd(r5,vONE);
        r6 = _mm_or_pd(r6,vONE);
        r7 = _mm_or_pd(r7,vONE);
        r8 = _mm_or_pd(r8,vONE);
        r9 = _mm_or_pd(r9,vONE);
        rA = _mm_or_pd(rA,vONE);
        rB = _mm_or_pd(rB,vONE);

        c++;
    }

    r0 = _mm_add_pd(r0,r1);
    r2 = _mm_add_pd(r2,r3);
    r4 = _mm_add_pd(r4,r5);
    r6 = _mm_add_pd(r6,r7);
    r8 = _mm_add_pd(r8,r9);
    rA = _mm_add_pd(rA,rB);

    r0 = _mm_add_pd(r0,r2);
    r4 = _mm_add_pd(r4,r6);
    r8 = _mm_add_pd(r8,rA);

    r0 = _mm_add_pd(r0,r4);
    r0 = _mm_add_pd(r0,r8);


    //  Prevent Dead Code Elimination
    double out = 0;
    __m128d temp = r0;
    out += ((double*)&temp)[0];
    out += ((double*)&temp)[1];

    return out;
}

void test_dp_mac_SSE(int tds,uint64 iterations){

    double *sum = (double*)malloc(tds * sizeof(double));
    double start = omp_get_wtime();

#pragma omp parallel num_threads(tds)
    {
        double ret = test_dp_mac_SSE(1.1,2.1,iterations);
        sum[omp_get_thread_num()] = ret;
    }

    double secs = omp_get_wtime() - start;
    uint64 ops = 48 * 1000 * iterations * tds * 2;
    cout << "Seconds = " << secs << endl;
    cout << "FP Ops  = " << ops << endl;
    cout << "FLOPs   = " << ops / secs << endl;

    double out = 0;
    int c = 0;
    while (c < tds){
        out += sum[c++];
    }

    cout << "sum = " << out << endl;
    cout << endl;

    free(sum);
}

int main(){
    //  (threads, iterations)
    test_dp_mac_SSE(8,10000000);

    system("pause");
}

Salida (1 subproceso, 10000000 iteraciones) - Compilada con Visual Studio 2010 SP1 - Versión x64:

Seconds = 55.5104
FP Ops  = 960000000000
FLOPs   = 1.7294e+010
sum = 2.22652

La máquina es un Core i7 2600K @ 4.4 GHz. El pico teórico de SSE es de 4 flops * 4.4 GHz = 17.6 GFlops . Este código logra 17.3 GFlops , no está mal.

Salida (8 hilos, 10000000 iteraciones) - Compilada con Visual Studio 2010 SP1 - Versión x64:

Seconds = 117.202
FP Ops  = 7680000000000
FLOPs   = 6.55279e+010
sum = 17.8122

El pico de SSE teórico es de 4 flops * 4 núcleos * 4.4 GHz = 70.4 GFlops. Real es 65.5 GFlops .


Vayamos un paso más allá. AVX ...

#include <immintrin.h>
#include <omp.h>
#include <iostream>
using namespace std;

typedef unsigned long long uint64;

double test_dp_mac_AVX(double x,double y,uint64 iterations){
    register __m256d r0,r1,r2,r3,r4,r5,r6,r7,r8,r9,rA,rB,rC,rD,rE,rF;

    //  Generate starting data.
    r0 = _mm256_set1_pd(x);
    r1 = _mm256_set1_pd(y);

    r8 = _mm256_set1_pd(-0.0);

    r2 = _mm256_xor_pd(r0,r8);
    r3 = _mm256_or_pd(r0,r8);
    r4 = _mm256_andnot_pd(r8,r0);
    r5 = _mm256_mul_pd(r1,_mm256_set1_pd(0.37796447300922722721));
    r6 = _mm256_mul_pd(r1,_mm256_set1_pd(0.24253562503633297352));
    r7 = _mm256_mul_pd(r1,_mm256_set1_pd(4.1231056256176605498));
    r8 = _mm256_add_pd(r0,_mm256_set1_pd(0.37796447300922722721));
    r9 = _mm256_add_pd(r1,_mm256_set1_pd(0.24253562503633297352));
    rA = _mm256_sub_pd(r0,_mm256_set1_pd(4.1231056256176605498));
    rB = _mm256_sub_pd(r1,_mm256_set1_pd(4.1231056256176605498));

    rC = _mm256_set1_pd(1.4142135623730950488);
    rD = _mm256_set1_pd(1.7320508075688772935);
    rE = _mm256_set1_pd(0.57735026918962576451);
    rF = _mm256_set1_pd(0.70710678118654752440);

    uint64 iMASK = 0x800fffffffffffffull;
    __m256d MASK = _mm256_set1_pd(*(double*)&iMASK);
    __m256d vONE = _mm256_set1_pd(1.0);

    uint64 c = 0;
    while (c < iterations){
        size_t i = 0;
        while (i < 1000){
            //  Here's the meat - the part that really matters.

            r0 = _mm256_mul_pd(r0,rC);
            r1 = _mm256_add_pd(r1,rD);
            r2 = _mm256_mul_pd(r2,rE);
            r3 = _mm256_sub_pd(r3,rF);
            r4 = _mm256_mul_pd(r4,rC);
            r5 = _mm256_add_pd(r5,rD);
            r6 = _mm256_mul_pd(r6,rE);
            r7 = _mm256_sub_pd(r7,rF);
            r8 = _mm256_mul_pd(r8,rC);
            r9 = _mm256_add_pd(r9,rD);
            rA = _mm256_mul_pd(rA,rE);
            rB = _mm256_sub_pd(rB,rF);

            r0 = _mm256_add_pd(r0,rF);
            r1 = _mm256_mul_pd(r1,rE);
            r2 = _mm256_sub_pd(r2,rD);
            r3 = _mm256_mul_pd(r3,rC);
            r4 = _mm256_add_pd(r4,rF);
            r5 = _mm256_mul_pd(r5,rE);
            r6 = _mm256_sub_pd(r6,rD);
            r7 = _mm256_mul_pd(r7,rC);
            r8 = _mm256_add_pd(r8,rF);
            r9 = _mm256_mul_pd(r9,rE);
            rA = _mm256_sub_pd(rA,rD);
            rB = _mm256_mul_pd(rB,rC);

            r0 = _mm256_mul_pd(r0,rC);
            r1 = _mm256_add_pd(r1,rD);
            r2 = _mm256_mul_pd(r2,rE);
            r3 = _mm256_sub_pd(r3,rF);
            r4 = _mm256_mul_pd(r4,rC);
            r5 = _mm256_add_pd(r5,rD);
            r6 = _mm256_mul_pd(r6,rE);
            r7 = _mm256_sub_pd(r7,rF);
            r8 = _mm256_mul_pd(r8,rC);
            r9 = _mm256_add_pd(r9,rD);
            rA = _mm256_mul_pd(rA,rE);
            rB = _mm256_sub_pd(rB,rF);

            r0 = _mm256_add_pd(r0,rF);
            r1 = _mm256_mul_pd(r1,rE);
            r2 = _mm256_sub_pd(r2,rD);
            r3 = _mm256_mul_pd(r3,rC);
            r4 = _mm256_add_pd(r4,rF);
            r5 = _mm256_mul_pd(r5,rE);
            r6 = _mm256_sub_pd(r6,rD);
            r7 = _mm256_mul_pd(r7,rC);
            r8 = _mm256_add_pd(r8,rF);
            r9 = _mm256_mul_pd(r9,rE);
            rA = _mm256_sub_pd(rA,rD);
            rB = _mm256_mul_pd(rB,rC);

            i++;
        }

        //  Need to renormalize to prevent denormal/overflow.
        r0 = _mm256_and_pd(r0,MASK);
        r1 = _mm256_and_pd(r1,MASK);
        r2 = _mm256_and_pd(r2,MASK);
        r3 = _mm256_and_pd(r3,MASK);
        r4 = _mm256_and_pd(r4,MASK);
        r5 = _mm256_and_pd(r5,MASK);
        r6 = _mm256_and_pd(r6,MASK);
        r7 = _mm256_and_pd(r7,MASK);
        r8 = _mm256_and_pd(r8,MASK);
        r9 = _mm256_and_pd(r9,MASK);
        rA = _mm256_and_pd(rA,MASK);
        rB = _mm256_and_pd(rB,MASK);
        r0 = _mm256_or_pd(r0,vONE);
        r1 = _mm256_or_pd(r1,vONE);
        r2 = _mm256_or_pd(r2,vONE);
        r3 = _mm256_or_pd(r3,vONE);
        r4 = _mm256_or_pd(r4,vONE);
        r5 = _mm256_or_pd(r5,vONE);
        r6 = _mm256_or_pd(r6,vONE);
        r7 = _mm256_or_pd(r7,vONE);
        r8 = _mm256_or_pd(r8,vONE);
        r9 = _mm256_or_pd(r9,vONE);
        rA = _mm256_or_pd(rA,vONE);
        rB = _mm256_or_pd(rB,vONE);

        c++;
    }

    r0 = _mm256_add_pd(r0,r1);
    r2 = _mm256_add_pd(r2,r3);
    r4 = _mm256_add_pd(r4,r5);
    r6 = _mm256_add_pd(r6,r7);
    r8 = _mm256_add_pd(r8,r9);
    rA = _mm256_add_pd(rA,rB);

    r0 = _mm256_add_pd(r0,r2);
    r4 = _mm256_add_pd(r4,r6);
    r8 = _mm256_add_pd(r8,rA);

    r0 = _mm256_add_pd(r0,r4);
    r0 = _mm256_add_pd(r0,r8);

    //  Prevent Dead Code Elimination
    double out = 0;
    __m256d temp = r0;
    out += ((double*)&temp)[0];
    out += ((double*)&temp)[1];
    out += ((double*)&temp)[2];
    out += ((double*)&temp)[3];

    return out;
}

void test_dp_mac_AVX(int tds,uint64 iterations){

    double *sum = (double*)malloc(tds * sizeof(double));
    double start = omp_get_wtime();

#pragma omp parallel num_threads(tds)
    {
        double ret = test_dp_mac_AVX(1.1,2.1,iterations);
        sum[omp_get_thread_num()] = ret;
    }

    double secs = omp_get_wtime() - start;
    uint64 ops = 48 * 1000 * iterations * tds * 4;
    cout << "Seconds = " << secs << endl;
    cout << "FP Ops  = " << ops << endl;
    cout << "FLOPs   = " << ops / secs << endl;

    double out = 0;
    int c = 0;
    while (c < tds){
        out += sum[c++];
    }

    cout << "sum = " << out << endl;
    cout << endl;

    free(sum);
}

int main(){
    //  (threads, iterations)
    test_dp_mac_AVX(8,10000000);

    system("pause");
}

Salida (1 subproceso, 10000000 iteraciones) - Compilada con Visual Studio 2010 SP1 - Versión x64:

Seconds = 57.4679
FP Ops  = 1920000000000
FLOPs   = 3.34099e+010
sum = 4.45305

El pico AVX teórico es de 8 flops * 4.4 GHz = 35.2 GFlops . Real es 33.4 GFlops .

Salida (8 hilos, 10000000 iteraciones) - Compilada con Visual Studio 2010 SP1 - Versión x64:

Seconds = 111.119
FP Ops  = 15360000000000
FLOPs   = 1.3823e+011
sum = 35.6244

El pico AVX teórico es de 8 flops * 4 núcleos * 4.4 GHz = 140.8 GFlops. Real es 138.2 GFlops .


Ahora para algunas explicaciones:

La parte crítica del rendimiento es obviamente las 48 instrucciones dentro del bucle interno. Notarás que está dividido en 4 bloques de 12 instrucciones cada uno. Cada uno de estos 12 bloques de instrucciones es completamente independiente el uno del otro, y toma un promedio de 6 ciclos para ejecutarse.

Así que hay 12 instrucciones y 6 ciclos entre problemas de uso. La latencia de la multiplicación es de 5 ciclos, por lo que es suficiente para evitar los bloqueos de latencia.

El paso de normalización es necesario para evitar que los datos se desborden / desborden. Esto es necesario ya que el código de no hacer nada aumentará / disminuirá lentamente la magnitud de los datos.

Por lo tanto, en realidad es posible hacerlo mejor si solo usa todos los ceros y se deshace del paso de normalización. Sin embargo, desde que escribí el punto de referencia para medir el consumo de energía y la temperatura, tuve que asegurarme de que los flops estuvieran en datos "reales", en lugar de ceros , ya que las unidades de ejecución pueden tener un manejo de casos especial para ceros que usan menos energía y producen menos calor.


Más resultados:

  • Intel Core i7 920 a 3.5 GHz
  • Windows 7 Ultimate x64
  • Visual Studio 2010 SP1 - Versión x64

Hilos: 1

Seconds = 72.1116
FP Ops  = 960000000000
FLOPs   = 1.33127e+010
sum = 2.22652

Pico teórico de SSE: 4 flops * 3.5 GHz = 14.0 GFlops . Real es 13.3 GFlops .

Subprocesos: 8

Seconds = 149.576
FP Ops  = 7680000000000
FLOPs   = 5.13452e+010
sum = 17.8122

Pico teórico de SSE: 4 flops * 4 núcleos * 3.5 GHz = 56.0 GFlops . Real es 51.3 GFlops .

¡Las temperaturas de mi procesador alcanzaron los 76 ° C en la ejecución de subprocesos múltiples! Si ejecuta estos, asegúrese de que los resultados no se vean afectados por la aceleración de la CPU.


  • 2 x Intel Xeon X5482 Harpertown @ 3.2 GHz
  • Ubuntu Linux 10 x64
  • GCC 4.5.2 x64 - (-O2 -msse3 -fopenmp)

Hilos: 1

Seconds = 78.3357
FP Ops  = 960000000000
FLOPs   = 1.22549e+10
sum = 2.22652

Pico SSE teórico: 4 flops * 3.2 GHz = 12.8 GFlops . Real es 12.3 GFlops .

Subprocesos: 8

Seconds = 78.4733
FP Ops  = 7680000000000
FLOPs   = 9.78676e+10
sum = 17.8122

Pico SSE teórico: 4 flops * 8 núcleos * 3.2 GHz = 102.4 GFlops . Real es 97.9 GFlops .

Místico
fuente
13
Tus resultados son muy impresionantes. He compilado su código con g ++ en mi sistema anterior, pero no obtengo resultados tan buenos: iteraciones de 100k, 1.814s, 5.292 Gflops, sum=0.448883de un máximo de 10.68 Gflops o apenas menos de 2.0 flops por ciclo. Parece add/ mulno se ejecuta en paralelo. Cuando cambio su código y siempre agrego / multiplico con el mismo registro, digamos rC, de repente alcanza casi el pico: 0.953s, 10.068 Gflops, sum=0o 3.8 flops / ciclo. Muy extraño.
user1059432
11
Sí, dado que no estoy usando el ensamblaje en línea, el rendimiento es muy sensible al compilador. El código que tengo aquí ha sido ajustado para VC2010. Y si no recuerdo mal, el compilador de Intel da tan buenos resultados. Como habrás notado, es posible que tengas que ajustarlo un poco para que se compile bien.
Mysticial
8
Puedo confirmar sus resultados en Windows 7 usando cl /O2(64 bits desde Windows SDK) e incluso mi ejemplo se ejecuta cerca del pico para operaciones escalares (1.9 flops / ciclo) allí. El compilador se desenrolla y reordena, pero esa podría no ser la razón por la que debe analizar esto un poco más. Acelerar no es un problema. Soy amable con mi CPU y mantengo las iteraciones a 100k. :)
user1059432
66
@Mysticial: Hoy apareció en el subreddit r / coding .
greyfade
2
@haylem Se derrite o despega. Nunca los dos. Si hay suficiente enfriamiento, obtendrá tiempo de aire. De lo contrario, simplemente se derrite. :)
Mysticial
33

Hay un punto en la arquitectura de Intel que la gente suele olvidar, los puertos de envío se comparten entre Int y FP / SIMD. Esto significa que solo obtendrá una cierta cantidad de ráfagas de FP / SIMD antes de que la lógica del bucle cree burbujas en su flujo de coma flotante. Mystical obtuvo más fracasos de su código, porque usó zancadas más largas en su bucle desenrollado.

Si observa la arquitectura de Nehalem / Sandy Bridge aquí http://www.realworldtech.com/page.cfm?ArticleID=RWT091810191937&p=6 , está bastante claro lo que sucede.

Por el contrario, debería ser más fácil alcanzar el máximo rendimiento en AMD (Bulldozer) ya que las tuberías INT y FP / SIMD tienen puertos de problema separados con su propio programador.

Esto es solo teórico ya que no tengo ninguno de estos procesadores para probar.

Patrick Schlüter
fuente
2
Sólo hay tres instrucciones de sobrecarga de bucle: inc, cmp, y jl. Todos estos pueden ir al puerto # 5 y no interferir con ni vectorizado faddni fmul. Prefiero sospechar que el decodificador (a veces) se interpone en el camino. Necesita mantener entre dos y tres instrucciones por ciclo. No recuerdo las limitaciones exactas, pero la duración de la instrucción, los prefijos y la alineación entran en juego.
Mackie Messer
cmpy jlciertamente vaya al puerto 5, incno tan seguro como siempre viene en grupo con los otros 2. Pero tienes razón, es difícil saber dónde está el cuello de botella y los decodificadores también pueden ser parte de él.
Patrick Schlüter
3
Jugué un poco con el bucle básico: el orden de las instrucciones es importante. Algunos arreglos toman 13 ciclos en lugar de los 5 ciclos mínimos. Es hora de mirar los contadores de eventos de rendimiento, supongo ...
Mackie Messer
16

Las sucursales definitivamente pueden evitar que mantenga un rendimiento teórico máximo. ¿Ves alguna diferencia si realizas manualmente un ciclo de desenrollado? Por ejemplo, si coloca 5 o 10 veces más operaciones por iteración de bucle:

for(int i=0; i<loops/5; i++) {
      mul1*=mul; mul2*=mul; mul3*=mul; mul4*=mul; mul5*=mul;
      sum1+=add; sum2+=add; sum3+=add; sum4+=add; sum5+=add;
      mul1*=mul; mul2*=mul; mul3*=mul; mul4*=mul; mul5*=mul;
      sum1+=add; sum2+=add; sum3+=add; sum4+=add; sum5+=add;
      mul1*=mul; mul2*=mul; mul3*=mul; mul4*=mul; mul5*=mul;
      sum1+=add; sum2+=add; sum3+=add; sum4+=add; sum5+=add;
      mul1*=mul; mul2*=mul; mul3*=mul; mul4*=mul; mul5*=mul;
      sum1+=add; sum2+=add; sum3+=add; sum4+=add; sum5+=add;
      mul1*=mul; mul2*=mul; mul3*=mul; mul4*=mul; mul5*=mul;
      sum1+=add; sum2+=add; sum3+=add; sum4+=add; sum5+=add;
   }
TJD
fuente
44
Puedo estar equivocado, pero creo que g ++ con -O2 intentará desenrollar automáticamente el bucle (creo que usa el dispositivo de Duff).
Weaver
66
Sí, gracias de hecho mejora un poco. Ahora obtengo alrededor de 4.1-4.3 Gflops, o 1.55 flops por ciclo. Y no, en este ejemplo -O2 no se desenrolló en bucle.
user1059432
1
Weaver tiene razón sobre el desenrollamiento del bucle, creo. Por lo tanto, es probable que no sea necesario desenrollar manualmente
jim mcnamara
55
Vea la salida del ensamblaje arriba, no hay signos de desenrollamiento del bucle.
user1059432
14
El desenrollado automático también mejora a un promedio de 4.2 Gflops, pero requiere una -funroll-loopsopción que ni siquiera está incluida -O3. Ver g++ -c -Q -O2 --help=optimizers | grep unroll.
user1059432
7

Usando Intels icc Versión 11.1 en un Intel Core 2 Duo de 2.4GHz obtengo

Macintosh:~ mackie$ icc -O3 -mssse3 -oaddmul addmul.cc && ./addmul 1000
addmul:  0.105 s, 9.525 Gflops, res=0.000000
Macintosh:~ mackie$ icc -v
Version 11.1 

Eso está muy cerca de los 9.6 Gflops ideales.

EDITAR:

Oops, mirando el código de ensamblaje parece que icc no solo vectorizó la multiplicación, sino que también eliminó las adiciones del bucle. Al forzar una semántica fp más estricta, el código ya no está vectorizado:

Macintosh:~ mackie$ icc -O3 -mssse3 -oaddmul addmul.cc -fp-model precise && ./addmul 1000
addmul:  0.516 s, 1.938 Gflops, res=1.326463

EDIT2:

De acuerdo a lo pedido:

Macintosh:~ mackie$ clang -O3 -mssse3 -oaddmul addmul.cc && ./addmul 1000
addmul:  0.209 s, 4.786 Gflops, res=1.326463
Macintosh:~ mackie$ clang -v
Apple clang version 3.0 (tags/Apple/clang-211.10.1) (based on LLVM 3.0svn)
Target: x86_64-apple-darwin11.2.0
Thread model: posix

El bucle interno del código de clang se ve así:

        .align  4, 0x90
LBB2_4:                                 ## =>This Inner Loop Header: Depth=1
        addsd   %xmm2, %xmm3
        addsd   %xmm2, %xmm14
        addsd   %xmm2, %xmm5
        addsd   %xmm2, %xmm1
        addsd   %xmm2, %xmm4
        mulsd   %xmm2, %xmm0
        mulsd   %xmm2, %xmm6
        mulsd   %xmm2, %xmm7
        mulsd   %xmm2, %xmm11
        mulsd   %xmm2, %xmm13
        incl    %eax
        cmpl    %r14d, %eax
        jl      LBB2_4

EDITAR3:

Finalmente, dos sugerencias: Primero, si le gusta este tipo de evaluación comparativa, considere usar la rdtscinstrucción en lugar de gettimeofday(2). Es mucho más preciso y ofrece el tiempo en ciclos, que generalmente es lo que le interesa de todos modos. Para gcc y amigos, puede definirlo así:

#include <stdint.h>

static __inline__ uint64_t rdtsc(void)
{
        uint64_t rval;
        __asm__ volatile ("rdtsc" : "=A" (rval));
        return rval;
}

En segundo lugar, debe ejecutar su programa de referencia varias veces y usar solo el mejor rendimiento . En los sistemas operativos modernos suceden muchas cosas en paralelo, la CPU puede estar en un modo de ahorro de energía de baja frecuencia, etc. Ejecutar el programa repetidamente le da un resultado más cercano al caso ideal.

Mackie Messer
fuente
2
¿Y cómo se ve el desmontaje?
Bahbar
1
Interesante, eso es menos de 1 flop / ciclo. ¿El compilador mezcla los addsd'sy mulsd' o están en grupos como en mi salida de ensamblaje? También obtengo aproximadamente 1 flop / ciclo cuando el compilador los mezcla (sin el cual lo hago -march=native). ¿Cómo cambia el rendimiento si agrega una línea add=mul;al comienzo de la función addmul(...)?
user1059432
1
@ user1059432: las instrucciones addsdy subsdse mezclan en la versión precisa. También probé el clang 3.0, no combina instrucciones y se acerca mucho a 2 flops / ciclo en el núcleo 2 duo. Cuando ejecuto el mismo código en mis computadoras portátiles Core i5, mezclar el código no hace ninguna diferencia. Tengo alrededor de 3 flops / ciclo en cualquier caso.
Mackie Messer
1
@ user1059432: Al final, se trata de engañar al compilador para que genere código "significativo" para un punto de referencia sintético. Esto es más difícil de lo que parece a primera vista. (es decir, icc supera su punto de referencia) Si todo lo que desea es ejecutar algún código a 4 flops / ciclo, lo más fácil es escribir un pequeño bucle de ensamblaje. Mucho menos dolor de cabeza. :-)
Mackie Messer
1
Ok, ¿entonces te acercas a 2 flops / ciclo con un código de ensamblaje similar al que he citado anteriormente? ¿Qué tan cerca de 2? Solo obtengo 1.4, así que eso es significativo. No creo que obtenga 3 flops / ciclo en su computadora portátil a menos que el compilador haga optimizaciones como ha visto iccantes, ¿puede verificar el ensamblaje?
user1059432