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 19.03.2007
Hier mein Lösungsvorschlag (soweit vorhanden) zur Klausur vom 19.03.2007
Feedback, Verbesserungsvorschläge und fehlende Lösungsvorschläge sind ausdrücklich erwünscht 
Aufgabe 1 (Optimierung und Modellierung)
a) Optimierung
In der folgenden Abbildung sind die Werte bezüglich zweier Optimierungsziele (Gewinn und Geschwindigkeit) für eine Menge von Implementierungen dargestellt. Während der Entwurfsraumexploration will der Systementwickler die Geschwindigkeit wie auch den Gewinn maximieren.
-
Geben Sie alle nicht dominierten Lösungen an!
Fünf Punkte: (1 / 10), (5 / 8), (10 / 7), (11 / 2), (18 / 1) -
Andere Optimierungsverfahren versuchen, das Maxiumum einer gewichteten Summe zu finden. Geben Sie an, welche Lösung ein Systementwickler umsetzt, wenn er den Gewinn mit 0,25 und die Geschwindigkeit mit 0,75 gewichtet!
ANTWORT FEHLT
b) Modellierung
1. Geben Sie das Petri-Netz G = (P, T, F, K, W, M0) algebraisch an.
P = (S1, S2, S3, S4)
T = {T1, T2, T3, T4}
K(S1) = K(S2) = K(S3) = K(S4) = unendlich
F = {(S1, T1), (T1, S2), (S1, T2), (S2, T2), (T2, S3), (S3, T3), (T3, S4), (T3, S1), (S4, T4), (T4, S1)}
W(f1, …, f10) = 1
Mo = (2, 0, 0, 0)
2. Bestimmen Sie für G den Erreichbarkeitsgraphen mit M0 = (2, 0, 0, 0).
[m](2, 0, 0, 0) -T1-> (1, 1, 0, 0) -T2-> (0, 0, 1, 0) - T3 → (1, 0, 0, 1)
/\ | |
| | |
- - - - - - - - - - | - - - - - T4 - - - - - - - - - - - - - -
/
(0, 2, 0, 0) [/m]
3. Ist das Petri-Netz konfliktfrei, beschränkt bzw. deadlockfrei? Begründen Sie Ihre Antworten.
Konfliktfrei: Nein, da Verzweigung
Beschränkt: Ja, da endlicher Erreichbarkeitsgraph
Deadlockfrei: Nein, da keine Kante von (0, 2, 0, 0) wegführt
4. Zeichnen Sie den äquivalenten synchronen Datenflussgraphen G = V, E, cons, prod, d) für das modifizierte Petri-Netz. Die entsprechenden Gewichte sind an den Kanten des Petri-Netzes annotiert.
ANTWORT FEHLT
Aufgabe 2 (Hardwaresynthese)
a) Welche Aussage ist wahr bzw. falsch?
- wahr
- falsch
- falsch
- falsch
b) Gegeben ist der in Abbildung 1 dargestellte Datenflussgraph mit den fünf Knoten v1,…,v5 den Eingängen a,b,c,d und den Ausgängen x und y. Die Operationstypen sind ebenfalls in den Knoten dargestellt. Hierbei können Additionen und Subtraktionen auf einem Ressourcetyp r1 in einem Zeitschritt ausgeführt werden. Für Multiplikationen stehen zwei unterschiedlich schnelle Ressourcetypen zur Verfügung, nämlich der Ressourcetyp r2, welcher drei Zeitschritte benötigt und der Ressourcetyp r3, welcher vier Zeitschritte benötigt.
1. Ermitteln Sie einen Ablaufplan nach dem ASAP-Verfahren und dem ALAP-Verfharen, 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 = 7 für das ALAP-Verfahren betragen.
2. Bestimmen Sie die Mobilität u(vi) der Operationen vi € V.
| [m]i | ASAP | ALAP | u(vi) |
|---|---|---|---|
| 1 | 0 | 3 | 3 |
| 2 | 0 | 2 | 2 |
| 3 | 1 | 4 | 3 |
| 4 | 3 | 5 | 2 |
| 5 | 4 | 6 | 2[/m] |
[Seiten 6 und 7 fehlen mir]
-
Ablaufplanverträglichkeit:
ANTWORT FEHLT -
starker Verträglichkeit:
ANTWORT FEHLT
Aufgabe 3 (Softwaresynthese)
a) Im Folgenden werden Ablaufplanungsverfahren mit Echtzeitanforderungen betrachtet.
- wahr
- wahr
- wahr
- falsch
- wahr
- falsch
- wahr
- falsch
- wahr
- wahr
b) Gegeben sind in Tabelle 2 fünf unterbrechbare Tasks mit Ihren Ankunfszeiten ri, ihren Ausführungszeiten Ci und ihren Deadlines di.
Bestimmen Sie graphisch den Ablaufplan mit dem EDF-Algorithmus.
[m]J5 -|–|–|–|–|–|–|–|–|–|–| | |—|—|—|—|—|—|—|—|–
J4 -|–|–|–|–|–|–|–|–| | |—|—|—|—|—|—|—|—|—|—|–
J3 -| | |–| | | | |–|–|–|—|—|—|—|—|—|—|—|—|—|–
J2 -|–|–|–|–|–|–|–|–|–|–|—|—|—|—|—|—|—|—|—|—|–
J1 -|–|–|–|–|–|–|–|–|–|–|—|—|—| | | |—|—|—|—|–
----0–1–2–3–4–5–6–7–8–9–10–11–12–13–14–15–16–17–18–19–20–>[/m]
c) Zusätzlich zu den Vorgaben aus Aufgabe 3d) sollen nun folgende Abhängigkeiten gelten: J2 → J4, J3 → J2, J4 → J5
1. Bestimmen Sie die veränderten Ankunfszeiten ri* und Deadlines di* für einen EDF-Algorithmus, der Datenabhängigkeiten berücksichtigt (EDF*)
[m] | J1 | J2 | J3 | J4 | J5
ri* | 13 | 6 | 0 | 8 | 10
di* | 17 | 8 | 7 | 11 | 14
[/m]
2. Zeichnen Sie den Ablaufplan gemäß des EDF*-Algorithmus.
[m]
J5 -|–|–|–|–|–|–|–|–|–|–| | | |—|—|—|—|—|—|—|–
J4 -|–|–|–|–|–|–|–|–| | |—|—|—|—|—|—|—|—|—|—|–
J3 -| | | | | | |–|–|–|–|—|—|—|—|—|—|—|—|—|—|–
J2 -|–|–|–|–|–|–|–|–|–|–|—|—|—|—|—|—|—|—|—|—|–
J1 -|–|–|–|–|–|–|–|–|–|–|—|—|—| | | |—|—|—|—|–
----0–1–2–3–4–5–6–7–8–9–10–11–12–13–14–15–16–17–18–19–20–>[/m]
d) Gegeben ist die folgende Menge von periodischen Tasks. Führen Sie eine Ablaufplanung mittels des DM-Verfahrens durch.
1. Geben Sie hierfür zunächst einen hinreichenden Test an, der allgemein für eine Menge von n gegebenen Tasks gilt:
n
Summe [di / td(vi)] <= n * (2^(1/n) - 1)
i = 1
2. Zeichnen Sie nun den Ablaufplan gemäß des DM-Verfahrens im Intervall von 0 bis 20.
ANTWORT FEHLT
Aufgabe 4 (Synchroner Datenfluss und Codegenerierung)
a) Synchroner Datenfluss
- Überprüfen Sie die SDF-Graphen auf Konsistenz.
ANTWORT FEHLT
b) Codegenerierung
-
Geben Sie alle möglichen sequentiellen Ablaufpläne für die konsistenten SDF-Graphen aus Abbildung 4 an.
ANTWORT FEHLT -
Gibt es einen Single Appearance Schedule? Wenn ja, wie lautet dieser?
ANTWORT FEHLT -
Bestimmen Sie Ablaufpläne, die minimal bezüglich ihres Programmspeicherbedarfs sind und geben Sie den maximalen Programmspeicherbedarf an. Gehen Sie davon aus, dass zur Codegenerierung Code-Inlining verwendet wird.
ANTWORT FEHLT -
Bestimmen Sie Ablaufpläne, die minimal bezüglich ihres Datenspeicherbedarfs sind un geben Sie den maximalen Datenspeicherbedarf an. Es wird von einer statischen Allokation eines gemeinsamen Ringpuffers ausgegangen.
ANTWORT FEHLT -
Bestimmen Sie Ablaufpläne, die minimal bezüglich ihres Datenspeicherbedarfs sind und geben Sie den maximalen Datenspeicherbedarf an. Es wird von einer statischen Allokation eines Ringpuffers pro Kante ausgegangen.
ANTWORT FEHLT -
Zeichnen Sie für die Ablaufpläne mit dem geringsten Programmspeicherbedarf das Datenspeicherprofil.
ANTWORT FEHLT
Hi,
ein paar Anmerkungen/Fragen:
-
bei Aufgabe 1a sind das nicht die dominierten Lösungen, die du da angegeben hast? Also genau, die, die “guten” Lösungen. Gesucht waren doch die “schlechten”.
-
eine allgemeine Frage zu Aufgabe 3a, Frage4 (weil das öfter mal dranzukommen scheint):
prinzipiell kann man LDF doch schon für Datenunabhängige Tasks einsetzen, oder? Er ist zwar nicht dafür gedacht, aber es funktioniert doch. Das Ergebnis ist halt dasselbe wie bei EDD (Earliest Due Date). -
bei Aufgabe 3b ist Task 4 bei dir 3 Zeitschritte lang; in der Angabe steht 2 Zeitschritte; dadurch verschiebt sich auch Task 5 um einen Zeitschritt
Meine Lösung für diese Klausur: https://dl.dropboxusercontent.com/u/8705076/M2007.pdf (ich hoffe man kanns lesen ^-^)
Keine Garantie auf irgendwas, v.a. bei der letzten Aufgabe war ich mir sehr unsicher. Blatt 7 und 8 der Klausur fehlen mir, von daher konnte ich diese Aufgaben nicht bearbeiten.
zur 1a)
Nein, in der Klausur steht: Geben sie alle nicht dominierten Lösungen an, sprich alle Lösungen, die nicht dominiert werden, und das können nur die Pareto-Optima sein.
@R3count
Danke, alles klar. Hab wohl “dominierten” mit “dominierenden” verwechselt. Das ist aber auch umständlich formuliert.
zu deiner Lösung:
bei Aufgabe 2b: beim ALAP enden alle letzten Knoten bei der Latenzschranke und der Graph wird von dort aus rückwärts aufgebaut. Bei dir hängen Knoten 1 und 3 irgendwie “in der Schwebe”.
Achso sry, vergessen zu sagen. Der Graph zeigt in Aufgabe 2b) natürlich nur ASAP, ALAP hab ich da nicht eingezeichnet. 
Das hab ich schon bemerkt. Ich bin von der Tabelle ausgegangen. Wenn man das aufzeichnet hängen v1 und v3 zwischen Zeitschritt 2 und 6 anstatt das v3 an der Latenzschranke “dranklebt”.
Jo Tatsache. xD Danke, dass du das erwähnt hast, hatte es total vergessen dazu zu schreiben. 
Meine Anmerkungen bzw. Fragen:
Aufgabe 1
1a) Den Punkt (7,10) gibt es nicht, soll wohl (10,7) sein Warum berechnest du die gew. Summe nur von drei Punkten und nicht von allen?
4) Der Graph scheint mir falsch zu sein. Allgemein wird doch aus jeder Stelle des Petri-Netzes einfach eine “Transition” und die Transitionen des Petri-Netzes “verschwinden”. Demnach müssten im SDF 5 Stellen vorhanden sein, bei dir sinds aber sechs Stück und auch die Übergänge zwischen diesen “SDF-Stellen” scheinen mir nicht ganz zu stimmen. So gibt es bspw. keine Kante zu “S1”. Bin mir da aber auch noch nicht ganz sicher, wie die Überführung von Petri in SDF funktioniert.
Aufgabe 2
- Wieso beträgt die ALAP-Zeit für v3 bei dir 3? Wir haben eine Latenzschranke von 7 und die Multiplikation benötigt im schnellsten Fall 3 Zeiteinheiten. Müsste demnach bei 4 sein. Oder nehm ich beim ALAP immer die langsamste Komponente?
Aufgabe 3
a) 4. müsste falsch und 5. wahr sein (siehe hierzu im Skript “D_SoftwareSynthese_Handout” die Folie 37
d) Die gegebene Menge von periodischen Tasks lautet:
[m] | J1 | J2 | J3 | J4
Ci | 1 | 2 | 3 | 1
Di | 6 | 4 | 8 | 9
Ti | 6 | 7 | 10 | 10
[/m]
Hier hab ich persönlich keine Ahnung wie man da vorgehen soll. Gibts da im Skript i.welche guten Stellen dazu oder hat jmd. nen hilfreichen Link für mich?
Aufgabe 4
a) Du verwendest beim SDF-Graphen a) nur 5 der 6 Kanten ist das Absicht oder war das nur ein Versehen?
b) 3.-5. Wie kommst du da auf den jeweiligen Programmspeicherbedarf?
Aufgabe 1
1a) Habe da einfach mal 3 Punkte rausgenommen. Wenn man auf Nummer sicher gehen will, sollte man natürlich alle Punkte der Pareto-Front nehmen.
- Was meinst du mit: Aus jeder Stelle wird eine Transition? Wenn dann aus jeder Transition wird eine Stelle, aber prinzpiell habe ich keine Ahnung, wie man aus einem Petri-Netz einen SDF-Graphen macht, steht auch, soweit ich gesehen habe, nirgendwo in den Folien/Übungen. Wenn du da ne Quelle hast, wie man dabei vorgehen muss, wäre ich sehr dankbar.
Edit: Die Kante zu s1 hab ich vergessen. V:
Edit2: Ich glaub ich habs jetzt verstanden, ich poste bisschen später nochmal ne Lösung für diese Teilaufgabe.
Aufgabe 2
- Ja, da hast du Recht. Ich war da nämlich im Irrglauben, dass man für ALAP und ASAP im Graphen nicht 2 Operationen (hier: Multiplikation) derselben Ressource überlappen lassen darf. Natürlich ist dem nicht so, das ist mir allerdings erst selbst vor ungefähr einer Stunde aufgefallen. ^-^
Aufgabe 3
d) Wenn du mir sagen kannst, was Ci, Di und Ti sein sollen, dann kann ich dir sagen, wie man da vorgehen soll. Prinzipiell stehts ja im Skript: DM-Verfahren bedeutet, derjenige Task mit der kleinsten relativen Deadline hat eine höhere Priorität. Da es ein taskunterbrechendes Verfahren ist, bedeutet dies, dass es andere, sich in Ausführung befindliche Tasks, verdrängt.
Aufgabe 4
a) Nur ein Versehen, war da schon ganz durcheinander zu dem Zeitpunkt, hab es wohl nicht mitbekommen. ^-^ Aber vom Prinzip her sollte die Berechnung wenigstens stimmen. ^-^
b)
3. Naja, z.B. ist Schedule 2: (2AB)AC von der Programmgröße her kleiner als z.B. Schedule 1 (also rein von der Länge her), von daher benötige ich auch weniger Programmspeicher.
-
Statische Allokation, gemeinsamer Ringpuffer → ich nehme an, alle Kanten werden hier betrachtet. Naja, laut Ablaufplan hat jeder Ablaufplan einen Datenspeicherbedarf von 11, da die größte Summe der Daten auf jeder Kante 11 ist (siehe Folie D, S. 137).
-
Statische Allokation, gemeinsamer Ringpuffer, AUF NUR EINER KANTE (siehe auch: Folie D, S. 140):
“Summiere alle Maxima der Anzahl der Daten auf einer Kante e nach k Feuerungen von beliebigen Knoten.”
Hier bin ich einfach die Schedules durchgegangen und schaue mir dazu den Ablaufplan an, z.B. für Schedule 1: Kante e1 hat ein Maximum von 4, Kante e2 ein Maximum von 10 und e3 ein Maximum von 2. Summiert ergibt das 4+10+2 = 16. Ob das so stimmt, keine Ahnung, zumindest interpretiere ich so die Formel.
Sehe ich genauso, wenn man den Algorithmus (Übung 11) mal für datenunabhängige Tasks durchgeht, kommt das selbe raus wie bei EDD.
Meiner Meinung nach sind beide wahr
edit: sorry, war bei der falschen Aufgabe^^
generell verteilst du die Prioritäten statisch nach der Deadline und die Tasks sind unterbrechbar, heißt wenn ein Task mit höherer Priorität kommt, dann einfach den aktuellen unterbrechen, und den mit höhster Priorität ausführen
Ich habe mal eine Frage zu 1b) 2:
Im Zustand (1,0,0,1) könnte man doch eigentlich auch noch über T1 zu (0,1,0,1) kommen und daraus durch T4 wieder zu (1,1,0,0) oder?
ich glaub es muss mindestens eine Marke in S1 und S2 sein, damit T2 schalten kann, oder ?