Fonctionnement d'un ordinateur/Les pipelines multicycles

Dans le chapitre précédent, nous avons des exemples de pipelines très simples, comme le pipeline Fetch-Decode-Exec ou le pipeline RISC classique à 5 étages. Sur de tels pipelines, toutes les instructions s'exécutent en un cycle d'horloge, pas un de plus, pas un de moins. Et ce, que ce soit les accès mémoire, les calculs arithmétiques dans l'ALU, les calculs dans l'unité de branchements, ou toute autre opération. Nous appellerons ces pipelines les pipelines 1-cycle. L'implémentation d'un pipeline 1-cycle est très simple : il suffit d'ajouter des registres au bon endroit, de gérer la propagation des signaux de commande, et de faire quelques autres modifications mineures.

Mais dans les faits, les processeurs de ce type sont très rares. La quasi-totalité des processeurs modernes comme anciens supportent des instructions multi-cycle, à savoir des instructions qui mettent plusieurs cycles à s'exécuter. Un exemple typique est celui des opérations flottantes ou des multiplications. Il y a des instructions multi-cycles dont le nombre de cycles varie suivant l'instruction : les instructions d'accès mémoire sont dans ce cas. Et gérer de telles instructions avec un pipeline pose de nombreux problèmes d'implémentation. Les instructions multi-cycles ne semblent pas vraiment coller avec un pipeline, qui a une longueur fixe. On s'attend à ce qu'il ait un nombre fixe d'étages, qui font chacun un cycle d’horloge.

Les pipelines multicycles sont souvent appelés des pipelines dynamiques, nous utiliserons les deux termes dans ce cours.

Dans ce chapitre, nous allons voir comment modifier un processeur à pipeline, pour qu'il gère des instructions multi-cycles. La modification donne un pipeline multi-cycle, terme qui indique que le pipeline est modifier pour supporter des instructions multi-cycles. Avec un pipeline multicycle, certaines instructions peuvent prendre 1 cycle, d'autres 7 cycles, d'autres 9, d'autres 25, etc. Les instructions rapides prennent moins de cycles que les autres. L'implémentation d'un pipeline multicycle est assez simple : il y a juste besoin d'utiliser des unités de calcul dédiées pour les instructions lentes, avec par exemple un circuit multiplieur séparé d'une ALU entière. Le temps de calcul dépend de l'ALU, et donc le nombre de cycles de l'instruction associée.

Les pipelines multi-cycles séparent front-end et back-end

Avec un pipeline multicycle, le processeur est décomposé en deux parties. La première partie, l’amont (front end), prend en charge les étages communs à toutes les instructions. Il correspond au séquenceur et à l'unité de chargement et regroupe la mise à jour du program counter, le chargement, l'étage de décodage, etc. L'amont est suivi par le chemin de données, qui est organisée en plusieurs voies, chacune formant ce qu'on appelle un aval (back end), ou encore une voie. Un aval correspond soit à une unité de calcul, soit à l'unité mémoire, soit à une unité pour les branchements. Toutes les voies partagent le banc de registre, que ce soit pour lire les opérandes ou enregistrer un résultat.

La spécialisation des avals

La quasi-totalité des processeurs modernes dispose d'une voie séparée pour les accès mémoire, une unité mémoire dédiée. L'unité mémoire est séparée pour une bonne raison : les accès mémoire se marient assez mal avec un pipeline. Les accès mémoire ont une latence élevée, variable. Ils sont difficiles à pipeliner de manière générale. La voie pour les accès mémoire sert donc d'exception, c'est une unité qui n'est pas tout à fait pipelinée, alors que le reste du chemin de données l'est. Sa connexion avec le pipeline varie grandement suivant le processeur.

Si on omet les voies liées aux accès mémoire, les autres voies correspondent peu ou prou à une unité de calcul. Par exemple, il est fréquent d'avoir des voies séparés pour l'addition, la multiplication et les décalages (barrel shifter), vu que ces opérations sont dans des ALU entières séparées. De même, on a une voie séparée pour les instructions flottantes, lié au fait que la FPU est une unité de calcul séparée.

La destination de chaque voie peut varier. Les instructions de calcul ou les lectures enregistrent un résultat dans les registres, et se terminent donc sur le port d'écriture du banc de registres. Par contre, les voies pour les branchements ou les écritures n'enregistrent rien dans les registres. La voie pour les branchements se termine dans le séquenceur et/ou dans le registre d'état, la voie pour les écritures ne finit nulle part si ce n'est dans l'unité mémoire.

Plus tard dans la suite du cours, nous verrons que les processeurs modernes regroupent plusieurs ALUs par voie, pour des raisons assez compliquées à expliquer ici. Retenez juste que le chemin de données est composé de plusieurs voies relativement indépendantes, chacune spécialisée dans un type de micro-opération spécialisé. Les voies commencent toutes avec la lecture des opérandes, elles effectuent un calcul, puis enregistrent leurs résultats dans les registres si besoin.

Les processeurs à émission simple et multiple

Toujours est-il que le décodeur envoie des instructions décodées dans la voie appropriée. Par exemple, une instruction d'accès mémoire va dans l'unité mémoire, dans la voie spécialisée dans les accès mémoire. Une instruction de calcul va dans la voie spécialisée dans les calculs entiers simples, à savoir l'ALU entière. Et ainsi de suite. L'envoi d'une instruction/micro-opération dans une voie s'appelle l'émission. On dit qu'une instruction est émise quand elle est envoyée dans une voie.

Sur les processeurs dits à simple émission, une instruction est envoyée dans une voie à chaque cycle, soit dans une ALU, soit dans l'unité mémoire, soit dans les voies pour les branchements, etc. Ils peuvent émettre au maximum une instruction apr cycle d'horloge, ils exécutent en moyenne une instruction par cycle. Diverses optimisations comme le renommage de registres et l'exécution dans le désordre permettent de se rapprocher de ce rythme de croisière d'une instruction lancée par cycle.

Mais il existe des processeurs à émission multiple qui sont capables d'émettre plusieurs instructions à la fois, chacune dans des voies séparées. Les processeurs dits superscalaires sont dans ce cas, mais ils ne sont pas les seuls. Ils permettent de gagner en performance en utilisant au maximum les unités de calcul/voies. Si plusieurs unités de calcul sont inoccupées, un processeur à émission multiple pourra lancer une instruction dans chacune d'entre elles en même temps, ce qui permet de les occuper le plus vite possible. De moins, c'est le cas si les conditions adéquates sont réunies, mais laissons cela pour plus tard. Un chapitre entier sera dédié aux processeurs à émission multiple.

Les dépendances structurelles : l'occupation de chaque voie

Les pipelines multi-cycles doivent gérer des dépendances structurelles, à savoir le cas où deux instructions veulent utiliser le même circuit en même temps. Les dépendances structurelles sont généralement assez rares, car les pipelines prennent bien garde à bien séparer les étages du pipeline, en dupliquant des circuits s'il le faut. Par exemple, séparer le cache en un cache d'instruction et un cache de donnée élimine une dépendance structurelle. Mais sur les pipeline multi-cycles, c'est une autre histoire. Mais pour comprendre pourquoi, il faut voir quelles sont les sources de ces dépendances. Pour résumer, elles se situent au niveau des unités de calcul et du banc de registre.

Les dépendances structurelles liées aux unités de calcul

En théorie, une fois qu'une instruction est décodée, elle est envoyée dans la voie adaptée. Du moins, si cette voie est libre. En effet, l'usage d'instructions multicycles fait qu'une voie peut être occupée pendant plusieurs cycles. Un exemple est celui où on veut faire deux multiplications à la suite, en supposant qu'une multiplication fasse 5 cycles : la seconde doit attendre que la première se termine car le multiplieur est occupé pendant ce temps. Et en général, des instructions consécutives ne peuvent pas utiliser la même voie, la même ALU. La voie sera occupée par la première instruction, les autres devront attendre que la première ait terminé ses calculs.

En théorie, il est possible d'éliminer totalement ces dépendances structurelles. Une solution simple duplique l'unité de calcul fautive. Prenons un exemple où c'est le circuit multiplieur qui est fautif, où la multiplication prend cinq cycles sur le processeur. Avec une seule ALU, on doit attendre qu'une multiplication en cours soit terminée avant de lancer la suivante. Mais il est possible de lancer une nouvelle multiplication à chaque cycle si on dispose de 5 circuits multiplieurs : on lance une nouvelle multiplication à chaque cycle dans un multiplier différent. Mais le cout en transistors est prohibitif, surtout que le gain en performance est généralement faible. Il est en effet rare que 5 multiplications soient lancées à la suite dans le pipeline, ce qui fait que si on utilisait 5 multiplieurs, ils seraient sous-utilisés en pratique.

La seconde solution pipeline, échelonner les unités de calcul. Si jamais vous avez une opération qui prend cinq cycles, pourquoi ne pas lui fournir un seul circuit échelonné en cinq étages ? Pour certains circuits, c'est possible : on peut totalement échelonner une unité de multiplication, par exemple. En faisant ainsi, il est possible de démarrer une nouvelle multiplication à chaque cycle d'horloge dans la même ALU, éliminant ainsi toute dépendance structurelle.

Dans la réalité, les statistiques montrent qu'il est rare que deux instructions multicycles se suivent dans un programme. La seule exception étant les instructions mémoire, mais nous les mettons à part pour le moment. En conséquence, les dépendances structurelles ont un cout en performance assez mineur. Échelonner un circuit permet un gain de performance pour un cout en circuit modéré : il suffit d'ajouter quelques registres dans le circuit. Le problème est que certaines instructions s’échelonnent mal, notamment les divisions. Aussi, de nombreux concepteurs de processeurs laissent quelques dépendances structurelles. Nous verrons comment elles sont gérées au chapitre suivant.

Les dépendances structurelles à l'écriture dans le banc de registre

Les instructions multi-cycle lisent et écrivent dans le même banc de registres que les instructions 1-cycle. Le résultat est qu'elles peuvent écrire dans les registres en même temps. Par exemple, imaginons que l'on exécute une multiplication de 6 cycles, suivie au cycle suivant par une opération qui n'en prend que 5. Elles tenteront d'enregistrer leurs données en même temps 6 cycles après pour la première, 1 + 5 cycles pour l'autre. Elles voudront donc enregistre une donnée en même temps. Mais le banc de registre n'a qu'un seul port d'écriture...

La solution la plus simple est que la seconde instruction doit être retardée d'un cycle pour résoudre le problème. En soi, rien de problématique à gérer, l'unité de décodage a juste à insérer des bulles de pipeline. Une autre solution ajoute des ports d'écriture sur le banc de registres, afin que les deux instructions peuvent écrire en même temps dans le banc de registre. Il faut juste qu'elles écrivent dans des registres différents, mais il s'agit d'un cas de dépendance de données, pas une dépendance structurelle proprement dit.

La première solution a un cout en performance, mais est simple à implémenter. Son cout en transistor est limité, tout est concentré dans l'unité de décodage/émission. Pour la seconde solution, son cout en transistor est important, sans compter que le banc de registre devient alors plus gourmand en énergie. Le tout est à comparer à un gain en performance généralement limité. La solution est surtout utilisée sur les processeurs avec beaucoup d'unités de calcul.

Les premiers processeurs MIPS avaient une technique très particulière pour éliminer les dépendances structurelles de ce genre, qui éliminait aussi partiellement les dépendances WAW. Ils utilisaient un pipeline RISC classique modifié pour supporter des instructions multi-cycles, à savoir des multiplications et éventuellement les divisions. Ils ajoutaient un aval séparé, un simple circuit multiplieur/diviseur séparé de l'ALU entière. Les instructions multi-cycles disposaient de leur propre set de registres rien que pour elles, ce qui résolvait pas mal de problèmes de conflits d'accès aux registres.

L'inversion de l'ordre des écritures

Un problème des pipelines dynamiques est qu'ils ne garantissent pas l'ordre des écritures. Si on émet des instructions dans l'ordre du programme, il se peut qu'elles ne terminent pas dans le même ordre. Par exemple, prenons l'exemple d'une multiplication prenant 6 cycles, suivie par une addition s’exécutant en un cycle. Le résultat est illustré ci-dessous : l'ordre d'enregistrement des résultats des instructions s'est inversé. Les instructions sont émises une par une, dans l'ordre, mais l'enregistrement des résultats dans les registres se font dans le désordre si elles n'ont pas de dépendances entre elles. On dit qu'il y a inversion de l'ordre des écritures.

Exemple de problème survenant avec des pipeline de longueur variable

L'inversion de l'ordre des écritures pose problème pour supporter les exceptions précises. Il est possible qu'une instruction lève une exception alors qu'une instruction suivante a déjà enregistré son résultat. Imaginez par exemple qu'une multiplication soit suivie par une addition. Imaginez que la multiplication lève une exception matérielle du type "débordement d'entier", 3 cycles après avoir démarré. L'addition aura déjà enregistré son résultat, vu qu'elle se fait en un seul cycle...

Au-delà des problèmes liés aux exceptions précises, les dépendances de données posent aussi problème. Si deux écritures se font dans des registres différents, peu importe l'ordre des écritures, tout se passera bien. Mais si les deux écritures se font dans le même registre, il y a un problème : le résultat est incorrect, un registre a été écrasé avec une valeur antérieure. Le problème en question correspond à l'apparition de dépendances de donnée de type WAW. Les dépendances WAW imposent un ordre concernant les écritures dans les registres et posent des problèmes sur les pipelines dynamiques, uniquement eux.

Les registres d'échelonnage

Pour conserver l'ordre des écritures, la solution la plus simple est de retarder les écritures jusqu'à ce qu'elles atteignent la toute fin du pipeline. Ainsi, il n'y a pas d'inversion d'ordre des écritures dans les registres, ni d'écritures simultanées. L'implémentation est plus simple si on suppose que toutes les instructions font le même nombre de cycles. On parle alors d'un pipeline de longueur fixe. Le cout à payer est que les instructions doivent se caler sur l'instruction la plus lente. Si une addition met un cycle à s'exécuter et une multiplication 3, alors toutes les instructions font 3 cycles.

Si l'addition fournit son résultat en un cycle, il sera enregistré dans les registres avec un retard de deux cycles. Idem pour les lectures mémoire : si un accès mémoire fait 2 cycles, l'écriture de la donnée lue dans les registres sera retardée d'un cycle. Le retard dépend de l’opération à effectuer, en fonction de combien de cycles elle prend dans l'ALU. En clair, toutes les instructions ont le même nombre d'étages, mais certains étages sont inutiles pour certaines instructions. L'instruction doit passer par ces étages, mais ceux-ci ne doivent rien faire.

Reste à ajouter des cycles de retard, qui servent juste à retarder l'enregistrement dans les registres. Pour cela, on insère des registres entre la sortie de l'ALu et le banc de registre. Les registres en question sont appelés des staggering registers, ou encore des registres d'échelonnage. Il y a autant de registres d'échelonnage que cycles de retard à ajouter, car chacun retarde le résultat d'un cycle d’horloge. Pendant les cycles de retard, le résultat sera passé d'un registre d'échelonnage à l'autre, sans que rien ne se passe.

Un défaut de la méthode précédente est que les données sont copiées d'un registre à l'autre à chaque cycle d'horloge, ce qui consomme de l'énergie pour rien. Pour éviter cela, les processeurs modernes regroupent les registres d'échelonnage dans un banc de registre séparé, appelé le banc de registres d'échelonnage. Lors du décodage de l'instruction, un registre est attribué à l'instruction pour mémoriser son résultat, si besoin. Le résultat est enregistré dans le registre alloué en sortant de l'unité de calcul. Puis, il est copié dans le banc de registre architectural dès que le délai nécessaire est écoulé.

Il faut rappeler que pour les écritures en RAM, le processeur utilise une file d'écriture pour garantir que les écritures se font dans l'ordre. Nous en avions parlé dans le chapitre sur le pipeline, quand nous avions parlé des exceptions précises. On peut la voir comme une sorte d'équivalent des registres d'échelonnage, mais pour les écritures en mémoire. La file d'écriture est séparée des registres d'échelonnage, pour une raison simple : elle ne communique pas avec les registres, mais avec le cache. Sa sortie étant différente, elle est donc séparée.

Le tampon de réordonnancement

Le tampon de réordonnancement est la technique phare utilisée pour remettre les écritures dans l'ordre. L'idée est là encore de remettre les écritures dans l'ordre. Les micro-opérations fournissent leurs résultats dans le désordre, mais les résultats sont mis en attente, afin que les écritures se fassent dans l'ordre. La mise en attente se fait dans une mémoire appelée le tampon de ré-ordonnancement, Re-order buffer en anglais, ce qui fait que j'utiliserais parfois l'abréviation ROB dans ce qui suit.

La différence avec les registres d’échelonnement est que la mise en attente est plus flexible, elle ne demande pas que toutes les instructions prennent le même nombre de cycles pour s'exécuter. Une instruction peut enregistrer son résultat dès que les précédentes sont terminées, au cycle précis où elles ont toutes enregistrées leurs résultats. Dit autrement, seule l'instruction la plus ancienne peut quitter le ROB et enregistrer son résultat, les autres instructions doivent attendre. De ce point de vue, le tampon de réordonnancent est donc une mémoire FIFO. On peut la voir comme une amélioration de la technique précédente, où les registres d’échelonnement sont remplacés par une structure matérielle plus complexe.

Les résultats sont enregistrés dans le désordre dans le ROB, mais finissent triés par l'ordre du programme. L'ordre d'écriture demande de mémoriser l'ordre d'exécution des instructions. Pour cela, on profite du fait que les instructions sont décodées dans l'ordre. Après les décodeurs se trouve un circuit appelé l'unité d'émission, qu'on détaillera dans le chapitre suivant. Pour simplifier, elle vérifie que l'instruction qu'elle reçoit peut s'exécuter, et l'envoie aux unités de calcul si c'est le cas. L'unité d'émission ajoute l'instruction au ROB quand elle l'envoie au chemin de données. Si le ROB est plein, on ne peut pas y ajouter de nouvelle instruction. En conséquence, le processeur bloque les étages de chargement, décodage, etc. Le processeur est débloqué quand une instruction enregistre ses résultats.

Un processeur avec un tampon de ré-ordonnancement est donc composé de trois sections : un front-end qui regroupe chargement et décodage, un chemin de données (ALU et registres), et un système complémentaire de ré-ordonnancement. Ce dernier est composé du tampon de ré-ordonnancement, de l'unité d'émission et de l'étage de writeback pour l'enregistrement dans les registres. Le ROB envoie toutes les informations nécessaires à l'étage de Writeback, à savoir le registre de destination, l'indicateur d'exception, le résultat à enregistrer, etc.

Les résultats sont enregistrés dans le ROB dans le désordre. Cependant, le ROB fait le lien entre un résultat et l'instruction qui l'a produite, il associe une instruction avec son résultat. Expliquer comment est fait ce lien demande d'expliquer comment est implémenté le ROB. Pour simplifier, c'est un subtil mélange entre une mémoire cache et une mémoire FIFO. Le ROB est composé d'entrées, chacune contient de quoi faire le lien entre un résultat et l'instruction associée.

Une entrée contient le program counter associé à l'instruction, le registre de destination du résultat, un champ pour mémoriser le résultat, et un bit de présence. Ce dernier indique si le résultat a bien été calculé. Le champ résultat est initialement laissé vide, mais le résultat de l'instruction est copié dedans une fois qu'il est disponible. Notons que certaines instructions ne renvoient pas de résultat, comme les branchements ou les écritures en mémoire, mais on leur alloue quand même une entrée dans le ROB. Pour cela, le bit de présence est couplé à un bit qui indique si l'instruction doit fournir un résultat ou non. Les deux sont regroupés sous le noms de bits de présence. Si le processeur gère des exceptions précises, il faut ajouter un champ pour l'indicateur d'exception, qui est utilisé pour gérer des exceptions précises.

Une entrée du ROB
Program counter	Registre de destination	Champ résultat	Bits de présence	Champ exception

Lorsqu'une instruction est émise, elle réserve une entrée du ROB, pour que son résultat soit ajouté dedans ultérieurement. L'émission se faisant dans l'ordre, les entrées du ROB sont allouées dans l'ordre. Le ROB est donc une sorte de mémoire FIFO du point de vue des instructions. Une instruction réserve une entrée du ROB en écrivant son Program counter dedans, et en remplissant le champ pour le registre de destination. Le champ

Par la suite, les différents résultats vont être enregistrés dans les entrées adéquates, dans l'entrée réservée par l'instruction. Pour faire le lien entre un résultat et une instruction, le ROB fonctionne comme un cache d'instruction dont le tag serait le program counter. Le program counter est propagé dans le pipeline, d'étage en étage, ce qui fait que le résultat sortira de l'unité de calcul en étant associé à ce program counter. Le program counter est alors utilisé pour accéder au ROB comme on le ferait avec un cache d'instruction. L'entrée qui déclenche un succès de cache est alors sélectionnée : le résultat est copié dedans.

Une fois que toutes les instructions précédentes sont terminées, l'instruction peut enregistrer son résultat dans les registres. instruction quitte alors le ROB, dans le sens où l'entrée est vidée. Le résultat à enregistrer est lu depuis le champ résultat, le registre de destination est lu depuis le champ du même nom. L'étage de Writeback vérifie que le résultat est disponible en vérifiant les bits de présence. L'étage de writeback peut aussi vérifier si l'instruction a levé une exception matérielle, en regardant le champ Exception. Si une exception a lieu, cela signifie que les instructions suivantes sont invalides. Le ROB est alors vidé, ce qui le débarrasse des instruction invalides : leurs résultats ne seront pas enregistrés dans les registres architecturaux. Le même mécanisme est utilisé pour gérer les mauvaises prédictions de branchement.

Le tampon d’historique

Une autre solution laisse les instructions écrire dans les registres dans l'ordre qu'elles veulent, mais conserve des informations pour remettre les écritures dans l'ordre, pour retrouver les valeurs antérieures. Ces informations sont stockées dans ce qu'on appelle le tampon d’historique (history buffer ou HB).

Le tampon d'historique est une mémoire LIFO dont chaque mot mémoire est une entrée qui mémorise les informations dédiées à une instruction. Lorsqu'une instruction modifie un registre, le HB sauvegarde une copie de l'ancienne valeur, pour la restaurer en cas d'exception. Pour annuler les modifications faites par des instructions exécutées à tort, on utilise le contenu de l'HB pour remettre les registres à leur ancienne valeur. Plus précisément, on vide le HB dans l'ordre inverse d'ajout des instructions, en allant de la plus récente à la plus ancienne, jusqu'à vider totalement le HB. Une fois le tout terminé, on retrouve bien les registres tels qu'ils étaient avant l’exécution de l'exception.

Le banc de registres futurs

Le ROB et le HB sont deux techniques opposées sur le principe. Le ROB part du principe assez pessimiste que le banc de registre doit conserver un état propre, capable de gérer des exceptions précises. L'état temporaire est alors stocké dans le ROB, afin de pouvoir être annulé en cas de souci. La récupération en cas d'exception/branchement est alors assez rapide, mais le cout d'implémentation est assez important. Le HB fait l'inverse, avec une technique optimiste. Le HB enregistre directement l'état temporaire dans le banc de registre, mais mémorise de quoi revenir en arrière. Avec un HB, remettre les registres à l'état normal prend du temps. Deux techniques assez opposées, donc.

Il existe une solution intermédiaire, qui consiste à utiliser à la fois un ROB et un HB. La technique utilise deux bancs de registres. Le premier est mis à jour comme si les exceptions n’existaient pas, et conserve un état spéculatif : c'est le banc de registres futurs (future file ou FF). Il fonctionne plus ou moins comme l'History Buffer de la section précédente. L'autre stocke les données valides en cas d'exception : c'est le banc de registres de retrait (retirement register file ou RRF). Il fonctionne sur le même principe que le banc de registre avec un ROB. Il est d'ailleurs couplé à un ROB, histoire de conserver un état valide en cas d'exception. Mais ce ROB est simplifié, comme on va le voir dans ce qui suit.

Le FF est systématiquement utilisé pour l'exécution des instructions. Dès qu'on doit exécuter des instructions, c'est dans ce banc de registre que sont lues les opérandes. La raison est que ce banc de registre contient les dernières données calculées. Notons que dans la technique utilisant seulement un ROB, les opérandes auraient été lues depuis le ROB. Mais là, le ROB n'est plus connecté aux entrées de l'ALU, seul le FF l'est. Le câblage est donc plus simple et l'implémentation facilitée. Le RRF est quant à lui utilisé en cas d'exception ou de branchement, pour récupérer l'état correct.

Après une exception ou un branchement, deux méthodes sont possibles. Avec la première, les opérandes sont lues depuis ce banc de registre, jusqu'à ce que le FF soit de nouveau utilisable. Mais détecter quel banc de registre utiliser est assez compliqué. Elle n'est en pratique pas implémentée, car demandant trop de circuits. L'autre solution est de recopier le contenu du RRF dans le FF. Là encore, le temps de recopie est assez long, sauf si on utilise certaines optimisations des bancs de registre. Il existe en effet des méthodes pour copier un banc de registre entier dans un autre en à peine un ou deux cycles d'horloge. Elles sont assez compliquées et on ne peut pas les expliquer ici simplement.*

Une variante de cette technique a été utilisée sur le processeur Pentium 4. La différence avec la technique présentée est l'usage du renommage de registre, qui permettait de se passer de deux bancs de registres proprement dit. Les deux bancs de registres étaient inclus dans un banc de registre beaucoup plus grand. Mais nous détaillerons cela dans quelques chapitres.

Les point de contrôle de registre

La technique du register checkpointing est une technique qui marche surtout pour les branchements, mais ne gére pas les exceptions précises, du moins pas dans sa version la plus simple. Elle peut être adaptée pour gérer des exceptions précise, mais nous allons simplement voir une version qui gère uniquement les branchements.

Elle consiste à sauvegarder les registres quand un branchement est décodé, pour ensuite restaurer les registres si besoin. Tous les registres architecturaux du processeur sont sauvegardés, et parfois quelques registres microarchitecturaux. En clair, une copie intégrale du banc de registre est réalisée, le registre d'état est lui aussi sauvegardé, etc. La sauvegarde des registres porte le nom de point de contrôle de registre, nous dirons simplement "point de contrôle". Le point de contrôle est stocké dans un autre banc de registre, séparé du banc de registre principal, qui est complétement invisible pour le programmeur.

Un point de contrôle est pris au moment où un branchement est décodé. On ne sait pas si ce branchement sera pris ou non, ce qui fait les instructions qui vont suivre peuvent être correcte si le branchement n'est pas pris, ou incorrectes si le branchement est pris et saute ailleurs dans le programme. Le branchement s'exécute normalement, le banc de registre est modifié par les instructions qui le suivent, tout comme c'est le cas avec un HB. Vers la fin du pipeline, on regarde si le branchement est pris ou non. S'il n'est pas pris, il n'y a rien à faire : les registres contiennent des données valides. Mais si le branchement est pris, alors les registres contiennent des valeurs invalides. Le point de contrôle est restauré, à savoir que le banc de registre est restauré dans le même état qu'un moment du point de sauvegarde.

Il est intéressant de comparer cette technique à la technique du tampon d'historique. Le principe est le même : on laisse les instructions modifier les registres, mais on doit annuler ces modifications en revenant en arrière. Sauf que le tampon d'historique restaure les registres un par un. Alors qu'avec un point de contrôle, la restauration du banc de registre se fait en bloc : on restaure tous les registres d'un seul coup, en un seul cycle. Une autre différence est que le point de contrôle ne s’embarrasse pas à savoir quels registres ont été modifiés à tord ou non, tous les registres sont sauvegardés et restaurés en un ou deux cycles d'horloge. Bien sûr, cela demande des bancs de registre spécialement conçus pour. Tout se passe comme si le tampon d'historique étant remplacé par un second banc de registre, avec une procédure de restauration optimisée se faisant en bloc.

La technique peut aussi être comparée avec la technique du banc de registres futurs, elle-même très liée au tampon d'historique. L'idée est que le point de contrôle est le RRF (banc de registre de retirement), alors que le banc de registre normal est un FF (banc de registre futur). La différence est que le point de contrôle fait qu'on n'a pas besoin de savoir quelles sont les modifications à annuler ou non. Le banc de registre tout entier est restauré, pas seulement les registres modifiés à tord. Une autre différence est qu'avec un banc de registre futur, le RFF est mis à jour à chaque cycle d'horloge, dès qu'une instruction peut enregistrer ses résultats. Le point de contrôle n'est pas mis à jour mais est pris en une fois, en un seul cycle d'horloge, et ne change plus après. En conséquence, il n'y a pas besoin de ROB pour gérer l'état du RRF.

La complétion dans le désordre

Les techniques précédentes remettent dans l'ordre les écritures dans les registres, afin de gérer les branchements et exceptions. Mais elles s'appliquent sur toutes les instructions, même en absence de branchements. Mais diverses optimisations permettent de contourner ces techniques ou de les désactiver dans des conditions bien précises, pour gagner en performance, tout en garantissant que cela n'ait pas de conséquences sur l'exécution du programme. Il s'agit de techniques dites de complétion dans le désordre.

En général, elles s'appliquent en absence de branchements ou quand le processeur sait qu'aucune exception ne peut survenir. La remise en ordre des écritures est alors mise en pause et les écritures se font dans le désordre. Les écritures sont faites en avance, alors que des instructions précédentes ne sont pas terminées. Par valider des écritures en avance, on veut parler de mettre à jour les bancs de registre, qu'il s'agisse du retirement register file, du point de contrôle, ou toute autre structure des techniques précédentes. Rappelons que le scoreboard ou l'unité d'émission s'arrange pour l'exécution dans le désordre ne change pas le comportement du programme exécuté.

Un exemple est celui du processeur ARM Cortex 73, qui dispose d'un tel mécanisme. Il s’applique en absence de branchements et peut être vu comme une amélioration des lectures non-bloquantes. Le mécanisme s'active quand une lecture est bloquée par un défaut de cache ou toute autre situation. Le processeur implémente l'exécution dans le désordre, ce qui fait qu'il exécute les instructions qui suivent une lecture bloquée, à condition qu'elles ne dépendent pas de la lecture. L'idée est alors de laisser ces instructions écrire dans le banc de registre, alors que la lecture précédente est encore en attente. Il faut cependant que la lecture soit arrivée à un certain état d'avancement pour que le processeur autorise ces écritures : il faut garantir que la lecture ne déclenchera pas un défaut de page ou toute autre exception matérielle. Mais une fois que le processeur sait que la situation est OK, il autorise les instructions suivant la lecture enregistrer leurs résultats pour de bon.

Le processeur ARM Cortex 73 en question ne dispose apparemment pas de ROB, mais il doit certainement avoir une structure similaire pour garantir l'ordre des écritures quand un branchement est présent. L'avantage de la technique est qu'elle permet à certaines instructions de finir en avance, ce qui libère de la place dans le ROB, le tampon d'historique, ou toute autre structure matérielle qui met en attente les écritures. Elles permet d'avoir de meilleures performances sans augmenter la taille de ces structures, ou bien d'obtenir des performances similaires à cout en circuits réduit. Le CPU ARM Cortex 73 a un budget en transistor assez restreint, ce qui fait que cette optimisation prend tout son sens sur ce CPU.

La fréquence des avals des pipelines multicycle

L'usage d'un pipeline complexe , qui sépare amont et avals, permet de nombreuses optimisations. Par exemple, il est possible de faire fonctionner certains avals à une fréquence supérieure aux autres. Typiquement, on peut faire fonctionner l'unité de calcul flottante à une fréquence inférieure des unités de calcul entières, afin d'économiser un peu d'énergie. Ou encore, certaines ALU peuvent fonctionner à une fréquence double de celle du processeur, afin de gagner en performance. Voyons un petit peu quelles sont ces optimisations.

Le clock gating des avals inutilisés

Afin de réduire la consommation d'énergie du processeur, les avals inutilisés peuvent être désactivés, mis en veille. La technique du clock gating vue dans le chapitre sur la consommation électrique des circuits, coupe le signal d'horloge pour les unités de calcul inutilisées. Mais il est aussi possible de couper l'alimentation, ce qui porte le nom de power gating.

Les processeurs avec un pipeline simple bloquent dès qu'un défaut de cache est rencontré, à savoir qu'ils émettent des bulles de pipeline tant que la RAM n'a pas répondu. Lors d'un défaut de cache, il est possible de désactiver les unités de calcul et les registres en attendant que la RAM réponde. Les registres sont réactivés juste avant que la donnée n'arrive. Les gains sont d'autant plus grands que les accès mémoires sont longs, mais il faut avouer que ce n'est pas l'exemple le plus crédible. Les processeurs modernes disposent d'optimisations, comme les lectures non-bloquantes ou l'exécution dans le désordre, qui permettent d'exécuter des calculs pendant un défaut de cache.

Un autre exemple, bien plus intéressant, se base sur une observation assez intéressante : il est très rare qu'un programme entrelace des instructions flottantes et entières. En conséquence, il est possible de désactiver la FPU et le banc de registres flottants si elles sont inutilisées. Et il est aussi possible de désactiver l'ALU entière et les registres entiers pendant les instructions de calcul flottant. Les instructions flottantes étant assez longues, généralement une dizaine de cycles, voire plus, désactiver l'ALU et les registres entiers permet d'économiser pas mal d'énergie. Et vu qu'une instruction flottante vient rarement seule, l'ALU et les registres entiers sont généralement désactivés pendant une centaine/milliers de cycles d'horloge.

La désactivation des unités inutilisée est commandée par l'unité de contrôle. Une fois qu'elle a décodée l'instruction, elle sait quelles unités sont nécessaires pour exécuter l'instruction et quelles sont celles inutilisées. L'unité de contrôle a juste à envoyer des signaux de commande supplémentaires aux circuits de clock gating. Les gains peuvent être substantiels. Par exemple, pour le processeur Power 5, IBM a déclaré que le clock gating lui permettait d'économiser 25% d'énergie.

Les unités de calcul à double fréquence : le cas particulier de l'ALU entière du Pentium 4

Le Pentium 4 était un peu particulier dans son genre, avec une ALU à mi-chemin entre une ALU normale et une ALU bit-slicée. Il disposait de plusieurs unités de calcul sur les nombres entiers, dont l'une d'entre elle était une ALU simple qui ne gérait que les additions, les soustractions, les opérations logiques et les comparaisons. Les multiplications et décalages étaient gérés par une ALU séparée. Il y avait donc une ALU simple à côté d'une ALU complexe.

L'ALU simple était composée de deux sous-ALU de 16 bits chacune. La première envoyait le bit de retenue qu'elle a calculée à la seconde. Un point important est que l'ALU prenait deux cycles d'horloge pour faire son travail : le premier cycle calculait les 16 bits de poids faible dans la première sous-ALU, puis calculait les 16 bits de poids fort lors du second cycle (il y avait aussi un troisième cycle pour le calcul des drapeaux du registre d'état, mais passons). Le tout est appelé addition étagée (staggered add) dans la documentation Intel.

Et la magie était que l'unité de calcul fonctionnait à une fréquence double de celle du processeur ! Pour faire la différence entre les deux fréquences, nous parlerons de fréquence/cycle processeur et de fréquence/cycle de l'ALU. Le résultat de ce fonctionnement franchement bizarre, est que les 16 bits de poids faible étaient calculés en une moitié de cycle processeur, alors que l'opération complète prenait un cycle. L'utilité devient évidente quand on sait que l'ALU simple était utilisée pour les calculs d'adresse. L'accès à la mémoire cache intégrée au processeur a besoin des bits de poids faible de l'adresse en priorité, les bits de poids fort étant nécessaires plus tard lors de l'accès. Calculer les bits de poids faibles d'une adresse en avance permettait d'accélérer les accès au cache de quelques cycles.

La technique en question porte le nom barbare d'ALU double pumped, dont une traduction naïve ne donne pas un terme français très parlant. L'idéal est de la parler d'ALU à double fréquence. Il peut exister des ALU à triple ou quadruple fréquence, mais ce n'est pas très utilisé. Il faut noter que certains processeurs autres que le Pentium 4 utilisent cette technique, mais nous en reparlerons quand nous serons au chapitre sur les processeurs SIMD.

◄ Retour vers « Les optimisations du chargement des instructions »

Sommaire du livre

Continuer vers « L'émission dans l'ordre des instructions » ►