Branch Prediction (Sprungvorhersage) ist eine Technik der CPU, die vorhersagt, ob ein bedingter Sprung (Branch) genommen wird — noch bevor die Bedingung wirklich ausgewertet ist. Sie ist der Schlüssel, damit tiefe Pipelines bei Schleifen und Verzweigungen nicht ständig geleert werden müssen.
Das Problem: Kontroll-Hazards
Beim Pipelining wird der nächste Befehl geladen, während der aktuelle noch läuft. Trifft der Prozessor auf einen Sprung, weiß er erst nach der Auswertung, wohin es weitergeht. Ohne Vorhersage müsste er warten (Stall) — bei einer 20-stufigen Pipeline gingen pro Sprung bis zu 20 Takte verloren. Moderne Programme enthalten alle 5–10 Befehle einen Sprung, daher wäre das unbezahlbar langsam.
Statische und dynamische Vorhersage
Statische Verfahren raten nach festen Regeln, z. B. „Rückwärtssprünge werden genommen" (Schleifen) oder Hinweise des Compilers aus der Codegenerierung.
Dynamische Verfahren lernen aus der Vergangenheit:
- Branch History Table (BHT): speichert pro Sprungstelle den Ausgang des letzten Sprungs (1-Bit- oder 2-Bit-Saturierungszähler — letzterer ignoriert einzelne Ausreißer).
- Branch Target Buffer (BTB): merkt sich zusätzlich die Zieladresse des Sprungs, damit sie nicht jedes Mal neu berechnet werden muss.
- TAGE & neuronale Prädiktoren (modern): kombinieren lange Verlaufs-Historien und erreichen über 95 % Trefferquote — entscheidend für die superskalare Ausführung.
Kosten einer Fehlvorhersage
Liegt die Vorhersage falsch (Misprediction), müssen alle bereits geladenen Befehle aus der Pipeline verworfen werden — die CPU verliert so viele Takte, wie die Pipeline Stufen hat. Instruction Scheduling in der Codegenerierung kann Sprünge so umordnen, dass häufige Fälle vorhersagbar werden; der Compiler unterstützt mit bedingten Sprüngen und Schleifen-Aufrollung.
Sicherheit: Spectre
Seit 2018 ist die Sprungvorhersage auch ein Sicherheitsthema: Angriffe wie Spectre nutzen aus, dass vorhersagende CPUs Befehle spekulativ ausführen und Spuren davon über den Cache-Speicher messbar sind. Moderne CPUs isolieren deshalb Vorhersage-Strukturen zwischen Prozessen.
Verwandte Grundlagen: Instruktionssatz, Opcode, Mikroarchitektur.