Gegeben sei der folgende Kontrollflußgraph. Die Ausführungshäufigkeiten stehen rechts neben den Blöcken. Geben Sie den Konfliktgraphen und die Auslagerungskosten für alle Pseudoregister an. Dabei wird angenommen, daß ein Speicherbefehl zwei Zyklen und ein Ladebefehl drei Zyklen kostet.
Anmerkung: Der Kontrollflußgraph ist bei den Erklärungen gegeben.
R| R:=| :=R|Summe -+----+----+------------------ A| 5 | 12 | 46 = 5*2 + 12*3 B| 5 | 9 | 37 = 5*2 + 9*3 C| 5 | 3 | 19 = 5*2 + 3*3 D| 2 | 2 | 10 = 2*2 + 2*3 E| 9 | 9 | 45 = 9*2 + 9*3 F| 2 | 2 | 10 = 2*2 + 2*3 G| 11 | 5 | 37 = 11*2 + 5*3
Um den Konfliktgraph bestimmen zu können, müssen zuerst die
Aktivitätsbereiche der Register bestimmt werden. Ein Register ist
normalerweise vom Zeitpunkt des Beschreibens (R:=) bis zum
Zeitpunkt des Lesens (:=R) aktiv. Bei mehreren Schreib-
Lese-Kombinationen eines Registers zählen nur die minimalen Bereiche,
d.h. bei
ABC | A:= || B:= || :=A || C:= ||| A:= ||| :=B | | :=A | :=C
gibt es zwei Bereiche, wo das Register A aktiv
ist.
Bei Lesezugriffen in Schleifen muß man aufpassen. Wenn ein
Register R schon vor Beginn einer Schleife aktiv ist
und innerhalb der Schleife davon gelesen wird, dann ist R
über den gesamten Bereich der Schleife aktiv! Die
nächste Darstellung zeigt ein Schleife. Es sei angenommen, daß
das Register A schon vor Beginn der Schleife einen Wert
zugewiesen bekommen hat und daß von Register C nach der
Schleife gelesen wird.
ABC || B:= || :=A || :=B | | C:=
Register A ist über den gesamten Bereich aktiv. Es
darf kein anderer Wert in dieses Register geschrieben werden weil die
Schleife ja wiederholt werden könnte. Register B ist nur
innerhalb der Schleife aktiv da es bei jedem Durchlauf erneut initialisiert
wird. In Register C wird bei jedem Durchlauf ein neuer Wert
hineingeschrieben. Das Register kann also vor diesem Schreibzugriff
anderwertig verwendet werden.
Damit können wir die Aktivitätsbereiche für alle Blöcke bestimmen.
Der Konfliktgraph läßt sich nun ganz leicht aus den Aktivitätsbereichen ablesen: Sind zwei Register zum gleichen Zeitpunkt aktiv, dann stehen sie miteinander in Konflikt. Daraus ergibt sich der Konfliktgraph.
Die Auslagerungskosten sind sehr einfach zu berechnen. Für jedes Register zählt man die Anzahl der Speicher- und Ladebefehle. Man beachte dabei die Ausführungshäufigkeiten, die neben den Blöcken stehen und multipliziere die entsprechend. Die Anzahlen werden mit den entsprechenden Kosten der Zyklen multipliziert, in diesem Beispiel also mit 2 bzw. 3.
R| R:=| :=R|Summe -+----+----+------------------ A| 5 | 12 | 46 = 5*2 + 12*3 B| 5 | 9 | 37 = 5*2 + 9*3 C| 5 | 3 | 19 = 5*2 + 3*3 D| 2 | 2 | 10 = 2*2 + 2*3 E| 9 | 9 | 45 = 9*2 + 9*3 F| 2 | 2 | 10 = 2*2 + 2*3 G| 11 | 5 | 37 = 11*2 + 5*3