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

Il va de soitsoi 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 contient les instructions du programme et précise les dépendances de données entre instructions. 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. 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.

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'' quandquant à eux, sont l'équivalent des instructions de branchements, vues plus haut.

Il n'est pas rare qu'une instruction doive attendre un certain évènement avant que ses opérandes soient disponibles. Par exemple, c'est le cas si une instruction attend que des opérandes soient tapéestapés 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 le programme s’exécute, il faut que le processeur sache 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).

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. Lorsque toutestous les opérandes d'une instruction ont leur jeton actif, l'instruction supprime les jetons de ses données et fournit un résultat, auquel on attribuera un nouveau jeton. En clair, les opérandes auront étésété utiliséesutilisés 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 du programme consiste à une propager les jetons à travers le graphe, ce qui se fera suivant les disponibilités des jetons. Quoiqu'ilQuoi qu’il en soit, pour exécuter une instruction, il faudra détecter la disponibilité des jetons qu'elle manipule. 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. 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éunieré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 ?

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éeassocié 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'''.

|[[File:Dataflowsimplestructure.png|centre|vignette|upright=1.5|Illustration du codage de haut niveau d'unune instruction sur une architecture dataflow statique. On voit bien que chaque instruction a un espace réservé pour chaque opérande.]]

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éescalculé 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.

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.

Ces architectures ''dataflow'' statiques ont de gros défauts. Le plus important est que 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é. Autant vous dire que ces architectures ne servent pas à grand chose. 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, lorsqu'on exécute 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 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.

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 quellesquels 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 soitsoi 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''' 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ésententrepré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. 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.

Et ensuite, le plus gros problème de tous : ces architectures sont limitéelimitées par la rapidité de la mémoire RAM principale. La même chose a lieu dans les programmes impératifs sur des architectures normalenormales, à 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ésété abandonnées, après pas mal de recherches, en raison de leurs faibles performances. Mais certains chercheurs ont quand même décidésdé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 '''''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). CesCe 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''.

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. Quoiqu'ilQuoi qu’il en soit, je recommande la lecture dsdes liens qui suivent, pour se renseigner un peu plus sur le sujet :