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

Ihre Aufgabe ist das Gegenteil unserer ersten Laboraufgabe, bei der ein Primzahlprogramm optimiert wurde. Ihr Zweck in dieser Aufgabe ist es, das Programm zu pessimieren, dh langsamer laufen zu lassen. Beide 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 Möglichkeiten vor, Befehlspfade neu zu ordnen, um WAR, RAW und andere Gefahren einzuführen. Überlegen Sie, wie Sie die Effektivität des Caches minimieren können. Sei teuflisch inkompetent.

Die Aufgabe gab eine Auswahl von Whetstone- oder Monte-Carlo-Programmen. Die Kommentare zur Cache-Effektivität gelten meistens 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 Code-Laufzeit um eine Sekunde zu erhöhen, aber ich bin nicht ganz sicher, was ich ändern kann, um die Pipeline zu blockieren, ohne Code hinzuzufügen. Ein Punkt in die richtige Richtung wäre fantastisch, ich freue mich über jede Antwort.

Update: Der Professor, der diese Aufgabe gegeben hat, hat einige Details veröffentlicht

Die Highlights sind:

• Es ist ein Architekturkurs im zweiten Semester an einem Community College (unter Verwendung des Lehrbuchs von Hennessy und Patterson).
• Die Laborcomputer verfügen über Haswell-CPUs
• Die Schüler wurden mit der CPUIDAnweisung und der Bestimmung der Cache-Größe sowie den Grundlagen und der CLFLUSHAnweisung vertraut gemacht.
• Alle Compileroptionen sind zulässig, ebenso wie Inline-Asm.
• Das Schreiben eines eigenen Quadratwurzel-Algorithmus wurde als außerhalb des Blassen befindlich angekündigt

Cowmooguns Kommentare zum Meta-Thread deuten darauf hin, dass es nicht klar war, dass Compiler-Optimierungen Teil davon sein könnten-O0 , und dass eine Verlängerung 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 Parallelität auf Unterrichtsebene oder ähnliches zu reduzieren, aber es ist keine schlechte Sache, dass die Leute tiefer gegangen sind und mehr gelernt haben.

Beachten Sie, dass dies eine Frage zur Computerarchitektur ist und keine Frage, wie C ++ im Allgemeinen langsam gemacht werden kann.

Wichtige Hintergrundlesung: Agner Fogs Mikroarch pdf und wahrscheinlich auch Ulrich Dreppers Was jeder Programmierer über Speicher wissen sollte . Siehe auch die anderen Links in derx86Tag-Wiki, insbesondere Intels Optimierungshandbücher, und David Kanters Analyse der Haswell-Mikroarchitektur mit Diagrammen .

Sehr coole Aufgabe; viel besser als die, bei denen die Schüler aufgefordert wurden, Code zu optimierengcc -O0 , und eine Reihe von Tricks gelernt haben, 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 blind zu raten. Der lustigste Teil davon ist, jede Pessimisierung mit "teuflischer Inkompetenz" zu rechtfertigen, nicht mit vorsätzlicher Bosheit.

Probleme mit dem Wortlaut und dem Code der Zuordnung :

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 von exp/ loglibrary-Funktionen. Es gibt keinen offensichtlichen Weg, mehr oder weniger Parallelität auf Befehlsebene zu erreichen, und die von Schleifen getragene Abhängigkeitskette ist sehr kurz.

Ich würde gerne eine Antwort sehen, die versucht hat, die Neuanordnung der Ausdrücke zu verlangsamen, um die Abhängigkeiten zu ändern und ILP nur aufgrund von Abhängigkeiten (Gefahren) zu reduzieren . Ich habe es nicht versucht.

CPUs der Intel Sandybridge-Familie sind aggressive Out-of-Order-Designs, die viel Transistoren und Strom verbrauchen, um Parallelität zu finden und Gefahren (Abhängigkeiten) zu vermeiden, die eine klassische RISC-Pipeline in der Reihenfolge stören würden . Normalerweise sind die einzigen herkömmlichen Gefahren, die es verlangsamen, "echte" RAW-Abhängigkeiten, die dazu führen, dass der Durchsatz durch die Latenz begrenzt wird.

WAR- und WAW-Gefahren für Register sind dank der Umbenennung von Registern so gut wie kein Problem . (mit Ausnahme vonpopcnt/lzcnt/tzcnt, deren Ziel von Intel-CPUs falsch abhängig ist , obwohl es nur schreibgeschützt ist. Das heißt, WAW wird als RAW-Gefahr + Schreibvorgang behandelt). Bei der Speicherbestellung verwenden moderne CPUs Speicherwarteschlangen, um das Festschreiben im Cache bis zur Stilllegung zu verzögern und gleichzeitig WAR- und WAW-Gefahren zu vermeiden .

Warum dauert Mulss auf Haswell nur 3 Zyklen, anders als in Agners Anweisungstabellen? Weitere Informationen zum Umbenennen von Registern und zum Ausblenden der FMA-Latenz in einer FP-Punktproduktschleife.

Der Markenname "i7" wurde mit Nehalem (Nachfolger von Core2) eingeführt , und einige Intel-Handbücher sagen sogar "Core i7", wenn sie Nehalem bedeuten, aber sie behielten das "i7" -Markenzeichen für Sandybridge und spätere Mikroarchitekturen bei. SnB ist, als sich die P6-Familie zu einer neuen Spezies entwickelte, der SnB-Familie . In vielerlei Hinsicht hat Nehalem mehr mit Pentium III gemeinsam als mit Sandybridge (z. B. Register-Lesestände und ROB-Lesestände treten bei SnB nicht auf, da eine physische Registerdatei verwendet wurde. Auch ein UOP-Cache und ein anderes internes UOP-Format). Der Begriff "i7-Architektur" ist nicht sinnvoll, weil es wenig Sinn macht, die SnB-Familie mit Nehalem zu gruppieren, aber nicht mit Core2. (Nehalem hat jedoch die gemeinsam genutzte inklusive L3-Cache-Architektur für die Verbindung mehrerer Kerne eingeführt. Und auch integrierte GPUs. Daher ist die Benennung auf Chipebene sinnvoller.)

Zusammenfassung der guten Ideen, die teuflische Inkompetenz rechtfertigen kann

Selbst die teuflisch inkompetenten Personen werden wahrscheinlich keine offensichtlich nutzlose Arbeit oder eine Endlosschleife hinzufügen, und ein Durcheinander mit C ++ / Boost-Klassen würde den Rahmen der Aufgabe sprengen.

• Multithread mit einem einzelnen gemeinsam genutzten std::atomic<uint64_t> Schleifenzähler, sodass die richtige Gesamtzahl von Iterationen erfolgt. Atomic uint64_t ist besonders schlecht mit -m32 -march=i586. Sorgen Sie dafür, dass die Bonuspunkte falsch ausgerichtet sind und eine Seitengrenze mit einer ungleichmäßigen Aufteilung (nicht 4: 4) überschritten wird.
• Falsche Freigabe für eine andere nichtatomare Variable -> Fehlspekulationspipeline in Speicherreihenfolge wird gelöscht, sowie zusätzliche Cache-Fehler.
• Anstatt -FP-Variablen zu verwenden, XOR das High-Byte mit 0x80, um das Vorzeichenbit umzudrehen, was zu Speicherstillstandsstillständen führt .
• Zeit jede Iteration unabhängig, mit etwas noch schwerer als RDTSC. zB CPUID/ RDTSCoder eine Zeitfunktion, die einen Systemaufruf ausführt. Serialisierungsanweisungen sind von Natur aus Pipeline-unfreundlich.
• Ändern Sie Multiplikationen mit Konstanten in Divisionen durch ihren Kehrwert ("zur Erleichterung des Lesens"). div ist langsam und nicht vollständig per Pipeline.
• Vektorisieren Sie das Multiplizieren / Quadrat mit AVX (SIMD), verwenden Sie es jedoch nicht, vzeroupperbevor Sie die skalare Mathematikbibliothek exp()und log()Funktionen aufrufen , was dazu führt, dass der AVX <-> SSE-Übergang blockiert .
• Speichern Sie die RNG-Ausgabe in einer verknüpften Liste oder in Arrays, die Sie nicht in der richtigen Reihenfolge durchlaufen. Gleiches gilt für das Ergebnis jeder Iteration und die Summe am Ende.

Ebenfalls in dieser Antwort behandelt, aber aus der Zusammenfassung ausgeschlossen: Vorschläge, die auf einer CPU ohne Pipeline genauso langsam wären oder die selbst bei teuflischer Inkompetenz nicht zu rechtfertigen scheinen. zB viele Gimp-the-Compiler-Ideen, die offensichtlich unterschiedliche / schlechtere Asm erzeugen.

Multithread schlecht

Verwenden Sie OpenMP möglicherweise für Multithread-Schleifen mit sehr wenigen Iterationen, mit viel mehr Overhead als Geschwindigkeitsgewinn. Ihr Monte-Carlo-Code hat jedoch genug Parallelität, um tatsächlich eine Beschleunigung zu erzielen, insb. wenn es uns gelingt, jede Iteration langsam zu machen. (Jeder Thread berechnet einen Teil payoff_sum, der am Ende hinzugefügt wird.) #omp parallelIn dieser Schleife wäre wahrscheinlich eine Optimierung, keine Pessimierung.

Multi-Thread, aber beide Threads müssen denselben Schleifenzähler verwenden (mit atomicInkrementen, damit die Gesamtzahl der Iterationen korrekt ist). Dies scheint teuflisch logisch. Dies bedeutet, dass eine staticVariable als Schleifenzähler verwendet wird. Dies rechtfertigt die Verwendung von atomicfor-Schleifenzählern und erzeugt tatsächliches Ping-Ponging in der Cache-Zeile (solange die Threads nicht mit Hyperthreading auf demselben physischen Kern ausgeführt werden; dies ist möglicherweise nicht so langsam). Auf jeden Fall ist dies viel langsamer als der unbestrittene Fall für lock inc. Und lock cmpxchg8bum ein konkurrierendes uint64_tauf einem 32-Bit-System atomar zu erhöhen, muss es in einer Schleife erneut versucht werden, anstatt dass die Hardware ein Atom vermittelt inc.

Erstellen Sie auch eine falsche Freigabe , bei der mehrere Threads ihre privaten Daten (z. B. den RNG-Status) in verschiedenen Bytes derselben Cache-Zeile speichern. (Intel Tutorial darüber, einschließlich Perf Counter zum Anschauen) . Dies hat einen mikroarchitekturspezifischen Aspekt : Intel-CPUs spekulieren über Speicherfehler keine , und es gibt ein maschinenlöschendes Perf-Ereignis für die Speicherreihenfolge, um dies zumindest auf P4 zu erkennen . Die Strafe für Haswell ist möglicherweise nicht so hoch. Wie dieser Link zeigt, a,lock ed-Anweisung davon dass dies passieren wird, um Fehlerspekulationen zu vermeiden. Ein normales Laden spekuliert, dass andere Kerne eine Cache-Zeile zwischen dem Ausführen des Ladens und dem Zurückziehen in Programmreihenfolge nicht ungültig machen (es sei denn, Sie verwendenpause ). Echtes Teilen ohnelocked Anweisungen ist in der Regel ein Fehler. Es wäre interessant, einen nichtatomaren Shared-Loop-Zähler mit dem atomaren Fall zu vergleichen. Um wirklich zu pessimisieren, behalten Sie den Zähler für gemeinsam genutzte Atomschleifen bei und verursachen Sie eine falsche Freigabe in derselben oder einer anderen Cache-Zeile für eine andere Variable.

Zufällige uarch-spezifische Ideen:

Wenn Sie unvorhersehbare Zweige einführen können , wird der Code dadurch erheblich pessimiert. Moderne x86-CPUs haben ziemlich lange Pipelines, sodass eine Fehlvorhersage ~ 15 Zyklen kostet (wenn sie aus dem UOP-Cache ausgeführt wird).

Abhängigkeitsketten:

Ich denke, dies war einer der beabsichtigten Teile der Aufgabe.

Besiegen Sie die Fähigkeit der CPU, Parallelität auf Befehlsebene auszunutzen, indem Sie eine Reihenfolge von Operationen auswählen, die eine lange Abhängigkeitskette anstelle mehrerer kurzer Abhängigkeitsketten aufweisen. Compiler dürfen die Reihenfolge der Operationen für FP-Berechnungen nur ändern, wenn Sie sie verwenden-ffast-math nur ändern, , da dies die Ergebnisse ändern kann (wie unten erläutert).

Um dies wirklich effektiv zu machen, erhöhen Sie die Länge einer von Schleifen getragenen Abhängigkeitskette. Nichts ist jedoch so offensichtlich: Die geschriebenen Schleifen haben sehr kurze, von Schleifen getragene Abhängigkeitsketten: nur ein FP-Add. (3 Zyklen). Bei mehreren Iterationen können die Berechnungen gleichzeitig ausgeführt werden, da sie weit vor payoff_sum +=dem Ende der vorherigen Iteration beginnen können. ( log()und expnehmen Sie viele Anweisungen, aber nicht viel mehr als Haswells Fenster außerhalb der Reihenfolge, um Parallelität zu finden: ROB-Größe = 192 Uops mit verschmolzener Domäne und Scheduler-Größe = 60 Uops mit nicht verschmolzener Domäne. Sobald die Ausführung der aktuellen Iteration weit genug fortgeschritten ist, um Platz für Anweisungen ab der nächsten Iteration zu schaffen, werden alle Teile davon bereitstehen (dh unabhängig / getrennt) dep chain) kann mit der Ausführung beginnen, wenn ältere Anweisungen die Ausführungseinheiten frei lassen (z. B. weil sie aufgrund der Latenz und nicht des Durchsatzes einen Engpass aufweisen).

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

Verwenden Sie langsamere / mehr FP-Operationen (insbesondere mehr Division):

Teilen Sie durch 2,0, anstatt mit 0,5 zu multiplizieren, und so weiter. FP-Multiplikation ist in Intel-Designs stark überlastet und hat einen Durchsatz von 0,5 c bei Haswell und höher. FP divsd/ divpdist nur teilweise per Pipeline . (Obwohl Skylake einen beeindruckenden Durchsatz von 1 pro divpd xmm4 c mit einer Latenz von 13 bis 14 c hat und bei Nehalem (7 bis 22 c) überhaupt keine Pipeline hat).

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

Wie @Paul Clayton vorschlägt, kann das Umschreiben von Ausdrücken mit assoziativen / verteilenden Äquivalenten mehr Arbeit bedeuten (solange Sie es nicht verwenden -ffast-math, damit der Compiler erneut optimieren kann). (exp(T*(r-0.5*v*v))könnte werden exp(T*r - T*v*v/2.0). Beachten Sie, dass Mathematik für reelle Zahlen zwar assoziativ ist, Gleitkomma-Mathematik jedoch nicht , auch ohne Berücksichtigung von Überlauf / NaN (weshalb diese Option -ffast-mathnicht standardmäßig aktiviert ist). Siehe Pauls Kommentar für einen sehr haarigen, verschachtelten pow()Vorschlag.

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

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

Verwenden Sie movntidiese Option, um Ihre Daten aus dem Cache zu entfernen . Teuflisch: Es ist neu und schwach geordnet, so dass die CPU es schneller laufen lassen sollte, oder? Oder sehen Sie sich diese verknüpfte Frage für einen Fall an, in dem jemand in Gefahr war, genau dies zu tun (für verstreute Schreibvorgänge, bei denen nur einige der Standorte heiß waren). clflushist wahrscheinlich ohne Bosheit unmöglich.

Verwenden Sie Integer-Shuffles zwischen FP-Mathematikoperationen, um Bypass-Verzögerungen zu verursachen.

Das Mischen von SSE- und AVX-Anweisungen ohne ordnungsgemäße Verwendung vzeroupperführt in Pre-Skylake zu großen Verzögerungen (und in Skylake zu einer anderen Strafe). Auch ohne dies kann eine schlechte Vektorisierung schlechter als eine Skalarisierung sein (mehr Zyklen, die damit verbracht werden, Daten in / aus Vektoren zu mischen, als durch Speichern der Operationen add / sub / mul / div / sqrt für 4 Monte-Carlo-Iterationen gleichzeitig mit 256b-Vektoren gespeichert wurden) . Die Ausführungseinheiten add / sub / mul sind vollständig pipelined und in voller Breite, aber div und sqrt auf 256b-Vektoren sind nicht so schnell wie auf 128b-Vektoren (oder Skalaren), sodass die Beschleunigung für nicht dramatisch istdouble.

exp()und log()keine Hardware-Unterstützung, sodass für diesen Teil Vektorelemente zurück in den Skalar extrahiert und die Bibliotheksfunktion separat aufgerufen werden müssen, um die Ergebnisse dann wieder in einen Vektor zu mischen. libm wird normalerweise so kompiliert, dass nur SSE2 verwendet wird. Daher werden die Legacy-SSE-Codierungen von skalaren mathematischen Anweisungen verwendet. Wenn Ihr Code 256b-Vektoren verwendet und aufruft, expohne dies vzeroupperzuerst zu tun , bleiben Sie stehen. Nach der Rückkehr wird auch ein AVX-128-Befehl vmovsdzum Einrichten des nächsten Vektorelements als Argument für expblockiert. Und wird dann exp()wieder blockiert, wenn eine SSE-Anweisung ausgeführt wird. Dies ist genau das, was in dieser Frage passiert ist und eine 10-fache Verlangsamung verursacht hat. (Danke @ZBoson).

Siehe auch Nathan Kurzs Experimente mit Intels Math Lib vs. Glibc für diesen Code . Zukünftiges glibc wird mit vektorisierten Implementierungen von exp()und so weiter kommen.

Wenn Sie auf Pre-IvB oder esp. Nehalem, versuchen Sie, gcc dazu zu bringen, Teilregisterstillstände mit 16-Bit- oder 8-Bit-Operationen, gefolgt von 32-Bit- oder 64-Bit-Operationen, zu verursachen. In den meisten Fällen wird gcc movzxnach einer 8- oder 16-Bit-Operation verwendet. In diesem Fall wird gcc jedoch geändert ahund dann gelesenax

Mit (inline) asm:

Mit (inline) asm können Sie den UOP-Cache beschädigen: Ein 32B-Codeabschnitt, der nicht in drei 6UOP-Cache-Zeilen passt, erzwingt einen Wechsel vom UOP-Cache zu den Decodern. Eine Inkompetenz, ALIGNdie viele Einzelbytes nopanstelle von ein paar langen nops auf einem Verzweigungsziel innerhalb der inneren Schleife verwendet, könnte den Trick tun. Oder platzieren Sie das Ausrichtungspolster nach dem Etikett anstatt vor dem Etikett. : P Dies ist nur wichtig, wenn das Frontend ein Engpass ist. Dies ist nicht der Fall, wenn es uns gelungen ist, den Rest des Codes zu pessimieren.

Verwenden Sie selbstmodifizierenden Code, um Pipeline-Löschvorgänge (auch bekannt als Maschinennukes) auszulösen.

Es ist unwahrscheinlich, dass LCP-Blockierungen von 16-Bit-Befehlen mit sofort zu großen Werten für 8 Bit nützlich sind. Der UOP-Cache auf SnB und höher bedeutet, dass Sie die Dekodierungsstrafe 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 generiert manchmal solche Anweisungen, auch mit-mtune=intel wenn ein 32-Bit-Befehl verwendet werden könnte.

Eine gebräuchliche Redewendung für das Timing ist dann CPUID(zu serialisieren)RDTSC . Zeit jede Iteration separat mit einem CPUID/ RDTSC, um sicherzustellen, dass das RDTSCnicht mit früheren Anweisungen neu angeordnet wird, was die Dinge sehr verlangsamt . (Im wirklichen Leben besteht der clevere Weg zur Zeit darin, alle Iterationen zusammen zu messen, anstatt sie einzeln zu steuern und zu addieren.)

Verursacht viele Cache-Fehler und andere Speicherverlangsamungen

Verwenden Sie a union { double d; char a[8]; }für einige Ihrer Variablen. Verursachen Sie einen Speicherweiterleitungsstopp, indem Sie einen engen Speicher (oder Read-Modify-Write) für nur eines der Bytes ausführen. (Dieser Wiki-Artikel behandelt auch viele andere mikroarchitektonische Dinge für Lade- / Speicherwarteschlangen). Beispiel: Drehen Sie das Vorzeichen von a doublemit XOR 0x80 nur auf das High-Byte anstatt auf a- Operators . Der teuflisch inkompetente Entwickler hat möglicherweise gehört, dass FP langsamer als Integer ist, und versucht daher, mit Integer-Ops so viel wie möglich zu tun. (Ein sehr guter Compiler, der auf FP-Mathematik in SSE-Registern abzielt, kann dies möglicherweise zu einem kompilierenxorps mit einer Konstante in einem anderen xmm-Register, aber der einzige Weg, wie dies für x87 nicht schrecklich ist, besteht darin, dass der Compiler erkennt, dass er den Wert negiert, und die nächste Addition durch eine Subtraktion ersetzt.)

Verwenden volatileSie diese Option, wenn Sie mit kompilieren -O3und nicht verwenden 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 / Neuladungen, aber die schwache Reihenfolge des C ++ - Speichermodells erfordert nicht, dass der Compiler ständig in den Speicher verschüttet / neu lädt .

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 ihre Existenz zu rechtfertigen).

Wählen Sie Ihr Speicherlayout so, dass alles in einer anderen Zeile im selben "Satz" im L1-Cache abläuft . Es ist nur 8-Wege-Assoziativ, dh jeder Satz hat 8 "Wege". Cache-Zeilen sind 64B.

Noch besser, stellen Sie die Dinge genau 4096B auseinander, da Ladevorgänge eine falsche Abhängigkeit von Speichern auf verschiedenen Seiten haben, jedoch mit demselben Versatz innerhalb einer Seite . Aggressive CPUs außerhalb der Reihenfolge verwenden die Speicherdisambiguierung, um herauszufinden, wann Lasten und Speicher neu angeordnet werden können, ohne die Ergebnisse zu ändern. Die Implementierung von Intel weist Fehlalarme auf, die verhindern, dass Lasten frühzeitig 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. Neben Agners Leitfaden finden Sie eine Antwort von Stephen Canon sowie einen Abschnitt am Ende von @ Krazy Glews Antwort auf dieselbe Frage. (Andy Glew war einer der Architekten der ursprünglichen P6-Mikroarchitektur von Intel.)

Verwenden __attribute__((packed))Sie diese Option, um Variablen falsch auszurichten, sodass sie sich über Cache-Zeilen- oder sogar Seitengrenzen erstrecken. (Eine Ladung von einem doublebenötigt also Daten aus zwei Cache-Zeilen). Falsch ausgerichtete Ladevorgänge haben in keinem Intel i7-Archiv eine Strafe, außer beim Überqueren von Cache- und Seitenzeilen. Cache-Line-Splits benötigen noch zusätzliche Zyklen . Skylake reduziert die Strafe für das Teilen von Seiten von 100 auf 5 Zyklen erheblich. (Abschnitt 2.1.3) . Vielleicht hängt es damit zusammen, dass zwei Seiten gleichzeitig ausgeführt werden können.

Ein Seitensplit auf einem atomic<uint64_t>sollte fast der schlimmste Fall sein , insb. 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 Uarchen, IIRC. Legen 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_toder uint16_tfür etwas vor dem Zähler verwenden.

Wenn Sie den Compiler dazu bringen können, indizierte Adressierungsmodi zu verwenden, wird dies die uop-Mikrofusion zunichte machen . Vielleicht durch die Verwendung von #defines, um einfache skalare Variablen durch zu ersetzen my_data[constant].

Wenn Sie eine zusätzliche Indirektionsebene einführen können, sodass Lade- / Speicheradressen nicht frühzeitig bekannt sind, kann dies zu einer weiteren Pessimierung führen.

Durchlaufen Sie Arrays in nicht zusammenhängender Reihenfolge

Ich denke, wir können uns zunächst eine inkompetente Rechtfertigung 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 werden, um später summiert zu werden (mit teuflischer Inkompetenz).

Für "maximale Zufälligkeit" könnte ein Thread über das Zufallsarray laufen und neue Zufallszahlen in das Array schreiben. Der Thread, der die Zufallszahlen verbraucht, könnte einen Zufallsindex erzeugen, aus dem eine Zufallszahl geladen wird. (Hier gibt es einige Arbeiten, aber mikroarchitektonisch hilft es, dass Ladeadressen frühzeitig erkannt werden, damit eine mögliche Ladelatenz behoben werden kann, bevor die geladenen Daten benötigt werden.) Wenn ein Leser und ein Schreiber auf verschiedenen Kernen vorhanden sind, führt dies zu einer falschen Speicherreihenfolge -speculation Pipeline wird gelöscht (wie bereits für den Fall der falschen Freigabe erläutert).

Um eine maximale Pessimierung zu erzielen, durchlaufen Sie Ihr Array mit einem Schritt von 4096 Bytes (dh 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 für den Zugriff auf ein 2D-Array wie double rng_array[MAX_ROWS][512]in der falschen Reihenfolge (Schleifen über Zeilen anstelle von Spalten innerhalb einer Zeile in der inneren Schleife, wie von @JesperJuhl vorgeschlagen). Wenn teuflische Inkompetenz ein 2D-Array mit solchen Abmessungen rechtfertigen kann, rechtfertigt die reale Inkompetenz der Gartenvielfalt leicht das Schleifen mit dem falschen Zugriffsmuster. Dies geschieht im realen Code im realen Leben.

Passen Sie die Schleifengrenzen bei Bedarf an, um viele verschiedene Seiten zu verwenden, anstatt dieselben wenigen Seiten wiederzuverwenden, wenn das Array nicht so groß ist. Das Hardware-Prefetching funktioniert nicht (auch / überhaupt) seitenübergreifend. Der Prefetcher kann innerhalb jeder Seite einen Vorwärts- und einen Rückwärtsstrom verfolgen (was hier passiert), wirkt jedoch nur dann darauf, wenn die Speicherbandbreite nicht bereits mit Nicht-Prefetch gesättigt ist.

Dies wird auch viele TLB - Fehler erzeugen, es sei denn , die Seiten in eine hugepage verschmolzen bekommen ( Linux tut dies opportunistisch für anonyme (nicht Datei-backed) Zuweisungen wie malloc/ newdiese Verwendungmmap(MAP_ANONYMOUS) ).

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

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

Etwas abseits des Themas: Lassen Sie den Compiler schlechteren Code generieren / machen Sie mehr Arbeit:

Verwenden Sie C ++ 11 std::atomic<int>und std::atomic<double>den pessimalsten Code. Die MFENCEs und locked-Anweisungen sind auch ohne Konkurrenz durch einen anderen Thread ziemlich langsam.

-m32macht langsameren Code, weil x87-Code schlechter ist als SSE2-Code. Die stapelbasierte 32-Bit-Aufrufkonvention benötigt mehr Anweisungen und übergibt sogar FP-Argumente auf dem Stapel an Funktionen wie exp(). atomic<uint64_t>::operator++on -m32erfordert eine lock cmpxchg8BSchleife (i586). (Verwenden Sie das also für Schleifenzähler! [Böses Lachen]).

-march=i386wird auch pessimisieren (danke @Jesper). FP-Vergleiche mit fcomsind langsamer als 686 fcomi. Pre-586 bietet keinen atomaren 64-Bit-Speicher (geschweige denn einen cmpxchg), sodass alle 64-Bit- atomicOperationen zu libgcc-Funktionsaufrufen kompiliert werden (der 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.

Verwendung long double/ sqrtl/ explfür zusätzliche Präzision und extra Langsamkeit in ABIs wo sizeof ( long double) 10 oder 16 (mit einer Polsterung für die Ausrichtung). (IIRC, 64-Bit-Windows verwendet 8-Byte- long doubleÄquivalent zu double. (Wie auch immer, das Laden / Speichern von 10-Byte-FP-Operanden (80-Bit) beträgt 4/7 Uops, verglichen mit floatoder doublenur 1 UOP fürfld m64/m32 / fst.) X87 Erzwingen mit long doubleNiederlage auto-Vektorisierung sogar gcc -m64 -march=haswell -O3.

Wenn nicht mit atomic<uint64_t> Schleifenzähler verwenden, verwenden Sie diese long doublefür alle, einschließlich der Schleifenzähler.

atomic<double>Kompiliert, aber Lese-, Änderungs- und Schreibvorgänge wie +=werden nicht unterstützt (auch nicht auf 64-Bit). atomic<long double>muss eine Bibliotheksfunktion nur für atomare Lasten / Speicher aufrufen. Es ist wahrscheinlich wirklich ineffizient, da der x86-ISA natürlich keine atomaren 10-Byte-Ladevorgänge / -Speicher unterstützt und der einzige Weg, den ich mir ohne locking ( cmpxchg16b) vorstellen kann, den 64-Bit-Modus erfordert.

Das -O0Aufbrechen eines großen Ausdrucks durch Zuweisen von Teilen zu temporären Variablen führt zu mehr Speichern / Neuladen. Ohne volatileoder etwas anderes spielt dies bei Optimierungseinstellungen keine Rolle, die ein echter Build von echtem Code verwenden würde.

C-Aliasing-Regeln erlauben es char, alles zu aliasen, so dass das Speichern durch a char*den Compiler zwingt, alles vor / nach dem Byte-Speicher zu speichern / neu zu laden, auch bei -O3. (Dies ist ein Problem bei der automatischen Vektorisierung Code, der beispielsweise mit einem Array vonuint8_t arbeitet.)

Versuchen Sie uint16_tSchleifenzähler, um das Abschneiden auf 16 Bit zu erzwingen, wahrscheinlich mithilfe der Operandengröße von 16 Bit (potenzielle Verzögerungen) und / oder zusätzlicher movzxAnweisungen (sicher). Signierter Überlauf ist ein undefiniertes Verhalten . Wenn Sie also keine signierten Schleifenzähler verwenden -fwrapvoder zumindest verwenden -fno-strict-overflow, müssen diese nicht bei jeder Iteration erneut signiert werden Wenn , selbst wenn sie als Offsets für 64-Bit-Zeiger verwendet werden.

Konvertierung von Ganzzahl nach floatund wieder zurück erzwingen. Und / oder double<=> floatConversions. Die Anweisungen haben eine Latenz von mehr als eins, und skalar int-> float ( cvtsi2ss) ist schlecht ausgelegt, um den Rest des xmm-Registers nicht auf Null zu setzen. (gcc fügt pxoraus diesem Grund ein Extra ein , um Abhängigkeiten zu lösen.)

Häufig Ihre CPU - Affinität zu einer anderen CPU gesetzt (vorgeschlagen von @Egwor). teuflische Argumentation: Sie möchten nicht, dass ein Kern überhitzt wird, wenn Sie Ihren Thread für längere Zeit laufen lassen, oder? Wenn Sie zu einem anderen Kern wechseln, erreicht dieser Kernturbo möglicherweise eine höhere Taktrate. (In Wirklichkeit: Sie sind thermisch so nahe beieinander, dass dies höchst unwahrscheinlich ist, außer in einem System mit mehreren Steckdosen.) Verstehen Sie jetzt einfach die Stimmung falsch und machen Sie es viel zu oft. Neben der Zeit, die für das Speichern / Wiederherstellen des Thread-Status des Betriebssystems aufgewendet wurde, verfügt der neue Kern über kalte L2 / L1-Caches, UOP-Caches und Verzweigungsvorhersagen.

Das Einführen häufiger unnötiger Systemaufrufe kann Sie verlangsamen, egal was sie sind. Obwohl einige wichtige, aber einfache wie gettimeofdayim User-Space mit implementiert werden können, ohne Übergang in den Kernel-Modus. (glibc unter Linux tut dies mit Hilfe des Kernels, da der Kernel Code in den Kernel exportiert vdso).

Weitere Informationen zum Overhead von Systemaufrufen (einschließlich Cache- / TLB-Fehlern nach der Rückkehr in den Benutzerbereich, nicht nur zum Kontextwechsel selbst) finden Sie im FlexSC-Dokument mit einer umfassenden Analyse der aktuellen Situation sowie einem Vorschlag für ein Batching-System Aufrufe von massiven Multithread-Serverprozessen.

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 Sie std::atomicüberall Variablen. Dies macht sie sehr teuer, da der Compiler gezwungen ist, überall Speicherbarrieren einzufügen. Und dies ist etwas, was eine inkompetente Person plausibel tun könnte, um "die Gewindesicherheit zu gewährleisten".

• Stellen Sie sicher, dass der Prefetcher so schlecht wie möglich auf den Speicher zugreift (Spaltenmajor vs. Zeilenmajor).

• Um Ihre Variablen besonders teuer zu machen, können Sie sicherstellen, dass sie alle eine "dynamische Speicherdauer" (Heap zugewiesen) haben, indem Sie sie zuweisen, newanstatt ihnen eine "automatische Speicherdauer" (Stapel zugewiesen) zuzuweisen.

• Stellen Sie sicher, dass der gesamte von Ihnen 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 , die meisten ausdrucke Debug - Symbole zu ermöglichen , können Sie (werden nicht den Code machen läuft langsamer, aber es wird etwas mehr Speicherplatz verschwenden).

Hinweis: Diese Antwort fasst im Grunde nur meine Kommentare zusammen, die @Peter Cordes bereits in seine sehr gute Antwort aufgenommen hat. Schlagen Sie vor, er bekommt Ihre Gegenstimme, wenn Sie nur eine übrig haben :)

Sie können long doublefür die Berechnung verwenden. Auf x86 sollte es das 80-Bit-Format sein. Nur die alte x87-FPU unterstützt dies.

Einige Mängel der x87-FPU:

1. Mangels SIMD sind möglicherweise weitere Anweisungen erforderlich.
2. Stapelbasiert, 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.

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

Verwenden Sie mmap, um Ihre Knoten zuzuweisen, sodass Sie meistens das MSB der Adresse verwenden. Dies sollte zu langen TLB-Suchketten führen. Eine Seite besteht aus 12 Bit, wobei 52 Bit für die Übersetzung übrig bleiben, oder etwa 5 Ebenen, die jedes Mal durchlaufen werden müssen. Mit etwas Glück müssen sie jedes Mal in den Speicher gehen, um 5 Ebenen zu suchen und 1 Speicherzugriff zu erhalten, um zu Ihrem Knoten zu gelangen. Die oberste Ebene befindet sich höchstwahrscheinlich irgendwo im Cache, sodass wir auf einen 5 * Speicherzugriff hoffen können. Platzieren Sie den Knoten so, dass er den schlechtesten Rand überschreitet, sodass das Lesen des nächsten Zeigers weitere 3-4 Übersetzungssuchen verursachen würde. Dies könnte auch den Cache aufgrund der enormen Anzahl von Übersetzungssuchen völlig zerstören. Die Größe der virtuellen Tabellen kann auch dazu führen, dass die meisten Benutzerdaten für zusätzliche Zeit auf die Festplatte übertragen werden.

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