Datenfluss-Architektur

Eine Datenfluss-Architektur ist eine alternative Rechnerarchitektur zur sog. von-Neumann-Architektur, nach der die allermeisten heute gängigen Rechner implementiert sind. Ein nach der Datenfluss-Architektur implementierter Rechner heißt Datenflussrechner. Solche Rechner wurden zu Testzwecken gebaut, wie beispielsweise der Monsoon-Datenflussrechner am MIT. Einen kommerziellen Erfolg konnten Rechner dieser Architektur aber nicht verbuchen.

Unterschiede zur von-Neumann-Architektur

Maßgeblicher Unterschied zwischen einem von-Neumann-Rechner und einem Datenflussrechner ist, dass ein Datenflussrechner keine sequenziellen Programme abarbeitet, sondern Maschinenbefehle, die einen sog. Datenflussgraphen beschreiben.

Alle Mikroprozessoren, die nach dem gängigen von-Neumann-Prinzip arbeiten, folgen einem streng sequenziellen Verarbeitungsmodell. Die Befehlsabfolge folgt dem Von-Neumann-Zyklus, das heißt, nach dem Laden der gegenwärtigen Instruktion wird implizit die Adresse der nachfolgenden Instruktion angesteuert, diese wird geladen und ausgeführt. Das Laden des entsprechenden Befehls erfolgt unter der Kontrolle eines Programmzählers, ein Konzept, das reihenfolgerhaltendes Laden der einzelnen Maschinenbefehle impliziert.

Zwar zielt auch das dynamische Scheduling superskalarer Prozessoren, welches alle modernen Prozessoren der von-Neumann-Rechner implementieren, auf das Ausführen der Maschinenbefehle in Datenflussreihenfolge ab. Dabei wird der sequenziell gelesene Befehlsstrom zeitweise während des Bearbeitens in der Pipeline semantikerhaltend umgeordnet. Das Ergebnis des Bearbeitens des Befehlsstromes muss letztendlich jedoch dem sequenziellen Abarbeiten des Befehlsstroms äquivalent sein.

Die Maschineninstruktionen werden beim von-Neumann-Prinzip stets reihefolgeerhaltend geladen und das Speichern des Ergebnisses in den Registern (im Cache/im Speicher) nach Beendigung des jeweiligen Befehls muss reihenfolgeerhaltendend vorgenommen werden; so kann beispielsweise das Ergebnis des auf einen Sprungbefehl folgenden Befehls erst gespeichert werden, wenn die Sprungbedingung ausgewertet wurde und klar ist, ob der entsprechende Befehl überhaupt hätte ausgeführt werden sollen; die Berechnung des besagten Ergebnisses kann dagegen durchaus vor dem Auswerten der Sprungbedingung erfolgen. Das von-Neumann-Prinzip erfordert also die Abarbeitung der Maschineninstruktionen unter Berücksichtigung von Kontrollflussabhängigkeiten.

Die Abarbeitung des Programms eines Datenflussrechners wird nicht von Kontrollflussabhängigkeiten, sondern ausschließlich von Datenabhängigkeiten bestimmt. Das bedeutet, jede Maschineninstruktion kann prinzipiell geladen, ausgeführt und das Ergebnis der Berechnung gespeichert werden, sobald ihre Operanden vorliegen. Dieses Konzept bringt es mit sich, dass es einige Herausforderungen der von-Neumann-Architektur, wie die Sprungvorhersage - bei den verabeiteten Datenflussgraphen gibt es keine Sprünge - und das reihenfolgeerhaltenden Ausführen von Lade- und Speicherbefehle des abzuarbeitenden Programmes hier nicht gibt.

Datenflusssprachen

Zum Schreiben der abzuarbeitenden Programme für einen Datenflussrechner bedarf es einer Programmiersprache, deren kompiliertes Maschinenprogramm zur seiner Abarbeitung nicht eines Programmzählers bedarf und mit der man sehr einfach nebenläufige Vorgänge beschreiben kann.

Einige Beispiele für solche Sprachen sind:

Id (Irvine data flow language)
Lucid
Lustre
SISAL

Datenfluss-Programmiersprachen sind mit funktional Programmiersprachen verwandt, ihre Programme sind nichts anderes als Funktionen, die Eingabewerte auf Ausgabewerte abbilden. Beide befolgen die sog. Single-Assignment-Regel: Einer Variablen kann nicht in der gleichen Funktion mehrmals nacheinander ein Wert zugewiesen werden, was der eigentlichen mathematischen Bedeutung einer Variablen gerecht wird.

Programme, die mit einer Datenfluss-Programmiersprache geschrieben sind, können mithilfe eines sog. Datenflussgraphen modelliert bzw. mithilfe eines Compilers in Maschineninstruktionen übersetzt werden, die einen solchen beschreiben. Datenflussgraphen beschreiben in der Regel nebenläufige Prozesse, die von einem Datenflussrechner mehrfädig berechnet werden können.

Ein Datenflussgraph ist ein gerichteter Graph, dessen Knoten eine bestimmte Operation darstellen und dessen Token auf den Kanten die entsprechenden Operanden tragen. Seine Abarbeitung wird von Datenabhängigkeiten kontrolliert. Wenn genügend Tokens auf seinen Eingangskanten vorhanden sind, kann ein Knoten feuern, das heißt, einige der Token auf den Eingangskanten werden konsumiert und neue Token auf den Ausgangskanten produziert, was es nachfolgenden Knoten ermöglichen kann, zu feuern.

Der Datenflussgraph zur Rechten entspricht dem Programm:

input u, v, w;

x:= u+v*w;

y:=u-v*w;

output x,y;

Dies ist kein sequenzielles Programm.

Beim Abarbeiten des Graphen wandern die mit Werten markierten Token durch den Graphen; die Funktion des Knotens DUP ist es, das Token auf der Eingangskante auf beide Ausgangskanten zu duplizieren. Zu Beginn könnten die Knoten MUL und DUP feuern, entweder ein Knoten nach dem andern oder beide gleichzeitig; das Feuern geht hier in Form einer asynchronen Nebenläufigkeit vonstatten. Wenn beide Knoten gefeuert haben, sind ihre beiden Nachfolgeknoten ADD und SUB imstande, zu feuern. Die Ausführungsreihenfolge beeinflusst eventuell die Laufzeit beim Abarbeiten, hat aber keinen Einfluss aus das Ergebnis. Die Abarbeitung des Programms ist also deterministisch.

Weitere konzeptuell verschiedene Datenflussgraphen sind denkbar, etwa solche, bei denen Knoten mehrere Token auf einer Kante als Input haben können oder dynamische Datenflussgraphen, bei denen die Token, die von einem Knoten auf dessen Eingangskante konsumiert werden, von dessen Input abhängt; solche Graphen unterscheiden sich in ihrem Verhalten und ihrer Ausdrucksmächtigkeit.

Einfache Implementierung

Ein Datenflussrechner könnte Operationstupel der folgenden Form verarbeiten:

opc

rdy_{1}

v_{1}

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle rdy_2}

v_{2}

pc_{1}

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle lhs_1}

pc_{2}

lhs_{2}

Dabei sind

opc der Operationskode, der bestimmt, welcher Art die Operation ist, bspw. ADD, SUB, DUP, ...; dieser entspricht einem Knoten im Datenflussgraphen, der Token konsumiert und eine Berechnung vornimmt.
const ein möglicher Direktoperand
$v_{i}$ sind die Werte der Operanden; sie entsprechen den Token im Datenflussgraph
$rdy_{i}\in \mathbf {0,1}$ zeigt, ob $v_{i}$ verfügbar, also schon berechnet ist
$pc_{i}$ ist die Adresse eines Operationstupels, das auf das errechnete Ergebnis wartet; $pc_{i}$ entspricht der Ausgangskante eines Knotens in einem Datenflussgraphen.
$lhs_{i}\in \mathbf {0,1}$ zeigt an, ob das berechnete Ergebnis der linke oder rechte Operand des Operationstupels an der Speicherstelle Mem[ $pc_{i}$ ] ist.

Solche Operationstupel beschreiben direkt einen Datenflussgraphen; sie bewirken dabei einige Einschränkungen diesen betreffend:

Zu jedem Knoten gibt es höchsten zwei Nachfolgeknoten; mithilfe der Operation DUP lässt sich aber zu jedem Graphen ein äquivalentes Programm aus Operationstupel schreiben.
Es gibt nur jeweils zwei Operanden pro Knoten (neben dem möglichen Direktoperanden)
Jeder Knoten konsumiert lediglich ein Token auf seiner Eingangskante und produziert lediglich ein Token auf seiner Ausgangskante.

Einfache schematische Darstellung eines Datenflussrechners

Die Grafik zur Linken zeigt das Prinzip, nach dem ein Datenflussrechner arbeitet: Der Hauptspeicher enthält die Operationstupel, die einen Datenflussgraphen beschreiben. Der Datenflussrechner hat einen Prozessor mit mehreren gepipelineten Ausführungseinheiten - in der Regel handelt es sich bei einem Datenflussrechner auch um ein Multiprozessorsystem mit mehreren Prozessoren. In jedem Protessortakt wählt die Selektionseinheit einen Knoten, dessen Operanden $v_{1}$ und $v_{2}$ verfügbar sind und teilt diese einer verfügbaren Ausführungseinheit zu. Eine Distributionseinheit sendet die errechneten Operanden ihren korrespondierenden Operationstupeln zu. Dieses Schema ist sehr stark vereinfacht, insbesondere das Durchsuchen des Hauptspeichers nach entsprechenden Operationstupeln ist unpraktikabel und müsste in der Praxis anders gelöst werden.

Motivation für Multithreading

Datenflussrechner haben eine schlechte Performance, wenn sie einen einzelnen sequenziellen Thread ausführen. Die jeweiligen Ergebnisse eines Operationstupels werden in der letzten Stufe der Pipeline berechnet und Datenkonflikte würden dazu führen, dass nur jeweils eine Instruktion in der Pipeline ist, so dass die Pipeline offensichtlich keinen Nutzen bringt. Datenflussprogramme bestehen jedoch im Allgemeinen aus vielen nebenläufigen Threads, so dass es möglich ist, die Pipeline fortlaufend mit datenunabhängigen Instruktionen zu füllen, so dass keine Pipelinekonflikte entstehen und die Pipeline voll ausgelastet werden kann. Insbesondere ist es so auch möglich, lange Latenzzeiten zu überbrücken, die beispielsweise Lade- und Speicheroperationen verursachen; in der Zwischenzeit werden einfach datenunabhängige Instruktionen anderer Threads in die Pipeline gespeist. Dem Multithreading heutiger Prozessoren, oder Hyperthreading bei Intel's Pentium, liegt das selbe Prinzip zugrunde.

Vor- und Nachteile

Nachteile

Kein Nutzen von Registern - statt dessen Result-Forwarding - und schlechtes Ausnutzen von Caches: Die in der von-Neumann-Architektur genutzte Referenzlokalität beim Zugriff auf Daten- und Instruktionscaches ist in der Datenfluss-Architektur kaum vorhanden, bestimmt aber maßgeblich die Leistungsfähigkeit eines Caches. Highspeed-Prozessoren benötigen Caches, um ihre Ausführungseinheiten auslasten zu können. Da sich die Verarbeitungsgeschwindigkeit der Prozessorn im Vergleich zur Speicherzugriffsgeschwindigkeit in den letzten Jahren wesentlich stärker erhöht hat und Datenflussrechner wenig Gebrauch von Registern und Caches machen, stattdessen im Vergleich mit heutigen Rechnerarchitekturen wesentlich häufiger auf den Speicher zugreifen müssen, sind Datenflussrechner mit heute gängigen Supercomputern nicht wettbewerbsfähig.
Leistungseinbußen aufgrund von Duplikationsoperationen: Etwa 20% der verarbeiteten Knoten eines Datenflussgraphen sind Duplikationsoperationen, die in der von-Neumann-Architektur nicht existieren.
Schlechte Performance beim Verarbeiten eines einzelnen Threads: Beim Verarbeiten eines einzelnen Threads müssen Operationstupel warten, bis die Vorgängeroperation beendet wurde. Ein Datenflussrechner hat seine Stärke beim Ausführen vieler Threads, um mit vielen unbahängigen Oprationen seine Pipelines füllen und auslasten zu können.
Relativ breite Maschineninstruktionen: Der Datenpfad des Monsoon-Datenflussrechners war beispielsweise 144 Bit breit.

Vorteile

Ein Datenflussrechner kann viele Threads auf einem oder mehren Prozessoren ausführen; seine Performance steigt dabei beinahe linear mit der Anzahl seiner Prozessoren.
Programmierer müssen sich weniger um Nebenläufigkeit beim Programmieren kümmern.

Einfluss auf heutige Architekturen

Datenflussrechner wurden in den 1980er Jahren gebaut, sind mit den heutigen Supercomputern aber nicht mehr wettbewerbsfähig. Einige wichtige Konzepte von Datenflussrechnern „überleben“ jedoch in heutigen Prozessoren, so das dem Datenflussprinzip entsprechende nicht-reihefolgeerhaltende Ausführen der Maschinenbefehle beim dynamischen Scheduling superskalarer Prozessoren und das Multithreading.

Literatur

Arvind und R. Nikhil: Executing a program on the MIT tagged-token dataflow architecture. IEEE Transaction on computers, 1990
G. Papadopoulos und D. Culler: Monsoon: an explicit token-store architecture. International Symposium on Computer Architecture (ISCA), 1990 (Beschreibt die Architektur des Monsoon-Datenflussrechners)
J. Silic, B. Robic und T. Ungerer: Asynchrony in parallel computing: From data flow to multithreading. Technical report CSD, Computer Systems Department, Josef Stefan Institute, Ljubljana, Slowenien, 1997 (Listet alle bedeutenden Datenflussrechner, beschreibt deren historische Entwicklung und erklärt, warum heutige multithreadingfähige Prozessoren Abkömmlinge der Datenflussrechner sind)