Fonctionnement d'un ordinateur/Les pipelines de longueur fixe et dynamiques

Dans ce chapitre, nous allons étudier en détail tout ce qui a trait aux pipelines de longueur fixe, ainsi que les pipelines dynamiques. Les deux types de pipeline ont leurs propres spécificités, qui méritent qu'on les aborde en détail. Pour rappel, les pipelines les plus simples sont appelés des pipelines de longueur fixe. Par longueur fixe, on veut dire que toutes les instructions prennent le même nombre d'étages, donc le même nombre de cycles d'horloge. De tels pipelines ne correspondent pas aux processeurs modernes, qui ont des pipelines de longueur variable, où certaines instructions prennent plus de cycles que d'autres pour s'exécuter.

Dans ce chapitre, nous allons faire la différence entre deux sous-types de pipeline fixes. Avec le premier type, 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. Le second type de pipeline est les pipelines multicycle, qui supportent des instructions multicycles. Nous allons voir que leur implémentation est assez peu intuitive sur un pipeline fixe. Elle est plus simple à comprendre sur les pipelines de longueur variable.

Les pipelines 1-cycle : le contournement simple (bypass)

L'implémentation d'un pipeline 1-cycle de ce type 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. Nous avons déjà vu deux pipelines de ce type : le pipeline Fetch-Decode-Exec et le pipeline RISC classique à 5 étages sont de ce type.

Sur un pipeline 1-cycle, la plupart des problèmes qu'ont les autres pipelines disparaissent totalement. Il y a bien le cas des branchements à résoudre, mais l'usage de délai de branchement fait l'affaire vu que leur pipeline est assez court. Les dépendances de données sont aussi presque inexistantes, à l'exception du cas où une instruction a pour opérande le résultat d'une instruction précédente. Le résultat doit être enregistré dans les registres avant de pouvoir être utilisé comme opérande, mais cette écriture a lieu à la fin du pipeline, quelques cycles après son exécution. Il y a un délai de quelques cycles entre le moment où le résultat est calculé et enregistré. Ainsi, si deux instructions consécutives ont une dépendance de ce type, la seconde lira le registre opérande alors que le résultat n'a pas encore été enregistré dedans.

Pour éviter ce genre de problèmes, on a deux grandes solutions. La première solution est de retarder l'exécution de la seconde instruction tant que la première n'a pas enregistré son résultat dans les registres. Et pour cela, on doit émettre des bulles de pipeline autant de cycles qu'il le faut. L'autre solution fait en sorte que le résultat d'une instruction soit disponible rapidement, qu'il soit utilisable directement dans le pipeline, avant son enregistrement dans les registres. Avec la technique du contournement (bypass), le résultat est utilisable dès qu'il est calculé, avant d'être enregistré dans les registres.

Dans ce qui va suivre, on part du principe que toutes les instructions s'exécutent en un seul cycle d'horloge. De plus, il n'y a qu'une seule unité de calcul, combinée avec une unité d'accès mémoire. La raison est que les instructions multicycles compliquent la mise en place du contournement. Il en est de même avec la présence de plusieurs unités de calcul.

Le contournement de l'unité de calcul

La technique du contournement la plus simple implique uniquement l'unité de calcul. Elle permet à un résultat en sortie de l'unité de calcul d'être réutilisé immédiatement en entrée.

Pour cela, on connecte la sortie de l'unité de calcul sur son entrée si besoin, et on la déconnecte sinon. La connexion/déconnexion se fait avec des multiplexeurs.

Pour détecter les dépendances, il faut comparer le registre destination avec le registre source en entrée : si ce registre est identique, on devra faire commuter le multiplexeur pour relier la sortie de l'unité de calcul.

Implémentation complète du contournement

Le contournement de l'unité d'accès mémoire

La technique précédente gère les instructions de calcul uniquement, à savoir le cas où le résultat d'une instruction de calcul est utilisé comme opérande par une instruction suivante. Mais on peut gérer le cas où l'opérande est lu en mémoire. Une telle situation survient quand une instruction mémoire lit une donnée qui sert d'opérande à une instruction arithmétique. Elle survient aussi sur les architectures CISC, pour gérer les instructions de type load-op, qui fusionnent une lecture et une opération en une seule instruction (le pipeline de tels processeurs est assez compliqué).

Gérer une telle situation demande de rajouter une interconnexion qui part de l'unité d'accès mémoire et se connecte sur l'entrée de l'ALU. Le tout est très similaire au contournement de l'unité de calcul et demande juste d'ajouter une entrée sur le multiplexeur, sur laquelle on relie la sortie de l'unité de lecture/mémoire.

Implémentation du contournement de l'unité mémoire

La seule complexité est de commander le multiplexeur. Pour cela, on rajoute un second comparateur, qui compare le registre opérande avec le registre de destination fournit par l'unité mémoire. Il y a donc au total deux comparateurs, dont les résultats sont combinés pour commander le multiplexeur. Les comparateurs et le circuit de combinaison sont souvent regroupés dans un seul circuit appelé le l'unité de contournement. D'autres processeurs ont des unités de contournement plus élaborée, mais dont le principe est le même : comparer les registres destination et opérande, en déduire de quoi configurer les multiplexeurs.

Mais ce qui vient d'être dit marche uniquement si on a une unité mémoire qui fonctionne en parallèle de l'unité de calcul. Sur le pipeline RISC classique, l'unité de calcul et l'unité mémoire sont placées en série, et les choses sont plus compliquées. En effet, il y a deux cycles de différence entre l'entrée de l'unité de calcul et la sortie de l'unité mémoire. La conséquence est que la donnée lue est disponible deux cycles après l'entrée dans l'ALU, alors que l'instruction de calcul démarre un cycle après l'instruction d'accès mémoire. Il y a un cycle de différence qui fait que le résultat est connu un cycle trop tôt.

La solution est de retarder le résultat d'un cycle d'horloge en insérant une bulle de pipeline avant de démarrer l'instruction de calcul. En clair, on économise un cycle au lieu de deux.

La commande du multiplexeur devient aussi plus compliquée. On retrouve les comparateurs entre registres destination et source, mais le délai fait que des subtilités se font jour.

Les pipeline fixes multicycle : plusieurs ALUs et des registres d'échelonnage

Sur un processeur non pipeliné, certaines instructions peuvent prendre 1 cycle, d'autres 7 cycles, d'autres 9, d'autres 25, etc. Le cas typique est celui de la multiplication ou de la division, ou de toute opération complexe. Les instructions qui mettent plus d'un cycle pour s’exécuter s’appellent des instructions multicycle. Il est possible d'implémenter des instructions multicycle sur les pipeline de longueur fixe, en rusant un peu. Le résultat est un pipeline multicycle, sur lesquels les instructions s'exécutent en plusieurs cycles d'horloge.

Les pipeline multicycle incorporent plusieurs unités de calcul séparées, avec des unités de calcul distinctes pour la multiplication et la division. Il est aussi possible d'ajouter de nombreuses unités de calcul en un cycle, comme pour les décalages et les rotations. Et la présence de plusieurs unités de calcul pose quelques problèmes. De plus, gérer des instructions multicycle pose de nombreux problèmes qu'il faut résoudre.

Retarder les écritures : les registres d'échelonnage

Sur de tels processeurs, toutes les instructions ont le même nombre d'étages. On doit se caler sur l'instruction la plus lente pour implémenter les opérations multicycle. Par exemple, si j'ai une addition en un cycle, et une multiplication en 3 cycles, on doit faire en sorte que les deux fassent trois cycles. Si on ne fait pas ça, on obtient un pipeline de longueur variable, avec leurs problèmes, leurs spécificités, et tout ce qui fera l'objet du chapitre suivant.

Pour ce faire, il faut retarder l'écriture dans les registres du résultat de l'instruction. Par exemple, prenons un pipeline où toutes les opérations doivent faire 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 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 registre 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é.

Le contournement est plus complexe avec des instructions multicycles

L'usage d'instructions multicycles complexifie grandement d'implémentation du contournement. Et il y a plusieurs raisons à cela. La première est la présence de plusieurs unités de calcul, qui complexifie les interconnexions. La seconde est l'usage des registres d'échelonnage, qui doivent être pris en compte pour le contournement. Troisièmement, la durée des instructions est à prendre en compte pour effectuer un contournement convenable.

Le premier problème est la présence de plusieurs unités de calcul. Intuitivement, on se dit qu'il faut envoyer la sortie de chaque ALU sur l'entrée de tous les autres. Le nombre d'interconnexion est alors assez important. Pour N unités de calcul, cela demande 2 * N² interconnexions, implémentées avec 2N multiplexeurs de N entrées chacun. Si c'est faisable pour 2 ou 3 ALUs, la solution est impraticable sur les processeurs modernes, qui ont facilement une dizaine d'unité de calcul. A la place, les interconnexions sont alors simplifiées, au prix d'une petite perte de performance.

L'ensemble des interconnexions pour le contournement s'appelle le réseau de contournement. Il peut être très complexe, proche d'une interconnexion totale (toutes les sorties sur toutes les entrées) ou au contraire réduit au minimum. Concevoir un réseau de contournement demande de vérifier quelles interconnexions possibles sont vraiment utiles. Il est des interconnexions qui sont inutiles, d'autres qui sont utiles dans des cas assez rares, d'autres qui ne sont tout simplement pas nécessaires.

Il est possible de limiter le réseau d'interconnexion pour connecter la sortie d'une ALU sur l'entrée du autre, mais que ce ne soit pas réciproque. Par exemple, il est fréquent que les unités de calcul d'adresse utilisent des opérandes calculées par les ALU entières. En conséquence, il faut relier les sorties des ALU entières aux unités de calcul d'adresse. Cela fait des interconnexions nécessaires, qui ont un impact important pour les performances. Mais les connexions inverses, de l'ALU de calcul d'adresse vers l'ALU entière, ne servent pas à grand chose. La connexion AGU-ALU se fait dans un sens seulement. Dans le même genre, la sortie de l'unité mémoire est reliée aux entrées de toutes les autres unités de calcul, pas le choix.

Dans le meilleur des cas, il n'y a pas besoin de connecter certaines ALU. Un exemple assez typique est celui d'un processeur avec une unité de calcul entière et une unité de calcul flottante. En théorie, on devrait envoyer les résultats flottants à l'ALU entière et les résultats entiers à la FPU. Mais dans les faits, cela ne servirait pas à grand chose. Il est rare que les instructions entières et flottantes échangent des données. Et si elles le font, elles peuvent passer par des copies registres, des registres flottants vers entiers et inversement. Aussi, le contournement entre ALU entière et FPU n'est presque jamais implémenté.

Le second problème est que le contournement ne doit pas uniquement relier la sortie de l'ALU, mais doit aussi tenir compte des registres d'échelonnage. En effet, imaginez qu'une instruction ait pour opérande le résultat d'une instruction exécutée deux cycles plus tôt. Il y a un délai de deux cycles entre les deux, mais l'ALU a fournit un résultat en un cycle d'horloge. Où est le résultat voulu ? Il n'est pas en sortie de l'ALU, mais dans le registre d'échelonnage juste après. Le contournement doit donc relier les registres d'échelonnage aux entrées des unités de calcul.

Vu que les registres sont regroupés dans un banc de registre à part, les opérandes peuvent donc provenir de trois sources :des registres architecturaux, des registres d'échelonnage, du contournement direct (de la sortie aux entrées des ALUs). Toute la difficulté est de lire le bon registre d'échelonnage, ce qui demande de faire le lien entre registre architectural et registre d'échelonnage. Mais faire ainsi nous emmènerait assez loin. L'usage de contournement de ce genre est potentiellement équivalent à une forme de renommage de registre ! Dans les faits, disons juste qu'il n'est pas souvent implémenté. A la place, le processeur détecte ce genre de dépendance entre instruction au décodage et insère des bulles de pipeline si besoin.

Les pipelines dynamiques : l'apparition des dépendances WAW

Les pipelines précédents sont des pipelines de longueur fixes, où toutes les instructions s’exécutent en un nombre fixe de cycles, sauf les accès mémoire qui sont traités à part. Sur ces pipelines, 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. Mais idéalement, on souhaiterait que l'addition ne prennent qu'un seul cycle, quitte à enregistrer son résultat dans les registres en avance.

Et c'est là qu'interviennent les pipelines de longueur variable, où certaines instructions prennent plus de cycles que d'autres. Un autre terme, peu utilisé, est celui de pipeline dynamique, terme plus court qu'il nous arrivera d'utiliser. L'implémentation d'un pipeline dynamique est similaire à celle d'un pipeline de longueur fixe, à une différence près : les registres d'échelonnement sont enlevés. Le réseau de contournement est alors simplifié, et on économise pas mal de circuits, sur le principe. Par contre, l'absence des registres d’échelonnement entraine l'apparition de plusieurs problèmes assez sérieux.

Les dépendances structurelles à l'écriture

Les instructions multicycle lisent et écrivent dans le même banc de registres que les instructions 1-cycle. Le résultat est qu'elles peuvent lire ou écrire dans les registres en même temps. Par exemple, imaginons que l'on charge dans le pipeline une instruction de 6 cycles, suivie au cycle suivant par une 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.

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 est d'ajouter d'autres ports d'écriture sur le banc de registres. Dans ce cas, 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 assez simple à implémenter, comme on le verra plus tard. Son cout en transistor est limité, tout est concentré dans l'unité de décodage/émission. Pour la seconde solution, son défaut est que le 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 qui va de limité avec peu d'unité de calcul, à plus important avec beaucoup d'unités de calcul. La solution est surtout utilisée sur les processeurs avec beaucoup d'unités de calcul.

L'inversion de l'ordre de certaines é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 où une instruction multicycle de 6 cycles, est suivie par une instruction s’exécutant en un seul cycle. Le résultat est illustré ci-dessous : l'ordre d'enregistrement des résultats des instructions s'est inversé.

Ce genre de situation ne pose pas de problème, à une condition : si les deux écritures se font dans des registres différents. Si les deux écritures se font dans le même registre, alors il y a un problème : le résultat est incorrect, un registre a été écrasé avec une valeur incorrecte. Le problème en question correspond à l'apparition de dépendance de donnée de type WAW. Les dépendances WAW imposent un ordre concernant les écritures dans les registres. Et sur les pipelines dynamiques, si on ne fait rien, l'ordre des écritures change.

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

Les premiers processeurs MIPS avaient une technique très particulière pour éliminer les dépendances WAW. Ils utilisaient un pipeline RISC classique modifié pour supporter des instructions multicycles, à 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 multicycles 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. Mais les processeurs dynamiques n'utilisent généralement pas cette solution.

Mais au-delà de cette solution assez ingénieuse, le cas général est géré autrement. Pour conserver l'ordre des écritures, il n'y a pas 36 solutions : il faut utiliser des bulles de pipeline. Dans le cas précédent, si une instruction risque d'écrire avant la première, et que les deux écritures se font dans le même registre, alors la seconde instruction doit être retardée. Pour cela, l'unité d'émission émet des bulles de pipeline tant que la dépendance risque de poser problème.

Il est intéressant de comparer les pipelines dynamiques et les pipelines multicycles. Les deux ont des instructions multicycles, mais gèrent les dépendances WAW différemment. Les pipelines dynamique et multicycles utilisent deux méthodes opposées pour conserver l'ordre des écritures. Les pipelines dynamiques retardent l'émission des instructions problématiques, ils maintiennent les instructions avec une dépendance WAW dans l'unité d'émission. Mais les pipelines multicyles ne retardent pas l'émission, mais seulement l'écriture dans les registres. L'instruction est émise dès que possible, mais l'écriture dans les registres est retardée par des registres d'échelonnement.

Nous verrons dans le prochain chapitre qu'il existe des techniques pour conserver l'ordre normal des écritures, sans pour autant retarder l'émission. Les pipelines dynamiques de ce type utilisent une structure matérielle similaire aux registres d'échelonnement, qui remet les écritures dans l'ordre. Nous verrons cela dans le chapitre sur les exceptions précises.

La fréquence des avals des pipelines multicycle et dynamiques

Dans le chapitre précédent, j'ai fait la différence entre un pipeline simple et les pipelines complexes. La différence entre les deux est que les pipeline complexes sont coupés en deux sections : un amont contenant l'unité de chargement et le décodeur d'instruction, suivi par plusieurs avals. Un aval est soit une unité de calcul, soit l'unité d'accès mémoire. Les processeurs avec un pipeline multicycle ou dynamique sont des pipelines complexes.

L'usage d'un pipeline complexe permet de nombreuses optimisations, notamment pour ce qui est de la gestion du signal d'horloge. 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.

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 autre que le Pentium 4 utilisent cette technique, mais nous en reparlerons quand nous serons au chapitre sur les processeurs SIMD.

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

◄ Retour vers « Le pipeline »

Sommaire du livre

Continuer vers « Les exceptions précises et branchements » ►