Skalare Prozessoren - Moderne Prozessorarchitekturen: Prinzipien und ihre Realisierungen - page 109

verzweigt (t) verzweigt nicht (n)

n

ST
wird
verzweigen

LT
wird
verzweigen

LN
wird nicht
verzweigen

SN
wird nicht
verzweigen

n n

t t

t

Bild 2.32. Modifizierte dynamische Sprungvorhersage durch Gewichtung

Adaptive Sprungvorhersage

Mit den zuvor beschriebenen Verfahren lassen sich Sprungentscheidungen mit im
Durchschnitt über 90%iger Sicherheit vorhersagen, indem man häufig auftretende
Sprungfolgen vollständig oder teilweise erkennt. Um die Zuverlässigkeit der
Sprungvorhersage zu verbessern, müssen jedoch auch selten auftretende Sprungfol-
gen, die oft vom konkreten Programm abhängig sind, korrekt vorhersagt werden
können. Dies ist mit Hilfe der sog. adaptiven Sprungvorhersage möglich, die zur
Vorhersage nicht einzelne Sprungentscheidungen in ihrer Folge berücksichtigt, son-
dern Sprungmuster . Das Verhalten eines Sprungbefehls wird dabei über eine vorge-
gebene Anzahl von Durchgängen protokolliert und das so erzeugte Sprungmuster
zur Indizierung einer sog. Sprungmustertabelle ( pattern history table ) verwendet. In
ihr ist zu jedem Sprungmuster in einer abstrakten Form eingetragen, mit welcher
Sprungentscheidung es in der Vergangenheit fortgesetzt wurde. Entsprechend dieser
Information lässt sich der Sprungbefehl schließlich als verzweigend oder nichtver-
zweigend vorhersagen [201, 102, 98, 110].
Lokale adaptive Sprungvorhersage mit globaler Sprungmustertabelle (local
predictor). Die prinzipielle Funktionsweise der adaptiven Sprungvorhersage soll
anhand von Bild 2.33 beschrieben werden. In einer als Cache organisierten sog.
Sprunghistorientabelle ( branch history table ) sind zu den Adressen der Sprungbe-
fehle, jeweils die letzten n Sprungentscheidungen (hier mit n gleich Drei) gespei-
chert (Pfeil a). Falls ein Sprungbefehl zu Ausführung kommt, zu dem ein Eintrag in
der Sprunghistorientabelle existiert, wird das ermittelte Sprungmuster zur Adressie-
rung der Sprungmustertabelle verwendet (Pfeil b). In ihr ist, abhängig von der Imp-
lementierung, zu einzelnen oder zu allen Sprungbefehlen, ein Zustand gespeichert,
mit einer zu einer Statistik vergleichbaren Bedeutung, der Auskunft darüber gibt, ob
das entsprechende Sprungmuster bisher häufiger durch einen verzweigenden oder
einen nichtverzweigenden Sprungbefehl fortgesetzt wurde.
Dabei kann die Vorhersage in den Zuständen ST (strong taken) und SN (strong not
taken) als sehr zuverlässig, in den Zuständen WT (weakly taken) und WN (weakly
not taken) als wenig zuverlässig eingestuft werden: Eine als sehr zuverlässig einge-
stufte Vorhersage wird nur geändert, wenn sie sich wenigstens zweimal hintereinan-
der als falsch erweist. Eine wenig zuverlässige Vorhersage wird geändert, wenn eine
einzelne Fehlvorhersage auftritt. Für zukünftige Sprungvorhersagen ist schließlich
nur noch der in der Sprungmustertabelle gespeicherte Zustand (Pfeil f) und das zum
Sprungbefehl gespeicherte Sprungmuster in der Sprunghistorientabelle (Pfeil g) zu
aktualisieren.