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 17.03.2008
Hier mein Lösungsvorschlag (soweit vorhanden) zur Klausur vom 17.03.2008
Feedback, Verbesserungsvorschläge und fehlende Lösungsvorschläge sind ausdrücklich erwünscht 
Aufgabe 1 (Kurzfragen):
a) Welche Aussage ist wahr bzw. falsch?
- falsch
- falsch
- falsch
- falsch
- wahr
- wahr
b) Welche Aussage ist wahr bzw. falsch?
- wahr
- wahr
- wahr
- falsch
- wahr
- falsch
- wahr
- falsch
- wahr
- wahr
- wahr
- falsch
c) Geben Sie die Ihnen bekannten Spezifikationssprachen für den Entwurf von eingebetten Hardware-Software-Systemen an!
SystemC, Signal, Lustre, Esterel
d) Nennen Sie vier Optimierungskriterien bei dynamischen Ablaufplanungsproblemen!
Wartezeit, Antwortzeit, Latenz, Überhang (Tardiness), Verspätung (Lateness)
e) Erstellen und beschriften Sie das aus der Vorlesung bekannte Doppeldachmodell.
Siehe Skript “A_Einfuehrung_Handout” Folie 18
f) Was wird durch die Pfeile im Doppeldachmodell dargestellt?
Die Synthese
g) Welches sind die Hauptaufgaben, die auf jeder Abstraktionsebene zu lösen sind?
Allokation, Bindung, Ablaufplanung
h) Sind Markierte Graphen mächtiger als Synchrone-Datenfluß-Graphen (SDF)?
ANTWORT FEHLT
i) Was sind die Vorteile hierarchischer FSMs gegenüber konventionellen FSMs?
- spart Kanten bei XOR-Dekomposition
- spart Zustände bei AND-Dekomposition
- Kommunikation zwischen nebenläufigen Komponenten
Aufgabe 2 (Softwaresynthese)
a) Gegeben sind in Tabelle 1 fünf unterbrechbare Tasks mit ihren Ankunftszeiten tr(vi), ihren Ausführungszeiten di und ihren Deadlines td(vi)
1. Bestimmen Sie graphisch den mit dem EDF-Algorithmus resultierenden Ablaufplan.
[m]v5 -|–|–|–|–|–| | | | | | | | | |—|—|—|—|—|—|–
v4 -|–| |–|–| |–|–|–|–|–|—|—|—|—|—|—|—|—|—|—|–
v3 -| |–|–|–|–|–|–|–|–|–|—|—|—|—|—|—|—|—|—|—|–
v2 -|–|–|–|–|–| |–|–|–|–|—|—|—|—| | | |—|—|—|–
v1 -|–|–| | |–|–|–|–|–|–|—|—|—|—|—|—|—|—|—|—|–
----0–1–2–3–4–5–6–7–8–9–10–11–12–13–14–15–16–17–18–19–20–>[/m]
2. Angenommen eine Menge periodischer Tasks kann nicht mit EDF geplant werden. Kennen Sie einen Algorithmus, den man statt dessen verwenden kann? Begründen Sie Ihre Antwort?
Nein, da kein anderer Algorithmus eine Menge periodischer Tasks zulässig abarbeiten kann, die nicht durch EDF zulässig abgearbeitet werden kann.
(vgl. Skript “D_SoftwareSynthese_Handout” Folie 62)
b) Gegeben sind in Tabelle 2 fünf unterbrechbare Tasks mit hren Ankunftszeiten tr(vi), ihren Ausführungszeiten di und ihren Deadline td(vi). Die Tasks haben folgende Abhängigkeiten: v2 → v3, v3 → v5, v5 → v4
1. Bestimmen Sie die veränderten Ankunftszeiten tr(vi) und Deadlines td(vi) für einen EDF-Algorithmus, der Datenabhängigkeiten berücksichtigt (EDF*).
[m] | v1 | v2 | v3 | v4 | v5
tr(vi)* | 13 | 0 | 6 | 10 | 8
td(vi)* | 17 | 7 | 8 | 14 | 11[/m]
2. Zeichnen Sie den Ablaufplan gemäßg EDF*-Algorithmus
[m]
v5 -|–|–|–|–|–|–|–|–| | |—|—|—|—|—|—|—|—|—|—|–
v4 -|–|–|–|–|–|–|–|–|–|–| | | |—|—|—|—|—|—|—|–
v3 -|–|–|–|–|–|–| |–|–|–|—|—|—|—|—|—|—|—|—|—|–
v2 -| | | | | | |–|–|–|–|—|—|—|—|—|—|—|—|—|—|–
v1 -|–|–|–|–|–|–|–|–|–|–|—|—|—| | | |—|—|—|—|–
----0–1–2–3–4–5–6–7–8–9–10–11–12–13–14–15–16–17–18–19–20–>[/m]
c) Gegeben ist die folgende Menge von periodischen Tasks mit ihren Perioden P(vi), ihren Ausführungszeiten di und ihren Deadlines td(vi). Die Ankunftszeit tr(vi) aller Tasks ist 0.
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äß DM-Verfahren im Intervall von 0 bis 20.
ANTWORT FEHLT
Aufgabe 3 (Entwurfsraumexplosion, Codegenerierung)
a) Tragen Sie alle möglichen Bindungskombinationen von Tasks vi auf Ressourcen ri in Tabelle 4 ein! Berechnen Sie für jeden dieser Entwurfspunkte die Kosten c(ri) und die minimale Gesamtberechnungszeit L unter Berücksichtigung der Datenabhängigkeiten!
ANTWORT FEHLT
b) Tragen Sie die Kosten c(ri) und Gesamtberechnungszeit L Ihrer Entwurfspunkte aus Teilaufgabe a) in das Diagramm 2 ein! Beschriften Sie jeden Entwurfspunkt mit seiner zugehörigen Nummer! Welche Ihrer Entwurfspunkte sind Pareto-optimal?
ANTWORT FEHLT
c) Welche weiteren Entwurfspunkte gibt es, wenn die Anzahl der Ressourcen nicht beschränkt ist? Tragen Sie die neu hinzugekommenen Entwurfspunkte in Tabelle 5 und Diagramm 2 aus Teilaufgabe b) ein! Welche Entwurfspunkte sind jetzt Pareto-optimal?
ANTWORT FEHLT
d) Wie viele Entwurfspunkte gilt es maximal zu betrachten, wenn ein Taskgraph aus n Tasks besteht, wobei jeder Task auf drei unterschiedliche Ressourcen gebunden werden kann und die Anzahl der Ressourcen beschränkt ist?
ANTWORT FEHLT
e) Stellen Sie für den SDF-Graphen aus Abbildung 3 den zugehörigen Zustandsübergangsgraphen dar.
ANTWORT FEHLT
f) Geben Sie alle möglichen (periodischen) Loop Schedules für den SDF-Graphen an.
ANTWORT FEHLT
g) Bestimmen Sie für jeden gültigen Ablaufplan aus Teilaufgabe f) denjenigen Loop Schedule mit dem geringsten Programmspeicherbedarf! Welcher ihrer Loop Schedules weist den geringsten Programmspeicherbedarf auf? Gehen Sie davon aus, dass zur Codegenerierung Code-Inlining verwendet wird.
ANTWORT FEHLT
Aufgabe 4 (Ablaufplanung, Petrinetz)
a) Gegeben ist der in Abbildung 4 dargestellte Graph mit den fünf Knoten v1,…,v5. 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 jeweils einen Ablaufplan nach dem ASAP- und dem 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 = 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]
b) Gegeben sei der in Abbildung 5 dargestellte DFG. Es gibt den Ressourcetyp ALU(r) für die Ausführung der Operationen + und -. Außerdem gelte der folgende Ablaufplan t(v1) = 0, t(v2) = 0, t(v3) = 3, t(v4) = 3 und t(v5) = 6.
Zeichnen Sie den Konfliktgraphen für die Fälle von
-
Ablaufplanverträglichkeit
ANTWORT FEHLT -
starker Verträglichkeit
ANTWORT FEHLT
c) Betrachten Sie das folgende Petri-Netz
1. Welche der Transitionen sind schaltbereit?
t1, t2
2. Stellen Sie den Erreichbarkeitsgraphen für das Petri-Netz auf! Ist die Markierung M1 = (0, 0, 0)^T zu erreichen?
[m]
–>(2,0,0) -t1-> (1,1,0)
| | |
| | t2 | t2
| / /
| (1,0,1) -t1-> (0,1,1)
| t3 |
[/m]
Nein, M1 ist nicht erreichbar
3. Ist das Petri-Netz beschränkt, bzw. deadlockfrei? Was ist ein Konflikt? Kann es in dem gegebenen Petri-Netz zu einem Konflikt kommen? Begründen Sie Ihre Antworten.
Beschränkt: Ja, da endlicher Erreicharkeitsgraph
Deadlockfrei: Ja, da in jeder Markierung eine Transition aktivierbar
Konflikt: Ein Konflikt tritt auf, wenn zwei Transitionen aktivierbar sind, jedoch nicht beide gemeinsam (Bspw. Verzweigung)
Ist 1a) 1. wirklich falsch? In Übung 9 Aufgabe 2 haben die beiden ja die gleiche Latenz, wenn man die Latenz als max{t(v_i)+d_i}-min{t(v_i)} berechnet.
Also das sieht ja größtenteils richtig aus, hätte nur diese Korrekturen:
Aufgabe 1:
a) 1. wahr
4. wahr (siehe S.117 Skriptteil C)
6. falsch, nur für chordale Graphen
h)
Nein, es gilt nur zusätzlich, dass alle Kantengewichte immer 1 sind.
Aufgabe 4
Das Petrinetz ist nicht deadlockfrei, wenn man zwei mal t1 oder zwei mal t2 feuert, ist es tot.
Stimmt mir da jemand zu?
- a) 4. ist falsch weil es kein “oder” sondern ein “und” sein muss.
Die anderen sind so wie du sagst.
Bei Aufgabe 1. f) sollte man sagen, dass die vertikalen Pfeile die Synthese darstellen und die horizontalen Pfeile Verfeinerungen.
bei h) stimme ich dir zu
Bei Aufgabe 4 hast du auch recht, der Erreichbarkeitsgraph ist auch nicht vollständig.
Aufgabe 1b) 11. EDF minimiert die Anzahl verspäteter Tasks?
Ist doch falsch oder? EDF minimiert die maximale Verspätung, was aber doch nicht zwangsläufig einher geht…
Vielleicht gibt es ja Situationen, in denen sich Tasks so umplanen ließen, dass vielleicht einer noch später fertig wird, als eh schon (was Vmax vergrößern würde), dafür aber andere Tasks vor ihre Deadline rutschen…
Meinungen dazu? 
Aufgabe 4 (Ablaufplanung, Petrinetz
a)2. Bestimmen Sie die Mobilität u(vi) der Operationen vi € V.
Bei obiger Antwort werden mir die ALAP Zeiten nicht wirklich klar:
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
Unter der Annahme, dass v3 auf r2 mit d=3 und v2 auf r3 mit d=4 gebunden wird sieht der Ablauf wie folgt aus:
0 |
1 |
2 | (v2)
3 | (v2)
4 | (v1) (v2)
5 | (v3) (v2)
6 | (v3) (v4)
7 | (v3) (v5)
Unter der Annahme, dass v2 auf r2 mit d=3 und v3 auf r3 mit d=4 gebunden wird sieht der Ablauf wie folgt aus:
0 |
1 |
2 |
3 | (v1) (v2)
4 | (v3) (v2)
5 | (v3) (v2)
6 | (v3) (v4)
7 | (v3) (v5)
Der Lösungsvorschlag geht wohl davon aus das r2 und r3 auf die “langsamere” Ressource gebunden werden. Ist das hier zulässig?
c) Betrachten Sie das folgende Petri-Netz
2. Stellen Sie den Erreichbarkeitsgraphen für das Petri-Netz auf! Ist die Markierung M1 = (0, 0, 0)^T zu erreichen?
Sieht der Erreichbarkeitsgraph nicht vielmehr wie folgt aus?
–>(2,0,0) -t1 → (1,1,0) -t1-> (0,2,0)
| | |
| | t2 | t2
| / /
| (1,0,1) -t1-> (0,1,1)
| | |
| | t2 |
| V |
| (0,0,2) |
| |
| t3 |
Können denn t1 und t2 nicht jeweils zwei mal direkt hinter einander feuern und somit einen Deadlock erzeugen? Die Plätze p1 und p2 weisen ja keine Beschränkungen auf