Aller au contenu

Fonctionnement d'un ordinateur/Les pipelines de longueur fixe

Un livre de Wikilivres.

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)

[modifier | modifier le wikicode]

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

[modifier | modifier le wikicode]

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

[modifier | modifier le wikicode]

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

[modifier | modifier le wikicode]

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

[modifier | modifier le wikicode]

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

Banc de registres d'échelonnage

Le contournement est plus complexe avec des instructions multicycles

[modifier | modifier le wikicode]

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 dépendances structurelles avec les instructions multicycles

[modifier | modifier le wikicode]

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.