Information Technology Reference
In-Depth Information
das in Bild 3.26b skizzierte Programm erzeugen. Ein für das Trace-Scheduling dar-
aus separierter Programmpfad enthält eine deutlich höhere Anzahl parallelisierbarer
Operationen als ein vor Abrollen der Schleife separierter Programmpfad.
Die mehrfache Überprüfung der Schleifenabbruchbedingung in Bild 3.26b lässt sich
vermeiden, wenn die Anzahl der Schleifendurchläufe vor Eintritt in die Schleife
bekannt ist. Ein entsprechend optimiertes Programm zeigt Bild 3.26c. Innerhalb des
Schleifenrumpfs zwischen den Zeilen 5 und 9 wird die Schleifenabbruchbedingung
ein einziges Mal überprüft. Die Semantik der in Bild 3.26a dargestellten Schleife
bleibt dabei trotzdem erhalten, wenn die Anzahl der Schleifendurchläufe hier durch
Drei teilbar ist, was jedoch nicht immer gilt. Aus diesem Grund wird vor dem
Schleifeneintritt in den Zeilen 1 und 3 die Abbruchbedingung auf Teilbarkeit durch
Drei überprüft und der ursprüngliche Schleifenrumpf ggf. ein oder zweimal außer-
halb der Schleife, nämlich in Zeile 2 bzw. Zeile 4 ausgeführt.
Die Überprüfung der Teilbarkeit durch Drei vor Bearbeitung der abgerollten
Schleife bezeichnet man als Präkonditionierung [101]. Bei der ebenfalls möglichen
sog. Postkonditionierung werden unbearbeitete Schleifendurchgänge im Anschluss
an die abgerollte Schleife ausgeführt. Es sei angemerkt, dass die durch Nutzung der
Prä- oder Postkonditionierung abgerollten Schleifen nicht schneller bearbeitet wer-
den müssen als ein Programm, das entsprechend Bild 3.26b optimiert ist, da sich die
bedingten Sprungoperationen oft parallel zu Operationen des Schleifenrumpfs aus-
führen lassen.
1:
loop: if -- goto end
1:
loop:
if -- goto end
1:
if mod -- goto loop
2:
body
2:
body
2:
body
3:
goto
loop
3:
if -- goto end
3:
if mod -- goto loop
4:
end:
4:
body'
4:
body'
5:
if -- goto end
5:
loop:
if -- goto end
6:
body''
6:
body''
7:
goto
loop
7:
body'''
8:
end:
8:
body''''
9:
goto
loop
10:
end:
a
b
c
Bild 3.26. Optimierung einer Schleife durch Abrollen. a Die nichtoptimierte Schleife. b Die über
drei Iterationsschritte einfach abgerollte Schleife. c Die über drei Iterationsschritte abgerollte prä-
konditionierte Schleife
Software-Fließbandverarbeitung (software-pipelining). Ein weiteres Verfahren
zur Erhöhung der in Schleifen codierbaren Operationsparallelität ist die sog. Soft-
ware-Fließbandverarbeitung, bei der man aufeinander folgende Schleifenrümpfe
überlappend parallel ausführt. Bild 3.27 zeigt hierzu ein aus dem Handbuch zur Pro-
zessorarchitektur IA-64 von Intel und HP stammendes Beispiel [70]. Die Operatio-
nen in den Zeilen 1 bis 3 von Bild 3.27a sind, wegen der über r4 und r7 bestehenden
Datenabhängigkeiten, nicht parallel ausführbar. Sobald jedoch das Ergebnis der
Ladeoperation des ersten Schleifendurchlaufs feststeht, kann gleichzeitig zur Addi-
tion bereits ein in einem späteren Schleifendurchlauf benötigter Operand aus dem
Hauptspeicher gelesen und auch verarbeitet werden. Das in dieser Weise realisierte
Search WWH ::




Custom Search