80
2 Spezifikation und Modellierung
Beispielsweise wird die erste Ausführung von A drei Marken von der Rückwärtskante konsumieren, sodass nur noch eine Marke auf dieser Kante verbleibt, was
dem einen leeren FIFO-Platz nach der ersten Ausführung von A auf der linken Seite
entspricht.
Aufgrund der statischen Anzahl der erzeugten und der konsumierten Marken auf
jeder Kante ist es möglich, eine Ausführungsreihenfolge und den Speicherbedarf zur
Entwurfszeit zu bestimmen. Damit kann eine komplexe Bestimmung einer Ausführungsreihenfolge zur Laufzeit (ein dynamisches Scheduling) vermieden werden. Es
ist möglich, aus SDF-Graphen periodische Ausführungsreihenfolgen zu erzeugen.
Beispiel 2.22: Wir betrachten Ausführungsreihenfolgen (engl. schedules) von SDFGraphen anhand des Modells in Abb. 2.41. Angenommen, es gäbe anfänglich sechs
Abb. 2.41 SDF-Schleife
6
4
2
3
e 1
2
e
.......
A
B
Marken auf der Kante e 1 . Tabelle 2.2 (links) zeigt die resultierende Ausführungsreihenfolge. Aufgrund der begrenzten Anzahl anfänglich vorhandener Marken ist
nur eine sequentielle Ausführung möglich. Nunmehr nehmen wir an, es gäbe neun
Tabelle 2.2 Schedule für SDF-Schleife: links: 6 initiale Marken, rechts: 9 initiale Marken
Takt Marken auf Kanten Nächste Aktion
e 1
e 2
A oder B
0
6
0
A
1
3
2
A
2
0
4
B
3
6
0
A
4
3
2
A
Takt Marken auf Kanten
Nächste Aktion
e 1
e 2
A oder B oder (A und B)
0
9
0
A
1
6
2
A
2
3
4
A und B
3
6
2
A
4
3
4
A und B
initiale Marken auf der Kante e 1 . Unter der Annahme, dass alle Aktoren so früh wie
möglich ausgeführt werden, ergibt sich die Ausführung gemäß Tabelle 2.2 (rechts).
Unter dieser Annahme werden A und B gleichzeitig ausgeführt.
∇
Bei der Erzeugung von Ausführungsreihenfolgen könnten wir auch Zielfunktionen und Beschränkungen berücksichtigen, wie beispielsweise eine beschränkte
Anzahl von Prozessoren [57].
In obigem Beispiel führten die Kantengewichte 2, 3, 4 und 6 zu unterschiedlichen
Ausführungsraten der Aktoren A und B. Im Allgemeinen erlauben Kantengewichte
die Modellierung von Mehrraten-Signalverarbeitungsanwendungen, d.h. Anwendungen, bei denen bestimmte Signale mit Raten erzeugt werden, die ein Vielfaches der
Raten anderer Signale sind. Beispielsweise könnten in einem Fernsehgerät manche
2 Spezifikation und Modellierung
Beispielsweise wird die erste Ausführung von A drei Marken von der Rückwärtskante konsumieren, sodass nur noch eine Marke auf dieser Kante verbleibt, was
dem einen leeren FIFO-Platz nach der ersten Ausführung von A auf der linken Seite
entspricht.
Aufgrund der statischen Anzahl der erzeugten und der konsumierten Marken auf
jeder Kante ist es möglich, eine Ausführungsreihenfolge und den Speicherbedarf zur
Entwurfszeit zu bestimmen. Damit kann eine komplexe Bestimmung einer Ausführungsreihenfolge zur Laufzeit (ein dynamisches Scheduling) vermieden werden. Es
ist möglich, aus SDF-Graphen periodische Ausführungsreihenfolgen zu erzeugen.
Beispiel 2.22: Wir betrachten Ausführungsreihenfolgen (engl. schedules) von SDFGraphen anhand des Modells in Abb. 2.41. Angenommen, es gäbe anfänglich sechs
Abb. 2.41 SDF-Schleife
6
4
2
3
e 1
2
e
.......
A
B
Marken auf der Kante e 1 . Tabelle 2.2 (links) zeigt die resultierende Ausführungsreihenfolge. Aufgrund der begrenzten Anzahl anfänglich vorhandener Marken ist
nur eine sequentielle Ausführung möglich. Nunmehr nehmen wir an, es gäbe neun
Tabelle 2.2 Schedule für SDF-Schleife: links: 6 initiale Marken, rechts: 9 initiale Marken
Takt Marken auf Kanten Nächste Aktion
e 1
e 2
A oder B
0
6
0
A
1
3
2
A
2
0
4
B
3
6
0
A
4
3
2
A
Takt Marken auf Kanten
Nächste Aktion
e 1
e 2
A oder B oder (A und B)
0
9
0
A
1
6
2
A
2
3
4
A und B
3
6
2
A
4
3
4
A und B
initiale Marken auf der Kante e 1 . Unter der Annahme, dass alle Aktoren so früh wie
möglich ausgeführt werden, ergibt sich die Ausführung gemäß Tabelle 2.2 (rechts).
Unter dieser Annahme werden A und B gleichzeitig ausgeführt.
∇
Bei der Erzeugung von Ausführungsreihenfolgen könnten wir auch Zielfunktionen und Beschränkungen berücksichtigen, wie beispielsweise eine beschränkte
Anzahl von Prozessoren [57].
In obigem Beispiel führten die Kantengewichte 2, 3, 4 und 6 zu unterschiedlichen
Ausführungsraten der Aktoren A und B. Im Allgemeinen erlauben Kantengewichte
die Modellierung von Mehrraten-Signalverarbeitungsanwendungen, d.h. Anwendungen, bei denen bestimmte Signale mit Raten erzeugt werden, die ein Vielfaches der
Raten anderer Signale sind. Beispielsweise könnten in einem Fernsehgerät manche