78
2 Spezifikation und Modellierung
bekannten FIFO-Konflikte existieren hier nicht. Diese schöne Eigenschaft hat zur
Folge, dass KPNs häufig als interne Repräsentation innerhalb eines Entwurfsflusses
verwendet werden.
KPNs können durch einen merge-Operator erweitert werden (ähnlich der selectAnweisung in Ada, siehe Seite 124). Dieser erlaubt es, Leseaufträge für mehrere
Kanäle in eine Warteschlange einzureihen und darauf zu warten, dass einer der
Kanäle Daten erzeugt. Ein solcher Operator führt ein nichtdeterministisches Verhalten ein: wenn von mehreren Kanten gleichzeitig Daten eintreffen, dann ist die
Reihenfolge der Abarbeitung dieser Daten nicht mehr festgelegt. Diese Erweiterung
ist in der Praxis nützlich, sie macht aber die schönste Eigenschaft der KPNs zunichte.
Im Allgemeinen benötigen KPNs ein Scheduling zur Laufzeit, da sich ihr genaues
Verhalten nur schwer voraussagen lässt. Die Ursache dafür ist, dass wir keinerlei
Annahmen über die Geschwindigkeiten von Kanälen und Knoten machen. Da aber in
frühen Entwurfsphasen keinerlei Ausführungszeiten bekannt sind, ist dieses Modell
für diese Phasen sehr gut geeignet.
KPNs sind Turing-vollständig. Das bedeutet: alles, was mit einer Turing-Maschine
(dem Standard-Modell der Berechenbarkeit) berechnet werden kann, kann auch mit
einem KPN berechnet werden. Der Beweis basiert darauf, dass KPNs eine Obermenge der Boolean Dataflow (BDF)-Netzwerke sind und nach Buck [73] können
BDF-Netzwerke Turing-Maschinen simulieren. Eine Einschränkung der Anwendbarkeit von KPNs ergibt sich allerdings aus der Tatsache, dass die Anzahl der Prozesse
in KPNs fest ist, sich also nicht zur Laufzeit ändert.
Im allgemeinen Fall ist es unentscheidbar, ob FIFOs endlicher Länge für ein
gegebenes KPN-Modell ausreichen. Eine Reihe praktisch anwendbarer SchedulingAlgorithmen für KPNs werden in [294] beschrieben. Auch gibt es für einige spezielle
Fälle Beweise der Beschränkheit der Größe von FIFOs [99]. Beispielsweise können
Schranken für den Spezialfall Polyhedral Process Networks (PPNs) bestimmt werden. Bei PPNs müssen die Grenzen aller Schleifen zur Compilezeit bekannt sein.
Derin [125] nutzt Wissen über den Programmcode der Knoten für eine dynamische
Verlagerung von Prozessen zwischen Prozessoren.
2.5.3 SDF
Wenn wir Beschränkungen für das Timing von Knoten und Kanälen zulassen, wird
das Scheduling deutlich einfacher und außerdem lassen sich benötigte Puffergrößen
bestimmen. Dies ist beim SDF-Modell der Fall [334]. SDF bedeutete ursprünglich
Synchronous Data Flow bzw. synchroner Datenfluss, wird aber heute teilweise als
Static Data Flow gedeutet.
Das SDF-Modell [334] lässt sich am besten anhand seiner graphischen Darstellung erklären. Die Darstellung basiert auf einem gerichteten Graphen bestehend
aus Knoten und gerichteten Kanten. Die Knoten werden auch als Aktoren (engl. actors) bezeichnet. Die Kanten können Marken speichern, wobei die Speicherkapazität
standardmäßig unbegrenzt ist. Im Allgemeinen werden manche der Kanten anfangs
2 Spezifikation und Modellierung
bekannten FIFO-Konflikte existieren hier nicht. Diese schöne Eigenschaft hat zur
Folge, dass KPNs häufig als interne Repräsentation innerhalb eines Entwurfsflusses
verwendet werden.
KPNs können durch einen merge-Operator erweitert werden (ähnlich der selectAnweisung in Ada, siehe Seite 124). Dieser erlaubt es, Leseaufträge für mehrere
Kanäle in eine Warteschlange einzureihen und darauf zu warten, dass einer der
Kanäle Daten erzeugt. Ein solcher Operator führt ein nichtdeterministisches Verhalten ein: wenn von mehreren Kanten gleichzeitig Daten eintreffen, dann ist die
Reihenfolge der Abarbeitung dieser Daten nicht mehr festgelegt. Diese Erweiterung
ist in der Praxis nützlich, sie macht aber die schönste Eigenschaft der KPNs zunichte.
Im Allgemeinen benötigen KPNs ein Scheduling zur Laufzeit, da sich ihr genaues
Verhalten nur schwer voraussagen lässt. Die Ursache dafür ist, dass wir keinerlei
Annahmen über die Geschwindigkeiten von Kanälen und Knoten machen. Da aber in
frühen Entwurfsphasen keinerlei Ausführungszeiten bekannt sind, ist dieses Modell
für diese Phasen sehr gut geeignet.
KPNs sind Turing-vollständig. Das bedeutet: alles, was mit einer Turing-Maschine
(dem Standard-Modell der Berechenbarkeit) berechnet werden kann, kann auch mit
einem KPN berechnet werden. Der Beweis basiert darauf, dass KPNs eine Obermenge der Boolean Dataflow (BDF)-Netzwerke sind und nach Buck [73] können
BDF-Netzwerke Turing-Maschinen simulieren. Eine Einschränkung der Anwendbarkeit von KPNs ergibt sich allerdings aus der Tatsache, dass die Anzahl der Prozesse
in KPNs fest ist, sich also nicht zur Laufzeit ändert.
Im allgemeinen Fall ist es unentscheidbar, ob FIFOs endlicher Länge für ein
gegebenes KPN-Modell ausreichen. Eine Reihe praktisch anwendbarer SchedulingAlgorithmen für KPNs werden in [294] beschrieben. Auch gibt es für einige spezielle
Fälle Beweise der Beschränkheit der Größe von FIFOs [99]. Beispielsweise können
Schranken für den Spezialfall Polyhedral Process Networks (PPNs) bestimmt werden. Bei PPNs müssen die Grenzen aller Schleifen zur Compilezeit bekannt sein.
Derin [125] nutzt Wissen über den Programmcode der Knoten für eine dynamische
Verlagerung von Prozessen zwischen Prozessoren.
2.5.3 SDF
Wenn wir Beschränkungen für das Timing von Knoten und Kanälen zulassen, wird
das Scheduling deutlich einfacher und außerdem lassen sich benötigte Puffergrößen
bestimmen. Dies ist beim SDF-Modell der Fall [334]. SDF bedeutete ursprünglich
Synchronous Data Flow bzw. synchroner Datenfluss, wird aber heute teilweise als
Static Data Flow gedeutet.
Das SDF-Modell [334] lässt sich am besten anhand seiner graphischen Darstellung erklären. Die Darstellung basiert auf einem gerichteten Graphen bestehend
aus Knoten und gerichteten Kanten. Die Knoten werden auch als Aktoren (engl. actors) bezeichnet. Die Kanten können Marken speichern, wobei die Speicherkapazität
standardmäßig unbegrenzt ist. Im Allgemeinen werden manche der Kanten anfangs