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

erzeugter Datenstrukturen, also bei Listen, Bäumen oder Graphen auftreten, prinzi-
piell nur durch eine kontextbasierte Wertvorhersage im Voraus bestimmt werden.
Eine gänzlich andere Möglichkeit bietet sich in Prozessoren, deren Programmiermo-
dell über Befehle zur Berechnung von Adressen verfügen, wie z.B. der Itanium 2
von Intel [78], der ARM7TDMI von ARM [10] (siehe auch [83]) und der Nemesis
C der TU Berlin [114, 198]. Bei all diesen Prozessoren ist es möglich, mit dem
Laden eines Operanden die jeweils verwendete Adresse für den nächsten Zugriff
durch Addition oder Subtraktion mit einem konstanten oder variablen Offset zu
modifizieren. Somit ist bereits bei Ausführung eines entsprechenden Ladebefehls
bekannt, auf welche Adresse in nächster Zukunft wahrscheinlich zugegriffen wer-
den wird. Dies lässt sich nutzen, um entweder das jeweilige Datum im Voraus zu
laden oder die Adresse des nächsten Zugriffs vorherzusagen.

Beispiel 2.9. Vorhersage von Ladeadressen . In Bild 2.51 ist ein Programm für den Nemesis C
dargestellt, mit dem die Anzahl der Elemente einer nullterminierten Liste gezählt werden kann, des-
sen erstes Element durch r1 adressiert wird (wobei der Einfachheit halber die Liste wenigstens ein
Element enthalten muss). Das Ergebnis der Zählung befindet sich nach Ausführung der Schleife im
Register r2. Obwohl im Nemesis C keine Einheit zur Wertvorhersage realisiert ist, sind im Pro-
grammiermodell des Prozessors bereits Befehle vorgesehen, die eine spätere Erweiterung vereinfa-
chen.

1: mov r2, 0 // r2 = 0; Schleifenzähler initialisieren (Pseudobefehl)

2: loop: add r2, r2, 1 // r2 = r2 + 1; Schleifenanzahl zählen

3: ldp r1, [r1 + 4] // r1 = r1->next; Nächstes Element adressieren

4: bregnz r1, loop // Wiederholen, bis r1 gleich Null ist

Bild 2.51. Programm zum Zählen der Elemente einer nullterminierten verketteten Liste

Der Befehl ldp (load pointer) dient z.B. ausschließlich dazu, eine Adresse aus dem Datenspeicher in
ein Register zu laden. So ist es möglich, bereits den Zugriff auf den im nächsten Schleifendurchlauf
zu adressierenden Datenbereich anzustoßen und diesen z.B. in den Datencache zu übertragen. Im
zweiten und allen folgenden Schleifendurchläufen ist dann für die Zugriffe nur noch die kurze
Latenzzeit des Datencaches abzuwarten. Falls man die Reihenfolge der Befehle geringfügig verän-
dert, lässt sich diese Zeit zum Teil noch eleminieren: Indem nämlich die Addition in Zeile 2 mit
dem Ladebefehl in Zeile 3 vertauscht wird, kann in der Zeit des Zugriffs auf den Datencache bereits
die Addition in Fließbandtechnik ausgeführt werden. Mit dem Sprungbefehl ist dies jedoch nicht
möglich, weil eine echte Datenabhängigkeit zum Ladebefehl besteht.

Sprungvorhersage durch Wertvorhersage

Bei einer Sprungvorhersage durch Wertvorhersage bestimmt man nicht direkt die
wahrscheinliche Sprungentscheidung, sondern die vom bedingten Sprungbefehl
bzw. einem Vergleichsbefehl auszuwertenden Operanden, und mit ihrer Hilfe, ob es
zu einer Verzweigung kommen wird oder nicht. In Abschnitt 2.2.4 wurden einige
Verfahren beschrieben, mit denen sich bei geringem Aufwand Sprungentscheidun-
gen mit einer Zuverlässigkeit von deutlich über 90% korrekt vorhersagen lassen.
Kein Verfahren zur Vorhersage nichtboolescher Werte erreicht eine ähnlich hohe
Zuverlässigkeit. Zum Beispiel sind nach [148] von einer kontextbasierten Wertvor-
hersage unter idealen Voraussetzungen (unbegrenzter Speicherkapazität für Werthis-
torien- und Wertvorhersagetabellen) im Durchschnitt lediglich 78% der Werte kor-