Rechnerarchitektur (Subject) / Sprungvorhersage (Lesson)
There are 11 cards in this lesson
Branch Prediction
This lesson was created by fuchsik.
This lesson is not released for learning.
- statische Sprungvorhersage:Stall/Freeze hält die Pipeline kurz an wird in ID-Stufe(Instruction Decode) Sprungbefehl festgestellt, wird Pipeline solange angehalten, bis man in EX-Stufe (Execute) weiß, ob Sprung ausgeführt wird
- statische Sprungvorhersage:Delayed Branches wird Sprungbefehl festgestellt > nicht bekannt, ob ausgeführt wird oder nicht jeder Sprungbefehl bekommt Delay-Slots, die mit Instruktionen gefüllt werden können findet Sprung nicht statt, wird nach Delay-Slot normal weitergemacht findet Sprung statt, werden Daten aus Sprungzieladresse nach den Delay-Slot-Instruktionen ausgeführt
- Statische Sprungvorhersage:Predict (Not) Taken Sprungvorhersage im Prozessor fest verdrahtet alle Sprünge werden erstmal abgelehnt oder erstmal durchgeführt Branch-Not-Taken/Predict-Not-Taken/Always Not Taken:- Annahme, dass Verzweigungen nicht stattfinden > kein Sprung ausgeführt wird Branch-Taken/Predict-Taken/Always Taken:- Annahme, dass Verzweigungen immer stattfinden > jeder Sprung ausgeführt wird
- compiler-adressierte Sprungvorhersage Codierung der Vorhersage in einem Bit des Opcodes > 2 Opcodes je Sprungbefehl: Bit im Opcode gibt an, ob Verzweigung wahrscheinlich ausgeführt werden wird Hardwareunterstützung notwendig Holen der Befehle von festgelegter Sprungrichtung Bei falscher Vorhersage werden geholte Befehle wieder verworfen
- Unterschied statische und dynamische Sprungvorhersage Statische Vorhersage geht immer vom selben Ergebnis aus, d.h. ein Sprung tritt entweder immer ein oder nie Dynamische Sprungvorhersage trifft basierend auf Erinnerung an die letzte Entscheidung entsprechend individuell
- dynamische Prädiktion Sprungvorhersage zur Laufzeit mit Hilfe von Laufzeitinformationen basierend auf Erinnerung an letzte Entscheidung bzgl. des jeweiligen Sprungbefehls
- dynamische Prädiktion:1-Bit-Prädiktor für jede Verzweigung wird gespeichert, wie sie das letzte Mal verlief Vorhersage: Nächste Ausführung verläuft so wie letzte
- dynamische Prädiktion:1-Bit-Prädiktor::Vor-/Nachteile es erfolgt korrekte Vorhersage eines Sprungs am Ende einer Schleife, solange Schleife ausgeführt wird Schleifenaustritt (also „Not Taken“): Sprung wird jedoch falsch (als „Taken“) vorhergesagt erneute Verwendung der Schleife: erste Vorhersage am Ende der Schleife ebenfalls falsch, da dieser Wert beim letzten Austritt gespeichert wurde Grund der Probleme: kurze Historie> Verringerung des Problems durch 2-Bit-Prädiktor
- dynamische Prädiktion:2-Bit-Prädiktor 2 Bit pro Eintrag für Codierung der Vorhersage > 4 Zustände: -„sicher genommen“ („strongly taken“) -„vielleicht genommen“ („weakly taken“) -„vielleicht nicht genommen“ („weakly not taken“) -„sicher nicht genommen“ („strongly not taken“) in sicherem Zustand sind 2 aufeinanderfolgende Fehlannahmen nötig um Vorhersageannahme umzudrehen > so erhält man eine Art Hysterese im Entscheidungsprozess
- dynamische Prädiktion:Branch History Table BHT Sprungverlaufstabelle Protokolliert letzte Sprünge Verwendet Teil der Sprungbefehlsadresse als hash Wert Tabelle wird demnach nach jedem Sprung aktualisiert
- dynamische Prädiktion:Branch Target Buffer BTB Problem: Sprungziel wird erst in zweiter Pipeline oder noch später berechnet Lösung bei längerer (realistischerer) Pipeline:Branch Target Buffer speichert ausgeführte Sprünge in Tabelle Sprungziel steht bei korrekter Vorhersage sofort zur Verfügung, auch wenn noch nicht klar ist, ob Sprung ausgeführt wird oder nicht!