[HSCD] Lösungsvorschlag für die Klausur 2013-04-04

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 2013-04-04
Die Klausuren liegen bei der FSI-Informatik zum Kopieren für den Eigenbedarf bereit.

Hier meine Lösungsvorschläge für die Klausur vom 04.April 2013:

3

Aufgabe 1 (Kurzfragen):

a)
Vorlesungsfolien 1 - Folie 8

b)
Allokation
Bindung
Ablaufplanung

c)
DSPs
Microcontroller

d)
schneller als CPUs
flexibler als ASICs
auch für kleine Stückzahlen (im Vergleich zu ASICs)

e)
Ich tippe mal auf den Datenflussgraphen. Es gibt neben dem datenflussdominanten noch das kontrollflussdominante und das heterogene Datenmodell, aber für die Signalverarbeitung braucht man Datenflussdominanz (siehe auch die Folie zu DSP).

f)
Lexikalische Analyse
Syntaktische Analyse
Semantische Analyse
Zwischencodegenerierung
Codeoptimierung
Codegenerierung

g)

(5/10)
(10/15)
(20/20)
(25/35)
f(5/10) = -2,5;
f(10/15) = -2,5;
f(20/20) = 0;
f(25/35) = -5

Vorangegangene Teilaufgabe war Einzieloptimierungsverfahren

h)

2^20 * 2^30 * 2^40 = 2^90

i)

0,8 * 4ns + 0,2 * 120ns = 27,2ns
4

Aufgabe 2 (Compiler und Codegenerierung):

a)

  1. siehe Anhang

  2. Ja.

b)

(01) j := 1
(02) if (j >= i) goto(13)
(03) t1 := j - 1
(04) t1 := t1 * 4
(05) a := x[t1]
(06) t2 := j * 4
(07) b := x[t2]
(08) if (a <= b) goto(11)
(09) x[t1] := b
(10) x[t2] := a
(11) j := j + 1
(12) goto(02)
--------------------
(01) j := 1
--------------------
(02) if (j >= i) goto(13)
--------------------
(03) t1 := j - 1
(04) t1 := t1 * 4
(05) a := x[t1]
(06) t2 := j * 4
(07) b := x[t2]
(08) if (a <= b) goto(11)
--------------------
(09) x[t1] := b
(10) x[t2] := a
--------------------
(11) j := j + 1
(12) goto(02)
--------------------

c)

  1. (a + b) * (e / (c * d))

  2. siehe Anhang

R0 := e
R1 := c
R1 := R1 * d
R0 := R0 / R1
R1 := a
R1 := R1 + b
R1 := R1 * R0

Attachment:
2013_04_04-aufgabe2.pdf: https://fsi.cs.fau.de/unb-attachments/post_142502/2013_04_04-aufgabe2.pdf

5

Aufgabe 3 (Hardware/Software-Partitionierung):

a)
siehe Anhang

b)
exaktes Lösungsverfahren, garantiert minimale Kosten, lineare Nebenbedingungen, optimale HW/SW-Partitionierung

c)

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

d)

Summe(n=1, k) xn,3 <= 3 (k = #Tasks)

e)

c4,node = 2*x3,4 + 2*x4,4 + 5*x5,4 + x6,4 + 3 * x7,4 <= 9

f)

x5,1 + x5,4 + x6,1 + x6,4 = 2 OR x5,4 + x5,5 + x6,4 + x6,5 = 2

g)

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

h)
heuristisch: hierarchical clustering
exakt: Integer Linear Program

Attachment:
2013_04_04-aufgabe3.pdf: https://fsi.cs.fau.de/unb-attachments/post_142503/2013_04_04-aufgabe3.pdf

6

Aufgabe 4 (Schätzung):

a)

F = 100 * ( 2 / (4 * 3) ) * (0 + 1 + 1 + 1 + 1 + 0) = 66,6666 %

b)
Harte Echtzeitsysteme: Hohe Treue bedeutet nicht automatisch korrekte Schätzwerte, für harte EZS hohe Exaktheit unerlässlich
Extrahieren von pareto-optimalen Punkten aus dem Suchraum: Hohe Treue ausreichen: Alle Punkte haben etwa gleiche Abweichung vom tatsächlichen Wert => Vergleichbarkeit gegeben

c)

T = del_max = 60ns
5 Takte => 300ns

Ablaufplan siehe Anhang

occ(MUL) = 5; occ(ALU) = 4
1) für 25ns <= T < 30ns: slack(MUL) = 3T - 60ns; slack(ALU) = T - 25ns; avgslack(T) = ( (5 * (3T - 60ns)) + (4 * (T - 25ns)) ) / 9 = 75 / 9 (T = 25ns)
2) für 30ns <= T < 60ns: slack(MUL) = 2T - 60ns; slack(ALU) = T - 25ns; avgslack(T) = ( (5 * (2T - 60ns)) + (4 * (T - 25ns)) ) / 9 = 20 / 9 (T = 30ns)
T = 30
8 Takte => 240ns

Ablaufplan siehe Anhang

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

Attachment:
2013_04_04-aufgabe4.pdf: https://fsi.cs.fau.de/unb-attachments/post_142504/2013_04_04-aufgabe4.pdf

7

Zunächst mal vielen Dank für die Lösungsvorschläge. Ich würde evtl. noch einige meiner Lösungen (ohne Gewähr) zu den “???”-Aufgaben ergänzen:

Aufgabe 1. e) Ich tippe mal auf den Datenflussgraphen. Es gibt neben dem datenflussdominanten noch das kontrollflussdominante und das heterogene Datenmodell, aber für die Signalverarbeitung braucht man Datenflussdominanz (siehe auch die Folie zu DSP).

Aufgabe 2. b)

(01) j = 1
(02) if (j >= i) goto (11)
(03) k = j - 1
(04) a = x[k]
(05) b = x[j]
(06) if (a <= b) goto (09)
(07) x[k] = b
(08) x[j] = a
(09) j = j + 1
(10) goto (02)
(11) return

An der Stelle bin ich allerdings nicht sicher, ob man sich so einfach Hilfsvariablen anlegen kann, würde ich aber gerne machen, da ich nicht glaube, dass man im 3-Adress-Code eine Rechenoperation als Arrayindex verwenden darf. Hier habe ich auch noch in Zeile (07) das k wiederverwendet, also keine neue Variable l = j - 1 angelegt, und auch da weiß ich nicht, ob man solche Optimierungen vornehmen darf.

Dementsprechend wäre Teil 2. bei mir:

(01) j = 1

(02) if (j >= i) goto (11)

(03) k = j - 1
(04) a = x[k]
(05) b = x[j]
(06) if (a <= b) goto (09)

(07) x[k] = b
(08) x[j] = a

(09) j = j + 1
(10) goto (02)

(11) return

Kann bitte jemand diese Lösungen kontrollieren?

8

ASIPs gehen wahrscheinlich auch noch

auch für kleine Stückzahlen (im Vergleich zu ASICs)

Datenflussgraphen, da der Fluss der Signale gut beschrieben werden kann

Zwischencodegenerierung :wink:

Übung 10, A3.3
Einzieloptimierungsverfahren: Findet nur eine Lösung entlang der konvexen Hülle, auf der die Pareto-Punkte liegen, obwohl es mehrere Pareto-optimale Lösungen geben kann

9

Bis auf das return und der Tatsache, dass meine Hilfsvariable t1 heißt, hab ich genau das Selbe raus bekommen. Endlich jemand der meine Meinung „Rechenoperation als Arrayindex ist verboten“ teilt :slight_smile:

10
11

Ich habe mich an die Folie 5-18 gehalten.

Jetzt denk ich aber, dass in meinem 3-Adress-Code ist meines Erachtens aber noch eine weitere Sache falsch ist: Ich bin davon ausgegangen, dass jedes Arrayelement 1 Byte verwendet. Wenn wir aber mit Integern arbeiten, müssen doch 4 Bytes verwendet werden. Muss man also vielleicht k noch mit 4 multiplizieren?

12

Ich habe bei der d) die Nachteile der WCET Abschätzung aufgezä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
13

Ja, mit dem Faktor vier hast du meiner Meinung nach Recht. Das wird auf den Vorlesungsfolien für Integer so gehandhabt.
Das müsste dann aber nicht nur für die Hilfsvariable gelten, sondern für alle Arrayzugriffe

Somit erfordert es eine neue Hilfsvariable…
(01) j = 1
(02) if (j >= i) goto (13)
(03) t1 = j - 1
(04) t1 = t14
(05) a = x[t1]
(06) t2 = j4
(07) b = x[t2]
(08) if (a <= b) goto (11)
(09) x[t1] = b
(10) x[t2] = a
(11) j = j + 1
(12) goto (02)
(13)

14

jop

15

stimm ich euch mittlerweile zu. Hab meine Lösung auch online gestellt und ist zu euren identisch.