[HSCD] Lösungsvorschlag für die Klausur 2014-09-24

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

[HSCD] Lösungsvorschlag für die Klausur 2014-09-24
Die Klausuren liegen bei der FSI-Informatik zum Kopieren für den Eigenbedarf bereit.

Hier meine Lösungsvorschläge für die Klausur vom 24.September 2014:


Aufgabe 1 (Kurzfragen):

a)
Vorlesungsfolien 1 - Folie 8

b)
Allokation
Bindung
Ablaufplanung

c)
Microcontroller: hohe Berechnungsanforderungen
DSPs: viel Parallelität, datenfluss-dominanter Code

d)
FPGA, da

  • flexibler als ASICs
  • perfomanter als DSPs bzw. Microcontroller
  • geringer Stromverbrauch

e)
???

f)
Start/Endknoten
Verzweigungsknoten
Iterationsknoten
Modulaufrufknoten

g)
Lexikalische Analyse
Syntaktische Analyse
Semantische Analyse
Zwischencodegenerierung
Codeoptimierung
Codegenerierung

h)

3^50 * 3^25 * 2^10 = 3^75 * 2^10

i)

(4 / 32)
(6 / 28)
(8 / 22)
(12 / 14)
(21 / 9)
(32 / 4)

j)
???


Aufgabe 2 (Compiler und Codegenerierung):

a)
Allokation: meist schon gegeben
Bindung: Registervergabe, Registerzuweisung, Befehlsauswahl
Ablaufplanung: Instruktionsreihenfolge

b)
siehe Anhang

c)

(01) j := 1
(02) if j >= N goto(15)
(03) b := 20
(04) l := j
(05) t1 := l * 4
(06) if x[t1] >= b goto(12)
(07) t2 := l * 2
(08) x[t1] := x[t1] + t2
(09) x[t1] := l + 1
(10) if x[t1] >= b goto(07)
(11) goto(13)
(12) b := x[t1]
(13) j := j + 1
(14) goto(02)

d)

--------------------
(01) i := m - 1
(02) j := n
(03) t1 := 4 * n
(04) v := a[t1]
--------------------
(05) i := i + 1
(06) t2 := 4 * i
(07) t3 := a[t2]
(08) if t3 < v goto(5)
--------------------
(09) j := j - 1
(10) t4 := 4 * j
(11) t5 := a[t4]
(12) if t5 > v goto(9)
--------------------
(13) if i >= j goto(23)
--------------------
(14) t6 := 4 * 1
(15) x := a[t6]
--------------------

e)

  1. ???
  2. siehe Anhang
R0 := b
R1 := c
R0 := R0 + R1
R1 := a
R1 := R1 - R0
R0 := y
R0 := x * R0
R0 := R0 / R1

Attachment:
2014_09_24-aufgabe2.pdf: https://fsi.cs.fau.de/unb-attachments/post_142541/2014_09_24-aufgabe2.pdf


Aufgabe 3 (Hardware/Software-Partitionierung):

a)
siehe Anhang

b)
siehe Anhang

c)
binäre Variable x_i,k = 1: Objekt o_i im Block p_k
Kosten c_i,k wenn Objekt o_i im Block p_k ist
x_i,k € {0,1} 1 <= i <= n; 1 <= k <= m
Summe von k=1 bis m über x_i,k = 1 für 1 <= i <= n
Beschränkungen werden durch lineare Nebenbedingungen gegeben

d)

x1,3 = 1
x2,1 + x2,2 + x2,4 = 1
x3,1 + x3,2 + x3,4 = 1
x4,1 + x4,3 + x4,4 + x4,5 = 1
x5,1 + x5,2 + x5,4 = 1
x6,4 + x6,5 = 1
x7,4 + x7,5 = 1

e)

x2,4 + x3,4 + x4,4 + x5,4 + x6,4 + x7,4 <= 5

f)

c1,node = 3 * x2,1 + 2 * x3,1 + 5 * x4,1 + 4 * x5,1 <= 9

g)

x5,1 + x7,4 <= 2
x5,1 + x7,5 <= 1
x5,2 + x7,4 <= 2
x5,2 + x7,5 <= 2
x5,4 + x7,4 <= 2
x5,4 + x7,5 <= 2

h)

min{Sum(k=1, m) Sum(i=1, n) xi,k * ci,k} (siehe Vorlesung Partitionierung 2 - Folie 7)

i)
iterative Verfahren:

  • Kernighan-Lin Algorithmus
  • Simulated Annealing
  • ???

konstruktive Verfahren:

  • random mapping
  • hierarchical clustering

Attachment:
2014_09_24-aufgabe3.pdf: https://fsi.cs.fau.de/unb-attachments/post_142542/2014_09_24-aufgabe3.pdf


Aufgabe 4 (Schätzung):

a)

F = 100 * ( 2 / (4 * 3) ) * (1 + 0 + 1 + 0 + 1 + 0) = 50 %

b)

T = del_max = 50ns
5 Takte => 250ns

Ablaufplan siehe Anhang

occ(MUL) = 5; occ(ALU) = 4
1) für 20ns <= T < 25ns: slack(MUL) = 3T - 50ns; slack(ALU) = T - 20ns; avgslack(T) = ( (5 * (3T - 50ns)) + (4 * (T - 20ns)) ) / 9 = 50 / 9 (T = 20ns)
2) für 25ns <= T < 50ns: slack(MUL) = 2T - 50ns; slack(ALU) = T - 20ns; avgslack(T) = ( (5 * (2T - 50ns)) + (4 * (T - 20ns)) ) / 9 = 20 / 9 (T = 25ns)
T = 25
7 Takte => 175ns

Ablaufplan siehe Anhang

d)
CPU: Multitasking / Scheduling => Allokation erst zur Laufzeit

Attachment:
2014_09_24-aufgabe4.pdf: https://fsi.cs.fau.de/unb-attachments/post_142543/2014_09_24-aufgabe4.pdf


Ich hätte ein paar Sachen zu Aufgabe 2.

Die If-Bedingen der Do-While Schleife sollte an das Ende des Blockes, da sie ja mindestens ein mal ausgeführt werden uss:
c)
(01) j := 1
(02) if j >= N goto(14)
(03) b := 20
(04) l := j
(05) if x[l] >= b goto(11)
(06) t1 := l * 2
(07) x[l] := x[l] + t1
(08) x[l] := l + 1
(09) if x[l] < b goto(06)
(10) goto(12)
(11) b := x[l]
(12) j := j + 1
(13) goto(02)

d)
Ich denke der Grundblock zwischen (11) und (12) ist falsch, da (12) nie Ziel einer Sprunganweisung ist:
(09) j := j - 1
(10) t4 := 4 * j
(11) t5 := a[t4]

(12) if t5 > v goto(9)


(13) if i >= j goto(23)

e)
Hier hätte ich eine allgemein Frage. Du hast den Teilbaum [a+c] und [d - (a+c)] mit 2 Registern gelöst.
Mit nur einem Register kommt man aber auf identische kosten. Gibt es hier irgend eine Faustregel? Je mehr Register man verwendet desto besser, oder eher so wenige Register wie möglich?
Allerdings komme ich mit nur einem Register auf etwas kompakteren Code:

R0 = c
R0 = b + R0
R0 = d - R0
R1 = y
R1 = x * R1
R1 = R1 / R0


Ich würde schon sagen, dass man bei gleicher Laufzeit weniger Register verwenden soll, um Speicherplatz zu sparen. Das kommt aber darauf an, wie viel vom übrigen Speicher verwendet wird. Ansonsten kommt das auf die jeweilige Anwendung an.

Eine Frage hätte ich aber noch zu deinem Code: verwendest du nicht auch 2 Register (R0 und R1)?

Ich würde den Code wahrscheinlich so gestalten:

R0 := c
R0 := b + R0
R0 := d - R0
R0 := y / R0
R0 := x * R0

Wäre sogar noch kompakter, glaub ich zumindest. :slight_smile:


Müsste falsch sein. Hab da Kosten und Durchsatz minimiert.

Richtig sollte sein:

(32 / 3)
(35 / 5)
(38 / 10)
(42 / 14)

stimme ich zu


Ich denk, dass ist falsch, da du den Operatorbaum damit umordnen würdest.


Da hast du wohl auch Recht. Allerdings müssen wir für den Array-Index noch ne temporäre Variable einführen und mit 4 multiplizieren. Denk ich zumindest :wink:
Hab meine Lösung aktualisiert.


Ich denke, dass wäre die Lösung für Kosten maximal und Durchsatz minimal, wobei auch dann der letzte Wert falsch wäre.

Für Kosten minimal und Durchsatz maximal sollte dies
(32/3)
(35/5)
(38/10)
(42/14)
richtig sein?

—edit
Und jetzt habe ich gerade gesehen, dass du es ja schon verbessert hast.