Sprungvorhersage - Rechneraufbau und Rechnerarchitektur - page 105

Tabelle 6.1. Alle Sprungbefehle des Quicksort-Programms (einschließlich Insertion Sort)
mit ihren Speicheradressen und den sich daraus ergebenden Indizes in die
Pradiktorentabelle, wenn a = 2 Bits zur Adressierung dieser Tabelle zur Verfugung stehen.
Die fur die Indexbestimmung relevanten Bits der Adresse sind durch einen Kasten
gekennzeichnet

Programmzeile Adresse hex/ dual Index

2

3H BNP j,4F #168 01 0110 1000

PBP tmp,5B #178 01 0111 1000 2

PBN tmp,2B #188 01 1000 1000 2

1

BN tmp,:ISort #194 01 1001 0100

2

PBNP tmp,1F #1b8 01 1011 1000

3

BNP tmp,1F #1cc 01 1100 1100

0

BNP tmp,1F #1e0 01 1110 0000

2

PBN tmp,1B #218 10 0001 1000

2

PBP tmp,2B #228 10 0010 1000

0

PBNN tmp,1F #230 10 0011 0000

” 1“ bedeutet, dass die Verzweigung entgegen der statischen Vorhersage
eingeschlagen wird ( In Opposition , kurz O). Dies entspricht einem Not
Taken bei einem Probable Branch und ansonsten einem Taken.

Realisiert werden kann ein solches Vorhersageverfahren durch eine separat
gespeicherte Tabelle, die zu jedem Sprungbefehl diesen Pradiktor enthalt. Es
sind aber nicht alle Speicheradressen mit Programmbefehlen belegt und von
diesen Befehlen sind nur einige Sprungbefehle. Also ware es zu aufwandig, zu
jeder Speicheradresse ein zusatzliches Bit zu speichern. Daher wird in kon-
kreten Implementierungen lediglich ein spezieller Speicher eingerichtet, der
2 a Pradiktoren enthalt und der mit der Adresse des Verzweigungsbefehls Mo-
dulo 2 a adressiert wird (also die niederwertigsten a Bit der Adresse) 3 .Das
heißt, es werden moglicherweise mehrere Verzweigungsbefehle durch densel-
ben Eintrag in diesem Speicher reprasentiert. Diese Mehrdeutigkeit wird aber
in Kauf genommen, da es sich bei dem Vorhersageverfahren ja grundsatzlich
nur um eine Heuristik handelt und nicht um ein exaktes Verfahren. Fur die
Sprungbefehle des Quicksort-Beispiels aus dem Anhang und den Wert a =2-
also 2 a = 4 verschiedene Pradiktoren - wird dies in Tabelle 6.1 dargestellt.

3 Bei RISC-Prozessoren wird die Adresse vorher durch die Befehlswortlange ge-
teilt. Bei MMIX wird also durch vier geteilt, da Befehle immer nur an durch vier
teilbaren Adressen stehen konnen.