Moderne Prozessoren sind superskalar, dh sie können mehrere Befehle gleichzeitig ausführen. Beispielsweise können einige Prozessoren vier bis sechs Befehle pro Zyklus verarbeiten. Darüber hinaus sind viele solcher Prozessoren in der Lage, Anweisungen außerhalb der Reihenfolge zu initiieren: Sie können viel später mit Befehlen beginnen, die sich im Code befinden.
Gleichzeitig enthält Code häufig Verzweigungen (
if–then ). Solche Verzweigungen werden häufig als "Übergänge" implementiert, bei denen der Prozessor entweder Befehle unterhalb des Codes ausführt oder den aktuellen Pfad fortsetzt.
Bei der superskalaren Ausführung von Befehlen außerhalb der Reihenfolge ist die Verzweigung schwierig. Zu diesem Zweck verfügen Prozessoren über ausgefeilte Verzweigungsvorhersageblöcke. Das heißt, der Prozessor versucht, die Zukunft vorherzusagen. Wenn er einen Zweig und damit einen Übergang sieht, versucht er zu erraten, in welche Richtung das Programm gehen wird.
Sehr oft funktioniert das ganz gut. Beispielsweise werden die meisten Schleifen als Zweige implementiert. Am Ende jeder Iteration der Schleife muss der Prozessor vorhersagen, ob die nächste Iteration durchgeführt wird. Für den Prozessor ist es oft sicherer vorherzusagen, dass der Zyklus (für immer) fortgesetzt wird. In diesem Fall sagt der Prozessor fälschlicherweise nur einen Zweig pro Zyklus voraus.
Es gibt andere gängige Beispiele. Wenn Sie auf den Inhalt eines Arrays zugreifen, fügen viele Programmiersprachen "gebundene Prüfung" hinzu - eine versteckte Überprüfung der Richtigkeit des Index, bevor Sie auf den Wert des Arrays zugreifen. Wenn der Index falsch ist, wird ein Fehler generiert, andernfalls wird der Code weiterhin wie gewohnt ausgeführt. Grenzkontrollen sind vorhersehbar, da in einer normalen Situation alle Zugriffsvorgänge korrekt sein sollten. Folglich sollten die meisten Prozessoren das Ergebnis nahezu perfekt vorhersagen.
Was passiert, wenn eine Verzweigung schwer vorherzusagen ist?
Innerhalb des Prozessors müssen alle Anweisungen, die ausgeführt wurden, sich aber auf dem falsch vorhergesagten Zweig befinden, abgebrochen und die Berechnungen neu gestartet werden. Es ist zu erwarten, dass wir für jeden Verzweigungsvorhersagefehler mehr als 10 Zyklen bezahlen. Aus diesem Grund kann sich die Ausführungszeit des Programms erheblich erhöhen.
Schauen wir uns einen einfachen Code an, in dem wir zufällige Ganzzahlen in ein Ausgabearray schreiben:
while (howmany != 0) { out[index] = random(); index += 1; howmany--; }
Wir können durchschnittlich für 3 Zyklen eine geeignete Zufallszahl erzeugen. Das heißt, die Gesamtverzögerung des Zufallszahlengenerators kann gleich 10 Zyklen sein. Unser Prozessor ist jedoch superskalar, dh wir können mehrere Zufallszahlenberechnungen gleichzeitig durchführen. Daher können wir ungefähr alle 3 Zyklen eine neue Zufallszahl generieren.
Ändern wir die Funktion ein wenig, sodass nur ungerade Zahlen in das Array geschrieben werden:
while (howmany != 0) { val = random(); if( val is an odd integer ) { out[index] = val; index += 1; } howmany--; }
Sie könnten naiv denken, dass diese neue Funktion schneller sein könnte. Und in der Tat, weil wir im Durchschnitt nur eine von zwei ganzen Zahlen aufzeichnen müssen. Es gibt eine Verzweigung im Code, aber um die Parität einer Ganzzahl zu überprüfen, überprüfen Sie einfach ein Bit.
Ich habe diese beiden Funktionen in C ++ auf einem Skylake-Prozessor verglichen:
Die zweite Funktion funktioniert etwa fünfmal länger!
Kann hier etwas behoben werden? Ja, wir können die Verzweigung einfach beseitigen. Eine ungerade ganze Zahl kann so charakterisiert werden, dass sie ein bitweises logisches UND mit einem Wert von 1 gleich eins ist. Der Trick besteht darin, den Array-Index nur dann um eins zu erhöhen, wenn der Zufallswert ungerade ist.
while (howmany != 0) { val = random(); out[index] = val; index += (val bitand 1); howmany--; }
In dieser neuen Version schreiben wir immer einen zufälligen Wert in das Ausgabearray, auch wenn dies nicht erforderlich ist. Auf den ersten Blick ist dies eine Verschwendung von Ressourcen. Es bewahrt uns jedoch vor falsch vorhergesagten Zweigen. In der Praxis entspricht die Leistung fast der des Originalcodes und ist viel besser als bei der Version mit Verzweigungen:
Könnte der Compiler dieses Problem selbst lösen? Im Allgemeinen lautet die Antwort nein. Manchmal haben Compiler Optionen, um Verzweigungen vollständig zu eliminieren, selbst wenn der Quellcode eine
if-then enthält. Beispielsweise kann die Verzweigung manchmal durch "bedingte Verschiebung" oder andere arithmetische Tricks ersetzt werden. Solche Tricks sind jedoch für die Verwendung in Compilern unsicher.
Eine wichtige Schlussfolgerung: Eine fälschlicherweise vorhergesagte Verzweigung ist kein unbedeutendes Problem, sondern hat einen großen Einfluss.
Mein Quellcode ist auf Github .
Das Erstellen von Benchmarks ist eine schwierige Aufgabe: Prozessoren lernen, Verzweigungen vorherzusagen
[Anmerkung transl .: Dieser Teil war ein
separater Artikel vom Autor, aber ich habe ihn mit dem vorherigen kombiniert, weil sie ein gemeinsames Thema haben.]
Im vorherigen Teil habe ich gezeigt, dass der größte Teil der Ausführungszeit eines Programms durch eine falsche Verzweigungsvorhersage verursacht werden kann. Mein Benchmark war das Schreiben von 64 Millionen zufälligen Ganzzahlwerten in ein Array. Als ich versuchte, nur ungerade Zufallszahlen aufzuzeichnen, nahm die Leistung aufgrund fehlerhafter Vorhersagen stark ab.
Warum habe ich 64 Millionen Ganzzahlen verwendet, anstatt beispielsweise 2000? Wenn Sie nur einen Test ausführen, spielt dies keine Rolle. Was passiert jedoch, wenn wir viele Versuche unternehmen? Die Anzahl der fälschlicherweise vorhergesagten Zweige sinkt schnell auf Null. Die Leistung des Intel Skylake-Prozessors spricht für sich:
Wie aus den folgenden Grafiken ersichtlich ist, wird das "Training" weiter fortgesetzt. Allmählich sinkt der Anteil falsch vorhergesagter Zweige auf etwa 2%.
Das heißt, wenn wir weiterhin die Zeit messen, die dieselbe Aufgabe benötigt, wird sie immer kürzer, weil der Prozessor lernt, das Ergebnis besser vorherzusagen. Die Qualität des „Trainings“ hängt vom jeweiligen Prozessormodell ab, es wird jedoch erwartet, dass neuere Prozessoren besser lernen.
Die neuesten AMD-Serverprozessoren lernen, die Verzweigung (innerhalb von 0,1%) in weniger als 10 Versuchen nahezu perfekt vorherzusagen.
Diese ideale Vorhersage für AMD Rom verschwindet, wenn die Anzahl der Werte im Problem von 2000 auf 10.000 erhöht wird: Die beste Vorhersage ändert sich von einem Bruchteil der Fehler von 0,1% auf 33%.
Sie sollten wahrscheinlich das Benchmarking von Code mit Verzweigung für kleine Aufgaben vermeiden.
Mein Github-Code .
Anerkennung : AMD Rome-Werte von Vel Erwan.
Zusätzliche Lektüre :
Ein Fall für (teilweise) TAgged GEometric History Length Branch-Vorhersage (Seznec et al.)