Hardware Reference
In-Depth Information
sortierenden Elementen im Mittel (
k
=1
k
1 Mal auf. Fur
N
=5somit
etwa 1,3 Mal, also mit einer Wahrscheinlichkeit von deutlich unter 50%.
Der Sprung in Zeile 27 wird ausgefuhrt, wenn das aktuell einzusortierende
Element seinen Platz noch nicht gefunden hat. Der Sprungbefehl wird nach
Knuth im Mittel 2
)
−
(
N
2
− N
)
/
4 Mal ausgefuhrt. Pro Element sind im Mittel
·
(
N−
1)
/
2 Vergleiche erforderlich. Also ergeben sich die statischen Vorhersagen
sinnvoll so, wie im Programm angegeben.
Messungen mit unserem Quicksort zum Sortieren von 10.000 zufalligen Wer-
ten ergaben, dass dieses Unterprogramm 1551 Mal aufgerufen wird, um im
Mittel
N
=5
,
44 Werte zu sortieren. Es ergaben sich fur die Sprungvorher-
sagen im Beispiel die folgenden Trefferraten, sofern die statische Vorhersage
korrekt angegeben ist:
Zeile/Befehl Taken Not Taken Trefferrate
23/
BNP
2059 16345 88,8%
27/
PBP
11505 4840 70,4%
32/
PBN
6899 1551 81,6%
Außer bei
MMIX
findet sich die statische Vorhersage mit TDTB noch beim
Motorola PowerPC 601 sowie bei der Alpha-Architektur. Das Setzen des
Bits ubernehmen ublicherweise optimierende Compiler. Zum Optimieren von
Hand sind Laufschleifen am augenfalligsten, wie diejenige, die durch den
PBN
-
Befehl in Zeile 32 gesteuert wird. Alle anderen bedingten Verzweigungen er-
fordern genaueres Hinsehen, wie etwa die Uberlegungen im vorangegangenen
Absatz.
Manche Prozessoren, die nicht uber diese Moglichkeit der statischen Vorher-
sage verfugen, benutzen fest eingebaute Strategien, um Sprungziele vorherzu-
sagen. Aus Beobachtungen wurde beispielsweise abgeleitet, dass Verzweigun-
gen nach ruckwarts (d.h. zu niedrigeren Adressen) haufiger ausgefuhrt werden
als solche nach vorne (zu hoheren Adressen) [4]. Diese einfachen Vorhersa-
geverfahren wurden mittlerweile durch kompliziertere dynamische Verfahren
ersetzt, die wir weiter unten besprechen.
Ubung 6.1.1
Gegeben sei folgendes
MMIX
-Programm:
1
6.1.1
LOC
#100
2
Main
SET
$4,30
3
loop1
SET
$3,3
4
SET
$2,2
5
loop2
BZ
$2,1F
6
SUB
$2,$2,1
7
1H
SUB
$3,$3,1
8
BP
$3,loop2
