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.

Pipeline Bypass

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.

Principe du contournement avec le pipeline RISC classique.

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.

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

Implémentation complète du contournement mémoire avec un multiplexeur

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.

Data Forwarding (Two Stage, error)

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.

Data Forwarding (Two Stage)

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.

Processeur à pipeline fixe qui gére des instructions multicycles

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.

Regsitres d'échelonnage

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

Banc de registres d'échelonnage

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 pus 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 sur les pipelines dynamiques

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, il arrive que deux instructions se mettent à faire des écritures au même moment. 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 seule solution 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.

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.

Bulle de pipeline.

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'éhcelonnement, qui remet les écritures dans l'ordre. Nous verrons cela dans le chapitre sur les exceptions précises.