Fonctionnement d'un ordinateur/Les architectures dataflow
Dans ce chapitre, nous allons nous intéresser aux architectures dataflow. Leur spécificité est que 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 jeu d'instruction dataflow théorique, un modèle de calcul
[modifier | modifier le wikicode]
Sur une architecture dataflow, un programme est représenté par un graphe, à savoir un ensemble de points qu'on relie par des flèches. Les points sont appelés des nœuds, et ils représentent ici une instruction chacun. Les flèches encodent les dépendances entre instructions : à quelle opération envoyer tel résultat, quelle instruction fournit telle opérande, etc. Pour résumer, les nœuds correspondent aux instructions, alors que les flèches encodent les dépendances RAW entre instructions.
Avant de poursuivre, petit instant terminologie. Une instruction prend en entrée des opérandes et fournit un résultat. On dit aussi qu'elle consomme des opérandes et produit un résultat. Lorsqu'une instruction a pour opérande le résultat d'une autre, on dit que la première est l'instruction consommatrice, alors que celle qui produit l'opérande est l'instruction productrice. Une instruction productrice et consommatrices ont une dépendance de donnée de type RAW. Dans un graphe dataflow, une instruction productrice émet une flèche vers la ou les instructions consommatrices, ces flèches encodent les dépendances entre instructions.
Les architectures à réduction de graphe et l'encodage des programmes
[modifier | modifier le wikicode]Les architectures dataflow sont conçues pour exécuter automatiquement un programme sous forme de 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. Niveau implémentation, les nœuds et flèches sont implémentés différemment. Implémenter les flèches demande d'encoder les dépendances entre instructions productrices et consommatrices.
Pour cela, les architectures dataflow se passent de program counter. A la place, chaque instruction intègre l'adresse de l'instruction suivante. Pour le dire autrement, l'instruction productrice encode l'adresse de l'instruction consommatrice, juste à côté de l'opcode. Évidemment, c'est là le cas le plus simple, où il y a une seule instruction consommatrice. S'il y en a plusieurs, il faut encoder une liste des instructions consommatrices. En clair, chaque instruction encode la liste des instructions suivantes, les adresses mémoire de toute instruction qui a besoin de son résultat.
En plus de l'adresse de l'instruction consommatrice, l'instruction peut encoder d'autres informations utiles. L'une d'entre elle est si l'instruction consommatrice consomme une ou deux opérandes. Une instruction peut utiliser une opérande (par exemple, l'opération NOT) ou deux opérandes (addition, soustraction, autres), parfois plus. Mais sur les architectures dataflow, on se limite aux instructions à une ou deux opérandes, pas plus. Le caractère mono- ou bi-opérande est encodé sur un bit. Il est utilisé pour certaines optimisations, comme on le verra plus bas.
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. Elles n'ont pas le choix, vu que l'ordre des instructions n'est pas garantit. Si elles modifiaient l'état du processeur, cela altérerait l'exécution des instructions suivantes. Et vu que ces instructions suivantes ne seraient pas les mêmes d'une exécution du programme à l'autre, du fait de l'exécution dans le désordre, cela causerait des bugs très difficiles à corriger.
 |
 |
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.
 |
 |
Ces instructions permettent de créer des structures de contrôle usuelles.
 |
 |
La gestion de la disponibilité des opérandes
[modifier | modifier le wikicode]Sur une architecture dataflow, 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 les architectures dataflow n'ont pas besoin de détecter les dépendances entre instructions, car elles leur sont données sur un plateau, tout est géré au niveau du jeu d'instruction. En théorie, les architectures dataflow peuvent en profiter pour charger et exécuter plusieurs instructions indépendantes en même temps. Pour cela, elles intègrent plusieurs unités de calcul, mais elles peuvent aussi inclure plusieurs processeurs dataflow reliés entre eux par un réseau local de communication.
Lorsqu'une instruction génère son résultat, celui-ci est combiné avec la liste des instructions consommatrices. La combinaison est assez logique, vu qu'elle regroupe le résultat et les instructions qui vont le consommer. Le regroupement est appelé un jeton, terminologie beaucoup utilisée dans la littérature sur les architectures dataflow. Le terme a cependant été utilisé pour désigner beaucoup de concepts similaire dans cette littérature : il désigne tout regroupement entre une donnée/opérande avec d'autres informations supplémentaires.
Dans le cas des instructions SWITCH et MERGE, qui remplacent les branchements, la liste d'instruction consommatrice n'est pas la même selon que le branchement est pris ou non.
Le jeton inclus aussi d'autres informations, associées avec les adresses des instructions consommatrices. Notamment, il inclut le caractère mono- ou bi-opérande de chaque instruction consommatrice. La raison est assez simple. Une instruction mono-opérande peut s'exécuter automatiquement si son adresse est encodée dans un jeton, car le jeton contient la seule opérande demandée par l'instruction mono-opérande pour s'exécuter. Elle peut être exécutée immédiatement et le processeur peut s'en rendre compte très facilement, juste en testant un bit. Par contre, les instructions bi-opérande doivent avoir deux jetons, deux opérandes prêtes. Détecter si une instruction bi-opérande peut s'exécuter demande plus de travail et un circuit spécialisé.
Le principal problème avec ce système est lié aux boucles ou à des fonctionnalités similaires. En présence de boucles, il se peut qu'une instruction productrice se soit déjà exécutée plusieurs fois et ait fournit plusieurs résultats. L'instruction consommatrice doit alors utiliser ces résultats dans le bon ordre, du plus ancien au plus récent. La réponse à ce problème distingue les architectures dataflow statiques et dynamiques.
Les architectures dataflow statiques
[modifier | modifier le wikicode]Les architectures dataflow statiques sont les plus simples. Leur design est très inspiré du design original de Dennis, premier chercheur à avoir proposé un design d'architecture dataflow. Sur ces architectures, une instruction productrice doit attendre que les instructions consommatrices aient consommés son résultat, avant de s'exécuter à nouveau.
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. Les limitations des architectures dataflow statiques sont un gros problème. Se passer de boucles ou de fonctions réentrantes n'est pas une option valable pour les programmeurs. Et cela explique que de telles architectures se comptent sur les doigts d'une main.
Elles ont été introduites par Dennis, dans un papier de recherche, qui a été implémenté en hardware par lui et son équipe. Le prototype était appelé la MIT static machine dataflow, et était implémenté avec 8 processeurs interconnectés avec des routeurs, avec un ordinateur PDP-11 servant d'interface. Les 8 processeurs étaient des processeurs séquentiels normaux qui émulaient un processeur dataflow via du microcode, les unités de calcul étaient implémentées avec des ALU bit-slicées d'AMD. D'autres prototypes du même genre ont été inventés, comme celui du projet LAU "langage à assignation unique" de l'université de Toulouse.
Une implémentation hardware sans microcode est celle du µPD7281 de Texas Instrument. Son architecture est décrite dans ce document : [1]. Une autre machien du même genre a été inventée par la Hughes Aircraft Company.
Le codage statique des instructions
[modifier | modifier le wikicode]Une instruction contient, outre son opcode, un espace pour stocker chaque opérande, ainsi que des bits de présence qui indiquent si l'opérande associé est disponible. Les opérandes sont donc stockés dans l'instruction et sont mises à jour par réécriture directe de l'instruction en mémoire. Une instruction contient donc un ou plusieurs opérandes, qui sont chacun associé à un bit de présence qui indique si l'opérande est disponible ou non. 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. De plus, chaque instruction contient l'adresse de l'instruction suivante, celle à laquelle envoyer le résultat.
 |
 |
Avec ces architectures, on doit empêcher une instruction productrice de fournir un résultat si un autre résultat est en attente d'être consommé. En effet, il ne faut pas que le nouveau résultat écrase celui en attente dans l'instruction consommatrice. Pour empêcher cela, chaque instruction contient un bit qui indique si elle peut calculer un nouveau résultat. Il est appelé le jeton d'autorisation. Quand une instruction consommatrice s'exécute, elle prévient ses instructions productrices, pour leur dire qu'elle est prête à accepter un nouvel opérande. Les instructions productrices s'exécutent alors, sauf si elles sont dans la même situation, fournissent leur résultat et l'enregistre dans l'instruction consommatrice.
L'introduction du jeton d'autorisation demande d'ajouter de quoi le gérer. L'instruction productrice fournit un résultat qui est utilisé par N instructions consommatrices, donc N jetons d'autorisation nécessaires. Pour garder la trace des N jetons d'autorisation nécessaires, une instruction productrice contient un champ "autorisation". Il est initialisé à la valeur N, mais est décrémenté à chaque fois qu'un jeton d'autorisation est émis. Quand il atteint 0, l'instruction productrice peut s'exécuter, si ses opérandes sont disponibles.
La microarchitecture d'une architecture dataflow statique
[modifier | modifier le wikicode]Dans les grandes lignes, une architecture dataflow statique est composée de deux éléments principaux, une Enabling Unit et une unité de calcul, représentés sur le schéma que vous pouvez voir en dessous. Seul l'Enabling Unit est reliée à la mémoire, l'unité de calcul ne l'est pas. Le séquenceur sert d'intermédiaire entre unité de calcul et mémoire RAM, c'est un peu comme une sorte de fusion entre un séquenceur normal et l'unité de communication avec la mémoire. Elle enregistre les résultats fournit par l'ALU en RAM, dans les champs opérande des instructions consommatrices. Lors de l'écriture d'un résultat, elle vérifie si l'instruction consommatrice a toutes opérandes, et l'exécute cas échéant.
Le défi est qu'un résultat est souvent envoyé à plusieurs instructions consommatrices, et qu'elles doivent toutes s'exécuter à se moment. Un moyen pour cela est d'en exécuter une et de mettre les autres en attente. Pour cela, le séquenceur peut intégrer une file d'instructions, qui met en attente les instructions consommatrices dont toutes les opérandes sont prêtes. L'enabling unit vérifie le contenu de la file d'instruction dès qu'elle veut exécuter une nouvelle instruction.
La file d'attente des instruction contient soit une copie des instructions elles-mêmes, soit leurs adresses en mémoire RAM. La seconde solution est beaucoup plus économe en circuit, ce qui fait qu'elle est préférée à la première. Dans les deux cas, l'introduction de la file d'attente fait qu'il est préférable de scinder l'Enabling Unit en deux. La première est l'unité d'appariement, ou Matching Unit, qui s'occupe de l'enregistrement des opérandes en RAM et de la détection des instructions prêtes. L'autre unité s'occupe du décodage des instructions, et éventuellement de leur chargement si la file d'instruction mémorise des adresses mémoire.
Les architectures dataflow dynamiques
[modifier | modifier le wikicode]Les architectures dataflow dynamiques acceptent plusieurs instances d'une même opérande, produites par une même instruction productrice. Mais il faut garantir que les opérandes soient utilisés dans l'ordre, dans leur ordre de production. Pour cela, ces architectures dataflow dynamiques associent un tag à chaque opérande, un numéro qui indique leur ordre de production. La gestion des opérandes change du tout au tout. Sur les architectures dataflow statiques, jetons et opérandes étaient approximativement la même chose, si ce n'est que les opérandes étaient propagées avec l'adresse de l'instruction consommatrice. Mais sur les architectures dataflow dynamiques, les jetons contiennent en plus le tag.
- Il est intéressant de faire une analogie entre les architectures dataflow avec les architectures à exécution dans le désordre. Les architectures dataflow dynamiques implémentent une sorte de renommage de registres. Le tag est équivalent à une sorte de numéro de registre physique, obtenu après renommage de registre. Sur une architecture dataflow statique, une instruction productrice écrit son résultat dans une adresse toujours fixe. Avec les dynamiques, les adresses sont renommées comme un registre le serait avec le renommage de registres, une même adresse logique correspond à plusieurs adresses logiques, le tag permettant de sélectionner la bonne adresse.
La gestion des tags des architectures dataflow dynamique
[modifier | modifier le wikicode]Avec l'usage de tags, l'instruction n'utilise plus des bits de présences pour chaque opérande. 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 opérandes avaient un emplacement pré-réservé dans les instructions mêmes, mais les architectures dynamiques ne le permettent pas. C'est maintenant aux opérandes d'indiquer quelle l'instruction qui doit les manipuler, quelle est son adresse.
Toute la difficulté est la production des tags. La gestion des tags peut être gérée directement dans le jeu d'instruction, avec des instructions dédiées à la gestion des tags. Mais le processeur peut aussi se débrouiller sans aide du logiciel. En théorie, les tags sont altérés à chaque fois qu'on entre dans une boucle ou qu'on exécute une fonction. Une implémentation partielle attribue un tag à chaque opérande, initialement à 0. Les instructions de calcul propagent les tags, c'est à dire que le tag d'un résultat est une copie du tag de leurs opérandes. Par contre, les instructions liées aux boucles ou les appels de fonction altèrent le tag passé en entrée.
Pour les instructions liées aux boucles, elles doivent générer un nouveau tag à chaque itération de la boucle. Typiquement, elles incrémenter le tag à chaque nouvelle itération. Le tag est alors un vulgaire compteur d'itération de boucle, pour les boucles les plus simples. La sortie de boucle peut ou non reset les tags, tout dépend de l'implémentation.
L'architecture générale d'une architecture dataflow dynamique
[modifier | modifier le wikicode]Les opérandes sont mémorisés à part des instructions, les deux sont dans des mémoires séparées (en clair, les architectures dynamiques sont de type Harvard). Il y a une mémoire RAM pour les opérandes, une autre pour les instructions proprement dite, à savoir leur opcode et la liste des instructions consommatrices. L'Enabling Unit est alors scindée en deux : une unité d'appariement (Matching Unit) et une unité de chargement/décodage. L'unité d’appariement écrit les opérandes en mémoire, vérifie si les instructions consommatrices ont toutes les opérandes sont disponibles. Si une instruction est prête, elle est envoyée à l'unité chargement, qui lit l'opcode de l'instruction, le concatène avec les opérandes, et envoie, le tout à l'ALU.
Il faut noter que pour simplifier les choses, les instructions sont considérées comme étant toutes dyadiques, à savoir qu'elles prennent deux opérandes. Et qui dit deux opérandes dit que l'une d'entre elle sera calculée avant l'autre. La première opérande sera mise en attente en attendant que la seconde soit produite. Pour cela, les opérandes sont mises en attente en sortie de l'ALU, dans une file d'opérande, une file de jetons. Les opérandes y attendent tant que l'instruction consommatrice puisse s'exécuter. Une fois qu'une instruction consommatrice a toutes ses opérandes, elles sont retirées de la file d'attente et envoyées à l'unité de chargement/décodage et/ou l'ALU.
Détecter qu'une instruction consommatrice est prête se fait lors de la production d'un résultat/opérande : l'unité d'appariement vérifie si une opérande avec le même tag et la même adresse d'instruction consommatrice est dans la file d'attente. Pour cela, la file d'attente des opérandes est en réalité une mémoire associative, plus précisément une sorte de cache. Elle mémorise l'opérande, le tag et l'adresse de l'instruction consommatrice. Dès qu'une nouvelle opérande est produite, son tag et l'adresse de l'instruction consommatrice sont comparées aux opérandes en attente. Si une correspondance est trouvée, alors l'instruction associée s'exécute. Sinon, l'opérande est mis en attente.
Afin de simplifier la détection des opérandes prêtes, le jeton peut indiquer si l'instruction consommatrice est dyadique (deux opérandes) ou à une seule opérande. L'idée est que pour les instructions mono-opérande, ont n'a pas besoin de détecter les opérandes prêtes. Dès que l'opérande est produite par l'ALU, on sait que l'instruction est prête, il y a juste à vérifier les tags.
La mise en attente des opérandes fait que les jetons d'autorisation n'ont plus de raison d'exister. Une instruction productrice peut accumuler des opérandes en avance, chacune avec des tags différents.
Les mémoires RAM sur les architectures dataflow dynamiques
[modifier | modifier le wikicode]La file d'opérande remplace les registres du processeur, en première approche. Les deux mémorisent les opérandes calculées et destinées à être utilisées plus tard. Et comme le banc de registres, la file d'opérande a une taille limitée. Sauf que si elle est pleine, le processeur est bloqué et ne peut plus démarrer de nouvelle instruction. Pour gérer ce cas problématique, le processeur incorpore une mémoire RAM et un système de gestion de débordement. Le système de gestion de débordement s'occupe d'échanger des données entre RAM et file d'opérandes.
Vous avez peut-être l'impression qu'il manque quelque chose à l'architecture précédente, ou du moins que quelque chose cloche. La RAM est utilisée comme une sorte de mémoire étendant la file d'opérande, elle n'est jamais adressée explicitement. Mais alors, comment sont gérées les structures de données ? La réponse est qu'elles demandent d'ajouter une seconde mémoire RAM annexe, spécialisée dans les structures de données; appelée une I-Structure.
Elles facilitent l'implémentation des tableaux principalement, mais aussi d'autres structures de données secondairement. La lecture ou l'écriture d'une opérande dans une I-structure se fait par l’intermédiaire d'instructions spécialisées, une pour la lecture, une autre pour l'écriture. Elles sont équivalentes aux instructions LOAD et STORE des architectures LOAD-STORE.
Les I-structures sont presque identiques aux mémoires RAM usuelles, la seule différence étant qu'elles sont conçues pour être utilisées avec une architecture taguée. Pour rappel, une architecture taguée ajoute des méta-données à chaque case mémoire. Ici, chaque case mémoire correspond à une opérande complète. Les méta-données sont utilisées pour savoir si une opérande est disponible, ou qu'une case mémoire est réservée pour une future opérande.
Intuitivement, ce sont une amélioration du bit de disponibilité, voire à un tag. Elles mémorisent si la case mémoire est inoccupée, occupée par une opérande valide, réservée pour une future opérande (une instruction a tenté de lire le mot mémoire, mais celle-ci était vide). Si le mot mémoire est dans le troisième cas, l'adresse de l'instruction consommatrice est ajoutée aux méta-données, idem pour le tag.
Les architectures Explicit Token Store
[modifier | modifier le wikicode]les architectures Explicit Token Store se débarrassent du système de tag des architectures dynamiques et reprennent les bits de présence pour chaque opérande. En théorie, c'est censé poser problème avec les boucles et les fonctions. L'idée est que les opérandes sont dupliquées, avec une copie pour chaque itération de boucle ou chaque instance d'une fonction. 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.
Pour cela, les opérandes d'une fonction ou d'une boucle sont stockées dans une structure dédiée. La structure regroupe plusieurs opérandes les unes à côté des autres en mémoire. Chaque opérande est associée à un bit de présence qui dit si l'opérande est disponible ou non. Pour les boucles, il y a autant de structures que d'itérations de la boucle, une par itération. Pour les fonctions, il y a autant de structures que d'instances de la fonction, une par instance.
Des instances ou itérations peuvent s'exécuter en même temps, ce n'est pas un problème car les opérandes seront écrites dans des adresses différentes, alors qu'elles auraient voulu écrire dans un même champ opérande sur une architecture dataflow. L'avantage avec les architectures à token tagué précédentes, est qu'elles n'ont pas besoin d'utiliser une mémoire associative couteuse pour détecter la disponibilité des opérandes. Pas besoin de comparer des tags, il suffit de calculer une adresse à partir du pointeur vers la structure.
Les structures en question peuvent être vues comme des cadres de pile, à la différence près qu'il n'y a pas de pile mais plutôt une liste chainée de structures, voire un arbre de structures. Une autre différence avec la pile des architectures usuelles tient dans le fait que les structures ne sont pas stockées les unes à la suite des autres en mémoire RAM, mais peuvent être dispersées n'importe où et n'importe comment 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.
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. La détection de la disponibilité des opérandes d'une instruction est assez coûteuse et prend un certain temps. L'immutabilité des variables fait que la gestion des structures de données est laborieuse pour le compilateur et le programmeur, avec un léger cout en performance comparé à un programme impératif. Et ensuite, le plus gros problème de tous : le code exécuté sur ces architectures a une mauvaise localité temporelle et spatiale, ce qui fait que les caches sont peu efficaces.
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 idées qui vont suivre sont faciles à comprendre si on introduit la notion de basic bloc, Bloc de base en français. Concrètement, les blocs de base correspondent soit aux corps des boucles, soit aux code d'une fonction. Un bloc de base est un ensemble d'instructions qui, dans un programme normal, s'exécutent les unes après les autres. Sur les architectures dataflow, cette contrainte est relâchée, mais il y a un ordre partiel. Par contre, dans les deux cas, il n'y a pas de branchements dans un bloc de base, ni d'instructions switch/merge ou tout autre instruction équivalente. Un bloc de base est exécuté quand un branchement/switch saute vers celui-ci,n vers sa première instruction. On quitte un bloc de base par un branchement ou une instruction switch/merge.
Les architectures Explicit Data Graph Execution utilisent une approche simple : on découpe un programme en blocs de base qui sont exécutés dans l'ordre, mais avec une exécution dans le désordre à l'intérieur des blocs de base. Les blocs de base ont une taille maximale de 128 instructions. Si l'exécution des blocs de base suit globalement l'ordre séquentiel, l'exécution à l'intérieur se fait dans le désordre, en suivant les dépendances de données. L'encodage des blocs de base suit un encodage similaire à celui des architectures dataflow. Certaines architectures de ce type ont déjà été inventées, comme les processeurs WaveScalar et TRIPS.
Les architectures Threaded Dataflow utilisent l'approche inverse. À l'intérieur de ces blocs de base, 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.