Sprungvorhersage

Die Sprungvorhersage ermöglicht es einem Pipelined-Prozessor, das Ergebnis und das Ziel eines Sprungs zu erraten, bevor dieser aufgelöst wird. Dadurch kann er Anweisungen entlang des wahrscheinlichen Pfades weiter abrufen und ausführen, anstatt anzuhalten.

Definition

Sprungvorhersage ist eine mikroarchitektonische Technik, die vorhersagt, ob ein bedingter Sprung genommen wird und wohin er führt. Dies ermöglicht es dem Prozessor, Anweisungen entlang des vorhergesagten Pfades spekulativ abzurufen und auszuführen und diese Arbeit zu verwerfen, wenn sich die Vorhersage als falsch erweist.

Scope

Dieses Thema behandelt Techniken zur Vorhersage des Kontrollflusses: statische Vorhersage, dynamische Prädiktoren basierend auf der Sprunghistorie (Ein- und Zwei-Bit-Zähler, korrelierende und Turnierprädiktoren), Sprungzielpuffer und die Kosten von Fehlvorhersagen. Es wird behandelt, wie die Vorhersage tiefe Pipelines und Spekulation ermöglicht. Ausgeschlossen sind die umfassendere spekulative Ausführungsmaschinerie und Wiederherstellung (Out-of-Order-Ausführung) sowie die grundlegende Kontrollgefahr selbst (Pipelining und Hazards).

Core questions

• Warum blockieren Sprünge tiefe Pipelines, und wie hilft die Vorhersage dabei?
• Wie nutzen dynamische Prädiktoren die Sprunghistorie, um die Genauigkeit zu verbessern?
• Was ist ein Sprungzielpuffer und was leistet er?
• Was ist die Strafe einer Fehlvorhersage und wie wird sie behoben?

Key concepts

• statische vs. dynamische Vorhersage
• Ein- und Zwei-Bit-Sättigungszähler
• Sprunghistorie und Korrelation
• Turnierprädiktoren
• Sprungzielpuffer
• Fehlvorhersagestrafe
• spekulativer Abruf

Key theories

Historienbasierte dynamische Vorhersage

Sprungergebnisse korrelieren stark mit ihrem eigenen und dem vergangenen Verhalten anderer Sprünge; Prädiktoren, die die Historie in Sättigungszählern aufzeichnen und lokale und globale Historie kombinieren (korrelierende und Turnierprädiktoren), erreichen eine sehr hohe Genauigkeit.

Mechanisms

Ein Prädiktor konsultiert die Historie, um die Richtung eines Sprungs zu erraten, und einen Sprungzielpuffer, um dessen Ziel zu erraten, wodurch das Frontend spekulativ weiter abrufen kann. Zwei-Bit-Sättigungszähler verfolgen die jüngsten Ergebnisse pro Sprung; korrelierende Prädiktoren fügen eine globale Historie hinzu; Turnierprädiktoren wählen dynamisch zwischen lokalen und globalen Schemata. Bei einer Fehlvorhersage werden die spekulativen Anweisungen verworfen und der Abruf am korrekten Adresse neu gestartet, was eine Strafe proportional zur Pipeline-Tiefe nach sich zieht.

Clinical relevance

Eine genaue Sprungvorhersage ist für moderne tiefe, breite Pipelines unerlässlich: Da Fehlvorhersagen viele Zyklen kosten, sind Prädiktoren mit einer Genauigkeit von über 95 Prozent erforderlich, um eine hohe Leistung aufrechtzuerhalten. Sprungvorhersagestrukturen sind auch sicherheitsrelevant geworden, da ihr spekulatives Verhalten transienten Ausführungsangriffen wie Spectre zugrunde liegt.

History

Einfache statische und Ein-Bit-dynamische Prädiktoren wichen Zwei-Bit-Sättigungszählern, dann korrelierenden und zweistufigen adaptiven Prädiktoren in den frühen 1990er Jahren und Turnier- und neuronalen Prädiktoren in Hochleistungskernen. Mit zunehmender Pipeline-Tiefe wuchs die Komplexität der Prädiktoren entsprechend, um Fehlvorhersagestrafen erträglich zu halten.

Key figures

• James E. Smith
• Yale Patt
• Tse-Yu Yeh
• John L. Hennessy

Seminal works

• hennessy2019
• patterson2020

Frequently asked questions

Was passiert, wenn ein Sprung falsch vorhergesagt wird?

Der Prozessor hat spekulativ Anweisungen auf dem falschen Pfad abgerufen und teilweise ausgeführt. Bei Erkennung der Fehlvorhersage verwirft (squasht) er diese spekulative Arbeit und startet den Abruf vom korrekten Ziel neu, wobei er eine Strafe zahlt, die ungefähr proportional zur Tiefe der Pipeline ist.

Wie genau sind moderne Sprungprädiktoren?

Moderne dynamische Prädiktoren erreichen typischerweise eine Genauigkeit von über 95 Prozent bei gängigen Arbeitslasten, indem sie lokale und globale Sprunghistorie kombinieren. Diese hohe Genauigkeit macht tiefe, breite Pipelines lohnenswert, da jede Fehlvorhersage viele Zyklen spekulativer Arbeit verschwendet.