Fonctionnement d'un ordinateur/Les architectures dataflow

Si vous programmez depuis un certain temps, vous savez sûrement qu'il existe plusieurs paradigmes de programmation : le paradigme procédural, l'impératif, l'objet, le fonctionnel, etc. Au départ, les premiers ordinateurs étaient optimisés pour exécuter des langages de programmation impératifs très simples. Puis l'assembleur de ces processeurs a évolué pour supporter les fonctionnalités des langages procéduraux et impératifs : le nombre de types supportés par le processeur s'est étoffé, des instructions spéciales pour supporter les sous-programmes ont été inventées, et de nombreux modes d'adressage dédiés aux tableaux et structures ont fait leur apparition. Quand la programmation orientée objet s'est démocratisée dans les années 1980, des processeurs prenant en charge la programmation orientée objet ont été inventés (l'Intel iAPX 432, par exemple).

De même, il existe de nombreuses architectures spécialement adaptées à l’exécution de langages fonctionnels ou logiques. Les premières tentatives se contentaient d’accélérer l’exécution des langages fonctionnels avec des méthodes impératives, tels des architectures à tags pour gérer le typage dynamique en matériel, des ramasse-miettes matériels, etc. Dans le genre, on peut citer les machines Lisp. Ce n'est que par la suite que sont apparues de véritables architectures dont le langage machine était un langage fonctionnel. Il s'agissait des architectures dites à réduction de graphe, les premières étaient la machine GRIP (un système multiprocesseurs avec un microcode spécialisé) et la SKIM machine. Plus récente, on pourrait citer le Reduceron, une architecture monoprocesseur qui exécute du code machine fonctionnel sans microcode.

Dans ce chapitre, nous allons nous intéresser à un sous-type d'architectures à réduction de graphe : les architectures dataflow. Leur spécificité est qu'elles sont capables d’exécuter plusieurs instructions en parallèle, d'une manière qui se voit directement dans le code machine. Les dépendances entre instructions sont encodées directement dans le code machine. Le processeur peut ainsi déterminer quelle instruction est prête à s’exécuter en fonction de la disponibilité des opérandes. En clair, l’exécution dans le désordre est réalisée par le compilateur, au niveau du jeu d'instruction.

Le modèle de calcul dataflow théorique

Exemple de graphe dataflow.

Sur une architecture dataflow, un programme et/ou toute expression est représentée par un graphe. Pour faire simple, un graphe est un ensemble de points qu'on relie par des flèches, les points sont appelés des nœuds. Les expressions d'un programmes sont représentées par un graphe dont les nœuds sont des constantes, variables, opérateurs ou fonctions. Les flèches encodent les dépendances entre les nœuds : à quelle opération envoyer telle opérande, à quel instruction envoyer le résultat d'une autre instruction, etc. Pour résumer, les nœuds correspondent aux instructions pas encore exécutées ou à leur résultat, alors que les flèches encodent les dépendances entre instructions.

Les architectures à réduction de graphe sont conçues pour exécuter automatiquement un programme sous cette forme, en parcourant le graphe et en effectuant les calculs imposés par les nœuds. Les architectures dataflow sont un exemple d'architecture à réduction de graphe à évaluation non-stricte, ce qui veut dire qu'une instruction s’exécute dès que ses opérandes sont disponibles, comme sur les architectures à exécution dans le désordre. De plus, pour limiter les dépendances de données au strict minimum, on ajoute une contrainte simple : impossible de modifier la valeur d'une donnée/variable après son initialisation. Avec cette contrainte, on garantit que les flèches vont de l'instruction qui calcule l'opérande vers celle qui l'utilise. Pour le dire autrement, elle indique que le résultat d'une instruction est utilisé par une autre, ce sont donc des dépendances de type RAW (Read After Write). 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.

Pour le dire rapidement, les architectures dataflow fonctionnent un peu comme les architectures à exécution dans le désordre, sauf qu'elles n'ont pas besoin de détecter les dépendances entre instructions, qui lui sont données sur un plateau. Un programme conçu pour ce genre d'architecture n'est pas une simple suite d'instruction, mais encode les dépendances entre instructions. On comprend donc qu'il n'y a pas de program counter, car pas d’exécution séquentielle d'une instruction. Niveau implémentation, les nœuds et flèches sont implémentés différemment. Chaque nœud d'un graphe est stocké sous la forme d'une structure, dont le format dépend de l'ordinateur. Pour encoder les fléches, chaque instruction indique l'adresse mémoire de toute instruction qui a besoin de son résultat.

Les instructions d'un programme dataflow

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

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

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. En raison de cette contrainte, certaines fonctionnalités importantes des langages de programmation fonctionnels ne sont pas implémentables sur ces architectures. Les fonctionnalités en question permettent d’exécuter plusieurs instances d'une même instruction : boucles qui répètent une instruction, fonctions de première classe, fonctions réentrantes, récursivité, etc. Avoir plusieurs instances d'une même instruction demanderait d'avoir plusieurs jetons par flèche : une par instance. Mais c'est chose impossible sur ces architectures. Une des conséquences est que 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.

Le codage des instructions

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

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. L'unité de chargement analyse en permanence la file d'instructions actives et détecte celles qui ont toutes leurs opérandes. Une fois qu'elle a détecté une ou plusieurs instructions prêtes, elle les charge, les distribue aux unités de calcul, et démarre leur exécution. Il s'agit autant d'une unité de chargement que d'une unité de distribution. Pour faciliter cette analyse, la file d'instruction est une mémoire associative, spécialement conçue pour faciliter la détection des instructions prêtes.

Diagramme d'une architecture dataflow statique.

Les architectures dataflow dynamiques

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

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

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

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

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.