Fonctionnement d'un ordinateur/Les architectures dataflow

Un livre de Wikilivres.
Aller à la navigation Aller à la recherche

Dans les années 1970 à 1980, les chercheurs tentaient de créer des architectures parallèles sans program counter, ce qui les amena à créer les architectures dataflow. 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 c'est le jeu d'instruction et le compilateur qui s'occupent de la gestion des dépendances. Un programme sur une architecture dataflow précise les dépendances de données entre instructions. Vu que chaque instruction ne s'exécute que si ses opérandes sont disponibles, détecter la disponibilité des opérandes des instructions est alors primordial, et c'est cette contrainte qui a façonné les architectures dataflow.

Le modèle de calcul dataflow théorique[modifier | modifier le wikicode]

Exemple de graphe dataflow.

Un programme conçu pour une architecture dataflow n'est pas une simple suite d'instruction, mais encode les dépendances entre instructions. Pour cela, chaque instruction indique l'adresse mémoire de toute instruction qui a besoin de son résultat. Pour limiter les dépendances de données au strict minimum, les compilateurs ajoutent une contrainte simple : impossible de modifier la valeur d'une donnée/variable après son initialisation. Avec ces deux contraintes, un programme d'architecture dataflow est 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. Avec un graphe orienté, les flèches ont un sens. Le terme acyclique signifie qu'il n'y a pas de boucles dans le graphe. Sur les processeurs dataflow, les points du graphe sont les instructions du programme, alors que les flèches entre instructions représentent chacune une dépendance de donnée de type RAW. Deux instructions seront reliées par une flèche si elles ont une dépendance de donnée, et la flèche va de l'instruction qui calcule l'opérande vers celle qui l'utilise. Rien n’empêche à une instruction de manipuler le résultat de plusieurs instructions différentes, mais il n'y a pas de boucles, du fait de l'acyclicité du graphe. Le stockage de ce graphe dépend de l'ordinateur utilisé, mais vous pouvez être certains qu'il est stocké quelque part (même si parfois de manière implicite) dans la mémoire de l'ordinateur et que le processeur l'utilise pour savoir quelles instructions exécuter et dans quel ordre.

Représentation d'une instruction dataflow.
Extrait de code dataflow (graphe simple) avec plusieurs instructions arithmétiques.

Les instructions d'un programme dataflow[modifier | modifier le wikicode]

Les instructions arithmétiques et logiques 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 sur les autres architectures, où ces instructions peuvent écraser une donnée, modifier des bits de contrôle du registre d'état, lever des exceptions matérielles, etc. Et cela réduit les possibilités de parallélisation, en ajoutant des dépendances avec le registre d'état ou d'autres structures matérielles. Rien de tout cela n'est permis sur les architectures dataflow, afin de garder un maximum d'opportunités de parallélisation.

Outre les instructions normales, on trouve des instructions équivalentes aux instructions de tests et de branchements, appelées switch et merge. Pour faire simple, les merges sont des instructions qui effectuent des comparaisons ou des tests et qui fournissent un résultat du style : la propriété testée est vraie (ou fausse). Les switch quant à eux, sont l'équivalent des instructions de branchements, vues plus haut.

Switch.
Merge.

Ces instructions permettent de créer des structures de contrôle usuelles.

Code dataflow avec un IF/ELSE.
Code dataflow avec une boucle WHILE.

La gestion de la disponibilité des opérandes[modifier | modifier le wikicode]

Pour exécuter un programme dataflow, le processeur a besoin de savoir quelles sont les données disponibles (ainsi que les instructions auxquelles elles sont destinées). Au niveau abstrait, la disponibilité des opérandes peut se voire sur le graphe acyclique qui représente le programme. À tout instant, les opérandes sont localisées sur les flèches du graphe. Associer une opérande/donnée avec une flèche est réalisé en attribuant d'un jeton à chaque opérande. Le jeton associé à une donnée mémorise l'adresse mémoire de la prochaine instruction à exécuter, c'est à dire l'adresse du prochain nœud du graphe. Qui plus est, le jeton peut aussi éventuellement contenir certains renseignements supplémentaires. Il est stocké en mémoire et va y attendre bien sagement qu'une instruction veuille bien l'utiliser.

Le schéma qui suit montre ce qu'il advient des jetons suite à l’exécution d'une instruction sur un graphe dataflow. Lorsque tous les opérandes d'une instruction sont disponibles, l'instruction consomme les opérandes et fournit un résultat. Les jetons des opérandes sont donc détruits, vu que les opérandes ont été consommées, alors que le résultat se voit attribuer un jeton. L’exécution du programme consiste à propager les jetons à travers le graphe, ce qui se fera suivant les disponibilités des jetons. Pour résumer, exécuter une instruction demande de détecter la disponibilité des opérandes via leurs jetons, ainsi que de créer et détruire les jetons adéquats. Vérifier la disponibilité des opérandes d'une instruction est le rôle d'un circuit spécialisé, comme on le verra plus tard.

Illustration de la propagation des jetons suite à l’exécution d'une instruction sur un graphe dataflow.

La détection de la disponibilité des opérandes est primordiale sur les architectures dataflow. Dans ce qui va suivre, on va voir qu'il existe différentes façons de gérer ce jeton, qui peuvent être plus ou moins évoluées suivant l'ordinateur dataflow utilisé. Le principal problème avec les jetons, c'est qu'ils doivent parfois attendre que leur instruction ait réuni toutes ses opérandes pour être utilisés. Dans pas mal de cas, les jetons n'attendent pas longtemps et un nouveau jeton n'a pas le temps d'arriver entre-temps. Mais il se peut qu'un nouveau jeton arrive avant que le précédent soit consommé. On est alors 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 réponse à cette question distingue les architectures dataflow statiques et dynamiques.

Les architectures dataflow statiques[modifier | modifier le wikicode]

La première solution est celle utilisée sur les architectures dataflow statiques. Sur ces architectures, on n'a qu'un seul jeton de disponible pour chaque flèche du graphe dataflow, par construction. 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. Dit autrement, chaque flèche du graphe ne doit contenir qu'un seul jeton à la fois lors de l’exécution du programme. En raison de cette contrainte, certaines fonctionnalités importantes des 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é. De plus, les boucles sont systématiquement exécutées en série, itérations après itérations, au lieu d’exécuter des itérations en parallèle quand c'est possible. En effet, une instruction dans une boucle va produire une nouvelle opérande par itération, qui se retrouveront toutes sur la même flèche du graphe dataflow, car produite par la même instruction. Mais la contrainte du un jeton par flèche ne permet qu’une seule opérande, donc une seule itération de la boucle.

Le codage des instructions[modifier | modifier le wikicode]

Une instruction contient, outre son opcode, un espace pour stocker les opérandes (les jetons) et des bits de présence qui indiquent si l'opérande associé 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, 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.

Illustration du codage de haut niveau d'une instruction sur une architecture dataflow statique. On voit bien que chaque instruction a un espace réservé pour chaque opérande.
Même chose, mais avec des instructions Switch et Merge.

Avec cette technique, il faut empêcher une instruction 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 qui indique si elle peut calculer un nouveau résultat. Ce bit est appelé le jeton d'autorisation. Quand une instruction s’exécute, elle prévient les instructions qui ont calculé ses opérandes qu'elle est prête à accepter un nouvel opérande. Les jetons de celles-ci sont mis à jour. Pour que cela fonctionne, chaque instruction doit savoir quelle est la ou les instructions qui la précédent dans l'ordre des dépendances, ce qui implique de mémoriser leurs adresses.

Représentation d'une instruction en mémoire sur une architecture dataflow.

La microarchitecture d'une architecture dataflow statique[modifier | modifier le wikicode]

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 vérifie aussi 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.

Diagramme d'une architecture dataflow statique.

Les architectures dataflow dynamiques[modifier | modifier le wikicode]

Les architectures dataflow dynamiques acceptent plusieurs jetons sur une flèche du graphe dataflow. Mais il faut éviter de confondre les opérandes, il faut garantir que les opérandes soient utilisés dans l'ordre, dans leur ordre d'arrivée. Pour cela, ces architectures associent un tag à chaque jeton, qui indique leur ordre d’exécution leur ordre d'arrivée sur la flèche du graphe dataflow. Dorénavant, une instruction s’exécute une fois que tous ses opérandes ayant le même tag sont disponibles.

Sur les architectures statiques, les jetons avaient un emplacement pré-réservé dans les instructions mêmes. Mais sur les architectures dynamiques, on ne peut réserver de la place pour les opérandes à l'avance. C'est maintenant aux jetons d'indiquer l'adresse de l'instruction qui doit les manipuler. Les opérandes sont mémorisés à part des instructions, dans des mémoires séparées (en clair, les architectures dynamiques sont de type Harvard). Les opérandes sont mis en attente dans une file d'attente. À chaque ajout d'un opérande dans la file d'attente, le processeur vérifie quels sont les opérandes de la file qui possèdent le même tag et la même adresse d'instruction.

Synoptique simplifié de la machine de l'Université de Manchester (1981)

La gestion des jetons change du tout au tout. Les jetons contiennent l'opérande, 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 la file d'attente des 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 quels sont les jetons présents dans cette file qui possèdent le même Tag, afin de charger celle-ci le cas échéant.

Architecture dataflow dynamique.

Il va de soi que vu les contraintes de fonctionnement de la file d’attente, celle-ci est une mémoire adressable par contenu, et précisément une mémoire associative. 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.

Les architectures Explicit Token Store[modifier | modifier le wikicode]

Les architectures Explicit Token-Store utilisent une sorte de pile. L'opérande est remplacé par deux choses : un pointeur vers le cadre de pile qui contient la donnée et de quoi localiser l'opérande dans la pile. Elle représente 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. À 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 cadres de pile sont localisés par leur adresse mémoire et les instructions ont juste à repérer la position dans le cadre de pile. La différence avec la pile des architectures usuelles tient dans le fait que les cadres de pile ne sont pas contiguës, mais peuvent être dispersées n'importe où et n'importe comment (ou presque) en mémoire. Qui plus est, les cadres de pile ne sont pas organisés avec une politique d'ajout et de retraits de type LIFO. Chaque donnée présente dans un cadre de pile possède des bits de présence, comme toutes les autres données.

Dans ces architectures, la mémoire est encore séparée en deux : une mémoire pour les instructions et une autre pour les cadres de pile. L’organisation est similaire aux architectures dynamiques, à un détail prêt : les cadres de pile sont stockées dans une mémoire tout ce qu'il y a de plus normale, avec des adresses et tout le reste.

Les architectures dataflow hybrides[modifier | modifier le wikicode]

Les architectures dataflow sont certes très belles et créatives, mais celles-ci souffrent de défauts qui empêchent de les utiliser de façon réellement efficace.

Premièrement, la gestion des jetons et des instructions est compliquée et utilise beaucoup de circuits. La détection de la disponibilité des opérandes d'une instruction est assez coûteuse et prend un certain temps, vu qu'elle est faite avec des mémoires associatives. Or, les mémoires associatives sont redoutablement lentes, ce qui pose de gros problèmes de performances. Le temps d'accès à la mémoire est suffisant pour compenser tous les gains apportés par la parallélisation. Autre problème : la répartition des instructions prêtes sur les différentes unités de calcul prend un certain temps, difficile à amortir. Autre problème : les tags prennent de la mémoire, suffisamment pour devenir un problème. Ensuite, l'immutabilité des variables fait que la gestion des structures de données est laborieuse pour le compilateur et le programmeur, entraîne beaucoup d'allocations mémoires et augmente fortement le nombre de lectures et écritures en mémoire, comparé à un programme impératif.

Et ensuite, le plus gros problème de tous : ces architectures sont limitées par la rapidité de la mémoire RAM principale. La même chose a lieu dans les programmes impératifs sur des architectures normales, à la différence que celles-ci ont des caches et une hiérarchie mémoire, afin d'amortir le coût des accès mémoires. Mais ces techniques ne fonctionnent correctement que lorsque le code exécuté a une bonne localité temporelle et spatiale. Ce qui n'est franchement pas le cas des programmes conçus pour les architectures dataflow et des programmes fonctionnels en général (à cause de l'immutabilité de variables, d'allocations mémoires fréquentes, des structures de donnée utilisées, etc).

On peut toujours compenser ces défauts en exécutant beaucoup d'instructions en parallèle, mais rares sont les programmes capables d’exécuter un grand nombre d'instructions à exécuter en parallèle. Il faut dire que les dépendances de données sont légion 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é abandonnées, après pas mal de recherches, en raison de leurs faibles performances. Mais certains chercheurs ont quand même décidé de donner une dernière chance au paradigme dataflow, en le modifiant de façon à le rendre un peu plus impératif.

Les architectures Threaded Dataflow[modifier | modifier le wikicode]

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 architecture Explicit Data Graph Execution[modifier | modifier le wikicode]

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). Ce 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.

Conclusion[modifier | modifier le wikicode]

Pour finir, sachez qu'il existe peu de documentation sur le sujet. Il s'agit d'un sujet de recherche assez ancien, et qui est un peu délaissé des dernières années. Quoi qu’il en soit, je recommande la lecture des liens qui suivent, pour se renseigner un peu plus sur le sujet :

Quelques liens sur l'architecture wavescalar :