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

Schriftliche Prüfung

Vorwort

Die Angabe der Prüfung erhielten wir als Kopien eines handgeschrieben karierten Zettels. Die folgenden Notizen wurden nach der Prüfung aus dem Gedächtnis aufgeschrieben. Die Notizen sind leider etwas wirr und wurden auch leider erst wesentlich später ins VOWI eingepflegt. Beim einpflegen konnte Ich schon leider selbst nicht mehr alle wirren Kommentare in den Notizen entschlüsseln. Im allgemeinen hielten sich die Beispiele scheinbar sehr nahe an vergangenen Prüfung bzw an was wir als Übungsmaterial verwendet hatten. Wir hatten allerdings während der Prüfung einige Fragen zur Angabe, da diese, in Ihrem handgeschriebenen Format, nicht besonders klar war.

Beispiele

Beispiel 1

Angabe

Konfliktgraph:

*     *
|     |
*--*--*
|  |  |
*--*--*
|  |  |
*--*--*

1. Wie viele Register benötigt der Algorithmus von Chaitin? Geben Sie eine Belegung an.
2. Wie viele Register benötigt der Algorithmus von Chaitin-Briggs? Geben Sie eine Belegung an.

Anmerkung: Gemeint war "Wie viele Register werden benötigt ohne das es zu Spill kommt".

Vermutete Antwort

Chaitin 3, Briggs 2.

Anmerkung: Nicht näher spezifiziert wie man zur Belegung kommt. In (m)einem Fall mit Stack abbau resultierte Chaitin trotzallem in nur 2 verwendeten Registern. Vermutlich falsch.

Beispiel 2

Angabe

Prozedurcallgraph:

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

Lokale Referenzen

A:g3
B:g1,g3
C:g1
D:g1
E:
F:g2,g3
G:g2
H:g2
I:g1

Geben sie für die lokale Registerbelegung für die globalen Variablen an.

Anmerkung: Gemeint war vermutlich "Verwende so viele Register wie notwendig"

Vermutete Antwort

Konflikt Graph:

(W1,W2)(W1,W3),(W4)

Belegung:

W1:g3:Register 2
W2:g1:Register 1
W3:g2:Register 1
W4:g1:Register 2

Beispiel 3

Angabe

List Scheduling:

load R0=a
load R1=b
add R2=R0+R1
load R3=c
add R0=R3+R1
load R4=d
mul R5=R4*R3
add R0=R0+R2

Zykels:

add:1
load:2
mul:4

Gib einen Schedule an.

Anmerkung: Je nach Heuristik bei Auswahl gleicher Prioritäten können möglicherweise unterschiedliche Schedules mit NOPS entstehen.

Beispiel 4

Angabe

Software Pipelining:

L:	load R0,(R1)
	add R1,R1,1
	beqz R0,L

Zykles:

add:1
load:2
branch:1

Vermutete Antwort

(WTF NEW REGISTER AND INSTRUCTIONS ARE/WERE ALLOWED TO INSERT FOR SOLUTION?!)

PROLOG:
		load R0,(R1) add R1,R1,1
		load R2,(R1) add R1,R1,1
		load R3,(R1) add R1,R1,1 bneqz R0,EXIT

KERNEL:
	LOOP:
		load R0,(R1) add R1,R1,1 bneqz R2,EXIT
		load R2,(R1) add R1,R1,1 bneqz R3,EXIT
		load R3,(R1) add R1,R1,1 beqz R0,LOOP

EPILOG:
	EXIT:
		add R1,R1,-2

Mündliche Prüfungen

Person 1

• Wie wird Parallelisierung in der MIA realisiert?

Pipelines Out of Order Execution (Precise Interrupts, Reorder-Buffer, Register Renaming, etc) Mehrere functional units Was ist Pipelining?

• Zu welchen Problemen kann es beim Pipelinen kommen?
• Hazards (Eine Instruction braucht das Ergebnis von der Vorherigen)
• Wie kann man Hazard vermeiden?

Stall Bypass Out of Order Execution mit Reservation Table

• Was ist return value forwarding?
• Was ist Register Renaming und warum braucht man es?
• PBQP (Was ist es und wie funktioniert es?)
• Auf welcher Datenstruktur arbeitet PBQP (Beim schedulen) Antwort: SSA Graph
• Wie werden complex pattern in PBQP realisiert?
• Wie wählt man diese patterns aus?
• IPS (Integrated Prepass Scheduling) Was ist das?

• Was ein branch address cache ist

Person 2

• Wie schauen heutige Mikroarchitekturen aus das Sie effizient Code ausführen? (MPC604)
• Instruction Selection? (PBQP)
• Integrated Prepass Scheduling?

Person 3

• Loop Optimizations?
• ORA?
• RASE?