« Fonctionnement d'un ordinateur/Les architectures dataflow » : différence entre les versions
Contenu supprimé Contenu ajouté
Aucun résumé des modifications |
m typo |
||
Ligne 7 :
[[File:Dataflow graph.PNG|vignette|Exemple de graphe dataflow.]]
Il va de
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.
Ligne 17 :
[[File:Singledataflownode.png|centre|vignette|Représentation d'une instruction "normale".]]
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''
{|
Ligne 34 :
===La gestion de la disponibilité des opérandes===
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
Pour cela, il va attribuer aux données disponibles ce qu'on appelle un '''jeton'''. Il 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''.
Ligne 40 :
[[File:Dataflowfiringnodes.png|centre|vignette|upright=2|Illustration de 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. Lorsque
==Les architectures ''dataflow'' statiques==
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
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 opérande, 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.
Ligne 50 :
===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
{|
|[[File:Dataflowsimplestructure.png|centre|vignette|upright=1.5|Illustration du codage de haut niveau d'
|[[File:Dataflowiterstructure.png|centre|vignette|upright=1.5|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
[[File:Représentation d'une instruction en mémoire sur une architecture dataflow.jpg|centre|vignette|upright=2|Représentation d'une instruction en mémoire sur une architecture dataflow.]]
Ligne 63 :
===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
[[File:Diagramme d'une architecture dataflow statique.jpg|centre|vignette|upright=2|Diagramme d'une architecture dataflow statique.]]
Ligne 69 :
===Les défauts de ces architectures===
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
==Les architectures ''dataflow'' dynamiques==
Ligne 79 :
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, vu qu'une instruction dans une boucle ou une fonction peut s’exécuter en un nombre indéterminé d'exemplaires. C'est maintenant aux jetons d'indiquer quelle est l'instruction qui doit les manipuler, en mémorisant son adresse. Les opérandes sont mémorisés à part des instructions, dans une mémoire séparée de la mémoire d'instructions (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.
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
[[File:Architecture dataflow dynamique.jpg|centre|vignette|upright=1.5|Architecture dataflow dynamique.]]
Il va de
==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
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.
Ligne 99 :
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. Hors, 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
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
===Les architectures ''Threaded Dataflow''===
Ligne 109 :
===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).
==Conclusion==
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.
* [http://csd.ijs.si/courses/dataflow/index.htm Dataflow Computers].
|