[ES] Lösungsvorschlag zur Klausur vom 23.03.2009

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.

[ES] Lösungsvorschlag zur Klausur vom 23.03.2009
Hier mein Lösungsvorschlag (soweit vorhanden) zur Klausur vom 23.03.2009
Feedback, Verbesserungsvorschläge und fehlende Lösungsvorschläge sind ausdrücklich erwünscht :wink:

Aufgabe 1 (Kurzfragen)
a) Modellierung und Synthese
1. Was sind die drei Hauptaufgaben der Synthese?
Allokation, Bindung & Ablaufplanung

2. Was wird durch die beiden Dächer des Doppeldachmodells dargestellt?
Oberes Dach: Verhalten
Unteres Dach: Struktur

3. Welche Vorteile ergeben sich bei Statecharts durch XOR-Dekomposition und AND-Dekomposition gegenüber konventionellen FSMs?

  • spart Kanten bei XOR-Dekomposition
  • spart Zustände bei AND-Dekomposition
  • Kommunikation zwischen nebenläufigen Komponenten

4. Kann man durch Statecharts mehr modellieren als durch konventionelle FSMs?
Ja

5. Markieren Sie in folgendem Diagramm alle Pareto-Punkte. Beide Zielfunktionen sind zu minimieren.
Insgesamt vier Punkte: 5 / 700, 10 / 500, 30 / 400, 45 / 200

b) In der folgenden Tabelle sind drei periodische Tasks mit Berechnungszeiten di und Perioden P(vi) gegeben, wobei die relative Deadline jedes Tasks seiner Periode entspreche:

1. Sind die Tasks mit EDF planbar? Begründne Sie Ihre Antwort.
2/4 + 6/18 + 1/2 = 1 1/3 > 1 => Nein sind nicht mit EDF planbar!

2. Können die Tasks mit statischen Prioritäten geplant werden? Begründen Sie Ihre Antwort.
ANTWORT FEHLT

3. Nennen Sie vier Ablaufplanungsverfahren auf der Modulebene, die für Tasks mit unterschiedlichen Ankunftszeiten geeignet sind.
FCFS, SJF, SRTN, RR, EDF

4. Nennen Sie zwei Ablaufplanungsverfahren auf der Modulebene, die sich für Tasks mit Datenabhängigkeiten eignen.
LDF, EDF*

5. Formulieren Sie eine hinreichende Bedingung, um zu überprüfen, ob ein gültiger Ablaufplan für n Tasks mit Berechnungszeiten di, Perioden P(vi) und Deadline td(vi) existiert. Es gelte td(vi) <= P(vi)
n
Summe [di / td(vi)] <= n * (2^(1/n) - 1)
i = 1

6. Welche Aussage bezüglich der Existenz eines gültigen Ablaufplans lässt sich treffen, wenn die hinreichende Bedingung erfüllt ist?
Ablaufplan kann Deadlines nicht einhalten

7. Wie berechnet sich für einen Task vi mit der Ankunfszeit tr(vi), Endzeit te(vi) und Berechnungszeit di die Antwortzeit und Wartezeit?
Antwortzeit F = te(vi) - tr(vi)
Wartezeit F_W = te(vi) - di - tr(vi)

Aufgabe 2 (Spezifikation & Modellierung)
a)

1. Welche Transitionen sind schaltbereit?
t1, t3

2. Was versteht man unter einem Konflikt? Tritt ein solcher Fall hier auf? Begründen Sie Ihre Antwort.
Zwei Transitionen sind im Konflikt, wenn beide aktivierbar sind, jedoch nicht zu selben Zeit (Bspw. Verzweigung)

3. Existiert ein äquivalenter SDF-Graph? Falls ja, zeichnen Sie ihn; Falls nicht, begründen Sie Ihre Antwort.
ANTWORT FEHLT

b) Inwiefern unterscheiden sich SDF-Graphen und markierte Graphen?
Bei einem markierten Graphen besitzen alle Kanten ein Gewicht = 1
Bei einem SDF-Graphen besitzen alle Kanten ein Gewicht = t € N

c) Gegeben ist der folgende SDF-Graph, bestehend aus den Operationen A, B und C:

1. Geben Sie sowohl die graphische als auch die algebraische Darstellung eines Petri-Netzes mit äquivalentem Verhalten an.
GRAPHIK FEHLT
P = {P1, P2, P3, P4}
T = {A, B, C}
M0 = (3, 0, 2, 1)
F = {(A, P1), (P1, A), (A, P2), (P2, B), (P4, B), (B, P3), (P3, C), (C, P4)}
W[(A, P1)] = W[(A, P2)] = W[(P2, B)] = W[(P4, B)] = 1
W[(P1, A)] = W[(B, P3)] = W[(C, P4)] = 2
W[(P3, C)] = 4
K(P1) = K(P2) = K(P3) = K(P4) = unendlich

2. Bestimmen Sie den Erreichbarkeitsgraphen des Petri-Netzes.
[m] A A
(3,0,2,1) → (2,1,2,1) —> (1,2,2,1)
| |
| B | B
/ A /
(2,0,4,0) → (1,1,4,0)
| |
| C | C
/ A /
(2,0,0,2) → (1,1,0,2)
|
| B
/
(1,0,2,1)[/m]

3. Klassifizieren Sie das Petri-Netz hinsichtlich Lebendigkeit und Sicherheit. Begründen Sie Ihre Antwort. Geben Sie zusätzlich die kritischen Markenzahlen der Stellen an.
Lebendigkeit: Nicht Lebendig, da Knoten im Erreichbarkeitsgraph ohne wegführende Kante
Sicherheit: sicher, da endlicher Erreichbarkeitsgraph
KM(P1) = 3
KM(P2) = 2
KM(P3) = 4
KM(P4) = 2

4. Der SDF-Graph wird nun modifiziert, indem die Selbstkante von Operation A entfernt wird. Wie sieht es nun mit der Lebendigkeit und SIcherheit des äquivalenten Petri-Netzes (nicht anzugeben) aus? Begründen Sie Ihre Antwort.
Lebendigkeit: stark lebendig, da alle Transitionen lebendig sind
Sicherheit: nicht sicher, da in P1 nun unendlich Token entstehen können

Aufgabe 3 (Synthese)
a) Gegeben sei der Sequenzgraph aus Abbildung 1, der die Operationen v1,…,v5 enthält. Die jeweiligen Operationstypen sind in den Knoten dargestellt. Es sollen zwei Ressourcentypen zur Verfügung stehen, wobei Additionen auf Ressourcetyp r1 in einem Zeitschritt und Multiplikationen auf Ressourcetyp r2 in zwei Zeitschritten ausgeführt werden.

1. Ermitteln Sie einen Ablaufplan nach dem ASAP- und ALAP-Verfahren, in dem Sie für jeden Knoten vi einen Startzeitpunkt t(vi) bestimmen. Hierbei soll der früheste Zeitpunkt 0 für das ASAP-Verfahren sein und die Latenzschranke L = 6 für das ALAP-Verfahren betragen.

[m]Task ASAP ALAP u(vi)
v1 0 1 1
v2 2 3 1
v3 2 3 1
v4 3 4 1
v5 0 4 4[/m]

2. Ermitteln Sie die Mobilität der Operation v1,…,v5 und tragen Sie das Ergebnis ebenfalls in Tabelle 1 ein.
siehe oben

c) Im Folgenden soll ein Ablaufplan mit Hilfe eines ganzzahligen linearen Programms (ILP) optimiert werden. Dazu werden binäre Variablen xi,t eingeführt. Wobei der früheste Startzeitpunkt jedes Knotens vi deren ASPA-Zeit li und der späteste deren ALAP-Zeit hi entspreche.

1. Jede Operation soll genau einmal ausgeführt werden. Formulieren Sie diese Bedingung für die Operation v5 als lineare Gleichung. Verwenden Sie dazu die in Aufgabe 3a) ermittelten ASAP- und ALAP-Zeiten.
x5,0 + x5,1 + x5,2 + x5,3 + x5,4 = 1

2. Zeigen Sie für alle Knoten vi € V, wie aus den binären Variablen die tatsächlichen Startzeitpunkte t(vi) durch lineare Glecihungen bestimmt werden können.
0 * x1,0 + 1 * x1,1 <= t(v1)
2 * x2,2 + 3 * x2,3 <= t(v2)
2 * x3,2 + 3 * x3,3 <= t(v3)
3 * x4,3 + 4 * x4,4 <= t(v4)
0 * x5,0 + 1 * x5,1 + 2 * x5,2 + 3 * x5,3 + 4 * x5,4 <= t(v5)

3. Formulieren Sie nun die im Sequenzgraph abgebildeten Datenabhängigkeiten mit Hilfe linearer Gleichungen für alle Knoten vi € V.
t(v2) - t(v1) >= 2
t(v3) - t(v1) >= 2
t(v4) - t(v2) >= 1
t(v4) - t(v3) >= 1
t(vn) - t(v4) >= 2
t(vn) - t(v5) >= 2
t(v5), t(v1) >= t(v0) >= 0

4. Formulieren Sie die Bedingung, dass der komplette Ablauf nicht länger als 5 Zeitschritte brauchen darf.
t(vn) - t(v0) <= 5

5. Durch das ILP soll nun der Flächenverbrauch (Kosten), der durch die verwendeten funktionalen Einheiten entsteht, minimiert werden. Dies hängt von der Allokation ab, dargestellt durch die Variablen a(r1) für Addierer und a(r2) für Multiplizierer. Formulieren Sie die Ressourcenbeschränkungen durch lineare Gleichungen für die Additionen.
t = 0: 0
t = 1 : 0
t = 2: x2,2 + x3,2 <= a(r1)
t = 3: x2,3 + x3,3 <= a(r1)

6. Das ILP soll nun so erweitert werden, dass die Kosten, die durch die Allokation der Ressourcen entstehen, minimiert werden. Der Addierer hat die Kosten c(r1) = 1 und der Mutliplizierer die Kosten c(r2) = 2. Formulieren Sie die Zielfunktion des ILPs.
min C = a(r1) * c(r1) + a(r2) * c(r2)

d) Gegeben sei der folgende Datenflussgraph mit Informationen über die Ablaufplanung:
1. Vervollständigen Sie den Konfliktgraph für den Fall der Ablaufplanverträglichkeit
Kante zwischen 1 und 2
Kante zwischen 2 und 4

2. Wieviele Instanzen der Ressourcetypen ALU und Multiplizierer werden für den Ablaufplan mindestens benötigt?
ALU: 1
Multiplizierer: 2

3. Synthetisieren Sie den Datenpfad, indem Sie die notwendigen Verbindungen in die Abbildung eintragen. Neben den Konstanten sind die zwei Register R0 und R1 gegeben, sowie die Multiplexer i0 bis i5. Außerdem sind zwei Multiplizierer und eine ALU alloziert.
ANTWORT FEHLT

4. Vervollständigen Sie den Moore-Steuerautomaten des Steuerwerks. Das Steuersignal sei folgendermaßen definiert: (i0, i1, i2, i3 | e_MUL1, e_MUL2, e_ALU | e_R0, e_R1). Hierbei sind i0,…,i3 die Steuereingänge der Multiplexer, e_MUL1, e_MUL2, e_ALU sind die Enable-Signale der Multiplizierer bzw. ALU, und e_R0, e_R1 sind die Write-Enable-Signale der beiden Register.
Bei (1): (0, 0, 0, 0 | 1, 1, 0 | 1, 1)
Bei (2): (1, 1, 0, 0 | 1, 0, 0 | 1, 0)
Bei (3): (0, 0, 0, 0 | 0, 0, 1 | 1, 0)

Aufgabe 4 (Codegenerierung für SDF-Graphen)
a) Sind die Begriffe Repetitionsvektor und Ablaufplan im Zusammenhang mit SDF-Graphen gleichbedeutend? Begründen Sie Ihre Antwort.

b) Betrachtet wird der SDF-Graph in Abbildung 2. Gemäß der dargestellten Form befinden sich anfänglich keine Marken auf den Kanten.
1. Bestimmen Sie zwei unterschiedliche Ablaufpläne, so dass jeder Knoten mindestens einmal aktiviert und sich das System nach Ausführung des Ablaufplans wieder in seinem ursprünglichen Zustand befindet.
C^T * y = 0
y = Lambda * (1, 1, -1)^T

y1 = (1, 1, -1)^T
y2 = (2, 2, -2)^T

2. Wählen Sie einen der beiden zuvor bestimmten Ablaufpläne aus und geben diesen hier nochmals an. Zeichnen Sie nun das Speicheraktivitätsprofil für den Datenspeicher des ausgewählten Ablaufplans für einen kompletten Durchlauf. Zeichnen Sie bitte jeweils pro Kante des Graphen ein Profl in die auf den nächsten Seiten folgenden Diagrammvorlagen.
ANTWORT FEHLT

3. Wie groß ist maximal der Gesamtdatenspeicherbedarf für den in der vorherigen Teilaufgabe ausgewählten Ablaufplan?
ANTWORT FEHLT

c) Was versteht man unter einem sogenannten Single-Appereance-Schedule (SAS) und was wird durch ihn minimiert?
SAS sind Looped Schedules bei denen jeder Knotenbezeichner nur genau einmal vorkommt.
Minimiert wird das Clustering unter Beibehaltung gültiger Ablaufplanungsreihenfolgen.

d) Es sei allgemein eine Kante e mit prod(e) und cons(e) eines SDF-Graphen betrachtet. Des Weiteren sei für diesen SDF-Graphen ein beliebiger SAS gegeben. Geben Sie eine untere Schranke für die Anzahl der Marken an, die auf der Kante e gespeichert werden müssen.
cons(e) - prod(e)

e) Gegeben sei folgender Looped Schedule (unendlich(5(5(3D2E)4F)16G)) und folgender SDF-Graph. Die Anzahl der konsumierten Marken für die Kante (D,E) sei c1 = 3. Bestimmen Sie die fehlenden Werte für p1, p2, p3, c2 und c3 so klein wie möglich.
u = unendlich
(u(5(5(3D2E)4F)16G)) = (u(5(15D10E20F)16G)) = u(75D50E100F80G) = u( (75D) (50E) (100F) (80G) )

p1 && c1:
c1 = 3
75 * p1 - 50 * c1 = 0
=> p1 = 2

p2 && c2:
50 * p2 - 100 * c2 = 0
=> p2 = 2 * c2
=> p2 = 2
=> c2 = 1

p3 && c3:
100 * p3 - 80 * c3 = 0
=> p3 = 4/5 * c3
=> p3 = 4
=> c3 = 5


Nein, die Modellierungsmächtigkeit ist von beiden gleich.

Nein, da obiger hinreichender und notwendiger Test auch für statische Prioriäten anwendbar ist.

Eigentlich keine, da ja ein anderer hinreichender Test existieren kann.

Nein, da der Vorbereich von P1 != 1.

0 * x1,0 + 1 * x1,1 = t(v1)
2 * x2,2 + 3 * x2,3 = t(v2)
2 * x3,2 + 3 * x3,3 = t(v3)
3 * x4,3 + 4 * x4,4 = t(v4)
0 * x5,0 + 1 * x5,1 + 2 * x5,2 + 3 * x5,3 + 4 * x5,4 = t(v5)

Kante zwischen 1 und 2

Ohne Gewähr.


Bist du dir da sicher? Weil in den Folien haben RM und DM nämlich einen anderen Planbarkeitstest als EDF und bei EDF steht nichts von universell anwendbar drinnen.


Ich denke t=2 sollte heißen: x2,2 + x3,3 <= a(r1), da:

min{1-1,2-2}=0, max{0,2-3}=0 => p=0 bis 0, d.h. x3,t-p = x3,3-0 = x3,3.

?


Kante zwischen 2 und 4 → Ich würde sagen Nein, da es sich hierbei um zwei verschiedene Ressourcetypen handelt.

2 Likes

Kann mir das mit den Konfliktgraphen vlt. jmd. erklären? Ich werd da weder aus der kleinen Übungsaufgabe noch mittels der Folien schlau draus wie ich den Konfliktgraph für die drei Verträglichkeitsarten (schwach, Ablaufplan, stark) erstelle. Danke euch!


Konfliktgraph ist einfach das Komplement vom Verträglichkeitsgraph, d.h. zuerst erstellst du einen Verträglichkeitsgraphen. Dabei gibt es 3 verschiedene Arten:

1. schwach: zwei Operationen (Knoten) haben denselben Ressourcetyp => einfach im Verträglichkeitsgraphen eine Linie zwischen diese beiden Knoten ziehen.

2. mittel :stuck_out_tongue: (also ablaufplanverträglich): zwei Operationen sind schwach verträglich UND es gilt, dass entweder die Startzeit von z.B. v(i) >= Startzeit v(j) + d(j) oder Startzeit von v(j) >= Startzeit von v(i) + d(i).

3. stark verträglich: zwei Operationen sind schwach verträglich UND im Graphen haben die beiden Knoten einen gerichteten Pfad (also Linie mit Pfeil) zueinander, d.h. entweder von v(i) → v(j) oder v(j) → v(i).

Je nach Vorgabe erstellst du jetzt also einen Verträglichkeitsgraph nach 1, 2 oder 3. Was du dabei noch beachten musst ist, dass du Operationen unterschiedlichen Ressourcetyps nicht miteinander verbinden darfst (zumindest hab ich das so verstanden).

Erstellen des Konfliktgraphs: Wenn du nun den Verträglichkeitsgraphen hast, dann zeichnest du einfach alle Knoten ab und verbindest dann all diejenigen Knoten im Konfliktgraph, die im Verträglichkeitsgraphen nicht miteinander verbunden sind. Das wars auch schon. :slight_smile:

1 Like

klasse! Danke dir!


Hat jemand hier eine Lösung für Aufgabe 4 a und b?


Vll (3A)(6B)(2C) oder so? Gibt irgendwie so viele Punkte?!
Zählt es als unterschiedlich, wenn man jetzt nochmal
das Doppelte nimmt? :smiley:


Ich hab mir gedacht das man noch (3A)(2(3B)C) machen könnte :smiley:


4a) Nein, da der Repetitionsvektor nur angibt, welche Knoten feuern, aber nicht deren Reihenfolge