wake-up-neo.com

Deoptimierung eines Programms für die Pipeline in CPUs der Intel Sandybridge-Familie

Ich habe mir seit einer Woche den Kopf zerbrochen, um diese Aufgabe zu erfüllen, und ich hoffe, dass mich jemand hier auf den richtigen Weg führen kann. Lassen Sie mich mit den Anweisungen des Lehrers beginnen:

Ihre Aufgabe ist das Gegenteil von unserer ersten Laboraufgabe, bei der es darum ging, ein Primzahlprogramm zu optimieren. Ihr Zweck bei dieser Aufgabe ist es, das Programm zu pessimieren, d. H. Es langsamer laufen zu lassen. Beides sind CPU-intensive Programme. Die Ausführung auf unseren Labor-PCs dauert einige Sekunden. Sie dürfen den Algorithmus nicht ändern.

Verwenden Sie Ihr Wissen über die Funktionsweise der Intel i7-Pipeline, um das Programm zu deoptimieren. Stellen Sie sich vor, wie Sie Anweisungspfade neu anordnen können, um WAR-, RAW- und andere Gefahren einzuführen. Überlegen Sie, wie Sie die Effektivität des Caches minimieren können. Seien Sie teuflisch inkompetent.

Der Auftrag gab eine Auswahl von Whetstone- oder Monte-Carlo-Programmen. Die Kommentare zur Cache-Effektivität gelten meist nur für Whetstone, aber ich habe mich für das Monte-Carlo-Simulationsprogramm entschieden:

// Un-modified baseline for pessimization, as given in the assignment
#include <algorithm>    // Needed for the "max" function
#include <cmath>
#include <iostream>

// A simple implementation of the Box-Muller algorithm, used to generate
// gaussian random numbers - necessary for the Monte Carlo method below
// Note that C++11 actually provides std::normal_distribution<> in 
// the <random> library, which can be used instead of this function
double gaussian_box_muller() {
  double x = 0.0;
  double y = 0.0;
  double euclid_sq = 0.0;

  // Continue generating two uniform random variables
  // until the square of their "euclidean distance" 
  // is less than unity
  do {
    x = 2.0 * Rand() / static_cast<double>(Rand_MAX)-1;
    y = 2.0 * Rand() / static_cast<double>(Rand_MAX)-1;
    euclid_sq = x*x + y*y;
  } while (euclid_sq >= 1.0);

  return x*sqrt(-2*log(euclid_sq)/euclid_sq);
}

// Pricing a European Vanilla call option with a Monte Carlo method
double monte_carlo_call_price(const int& num_sims, const double& S, const double& K, const double& r, const double& v, const double& T) {
  double S_adjust = S * exp(T*(r-0.5*v*v));
  double S_cur = 0.0;
  double payoff_sum = 0.0;

  for (int i=0; i<num_sims; i++) {
    double gauss_bm = gaussian_box_muller();
    S_cur = S_adjust * exp(sqrt(v*v*T)*gauss_bm);
    payoff_sum += std::max(S_cur - K, 0.0);
  }

  return (payoff_sum / static_cast<double>(num_sims)) * exp(-r*T);
}

// Pricing a European Vanilla put option with a Monte Carlo method
double monte_carlo_put_price(const int& num_sims, const double& S, const double& K, const double& r, const double& v, const double& T) {
  double S_adjust = S * exp(T*(r-0.5*v*v));
  double S_cur = 0.0;
  double payoff_sum = 0.0;

  for (int i=0; i<num_sims; i++) {
    double gauss_bm = gaussian_box_muller();
    S_cur = S_adjust * exp(sqrt(v*v*T)*gauss_bm);
    payoff_sum += std::max(K - S_cur, 0.0);
  }

  return (payoff_sum / static_cast<double>(num_sims)) * exp(-r*T);
}

int main(int argc, char **argv) {
  // First we create the parameter list                                                                               
  int num_sims = 10000000;   // Number of simulated asset paths                                                       
  double S = 100.0;  // Option price                                                                                  
  double K = 100.0;  // Strike price                                                                                  
  double r = 0.05;   // Risk-free rate (5%)                                                                           
  double v = 0.2;    // Volatility of the underlying (20%)                                                            
  double T = 1.0;    // One year until expiry                                                                         

  // Then we calculate the call/put values via Monte Carlo                                                                          
  double call = monte_carlo_call_price(num_sims, S, K, r, v, T);
  double put = monte_carlo_put_price(num_sims, S, K, r, v, T);

  // Finally we output the parameters and prices                                                                      
  std::cout << "Number of Paths: " << num_sims << std::endl;
  std::cout << "Underlying:      " << S << std::endl;
  std::cout << "Strike:          " << K << std::endl;
  std::cout << "Risk-Free Rate:  " << r << std::endl;
  std::cout << "Volatility:      " << v << std::endl;
  std::cout << "Maturity:        " << T << std::endl;

  std::cout << "Call Price:      " << call << std::endl;
  std::cout << "Put Price:       " << put << std::endl;

  return 0;
}

Die Änderungen, die ich vorgenommen habe, schienen die Laufzeit des Codes um eine Sekunde zu verlängern, aber ich bin nicht ganz sicher, was ich ändern kann, um die Pipeline anzuhalten, ohne Code hinzuzufügen. Ein Punkt in die richtige Richtung wäre genial, ich freue mich über jede Antwort.


Update: der Professor, der diesen Auftrag erteilt hat, hat einige Details veröffentlicht

Die Highlights sind:

  • Es ist ein Architekturkurs im zweiten Semester an einem Community College (nach dem Lehrbuch von Hennessy und Patterson).
  • die Laborcomputer verfügen über Haswell-CPUs
  • Die Schüler wurden mit der Anweisung CPUID und dem Ermitteln der Cache-Größe sowie mit der Anweisung CLFLUSH vertraut gemacht.
  • alle Compiler-Optionen sind zulässig, ebenso wie Inline-Asm.
  • Das Schreiben eines eigenen Quadratwurzel-Algorithmus wurde als außerhalb des Blassen angesagt

Cowmooguns Kommentare zum Meta-Thread deuten darauf hin, dass es war nicht klar, dass Compiler-Optimierungen ein Teil davon sein könnten, und nahmen an, dass -O0 , und dass eine Steigerung der Laufzeit um 17% angemessen war.

Es klingt also so, als ob das Ziel der Aufgabe darin bestand, die Schüler dazu zu bringen, die vorhandene Arbeit neu zu ordnen, um die Parallelität auf Unterrichtsebene oder ähnliches zu verringern. Es ist jedoch keine schlechte Sache, dass sich die Leute vertieft und mehr gelernt haben.


Denken Sie daran, dass dies eine Frage der Computerarchitektur ist, nicht die Frage, wie C++ im Allgemeinen langsam gemacht werden kann.

310
Cowmoogun

Wichtige Hintergrundinformationen: Agner Nebels Mikroarchitektur pdf und wahrscheinlich auch Ulrich Dreppers Was jeder Programmierer über Speicher wissen sollte . Siehe auch die anderen Links im x86 -Tag-Wiki, insbesondere die Optimierungshandbücher von Intel, und David Kanters Analyse der Haswell-Mikroarchitektur mit Diagrammen .

Sehr coole Aufgabe; viel besser als die, die ich bisher gesehen habe, als Schüler gebeten wurden, Code für gcc -O0 zu optimieren, um eine Reihe von Tricks zu lernen, die in echtem Code keine Rolle spielen . In diesem Fall werden Sie gebeten, sich mit der CPU-Pipeline vertraut zu machen und diese zu verwenden, um Ihre Bemühungen zur Deoptimierung zu steuern, und nicht nur um blinde Vermutungen anzustellen. Am meisten Spaß macht es, jede Pessimisierung mit "teuflischer Inkompetenz" zu rechtfertigen, nicht mit vorsätzlicher Bosheit.


Probleme mit dem Zuweisungswortlaut und dem Code:

Die uarch-spezifischen Optionen für diesen Code sind begrenzt. Es werden keine Arrays verwendet, und ein Großteil der Kosten entfällt auf Aufrufe der Bibliotheksfunktionen exp/log. Es gibt keinen offensichtlichen Weg, mehr oder weniger Parallelität auf Befehlsebene zu erreichen, und die durch Schleifen übertragene Abhängigkeitskette ist sehr kurz.

Ich würde gerne eine Antwort sehen, die versucht, eine Verlangsamung der Neuanordnung der Ausdrücke zu erreichen, um die Abhängigkeiten zu ändern und [~ # ~] ilp [~ # ~] nur aus Abhängigkeiten (Gefahren). Ich habe es nicht versucht.

CPUs der Intel Sandybridge-Familie sind aggressive Out-of-Order-Designs, die eine Menge Transistoren und Leistung aufwenden, um Parallelität zu finden und Gefahren (Abhängigkeiten) zu vermeiden, die eine klassische RISC-Pipeline in der richtigen Reihenfolge stören . Normalerweise sind RAW-Abhängigkeiten, bei denen der Durchsatz durch die Latenz begrenzt wird, die einzigen herkömmlichen Risiken, die ihn verlangsamen.

WAR- und WAW-Gefahren für Register sind dank der Umbenennung von Registern so gut wie kein Problem. (Mit Ausnahme von popcnt/lzcnt/tzcnt, deren Ziel eine falsche Abhängigkeit von Intel-CPUs aufweist , obwohl dies der Fall ist Nur Schreiben (dh WAW wird als RAW-Gefahr behandelt + Schreiben). Bei der Speicherreihenfolge verwenden moderne CPUs Speicherwarteschlangen, um das Festschreiben im Cache bis zur Stilllegung zu verzögern und gleichzeitig die Gefahren von WAR und WAW zu vermeiden.

Warum benötigt mulss bei Haswell im Gegensatz zu Agners Anweisungstabellen nur 3 Zyklen? enthält mehr Informationen zum Umbenennen von Registern und zum Ausblenden der FMA-Latenz in einer FP -Punkt-Produktschleife.


Der Markenname "i7" wurde mit Nehalem (Nachfolger von Core2) eingeführt, und einige Intel-Handbücher sagen sogar "Core i7", wenn sie Nehalem zu bedeuten scheinen, aber das "i7" -Markenzeichen wurde beibehalten für Sandybridge und spätere Mikroarchitekturen. SnB ist, wenn sich die P6-Familie zu einer neuen Art entwickelt hat, der SnB-Familie . In vielerlei Hinsicht hat Nehalem mehr mit Pentium III zu tun als mit Sandybridge (z. B. Register-Read-Stalls und ROB-Read-Stalls treten bei SnB nicht auf, da eine physische Registerdatei verwendet wird. Außerdem ein UOP-Cache und ein anderer interner Cache uop format). Der Begriff "i7-Architektur" ist nicht sinnvoll, da es wenig sinnvoll ist, die SnB-Familie mit Nehalem, aber nicht mit Core2 zu gruppieren. (Nehalem hat jedoch die gemeinsam genutzte inklusive L3-Cache-Architektur zum Verbinden mehrerer Kerne eingeführt. Außerdem sind GPUs integriert. Daher ist die Benennung auf Chip-Ebene sinnvoller.)


Zusammenfassung der guten Ideen, die teuflische Inkompetenz rechtfertigen kann

Es ist unwahrscheinlich, dass selbst die teuflischen Inkompetenten offensichtlich nutzlose Arbeit oder eine Endlosschleife hinzufügen, und ein Durcheinander mit C++/Boost-Klassen liegt außerhalb des Aufgabenbereichs.

  • Multithread mit einem einzelnen shared std::atomic<uint64_t> - Schleifenzähler, sodass die richtige Gesamtzahl der Iterationen auftritt. Atomic uint64_t ist besonders schlecht mit -m32 -march=i586. Lassen Sie Bonuspunkte falsch ausrichten und überschreiten Sie eine Seitengrenze mit ungleichmäßiger Aufteilung (nicht 4: 4).
  • Falsches Teilen für einige andere nicht-atomare Variablen -> Löscht Pipeline-Fehler der Speicherreihenfolge sowie zusätzliche Cache-Fehler.
  • Anstatt - Für FP Variablen zu verwenden, XOR das High-Byte mit 0x80, um das Vorzeichenbit umzudrehen, was Speicherweiterleitungsstillstände verursacht.
  • Zeit jede Iteration unabhängig, mit etwas noch schwerer als RDTSC. z.B. CPUID/RDTSC oder eine Zeitfunktion, die einen Systemaufruf ausführt. Serialisierungsanweisungen sind von Natur aus pipelineunfreundlich.
  • Ändern Sie Multiplikationen durch Konstanten in Divisionen durch ihren Kehrwert ("zur Erleichterung des Lesens"). div ist langsam und nicht vollständig pipelined.
  • Vektorisieren Sie die Multiplikation/Sqrt mit AVX (SIMD), verwenden Sie jedoch nicht vzeroupper, bevor Sie die Funktionen der skalaren Mathematikbibliothek exp() und log() aufrufen, wodurch AVX < -> SSE Transition Stalls.
  • Speichern Sie die RNG-Ausgabe in einer verknüpften Liste oder in Arrays, die Sie nicht in der richtigen Reihenfolge durchlaufen. Das gleiche gilt für das Ergebnis jeder Iteration und für die Summe am Ende.

Ebenfalls in dieser Antwort behandelt, aber von der Zusammenfassung ausgeschlossen: Vorschläge, die auf einer nicht über Pipelines verbundenen CPU genauso langsam wären oder die auch bei teuflischer Inkompetenz nicht zu rechtfertigen scheinen. z.B. viele gimp-the-compiler ideen, die offensichtlich andere/schlechtere asm produzieren.


Multithread schlecht

Verwenden Sie OpenMP möglicherweise für Multi-Thread-Schleifen mit sehr wenigen Iterationen, mit weitaus mehr Overhead als Geschwindigkeitsgewinn. Ihr Monte-Carlo-Code verfügt jedoch über genügend Parallelität, um tatsächlich eine Beschleunigung zu erzielen. wenn es uns gelingt, jede Iteration langsam zu machen. (Jeder Thread berechnet einen Teil payoff_sum, Der am Ende hinzugefügt wird). #omp parallel In dieser Schleife wäre wahrscheinlich eine Optimierung, keine Pessimisierung.

Multi-Thread, aber erzwinge, dass beide Threads den gleichen Schleifenzähler verwenden (mit Inkrementen von atomic, damit die Gesamtzahl der Iterationen korrekt ist). Dies scheint teuflisch logisch. Dies bedeutet, dass eine Variable static als Schleifenzähler verwendet wird. Dies rechtfertigt die Verwendung von atomic für Schleifenzähler und erstellt ein tatsächliches Ping-Ponging für die Cache-Zeile (solange die Threads nicht auf demselben physischen Kern ausgeführt werden) mit Hyperthreading, das ist möglicherweise nicht als langsam). Wie auch immer, dies ist viel langsamer als der nicht umstrittene Fall für lock inc. Und lock cmpxchg8b, Um einen konkurrierenden uint64_t Auf einem 32-Bit-System atomar zu erhöhen, muss in einer Schleife erneut versucht werden, anstatt dass die Hardware ein atomares inc arbitriert.

Erstellen Sie auch false sharing, wobei mehrere Threads ihre privaten Daten (z. B. den RNG-Status) in verschiedenen Bytes derselben Cache-Zeile speichern. (Intel-Tutorial dazu, einschließlich der Leistungsindikatoren zum Ansehen) . Das hat einen mikroarchitekturspezifischen Aspekt: Intel-CPUs spekulieren über falsche Speicherreihenfolge nicht und es gibt einen Speicher -Ordnen Sie ein maschinenleeres Leistungsereignis an, um dies zumindest auf P4 zu erkennen. Die Strafe für Haswell ist möglicherweise nicht so hoch. Wie dieser Link verdeutlicht, geht ein lock ed-Befehl davon aus, dass dies passieren wird, um Fehlspekulationen zu vermeiden. Ein normaler Ladevorgang spekuliert, dass andere Kerne eine Cache-Zeile zwischen der Ausführung des Ladevorgangs und der Beendigung in Programmreihenfolge ( nicht ungültig machen, es sei denn, Sie verwenden pause . Echtes Teilen ohne lock Anweisungen ist normalerweise ein Fehler. Es wäre interessant, einen nichtatomaren gemeinsamen Schleifenzähler mit dem atomaren Fall zu vergleichen. Wenn Sie wirklich pessimisieren möchten, behalten Sie den Zähler für gemeinsam genutzte Atomschleifen bei und verursachen Sie eine falsche gemeinsame Nutzung in derselben oder einer anderen Cache-Zeile für eine andere Variable.


Zufällige uarchenspezifische Ideen:

Wenn Sie alle unvorhersehbaren Zweige einführen können, wird der Code dadurch erheblich pessimiert. Moderne x86-CPUs haben ziemlich lange Pipelines, so dass eine Fehleinschätzung ~ 15 Zyklen kostet (wenn sie über den UOP-Cache ausgeführt wird).


Abhängigkeitsketten:

Ich denke, dies war einer der beabsichtigten Teile des Auftrags.

Beeinträchtigen Sie die Fähigkeit der CPU, die Parallelität auf Befehlsebene auszunutzen, indem Sie eine Operationsreihenfolge mit einer langen Abhängigkeitskette anstelle mehrerer kurzer Abhängigkeitsketten auswählen. Compiler dürfen die Reihenfolge der Operationen für FP - Berechnungen nur ändern, wenn Sie -ffast-math Verwenden, da dies die Ergebnisse ändern kann (siehe unten).

Erhöhen Sie die Länge einer durch Schleifen übertragenen Abhängigkeitskette, um diese Funktion effektiv zu nutzen. Nichts ist so offensichtlich: Die geschriebenen Schleifen haben sehr kurze, durch Schleifen übertragene Abhängigkeitsketten: nur ein FP add. (3 Zyklen). Bei mehreren Iterationen können die Berechnungen gleichzeitig ausgeführt werden, da sie weit vor dem payoff_sum += Am Ende der vorherigen Iteration beginnen können. (log() und exp benötigen viele Anweisungen, aber nicht viel mehr als Haswells Fenster für die Suche nach Parallelität: ROB size = 192 Fused-Domain-Uops , und Scheduler-Größe = 60 nicht verschmolzene Domänen-Uops . Sobald die Ausführung der aktuellen Iteration weit genug fortgeschritten ist, um Platz für Anweisungen der nächsten Iteration zu schaffen, stellen alle Teile davon ihre Eingaben bereit (d. h Eine unabhängige/separate Dep-Kette kann mit der Ausführung beginnen, wenn ältere Befehle die Ausführungseinheiten frei lassen (z. B. weil sie aufgrund der Latenz und nicht aufgrund des Durchsatzes einen Engpass aufweisen).

Der RNG-Zustand wird mit ziemlicher Sicherheit eine längere schleifengetragene Abhängigkeitskette sein als der addps.


Verwenden Sie langsamere/mehr FP Operationen (insb. Mehr Division):

Teilen Sie durch 2,0, anstatt mit 0,5 zu multiplizieren, und so weiter. FP multiply ist in Intel-Designs stark ausgefeilt und hat einen Durchsatz pro 0,5 c bei Haswell und höher. FP divsd/divpd ist nur teilweise pipelined. (Obwohl Skylake einen beeindruckenden Durchsatz von divpd xmm Pro 4 c hat, mit einer Latenz von 13 bis 14 c, im Gegensatz zu Nehalem (7 bis 22 c), das überhaupt nicht per Pipeline verbunden ist).

Das do { ...; euclid_sq = x*x + y*y; } while (euclid_sq >= 1.0); prüft eindeutig eine Entfernung, so dass es eindeutig angemessen wäre, es sqrt() zuzuweisen. : P (sqrt ist sogar langsamer als div).

Wie @Paul Clayton vorschlägt, kann das Umschreiben von Ausdrücken mit assoziativen/distributiven Entsprechungen mehr Arbeit verursachen (sofern Sie nicht -ffast-math Verwenden, um dem Compiler eine Neuoptimierung zu ermöglichen). (exp(T*(r-0.5*v*v)) Könnte zu exp(T*r - T*v*v/2.0) werden. Beachten Sie, dass, während Mathe für reelle Zahlen assoziativ ist, Gleitkomma-Mathe nicht ist, auch ohne Berücksichtigung von Überlauf/NaN (weshalb) -ffast-math Ist nicht standardmäßig aktiviert). Siehe Pauls Kommentar für einen sehr haarigen Vorschlag pow().

Wenn Sie die Berechnungen auf sehr kleine Zahlen verkleinern können, benötigen FP mathematische Operationen ~ 120 zusätzliche Zyklen, um den Mikrocode abzufangen, wenn eine Operation mit zwei normalen Zahlen eine Denormalität ergibt. Die genauen Zahlen und Details finden Sie im Mikroarchitektur-PDF von Agner Fog. Dies ist unwahrscheinlich, da Sie viele Multiplikationen haben, sodass der Skalierungsfaktor quadriert und bis zu 0,0 unterschritten wird. Ich sehe keine Möglichkeit, die notwendige Skalierung mit Inkompetenz (auch teuflisch), nur vorsätzlicher Bosheit, zu rechtfertigen.


Wenn Sie Intrinsics verwenden können (<immintrin.h>)

Verwenden Sie movnti, um Ihre Daten aus dem Cache zu entfernen . Teuflisch: Es ist neu und schwach geordnet, also sollte es die CPU schneller laufen lassen, oder? Oder sehen Sie sich diese verknüpfte Frage für einen Fall an, bei dem die Gefahr bestand, dass jemand genau dies tut (für verstreute Schriften, bei denen nur einige der Stellen heiß waren). clflush ist ohne Bosheit wahrscheinlich unmöglich.

Verwenden Sie zwischen FP mathematischen Operationen ganzzahlige Shuffles, um Umgehungsverzögerungen zu verursachen.

Mischen von SSE - und AVX-Befehlen ohne ordnungsgemäße Verwendung von vzeroupper führt zu großen Verzögerungen vor Skylake (und a unterschiedliche Strafe in Skylake ). Auch ohne dies kann das Vektorisieren schlechter sein als das Skalieren (mehr Zyklen für das Mischen von Daten in/aus Vektoren als für das Speichern durch Ausführen der Add/Sub/Mul/Div/Sqrt-Operationen für 4 Monte-Carlo-Iterationen auf einmal mit 256 b Vektoren). . Add/Sub/Mul-Ausführungseinheiten sind vollständig pipelined und in voller Breite, aber Div und Sqrt sind auf 256b-Vektoren nicht so schnell wie auf 128b-Vektoren (oder Skalaren), sodass die Beschleunigung für double nicht dramatisch ist. .

exp() und log() haben keine Hardwareunterstützung, sodass für diesen Teil Vektorelemente zurück in den Skalar extrahiert und die Bibliotheksfunktion separat aufgerufen werden müssten. Anschließend werden die Ergebnisse wieder in einen Vektor gemischt. libm ist normalerweise so kompiliert, dass nur SSE2 verwendet wird. Daher werden die Legacy-SSE-Codierungen skalarer mathematischer Anweisungen verwendet. Wenn Ihr Code 256b-Vektoren verwendet und exp aufruft, ohne zuerst ein vzeroupper auszuführen, bleiben Sie stehen. Nach der Rückkehr wird eine AVX-128-Anweisung wie vmovsd zum Einrichten des nächsten Vektorelements als Argument für exp ebenfalls angehalten. Und dann wird exp() wieder angehalten, wenn eine Anweisung SSE ausgeführt wird. Genau das ist in dieser Frage passiert und hat zu einer 10-fachen Verlangsamung geführt. (Danke @ZBoson).

Siehe auch Nathan Kurzs Experimente mit Intels math lib vs. glibc für diesen Code . Zukünftige glibc werden mit vektorisierten Implementierungen von exp() und so weiter kommen.


Bei Ausrichtung auf Pre-IvB oder esp. Nehalem, versuchen Sie, gcc zu veranlassen, Teilregister-Stalls mit 16-Bit- oder 8-Bit-Operationen gefolgt von 32-Bit- oder 64-Bit-Operationen zu verursachen. In den meisten Fällen verwendet gcc nach einer 8- oder 16-Bit-Operation movzx. In diesem Fall ändert gcc ah und liest dann ax


Mit (inline) asm:

Mit (inline) asm können Sie den UOP-Cache auflösen: Ein 32B-Codeblock, der nicht in drei 6UOP-Cache-Zeilen passt, erzwingt einen Wechsel vom UOP-Cache zu den Decodern. Ein inkompetentes ALIGN, das viele Einzelbyte-Zeichen nop anstelle einiger langer Zeichen nop auf einem Verzweigungsziel in der inneren Schleife verwendet, kann den Trick ausführen. Oder platzieren Sie den Ausrichtungsabstand nach dem Etikett und nicht vor dem Etikett. : P Dies ist nur dann von Bedeutung, wenn das Frontend einen Engpass darstellt. Dies ist jedoch nicht der Fall, wenn es uns gelungen ist, den Rest des Codes zu pessimieren.

Verwenden Sie selbstmodifizierenden Code, um das Löschen von Pipelines auszulösen (auch bekannt als Machine-Nukes).

LCP blockiert von 16-Bit-Befehlen, deren Direktzugriff zu groß ist, um in 8-Bit-Befehle zu passen. Der UOP-Cache bei SnB und höher bedeutet, dass Sie die Entschlüsselungsstrafe nur einmal bezahlen. Auf Nehalem (dem ersten i7) funktioniert es möglicherweise für eine Schleife, die nicht in den 28-UOP-Schleifenpuffer passt. gcc erzeugt manchmal solche Anweisungen, auch mit -mtune=intel und wenn es eine 32-Bit-Anweisung hätte verwenden können.


Eine gebräuchliche Sprache für das Timing ist CPUID (zum Serialisieren) und dann RDTSC . Führe jede Iteration einzeln mit einem CPUID/RDTSC durch, um sicherzustellen, dass das RDTSC nicht mit früheren Befehlen neu angeordnet wird, was eine - Menge verlangsamt . (Im wirklichen Leben besteht der kluge Weg zur Zeit darin, alle Iterationen zu timen, anstatt sie einzeln zu timen und zu addieren).


Verursacht viele Cache-Ausfälle und andere Speicherverlangsamungen

Verwenden Sie für einige Ihrer Variablen einen union { double d; char a[8]; }. Verursacht einen Speicherweiterleitungsstillstand Durchführen eines Narrow-Stores (oder Read-Modify-Write) auf nur eines der Bytes. (Dieser Wiki-Artikel befasst sich auch mit vielen anderen Mikroarchitekturen für Lade-/Speicherwarteschlangen). z.B. Kippen Sie das Vorzeichen eines double mit XOR 0x80 nur auf dem oberen Byte anstelle eines - - Operators. Der teuflisch inkompetente Entwickler hat möglicherweise gehört, dass FP langsamer als eine Ganzzahl ist, und versucht daher, mit Ganzzahloperationen so viel wie möglich zu tun. (Ein sehr guter Compiler, der auf FP math in SSE -Registern abzielt, kann dies möglicherweise zu einem xorps mit einer Konstanten in einem anderen xmm-Register kompilieren. Dies ist jedoch nicht der einzige Weg. ' Für x87 ist es schrecklich, wenn der Compiler erkennt, dass er den Wert negiert und die nächste Addition durch eine Subtraktion ersetzt.)


Verwenden Sie volatile, wenn Sie mit -O3 Kompilieren und nicht mit std::atomic, Um den Compiler zu zwingen, tatsächlich überall zu speichern/neu zu laden. Globale Variablen (anstelle von lokalen Variablen) erzwingen auch einige Speicher/Neuladevorgänge, aber die schwache Reihenfolge des C++ - Speichermodells erfordert nicht, dass der Compiler ständig in den Speicher geladen wird.

Ersetzen Sie lokale Variablen durch Mitglieder einer großen Struktur, damit Sie das Speicherlayout steuern können.

Verwenden Sie Arrays in der Struktur zum Auffüllen (und Speichern von Zufallszahlen, um deren Existenz zu begründen).

Wählen Sie Ihr Speicherlayout so, dass alles in einer anderen Zeile im selben "Set" im L1-Cache abläuft . Es ist nur eine 8-Wege-Assoziation, d. H. Jeder Satz hat 8 "Wege". Cachezeilen sind 64B.

Noch besser: Setzen Sie die Dinge genau 4096B auseinander, da Ladevorgänge eine falsche Abhängigkeit von Speichern auf verschiedenen Seiten aufweisen, jedoch mit demselben Versatz innerhalb einer Seite. Aggressive, nicht in der Reihenfolge befindliche CPUs verwenden die Speicherdisambiguierung , um herauszufinden, wann Ladevorgänge und Speicher neu angeordnet werden können, ohne die Ergebnisse zu ändern . Die Implementierung von Intel verfügt über False-Positives, die verhindern, dass Ladevorgänge vorzeitig gestartet werden . Wahrscheinlich prüfen sie nur Bits unterhalb des Seitenversatzes, sodass die Prüfung beginnen kann, bevor der TLB die hohen Bits von einer virtuellen Seite in eine physische Seite übersetzt hat. Siehe neben Agners Leitfaden auch eine Antwort von Stephen Canon sowie einen Abschnitt am Ende von @Krazy Glews Antwort auf dieselbe Frage. (Andy Glew war einer der Architekten von Intels ursprünglicher P6-Mikroarchitektur.)

Mit __attribute__((packed)) können Sie Variablen so ausrichten, dass sie sich über die Cache-Zeile oder sogar über Seitengrenzen erstrecken. (Eine Ladung von einem double benötigt also Daten aus zwei Cache-Zeilen). Falsch ausgerichtete Lasten haben in keinem Intel i7-Uarch einen Nachteil, außer beim Überqueren von Cache- und Seitenzeilen. Cache-Zeilensplits benötigen noch zusätzliche Zyklen . Skylake reduziert die Strafe für das Laden aufgeteilter Seiten drastisch von 100 auf 5 Zyklen. (Abschnitt 2.1.3) . Vielleicht im Zusammenhang mit der Möglichkeit, zwei Seitenläufe parallel durchzuführen.

Ein Seitenumbruch auf einem atomic<uint64_t> Sollte ungefähr der schlimmste Fall sein, esp. wenn es 5 Bytes auf einer Seite und 3 Bytes auf der anderen Seite sind oder etwas anderes als 4: 4. Sogar Teilungen in der Mitte sind effizienter für Cache-Zeilen-Teilungen mit 16B-Vektoren auf einigen Uarches (IIRC). Setzen Sie alles in ein alignas(4096) struct __attribute((packed)) (natürlich um Platz zu sparen), einschließlich eines Arrays zur Speicherung der RNG-Ergebnisse. Erreichen Sie die Fehlausrichtung, indem Sie uint8_t Oder uint16_t Für etwas vor dem Zähler verwenden.

Wenn Sie den Compiler dazu bringen können, indizierte Adressierungsmodi zu verwenden, besiegt dies uop micro-fusion . Verwenden Sie möglicherweise #define, Um einfache skalare Variablen durch my_data[constant] Zu ersetzen.

Wenn Sie eine zusätzliche Indirektionsebene einführen können, sodass das Laden/Speichern von Adressen nicht frühzeitig bekannt ist, kann dies zu einer weiteren Pessimisierung führen.


Arrays in nicht zusammenhängender Reihenfolge durchlaufen

Ich denke, wir können uns eine inkompetente Begründung für die Einführung eines Arrays einfallen lassen: Damit können wir die Zufallszahlengenerierung von der Zufallszahlenverwendung trennen. Die Ergebnisse jeder Iteration könnten auch in einem Array gespeichert und später summiert werden (mit teuflischer Inkompetenz).

Für "maximale Zufälligkeit" könnte ein Thread über das Zufallsarray laufen, in das neue Zufallszahlen geschrieben werden. Der Thread, der die Zufallszahlen verbraucht, könnte einen Zufallsindex erzeugen, aus dem eine Zufallszahl geladen werden kann. (Hier gibt es einige Neuerungen, aber es ist mikroarchitektonisch hilfreich, dass Ladeadressen frühzeitig erkannt werden, damit eine mögliche Latenz beim Laden behoben werden kann, bevor die geladenen Daten benötigt werden.) Wenn ein Reader und Writer auf verschiedenen Kernen installiert ist, kann dies zu Speicherfehlern führen -speculation-Pipeline wird gelöscht (wie bereits für den Fall der falschen Freigabe erläutert).

Um eine maximale Pessimisierung zu erzielen, durchlaufen Sie Ihr Array mit einer Schrittweite von 4096 Bytes (d. H. 512 Doubles). z.B.

for (int i=0 ; i<512; i++)
    for (int j=i ; j<UPPER_BOUND ; j+=512)
        monte_carlo_step(rng_array[j]);

Das Zugriffsmuster ist also 0, 4096, 8192, ...,
8, 4104, 8200, ...
16, 4112, 8208, ...

Dies erhalten Sie, wenn Sie auf ein 2D-Array wie double rng_array[MAX_ROWS][512] In der falschen Reihenfolge zugreifen (Schleifen über Zeilen anstatt über Spalten in einer Zeile in der inneren Schleife, wie von @JesperJuhl vorgeschlagen). Wenn teuflische Inkompetenz ein 2D-Array mit solchen Dimensionen rechtfertigen kann, rechtfertigt die Inkompetenz der Gartenvielfalt leicht das Schleifen mit dem falschen Zugriffsmuster. Dies geschieht im realen Code im realen Leben.

Passen Sie die Schleifengrenzen gegebenenfalls an, um viele verschiedene Seiten zu verwenden, anstatt die gleichen Seiten erneut zu verwenden, wenn das Array nicht so groß ist. Das Hardware-Prefetching funktioniert (auch/überhaupt) nicht seitenübergreifend. Der Prefetcher kann einen Vorwärts- und einen Rückwärtsstrom innerhalb jeder Seite verfolgen (was hier geschieht), wird jedoch nur dann darauf reagieren, wenn die Speicherbandbreite nicht bereits mit Non-Prefetch-Daten gesättigt ist.

Dies führt auch zu vielen TLB-Fehlern, es sei denn, die Seiten werden zu einer riesigen Seite zusammengeführt ( Linux führt dies opportunistisch für anonyme (nicht dateibasierte) Zuweisungen wie malloc/new, die mmap(MAP_ANONYMOUS) verwenden.

Anstelle eines Arrays zum Speichern der Ergebnisliste können Sie auch verknüpfte Liste verwenden. Dann würde jede Iteration eine Pointer-Chasing-Last erfordern (eine echte RAW-Abhängigkeitsgefahr für die Ladeadresse der nächsten Last). Mit einem fehlerhaften Allokator können Sie möglicherweise die Listenknoten im Arbeitsspeicher verteilen und den Cache beschädigen. Mit einem teuflisch inkompetenten Allokator könnte er jeden Knoten an den Anfang seiner eigenen Seite setzen. (z. B. direkt mit mmap(MAP_ANONYMOUS) zuweisen, ohne Seiten aufzubrechen oder Objektgrößen zu verfolgen, um free ordnungsgemäß zu unterstützen).


Diese sind nicht wirklich mikroarchitekturspezifisch und haben wenig mit der Pipeline zu tun (die meisten davon wären auch eine Verlangsamung bei einer CPU ohne Pipeline).

Etwas abseits des Themas: Den Compiler dazu bringen, schlechteren Code zu generieren/mehr Arbeit zu leisten:

Verwenden Sie C++ 11 std::atomic<int> Und std::atomic<double> Für den pessimalsten Code. Die Befehle MFENCEs und lock sind recht langsam, auch wenn kein anderer Thread darauf hinweist.

-m32 Macht den Code langsamer, da der x87-Code schlechter ist als der SSE2-Code. Die stapelbasierte 32-Bit-Aufrufkonvention nimmt mehr Anweisungen entgegen und übergibt sogar FP Args auf dem Stapel an Funktionen wie exp(). atomic<uint64_t>::operator++ Für -m32 Erfordert eine lock cmpxchg8B - Schleife (i586). (Also benutze das für Schleifenzähler! [Böses Lachen]).

-march=i386 Wird auch pessimisieren (danke @Jesper). FP im Vergleich zu fcom sind langsamer als 686 fcomi. In Pre-586 gibt es keinen atomaren 64-Bit-Speicher (geschweige denn ein cmpxchg). Daher werden alle 64-Bit-Operationen atomic mit libgcc-Funktionsaufrufen kompiliert (was wahrscheinlich für i686 kompiliert wird, anstatt tatsächlich eine Sperre zu verwenden). Probieren Sie es über den Link Godbolt Compiler Explorer im letzten Absatz aus.

Verwenden Sie long double/sqrtl/expl für zusätzliche Präzision und Langsamkeit bei ABIs, bei denen sizeof (long double) 10 oder 16 beträgt (mit Abstand zum Ausrichten). (IIRC, 64-Bit-Windows verwendet 8 Byte long double, Was double entspricht. (Das Laden/Speichern von 10 Byte (80 Bit) FP -Operanden beträgt 4/7 Uops im Vergleich zu float oder double nehmen nur jeweils 1 UOP für fld m64/m32/fst). Durch Erzwingen von x87 mit long double Wird die automatische Vektorisierung selbst für gcc -m64 -march=haswell -O3.

Wenn Sie keine atomic<uint64_t> - Schleifenzähler verwenden, verwenden Sie long double Für alles, auch für Schleifenzähler.

atomic<double> Kompiliert, aber Lese-, Änderungs- und Schreibvorgänge wie += Werden nicht unterstützt (auch nicht unter 64-Bit). atomic<long double> Muss eine Bibliotheksfunktion nur für atomare Ladevorgänge aufrufen. Es ist wahrscheinlich wirklich ineffizient , da der x86 ISA von Natur aus keine atomaren 10-Byte-Ladevorgänge/-speicher unterstützt und die einzige Möglichkeit ist, die ich mir vorstellen kann, ohne zu sperren (cmpxchg16b) Erfordert den 64-Bit-Modus.


Bei -O0 Führt das Aufbrechen eines großen Ausdrucks durch Zuweisen von Teilen zu temporären Variablen zu mehr Speichern/Neuladen. Ohne volatile oder etwas spielt dies keine Rolle bei Optimierungseinstellungen, die ein echter Build von echtem Code verwenden würde.

C-Aliasing-Regeln erlauben es einem char, einen Alias ​​für irgendetwas zu vergeben, so dass das Speichern durch einen char* Den Compiler zwingt, alles vor/nach dem Byte-Store zu speichern/neu zu laden, sogar bei -O3. (Dies ist ein Problem bei der automatischen Vektorisierung von Code, der beispielsweise auf ein Array von uint8_t angewendet wird.)

Versuchen Sie es mit uint16_t - Schleifenzählern, um das Abschneiden auf 16 Bit zu erzwingen. Verwenden Sie dazu möglicherweise 16-Bit-Operanden (mögliche Verzögerungen) und/oder zusätzliche movzx - Anweisungen (sicher). Signed Overflow ist undefiniertes Verhalten . Sofern Sie also nicht -fwrapv Oder mindestens -fno-strict-overflow Verwenden, geben Signed Loop-Zähler keine Es muss nicht bei jeder Iteration neu signiert werden , auch wenn dies als Versatz für 64-Bit-Zeiger verwendet wird.


Konvertierung von Integer nach float und zurück erzwingen. Und/oder double <=> float Konvertierungen. Die Anweisungen haben eine Latenz von mehr als 1, und der skalare int-> float (cvtsi2ss) Ist schlecht konstruiert, um den Rest des xmm-Registers nicht auf Null zu setzen. (Aus diesem Grund fügt gcc ein zusätzliches pxor ein, um Abhängigkeiten aufzubrechen.)


Häufig Stelle deine CPU-Affinität auf eine andere CPU ein (vorgeschlagen von @Egwor). teuflische Überlegung: Sie möchten nicht, dass ein Kern überhitzt, wenn Sie Ihren Thread für eine lange Zeit laufen lassen, oder? Möglicherweise führt das Wechseln zu einem anderen Kern dazu, dass dieser Kern auf eine höhere Taktrate gebracht wird. (In Wirklichkeit sind sie thermisch so nahe beieinander, dass dies mit Ausnahme eines Mehrfachsteckdosensystems höchst unwahrscheinlich ist.) Jetzt stimmen Sie einfach falsch und tun es viel zu oft. Neben der Zeit, die für das Speichern/Wiederherstellen des Thread-Status des Betriebssystems aufgewendet wurde, verfügt der neue Core über kalte L2/L1-Caches, UOP-Cache und Verzweigungsvorhersagen.

Das Einführen häufiger unnötiger Systemaufrufe kann Sie verlangsamen, unabhängig davon, um was es sich handelt. Obwohl einige wichtige, aber einfache wie gettimeofday ohne Übergang zum Kernel-Modus im User-Space mit implementiert werden können. (glibc unter Linux erledigt dies mit Hilfe des Kernels, da der Kernel Code in die vdso exportiert).

Weitere Informationen zum Systemaufruf-Overhead (einschließlich Cache-/TLB-Fehlern nach der Rückkehr in den Benutzerbereich, nicht nur der Kontextwechsel selbst) finden Sie auf dem FlexSC-Papier Die aktuelle Situation sowie ein Vorschlag für Batching-Systemaufrufe stammen von massiven Multithread-Serverprozessen.

397
Peter Cordes

Ein paar Dinge, die Sie tun können, um die Leistung so schlecht wie möglich zu machen:

  • kompilieren Sie den Code für die i386-Architektur. Dies verhindert die Verwendung von SSE und neueren Anweisungen und erzwingt die Verwendung der x87-FPU.

  • verwenden std::atomic Variablen überall. Dies wird sie sehr teuer machen, da der Compiler gezwungen ist, überall Speicherbarrieren einzufügen. Und dies ist etwas, was eine inkompetente Person plausibel tun könnte, um "die Thread-Sicherheit zu gewährleisten".

  • stellen Sie sicher, dass der Prefetcher auf den Speicher so weit wie möglich zugreift, um eine Vorhersage zu treffen (Spaltenmajor vs. Zeilenmajor).

  • um Ihre Variablen teurer zu machen, können Sie sicherstellen, dass sie alle über eine dynamische Speicherdauer (Heap-Zuweisung) verfügen, indem Sie ihnen new zuweisen, anstatt ihnen eine automatische Speicherdauer (Stack-Zuweisung) zuzuweisen.

  • stellen Sie sicher, dass der gesamte zugewiesene Speicher sehr seltsam ausgerichtet ist, und vermeiden Sie auf jeden Fall die Zuweisung großer Seiten, da dies viel zu TLB-effizient wäre.

  • was auch immer Sie tun, erstellen Sie Ihren Code nicht mit aktiviertem Compiler-Optimierer. Und stellen Sie sicher, dass Sie die aussagekräftigsten Debugsymbole aktivieren, die Sie verwenden können (der Code wird nicht langsamer ausgeführt , verschwendet jedoch zusätzlichen Speicherplatz). .

Hinweis: Diese Antwort fasst im Wesentlichen nur meine Kommentare zusammen, die @Peter Cordes bereits in seine sehr gute Antwort aufgenommen hat. Schlagen Sie vor, dass er Ihre Zustimmung erhält, wenn Sie nur eine übrig haben :)

33
Jesper Juhl

Sie können long double zur Berechnung. Auf x86 sollte es das 80-Bit-Format sein. Dies wird nur von der älteren x87-FPU unterstützt.

Einige Mängel der x87-FPU:

  1. Fehlt die SIMD-Karte, benötigen Sie möglicherweise weitere Anweisungen.
  2. Stack-basiert, problematisch für superskalare und Pipeline-Architekturen.
  3. Separate und recht kleine Registersätze erfordern möglicherweise mehr Konvertierung von anderen Registern und mehr Speicheroperationen.
  4. Auf dem Core i7 gibt es 3 Ports für SSE und nur 2 für x87, der Prozessor kann weniger parallele Anweisungen ausführen.
10
Michas

Späte Antwort, aber ich glaube nicht, dass wir verknüpfte Listen und den TLB genug missbraucht haben.

Verwenden Sie mmap, um Ihre Knoten so zuzuordnen, dass Sie meistens das MSB der Adresse verwenden. Dies sollte zu langen TLB-Suchketten führen, eine Seite hat 12 Bit und 52 Bit für die Übersetzung, oder ungefähr 5 Ebenen, die jedes Mal durchlaufen werden müssen. Mit ein bisschen Glück müssen sie jedes Mal in den Speicher gehen, um 5 Ebenen abzurufen, plus 1 Speicherzugriff, um zu Ihrem Knoten zu gelangen. Die oberste Ebene befindet sich höchstwahrscheinlich irgendwo im Cache. Wir können also auf 5 * Speicherzugriff hoffen. Platzieren Sie den Knoten so, dass er an der schlechtesten Grenze verläuft, sodass das Lesen des nächsten Zeigers weitere 3-4 Übersetzungssuchen verursachen würde. Dies könnte auch den Cache aufgrund der enormen Menge an Übersetzungssuchen völlig ruinieren. Auch die Größe der virtuellen Tabellen kann dazu führen, dass die meisten Benutzerdaten für einen längeren Zeitraum auf die Festplatte ausgelagert werden.

Stellen Sie beim Lesen aus der einzelnen verknüpften Liste sicher, dass Sie jedes Mal am Anfang der Liste lesen, um eine maximale Verzögerung beim Lesen einer einzelnen Nummer zu erreichen.

3
Surt