Home

Impressum

kreissl.info[rmation science]

best practices

Branch Prediction

Kapitel 7 - Branch Prediction

Jump / Branch Problematik
Statische und Dynamische Sprungvorhersage
BHT und BTB
Wie arbeitet Second Chance?
Wie werden Exeptions behandelt?

Control Hazards (Jump / Branch Problematik)

Sprungbefehle stellen einen Dorn im Auge einer jeden Pipeline dar, da diese besondere Vorkehrungen erfordern. Da das Ziel eines Sprungbefehles oft erst festgestellt werden muss, liegt diese Adresse erst ab der MEM ACCESS Phase bereit. Somit kann das erneute Laden des Programmcounters auch erst in dieser Phase geschehen. So verzögert sich das Holen des nächsten Befehles um einige Takte.

Durch eine Optimierung der Pipeline kann zwar die stall-Phase verkleinert, aber nicht ausgeschlossen werden. (durch Verlegung des Sprungbedingungstests in die Decode-Phase)

Welche Methoden gibt es zur Reduzierung von Sprungverlusten?

Predict Not Taken / Predict-Taken (fixed prediction)
Objektcode basiert (statisch)
dynamisch Brach-Prediction mit History Buffern (correlating / non-correlating)
Delayed-Branch

Wie funktioniert die Predict-Not-Taken bzw. Predict-Taken Methodik?

Hier wird nichts weiter gemacht als entweder alle Sprünge voreingestellt abzulehnen oder alle Sprünge ersteinmal ohne Gewähr duchzuführen. Allgemeine Programmstatistiken sagen aus, dass mehr bedingte Sprünge ausgeführt als abgewiesen werden.

Wie funktioniert die Delayed-Branch Methode?

Hier wird ein sprungunabhängiger Befehl in den Delay Slot eingeschleust. Dies muss somit schon von den Compilerbauern berücksichtigt werden. Um diese Bedingung zu Umgehen wird die "Cancelling Branches"-Technik eingesetzt. Im Mittel werden dann trotzdem die Branch-Verluste verringert. Durch ein zusätzliches Bit im Befehlscode gibt der Compiler die wahrscheinlichste Sprungrichtung an. Nun kann entsprechend dieser Annahme ein Befehl in den Delay Slot eingefügt werden, der nur gültig ist, wenn der Sprung richtig vorhergesagt war. Falls nicht wird der Delay-Slot-Befehl abgebrochen (gecancelt).

Dynamische Branch-Prediction

Um Wartezeiten durch bedingte Sprünge zu vermeiden, sollte das Sprungziel schon mit dem Ende der Fetch-Phase zur Verfügung stehen. Es gibt zwei Ansätze

Sprungzielspeicher (branch-target-buffer = BTB)
Sprungvorhersage-Puffer (Branch History Table = BHT)

Wie arbeitet eine Branch History Table?

In dieser Tabelle wird im Grunde nur durch ein Bit (oder mehr) vermerkt, ob ein Sprung durchgeführt wurde oder nicht. Als Index der Tabelle dient der niederwertige Teil der Adresse des dazugehörigen Sprungbefehls. Nun kann die Pipeline in der Fetchphase nach einem eventuell vorhandenen Eintrag schauen und diesen als Entscheidungsgrundlage nehmen.

Welchen Nachteil hat die 1-Bit Sprungvorhersage?

Es wird nicht nur bei einem Schleifenaustritt der Sprung falsch vorhergesagt, sondern auch die erste Vorhersage bei erneuter Verwendung der Schleife.

Wie arbeitet die 2-Bit-Sprungvorhersage mit BHT?

Durch einen einfachen Zähler kann man den Nachteil der 1-Bit-Vorhersage minimieren. Hier wird die Vorhersage erst geändert, wenn sie zweimal falsch war. Es hat sich gezeigt, daß durch Zähler mit mehr als 2 Bit sich die Performance nicht weiter signifikant erhöhen läßt.

2-Bit-Sprungvorhersage

Wie arbeitet der Branch-Target-Buffer?

Hier wird die Zieladresse eines gemachten Sprungs direkt gespeichert, um diese gegebenfalls ohne Verzögerung wiederzuverwenden. So kann bei einem Hit (Index stimmt mit Befehlsadresse überein) sofort der Instruction Counter mit der dazugehörigen Sprungadresse geladen werden).

Exeptions

Exeptions unterbrechen den Programmablauf Aufgrund verschiedenster Fehler oder Anforderungen, wie Softwareinterrupts, Page Faults oder anderen Verletzungen. Bei synchronen Exeptions treten die Fehler stehts an der gleichen Programmstelle auf. Asynchrone werden durch externe Geräte ausgelöst und können nach dem laufenden Befehl ausgeführt werden.

Was sind Precice Exeptions?

Sind Exeptions, welche garantieren, dass die Exeptions direkt nach oder während des Befehles ausgeführt werden und kein Folgebefehl vorher abgearbeitet wird.

Zusammenfassung der Sprungvorhersage

Sprungvorhersage ist extrem wichtig für Pipelining und Superskalarität, um stalls und Verzögerungen zu minimieren. Bei statischer Vorhersage werden Rückwärtssprünge meist erst durchgeführt und Vorwärtssprünge nicht. Wurde ein Sprung falsch vorhergesagt, muss die angefangene Instruktion rückgängig gemacht werden, was aufwendig ist. Deshalb gibt es ausgeklügelte Verfahren für die Branch Prediction.

Statische Sprungvorhersage

Es werden Compiler benutzt, die spezielle Sprungbefehle mitführen, welche ein Bit für die Sprungvorhersage enthalten. Da der Compiler ja weiß, wie oft eine Schleife durchlaufen wird, ist das sehr effizient. Dies muss aber architektonisch von der Hardware unterstützt werden. Des Weiteren ist kein Speicher für die History Table notwendig, was es kostengünstiger macht. Statische Verfahren erreichen eine Trefferrate von 65 bis 85%, was für moderne CPU's mit Superpipelines zu wenig ist. Dynamische Verfahren erreichen Trefferraten bei der Vorhersage von 98% und mehr!

Dynamische Sprungvorhersage

Es gibt zwei grundlegende Methoden. BHT und BTB. Die Branch History Table (Branch Predicion Buffer) ist ein Cache, in der alle bedingten Sprünge protokolliert werden. ( bis zu mehereren Tausend) Einfachste Version enthält ein Valid-Bit (Branch taken oder nicht), welches durch den niederwertigen Teil der Sprungadresse adressiert wird. Kompliziere Implementationen arbeiten nach dem n-Wege Prinzip. Durch Second Chance kann dieses Verfahren noch verbessert werden. Der Branch Target Buffer speichert nicht nur die taken-Bits, sondern auch die Sprungzieladresse, um null Verluste bei wiederholtem Aufruf zu haben. Das setzt voraus, dass nur taken branches aufgenommen werden. Bei einem Hit in der BTB kann somit während der Fetch Phase der Program Counter überschrieben werden. Werden keine History Bits mitgeführt spricht man vom BTAB.

Wie arbeitet Second Chance?

Nach Beenden einer Schleife wird ein Sprung logischerweise falsch vorhergesagt. Um zu vermeiden, dass nun fälschlicherweise das Sprungbit falsch gesetzt wird (da ja die gleiche Schleife noch mal durchlaufen werden kann), ändert man dieses erst nach der zweiten falschen Vorhersage. Leicht zu implementieren als Finite State Machine mit vier Zuständen. Nachteil der dynamischen Vorhersage ist die notwendige teuere und komplexere Hardware.

Was ist der Vorteil von BHT gegenüber BTB?

Branch Target Buffer loggen nur, ob ein Sprung genommen wurde oder nicht. Daher gibt es bei MIPS-Architekturen die BTB verwenden immernoch die sogenannten Branch Delay Slots, da die Sprungadresse trotzdem neu ermittelt werden muss.
BHT beseitigen diesen Nachteil, da sie die Sprungadresse mit abspeichern und diese dann sofort in den IP geladen werden kann.

Was sind Correlating Predictors?

Betrachten wir folgendes Codefragment, fällt uns auf, daß ein Branch Predictor, der nur einen Sprung als Entscheidungsgrundlage einbezieht, den Zusammenhang der drei Sprünge nicht erkennen kann.

  if (a==10)      //1. Sprung
     a=0;               
	 
  if (b=0)        //2. Sprung
     b=0;
	 
  if (a!=b){      //3. Sprung 
     ...          //abhängig von 1. und 2. Sprung
  }

Um diese Abhängigkeiten in eine Sprungvorhersage einbeziehen zu können, sind Correlating Predictors notwendig. Solche Einheiten werden oft als (m,n)-Predictors bezeichnet.

protokolliert wird das Verhalten der letzten m Sprünge je mit einem n-Bit Predictor (z.B. 2-Bit Second Chance)
somit wird aus 2^m*n-Bit Preticors ausgewählt, um Vorhersage für den jeweiligen Sprung zu treffen

Wie werden Correlating Predictors hardwaremäßig implementiert?

Das Implementieren dieser Predictors ist weitaus einfacher, als man es annehmen würde. Es wird einfach für die History-Bits ein m-Bit-Shift Register verwendet, um die letzten m Sprünge zu speichern.

Welche Performancesteigerung ist durch Correlating Predictors erreichbar?

Eqntott ist ein Benchmark, welches speziell mehrere voneinander abhängige Sprünge simuliert. Hier sinkt die Fehlvorhersage von 20% auf unter 8%!

Beim GCC-Compiler sind dagegen keine Unterschiede zwischen Correlating Predictors und normaler 2-Bit Sprungvorhersage erkennbar.

Inhalt

Anfang

zurück

vor

Kapitel 1	Einleitung
Befehlsschleife, Risc und Cisc...
Kapitel 2	Interrupts
Interrupts, Polling, DMA...
Kapitel 3	Speicherschutz
Segmentation, Paging, Mapping, Multitasking...
Kapitel 4	Caches
Lokalität, Cache-Arten, Schreibstrategien...
Kapitel 5	Risc
Risc-Architektur, Load/Store, Registerfenster...
Kapitel 6	Pipelining
Prinzip, Datenkonflikte, Forwarding, Delayed Load
Kapitel 7	Branch Prediction
Statische / Dynamische Brach-Prediction...
Kapitel 8	Superskalarität
Out-Of-Order Execution, Scoreboard und Tomasulo, VLIW...
Kapitel 9	Parallelrechner
SMP,Vektorrechner, Cache-Kohärenz