TU Wien:Codegeneratoren VO (Krall)/Prüfung WS2023

Schriftliche Prüfung

Registerallokation

Gegeben ist ein Konfliktgraph und man soll eine Registerbelegung ermitteln mit den Algorithmen von Chaitin und von Briggs.

      O
      |
O--O--O--O
|  |  |
O--O--O

Mit der Methode von Chaitin benötigt man 3 Register und mit der Methode von Briggs nur 2 Register.

Interprozedurale Registerallokation

Gegeben ist ein Call graph mit 9 Knoten und 3 globalen Variablen. Man soll eine Registerbelegung für die globalen Variablen finden.

A -> B
A -> F
B -> C
B -> D
D -> E
F -> G
F -> I
G -> H

Lokale Referenzen

Knoten	Globale Variablen
A	g2
B	g2, g3
C	g3
D	g3
E	g1
F	g1, g2
G	g1
H	-
I	g1

Es sind 4 Webs vorhanden.

Ergebnis

Web	globale Variable	Knoten	Register
Web 1	g2	A, B, F	R2
Web 2	g3	B, C, D	R1
Web 3	g1	F, G, I	R1
Web 4	g1	E	R1 oder R2

List scheduling

Gegeben sind 9 Befehle mit 5 loads, 3 adds und 1 mul. Latenzen sind 2 Zyklen für load, 1 für add und 4 für mul. Gefragt sind der Datenabhängigkeitsgraph, ein gültiges Schedule und Anzahl der Zyklen. Ergebnis waren 10 Zyklen, weil man einen Wartezyklus zwischen einem Load und Add hinzufügen musste.

Software pipelining

Gegeben:

Loop: load R0 = *(R2)
      add R2 = R2 + 1
      add R1 = R1 + R0
      beqz R0, Loop

Gefragt waren der Prolog, Kernel und Epilog der Schleife, die mit Software Pipelining verändert wurde. Die Maschine kann einen Ladebefehl, zwei Additionsbefehle und einen Jump-Befehl gleichzeitig ausführen und der Ladebefehl hat eine Latenz von 2 Zyklen und alle anderen nur 1 Zyklus.

Prolog: load R0=*(R2); add R2=R2+1
        load R3=*(R2); add R2=R2+1
  Loop: load R4=*(R2); add R2=R2+1; add R1=R1+R0; bnez R0, Epilog
        load R0=*(R2); add R2=R2+1; add R1=R1+R3; bnez R3, Epilog
        load R3=*(R2); add R2=R2+1; add R1=R1+R4; beqz R4, Loop
Epilog:  add R2=R2-2