Wie erreiche ich das theoretische Maximum von 4 FLOPs pro Zyklus?

642

Wie kann die theoretische Spitzenleistung von 4 Gleitkommaoperationen (doppelte Genauigkeit) pro Zyklus auf einer modernen x86-64 Intel-CPU erreicht werden?

Soweit ich weiß, dauert es drei Zyklen für eine SSE add und fünf Zyklen, mulbis eine SSE auf den meisten modernen Intel-CPUs abgeschlossen ist (siehe zum Beispiel die 'Instruction Tables' von Agner Fog ). Aufgrund von Pipelining kann ein Durchsatz von einem addpro Zyklus erzielt werden, wenn der Algorithmus mindestens drei unabhängige Summierungen aufweist. Da dies sowohl für gepackte addpdals auch für skalare addsdVersionen gilt und SSE-Register zwei enthalten doublekönnen, kann der Durchsatz bis zu zwei Flops pro Zyklus betragen.

Darüber hinaus scheinen (obwohl ich keine ordnungsgemäße Dokumentation dazu gesehen habe) addund mulkönnen parallel ausgeführt werden, was einen theoretischen maximalen Durchsatz von vier Flops pro Zyklus ergibt.

Ich konnte diese Leistung jedoch nicht mit einem einfachen C / C ++ - Programm replizieren. Mein bester Versuch ergab ungefähr 2,7 Flops / Zyklus. Wenn jemand ein einfaches C / C ++ - oder Assembler-Programm beisteuern kann, das Spitzenleistungen demonstriert, wäre er sehr dankbar.

Mein Versuch:

#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;
}

Zusammengestellt mit

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

erzeugt die folgende Ausgabe auf einem Intel Core i5-750 mit 2,66 GHz.

addmul:  0.270 s, 3.707 Gflops, res=1.326463

Das sind nur etwa 1,4 Flops pro Zyklus. Das Betrachten des Assembler-Codes mit g++ -S -O2 -march=native -masm=intel addmul.cppder Hauptschleife erscheint mir irgendwie optimal:

.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

Das Ändern der Skalarversionen mit gepackten Versionen ( addpdund mulpd) würde die Anzahl der Flops verdoppeln, ohne die Ausführungszeit zu ändern, und so würde ich nur knapp 2,8 Flops pro Zyklus erhalten. Gibt es ein einfaches Beispiel, das vier Flops pro Zyklus erzielt?

Nettes kleines Programm von Mysticial; Hier sind meine Ergebnisse (nur für ein paar Sekunden):

  • gcc -O2 -march=nocona: 5,6 Gflops von 10,66 Gflops (2,1 Flops / Zyklus)
  • cl /O2, openmp entfernt: 10,1 Gflops von 10,66 Gflops (3,8 Flops / Zyklus)

Es scheint alles ein bisschen komplex, aber meine bisherigen Schlussfolgerungen:

  • gcc -O2ändert die Reihenfolge der unabhängigen Gleitkommaoperationen mit dem Ziel des Wechsels addpdund mulpdwenn möglich. Gleiches gilt für gcc-4.6.2 -O2 -march=core2.

  • gcc -O2 -march=nocona scheint die in der C ++ - Quelle definierte Reihenfolge der Gleitkommaoperationen beizubehalten.

  • cl /O2Der 64-Bit-Compiler aus dem SDK für Windows 7 führt das automatische Abrollen der Schleife durch und scheint zu versuchen, Vorgänge so anzuordnen, dass Dreiergruppen mit Dreiergruppen addpdabwechseln mulpd(zumindest auf meinem System und für mein einfaches Programm). .

  • Mein Core i5 750 ( Nehalem-Architektur ) mag keine abwechselnden Adds und Mul's und scheint nicht in der Lage zu sein, beide Operationen parallel auszuführen. Wenn es jedoch in 3er gruppiert ist, funktioniert es plötzlich wie Magie.

  • Andere Architekturen (möglicherweise Sandy Bridge und andere) scheinen add / mul problemlos parallel ausführen zu können, wenn sie sich im Assemblycode abwechseln.

  • Es ist zwar schwer zuzugeben, aber auf meinem System cl /O2macht es einen viel besseren Job bei Optimierungsvorgängen auf niedriger Ebene für mein System und erzielt für das kleine C ++ - Beispiel oben eine nahezu maximale Leistung. Ich habe zwischen 1,85 und 2,01 Flops / Zyklus gemessen (habe Clock () in Windows verwendet, was nicht so genau ist. Ich denke, ich muss einen besseren Timer verwenden - danke Mackie Messer).

  • Das Beste, was ich geschafft habe, gccwar das manuelle Abrollen und Anordnen von Additionen und Multiplikationen in Dreiergruppen. Mit g++ -O2 -march=nocona addmul_unroll.cpp bekomme ich bestenfalls 0.207s, 4.825 Gflops1,8 Flops / Zyklus, mit denen ich jetzt ziemlich zufrieden bin.

Im C ++ - Code habe ich die forSchleife durch ersetzt

   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;
   }

Und die Montage sieht jetzt so aus

.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
...
user1059432
quelle
15
Sich auf die Wanduhrzeit zu verlassen, ist wahrscheinlich ein Teil der Ursache. Angenommen, Sie führen dies in einem Betriebssystem wie Linux aus, ist es jederzeit kostenlos, Ihren Prozess zu planen. Diese Art von externem Ereignis kann sich auf Ihre Leistungsmessungen auswirken.
Tdenniston
Was ist Ihre GCC-Version? Wenn Sie mit der Standardeinstellung auf einem Mac arbeiten, treten Probleme auf (es handelt sich um eine alte Version 4.2).
Semisight
2
Ja, Linux wird ausgeführt, aber das System ist nicht belastet, und das mehrmalige Wiederholen macht nur geringe Unterschiede (z. B. Bereiche 4.0-4.2 Gflops für die skalare Version, jetzt jedoch mit -funroll-loops). Versucht mit gcc Version 4.4.1 und 4.6.2, aber asm Ausgabe sieht in Ordnung aus?
user1059432
Haben Sie -O3für gcc versucht , was ermöglicht -ftree-vectorize? Vielleicht kombiniert mit -funroll-loopsobwohl ich nicht nicht, wenn das wirklich notwendig ist. Immerhin scheint der Vergleich irgendwie unfair zu sein, wenn einer der Compiler Vektorisierung / Abrollen durchführt, während der andere dies nicht tut, weil er es nicht kann, sondern weil es nicht auch gesagt wird.
Grizzly
4
@Grizzly -funroll-loopsist wahrscheinlich etwas zu versuchen. Aber ich denke -ftree-vectorizeist neben dem Punkt. Das OP versucht nur, 1 Mul + 1 Add-Anweisung / Zyklus aufrechtzuerhalten. Die Anweisungen können skalar oder vektoriell sein - dies spielt keine Rolle, da Latenz und Durchsatz gleich sind. Wenn Sie also 2 / Zyklus mit skalarer SSE aufrechterhalten können, können Sie sie durch Vektor-SSE ersetzen und Sie erhalten 4 Flops / Zyklus. In meiner Antwort habe ich genau das von SSE -> AVX aus gemacht. Ich habe alle SSE durch AVX ersetzt - gleiche Latenzen, gleiche Durchsätze, 2x die Flops.
Mysticial

Antworten:

517

Ich habe genau diese Aufgabe schon einmal erledigt. Es ging aber hauptsächlich darum, den Stromverbrauch und die CPU-Temperaturen zu messen. Der folgende Code (der ziemlich lang ist) erreicht auf meinem Core i7 2600K nahezu das Optimum.

Das Wichtigste dabei ist die enorme Menge an manuellem Abrollen von Schleifen sowie das Verschachteln von Multiplikationen und Adds ...

Das vollständige Projekt finden Sie auf meinem GitHub: https://github.com/Mysticial/Flops

Warnung:

Wenn Sie dies kompilieren und ausführen möchten, achten Sie auf Ihre CPU-Temperaturen !!!
Stellen Sie sicher, dass Sie es nicht überhitzen. Und stellen Sie sicher, dass die CPU-Drosselung Ihre Ergebnisse nicht beeinflusst!

Darüber hinaus übernehme ich keine Verantwortung für Schäden, die durch das Ausführen dieses Codes entstehen können.

Anmerkungen:

  • Dieser Code ist für x64 optimiert. x86 verfügt nicht über genügend Register, um dies gut zu kompilieren.
  • Dieser Code wurde getestet, um unter Visual Studio 2010/2012 und GCC 4.6 gut zu funktionieren.
    ICC 11 (Intel Compiler 11) hat überraschenderweise Probleme, es gut zu kompilieren.
  • Diese sind für Pre-FMA-Prozessoren. Um Spitzen-FLOPS auf Intel Haswell- und AMD Bulldozer-Prozessoren (und höher) zu erzielen, sind FMA-Anweisungen (Fused Multiply Add) erforderlich. Diese gehen über den Rahmen dieser Benchmark hinaus.

#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");
}

Ausgabe (1 Thread, 10000000 Iterationen) - Kompiliert mit Visual Studio 2010 SP1 - x64 Release:

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

Die Maschine ist ein Core i7 2600K bei 4,4 GHz. Der theoretische SSE-Peak beträgt 4 Flops * 4,4 GHz = 17,6 GFlops . Dieser Code erreicht 17.3 GFlops - nicht schlecht.

Ausgabe (8 Threads, 10000000 Iterationen) - Kompiliert mit Visual Studio 2010 SP1 - x64 Release:

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

Der theoretische SSE-Peak beträgt 4 Flops * 4 Kerne * 4,4 GHz = 70,4 GFlops. Tatsächlich sind es 65,5 GFlops .


Gehen wir noch einen Schritt weiter. 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");
}

Ausgabe (1 Thread, 10000000 Iterationen) - Kompiliert mit Visual Studio 2010 SP1 - x64 Release:

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

Der theoretische AVX-Peak beträgt 8 Flops * 4,4 GHz = 35,2 GFlops . Tatsächlich sind es 33,4 GFlops .

Ausgabe (8 Threads, 10000000 Iterationen) - Kompiliert mit Visual Studio 2010 SP1 - x64 Release:

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

Der theoretische AVX-Peak beträgt 8 Flops * 4 Kerne * 4,4 GHz = 140,8 GFlops. Tatsächlich sind 138,2 GFlops .


Nun zu einigen Erklärungen:

Der leistungskritische Teil sind offensichtlich die 48 Anweisungen innerhalb der inneren Schleife. Sie werden feststellen, dass es in 4 Blöcke mit jeweils 12 Anweisungen unterteilt ist. Jeder dieser 12 Befehlsblöcke ist völlig unabhängig voneinander - und die Ausführung dauert durchschnittlich 6 Zyklen.

Es gibt also 12 Anweisungen und 6 Zyklen zwischen der Ausgabe. Die Multiplikationslatenz beträgt 5 Zyklen, sodass es gerade ausreicht, um Latenzstillstände zu vermeiden.

Der Normalisierungsschritt ist erforderlich, um ein Über- / Unterlaufen der Daten zu verhindern. Dies ist erforderlich, da der Nichtstun-Code die Größe der Daten langsam erhöht / verringert.

Es ist also tatsächlich möglich, es besser zu machen, wenn Sie nur alle Nullen verwenden und den Normalisierungsschritt loswerden. Da ich jedoch den Benchmark zur Messung des Stromverbrauchs und der Temperatur geschrieben habe, musste ich sicherstellen, dass sich die Flops auf "echten" Daten und nicht auf Nullen befanden - da die Ausführungseinheiten möglicherweise eine spezielle Fallbehandlung für Nullen haben, die weniger Strom verbrauchen und produzieren weniger Wärme.


Mehr Ergebnisse:

  • Intel Core i7 920 bei 3,5 GHz
  • Windows 7 Ultimate x64
  • Visual Studio 2010 SP1 - x64-Version

Themen: 1

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

Theoretischer SSE-Peak: 4 Flops * 3,5 GHz = 14,0 GFlops . Tatsächlich sind es 13,3 GFlops .

Themen: 8

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

Theoretischer SSE-Peak: 4 Flops * 4 Kerne * 3,5 GHz = 56,0 GFlops . Tatsächlich sind 51,3 GFlops .

Meine Prozessortemperaturen erreichten beim Multithread-Lauf 76 ° C! Wenn Sie diese ausführen, stellen Sie sicher, dass die Ergebnisse nicht durch CPU-Drosselung beeinflusst werden.


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

Themen: 1

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

Theoretischer SSE-Peak: 4 Flops * 3,2 GHz = 12,8 GFlops . Tatsächlich sind es 12,3 GFlops .

Themen: 8

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

Theoretischer SSE-Peak: 4 Flops * 8 Kerne * 3,2 GHz = 102,4 GFlops . Tatsächlich sind 97,9 GFlops .

Mystisch
quelle
13
Ihre Ergebnisse sind sehr beeindruckend. Ich habe Ihren Code mit g ++ auf meinem älteren System kompiliert, erhalte jedoch nicht annähernd so gute Ergebnisse: 100.000 Iterationen, 1.814s, 5.292 Gflops, sum=0.448883von einem Spitzenwert von 10,68 Gflops oder nur knapp 2,0 Flops pro Zyklus. Scheint add/ mulwerden nicht parallel ausgeführt. Wenn ich Ihren Code ändere und immer mit demselben Register addiere / multipliziere rC, erreicht er plötzlich fast einen Spitzenwert: 0.953s, 10.068 Gflops, sum=0oder 3,8 Flops / Zyklus. Sehr eigenartig.
user1059432
11
Ja, da ich keine Inline-Assembly verwende, ist die Leistung in der Tat sehr empfindlich für den Compiler. Der Code, den ich hier habe, wurde für VC2010 optimiert. Und wenn ich mich richtig erinnere, liefert der Intel Compiler genauso gute Ergebnisse. Wie Sie bemerkt haben, müssen Sie es möglicherweise ein wenig optimieren, damit es gut kompiliert werden kann.
Mysticial
8
Ich kann Ihre Ergebnisse unter Windows 7 mit cl /O2(64-Bit von Windows SDK) bestätigen, und selbst mein Beispiel läuft dort nahe an der Spitze für skalare Operationen (1,9 Flops / Zyklus). Die Compiler-Schleife rollt ab und ordnet neu, aber das ist möglicherweise nicht der Grund, warum Sie sich etwas mehr damit befassen müssen. Drosselung kein Problem Ich bin nett zu meiner CPU und halte die Iterationen bei 100k. :)
user1059432
6
@Mysticial: Es wurde heute auf dem Subreddit r / encoding angezeigt .
Greyfade
2
@ Haylem Es schmilzt entweder oder es hebt ab. Niemals beides. Wenn es genügend Kühlung gibt, wird es Sendezeit bekommen. Ansonsten schmilzt es einfach. :)
Mysticial
33

Es gibt einen Punkt in der Intel-Architektur, den die Leute oft vergessen: Die Dispatch-Ports werden von Int und FP / SIMD gemeinsam genutzt. Dies bedeutet, dass Sie nur eine bestimmte Anzahl von FP / SIMD-Bursts erhalten, bevor die Schleifenlogik Blasen in Ihrem Gleitkomma-Stream erzeugt. Mystical hat mehr Flops aus seinem Code herausgeholt, weil er in seiner abgewickelten Schleife längere Schritte gemacht hat.

Wenn Sie sich die Nehalem / Sandy Bridge-Architektur hier ansehen, http://www.realworldtech.com/page.cfm?ArticleID=RWT091810191937&p=6 , ist ziemlich klar, was passiert.

Im Gegensatz dazu sollte es einfacher sein, mit AMD (Bulldozer) Spitzenleistungen zu erzielen, da die INT- und FP / SIMD-Pipes separate Issue-Ports mit einem eigenen Scheduler haben.

Dies ist nur theoretisch, da ich keinen dieser Prozessoren testen muss.

Patrick Schlüter
quelle
2
Es gibt nur drei Anweisungen des Schleifenoverhead: inc, cmp, und jl. Alle diese Faktoren können zu Port # 5 gehen und nicht stören entweder vektorisiert faddoder fmul. Ich würde eher vermuten, dass der Decoder (manchmal) in die Quere kommt. Es müssen zwischen zwei und drei Anweisungen pro Zyklus aufrechterhalten werden. Ich erinnere mich nicht an die genauen Einschränkungen, aber Befehlslänge, Präfixe und Ausrichtung spielen eine Rolle.
Mackie Messer
cmpund auf jljeden Fall zu Port 5 gehen, incnicht so sicher, da es immer in Gruppe mit den 2 anderen kommt. Aber Sie haben Recht, es ist schwer zu sagen, wo der Engpass liegt, und die Decoder können auch Teil davon sein.
Patrick Schlüter
3
Ich habe ein bisschen mit der Grundschleife herumgespielt: Die Reihenfolge der Anweisungen spielt eine Rolle. Einige Anordnungen dauern 13 Zyklen anstelle der minimalen 5 Zyklen. Zeit, sich die Leistungsereigniszähler anzusehen, denke ich ...
Mackie Messer
16

Zweige können Sie definitiv davon abhalten, die theoretische Spitzenleistung aufrechtzuerhalten. Sehen Sie einen Unterschied, wenn Sie das Schleifen manuell abrollen? Wenn Sie beispielsweise 5 oder 10 Mal so viele Operationen pro Schleifeniteration ausführen:

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
quelle
4
Ich kann mich irren, aber ich glaube, dass g ++ mit -O2 versuchen wird, die Schleife automatisch abzuwickeln (ich denke, es verwendet Duffs Gerät).
Weber
6
Ja, danke, es verbessert sich tatsächlich etwas. Ich bekomme jetzt ungefähr 4,1-4,3 Gflops oder 1,55 Flops pro Zyklus. Und nein, in diesem Beispiel hat -O2 das Abrollen nicht wiederholt.
user1059432
1
Ich glaube, Weaver hat Recht mit dem Abrollen von Schleifen. Ein manuelles Abrollen ist also wahrscheinlich nicht erforderlich
Jim Mcnamara
5
Siehe Baugruppenausgabe oben, es gibt keine Anzeichen für ein Abrollen der Schleife.
user1059432
14
Das automatische Abrollen verbessert sich ebenfalls auf durchschnittlich 4,2 Gflops, erfordert jedoch eine -funroll-loopsOption, die nicht einmal in enthalten ist -O3. Siehe g++ -c -Q -O2 --help=optimizers | grep unroll.
user1059432
7

Mit Intel icc Version 11.1 auf einem 2,4 GHz Intel Core 2 Duo bekomme ich

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 

Das kommt den idealen 9,6 Gflops sehr nahe.

BEARBEITEN:

Hoppla, wenn man sich den Assembler-Code ansieht, scheint es, dass icc nicht nur die Multiplikation vektorisiert, sondern auch die Additionen aus der Schleife gezogen hat. Durch Erzwingen einer strengeren fp-Semantik wird der Code nicht mehr vektorisiert:

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

EDIT2:

Wie gewünscht:

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

Die innere Schleife von Clangs Code sieht folgendermaßen aus:

        .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

EDIT3:

Abschließend zwei Vorschläge: Wenn Sie diese Art des Benchmarking mögen, sollten Sie zunächst die rdtscAnweisung anstelle von verwenden gettimeofday(2). Es ist viel genauer und liefert die Zeit in Zyklen, woran Sie normalerweise sowieso interessiert sind. Für gcc und Freunde können Sie es folgendermaßen definieren:

#include <stdint.h>

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

Zweitens sollten Sie Ihr Benchmark-Programm mehrmals ausführen und nur die beste Leistung verwenden . In modernen Betriebssystemen passieren viele Dinge parallel, die CPU befindet sich möglicherweise in einem Niederfrequenz-Energiesparmodus usw. Wenn Sie das Programm wiederholt ausführen, erhalten Sie ein Ergebnis, das dem Idealfall näher kommt.

Mackie Messer
quelle
2
und wie sieht die zerlegung aus?
Bahbar
1
Interessant, das ist weniger als 1 Flop / Zyklus. Mischt der Compiler die addsd's und mulsd' s oder sind sie in Gruppen wie in meiner Assembly-Ausgabe? Ich bekomme auch nur ungefähr 1 Flop / Zyklus, wenn der Compiler sie mischt (was ich ohne bekomme -march=native). Wie ändert sich die Leistung, wenn Sie add=mul;am Anfang der Funktion eine Zeile hinzufügen addmul(...)?
user1059432
1
@ user1059432: Die addsdund subsdAnweisungen sind in der Tat in der genauen Version gemischt. Ich habe auch Clang 3.0 ausprobiert, es mischt keine Anweisungen und es kommt 2 Flops / Zyklus auf dem Core 2 Duo sehr nahe. Wenn ich denselben Code auf meinem Laptop Core i5 ausführe, macht das Mischen des Codes keinen Unterschied. Ich bekomme in jedem Fall ungefähr 3 Flops / Zyklus.
Mackie Messer
1
@ user1059432: Am Ende geht es darum, den Compiler dazu zu bringen, "aussagekräftigen" Code für einen synthetischen Benchmark zu generieren. Das ist schwieriger als es auf den ersten Blick scheint. (dh icc überlistet Ihren Benchmark) Wenn Sie nur Code mit 4 Flops / Zyklus ausführen möchten, ist es am einfachsten, eine kleine Assembly-Schleife zu schreiben. Viel weniger Kopfschmerz. :-)
Mackie Messer
1
Ok, Sie nähern sich also 2 Flops / Zyklus mit einem Assembler-Code, der dem oben zitierten ähnlich ist? Wie nah an 2? Ich bekomme nur 1.4, das ist also wichtig. Ich glaube nicht, dass Sie 3 Flops / Zyklus auf Ihrem Laptop erhalten, es sei denn, der Compiler führt Optimierungen durch, wie Sie zuvor gesehen haben. Können Sie iccdie Baugruppe überprüfen?
user1059432