Wo/wie werden Verzweigungsvorhersagedaten gespeichert?

Question

Ich habe mich immer gefragt, wo/wie die Vorhersagedaten gespeichert sind? Gibt es eine Grenze? Sind es nur neuere Zweige? Ich bin hauptsächlich besorgt über die Intel-Architektur, aber alles, was ich über jede Architektur lernen kann, wird geschätzt.

Answer 1

Irgendwo intern im Prozessor. Was genau gemacht wird, hängt vom Prozessor ab.

In einem sehr einfachen Fall könnten Sie 4096 Bits Verzweigungsvorhersagedaten nehmen. Dann nehmen Sie für jeden Zweig die letzten 12 Bits der Adresse der Verzweigung, die 4096 verschiedene Werte ergibt, und nehmen diese als den Index in Ihre Verzweigungsvorhersagedaten auf. Und da Sie nur ein Datenbit haben, speichern Sie einfach, ob die letzte Verzweigung genommen wurde.

Der Vorteil ist, dass es sehr billig ist. Der Nachteil ist, dass zwei Zweige mit exakt 4096 Bytes den gleichen Eintrag in der Tabelle verwenden. Wenn also Ihr Code diese beiden Zweige ständig ausführt und eine immer genommen wird und eine nie genommen wird, ist die Verzweigungsvorhersage ziemlich schlecht.

Einige Prozessoren verwenden zwei Bits pro Zweig, was bedeutet "stark genommen", "genommen", "nicht genommen", "stark nicht genommen". Jedes Mal wenn eine Verzweigung genommen wird, bewegt sich die Vorhersage in Richtung "stark genommen", wenn die Verzweigung nicht genommen wird, bewegt sie sich in Richtung "stark nicht genommen". Dies funktioniert besser, wenn Zweige mit seltenen Ausnahmen verwendet werden.

Einige Prozessoren verwenden nicht nur die letzten 12 oder mehr Bits der Verzweigungsadresse, sondern sie mischen ein, ob die letzten vier Zweige genommen wurden. Angenommen, Sie haben den Code

if (x >= 0) { ... } 
if (x <= 0) { ... } 

und x ist selten 0, aber ziemlich zufällig positiv oder negativ. Dann ist der erste Zweig schwer vorherzusagen, aber der zweite wird nie genommen, nachdem der erste genommen wurde, und immer wenn der erste nicht genommen wird. Indem Sie diese Informationen einmischen, verwenden Sie zwei Einträge in der Verzweigungsvorhersagetabelle für die zweite Verzweigung, aber die Vorhersage für die zweite Verzweigung ist sehr genau, auch wenn die Verzweigung zufällig gewählt oder nicht genommen wird.

Sie haben immer das Problem, dass derselbe Eintrag in der Verzweigungsvorhersagetabelle für mehr als eine Verzweigung verwendet wird; damit lebst du einfach. (Wenn wir etwas cleveres machen, würde das viel zu viel Speicher beanspruchen. Wir verwenden 1 oder 2 Bit pro Verzweigungsvorhersage, so dass wir massive Tabellen mit sehr wenig Speicher haben können).