Fonctionnement d'un ordinateur/Architectures multithreadées et Hyperthreading
Vous pensez surement qu'il faut obligatoirement plusieurs cœurs pour exécuter plusieurs programmes en parallèle, mais sachez que c'est faux ! Les processeurs mono-cœur en sont capables, en alternant entre les programmes à exécuter. Plusieurs programmes s’exécutent donc sur le même processeur, mais chacun à leur tour et non en même temps. D'ordinaire, cette alternance est gérée par le système d'exploitation, mais certains processeurs gèrent cette alternance eux-mêmes, directement au niveau matériel. Les processeurs en question sont appelés des processeurs multithreadés, ou encore des architectures multithreadées, en référence au terme thread, qui est plus ou moins équivalent à celui de programme dans ce cours. Ils exécutent un thread à la fois, mais changent de thread plus ou moins régulièrement.
Pour comprendre le pourquoi des architectures multithreadées, il faut rappeler qu'il arrive que l'unité de calcul d'un processeur ne fasse rien, par exemple pendant que le processeur accède à la mémoire. Les cycles d'horloge où l'unité de calcul est inutilisée sont des cycles gâchés. L’exécution dans le désordre réduit ces cycles gâchés, mais les architectures multithreadées sont une solution alternative et complémentaire. Elles visent à ce que les cycles gâchés d'un thread soient remplis par les calculs d'autre thread. Pour cela, le reste du processeur subit des changements liés à la présence de plusieurs threads en cours d'exécution. Notamment, il y a deux changements qui sont systématiquement présents sur tous les processeurs avec multithreading matériel.
Premier changement : le processeur doit savoir à quel thread appartient chaque instruction dans son pipeline. Pour cela, il attribue à chaque thread un identifiant de thread, aussi appelé thread ID. Il n'est qu'un numéro qui précise le thread en question. Il y en autant que de threads exécutables simultanément par le processeur. Par exemple, si le processeur gère au maximum 8 threads simultanés, l'identifiant de thread va de 0 à 7 et est codé sur 3 bits.
Second changement : il y a un Program Counter par thread. A chaque cycle, un multiplexeur choisit le Program Counter - le thread - qui a la chance de charger ses instructions. Le choix du program counter sélectionné est le fait de l'unité d'ordonnancement, dont le fonctionnement dépend du processeur, comme nous le verrons plus bas.
Il existe trois techniques de multithreading matériel : le Fine Grained Multithreading, le Coarse Grained Multithreading et le Simultaneous MultiThreading. Le Simultaneous MultiThreading est spécifique aux processeurs superscalaires, alors que les autres techniques fonctionnent sur tous les processeurs, qu'ils soient superscalaire ou simple-émission.
- Dans ce qui suit, nous utiliserons l'abréviation FGMT pour parler du Fine Grained Multithreading, de CGMT pour parler du Coarse Grained Multithreading et de SMT pour le Simultaneous MultiThreading.
Le multithreading temporel
[modifier | modifier le wikicode]Le FGMT et le CGMT sont regroupés sous le terme de multithreading temporel. Les deux partagent en effet un même point commun : à chaque cycle, les instructions émises par l'unité d'émission proviennent d'un seul programme. La distinction n'a de sens que sur les processeurs à exécution multiple, ce sera plus clair dans la suite du chapitre quand on comparera multithreading temporel et SMT. La différence entre FGMT et CGMT est la fréquence des changements de thread : à chaque cycle ou presque pour le FGMT, lors d'un évènement bien précis pour le CGMT.
Les processeurs à multithreading temporel sont généralement des processeurs sans exécution dans le désordre, et n'ont donc pas de renommage de registres. Avec eux, il est obligatoire de dupliquer les registres pour que chaque programme ait son ensemble de registres architecturaux rien qu'à lui. Cela demande soit un banc de registre par programme, soit un banc de registre commun géré par fenêtrage de registre (chaque programme ayant sa propre fenêtre de registres).
Il faut aussi dupliquer les load-store queue, pour séparer les lectures/écritures en attente de chaque thread. Là encore, il est possible d'utiliser une load-store queue unique dans laquelle on ajoute des informations pour savoir à quel thread appartient telle ou telle lecture/écriture.
Le Coarse Grained Multithreading
[modifier | modifier le wikicode]
Le Coarse Grained Multithreading change de programme quand un évènement bien précis a lieu. L'évènement en question fait que l'ALU restera inutilisé pendant un moment : accès à la mémoire, branchements, etc.
Sur certains processeurs CGMT, il y a une instruction précise pour changer de thread. La commutation de thread est alors totalement ou partiellement décidée par le logiciel. Mais il s'agit là d'un cas particulier.
Le cas le plus fréquent est de changer de thread lors d'un défaut de cache. Vu que l'accès à la RAM est quelque chose de très lent, il est intéressant d'exécuter des instructions d'un autre thread pour recouvrir l'accès à la RAM. L'idée est similaire à ce qu'on a avec les lectures non-bloquantes et/ou l'exécution dans le désordre : pendant que l'unité d'accès mémoire gère le défaut de cache, on alimente l'unité de calcul avec des calculs indépendants. Sauf qu'avec le multithreading, les calculs proviennent d'un autre thread.
Un point important est que le cache doit être un cache non-bloquant, sans quoi le multithreading matériel ne fonctionne tout simplement pas. Par exemple, prenons une architecture qui change de thread à chaque défaut de cache. Si on veut supporter plus de deux threads, il faut que plusieurs threads subissent un défaut de cache pour que le multithreading ait de l'intérêt, ce qui implique un cache non-bloquant.
Avec le CGMT, on est certain que toutes les instructions en cours d’exécution appartiennent au même thread. Quand il passe d'un thread à l'autre, le processeur attend naturellement que le pipeline soit complétement vidé avant de charger les instructions du thread suivant. Le processeur peut donc se débrouiller avec un simple registre de thread qui mémorise le thread ID du thread en cours d'exécution. Le registre de thread est directement connecté à l'entrée d'adresse du banc de registre, pour gérer le fenêtrage de registres. Il est aussi connecté à la load-store queue, et surtout au multiplexeur de choix de thread, dans l'unité de chargement.
L'unité d'ordonnancement détermine quel thread charger dans le pipeline, elle sélectionne un thread ID. Pour faciliter son travail, cette unité contient un registre qui mémorise quels sont les threads actifs. Les threads bloqués par un défaut de cache sont marqués comme inactifs tant que le défaut de cache n'est pas résolu. Évidemment, dès qu'un défaut de cache est résolu, l'unité d'accès mémoire prévient l'unité de choix de thread pour que celui-ci marque le thread adéquat comme de nouveau actif. Le registre est composé de N bits sur un processeur qui gère N threads maximum : chaque bit est associé à un thread et indique s'il est actif ou non.
Le Fine Grained MultiThreading
[modifier | modifier le wikicode]
Le Fine Grained Multithreading regroupe deux types de processeurs différents. Le premier type est celui des barrel processors, qui changent de programme à chaque cycle d'horloge. Idéalement, chaque étage du pipeline est utilisé par une instruction différente. L'avantage est que, à l'intérieur d'un thread, une nouvelle instruction démarre quand la précédente est terminée. Le résultat d'une instruction est déjà dans les registres quand l'instruction suivante s’exécute. Il n'y a donc pas de dépendances entre instructions successives, les circuits liés aux dépendances de données sont fortement simplifiés, le réseau de contournement de l'ALU disparait, l'unité de prédiction de branchement disparait (car le résultat d'un branchement est connu avant que le même thread exécute sa prochaine instruction).
Mais les accès mémoire sont gérés à part des autres instructions. Lorsque un thread effectue un accès mémoire, il est mis en pause et d'autres threads sont lancés à sa place. Prenons l'exemple d'un processeur qui gère 16 threads maximum : si l'un d'eux est mis en pause, le processeur changera de thread tous les 15 cycles au lieu de 16. Mais pour que cela fonctionne sans encombre, on est obligé d'avoir un nombre assez élevé de programmes en cours d’exécution. Pour donner un exemple, le processeur MTA était capable d'exécuter un 128 threads maximum, pour un pipeline de 21 étages. La marge est élevée, mais cela compense le fait que le processeur n'a pas de cache, avec des accès mémoire prenant 150-170 cycles d'horloge ! Le désavantage est que les registres étaient dupliqués 128 fois ! Le processeur avait près d'un millier de registres, ce qui est énorme pour l'époque.
Utiliser un barrel processor au mieux demande donc qu'il y ait un grand nombre de threads en cours d'exécution. Mais quelques processeurs FGMT font autrement, en se rapprochant du CGMT. Ils peuvent exécuter un thread durant quelques cycles successifs, plus d'une dizaine, voire plus. Cependant, il s'agit de processeurs sans exécution dans le désordre, qui sont bloqués dès qu'ils tombent sur une instruction dépendante. Et justement, ils masquent ces blocages en changeant de thread au lieu d'émettre des bulles de pipeline. La technique est beaucoup utilisée sur les cartes graphiques modernes, et sur certains processeurs spécialisés.
Le désavantage est qu'ils doivent intégrer des scoreboards pour gérer les dépendances de données, sauf sur quelques processeurs laissaient la détection des dépendances au compilateur ! Un exemple historique assez ancien est le processeur Tera MTA (MultiThreaded Architecture), qui introduit la technique de l'anticipation de dépendances explicite (Explicit-Dependence lookahead). L'idée est que chaque instruction contient quelques bits pour dire au processeur : tu peux lancer 1, 2, 3 instructions à la suite, avant de changer de thread.
Qu'il s'agisse des barrel processor ou des autres processeurs FGMT, tous ont une implémentation similaire. Contrairement aux processeurs CGMT, il n'y a pas de registre de thread ID unique. En effet, le processeur doit savoir, pour chaque instruction dans le pipeline, à quel thread elle appartient. Pour cela, les thread ID sont générés lors du chargement et propagés dans le pipeline en même temps que les instructions, où il est utilisé par le banc de registre, dans les load store queues, etc. Pour résumer : propagation du thread ID dans le pipeline et disparition du registre de thread global.
Avec le FGMT, le processeur charge et décode les instructions, avant de les placer dans plusieurs files d'instruction. Il y a une file d'instruction par thread. Le choix de la file d'instruction est réalisé par un multiplexeur, commandé par une super-unité d'émission qui décide quel thread émet ses instructions (thread issue unit).
L'unité d'émission en question contient un scoreboard par thread, et combine leurs résultats pour décider quel thread émet une instruction. Sur les barrel processor, le scoreboard ne gère que les dépendances liées aux accès mémoire, pour gérer les threads mis en pause et les re-démarrer quand la lecture est terminée. Sur les autres processeurs, les scoreboard gèrent les dépendances entre instructions.
Les unités de choix de thread fonctionnent différemment entre les barrel processors et ceux qui peuvent exécuter plusieurs instructions successives d'un même thread. Pour ces derniers, l'implémentation demande une coopération entre l'unité d'émission et l'unité de chargement. Le processeur profite du fait que le chargement des instructions depuis la mémoire et leur exécution se font en même temps : le processeur charge des instructions pendant qu'il en exécute d'autres. Si un thread émet une instruction, ce même thread charge une instruction au même moment. Sauf si la file d'instruction du thread est déjà pleine, auquel cas un autre thread est choisi.
Il est possible de tenir compte du contenu de la fenêtre d'instruction pour décider quels threads sont éligibles au chargement. Il est possible de mettre en pause un thread si celui-ci accumule un peu trop d'instructions dans la fenêtre d'instruction. C'est en effet signe que ce thread est bloqué par un accès mémoire, une instruction multicycle ou des dépendances de données. A l'inverse, il est possible de prioriser les threads qui n'ont presque aucune instruction dans la fenêtre d'instruction. Car ce sont des threads qui s'exécutent rapidement au point de vider la fenêtre d'instruction. L'idée est de charger en priorité les instructions du thread pour lequel la file d'instruction est la moins remplie. L'unité de choix du thread utilise cette information pour déterminer quel thread charger au prochain cycle.
Le Simultaneous multithreading : une spécificité des processeurs superscalaires
[modifier | modifier le wikicode]Les deux techniques vues au-dessus peuvent s'adapter sur les processeurs à émission multiple, à savoir qui sont capables d'émettre plusieurs instructions simultanément. La seule contrainte est que l'implémentation du FGMT est compliquée sur les architectures superscalaires, ce qui fait que les barrel processors sont généralement des processeurs VLIW ou sans émission multiple. Mais il existe une technique de multithreading matériel spécialement pensée pour les processeurs à émission multiple : le Simultaneous multithreading. La comprendre est assez simple si on la compare au FGMT et au CGMT.
Avec le multithreading temporel, lors d'un cycle d'horloge, les instructions émises appartiennent au même thread matériel. Il n'y a pas de situation où une instruction du thread 1 est émise en même temps qu'une instruction du thread 2.
 |
 |
Le Simultaneous Multi-Threading, abrégé en SMT, permet d'émettre simultanément des instructions provenant de threads séparés. Elle fonctionne sur les processeurs superscalaires, mais n'est pas possible sur les processeurs VLIW.
L'implémentation matérielle du SMT
[modifier | modifier le wikicode]Dans les faits, tous les processeurs SMT sont des processeurs à exécution dans le désordre. Non pas que ce soit obligatoire, juste que le cout d'implémentation est bien plus faible sur un processeur à exécution dans le désordre. L'implémentation du SMT prend un processeur à exécution dans le désordre, ajoute plusieurs program counter et les circuits adéquats. L'unité d'émission choisit quelles instructions envoyer aux ALU, en utilisant l'exécution dans le désordre : tant qu'elles sont indépendantes, elles peuvent s’exécuter en parallèle. Et deux instructions de deux threads différents sont indépendantes ! Il y a donc un lien étroit entre exécution dans le désordre et SMT !
Ironiquement, avec l'amélioration des techniques d'exécution dans le désordre, le SMT commence à perdre de sa superbe. Plus l'exécution dans le désordre est efficace, plus le SMT est inutile. Si l'exécution dans le désordre est trop efficace, les cycles gâchés sont trop rares pour que le SMT ne servent pas à grande chose. Quand les cycles gâchés représentent grand maximum 10% du temps d’exécution grâce à l'usage de l’exécution dans le désordre, le SMT n'a plus grand-chose à remplir et le second programme s’exécuterait trop lentement pour ça vaille le coup.
Le SMT s'implémente généralement avec une seule fenêtre d’instruction et avec le renommage de registres. Le renommage de registres fait qu'on n'a pas à utiliser de fenêtrage de registres, juste à augmenter la taille du banc de registres. L'idée est que l'on concatène le thread ID au nom de registre avant de faire le renommage. Comme cela, on garantit que deux registres architecturaux identiques mais référencés dans des threads différents, correspondront à des registres physiques différents. Ainsi, l'unité d'émission a juste à vérifier les dépendances entre registres, pas besoin de gérer les thread ID. En faisant cela, la logique d'émission est beaucoup plus simple. Par contre, les tables pour le renommage de registre sont dupliqués, avec autant de table que de thread, chaque thread a la sienne.
Comme avec le FGMT, en cas des mauvaise prédiction de branchement, seules les instructions du thread fautif doivent être vidées. Pour cela, les files/fenêtres d'instruction doivent savoir à quel thread appartient tel ou telle instruction, pareil pour le Reorder Buffer. Pour cela, on ajoute, dans chaque entrée de ces structures, le thread ID de l'instruction.
Avec le SMT, les différents threads doivent se partager certaines ressources matérielles : la fenêtre d'instruction, le banc de registres, la load store queue, le cache, l'unité de prédiction de branchement ou d'autres structures matérielles. Le partage de ces ressources entre threads est dynamique, sauf pour quelques exceptions. La conséquence est qu'il peut y avoir une perte de performance si on lance deux threads et qu'il n'y a pas assez de ressources matérielles pour en profiter. Les threads entrent en compétition pour y accéder. Parlons un petit peu du partage du cache et de l'unité de prédiction de branchement.
Le partage des caches
[modifier | modifier le wikicode]La quasi-totalité des architectures multithreadées utilisent un cache partagé, et non des caches dédiés, ce qui impose de gérer le partage des caches entre les différents threads.
La première idée est de partitionner le cache en plusieurs morceaux, avec un par thread. Le partitionnement statique donne des portions égales à chaque programme, ce qui n'est pas toujours optimal mais a l'avantage d'être facile à implémenter. À l'opposé, le partitionnement dynamique partage le cache selon les besoins des thread en cours d'exécution. Si un programme a besoin de plus de place que l'autre, il peut réserver un peu plus de place que son concurrent. Mais la gestion du partitionnement est alors plus compliquée, et demande de partitionner efficacement le cache, sans quoi les deux programmes exécutés risquent de se marcher dessus et d'entrer en compétition pour le cache.
Une autre possibilité est de ne pas partitionner et de laisser les différents threads accéder au cache comme bon leur semble. Si le cache est physiquement tagué, il n'y a aucune modification à faire. Mais si le cache est virtuellement tagué, une même adresse virtuelle peut correspondre à des adresses physiques différentes pour deux threads différents. Pour éviter cela, il faut ajouter l'identifiant de thread dans chaque ligne de cache, dans les bits de contrôle. La détection des succès ou défaut de cache tient compte de l'identifiant de thread lors des comparaisons de tags, afin d'éviter qu'un thread lise une donnée d'un autre thread.
A l'inverse des processeurs mono-cœur, les processeurs multithreadés préfèrent des caches dont le débit binaire est plus important que la latence mémoire. La raison est que deux threads consomment deux fois plus de données qu'un seul et le débit binaire du cache doit suivre. Par contre, la latence est moins importante car les cycles gâchés qu'elle créé sont remplis par le multithreading matériel. Si un défaut de cache prend 4 cycles, le multithreading matériel va rapidement trouver des instructions à exécuter pendant ces cycles.
Tout ce qui vient d'être dit s'applique aussi sur la TLB. Il est possible de la partitionner entre plusieurs threads. La plupart du temps, le partitionnement est statique sur les TLB dédiées aux instructions, alors que les TLB pour les données sont partagées dynamiquement. C'est le cas sur les architectures Skylake d'Intel, où les 128 entrées de la TLB d'instruction de niveau 1 ont découpées en deux sections de 64 entrées, une par programme/thread, les autres TLB étant partitionnées dynamiquement. Une autre solution est d'ajouter un identifiant de thread dans chaque entrée de la TLB, sur le même principe que celui vu dans le chapitre sur la TLB. Le gain en performance est bien plus important, pour un cout en hardware limité.
L'unité de prédiction de branchement
[modifier | modifier le wikicode]Un autre cache est lui aussi partitionné ou complété avec des thread ID : le branch target buffer. Rappelons que c'est un cache spécialisé pour les adresses de branchements. L'unité de prédiction de branchements doit idéalement séparer les branchements entre chaque thread pour obtenir de bonnes performances, soit en partitionnant le BTB, soit en ajoutant ajouter un Thread ID dans chaque entrée de ce cache. Mais ce n'est pas obligatoire.
Les unités de prédiction de branchement vues dans les chapitres précédents peuvent parfaitement fonctionner telles quelles sur un processeur multithreadé. Le branch target buffer mémorise alors des branchements de threads différents, il ne sait pas à quel thread appartient tel branchement, mais le tout fonctionne. Le problème est que les prédictions pour un branchement sont parasitées par les branchements d'autres threads, surtout pour les unités se basant sur un historique global. Malgré tout, on obtient un résultat tolérable, les performances sont assez bonnes et cela s'explique avec ce qui suit.
Déjà, il arrive que les branchements des autres threads aient un effet positif sur la prédiction pour un thread. De telles interférences positives sont rares, mais possible si les deux threads travaillent sur des données partagées, et c'est alors les unités de prédiction de branchement normales, sans partitionnement ni thread ID qui fonctionnent mieux, sous certaines circonstances.
De plus, quand une mauvaise prédiction de branchement est détectée, il faut vider le pipeline des instructions chargées à tort. Et les instructions fautives appartiennent toutes à un même thread, les instructions des autres threads ne sont pas concernées. Le vidage du pipeline est donc sélectif. Là encore, la vidange du pipeline se base sur les Thread ID propagés dans le pipeline. Vu que le vidage du pipeline est sélectif, partiel, la perte de performance en cas de mauvaise prédiction de branchement est donc plus faible, et cela surcompense le fait que les prédictions de branchement sont parasitées par les branchements d’autres threads.