Fonctionnement d'un ordinateur/Les pipelines de longueur fixe

Avec ce qu'on a dit plus dans le chapitre précédent, il semblerait que l'implémentation d'un pipeline soit assez simple. Cependant, nous nous sommes limité à des pipelines simples, appelé 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 à des pipelines de processeurs modernes. Les processeurs modernes ont des instructions qui sont plus longues que d'autres : certaines utilisent l'ALU durant un cycle, d'autres pendant 5 cycles, etc. De même, les accès mémoire ne se font pas en un seul cycle en cas de défaut de cache. Les pipeline de ces processeurs sont appelés des pipelines de longueur variable.

Nous allons étudier en détail les pipelines de longueur fixe dans ce chapitre, car ils sont beaucoup plus simples que ceux de taille variable. De plus, ce qui sera dit dans ce chapitre vaudra aussi pour les pipelines de longueur variable, alors que les pipelines de longueur variable ont des spécificités bien distinctes, qu'il vaut mieux voir à part. Par exemple, il n'y a pas besoin d’exécution dans le désordre ou de renommage de registres avec un pipeline de longueur fixe.

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. L'implémentation d'un pipeline fixe 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.

Mais ils sont assez peu pratiques et n'ont été utilisés que sur certains processeurs RISC rudimentaires. Ils serviront surtout d'outil pédagogique pour introduire certaines notions assez complexes, vu que leur implémentation est très simple. Le second type de pipeline est le reste, à savoir les pipelines qui gèrent des instructions multicycle, qui mettent plusieurs cycles à s'exécuter. Nous allons les appeler pipeline fixes multicycle, ou encore pipeline multicycle. 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)

Sur un pipeline 1-cycle, la plupart des problèmes qu'on les autres pipeline 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. Par contre, une situation bien précise peut poser un problème : deux instructions consécutives, la seconde a pour opérande le résultat de la première. Le résultat doit être enregistré dans les registres avant de pouvoir être utilisé comme opérande d'une instruction, 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 que la seconde instruction ne doit pas s’exécuter tant que la première n'a pas enregistré son résultat dans les registres. Et pour cela, on doit retarder la seconde avec des bulles de pipeline autant de cycles qu'il le faut. L'autre solution est celle du contournement. L'idée est de faire en sorte que le résultat d'une instruction 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

Pour améliorer un peu les performances du système de contournement, certains processeurs ajoutent un petit cache en sortie des unités de calcul : le cache de contournement (bypass cache). Celui-ci mémorise les n derniers résultats produits par l’unité de calcul. Le tag de chaque ligne de ce cache est le nom du registre du résultat.

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

Il est aussi possible d'envoyer une donnée lue en mémoire sur l'entrée de l'unité de calcul? Il faut alors rajouter une interconnexion qui part de l'unité d'accès mémoire et se connecte sur l'entrée de l'ALU. Si on a une unité d'accès mémoire séparée de l'unité de calcul, tout va bien, tout se passe comme avec le contournement de l'unité de calcul, les circuits sont très similaires et demandent juste un multiplexeur bien placé. La sortie de l'unité d'accès mémoire est connectée à une entrée du multiplexeur, l'autre entrée est connectée aux registres. La sortie du multiplexeur est connectée à l'ALU. La commande du multiplexeur est effectuée par les signaux de commande adéquats provenant du séquenceur.

La seule complexité est de déterminer si la donnée lue est disponible, et de prévoir si l'instruction de calcul qui consomme cette donnée est disponible. Les processeurs modernes implémentent cette forme de contournement, mais uniquement en cas de succès de cache. En clair, on suppose que la donnée sera lue en un nombre fixe de cycles. Si ce n'est pas le cas, on fait face à un défaut de cache, qui cause un pipeline stall, une bulle de pipeline. En conséquence, l'instruction de calcul consommatrice est figée en entrée de l'ALU. Le câblage du processeur est alors plus complexe.

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)

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

Pour comprendre pourquoi il faut retarder l'enregistrement de certains résultats, il faut regarder ce qui se passerait si ce n'était pas le cas. Si on ne retardait pas l'enregistrement du résultat, 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é, et cela peut causer des problèmes assez sérieux ! Imaginez par exemple que la seconde ait besoin des résultats de la première pour s’exécuter : la seconde instruction aura lu des registres pas encore mis à jour, et donnera un résultat incorrect.

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

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

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. Mais ce n'est pas forcément utile. 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'aALU 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 quand même passer par les registres, au prix de quelques bulles de pipeline. Aussi, le contournement entre ALU entière et FPU n'est presque jamais implémenté.

Mais cela ne marche pas toujours. 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. Heureusement, 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.

Si on sort de ce genre d'exemples simples, il est intéressant d'envoyer la sortie de chaque ALU entière sur les entrées de toutes les autres ALU entières. 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.

Une solution est d'utiliser un bus de contournement. L'idée est que les sorties des unités de calcul sont reliées à un bus, qui est lui connecté aux entrées des ALU. La différence avec la technique précédente est qu'une seule unité de calcul peut envoyer des données sur ce bus. Rien d'étonnant : c'est un bus, il ne peut transférer qu'une donnée à la fois. Si plusieurs unités de calcul veulent transmettre leurs résultats sur ce bus, l'une d'entre elle est choisie et les autres doivent mettre en attente leurs résultats dans une mémoire tampon, soit un registre, soit une FIFO. Dans les deux cas, le registre ou la FIFO sont appelés des producers. L'implémentation demande de bloquer des opérations dans l'ALU si le contournement doit être mis en attente, ce qui bloque tout le pipeline en cas de problème.

Producteurs en sortie d'une ALU.

La gestion des dépendances de données est liée au contournement

Le second problème est quant à lui spécifique aux processeurs à pipeline de longueur fixe, là où le précédent vaut même sur les pipelines de longueur variable. Le 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.

Pour cela, le processeur doit mémoriser les registres qui vont être écrits par une instruction en vol dans le pipeline. Il utilise un registre appelé le registre de disponibilité, qui mémorise un bit par registre. Lorsqu'une instruction est décodée et envoyée aux ALU, le bit associé au registre de destination est mis à 1. Le registre de disponibilité mémorise donc tous les registres qui vont être écrits, ceux dont le résultat est idéalement censé être fournit par le système de contournement, en étant lu dans les registres d'échelonnage, mais ne l'est pas. Lorsqu'une instruction est décodée, il extrait les registres lus par l'instruction. Il compare alors ces registres avec le registre de disponibilité. S'ils sont occupés, alors l'unité de décodage insére des bulles de pipeline.

Unité d'émission simple, dans l'ordre

Les dépendances structurelles avec les instructions multicycles

Les instructions multicycles sont une source de conflits d'accès, en raison de comment fonctionnent les ALU associées. Un exemple est celui où on veut faire deux multiplications à la suite, en supposant qu'une multiplication fasse 5 cycles. La première multiplication est lancée au premier cycle, la seconde ne peut pas être lancée au cycle suivant : le circuit multiplieur est en cours d'utilisation par la première. Un tel conflit d'accès, où deux instructions veulent accéder à la même unité de calcul, est un cas particulier de dépendance structurelle, dont nous avions parlé au chapitre précédent.

Une solution simple pour éviter cela est de dupliquer le circuit multiplieur. Prenons un exemple : 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 une ALU différente.

La seconde solution consiste à pipeliner, échelonner les instructions. Si jamais vous avez une opération qui prend cinq cycles, pourquoi ne pas lui fournir un seul circuit et l’échelonner 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. Le problème est que certaines instructions s’échelonnent mal, notamment les divisions.

Exemple avec une unité de multiplication séparée, totalement pipelinée.

Dans la réalité, les statistiques montrent qu'il est rare que deux opérations nécessitant plusieurs cycles d’horloge se suivent dans un programme, ce qui fait que les unités de calcul sont rarement dupliquées. 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. Par contre, échelonner un circuit permet un gain de performance pour un cout en circuits généralement ridicules : il suffit d'ajouter quelques registres dans le circuit. La plupart des processeurs se limitent à utiliser un seul circuit multiplieur, qui est éventuellement échelonné.

Dans les exemples précédents, nous avons vu que l'on peut supprimer certaines dépendances structurelles en dupliquant certains circuits. Mais dupliquer des circuits a un cout en transistors qui peut être prohibitif. Échelonner les unités de calcul est une autre solution, mais elle n'est pas tout le temps applicable. Aussi, de nombreux concepteurs de processeurs laissent quelques dépendances structurelles, et les gèrent en insérant des bulles de pipeline si besoin.