Sprungvorhersage - Rechneraufbau und Rechnerarchitektur - page 107

Tabelle 6.3. Mit Ein-Bit-Pradiktoren erzielte Trefferrarten bei Insertion Sort

Zeile Erfolgreiche Vorhersagen Falsche Vorhersagen Trefferrate

23 14286 4118 77,6%

27 9302 7043 56,9%

32 5469 2981 64,7%

Ubung 6.3.2 Finden Sie ein Beispiel, bei dem der Ein-Bit-Pradiktor besser
ist als die statische Vorhersage. Welche Unterschiede kann es geben?

6.3.2

Tabelle 6.3 zeigt die mit diesem Pradiktor erzielbaren Trefferraten im Fall
des oben besprochenen Insertion Sort. Dabei wurde a so gewahlt, dass sicher
jeder Verzweigungsbefehl seinen eigenen Pradiktor besitzt.
Der Befehl in Zeile 27 verhalt sich etwa so, wie es oben in Tabelle 6.2 be-
schrieben wurde: Auf eine (mehr oder weniger lange) Serie von Taken folgt
ein Not Taken, wenn das einzusortierende Element seinen Platz gefunden hat.
Deshalb sinkt hier die Trefferrate gegenuber der statischen Vorhersage ab.
Das vorgestellte Verfahren kann nun in zwei Richtungen erweitert werden:
1. Man kann den Pradiktor als n -Bit-Zahler realisieren. Dieser Zahler wird
dann fur jede korrekte Vorhersage um 1 erhoht und fur jede falsche Vorher-
sage um 1 erniedrigt. Ist der Zahler großer 0, so wird ” Agreement“ vorher
gesagt, ansonsten ” Opposition“. Damit wird das Verhalten der Sprungbe-
fehle uber einen gewissen Zeitraum gemittelt und eine Mehrheitsentschei-
dung getroffen.
2. Man kann die genaue Vorgeschichte weiter in die Vergangenheit aufzeich-
nen und versuchen, Muster im Verhalten der Sprunge aufzuspuren. Im
obigen Beispiel mit einem Verlauf, in dem auf eine Serie von Taken jeweils
ein Not Taken folgt, heißt das, dass es unter Einbeziehung der Historie
wahrscheinlich ist, dass auf TN wieder ein T folgen wird. Dazu spater
mehr.

Die Beobachtung, dass bei jedem Schleifenende zwei falsche Vorhersagen auf-
treten und die Tatsache, dass solche Zahlschleifen recht haufig sind, hat sehr
fruh dazu gefuhrt, Pradiktoren mit zwei statt nur einem Bit zu verwenden.
Diese zwei Bits werden als saturierender Zahler in einer Zwei-Komplement-
Darstellung mit folgender Interpretation betrachtet: