Hardware Reference
In-Depth Information
6.1
6.1 Statische Vorhersage
Bei den ersten pipeline-basierten Mikroprozessoren war eine Vorzugsrichtung
fur Sprungbefehle fest vorgegeben. Man spricht dann noch nicht von Sprung-
vorhersage, sondern von Prefetching. Zum Beispiel beherrschte bereits der
8086-Prozessor von Intel diese Technik: Die Bus Interface Unit (BIU) konnte
parallel zur Ausfuhrungseinheit arbeiten und die nachsten Instruktions-Bytes
vorausschauend in einen schnellen Zwischenspeicher, die
Prefetch Queue
,la-
den. Bei Verzweigungen war diese Arbeit zwar umsonst und die BIU musste
den laufenden Prefetch-Zugriff zunachst beenden, die spekulativ geladenen
Bytes verwerfen und dann erst konnte sie von der neuen Adresse die Instruk-
tionen nachladen. Das dauerte etwas langer als Prefetch-freie Techniken, aber
im Mittel brachte diese Methode doch eine deutliche Leistungssteigerung [37].
Viel Aufwand wurde seither investiert, um Verfahren zu entwickeln, mit denen
sich Sprungziele mit hohen Trefferraten vorhersagen lassen.
Ein Ansatz uberlasst die Vorhersage dem Programmierer bzw. einem Com-
piler, indem bei jeder Verzweigung angegeben werden kann, ob sie wahr-
scheinlich ausgefuhrt oder wahrscheinlich nicht ausgefuhrt werden wird. Man
spricht von
statischer Vorhersage
. Meist gibt ein Bit im Opcode an, ob die
Verzweigung wahrscheinlich ausgefuhrt werden wird, das so genannte
Take/-
don't take Bit
(kurz
TDTB
) [11] oder auch
Static-Prediction Opcode Bit
.
Der
MMIX
verfugt uber diese Moglichkeit der Vorhersage. Jeder Verzweigungs-
befehl existiert in zwei Varianten: Als
Probable Branch
, der wahrscheinlich
ausgefuhrt werden wird (
PBZ
,
PBEV
etc.) und als gewohnlicher Branch, der
wahrscheinlich nicht ausgefuhrt werden wird (
BZ
,
BEV
etc.). Die Opcodes fur
die beiden Befehle unterscheiden sich jeweils am Bit 4 (Wertigkeit 2
4
). So ist
beispielsweise der Opcode von
BZ
(
”
Branch if Zero“) der Wert
#42
und der
Opcode von
PBZ
(
”
Probable Branch if Zero“) ist der Wert
#52
.
Diese Art der Vorhersage bewahrt sich insbesondere bei so genannten Zahl-
schleifen, also Schleifen, die vor dem Schleifenabbruch ofter hintereinander
durchlaufen werden. Als Beispiel betrachten wir das Sortieren durch Einfugen
(Insertion Sort), das im Anhang A.2 beschrieben ist. Dieses Sortierverfahren
wird oft zum Sortieren kleiner Felder verwendet, z.B. bei Quicksort am Ende
der Rekursion.
Der Befehl in Zeile 32 beendet das Sortierverfahren. Er wird je Unterpro-
grammlauf fur jeden Wert ein Mal ausgefuhrt und resultiert davon genau ein
Mal (zum Schluss) in einem nicht ausgefuhrten Branch. Bei
N
zu sortierenden
Werten ist die Wahrscheinlichkeit fur
Taken
also 1
1
/N
.
Die Verzweigung in Zeile 23 wird nur dann ausgefuhrt, wenn der Index bis
zum Feldanfang lauft. Nach Knuth [20] Abschnitt 5.2.1 tritt das bei
N
zu
−
