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 ! Il existe des processeurs spéciaux qui n'ont qu'un seul cœur, mais sont cependant capables d’exécuter plusieurs programmes quasi simultanément. La différence avec les processeurs multicœurs est qu'ils ne sont pas capables d’exécuter plusieurs programmes en même temps, mais qu'ils alternent 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 se passent de l'aide du système d'exploitation et 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, pour les distinguer des processeurs multicœurs.

Les différents types d'architectures multithreadées

Pour comprendre en quoi les architectures multithreadées sont intéressantes, il faut savoir qu'il arrive que l'unité de calcul d'un processeur ne fasse rien, pour diverses raisons. Par exemple, l'unité de calcul peut n'avoir aucun calcul à effectuer pendant que le processeur accède à la mémoire. Les cycles où l'ALU (Arithmetic and Logic Unit, UAL en français : Unité Arithmétique et Logique) est inutilisée sont des cycles gâchés, ce qui trahit bien le fait qu'ils entrainent une perte par rapport aux performances maximales.

Sur les processeurs modernes, on distingue deux types de cycles gâchés : les pertes verticales et horizontales.

Les pertes horizontales sont spécifiques aux processeurs superscalaires. Les pertes horizontales existent quand on n'a pas assez d'instructions à exécuter pour utiliser toutes les ALU : certaines sont utilisées, mais pas toutes. Elles sont spécifiques aux processeurs superscalaires, qui peuvent exécuter plusieurs instructions en parallèle dans des ALU identiques. Plus un processeur superscalaire a une émission large (il peut émettre beaucoup d'instructions en même temps), plus les pertes horizontales sont importantes.
Les pertes verticales correspondent au cas où on n'a juste pas d'instructions à exécuter sur l'ALU lors de ce cycle. Elles existent sur tous les processeurs, qu'ils soient superscalaires ou non, avec ou sans exécution dans le désordre. Avec elles, aucune ALU n’exécute d'instruction, le cycle n'effectue aucun calcul.

Les deux types ont souvent des origines bien différentes. Les pertes verticales sont typiquement causées par des instructions multicycles, comme des accès mémoire ou des opérations flottantes. La raison principale sur les processeurs modernes, est les accès mémoire. Les processeurs sans exécution dans le désordre sont plus exposés que ceux avec exécution dans le désordre aux pertes verticales. Les pertes horizontales sont liées au fait qu'on ne peut pas exécuter assez d'instructions, les instructions à exécuter ont trop de dépendances de données.

Différence entre cycles gâchés horizontaux et verticaux.

Pour éviter cela, les différentes techniques d’exécution dans le désordre sont une solution toute indiquée, mais elles ne suffisent pas toujours. Les architectures multithreadées sont une solution alternative et complémentaire à ce problème. Elles visent à exécuter plusieurs programmes sur un même processeur, de manière à ce que les cycles gâchés d'un programme soient remplis par les calculs du second et réciproquement.

Il existe plusieurs techniques pour ce faire, qui portent les doux noms de Coarse Grained Multithreading, Fine Grained Multithreading et Simultaneous MultiThreading. Elles sont classées en deux types distincts, avec le Simultaneous MultiThreading d'un côté, et les autres méthodes de l'autre. La différence entre les deux groupes est assez simple à comprendre : le Simultaneous MultiThreading permet de remplir les cycles gâchés horizontaux et verticaux, alors que les autres méthodes permettent seulement de remplir les cycles gâchés verticaux. Ces dernières sont donc très adaptées sur les processeurs à émission unique, à savoir non-superscalaires, alors que le Simultaneous MultiThreading est spécifique aux processeurs superscalaires.

Le multithreading temporel

Les deux premières techniques que nous allons sont regroupés sous le terme de multithreading temporel. Il s'agit des techniques autres que le smimultaneous multithreading. Elles ont pour particularité qu'à chaque cycle, les instructions exécutées par la ou les ALUs proviennent du même programme. Sur les processeurs sans émission multiple, la distinction n'a aucun intérêt, vu qu'ils ne peuvent exécuter qu'une seule instruction à la fois. Mais sur les processeurs à exécution multiple, la distinction prend tout son sens. Mais cela sera plus clair dans la suite de cette section. Voyons tout d'abord les deux types de multithreading temporel pour un processeur sans émission multiple, puis avec.

Le Coarse Grained Multithreading change de programme quand un évènement bien précis a lieu. Le changement de programme peut s’effectuer pour des raisons différentes. En général, on change de programme lorsque certaines instructions sont exécutées : accès à la mémoire, branchements, etc.

Le cas le plus fréquent est un accès à la mémoire (lors d'un cache miss). Il faut dire que l'accès à la mémoire est quelque chose de très lent, aussi changer de programme et exécuter des instructions pour recouvrir l'accès à la mémoire est une bonne chose. C'est là un avantage général du multithreading temporel : masquer la latence des accès mémoire.

L'idée est similaire à ce qu'on a avec les lectures non-bloquantes ou l'exécution dans le désordre. L'idée est que 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. Avec l'exécution dans le désordre, les calculs proviennent du même programme, ce sont les instructions qui suivent la lecture. Avec le multithreading, les calculs proviennent d'un autre thread, d'un autre programme.

Le Fine Grained Multithreading change de programme à chaque cycle d'horloge. L'avantage principal est que l'implémentation matérielle est très simple, et permet de simplifier fortement le processeur, comme on le verra plus bas. Mais pour cela, on est obligé d'avoir un nombre assez élevé de programmes en cours d’exécution. Les processeurs de ce type sont souvent appelés des barrel processors, et nous utiliserons ce terme pour simplifier l'écriture. Leur caractéristique est qu'ils changent d'instruction à, exécuter à chaque cycle.

De tels processeurs permettent encore une fois de masquer la latence des accès mémoire. Par exemple, imaginons que les lectures prennent 8 cycles. Si le processeur gére 8 threads et en change à chaque cycle, alors deux instructions d'un même programme seront espacées de 8 cycles de distance. Le résultat de la lecture est disponible immédiatement pour l'instruction suivante, sans avoir à bloquer le pipeline.

Après, la réalité est plus complexe, les accès mémoire sont généralement plus longs que la longueur du pipeline. Impossible de gérer des accès mémoire d'une centaine de cycles avec cette méthode, il faudrait plusieurs centaines de threads et tout autant de registres, ce qui est impraticable. L'idée est alors que lorsque un thread effectue un accès mémoire, il est mis en pause et d'autres threads sont lancés à sa place. Par exemple, sur un processeur qui gére 16 threads concurrents, si l'un d'eux est mis en pause, le processeur changera de thread tous les 15 cycles au lieu de 16. Et si plusieurs threads sont en pause, ils sont retirés du pool de thread chargés à chaque cycle.

Le nombre de threads exécutables par le processeur dépend de la longueur du pipeline. Au minimum, on est obligé d'avoir autant de programmes en cours d’exécution qu'il y a d'étages de pipeline. Et il s'agit d'un minimum, car il arrive que des threads soient mis en pause lors d'un accès mémoire ou d'une instruction multi-cycle très longue (division). Idéalement, il faut plus de threads que d'étage de pipeline, pour avoir assez de threads à exécuter dans le pipeline, malgré les threads mis en pause. Et quand ce n'est pas le cas, on trouve des solutions pour limiter la casse.

Une autre forme de Fine Grained Multithreading permet au processeur s'exécuter un même thread durant plusieurs cycles avant d'en changer. La techniques est beaucoup utilisée sur les cartes graphiques modernes, et sur certains processeurs spécialisés.

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 sans problème. L'implémentation exacte en termes de circuits n'est pas connue, mais une possibilité est la suivante. Les trois bits sont extraits de l'instruction après sa lecture, et introduit dans un compteur qui détermine quand changer de thread.

Le processeur MTA était capable d'exécuter un grand nombre de threads : 128 au total ! 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. Le processeur avait un pipeline de 21 étages, ce qui fait qu'il devait avoir 21 threads actifs pour fonctionner correctement. D'où le grand nombre de threads, 128 en tenant compte des threads mis en pause est une bonne marge de sécurité. 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 très grand nombre de threads était nécessaire pour couvrir la latence des accès mémoire.

Un petit point terminologie avant de poursuivre. Dans ce qui suit, nous utiliserons l'abréviation FGMT pour parler du Fine Grained Multithreading, et de CGMT pour parler du Coarse Grained Multithreading.

Le Simultaneous multithreading : une spécificité des processeurs superscalaires

Les deux techniques vues au-dessus peuvent s'adapter sur les processeurs à émission multiple, à savoir qui sont capables de démarrer plusieurs instructions simultanément sur des unités de calcul séparées, et qui regroupent processeurs superscalaires et VLIW. L'implémentation du CGMT sur un processeur à émission multiple n'a rien de spécifique. Par contre, l'implémentation du FGMT est généralement compliquée sur les architectures superscalaires. La conséquence est que les barrel processors sont généralement des processeurs VLIW ou sans émission multiple.

Avec le multithreading temporel (FGMT et CGMT), lors d'un cycle d'horloge, les deux unités de calcul doivent exécuter des opérations d'un même programme. La conséquence est que les pertes verticales sont atténuées, mais pas les pertes horizontales. Ce qui veut dire qu'on a pas de situation où une unité de calcul exécute une instruction du premier programme alors qu'une autre exécute une instruction du second programme. Il s'agit là de ce qui distingue le multithreading temporel du Simultaneous Multi-Threading.

Le Simultaneous Multi-Threading, abrégé en SMT, permet à plusieurs programmes d'exécuter leurs instructions en même temps, dans des ALUs séparées. À chaque cycle d'horloge, le processeur peut exécuter des instructions provenant de divers programmes. Cela réduit aussi bien les pertes verticales qu'horizontales. Elle ne fonctionne cependant que sur les processeurs superscalaires, mais n'est pas possible sur les processeurs VLIW.

L'implémentation du SMT est assez simple sur les processeurs à exécution dans le désordre. En effet, les circuits qui s'occupent de l’exécution dans le désordre peuvent être modifiés assez facilement pour supporter le SMT. Dans les faits, tous les processeurs SMT sont des processeurs à exécution dans le désordre. Non pas que ce soit obligatoire, on pourrait inventer un processeur SMT à exécution dans l'ordre, et certains travaux de recherche ne se sont pas privés de le faire. Mais la réalité est que le cout d'implémentation est très faible sur un processeur à exécution dans le désordre comparé à l'implémentation sur un processeur à exécution dans l'ordre. Une question d'économie de circuits, en somme.

Et ce n'est pas étonnant quand on sait que SMT et exécution dans le désordre ont plus ou moins le même but : réduire les pertes horizontales. Les deux résolvent le problème en trouvant des instructions indépendantes à exécuter en parallèle, mais pas au même endroit. L'exécution dans le désordre trouve ces instructions à l'intérieur d'un même programme, le SMT en cherchant dans un autre programme. La détection des instructions indépendantes est spécifique à l'exécution dans le désordre, mais les autres circuits ne le sont pas. Les circuits d'émission, de répartition (dispatch), la logique de réveil, les fenêtres d'instruction et autres sont très utiles pour implémenter le SMT.

Ironiquement, avec l'amélioration des techniques d'exécution dans le désordre, le SMT commence à perdre de sa superbe. Architectures multithréadées et exécution dans le désordre sont deux solutions à un même problème. Elles sont donc complémentaires, mais il y a un conflit entre les deux approches. C'est la raison pour laquelle les processeurs grand public modernes, qui ont une exécution dans le désordre très performante, ne sont pas des architectures multithreadées.

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 faibles pertes horizontales qui restent n'ont aucun intérêt à être remplie par un second programme via SMT. Quand seulement les pertes horizontales/verticales 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. Le second programme s’exécuterait trop lentement pour ça vaille le coup. Architectures multithreadées et exécution dans le désordre ont en effet le même but, bien que les solutions apportées soient différentes.

L'implémentation des architectures multithreadées : généralités

L'implémentation des architectures multithreadées est assez simple. Partons du principe que le processeur est composé d'un séquenceur, d'un chemin de données et d'une fenêtre d'instruction. Le séquenceur charge et décode les instructions, le chemin de données fait les calculs et communique avec la mémoire. La fenêtre d'instruction sert d'interface entre les deux en accumulant les instructions décodées et prêtes à être exécutée.

L'implémentation demande de dupliquer les registres

Dans les grandes lignes, il suffit de dupliquer les registres et une partie du séquenceur. Il est obligatoire de dupliquer les registres pour que chaque programme ait son ensemble de registres 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).

Et il n'y a pas que les registres généraux/flottants à dupliquer : le program counter est aussi concerné ! Au minimum, il faut utiliser plusieurs Program Counter, vu que le processeur charge des instructions en provenance de programmes différents. Un circuit se charge de choisir le Program Counter - le thread - qui a la chance de charger ses instructions. Et l’algorithme de choix du programme, l'algorithme d'ordonnancement, dépend du processeur. Le cas le plus simple est celui du FGMT, qui change de programme à chaque cycle d'horloge, le choix du thread est réalisé par un simple compteur incrémenté à chaque cycle d'horloge.

Enfin, il faut aussi dupliquer les load-store queue et éventuellement les ports d'accès au cache. Dupliquer les load-store queue permet de séparer les lectures/écritures en attente de chaque thread. Deux solutions à cela. La première utilise une load-store queue unique dan laquelle on ajoute des informations pour savoir à quel thread appartient telle ou telle lecture/écriture. L'autre est d'avoir des load-store queues physiquement séparées, une par thread.

L'unité de décodage n'a pas à être dupliquée, pas plus que l'unité de calcul.

L'attribution des instructions : le thread ID

Un problème avec le multithreading matériel est que le processeur exécute des instructions provenant de threads différents. Et il doit savoir à quel thread appartient telle ou telle instruction. Pour cela, il attribue à chaque thread un Thread ID, un numéro qui précise le thread en question. Chaque thread se voit attribuer son propre thread ID, 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, le Thread ID va de 0 à 7 et est codé sur 3 bits.

Le thread ID est notamment utilisé pour l'accès aux registres, du moins tant qu'on n'utilise pas d'optimisations avancées impliquant du renommage de registres. L'idée est d'utiliser la même technique que pour les fenêtres d'instructions. Le banc de registre est unique et contient N fois plus de registres, avec N le nombre de threads exécutables simultanément. L'adresse envoyée sur l'entrée d'adresse du banc de registre est formée en concaténant le thread ID avec le nom/numéro de registre. Il s'agit de la même technique que pour le fenêtrage de registres, sauf qu'on utilise ici une fenêtre de registre par thread.

Le thread ID est aussi utilisé pour configurer les multiplexeurs de l'unité de chargement, pour sélectionner le program counter qui aura la chance de charger ses instructions dans le pipeline. Pour du FGMT, on utilise un compteur est incrémenté à chaque cycle d'horloge. Pour le SMT et le CGMT, le thread ID est déterminé par un circuit qui détermine quel est le choix idéal pour charger l'instruction, qui détermine quel est le thread ID optimal. Le thread ID choisi est alors propagé dans le reste du pipeline si besoin.

Enfin, le thread ID est aussi utilisé pour les mémoires caches, comme nous allons le voir dans la section suivante.

Le partage des caches

La quasi-totalité des architectures multithreadées utilisent un cache partagé, et non des caches dédiés. Il reste à 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 peut être statique, ce qui revient à avoir des caches dédiés fusionnés en un seul cache partagé, ou dynamique et varier avec les besoins de chaque thread. Si ces morceaux ont la même taille, on parle de partitionnement statique. Si les morceaux ont des tailles qui changent lors de l’exécution, on parle de partitionnement dynamique.

Le partitionnement statique a l'avantage d'être simple, facile à implémenter. Par contre, il donne des portions égales à chaque programme, ce qui marche mal pour de telles situations. À l'opposé, le partitionnement dynamique permet à chaque programme d'avoir le plus de ressources possibles, ce qui maximise les performances. Si jamais 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 thread accéder au cache comme bon leur semble. Si le cache est physiquement tagué, il n'y a aucune modification à faire, le cache fonctionne très bien comme il est. Mais si le cache est virtuellement tagué, une même adresse virtuelle peut être utilisée par plusieurs threads et donc correspondre à autant d'adresses physiques différentes. Pour éviter cela, on a vu une solution dans le chapitre sur les mémoires caches : ajouter le thread ID dans chaque ligne de cache, dans les bits de contrôle. La détection des succès ou défaut de cache tient compte du thread ID lors des comparaisons de tags, afin d'éviter qu'un thread lise une donnée d'un autre thread.

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 thread ID 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é.

Les processeurs multithreadés ont besoin de caches dont le débit binaire est plus important que la latence mémoire. C'est l'inverse sur les processeurs mono-cœur, qui ont besoin d'une latence la plus faible possible et ne se préoccupent pas trop du débit binaire au-delà d'un certain seuil. La raison est que deux threads consomment deux fois plus de données qu'un seul. Le débit binaire du cache doit donc suivre, pour pouvoir alimenter les deux threads en données. Et si la latence est moins importante, c'est parce que celle-ci tend à créer des vides dans le pipeline, vides qui sont remplis par le SMT. Si un succès de cache prend 4 cycles, l’exécution dans le désordre et le SMT vont rapidement trouver des instructions à exécuter pendant ces 4 cycles. Pareil pour un défaut de cache de 20 cycles, même si c'est un peu plus compliqué.

Un autre 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 à CGMT qui switche de programme à 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,c e qui implique un cache non-bloquant.

L'unité de prédiction de branchement

Un autre cache est lui aussi partitionné ou complété avec des thread ID : le branch target buffer. Rappelons que c'est en effet un cache spécialisé, qui mémorise des adresses de branchements. Et de manière générale, l'unité de prédiction de branchements doit séparer les branchements entre chaque thread pour obtenir de bonnes performances.

Non pas que ce soit nécessaire, 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. Mais le problème est que les prédictions vont se faire en mélangeant des branchements appartenant à des threads différents. Les prédictions de branchement sont donc 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. La raison est que les processeurs SMT tolèrent bien les mauvaises prédictions de branchement.

Quand une mauvaise prédiction de branchement est détectée, il faut vider le pipeline des instructions chargées à tort. Pour cela, les instructions fautives sont retirées. Et elles 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 profite du fait que les Thread ID sont propagés dans le pipeline. Sans SMT ou multithreading matériel, toutes les instructions chargées à la suite du branchement seraient invalides, car appartenant au même thread. Mais avec multithreading matériel, seule une partie l'est, le reste est des instructions d'autres threads. La perte 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.

Cependant, il est possible de corriger ce problème de parasitage des prédictions. Pour cela, deux solutions : partitionner le BTB et les autres caches de branchements, ou ajouter un Thread ID dans chaque entrée de ces caches. Les deux solutions sont possibles, celle du Thread ID est de loin la plus simple à implémenter. Les prédictions sont alors fiables, non-parasitées. Cependant, 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.

L'implémentation des architectures multithreadées : détails spécifiques

La section précédente donne des détails génériques, qui valent pour toutes les architectures multithreadées. Mais il est temps de voir comment chaque technique s'implémente exactement. Intuitivement, on se doute que le CGMT et le FGMT ne s'implémentent pas de la même manière, de même que le SMT est différent des deux techniques précédentes. Rentrons maintenant dans les détails d'implémentation précis de chaque technique.

L'implémentation du coarse grained multithreading

Avec le CGMT, on est certain que toutes les instructions en cours d’exécution appartiennent au même thread. Le processeur change de thread régulièrement, mais il n'y a pas d'instructions provenant de deux thread en même temps dans le pipeline du processeur. 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é au banc de registre, sur son entrée d'adresse, pour gérer le fenêtrage de registres. Le registre de thread est aussi connecté aux load-store queues, pour les mêmes raisons : attribuer les lecture/écritures à un thread. Avec une load-store queue unique, dès qu'une lecture/écriture est insérée dans la load-store queue, il ajoute le thread ID du thread en cours d’exécution. Et cela demande de connecter le registre de thread aux load-store queues.

Le registre de thread ID est directement connecté au multiplexeur de choix de thread de l'unité de chargement, ainsi qu'à l'entrée d'adresse du banc de registres. Les seuls autres circuits à ajouter sont un circuit de choix de thread qui détermine quel thread charger dans le pipeline. Il prend en entrée divers signaux envoyés par le processeur pour faire son choix, et fournit en sortie le thread ID à placer dans le registre de thread.

La seule difficulté est de déterminer comment fonctionne le circuit de choix du thread. Une possibilité est de donner la priorité aux threads qui accèdent le moins à la mémoire RAM (peu de cache miss), à ceux qui ont exécuté le moins d'instructions de branchement récemment, etc. Mais le choix le plus utilisé est de basculer lors d'un défaut de cache. Typiquement, l'unité d'accès mémoire émet un signal cache miss quand un défaut de cache a lieu, qui est envoyé au décodeur pour que ce dernier puisse éventuellement bloquer le pipeline. Et ce signal est aussi envoyé au circuit de choix de thread.

Pour faciliter son travail, cette unité contient deux registres. L'un mémorise le nombre de threads actifs, codé sur quelques bits. L'autre registre mémorise quels sont les threads actifs, qui peuvent charger leurs instructions dans le pipeline. Par exemple, 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. Ils ne peuvent pas être choisis par l'unité de choix de thread, ils ne peuvent pas charger leurs instructions. É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.

L'implémentation d'un barrel processor

Un barrel processors a une microarchitecture similaire à la précédente, sauf que le registre de thread disparait. En effet, avec le FGMT, il y a plusieurs instructions d'un même thread présentes en même temps dans le pipeline. Le processeur doit savoir, pour chaque instruction, à quel thread appartient chaque instruction. Les instructions sont chargées dans l'ordre, en changeant de programme à chaque cycle d'horloge. Les thread ID sont propagés dans le pipeline en même temps que les instructions. Il en est plus ou moins de même avec le Simultaneous Multithreading, pour les mêmes raisons.

Le thread ID est généré par l'unité de choix de thread. Elle est implémentée avec un simple compteur, incrémenté à chaque cycle d'horloge. Le thread ID est envoyé directement sur les entrées du multiplexeur qui choisit quel program counter utiliser. Il est ensuite propagé dans le pipeline, où il est utilisé à plusieurs endroits. Au niveau du banc de registre, où il est envoyé sur les entrées d'adresse, pour gérer le fenêtrage de registres. Dans les unités d'accès mémoire, où il est utilisé pour gérer les load store queues. En somme, à part la propagation du thread ID dans le pipeline, et la disparition du registre de thread global, pas grandes différences avec la technique précédente.

L'avantage du FGMT est que deux instructions successives n'appartiennent pas au même programme. Il n'y a donc pas de dépendances entre instructions successives et les circuits liés à la détection ou la prise en compte de ces dépendances sont fortement simplifiés. Notamment, les circuits de contournement de l'ALU, qui envoient son résultat sur une de ses entrées, deviennent complétement inutiles. Mieux : si le processeur gère suffisamment de threads, le résultat d'une instruction est déjà dans les registres quand l'instruction suivante s’exécute. Les dépendances de données n'ont alors plus aucun impact négatif. Le réseau de contournement de l'ALU, les circuits d’exécution dans le désordre, le renommage de registres et bien d'autres sont complétement inutiles.

De même, l'unité de prédiction de branchement est parfois inutile. Si on exécute suffisamment de threads, le résultat du branchement est connu avant qu'un thread exécute sa prochaine instruction. Par exemple, sur un processeur qui gère 8 threads et change de thread tous les cycles, un thread démarre une nouvelle instruction tous les 8 cycles. Si un branchement met 5 cycles pour fournir un résultat, pas besoin d'unité de prédiction de branchement.

L'implémentation du Fine Grained MultiThreading sur un processeur à émission unique, dans l'ordre

Un barrel processor pur change de programme à chaque cycle d'instruction. Il a un pipeline fixe, ce qui fait que le chargement des instructions et leur exécution se fait dans le même ordre, avec seulement quelques cycles de décalage. Mais il est possible d'implémenter le FGMT sur un processeur avec une fenêtre d'instruction. C'est plus ou moins ce qui est fait sur les cartes graphiques modernes à l'architecture SIMT.

Le processeur est composé de deux boucles, séparées par la fenêtre d'instruction. La première boucle charge des instructions et les décode, avant de les placer dans la fenêtre d'instruction. Elle comprend l'unité de choix de thread, l'unité de chargement, le cache d'instruction, le décodeur. L'autre boucle détecte les instructions prêts à s'exécuter et les exécute. Elle comprend tout ce qui suit la fenêtre d'instruction, à savoir l'unité d'émission et le chemin de données (registres, unités de calcul, unités d'accès mémoire). Il faut noter que l'unité d'émission émet une seule instruction à la fois, qui appartient donc à un thread précis.

Un implémentation possible est alors d'utiliser plusieurs fenêtres d'instruction simplifiées, une par thread. Les fenêtres d'instruction sont très simples : ce sont de simples files d'instructions, à savoir des mémoires FIFOs. En conséquence, le processeur est un processeur à émission dans l'ordre, sans lectures non-bloquantes. Le choix de la file d'instruction est réalisé par un multiplexeur, commandé par une unité de choix de thread.

L'unité de choix de thread est, dans sa version la plus simple, un simple compteur. Les instructions sont chargées dans un ordre round-robin, à savoir que l'on change de thread actif à chaque cycle et que l'on fait passer chaque thread une fois avant de repartir du départ. Par exemple, avec 5 threads, on exécute le thread 1, puis le 2, le 3, le 4 et enfin le 5, avant de reprendre au thread 1 et rebelote.

L'intérêt n'est pas évident, mais l'usage d'une fenêtre d'instruction permet quelques optimisations. L'avantage premier est que le chargement des instructions est découplé de la fenêtre d'instruction, ce qui permet de charger des instructions à l'avance et d'avoir assez d'instructions pour couvrir un accès mémoire. Par exemple, si le processeur gère 32 threads et que la moitié sont en pause suite à un accès mémoire, les 16 restants ont chargé à l'avance assez d'instructions pour couvrir l'accès mémoire.

D'autres optimisations sont possibles. Par exemple, 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 qu'il exécute de longue chaines d'instructions dépendantes les unes des autres. A l'inverse, il est possible de prioriser les threads qui n'ont presque aucune instruction dans la fenêtre d'instruction, qui s'exécutent rapidement au point de vider la fenêtre d'instruction.

Une amélioration drastique de la technique précédente remplace la politique round-robin par un version plus élaborée. Avec elle, plusieurs instructions d'un même thread peuvent être envoyées aux unités de calcul à la suite. L'unité de calcul ne change pas de programme à chaque cycle, elle peut exécuter des instructions indépendantes les unes à la suite des autres, tant que l'émission se fait dans l'ordre. Pas besoin de gérer un nombre impressionnant de threads pour remplir les unités de calcul. Et pas besoin d'utiliser de l'anticipation de dépendances explicite : le processeur s'en charge de lui-même. Par contre, cela signifie que l'on doit ajouter un scoreboard dans l'unité d'émission pour détecter les dépendances entre instructions.

L'implémentation du Simultaneous MultiThreading

L'implémentation du SMT est plus complexe que l'implémentation du CGMT et du FGMT. De plus, l'implémentation fait une distinction entre ce qui est après la file/fenêtre d'instruction et ce qui est avant.

La plupart des implémentations du SMT ne permettent pas de charger des instructions provenant de plusieurs threads différents. Pour le dire autrement, à chaque cycle d'horloge, le processeur charge des instructions provenant du même thread. La raison est que le design de l'unité de chargement est grandement simplifié. L'unité de chargement est similaire à celle utilisée pour le FGMT et le CGMT, c'est une sorte d'hybride entre les deux. Le choix du thread à charger est réalisé par une unité de choix du thread similaire à celle du CGMT. Les thread ID sont propagé dans le pipeline, jusqu'à la file/fenêtre d'instruction. Là, elles sont mises en attente en attendant leur tour.

Les processeurs SMT fonctionnent en accumulant des instructions provenant de plusieurs threads dans la file/fenêtre d'instruction. L'unité d'émission peut choisir quelles instructions exécuter, sans se limiter à savoir si elles sont du même thread ou non : tant qu'elles sont indépendantes, elles peuvent s’exécuter en parallèle. Et deux instructions de deux threads séparés sont considérées comme indépendantes par défaut. On voit bien le lien entre exécution dans le désordre et SMT ! Les deux se basent sur le fonctionnement de l'unité d'émission et sa capacité à détecter des dépendances. SMT et exécution dans le désordre utilisent des méthodes presque identiques, l'unité d'émission ne subit aucune modification, ou alors seulement des modifications mineures.

La seule contrainte est qu'il faut gérer le cas des mauvaises prédictions de branchement et autres situations qui demandent qu'on vide le pipeline. Dans ce cas, 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.

L'implémentation est bien plus simple si on utilise le renommage de registres. Avec le renommage de registre, chaque registre architectural se voit attribuer un registre physique. 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 n'a pas à vérifier les thread ID pour détecter les instructions de threads différents, elle a juste à vérifier les dépendances entre registres, pas plus. En faisant cela, la logique d'émission est beaucoup plus simple, elle ne change pas du tout avec ou sans SMT.

Sans renommage de registres, il faut cependant trouver d'autres solutions. Et il y en a globalement trois :

La première est d'utiliser des fenêtres d'instruction séparées pour chaque thread, ce qui est utile si le processeur n'a pas de renommage de registres.
La seconde utilise une file/fenêtre d'instruction unique, mais qu'on découpe en plusieurs morceaux, attribués chacun à un thread. Là encore, le partitionnement peut être statique ou dynamique.
Une autre solution est d'utiliser une file/fenêtre d'instruction normale, mais d'utiliser les thread ID pour détecter les instructions de threads différents, qui sont indépendantes.

Le ROB subit lui aussi les mêmes modifications. Pour résumer, le ROB, les files/fenêtres d'instruction et les caches peuvent être partitionnés, séparées par thread, ou tagués avec un thread ID. Le thread ID est facultatif pour les caches si le cache est physiquement tagué.

Le partitionnement peut être statique ou dynamique, comme pour les caches. Le partitionnement statique fait que les ressources ne sont pas utilisées de manière optimale : certains threads un peu gourmands auront une part fixe du pipeline alors qu'ils pourraient avoir plus si l'autre thread est très léger. Mais l'avantage est que la performance est facile à prédire, qu'elle reste stable. Un exemple typique est celui de l'hyperthreading du processeur Pentium 4. Sur ce processeur, tout est partitionné avec un partitionnement statique. Si le processeur n’exécute qu'un seul thread, ce thread a accès à tout le cache, toute la file d'instruction, tout le ROB, etc. Mais en mode deux threads, chacun a accès à la moitié du ROB, de la file d'instruction, et du cache L1, et de la TLB.

Il faut noter que la première solution, à savoir utiliser une file d'instruction par thread, permet une optimisation assez intéressante pour le chargement des instructions. Les files d'instruction des différents threads sont plus ou moins utilisées, elles contiennent des entrées vides. Il y a d'autant plus d'entrées vides si le thread progresse vite. 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.

◄ Retour vers « Architectures multiprocesseurs et multicœurs »

Sommaire du livre

Continuer vers « Les architectures à parallélisme de données » ►