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

Aus VoWi
Zur Navigation springen Zur Suche springen

Schriftliche Prüfung[Bearbeiten | Quelltext bearbeiten]

Vorwort[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Beispiel 1[Bearbeiten | Quelltext bearbeiten]

Angabe[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Angabe[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Angabe[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Angabe[Bearbeiten | Quelltext bearbeiten]

Software Pipelining:

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

Zykles:

add:1
load:2
branch:1
Vermutete Antwort[Bearbeiten | Quelltext bearbeiten]

(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[Bearbeiten | Quelltext bearbeiten]

Person 1[Bearbeiten | Quelltext bearbeiten]

  • 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[Bearbeiten | Quelltext bearbeiten]

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

Person 3[Bearbeiten | Quelltext bearbeiten]

  • Loop Optimizations?
  • ORA?
  • RASE?