C++: Mysteriöserweise enorme Beschleunigung durch das Halten eines Operanden in einem Register

Ich habe versucht, eine Vorstellung von den Auswirkungen eines Arrays im L1-Cache im Vergleich zum Arbeitsspeicher zu bekommen, indem ich eine Routine getaktet habe, die die Elemente eines Arrays mit dem folgenden Code skaliert und summiert (ich bin mir bewusst, dass ich das Ergebnis einfach skalieren sollte durch ‘ a’ am Ende; es geht darum, sowohl eine Multiplikation als auch eine Addition innerhalb der Schleife durchzuführen – bisher hat der Compiler nicht herausgefunden, ‘a’ auszuklammern):

double sum(double a,double* X,int size)
{
    double total = 0.0;
    for(int i = 0;  i < size; ++i)
    {
        total += a*X[i];
    }
    return total;
}

#define KB 1024
int main()
{
    //Approximately half the L1 cache size of my machine
    int operand_size = (32*KB)/(sizeof(double)*2);
    printf("Operand size: %d\n", operand_size);
    double* X = new double[operand_size];
    fill(X,operand_size);

    double seconds = timer();
    double result;
    int n_iterations = 100000;
    for(int i = 0; i < n_iterations; ++i)
    {
        result = sum(3.5,X,operand_size);
        //result += rand();  
    }
    seconds = timer() - seconds; 

    double mflops = 2e-6*double(n_iterations*operand_size)/seconds;
    printf("Vector size %d: mflops=%.1f, result=%.1f\n",operand_size,mflops,result);
    return 0;
}

Beachten Sie, dass die Routinen timer() und fill() der Kürze halber nicht enthalten sind; Die vollständige Quelle finden Sie hier, wenn Sie den Code ausführen möchten:

http://codepad.org/agPWItZS

Nun, hier wird es interessant. Dies ist die Ausgabe:

Operand size: 2048
Vector size 2048: mflops=588.8, result=-67.8

Dies ist eine völlig ungecachte Leistung, trotz der Tatsache, dass alle Elemente von X zwischen Schleifeniterationen im Cache gehalten werden sollten. Betrachten Sie den Assembler-Code, der generiert wurde von:

g++ -O3 -S -fno-asynchronous-unwind-tables register_opt_example.cpp

Ich bemerke eine Kuriosität in der Summenfunktionsschleife:

L55:
    movsd   (%r12,%rax,8), %xmm0
    mulsd   %xmm1, %xmm0
    addsd   -72(%rbp), %xmm0
    movsd   %xmm0, -72(%rbp)
    incq    %rax
    cmpq    $2048, %rax
    jne L55

Die Anleitungen:

    addsd   -72(%rbp), %xmm0
    movsd   %xmm0, -72(%rbp)

zeigen an, dass es den Wert von “total” in sum() auf dem Stack speichert und ihn bei jedem Schleifendurchlauf liest und schreibt. Ich habe die Assembly so geändert, dass dieser Operand in einem Register gespeichert wird:

...
addsd   %xmm0, %xmm3
...

Diese kleine Änderung schafft a riesig Leistungssteigerung:

Operand size: 2048
Vector size 2048: mflops=1958.9, result=-67.8

tl;dr
Meine Frage ist: Warum beschleunigt das Ersetzen eines einzelnen Speicherortzugriffs durch ein Register den Code so sehr, da der einzelne Ort im L1-Cache gespeichert werden sollte? Welche architektonischen Faktoren machen dies möglich? Es scheint sehr seltsam, dass das wiederholte Schreiben einer Stack-Position die Effektivität eines Caches vollständig zerstören würde.

Anhang

Meine gcc-Version ist:

Target: i686-apple-darwin10
Configured with: /var/tmp/gcc/gcc-5646.1~2/src/configure --disable-checking --enable-werror --prefix=/usr --mandir=/share/man --enable-languages=c,objc,c++,obj-c++ --program-transform-name=/^[cg][^.-]*$/s/$/-4.2/ --with-slibdir=/usr/lib --build=i686-apple-darwin10 --with-gxx-include-dir=/include/c++/4.2.1 --program-prefix=i686-apple-darwin10- --host=x86_64-apple-darwin10 --target=i686-apple-darwin10
Thread model: posix
gcc version 4.2.1 (Apple Inc. build 5646) (dot 1)

Meine CPU ist:

Intel Xeon X5650

Es ist wahrscheinlich eine Kombination aus einer längeren Abhängigkeitskette und Load Misprediction*.

Längere Abhängigkeitskette:

Zuerst identifizieren wir die kritischen Abhängigkeitspfade. Dann schauen wir uns die Anweisungslatenzen an, die bereitgestellt werden von: http://www.agner.org/optimize/instruction_tables.pdf (Seite 117)

In der nicht optimierten Version lautet der kritische Abhängigkeitspfad:

• addsd -72(%rbp), %xmm0
• movsd %xmm0, -72(%rbp)

Intern zerfällt es wahrscheinlich in:

• Belastung (2 Zyklen)
• addd (3 Zyklen)
• speichern (3 Zyklen)

Wenn wir uns die optimierte Version ansehen, ist es nur:

• addd (3 Zyklen)

Sie haben also 8 Zyklen gegenüber 3 Zyklen. Fast Faktor 3.

Ich bin mir nicht sicher, wie empfindlich die Nehalem-Prozessorlinie auf Speicher-Lade-Abhängigkeiten reagiert und wie gut sie funktioniert Weiterleitung. Aber es ist vernünftig zu glauben, dass es nicht null ist.

Load-Store-Fehlvorhersage:

Moderne Prozessoren verwenden die Vorhersage auf mehr Arten, als Sie sich vorstellen können. Das bekannteste davon ist wahrscheinlich Branch Prediction. Eine der weniger bekannten ist Load Prediction.

Wenn ein Prozessor eine Last sieht, lädt er sie sofort, bevor alle anstehenden Schreibvorgänge abgeschlossen sind. Es wird davon ausgegangen, dass diese Schreibvorgänge nicht mit den geladenen Werten in Konflikt stehen.

Wenn sich herausstellt, dass ein früherer Schreibvorgang mit einem Ladevorgang kollidiert, muss der Ladevorgang erneut ausgeführt und die Berechnung bis zum Ladepunkt zurückgesetzt werden. (ähnlich wie falsche Vorhersagen von Verzweigungen rückgängig gemacht werden)

Wie es hier relevant ist:

Natürlich können moderne Prozessoren mehrere Iterationen dieser Schleife gleichzeitig ausführen. Der Prozessor versucht also, den Ladevorgang durchzuführen (addsd -72(%rbp), %xmm0) bevor es den Laden beendet (movsd %xmm0, -72(%rbp)) aus der vorherigen Iteration.

Das Ergebnis? Der vorherige Speicher kollidiert mit der Last – daher eine Fehlvorhersage und ein Rollback.

_{*Beachten Sie, dass ich mir beim Namen “Load Prediction” nicht sicher bin. Ich habe nur in den Intel-Dokumenten darüber gelesen und sie schienen ihm keinen Namen zu geben.}

Ich würde vermuten, dass das Problem nicht im Cache-/Speicherzugriff, sondern im Prozessor (Ausführung Ihres Codes) liegt. Hier gibt es mehrere sichtbare Engpässe.

Die Leistungszahlen hier basierten auf den von mir verwendeten Boxen (entweder Sandybridge oder Westmere)

Die Spitzenleistung für skalare Mathematik beträgt 2,7 GHz x2 FLOPS/Clock x2, da der Prozessor gleichzeitig addieren und multiplizieren kann. Die theoretische Effizienz des Codes beträgt 0,6/(2,7*2) = 11 %

Benötigte Bandbreite: 2 Doubles pro (+) und (x) -> 4Bytes/Flop 4 Bytes * 5,4GFLOPS = 21,6GB/s

Wenn Sie wissen, dass es kürzlich gelesen wurde, ist es wahrscheinlich in L1 (89 GB/s), L2 (42 GB/s) oder L3 (24 GB/s), sodass wir Cache-B/W ausschließen können

Das Speicher-Subsystem beträgt 18,9 GB/s, sodass selbst im Hauptspeicher die Spitzenleistung bei 18,9/21,6 GB/s = 87,5 % liegen sollte.

• Möglicherweise möchten Sie Anfragen so früh wie möglich bündeln (durch Entrollen).

Auch bei spekulativer Ausführung ist tot += a *X[i] Die Hinzufügungen werden serialisiert, da tot(n) ausgewertet werden müssen, bevor tot(n+1) gestartet werden kann

Erste Abrollschlaufe
bewege i um 8er und tue

{//your func
    for( int i = 0; i < size; i += 8 ){
        tot += a * X[i];
        tot += a * X[i+1];
        ...
        tot += a * X[i+7];
    }
    return tot
}

Verwenden Sie mehrere Akkumulatoren
Dadurch werden Abhängigkeiten aufgehoben und ein Blockieren der Additionspipeline vermieden

{//your func//
    int tot,tot2,tot3,tot4;
    tot = tot2 = tot3 = tot4 = 0
    for( int i = 0; i < size; i += 8 ) 
        tot  += a * X[i];
        tot2 += a * X[i+1];
        tot3 += a * X[i+2];
        tot4 += a * X[i+3];
        tot  += a * X[i+4];
        tot2 += a * X[i+5];
        tot3 += a * X[i+6];
        tot4 += a * X[i+7];
    }
    return tot + tot2 + tot3 + tot4;
}

UPDATE Nachdem ich dies auf einer SandyBridge-Box ausgeführt habe, habe ich Zugriff auf: (2,7 GHz SandyBridge mit -O2 -march=native -mtune=native

Ursprünglicher Code:

Operand size: 2048  
Vector size 2048: mflops=2206.2, result=61.8  
2.206 / 5.4 = 40.8%

Verbesserter Code:

Operand size: 2048  
Vector size 2048: mflops=5313.7, result=61.8  
5.3137 / 5.4 = 98.4%  

Ich kann das nicht wirklich reproduzieren, weil mein Compiler (gcc 4.7.2) hält total in einem Register.

Ich vermute, dass der Hauptgrund für die Langsamkeit nicht mit dem L1-Cache zu tun hat, sondern eher in der Datenabhängigkeit zwischen den Speichern liegt

movsd   %xmm0, -72(%rbp)

und die Belastung der nachfolgenden Iteration:

addsd   -72(%rbp), %xmm0