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

„verzweigen“ in 90% der Fälle korrekt. Dies bedeutet jedoch nicht, dass hier in 90% der Fälle kein
Kontrollflusskonflikt mehr auftritt. Wie eingangs erwähnt, ist das Zeitverhalten des PowerPC bei
Ausführung eines Sprungbefehls nämlich von vielen weiteren Faktoren abhängig.

1: sum: li r31, 10 // Schleifenzähler initialisieren (r31 = 10)

2: mtctr r31 // Schleifenzählregister initialisieren (ctr = r31)

3: li r1, 0 // Summenregister initialisieren (r1 = 0)

4: loop: mfctr r31 // Zählregister umspeichern (r31 = ctr)

5: add r1, r31, r1 // Summe bilden (r1 = r1 + r31)

6: bc jtaken | ctrnz, nocc, loop // Schleifensprung (siehe Text)

Bild 2.28. Befehlsfolge für den PowerPC von Motorola oder IBM als Beispiel für die statische
Sprungvorhersage. Es wird die Summe der Zahlen von 1 bis 10 berechnet

Dynamische Sprungvorhersage

Die Häufigkeit, mit der bei Ausführung von Sprungbefehlen bestimmte endliche
Verzweigungsfolgen auftreten, ist von Lee und Smith statistisch mit dem Resultat
untersucht worden, dass Sprungbefehle häufig ein vom Programm unabhängiges
Sprungverhalten aufweisen [97]. So wurde ermittelt, dass die Verzweigungsfolge n-
n-n-n-n etwa 18 mal häufiger als die Verzweigungsfolge n-n-n-n-t auftritt, wobei
verzweigende Sprungbefehle mit „t“ (branch taken) und nichtverzweigende Sprung-
befehle mit „n“ (branch not taken) abgekürzt sind. Mit anderen Worten: es ist mög-
lich, einen Sprungbefehl nach einer Verzweigungsfolge n-n-n-n mit etwa 95%iger
Wahrscheinlichkeit als nichtverzweigend vorherzusagen. Ähnlich wird ein Sprung-
befehl nach einer Verzweigungsfolge t-t-t-t mit hoher Wahrscheinlichkeit verzwei-
gen. Ebenfalls bemerkenswert ist, dass die Verzweigungsfolge t-n-t-n-t (bzw. n-t-n-
t-n) bis zu 16 mal häufiger auftritt als die Verzweigungsfolge t-n-t-n-n (bzw. n-t-n-t-
t). Die Ergebnisse dieser Untersuchung lassen sich nutzen, um Sprungentscheidun-
gen mit einer Wahrscheinlichkeit von über 90% korrekt vorherzusagen.

Im einfachsten Fall speichert man die Historie der Sprungentscheidungen in einem
sog. Sprungvorhersagecache ( branch prediction cache ), der jeweils mit den
Befehlsadressen der Sprungbefehle adressiert wird (zu Caches siehe Abschnitt
2.3.1). Mit jedem auszuführenden Befehl durchsucht man den Sprungvorhersageca-
che. Lässt sich zu der entsprechenden Befehlsadresse kein Eintrag finden, handelt es
sich entweder nicht um einen Sprungbefehl oder es ist keine Historie zu dem
Sprungbefehl gespeichert. Im letztgenannten Fall wird eine statische Sprungvorher-
sage durchgeführt und für eine erneute Ausführung des Sprungbefehls ein Eintrag
im Sprungvorhersagecache erzeugt. Falls jedoch zu dem Sprungbefehl bereits ein
Eintrag existiert, lässt sich der jeweilige Sprung entsprechend dieses Eintrags vor-
hersagen. Im Prinzip ist es auf diese Weise möglich, zu einer alternierenden Ver-
zweigungsfolge t-n-t-n eine korrekte Vorhersage t zu erzeugen. Allerdings ist dies
davon abhängig, welches Verfahren zur Sprungvorhersage verwendet wird.

Dynamische Sprungvorhersage mit einstufiger Historie. Dieses Verfahren kann
alternierende Verzweigungsfolgen zwar noch nicht vorhersagen, hat jedoch den Vor-
teil, sehr einfach realisierbar zu sein. Es ist in Bild 2.29 als Graph dargestellt: Falls
ein Sprungbefehl bei seiner Ausführung verzweigt, wird im Sprungvorhersagecache