[HSCD] Lösungsvorschlag für die Klausur 2009-10-07

Master / Vertiefung LS 12: Hardware-Software-Co-Design
1

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.

2

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

Hier meine Lösungsvorschläge für die Klausur vom 07.Oktober 2009:

3

Aufgabe 1 (Kurzfragen):

a)
Vorlesungsfolien 1 - Folie 8

b)
Allokation
Bindung
Ablaufplanung

c)
Memory-Mapped-IO
Bus
Befehlssatzerweiterung

d)
VHDL
Verilog
ISP
SystemC

e)
Kernighan-Lin Algorithmus
Evolutionäre Algorithmen
Integer Linear Programs
Simulated Annealing

f)
Mutation
Crossover
Selektion

g)
ILP: exaktes Verfahren, kleine Problemgrößen, lineare Nebenbedingungen
EA: Lösung durch Approximation, große Suchräume, robust, breit anwendbar

h)
Zusammenfassung der Zielfunktionen in eine einzige Funktion

i)

(7,5 / 875)
(9 / 790)
(12,5 / 700)
(16 / 525)
(24 / 425)
(30 / 300)

j)

2^10 * 3^90
4

Aufgabe 2 (Compiler und Codegenerierung):

a)
Lexikalische Analyse
Syntaktische Analyse
Semantische Analyse
Zwischencodegenerierung
Codeoptimierung
Codegenerierung

b)
siehe Anhang

c)

code x := 1
(02) i := 1
(03) if i > m goto(13)
(04) if F2[i] <= 0 goto(11)
(05) F[x] := i
(06) t1 := x * x
(07) t1 := t1 * i
(08) F2[i] := F2[i] - t1
(09) x := x + 1
(10) goto(4)
(11) i := i + 1
(12) goto(3)
[/code]

d)

--------------------
(10)
--------------------
(20)
--------------------
(30)
--------------------
(40)
--------------------
(50)
(60)
(70)
(80)
--------------------
(90)
(100)
--------------------
(110)
(120)
--------------------
(130)
(140)
--------------------
(150)
--------------------

e) Diagramm siehe Anhang

R0 := 2
R1 := s
R1 := R1 * t
R0 := R0 * R1
R1 := x
R1 := R1 - m
R1 := R1 / R0
5

Aufgabe 3 (Entwurfsraumexploration):

a)
siehe Anhang

b)

x1,1 + x1,2 = 1
x2,2 + x2,3 = 1
x3,1 + x3,2 = 1
x4,2 = 1
x5,2 + x5,3 = 1

c)

x1,1 OR x2,1 = nCPU
x1,2 OR x2,2 OR x3,2 OR x4,2 OR x5,2 = nFPGA
x2,3 OR x5,3 = nDSP

d)

(1-->3): x1,1 + x1,2 + x3,1 + x3,2 = 2
(2-->3): (x2,2 + x3,1 + x3,2) OR (x2,2 + x2,3 + x3,2) = 2
(3-->5): (x3,1 + x3,2 + x5,2) OR (x3,2 + x5,2 + x5,3) = 2

e)

c2,node = 2 * x1,2 + 2 * x2,2 + 5 * x3,2 + x4,2 + 3 * x5,2 <= 9

f)

min{5 * x4,1 + 2 * x1,2 + 2 * x2,2 + 4 * x2,3 + 7 * x3,1 + 5 * x3,2 + 1 * x4,2 + 3 * x5,2 + 3 * x5,3}

Attachment:
2009_10_07-aufgabe3.pdf: https://fsi.cs.fau.de/unb-attachments/post_142510/2009_10_07-aufgabe3.pdf

6

Aufgabe 4 (Schätzung):

a)

A(W) = 106/109
A(X) = 128/137
A(Y) = 103/121
A(Z) = 59/132
F = 100 * ( 2 / (4 * 3) ) * (1 + 1 + 1 + 0 + 0 + 1) = 66,6666 %

b)

T = del_max = 80ns
4 Takte => 320ns

Ablaufplan siehe Anhang

occ(MUL) = 5; occ(ALU) = 2
1) für 30ns <= T < 40ns: slack(MUL) = 3T - 80ns; slack(ALU) = T - 30ns; avgslack(T) = ( (5 * (3T - 80ns)) + (2 * (T - 30ns)) ) / 7 = 50 / 7 (T = 30ns)
2) für 40ns <= T < 80ns: slack(MUL) = 2T - 80ns; slack(ALU) = T - 30ns; avgslack(T) = ( (5 * (2T - 80ns)) + (2 * (T - 30ns)) ) / 7 = 20 / 7 (T = 40ns)
T = 40
7 Takte => 280ns

Ablaufplan siehe Anhang

c)
CPU:

  • Multitasking / Scheduling => Allokation erst zur Laufzeit
  • Suboptimale Ausnutzung des Instruktionssatzes der Zielarchitektur
  • keine Berücksichtigung von prozessorspezifischen Compileroptimierungen
  • keine Berücksichtigung von Pipelining, Caching

Attachment:
2009_10_07-aufgabe4.pdf: https://fsi.cs.fau.de/unb-attachments/post_142511/2009_10_07-aufgabe4.pdf

7

Ergänzung zu Aufgabe 1 c):

  • Memory-Mapped-IO
  • Bus
  • Befehlssatzerweiterung

Aus Lösung der 1. Tafelübung, Teilaufgabe 2.

8

Zwischencodegenerierung :wink:

9

240 ns sollten 7*40ns=280ns sein?

Woher weiß man bei diesem Aufgabentyp eigentlich, für welches T man sich entscheiden soll?
Immer das T, bei dem die kürzere Ausführungszeit berechnet wird?

10

Ich habe bei der c) die Nachteile der WCET Abschätzung augezählt (VL Abschätzung von Software F. 12):

  • Suboptimale Ausnutzung des Instruktionssatzes der Zielarchitektur
  • keine Berücksichtigung von prozessorspezifischen Compileroptimierungen
  • keine Berücksichtigung von Pipelining, Caching
11

jop

Man nimmt das T, welches den avgslack minimiert.