Voir la source de Architecture Dataflow

Le '''''{{lang|en|dataflow}}''''' (en {{lang-fr|flux de données}}) est une architecture où les données sont des entités actives qui traversent le programme de manière [[asynchrone]], contrairement à l'architecture classique [[Architecture de von Neumann|von Neumann]], où elles attendent passivement en [[Mémoire informatique|mémoire]] pendant que le programme est exécuté séquentiellement suivant le contenu du [[Registre (informatique)|pointeur de programme]] (PC). On parle aussi d'ordinateur cadencé par les données.

== Principe de fonctionnement ==
Dans une architecture flux de données, les [[programmes]] sont représentés sous forme de [[graphe (théorie des graphes)|graphes]] : un [[nœud (réseau)|nœud]] représente une opération à effectuer, tandis que les données circulent sur les [[Lexique de la théorie des graphes#A|arcs]] et forment les entrées aux nœuds. Les données sont transportées par des jetons (''{{lang|en|tokens}}''). La règle de base, dite « de déclenchement », instaure que lorsqu'un nœud voit toutes ses entrées satisfaites, il est activé et produit une valeur en sortie, et les jetons présents en entrée sont supprimés.

Ces architectures sont étroitement couplées aux langages de [[programmation fonctionnelle]]. Elles ne génèrent pas d'[[Effet de bord (informatique)|effet de bord]], donc ne nécessitent pas de [[Mémoire partagée (communication inter-processus)|mémoire partagée]], ni de [[Unité de contrôle|séquenceur]] ou de [[registre (informatique)|pointeur de programme]]. Elles sont aussi éminemment parallèles : l'unité responsable de l'exécution des instructions issue de la mémoire contenant le programme doit posséder un nombre relativement élevé de processeurs (16 et plus) afin de maximiser la puissance totale de l'ordinateur. 

Plusieurs unités de calcul traitant des données différentes les classent dans la famille des ordinateurs [[MIMD]] ({{lang|en|Multiple Instructions, Multiple Data}}).

== Les graphes comme langage ==
Un nœud computationnel peut être représenté comme le sommet d'un [[graphe (théorie des graphes)|graphe]]. Les jetons circulent sur les arcs reliant les sommets. Quand deux jetons contenant respectivement les {{nobr|valeurs 3 et 5}} se présentent aux entrées du nœud, celui-ci exécute l'opération pour laquelle il est conçu (ici une addition), génère un jeton en sortie représentant la somme ({{nobr|3 + 5}}), 8, et supprime les jetons d'entrée :

{{multiple image|direction = horizontal| align = center|image1=Singledataflownode.png| width1 = 100px|caption1=Un nœud de base d'une architecture ''{{lang|en|dataflow}}''.|image2=Dataflowfiringnodes.png|width2 = 240px|caption2=Activation d'un nœud. Notez la disparition des jetons d'entrée après la production d'une valeur en sortie.}}

L'expression plus complexe z = (x + y) × (x - y) correspond au graphe ci-dessous. On constate que le parallélisme est implicite : les deux nœuds '''+''' et '''-''' sont activables simultanément.

[[Image:Dataflowexpr.png|186px|thumbnail|center|Le programme (graphe) correspondant à l'expression z = (x + y) * (x - y).]]
{{Clr}}

Grâce à deux types de nœuds appelés ''{{lang|en|switch}}'' et ''{{lang|en|merge}}'', on peut coder la condition ''si''. Le premier type possède deux entrées et deux sorties, tandis que le second possède trois entrées et une sortie. Le type ''{{lang|en|switch}}'' répercutera son jeton d'entrée sur l'une ou l'autre de ses sorties suivant l'état de sa seconde entrée. Le type ''{{lang|en|merge}}'' fera la sélection d'un de ses deux jetons d'entrée suivant la valeur d'un troisième. Schématiquement :

{|
|-
| valign="top"|[[Image:Switchdataflownode.png|186px|thumbnail|Un nœud de type ''{{lang|en|switch}}''. V et F tiennent lieu de Vrai et Faux.]]
| valign="top"|[[Image:Mergedataflownode.png|186px|thumbnail|Un nœud de type ''{{lang|en|merge}}''. V et F tiennent lieu de Vrai et Faux.]]
|}

Voici deux exemples de ces instructions, dans un test conditionnel et dans une boucle. Notez l'initialisation à Faux sur le nœud ''{{lang|en|merge}}'' pour correctement sélectionner la valeur de x.

{|
|-
| valign="top"|[[Image:Conditiondataflow.png|286px|thumbnail|Le graphe du programme y = (IF x > 3 THEN x + 2 ELSE x -1) × 4.]]
| valign="top"|[[Image:Dataflowwhileloop.png|286px|thumbnail|Le graphe du programme WHILE x > 0 DO x - 1.]]
|}

=== Implications de l'utilisation de graphes ===
# Localité : les interdépendances entre les données sont très localisées, contrairement aux langages impératifs habituels qui utilisent des [[Variable globale|variables globales]] (situées « loin » des procédures qui sont susceptibles de les modifier).
# Pas d'effets de bord, pas de notion de passage de paramètres par référence : les valeurs sont dupliquées.
# [[Dépliage des boucles]] : pour paralléliser l'exécution des boucles, le code doit être déplié pour que chaque [[itération]] puisse être exécutées en parallèle.
# Règle de la référence unique :
:: le nom d'une variable ne peut apparaître qu'une seule fois dans une assignation. Pour éviter cela, on renomme la variable à partir de ce point, et on utilise ce nouveau nom par la suite. Par exemple :
<br />
{| border="1" cellpadding="5" cellspacing="0" align="center"
|- 
| X = P - Q  ||  X = P - Q
|-
| {{Souligner|X}} = {{Souligner|X}} × Y  || '''X1''' = X × Y
|-
| W = X - Y  || W = '''X1''' - Y 
|}
{{Clr}}
:: Cette règle a été proposée en 1968.

== Structure des graphes ==
Pour mieux comprendre comment les programmes flot de données peuvent être exécutés par un ordinateur, il est plus aisé de représenter les graphes sous la forme d'une collection de structures reliées entre elles par des pointeurs.

Le premier graphe z = (x + y) × (x - y) peut être représenté par cette structure :

[[Image:Dataflowsimplestructure.png|thumbnail|center|286px|Représentation structurelle de l'expression z = (x + y) × (x - y).]]

Chaque nœud est représenté par un bloc dont le premier élément est l'opération à effectuer, puis suivent les emplacements indiqués par des parenthèses « [ ] » qui sont destinées à contenir les paramètres de l'opération, ainsi que des emplacements contenant les adresses où sera placé le résultat. Certains emplacements peuvent éventuellement contenir des constantes.

Les itérations ne posent pas de problème non plus, ci-dessous la structure de la [[Boucle while|boucle WHILE]] précédemment évoquée :
[[Image:Dataflowiterstructure.png|thumbnail|center|286px|Représentation structurelle d'une itération.]]

== Types de machine ==
Il existe plusieurs types d'ordinateur flot de données, mais on peut distinguer deux modèles :
* Le modèle statique : il n'y a qu'un seul jeton sur un arc à un instant donné ;
* Le modèle dynamique : il peut y avoir plusieurs jetons en attente sur un arc.

Des machines hybrides ''{{lang|en|dataflow}}''/[[Architecture de von Neumann|von Neumann]] ont aussi été conçues ([[Massachusetts Institute of Technology|MIT]] [[P-RISC]]).

=== Machines statiques ===
Rentrent dans cette catégorie la machine conçue par [[Jack Dennis]] du [[Massachusetts Institute of Technology]] en [[1974]]. La difficulté rencontrée sur cette architecture est la contrainte de n'avoir qu'une seule valeur (jeton) sur un arc à un moment donné (car on ne peut pas faire de différence entre les jetons). Elle est effacée par l'utilisation de jetons de contrôles qui acquiescent la transmission des données d'un nœud à un autre.

=== Machines dynamiques ===
Ces machines associent un marqueur (''{{lang|en|tag}}''), ou une couleur, à chaque jeton. La règle de base est modifiée, et devient : « lorsqu'un nœud voit toutes ses entrées satisfaites par des jetons de même couleur, il est activé et produit une valeur en sortie, avec sa propre couleur, et les marqueurs et jetons d'entrées sont effacés ». L'architecture en est simplifiée et le dépliage des boucles se fait tout seul : il est créé autant de couleurs et jetons que nécessaire.

=== Exemple : la machine ''{{lang|en|dataflow}}'' dynamique de Manchester ===
[[Image:Dataflowmanchester.png|thumbnail|286px|right|Synoptique simplifié de la machine de l'Université de Manchester ([[1981]]).]]
Son architecture simplifiée est représentée par la figure ci à droite. Elle est volontairement simplifiée, mais est tout à fait représentative des machines de type dynamique. On remarque immédiatement qu'elle est très facilement « [[pipeline (informatique)|pipelinable]] », ce qui bien sûr améliore sensiblement les performances. Il est spécifié en caractères italiques le type de paquets circulant entre deux unités.

Les jetons appartenant à une même instruction sont appairés dans l'unité de correspondance. Ils sont envoyés vers l'unité où sont stockées les instructions, d'où ils chargent les instructions dont ils dépendent. Ces paquets enfin exécutables sont dirigés vers l'unité de calcul qui, à la suite de l'exécution de l'instruction reçue en entrée, va émettre de nouveaux jetons. L'unité d'entrée/sortie sert à communiquer avec l'ordinateur externe qui contrôle la machine ''{{lang|en|dataflow}}'', par le biais du bus schématisé verticalement, qui permet l'injection de paquets ou bien leur récupération. La file d'attente « jetons » est simplement une mémoire tampon [[First in, first out|FIFO]].

Les jetons sont formés de :
* {{nombre|37|[[Bit (informatique)|bits]]}} de données, associées à
* un marqueur de {{nombre|36|[[Bit (informatique)|bits]]}} suivi de
* une adresse de destination sur {{nombre|22|[[Bit (informatique)|bits]]}}, puis
* un second marqueur de {{unité|1|[[Bit (informatique)|bit]]}}.

Étant donné que de larges itérations ou de vastes ensembles de données peuvent provoquer un dépassement de capacité (en nombre de jetons), une unité particulière est couplée à l'unité de correspondance pour pallier ce cas. L'unité de calcul va bien sûr contenir plusieurs [[Unité arithmétique et logique|unités arithmétiques et logiques]] pour permettre d'exécuter les instructions en parallèle.

== Langages ==
* '''Id''' a été mis au point à Irvine (Université de [[Californie]]), puis au [[Massachusetts Institute of Technology|MIT]]
* '''Val''' au MIT.
* '''SISAL''' (''{{Langue|en|texte=Streams and Iteration in a Single Assignment Language}}'') à l'université de [[Manchester]].

== Historique ==
Les premières idées et concepts qui ont donné naissance à ces architectures sont nés dans les années [[1960]].

Les premiers [[ordinateur]]s de ce type sont nés au début des {{lnobr|années 1970}}, d'abord aux [[États-Unis]] et au [[Japon]], mais aussi en [[France]] avec le LAU (Langage à Assignation Unique, CERT-ONERA de [[Toulouse]]). Les constructeurs qui se sont impliqués sont : [[Texas Instruments]], [[NEC]], [[OKI]] etc. Certaines machines ont été construites sur la base de microprocesseurs tel que le [[Zilog]] [[Z8001]] et [[Motorola]] [[88110]] ou bien encore des [[Processeur en tranche|microprocesseurs en tranches]] [[Advanced Micro Devices|AMD]].

== Quelques machines ==

=== Machines à architecture statique ===
* MIT {{lang|en|Static Dataflow Architecture}}, un prototype avec {{nombre|8|processeurs}}.
* HDFM, {{lang|en|Hughes Dataflow Multiprocessor}}, avec {{nombre|512|processeurs}}.
* LAU, {{lang|en|TI's Distributed Data Processor}}, DDM1, etc.

=== Machines a jetons marqués (architecture dynamique) ===
* MIT {{lang|en|Tagged-Token Dataflow Machine}}, {{nombre|4|processeurs}} par ''{{lang|en|cluster}}'', les clusters sont interconnectés sur un réseau en boucle.
* {{nobr|SIGMA-1}}, [[superordinateur]] [[Japon]]ais, {{nombre|128|processeurs}}, 1988.
* [[LDF 100|LFD 100]], entre 5 et 128 processeurs, 1986.
* PATTSY, {{lang|en|Processor Array Tagged-Token System}}, système expérimental australien. {{nombre|18|processeurs}} {{nobr|Intel 8085}} reliés à un {{nobr|IBM-PC}}.
* DDDP, {{lang|en|Distributed Data Driven Processor}}, conception Japonaise, {{nombre|16|processeurs}}.
* {{nobr|Q-p}}, SDFA, CSIRAC II, {{nobr|PIM-D}} etc.

Il est tout à fait possible que le ''{{lang|en|dataflow}}'' soit utilisé sous une forme « moderne » pour équiper un [[superordinateur]].

== Références ==
=== Liens internes ===
* [[Programmation fonctionnelle]]

=== Liens externes ===
* {{pdf}} [http://www.cs.wisc.edu/~isca2005/ttda.pdf Executing a Program on the MIT Tagged-Token Dataflow Architecture].
* [http://www.jpaulmorrison.com/fbp/index.shtml Flow-based Programming] : un livre sur la programmation orientée flot de données.
{{Portail|informatique}}

[[Catégorie:Architecture informatique]]
[[Catégorie:Programmation fonctionnelle]]