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 2016-10-06
Hier ist mal mein Lösungsvorschlag zu der Klausur:
Aufgabe 1
a) Doppeldach zeichnen (Siehe Skript)
b) Allokation: Auswahl von Komponenten
Bindung: Zuweisung von Funktionen zu Komponenten
Ablaufplanung: Festlegung der Ausführungsreihenfolge
c) Datenflussgraph, weil hierfür Signalverarbeitungen nötig sind.
d) DSPs
e) Passive code elmination
copy propagation
code motion
induced variables and operator reduction
(Jedoch unsicher ob das stimmt)
f) Lexikalische Analyse
Syntaktische Analyse
Semantische Analyse
Zwischencodegenerierung
Codeoptimierung
Codegenerierung
g) 2^5 * 3^3 * 3^10 = 2^5 * 3^13
h) (32, 5)
(35, 8)
(36,13)
(37,43)
i) ILP: exaktes Lösungsverfahren, geeignet nur für kleine Problemgrößen, lineare Nebenbedingungen
Evolutionäre Algorithmen: Heuristisches Lösungsverfahren, geeignet für große Suchräume, breit anwendbares, robustes Verfahren,
geringe Anforderungen an Zielfunktion, leicht Parallelisierbarkeit
Aufgabe 2
a) → |:=|<--------------------
| |
| |
->|[]| ← ------>|+|<-------------------
| | | |
|g| |i| |t|–>|:=|<- -->||<–
| | |
| | |
—>|-|<---- | |f|
| | |
| -->||<-- —
| | | |
| |a| ->|+|<–
| | |
------------|b| |c|
b) 1.
(01) i:=0
(02) sum:=0
(03) if i >= l goto(19)
(04) t1:=i*4
(05) t2:=a[i]
(06) sum:= sum + t2
(07) if i<= 0 goto(15)
(08) if sum<= 20 goto (15)
(09) t3:= i-1
(10) t3:= t3 *4
(11) t4:= a[t3]
(12) t5:= t2 *t4
(13) a[t1]:= t5
(14) goto(17)
(15) t6:= i-2
(16) sum:=sum*t6
(17) i:= i+1
(18) goto(3)
(19)--------------------------------------
(01) i:=0
(02) sum:=0
--------------------------------------
(03) if i >= l goto(19)
--------------------------------------
(04) t1:=i*4
(05) t2:=a[i]
(06) sum:= sum + t2
(07) if i<= 0 goto(15)
--------------------------------------
(08) if sum<= 20 goto (15)
--------------------------------------
(09) t3:= i-1
(10) t3:= t3 *4
(11) t4:= a[t3]
(12) t5:= t2 *t4
(13) a[t1]:= t5
(14) goto(17)
(15) t6:= i-2
(16) sum:=sum*t6
--------------------------------------
(17) i:= i+1
(18) goto(3)
--------------------------------------
(19)
--------------------------------------- B1
|
->B2--------
| | |
| B3 |
| | |
| B4— |
| | | |
| --B5 | |
|| | | |
|| B6<-- |
|| | |
|->B7 |
| |
B8<-------
c) 1.
a: {1,1}, {2,3}, {4,5}
b: {3,4}
f: {1,4}, {5,5}
g: {1,5}
- alles verbinden außer a und b
- Graphenfärbung und
c(a) = 1 + 2 = 3
c(b) = 0 + 2 = 2
c(f) = 0 + 2 = 2
c(g) = 3 + 0 = 3
=> r1= g, r2=a, r3=f
Aufgabe 3
- (a) Konstruktive Verfahren: random mapping, hierarchical clustering
(b) iterative Verfahren: Kernighan-Lin Algorithmus, Simulated Annealing
(c) Exakte Verfahren: ILP, Enumeration der Lösungen
2.(a)r1
| |
==rbus
|| | |
|| r2
|| |
|| rp2p
|| |
== r3
(ich hoffe man versteht was ich mein)
(b) einfach verbinden 
(c) v5, v6, v7
-
(a)? (Eventuell Bit-string wie ILP aufgeschrieben)
(b)? (wäre dann 2^9) -
(a)
x_i,k ∈ {0,1} 1<= i <= 4, 1<= k <= 3
summe von k=1 bis 3 x_i,k = 1(b)
x_1,1 + x_1,2 + x_1,3 = 1
x_2,1 + x_2,2 = 1
x_3,1 + x_3,3 = 1
x_4,1 + x_4,3 = 1(c) -x_1,2 - x_4,3 + 2*x_7,p2p = 0
(d)
x_1,2 + x_2,2 <= 9
x_1,3 + x_3,3 + x_4,3 <= 13(e)
min{sum k=1 über 3 sum i=1 über 4 x_i,k * c_i,k}
Aufgabe 4
a) F = 100 * (2/(5*4)) * (0 + 0 + 0 + 0 + 0 + 1 + 1 + 1 + 1 + 0) = 40%
b) Takt 1 : MUL 1 und ALU 2; Takt 2: MUL 3, 4; Takt 3: MUL 6 und ALU 5; Takt 4: MUL 7, 8 und ALU 9;
T_ex = 240ns
c) occ(MUL)= 6 , occ(ALU)= 3
(1) 26ns <= T <= 30ns: slack(MUL) = 3T-60ns ; slack(ALU)= T-26ns; avgslack(T=26ns) = (6(3T-60ns)+3*(T-26ns))/9 = 12ns
(2) 30ns <= T <= 60ns: slack(MUL) = 2T-60ns ; slack(ALU)= T-26ns; avgslack(T=30ns) = (6(2T-60ns)+3*(T-26ns))/9 = 1,33ns
Damit ist die neue grenze bei T= 30ns was aber immer noch T_ex = 240ns bei 8 Takten
Ablaufplan gleich nur jetzt mit der Grenze jeden 30ns
d) weil die Abhängigkeiten so sind das man auch bei der avgslack(T) genauso lange braucht. Auch hier ist die Task auslastung noch bei fast 1
Hi
also bei aufgabe 3.3 bin ich mir jetzt auch nicht sicher ob ich richtig liege
a)
aber bit-string codiert ja nur wahr oder falsch, da wir aber 3 ausgehende kannten bei v1 haben kann man diese nicht damit codieren.
hätte daher auf permutation getippt aber leider ist bei der Übung 10 die permutation nur als fakultät dargestellt obwohl es laut wiki auch anders geht.
würde daher zur a sagen es muss eine Integer Genotyp sein.
b)
wäre ja dann genauso zu lösen wie aufgabe 1.g
also
3¹ * 2¹ * 2²
Hallo,
eine Frage habe ich zu der Aufgabe 2 c1.
Wie kann es sein, dass “g” immer aktiv ist! “g” wird doch erst im Zeitpunkt 2 von “a” verwendet und in der Aufgabe steht nicht ob z.B. “g” am Eingang aktiv ist oder nicht.
Kann mir jemand dabei helfen?