Sprungvorhersage
aus Wikipedia, der freien Enzyklopädie
Die Sprungvorhersage wird in der (Mikro-)Rechnerarchitekur verwendet und behandelt das Problem von Mikroprozessoren, alle Stufen ihrer Pipeline möglichst immer und sinnvoll auszulasten.
Inhaltsverzeichnis |
[Bearbeiten] Übersicht
Unter Sprungvorhersage (auch Verzweigungsvorhersage) versteht man:
- Die Vorhersage, ob ein bedingter Sprung ausgeführt wird
- Die Zieladresse eines Sprunges zu ermitteln
Es existieren 2 Arten von Sprüngen:
- bedingter Sprung (z. B. von einer IF-Abfrage)
- unbedingter Sprung (z. B. GOTO, RETURN, Method-Calls)
Das Problem: Normalerweise werden der Pipeline die Daten sequentiell, wie sie kommen, zugeführt. Wird aber ein Sprung ausgeführt (dies wird erst später in der Pipeline erkannt), sind alle Daten, die nach ihm in die Pipeline geraten sind, wertlos und müssen verworfen werden (Performanceverlust).
Das Ziel: Möglichst frühes Erkennen eines Sprungbefehls UND Erkennen seiner Sprungzieladresse, damit gleich die Daten der Zieladresse dem Sprungbefehl in die Pipeline folgen können.
[Bearbeiten] Funktionsweise
Die Sprungvorhersage lässt sich in zwei Arten unterscheiden.
[Bearbeiten] Statische Sprungvorhersage
Die statische Sprungvorhersage ändert ihre Vorhersage während das Programmablaufs nicht. Sie erreicht dadurch nur eine Vorhersagegenauigkeit von 55%-80%. Diese Technik geht von bekannten Tatsachen aus, z. B. dass Schleifen häufig Sprünge ausführen, währenddessen bei Auswahlverfahren dies weniger häufig vorkommt. Manche Compiler unterstützen den Mechanismus auch mit speziellen Flags im Befehlscode (Vorhersage wird beim Kompilieren eingebaut).
[Bearbeiten] Dynamische Sprungvorhersage
Die dynamische Sprungvorhersage geschieht nur zur Laufzeit. Sie benutzt multiple Techniken zur Erzeugung einer Vorhersage. Ihre Vorhersagegenauigkeit liegt bei bis zu 98%. Um einen Sprungbefehl zu erkennen, wird die Befehlsadresse des Sprungbefehls herangezogen.
[Bearbeiten] Per-Address History
Wird ein Sprung erkannt, so wird dieser protokolliert und für weitere Sprungvorhersagen herangezogen (bei Schleifen werden Sprünge i. d. R. öfter vorkommen – so muss der Sprung nur einmal erkannt werden). Implementiert wird diese Technik z. B. von der Branch History Table (BHT).
[Bearbeiten] Global History
Bei der globalen Vorgeschichte wird der komplette Pfad, den ein Programm genommen hat, protokolliert (über eine begrenzte Anzahl Schritte hinweg). Erkennt man nun, dass zwei Sprünge sich ähneln, könnten sie den selben Pfad nehmen - somit ist der Logik u. U. schon ein Teil dessen bekannt, was das Programm in Zukunft machen wird. Gespeichert wird der Pfad meist in einem Schieberegister. Für die Vorhersagen benutzt man entweder einen Zähler oder einen (trägen) Automaten.
[Bearbeiten] Statische Sprungvorhersage-Techniken
[Bearbeiten] Stall / Freeze
Diese Technik hält einfach die ganze Pipeline kurz an. Wird in der ID-Stage ein Sprungbefehl festgestellt, wird die Pipeline solange angehalten (stalled/freezed), bis man in der EX-Stage weiß, ob der Sprung ausgeführt wird.
- Sprung wird nicht ausgeführt: mache normal weiter
- Sprung wird ausgeführt: Setze Programm-Zähler auf Sprungzieladresse und fülle die Pipeline mit den Instruktionen, die sich am Sprungziel befinden.
[Bearbeiten] Predict-Taken
Geht einfach davon aus, dass jeder bedingte Sprung auch ausgeführt wird. D. h. wir stellen in der ID-Stage fest, dass es ein Sprungbefehl ist und beginnen schon mal die Zieladresse zu bestimmen und in die dortigen Daten gleich in die Pipeline als Folgeinstruktionen zu laden. Wird in der EX-Stage allerdings festgestellt, dass der Sprung doch nicht stattfindet, war die vorherige Arbeit umsonst (verwendet bei Schleifen).
[Bearbeiten] Predict-Not-Taken
Geht davon aus, dass jeder bedingte Sprung nicht ausgeführt wird und macht normal weiter. Dies bedeutet (sollte der Sprung wirklich nicht ausgeführt werden) einen guten Performancegewinn. Sollte in der EX-Stage festgestellt werden, dass der Sprung wider Erwarten doch ausgeführt wird, muss die Folge-Instruktion angehalten, der PC auf die Sprungzieladresse gestellt und damit dann die Pipeline gefüllt werden (verwendet bei Auswahlverfahren).
[Bearbeiten] Delayed Branches
Wird in der ID-Stage ein Sprungbefehl festgestellt, wissen wir ja noch nicht, ob er ausgeführt wird oder nicht. Daher bekommt jeder Sprungbefehl einen (oder mehrere) Delay-Slots, die mit unabhängigen, sinnvollen Instruktionen gefüllt werden können. Findet der Sprung nicht statt, wird nach dem Delay-Slot normal weitergemacht. Findet der Sprung statt, werden die Daten der Sprungzieladresse nach den Delay-Slot Instruktionen ausgeführt. Welche Daten in die Delay-Slots kommen können, ist Aufgabe des Compilers/Assemblerprogrammierers.
[Bearbeiten] Dynamische Sprungvorhersage-Techniken
[Bearbeiten] Branch History Table (BHT)
Die BHT versucht, wie ihr Name schon sagt, ebenfalls die letzten Sprünge mitzuprotokollieren. Dazu verwendet sie einen Teil der Sprungbefehlsadresse als Hashindex. Im allgemeinen nimmt man dafür den niederwertigen Adressanteil. Diese Adressteile können natürlich nicht immer eindeutig sein, so dass es Kollisionen geben kann (mehrere unterschiedliche Sprünge belegen denselben Platz in der Tabelle).
Die Tabelle wird nach jedem Sprung aktualisiert.
[Bearbeiten] n-Bit träger Automat
Ist ein endlicher Automat, der Vorhersageinformationen liefert.
- 1-Bit Automat:
Wird ein gespeicherter Sprung richtig vorhergesagt, wird dessen Bit von 0 auf 1 gesetzt (Speichern der Richtigkeit von Vorhersagen). Ein Problem ist aber, dass er alternierende Sprünge nicht berücksichtigt (Sprünge, die z. B. nur jedes 2. Mal stattfinden, würden immer wieder auf 0 gesetzt werden). Die Lösung hierfür ist ein n-Bit Automat.
- n-Bit träger Automat:
Dieser setzt das Korrektheitsbit erst nach den n Fehlschlägen auf 0. Im Allgemeinen wird n=2 verwendet. (Tests haben gezeigt, dass n>2 keine größeren Performancesteigerungen mehr bringt)
[Bearbeiten] gshare
gshare garantiert eine Vorhersagegenauigkeit von über 99%. Hierbei werden der Adressteil und die Sprungsignatur mit XOR verknüpft und in eine Tabelle abgelegt. Die Informationen der Tabelle werden dann zur Sprungvorhersage herangezogen. gshare kombiniert somit Per-Address History mit Global History. Da hier XOR als Hashverfahren genommen wird, können wieder Kollisionen entstehen.
Dieses Verfahren findet z. B. im Pentium 4 Anwendung.
[Bearbeiten] Übersicht
-
Verfahren Genauigkeit Hardwareaufwand Zeitverhalten statisch zur Laufzeit -- ++ ++ statisch zur Compilezeit - ++ ++ Per-Address History + + + Global History + + + gshare ++ + +
[Bearbeiten] Sprungzielvorhersage-Techniken
Besser als eine bloße Sprungvorhersage ist gleich eine Sprungzielvorhersage. Sobald man in der ID-Stage erkennt, dass es sich um einen Sprung handelt, kann man prüfen, ob dieser Sprung schonmal stattfand und ggf. sein Sprungziel aus einem Puffer holen. Somit kann man den Programmzähler sofort auf dieses Sprungziel stellen und die dortigen Instruktionen in die Pipeline laden.
[Bearbeiten] Branch Target Buffer (BTB)
Der BTB (auch Sprungzielpuffer oder Branch-target Adress Cache (BTAC)) speichert genommene (tatsächlich ausgeführte) Sprünge in einer Tabelle ab.
Diese Tabelle enthält:
- Vorhersageinformationen
- Zieladressen
- Tags
Der BTB liefert immer eine Adresse zurück. Wird ein unbekannter Sprung abgefragt, so liefert er einfach die Folgeadresse. Wird aber ein bekannter Sprung abgefragt, so liefert er die Zieladresse.
Der BTB kann nicht immer korrekt arbeiten. Da z. B. RETURN-Anweisungen variable Zieladressen haben (Moving Targets), kann der BTB zu einem korrekten Sprung eine falsche Zieladresse abspeichern. Da in modernen Programmierhochsprachen objektorientiert programmiert wird, kommt es zu häufigen Methodenaufrufen und somit zu vielen Moving Targets. Um diese in der Hinsicht fatale Schwäche zu beheben, werden BTBs um einen Call-Return Stapel erweitert.
[Bearbeiten] Call-Return Stapel
Dieser Stapel speichert alle Return-Adressen nach dem LIFO Prinzip. Weiterhin wird von speziellen Call - und Return Befehlen im Befehlssatz ausgegangen (wird also von einem normalen Sprung unterschieden).
Sonderbehandlung beider Sprünge im Branch Target Buffer (BTB).
- Call: Bei Aufruf wird in dem BTB zusätzlich die Adresse des Return-Befehls abgelegt.
- Return: Extra Kennzeichnung des Befehls im BTB. Bei Aufruf eines so gekennzeichneten Befehls im BTB wird statt der Zieladresse aus dem BTB die oberste Adresse des Call-Return Stacks genommen.
Somit kann gewährleistet werden, dass immer die richtige Rücksprungadresse benutzt wird.
[Bearbeiten] Weblinks
- Ausarbeitung zu den grundlegendsten Themen der Rechnerarchitektur (Überblick) (Kapitel 7 - Branch Prediction)
