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

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.

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.

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.

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.

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.

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