« Fonctionnement d'un ordinateur/Les architectures dataflow » : différence entre les versions

Dans les années 1970 à 1980, les chercheurs tentaient de créer des architectures parallèles, pouvant se passer de program counter. Les architectures dataflow furent une de ces réponses. Sur ces architectures, une instruction s’exécute dès que ses opérandes sont disponibles, comme sur les architectures à exécution dans le désordre. Sauf que cette fois-ci, c'est directement le jeu d'instruction qui permet ce genre de prouesses. Supprimer les dépendances de données est alors le rôle du compilateur. Pour supprimer ces dépendances, les compilateurs ajoutent une contrainte simple : impossible de modifier la valeur d'une donnée/variable tant que celle-ci peut encore être utilisée. Or, les langages fonctionnels permettent d'initialiser une variable lors de sa création, mais pas de la modifier ! Il va de soi qu'un programme sur une architecture dataflow doit préciser les dépendances de données entre instructions, vu que le program counter a disparu. Pour cela, chaque instruction indique l'adresse mémoire de toute instruction qui a besoin de son résultat. Vu que chaque instruction ne s'exécute que si ses opérandes sont disponibles — ont été calculés — détecter la disponibilité des opérandes des instructions est alors primordial.

 

 

Il va de soit qu'avec ce qu'on a dit plus haut, un programme conçu pour une architecture dataflow n'est pas une simple suite d'instruction. Un programme de ce type sera quelque chose de plus compliqué : il devra contenir les instructions du programme, et préciser les dépendances de données entre instructions (vu que notre processeur se basera sur ces dépendances de données entre instructions pour choisir quelles sont les instructions à exécuter). Sur ces processeurs, un programme sera ce qu'on appelle un '''graphe orienté acyclique''', un objet mathématique assez particulier qu'on va décrire assez rapidement. Pour faire simple, un graphe est un ensemble de points qu'on relie par des flèches (les matheux qui lisent ce cours vont surement vouloir me tuer...). Avec un graphe orienté, les flèches ont un sens. Le terme acyclique vient d fait qu'il n'y a pas de boucles dans le graphe.

 

 

Sur les processeurs dataflow, les points du graphe sont les instructions du programme. Niveau instructions, on retrouvera nos fameux add, mul, et autres instructions arithmétiques et logiques. Ces instructions sont particulièrement simples : elles consomment leurs entrées, et fournissent un résultat sans rien faire d'autre : elles sont sans aucun effet de bord. Mine de rien, cela n'est pas le cas dans les processeurs Von Neumann : certaines instructions arithmétiques vont faire plus que fournir un résultat. Elles peuvent écraser une donnée, modifier des bits de contrôle du registre d'état, lever des exceptions matérielles, etc. Rien de tout cela n'est permis sur les architectures dataflow, afin de limiter les effets de bords, honnis dans le paradigme fonctionnel. Cela permet de plus de garder un maximum d'opportunités de parallélisation.

On peut aussi utiliser des fonctions, avec ce genre de programme. Une fonction n'est rien d'autre qu'un ensemble d'instructions avec ses dépendances de données, comme tout programme digne de ce nom. Sur ces architectures, une fonction est donc un graphe qu'on peut incorporer dans le graphe du programme principal ou dans celui d'une autre fonction. Petit détail : une fonction devra attendre que tous ses arguments soient disponibles avant de pouvoir s’exécuter.

 

 

Il n'est pas rare qu'une instruction doive attendre un certain évènement avant que ses opérandes soient disponibles. Par exemple, ce peut être le cas si une instruction attend que des opérandes soient tapées au clavier ou proviennent d'une carte réseau. Dans ce cas, certaines flèches partiront de données, qui seront fournies par des périphériques ou qui seront présentes en mémoire au lancement du programme. Reste que lorsque notre programme s’exécute, il faut que notre processeur puisse savoir s'il peut sauter d'un point à un autre, ce qui correspond à déclencher l’exécution d'une nouvelle instruction. Pour cela, il a besoin de savoir quelles sont les données disponibles (ainsi que les instructions auxquelles elles sont destinées). Pour cela, il va attribuer aux données disponibles ce qu'on appelle un '''jeton'''. Ce jeton permet de se repérer dans le graphe vu au-dessus en mémorisant, pour une donnée, l'adresse mémoire de la prochaine instruction à exécuter. Qui plus est, ce jeton contient aussi la donnée qui se voit attribuer le jeton et peut aussi éventuellement contenir certains renseignements supplémentaires. Il est stocké en mémoire, et va y attendre bien sagement qu'une instruction veulent bien l'utiliser. Le schéma qui suit montre la propagation des jetons suite à l’exécution d'une instruction sur un graphe dataflow.

 

 

Chaque donnée de départ, fournie par un périphérique ou enregistrée en mémoire au lancement d'un programme, se voit attribuer un jeton, qui signifie tout simplement que la donnée est disponible et prête à se faire "instructionner". Lorsque toutes les opérandes d'une instruction ont leur jeton actif, l'instruction va alors supprimer les jetons de ses données et va fournir un résultat, auquel on attribuera un nouveau jeton. En clair, les opérandes auront étés utilisées et ne sont plus disponibles, tandis que le résultat l'est. Un nouveau jeton sera alors crée pour le résultat, et rebelote. L’exécution de notre programme consistera à une propagation de jetons à travers ce graphe, qui se fera suivant les disponibilités et le parcourt des jetons. Ce jeton est un concept assez théorique, mais on verra comment celui-ci est géré dans notre ordinateur dataflow dans les chapitres qui suivent. Quoiqu'il en soit, pour éxecuter une instruction, il faudra détecter la disponibilité des jetons qu'elle manipule (et qui contiennent ses opérandes). Et c'est le processeur qui se chargera de vérifier la disponibilité des opérandes d'une instruction. Plus précisément, ce sera le rôle d'un circuit spécialisé, comme on le verra plus tard.

 

 

La détection de la disponibilité des opérandes est primordiale sur les architectures dataflow. Suivant l'ordinateur utilisé, cette gestion du jeton peut être plus ou moins évoluée et peut permettre ou interdire certaines manipulations potentiellement intéressantes. Dans ce qui va suivre, on va voir qu'il existe différentes façons de gérer ce jeton. Le principal problème avec les jetons, c'est que ceux-ci doivent parfois attendre que leur instruction ait réunie toutes ses opérandes pour être utilisés. Dans pas mal de cas, cela ne pose pas de problèmes : les jetons n'ont pas trop de temps à attendre et un nouveau jeton n'a pas le temps d'arriver entre temps. Mais ce n'est pas toujours le cas, et parfois, on peut se retrouver avec un nouveau jeton qui arrive avant que le précédent soit consommé. Dans ce cas, on est face à un problème : comment faire pour différencier l'ancienne donnée, qui doit être utilisée dans le calcul à faire, de la donnée du jeton nouveau venu ? La première solution est celle utilisée sur les '''architectures dataflow statiques'''. Sur ces architectures, on doit se débrouiller pour n'avoir qu'un seul jeton de disponible pour chaque opérande. Dit autrement, chaque flèche du graphe ne doit contenir qu'un seul jeton à la fois lors de l’exécution du programme. En clair, une instruction ne peut pas avoir plusieurs valeurs différentes d'une même opérande en attente, chose qui serait possible avec l'usage de boucles, par exemple.

 

 

Une instruction contient alors, outre son opcode, un espace pour stocker les opérandes (les jetons) et quelques bits de présence qui indiquent si l'opérande associée est disponible. Les jetons sont donc stockés dans l'instruction, et sont mis à jour par réécriture directe de l'instruction en mémoire. De plus, il ne faut pas oublier de représenter la flèche, les dépendances de données qu'elle peut avoir. Pour cela, chaque instruction contient l'adresse de l'instruction suivante, celle à laquelle envoyer le résultat. Tout cela ressemble aux entrées des stations de réservation sur les processeurs à exécution dans le désordre, à un détail près : tout est stocké en mémoire, dans la suite de bits qui code l'instruction. Vu qu'une instruction contient ses propres opérandes, on préfère parfois utiliser un autre terme que celui d'instruction et on parle d''''activity template'''.

En effet, il faut trouver un moyen de toujours respecter cette contrainte. Il faut empêcher une instruction de s’exécuter et de fournir un résultat si une autre donnée est en train d'attendre sur la même flèche. Pour empêcher cela, chaque instruction contient un bit, un jeton d'autorisation qui indique si elle peut calculer un nouveau résultat. Quand une instruction s’exécute, elle prévient l'instruction qui a calculé l'opérande qu'elle est prête à accepter un nouvel opérande : le jeton de celle-ci est mis à jour. Pur que cela fonctionne, chaque instruction doit savoir quelle est la ou les instructions qui la précédent dans l'ordre des dépendances. Pour cela, une seule solution : stocker toutes leurs adresses dans l'instruction.

 

 

 

Dans les grandes lignes, une architecture dataflow statique est composée de plusieurs éléments, représentés sur le schéma que vous pouvez voir en-dessous. La file d'instructions est une mémoire qui met en attente les instructions dont toutes les données sont prêtes : elle contient leurs adresses, qu'elle peut fournir à l'unité de chargement. L'unité de mise à jour enregistre les résultats des instructions en mémoire et met à jour les bits de présence. Elle va aussi vérifier que l'instruction de destination du résultat a tous ses opérandes disponibles, et charge celle-ci dans la file d'instructions si c'est le cas.

 

 

 

Ces architectures ont toutefois de gros défauts : certaines fonctionnalités importantes de nos langages de programmation fonctionnels ne sont pas implémentables sur ces architectures. Exemples : pas de fonctions de première classe, pas de fonctions réentrantes, ni de récursivité. Autant vous dire que ces architectures ne servent pas à grand chose. Pire : les boucles dont les itérations sont indépendantes ne peuvent pas être déroulées (ni pipelinées) : on exécute itérations après itérations au lieu d’exécuter toutes les boucles en parallèle. En effet, lorsqu'on exécute une fonction réentrante ou plusieurs itérations d'une boucle, plusieurs versions des mêmes instructions peuvent s’exécuter en même temps : une version de la fonction par appel récursif ou par itération. Et chaque version va vouloir écrire dans les champs opérandes et mettre à jour les bits de présence. Heureusement, les jetons d'autorisation vont éviter tout problème, en ne laissant qu'une seule version (la plus ancienne) s'exécuter, en faisant attendre les autres.

 

 

 

Vu que la règle du "un jeton par flèche " est à l'origine du mal, la seule solution est de faire sauter cette règle inepte servant juste à rendre inutiles nos magnifiques architectures dataflow. La solution de ces problème est venue des '''architectures dataflow dynamiques'''. Avec elles, les fonctions récursives et réentrantes sont supportées, et les boucles sont automatiquement déroulées par le processeur à l’exécution. Pour cela, on ajoute à chaque opérande des informations qui permettent de préciser à quel exemplaire d'une fonction ou d'une boucle ils sont destinés. Ces informations sont stockées dans l'opérande, et sont regroupées dans ce qu'on appelle le tag. Dorénavant, une instruction s’exécute une fois que tous ses opérandes ayant le même tag sont disponibles. Cela a une grosse conséquence : on ne peut coder les instructions comme sur les architectures statiques.

La gestion des jetons change du tout au tout. Sur les architectures statiques, les jetons n'étaient pas vraiment présents dans la mémoire : on avait pré-reservé leur emplacement directement dans les instructions. Mais maintenant, ce n'est plus le cas. Par facilité, c'est maintenant aux jetons d'indiquer quelle est l'instruction qui doit les manipuler. Ceux-ci contiennent donc la donnée à manipuler, leur Tag, et l'adresse de l'instruction de destination, ainsi que le nombre d'opérandes de cette instruction (afin de faciliter la détection de la disponibilité des opérandes de celle-ci). Dès qu'un jeton a été calculé par l'ALU, il est stocké dans une file d'attente, dédiée aux jetons disponibles. Reste à vérifier la disponibilité des opérandes. Si l'instruction a toutes ses opérandes disponibles dans cette file d'attente, il y a juste à les récupérer et à lancer l'instruction. Ainsi, à chaque ajout d'un jeton dans la file d'attente des jetons, on va vérifier quelles sont les jetons présents dans cette file qui possèdent le même Tag, afin de charger celle-ci le cas échéant.

 

 

Il va de soit que vu les contraintes de fonctionnement de la file d’attente, celle-ci est une mémoire adressable par contenu. Le seul problème (car il y en a un) est que les performances d'une architecture dynamique dépendent fortement de la vitesse de cette mémoire adressable par contenu : si celle-ci est un peu lente, votre merveilleuse architecture dataflow à 200 unités de calcul sera aussi lente qu'un 486 DX mal réveillé.

 

 

Les '''architectures Explicit Token-Store''', qui utilisent une sorte de pile : l'opérande est remplacé par un pointeur vers le cadre de pile qui contient la donnée et de quoi localiser l'opérande dans la pile. Elle représentent une amélioration assez conséquente des architectures précédentes. Sur ces machines, lorsqu’une fonction ou une boucle s’exécute, elle réserve un cadre de pile et y stocke ses opérandes et ses variables locales. A chaque appel d'une fonction ou à chaque itération d'une boucle, on crée un nouveau cadre pour les opérandes de la dite version : ainsi, chaque fonction ou itération de boucle pourra avoir son propre jeu d'opérandes et de variables locales, permettant ainsi l'utilisation de fonctions réentrantes ou récursives et un déroulage matériel des boucles. Ces Frames sont localisées par leur adresse mémoire et les instruction ont juste à repérer la position dans la Frame. La différence entre la pile des architectures usuelles et ces Frames tient dans le fait que les Frames ne sont pas placées de façon consécutive dans la mémoire, mais peuvent être dispersées n'importe où et n'importe comment (ou presque) en mémoire. Qui plus est, ces Frames ne sont pas organisés dans une pile, avec une politique d'ajout et de retraits de type LIFO. Chaque donnée présente dans la Frame possède des bits de présence, comme toutes les autres données utilisées sur ces architectures. Dans ces architectures, la mémoire est encore séparée en deux : une mémoire pour les instructions et les slots qui vont avec, et une autre pour les Frames. L’organisation est similaire aux architectures dynamiques, à un détail prêt : nos Frames sont stockées dans une mémoire tout ce qu'il y a de plus normale, avec des adresses et tout le reste.

 

 

Nos architectures dataflow sont certes très belles, élégantes, tout ce qu'on veut (et encore, ça se discute...), mais celles-ci ont, comme toute architecture, été créées pour répondre à un besoin : la performance ! C'est le seul critère sur lequel on peut juger une architecture : est-elle rapide ? Le bilan est sans appel : ces architectures souffrent de défauts qui empêchent de les utiliser de façon réellement efficace.

On peut toujours amortir ces différents couts en exécutant beaucoup d'instructions en parallèle, mais cela ne suffit pas forcément. Il faut dire que rares sont les programmes avec peu de dépendances et pour lesquels on peut trouver un grand nombre d'instructions à exécuter en parallèle. En tout cas, pas forcément suffisamment pour compenser les couts de recherche des opérandes et les autres couts annexes. Il faut dire que beaucoup d'instructions possèdent des dépendances dans un programme (même programmé avec des langages fonctionnels), et qu'il n'y a pas de miracles : on ne peut pas toujours trouver suffisamment d'instructions à paralléliser, sauf dans certains programmes, qui résolvent des problèmes particuliers. En conséquence, les architectures dataflow ont étés abandonnées, après pas mal de recherches, en raison de leurs faibles performances. Mais certains chercheurs ont quand même décidés de donner une dernière chance au paradigme dataflow, en le modifiant de façon à le rendre un peu plus impératif.

 

 

Ainsi sont nées les '''architectures Threaded Dataflow''' ! Sur ces architectures, un programme est découpé en plusieurs blocs d'instructions. À l'intérieur de ces blocs, les instructions s’exécutent les unes à la suite des autres. Par contre, les blocs eux-mêmes seront exécutés dans l'ordre des dépendances de données : un bloc commence son exécution quand tous les opérandes nécessaires à son exécution sont disponibles.

 

 

Les architectures '''Explicit Data Graph Execution''' se basent sur le fonctionnement des compilateurs modernes pour découper un programme procédural ou impératif en blocs de code. Généralement, ceux-ci vont découper un programme en petits morceaux de code qu'on appelle des blocs de base, qui sont souvent délimités par des branchements (ou des destinations de branchements). Ces sont ces blocs de base qui seront exécutés dans l'ordre des dépendances de données. Certaines architectures de ce type ont déjà été inventées, comme les processeurs WaveScalar et TRIPS.