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

[system]

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.

[Eumel]

[HSCD] Lösungsvorschlag für die Klausur 2008-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 2008:

[Eumel]

---

Aufgabe 1 (Kurzfragen):

a)
Vorlesungsfolien 1 - Folie 8

b)
Allokation
Bindung
Ablaufplanung

c)
FPGAs
ASICs
DSPs
GPPs/CPUs
Microcontroller

d)
Bildverarbeitung = Matrix- und Multiplikationsoperationen → Parallelität

e)
Hoher Datendurchsatz
Viel Paralellität
Datenfluss-dominanter Code

f)
globale Registerzuweisung
Verwendungszähler
Registerzuweisung durch Graphfärbung

g)
Peephole: Entfernen überflüssiger Anweisungen, Algebraische Vereinfachungen, Kontrollflussoptimierungen, Operatorreduktionen
Lokale: common subexpression elimination, variable renaming, instruction interchange

h)
passive code elimination
copy propagation
code motion
induced variables and operator reduction

i)

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

j)

2^10 * 3^90

[Eumel]

---

Aufgabe 2 (Compiler und Codegenerierung):

a)
Lexikalische Analyse
Syntaktische Analyse
Semantische Analyse
Zwischencodegenerierung
Codeoptimierung
Codegenerierung

b)
siehe Anhang

c)

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

d)
siehe Anhang

e)

siehe Anhang

siehe Anhang

siehe Anhang

c(x) = verwendet(x,B) + 2 * aktiv(x,B)

c(a) = 1 + 0 = 1
c(b) = 0 + 0 = 0
c(c) = 0 + 0 = 0
c(d) = 0 + 0 = 0
c(e) = 0 + 0 = 0
c(f) = 0 + 2 = 2
c(g) = 2 + 2 = 4

Damit ergibt sich:

R0 := g
R1 := f
R2 := a 

Attachment:
2008_10_07-aufgabe2.pdf: https://fsi.cs.fau.de/unb-attachments/post_142514/2008_10_07-aufgabe2.pdf

[Eumel]

---

Aufgabe 3 (Entwurfsraumexploration):

a)
siehe Anhang

b)

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

c)

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

Nein Verhindert die Allokation nicht, hierfür müsste eine zeitliche Bedingung gesetzt werden.

d)

(1-->2): x1,1 + x1,2 + x2,1 + x2,2 = 2
(2-->4): x2,1 + x2,2 + x4,2 = 2

e)

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

f)

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

g)
Selektion
Mutation
Rekombination

h)

(50 / 280)
(52 / 240)
(64 / 220)
(72 / 200)

Attachment:
2008_10_07-aufgabe3.pdf: https://fsi.cs.fau.de/unb-attachments/post_142515/2008_10_07-aufgabe3.pdf

[Eumel]

---

Aufgabe 4 (Schätzung):

a)
Lineares Gleichungssystem:

d1 + d2 = d4 + d5 = x1
d4 = d6 = x2
d5 + d3 = d7 = x3
d6 + d7 = d2 + d3 + d8 = x4
x2 = 2 * x3
d2 = 9
d3 = 2
d8 = 1
d1 = 1

Lösen:

x1 = d1 + d2 = 1 + 9 = 10
x4 = d2 + d3 + d8 = 9 + 2 + 1 = 12
d6 + d7 = 12 = x2 + x3 = 2 * x3 + x3 = 3 * x3
x3 = 4
x2 = 2 * x3 = 2 * 4 = 8

WCET:

Summe(i = 1; N) c_i * x_i = 10 * t_exec + 8 * t_exec + 4 * t_exec + 12 * t_exec = 34 * t_exec

b)
siehe Anhang

Attachment:
2008_10_07-aufgabe4.pdf: https://fsi.cs.fau.de/unb-attachments/post_142516/2008_10_07-aufgabe4.pdf

[A7eex]

---

Hi,

Wir waren heute beim Übungsleiter der gemeint hat, dass bei ILPs der OR Operator nicht zulässig ist.(Das ist keine lineare Operation) Daher ist Aufgabe 3c so nicht korrekt. Dummerweise sitzen wir selbst noch am knobeln was da anstelle dessen richtig ist. Für 2 Tasks auf einer Ressource sieht es folgendermaßen aus. nCPU = x1CPU+x2CPU -( x1CPU*x2CPU)
Das muss man jetzt aber auf 4 erweitern und da stehen wir wie gesagt auf dem Schlauch.

Grüße

[ic97usop]

---

x1 + x2 - x1 * x2 ist dann aber auch nicht linear wegen der Multiplikation.

Kann man das Problem vielleicht auf ein Matching-Problem abbilden?

[pd1]

---

Hi,

zu Aufgabe 2 d)
Wieso gehst du für den Befehl Ri:=M von Kosten (2) aus?
Also wieso haben deine Blätter im Baum alle Kosten von (0,2,2)?
In der Aufgabe sind ja nur Kosten für c_ und c* gegeben, also bin ich für alle anderen Befehle von Kosten (1) ausgegangen.
In den neueren Klausuren sind ja für alle Befehle die Kosten entsprechend gelistet.

zu Aufgabe 4 b)
Wieso fasst du zuerst Konten 1 und 2 zusammen?
In der Übung und auch in der Vorlesungsfolie wurden bisher immer die Knoten mit der höchsten Metrik zuerst zusammengefasst.
Dementsprechend komme ich auf folgenden Graphen:
{1, 2, 3, 4, 5} → {14, 2, 3, 5} → {134, 2, 5} → {134, 25} → {12345}

[Eumel]

---

@pd

zu Aufgabe 2 d)
Wieso gehst du für den Befehl Ri:=M von Kosten (2) aus?
Also wieso haben deine Blätter im Baum alle Kosten von (0,2,2)?
In der Aufgabe sind ja nur Kosten für c_ und c* gegeben, also bin ich für alle anderen Befehle von Kosten (1) ausgegangen.
In den neueren Klausuren sind ja für alle Befehle die Kosten entsprechend gelistet.

Die Kosten hab ich einfach angenommen, weil eben nichts da stand.

@pd

zu Aufgabe 4 b)
Wieso fasst du zuerst Konten 1 und 2 zusammen?
In der Übung und auch in der Vorlesungsfolie wurden bisher immer die Knoten mit der höchsten Metrik zuerst zusammengefasst.
Dementsprechend komme ich auf folgenden Graphen:
{1, 2, 3, 4, 5} → {14, 2, 3, 5} → {134, 2, 5} → {134, 25} → {12345}

Welchen Wert hat denn die Kante 1->4? Meine Kopie ist nicht sonderlich gut und hab da einfach mal ne 13 angenommen.

[Eumel]

---

@A7eex

Wir waren heute beim Übungsleiter der gemeint hat, dass bei ILPs der OR Operator nicht zulässig ist.(Das ist keine lineare Operation) Daher ist Aufgabe 3c so nicht korrekt. Dummerweise sitzen wir selbst noch am knobeln was da anstelle dessen richtig ist. Für 2 Tasks auf einer Ressource sieht es folgendermaßen aus. nCPU = x1CPU+x2CPU -( x1CPU*x2CPU)
Das muss man jetzt aber auf 4 erweitern und da stehen wir wie gesagt auf dem Schlauch.

Dachte mir schon, dass das nicht stimmt. Wusste aber auch keine andere Lösung. In den Übungen bzw. in den Vorlesungsfolien hab ich auch nichts dazu gefunden. Oder hab ich nur i.was übersehen?

[ic97usop]

---

@Eumel

Welchen Wert hat denn die Kante 1->4?

[Eumel]

---

@ic97usop

@Eumel

Welchen Wert hat denn die Kante 1->4?

ok. Dann macht meine Lösung so natürlich keinen Sinn. Aber denk bei der Aufgabenstellung kann man net wirklich was falsch machen.

[JoeBlack]

---

@Eumel:1443458708

Aufgabe 2 (Compiler und Codegenerierung):

a)
Lexikalische Analyse
Syntaktische Analyse
Semantische Analyse
Zwischencodeoptimierung
Codeoptimierung
Codegenerierung

Zwischencodegenerierung

[JoeBlack]

---

@Eumel:1443458708

Da 3-färbbar sein soll, kommen nur Variablen mit „eigener“ Farbe in Frage → a bzw. g. Im Register sollte die Variable gehalten werden, die am häufigsten verwendet wird → a

Ich habe die Aufgabenstellung so verstanden, dass wir drei Register verwenden sollen.
D.h. für das Verwendungszählerverfahren c(x) = verwendet(x,B) + 2*aktiv(x,B) erhalten wir:
a = 1 + 0 = 1
b = 0 + 0 = 0
c = 0 + 0 = 0
d = 0 + 0 = 0
e = 0 + 0 = 0
f = 0 + 2 = 2
g = 2 + 2 = 4

Damit ergibt sich:
R_0 := g
R_1 := f
R_2 := a

[Eumel]

---

@JoeBlack

@Eumel:1443458708

Da 3-färbbar sein soll, kommen nur Variablen mit „eigener“ Farbe in Frage → a bzw. g. Im Register sollte die Variable gehalten werden, die am häufigsten verwendet wird → a

Ich habe die Aufgabenstellung so verstanden, dass wir drei Register verwenden sollen.
D.h. für das Verwendungszählerverfahren c(x) = verwendet(x,B) + 2*aktiv(x,B) erhalten wir:
a = 1 + 0 = 1
b = 0 + 0 = 0
c = 0 + 0 = 0
d = 0 + 0 = 0
e = 0 + 0 = 0
f = 0 + 2 = 2
g = 2 + 2 = 4

Damit ergibt sich:
R_0 := g
R_1 := f
R_2 := a

klingt vernünftiger als meins