Warum ist ein bedingter Umzug nicht anfällig für Branch Prediction Failure?

77

Nachdem ich diesen Beitrag gelesen hatte (Antwort auf StackOverflow) (im Optimierungsabschnitt), habe ich mich gefragt, warum bedingte Verschiebungen nicht für Branch Prediction Failure anfällig sind. Ich habe hier einen Artikel über Cond Moves gefunden (PDF von AMD) . Auch dort beanspruchen sie den Leistungsvorteil von cond. bewegt sich. Aber warum ist das so? Ich sehe es nicht Zum Zeitpunkt der Auswertung dieses ASM-Befehls ist das Ergebnis des vorhergehenden CMP-Befehls noch nicht bekannt.

Martijn Courteaux
quelle
7
Übrigens möchten Sie vielleicht wissen, dass cmov nach meiner Erfahrung mit Intel Core2- und Core-i7-CPUs nicht immer ein Leistungsgewinn ist. In meinen Tests war der Zweig selbst besser, solange die Vorhersagerate über ca. 99% lag. Das mag hoch klingen, ist aber bei Intels Branch Predictors ziemlich verbreitet. Dies geschieht insbesondere bei Verzweigungen innerhalb von Schleifen: Sagen wir, eine Verzweigung, die 1000-mal iteriert, und beim 999. Mal macht sie etwas anderes. Ein solcher Fall wäre immer effizienter, wenn ein bedingter Sprung anstelle von cmov verwendet würde.
jstine
1
Der PDF-Link erfordert derzeit eine Autorisierung.
Leez
Für C ++ - Compiler sind sie gleich: Siehe beigefügtes Bild
Nikolai Trandafil
1
@NikolaiTrandafil: Das hängt völlig vom ausgewählten Compiler, den von Ihnen aktivierten Kompilierungsflags und der Ziel-ISA ab.
Martijn Courteaux
Verwandte: Wird CMOVcc als Verzweigungsanweisung betrachtet? - Nein, es ist eine ALU-Auswahloperation. Die Antwort enthält einige Links zu Details zum Leistungskompromiss.
Peter Cordes

Antworten:

64

Falsch vorhergesagte Filialen sind teuer

Ein moderner Prozessor führt im Allgemeinen zwischen einem und drei Befehlen pro Zyklus aus, wenn die Dinge gut laufen (wenn er nicht auf Datenabhängigkeiten wartet, bis diese Befehle aus vorherigen Befehlen oder aus dem Speicher eintreffen).

Die obige Aussage gilt überraschend gut für enge Schleifen, aber dies sollte Sie nicht für eine zusätzliche Abhängigkeit blind machen, die verhindern kann, dass ein Befehl ausgeführt wird, wenn sein Zyklus kommt: Damit ein Befehl ausgeführt werden kann, muss der Prozessor mit dem Abrufen und Decodieren begonnen haben es 15-20 Zyklen vor.

Was soll der Prozessor tun, wenn er auf einen Zweig stößt? Das Abrufen und Decodieren beider Ziele wird nicht skaliert (wenn weitere Verzweigungen folgen, müsste eine exponentielle Anzahl von Pfaden parallel abgerufen werden). Der Prozessor holt und spekuliert also nur spekulativ einen der beiden Zweige.

Aus diesem Grund sind falsch vorhergesagte Zweige teuer: Sie kosten die 15 bis 20 Zyklen, die aufgrund einer effizienten Befehlspipeline normalerweise unsichtbar sind.

Bedingter Umzug ist nie sehr teuer

Ein bedingter Zug erfordert keine Vorhersage, daher kann er diese Strafe niemals haben. Es hat Datenabhängigkeiten, wie gewöhnliche Anweisungen. Tatsächlich weist eine bedingte Verschiebung mehr Datenabhängigkeiten auf als normale Anweisungen, da die Datenabhängigkeiten sowohl Fälle von "Bedingung wahr" als auch "Bedingung falsch" umfassen. Nach einer Anweisung , dass bedingt bewegt r1zu r2, deren Inhalte r2sowohl auf dem vorherigen Wert von scheinen zu hängen r2und auf r1. Ein gut vorhergesagter bedingter Zweig ermöglicht es dem Prozessor, genauere Abhängigkeiten abzuleiten. Es dauert jedoch in der Regel ein bis zwei Zyklen, bis Datenabhängigkeiten eintreffen, wenn sie überhaupt Zeit benötigen.

Beachten Sie, dass ein bedingter Wechsel vom Speicher zum Register manchmal eine gefährliche Wette ist: Wenn die Bedingung so ist, dass der aus dem Speicher gelesene Wert nicht dem Register zugewiesen wird, haben Sie auf nichts im Speicher gewartet. Die in Befehlssätzen angebotenen bedingten Verschiebungsbefehle werden jedoch typischerweise von Register zu Register registriert, wodurch dieser Fehler seitens des Programmierers verhindert wird.

Pascal Cuoq
quelle
1
Ich stimme mit allem überein, was Sie geschrieben haben (oder für mich zumindest akzeptabel erscheinen), mit Ausnahme der ersten Aussage. Können Sie näher erläutern, dass eine CPU in jedem Zyklus drei asm-Anweisungen ausführt?
Martijn Courteaux
4
@MartijnCourteaux Ein typischer moderner Desktop-Prozessor verfügt über alle Phasen seiner Pipeline, in denen etwa 3 Befehle verarbeitet werden können, was im besten Fall zu einem Durchsatz von 3 Befehlen / Zyklus führt. Die Decodierungsstufe kann beispielsweise 16 Bytes von Befehlen pro Zyklus decodieren: das sind typischerweise 3 Befehle. Es gibt auch genügend Ausführungseinheiten, um drei unabhängige Anweisungen in einem einzigen Zyklus zu verarbeiten. Details unter agner.org/optimize/microarchitecture.pdf ( übrigens eine hervorragende Referenz).
Pascal Cuoq
@MartijnCourteaux Zum Beispiel Seite 79: „Der Durchsatz des Restes der Pipeline beträgt normalerweise 4 Befehle pro Taktzyklus“ (aber Sie erhalten fast nie die theoretischen 4 Befehle pro Zyklus. Sogar 3 sind nur dann verfügbar, wenn der Algorithmus dies zulässt und Hand- benötigt). geschriebener, manuell ausgerichteter Code für ein bestimmtes Prozessormodell)
Pascal Cuoq
Es kann also 4 Befehle dekodieren, aber 2 oder 3 im gleichen Zyklus verarbeiten, je nachdem, wie viel Glück wir mit dem Algorithmus haben.
Martijn Courteaux
Es können nur 4 Anweisungen dekodiert werden, wenn sie in 16 Bytes passen. Das hängt also davon ab, wie viel Glück Sie mit der Länge der Anweisungen haben, die Sie für einen Start benötigen. Und es kann nur bis zu 4 ausführen, wenn es alle notwendigen Einheiten hat, um sie alle auszuführen (wenn dies Ihr Ziel ist, müssen möglicherweise Gleitkomma- und Ganzzahlberechnungen gemischt werden, um dies zu erreichen), und wenn die Eingabe von eins nicht die Ausgabe von ist Ein weiterer. Wenn Sie wirklich interessiert sind, können Sie sich diese Technik ansehen, um die Feinkornparallelität zu erhöhen, aber ich sollte Sie warnen, dass sie die Dinge in der Praxis selten beschleunigt: en.wikipedia.org/wiki/Software_pipelining
Pascal Cuoq
48

Es dreht sich alles um die Anweisungspipeline . Denken Sie daran, dass moderne CPUs ihre Anweisungen in einer Pipeline ausführen, was zu einer erheblichen Leistungssteigerung führt, wenn der Ausführungsfluss von der CPU vorhersehbar ist.

cmov

    add     eax, ebx
    cmp     eax, 0x10
    cmovne  ebx, ecx
    add     eax, ecx

Zum Zeitpunkt der Auswertung dieses ASM-Befehls ist das Ergebnis des vorhergehenden CMP-Befehls noch nicht bekannt.

Vielleicht, aber die CPU weiß immer noch, dass der Befehl nach dem cmovBefehl direkt danach ausgeführt wird, unabhängig vom Ergebnis des Befehls cmpund cmov. Der nächste Befehl kann somit sicher vorzeitig abgerufen / decodiert werden, was bei Verzweigungen nicht der Fall ist.

Die nächste Anweisung könnte sogar vor der Ausführung ausgeführt werden cmov(in meinem Beispiel wäre dies sicher).

Ast

    add     eax, ebx
    cmp     eax, 0x10
    je      .skip
    mov     ebx, ecx
.skip:
    add     eax, ecx

In diesem Fall muss der Decoder der CPU, wenn er dies sieht je .skip, entscheiden, ob das Vorabrufen / Decodieren von Befehlen entweder 1) vom nächsten Befehl oder 2) vom Sprungziel fortgesetzt werden soll. Die CPU wird davon ausgehen, dass diese bedingte Vorwärtsverzweigung nicht stattfinden wird, sodass der nächste Befehl mov ebx, ecxin die Pipeline aufgenommen wird.

Ein paar Zyklen später wird das je .skipausgeführt und der Zweig genommen. Verdammt! Unsere Pipeline enthält jetzt zufälligen Junk, der niemals ausgeführt werden sollte. Die CPU muss alle zwischengespeicherten Anweisungen leeren und neu starten .skip:.

Dies ist der Leistungsverlust von falsch vorhergesagten Zweigen, der niemals auftreten kann, cmovda er den Ausführungsfluss nicht verändert.

Martin
quelle
4
Ich kann herausfinden, dass dies wahrscheinlich eine Intel-Syntax mit Opcode, Ziel, Quelle ist, aber es wäre großartig, wenn Sie Ihren Assembly-Standard explizit erwähnen würden.
Zan Lynx
18

Das Ergebnis ist zwar noch nicht bekannt, aber wenn andere Umstände dies zulassen (insbesondere die Abhängigkeitskette), kann die CPU Anweisungen gemäß den Anweisungen neu anordnen und ausführen cmov. Da es sich nicht um eine Verzweigung handelt, müssen diese Anweisungen in jedem Fall ausgewertet werden.

Betrachten Sie dieses Beispiel:

cmoveq edx, eax
add ecx, ebx
mov eax, [ecx]

Die beiden folgenden Anweisungen cmovhängen nicht vom Ergebnis des ab cmov, sodass sie auch ausgeführt werden können, während das cmovselbst ansteht (dies wird als Ausführung außerhalb der Reihenfolge bezeichnet ). Auch wenn sie nicht ausgeführt werden können, können sie abgerufen und dekodiert werden.

Eine Verzweigungsversion könnte sein:

    jne skip
    mov edx, eax
skip:
    add ecx, ebx
    mov eax, [ecx]

Das Problem hierbei ist, dass sich der Kontrollfluss ändert und die CPU nicht klug genug ist, um zu erkennen, dass sie die übersprungene movAnweisung einfach "einfügen" kann, wenn der Zweig als genommen falsch vorhergesagt wurde. Stattdessen wirft sie alles weg, was sie nach dem Zweig getan hat, und startet neu von Grund auf neu. Hier kommt die Strafe her.

Narr
quelle
2
Ich kann herausfinden, dass dies wahrscheinlich eine Intel-Syntax mit Opcode, Ziel, Quelle ist, aber es wäre großartig, wenn Sie Ihren Assembly-Standard explizit erwähnen würden.
Zan Lynx
3

Sie sollten diese lesen. Suchen Sie mit Fog + Intel einfach nach CMOV.

Linus Torvalds Kritik an CMOV um 2007
Agner Fogs Vergleich der Mikroarchitekturen Referenzhandbuch zur Optimierung von
Intel® 64- und IA-32-Architekturen

Kurze Antwort, korrekte Vorhersagen sind "kostenlos", während bedingte Verzweigungsvorhersagen auf Haswell 14 bis 20 Zyklen kosten können. CMOV ist jedoch niemals kostenlos. Trotzdem denke ich, dass CMOV jetzt viel besser ist als damals, als Torvalds schimpfte. Es gibt keinen einzigen, der für alle Zeiten korrekt ist, und alle Prozessoren antworten jemals.

Olsonist
quelle
3
Nein, cmovist immer noch eine Datenabhängigkeit, sodass durch Schleifen übertragene Abhängigkeitsketten erstellt werden können, die die Verzweigungsvorhersage verborgen hätte. Intel Broadwell / Skylake dekodieren es in ein einzelnes UOP anstelle von 2 (Haswell und früher), sodass es jetzt etwas günstiger ist. Der UOP-Cache von Sandybridge und höher bedeutet, dass die Strafe für den Decodierungsdurchsatz für Multi-UOP-Anweisungen normalerweise ebenfalls kein Faktor ist. Der grundlegende Unterschied zwischen einer Daten- und einer Steuerelementabhängigkeit wird dadurch jedoch nicht geändert. Außerdem verfügt x86 cmovimmer noch nicht über ein Formular mit einem unmittelbaren Operanden und ist daher x = x<3 ? x : 3immer noch umständlich zu implementieren.
Peter Cordes
1
Ich denke auch, dass Sie einen Bearbeitungsfehler haben in: "CMOV ist nie sehr teuer, es sei denn, Zweigvorhersagen falsch". Dieser Satz ist totaler Unsinn, da cmov nicht vorhergesagt wird. Das ist , warum es nicht von falscher Vorhersage leiden kann.
Peter Cordes
Vielen Dank für die nützlichen Links.
Maxim Masiutin
Ein weiterer Link, der von Interesse sein könnte: gcc.gnu.org/bugzilla/show_bug.cgi?id=56309
Max Barraclough
0

Ich habe diese Illustration von [Peter Puschner et al.] Folie, die erklärt, wie sie sich in Einzelpfadcode umwandelt und die Ausführung beschleunigt.

Geben Sie hier die Bildbeschreibung ein

KALTES EIS
quelle
1
Eine Anweisung zum Vergleichen und Prädikieren des nächsten wäre nett, aber echte Architekturen benötigen normalerweise auch 3 Anweisungen für die prädizierte Sequenz. (Außer ARM 32-Bit, das cmp/ könnte swplt, wenn es eine Swap / Exchange-Anweisung hätte.) Wie auch immer, moderne CPUs haben im Allgemeinen keine Blasen von genommenen Zweigen, sondern Blasen von falschen Vorhersagen : stackoverflow.com/questions/11227809/… . In Code mit hohem Durchsatz können korrekt vorhergesagte genommene Verzweigungen die Decodierungs- / Front-End-Bandbreite jedoch etwas reduzieren.
Peter Cordes