Fonctionnement d'un ordinateur/Le pipeline

Dans le chapitre sur les performances d'un ordinateur, on a vu que le temps d’exécution d'une instruction dépend du CPI, le nombre moyen de cycles d'horloge par instruction et de la durée P d'un cycle d'horloge. En conséquence, rendre les instructions plus rapides demande de diminuer le CPI ou d'augmenter la fréquence. Monter en fréquence a commencé à monter ses limites avec le processeur Pentium 4, les contraintes de consommation énergétique se faisant de plus en plus lourdes. Les concepteurs de processeurs ont alors cherché à optimiser au mieux les instructions les plus utilisées et se sont plus ou moins heurtés à un mur. Il est devenu évident au fil du temps qu'il fallait réfléchir hors du cadre et trouver des solutions innovantes, ne ressemblant à rien de connu. Ils ont fini par trouver une solution assez incroyable : exécuter plusieurs instructions en même temps ! Pour cela, il a bien fallu trouver quelques solutions diverses et variées, dont le pipeline est la plus importante.

Le pipeline : rien à voir avec un quelconque tuyau à pétrole !

Pour expliquer en quoi il consiste, il va falloir faire un petit rappel sur les différentes étapes d'une instruction. Dans le chapitre sur la micro-architecture d'un processeur, on a vu qu'une instruction est exécutée en plusieurs étapes bien distinctes : le chargement, le décodage, et diverses étapes pour exécuter l'instruction, ces dernières dépendant du processeur, du mode d'adressage, ou des manipulations qu'elle doit effectuer. Sans pipeline, ces étapes sont réalisées les unes après les autres et une instruction doit attendre que la précédente soit terminée avant de démarrer.

Avec un pipeline, on peut commencer à exécuter une nouvelle instruction sans attendre que la précédente soit terminée. Par exemple, on peut charger la prochaine instruction pendant que l'instruction en cours d’exécution en est à l'étape d'exécution. Après tout, ces deux étapes sont complètement indépendantes et utilisent des circuits séparés. Le principe du pipeline est simple : exécuter plusieurs instructions différentes, chacune étant à une étape différente des autres. Chaque instruction passe progressivement d'une étape à la suivante dans ce pipeline et on charge une nouvelle instruction par cycle dans le premier étage.

Pipeline : principe.

Pour comprendre ce que cela signifie, comparons l’exécution de cette instruction sans et avec pipeline. Sans pipeline, on doit attendre qu'une instruction soit finie pour exécuter la suivante. L'instruction exécute toutes ses étapes, avant que l'instruction suivante démarre à l'étape 1.

Exécution de trois instructions sans pipeline.

Avec un pipeline, on démarre une nouvelle instruction par cycle (dans des conditions optimales).

Exécution de trois instructions avec pipeline.

Une illustration plus intuitive est la suivante. Chaque instruction correspond à une couleur :

Pipeline à 5 étages.

Les étages du pipeline

Concevoir un processeur avec un pipeline nécessite quelques modifications de l'architecture de notre processeur. Tout d'abord, chaque étape d'une instruction doit s'exécuter indépendamment des autres, ce qui signifie utiliser des circuits indépendants pour chaque étape. Par exemple, sur un processeur sans pipeline, l'additionneur de l'ALU peut être utilisé pour mettre à jour le program counter lors du chargement, calculer des adresses lors d'un accès mémoire, les additions, etc. Mais sur un processeur doté d’un pipeline, on ne peut pas se le permettre, ce qui fait que chaque étape doit utiliser son propre additionneur. Et en général, il est impossible de réutiliser un circuit dans plusieurs étapes, comme on le fait dans certains processeurs sans pipeline.

Chaque circuit dédié à une étape est appelé un étage du pipeline. La plupart des pipelines intercalent des registres entre les étages, pour les isoler mais aussi pour synchroniser leurs échanges, les contre-exemples étant assez rares. Les seuls exemples de pipelines sans registres sont appelés des pipelines à vague. Mais la règle est clairement de séparer les étages dans des circuits séparés, interfacés par des registres.

Le nombre total d'étapes nécessaires pour effectuer une instruction (et donc le nombre d'étages du pipeline) est appelé la profondeur du pipeline. Il correspond au nombre maximal théorique d'instructions exécutées en même temps dans le pipeline. Et j'ai bien dit maximal théorique : quelques petites subtilités viennent mettre leur grain de sel et font que ce maximum n'est pas toujours atteint, comme on le verra plus tard. Pour les curieux, voici les longueurs de pipeline de certains processeurs plus ou moins connus.

Processeur	Longueur du pipeline
Motorola PowerPC G4	7
MIPS R4400	8
Intel Itanium	10
Intel Pentium II	14
Intel Pentium 3	10
Intel Pentium 4 Prescott	31
Intel Pentium 4	20
AMD Athlon	12
AMD Athlon 64	16
IBM PowerPC 970	16
Sun UltraSPARC IV	14

Plus haut, il a été dit que les étages du pipeline sont censés être totalement séparés, sans partage de circuit entre deux étages. Mais la réalité est beaucoup plus complexe. Dans la réalité, il existe quelques circuits qui sont partagés entre plusieurs étages, car on n'a pas le choix. Deux circuits sont notablement concernés par ce problème : le ou les bancs de registres, l'accès à la mémoire. Il est fréquent qu'un registre soit lu dans un étage et écrit dans un autre, comme on le verra plus bas. Heureusement, le banc de registre est conçu pour gérer la situation, car il a des ports de lecture séparés des ports d'écriture.

Mais on verra que d'autres exemples de ce type sont assez fréquents et qu'il faut gérer la situation. Par exemple, deux instructions peuvent accéder à la mémoire simultanément, exécuetr une micro-opération dans la même unité de calcul, lire le même registre en même temps, etc. De telles dépendances structurelles surviennent quand plusieurs instructions veulent accéder à un circuit du processeur en même temps. Les processeurs modernes incorporent de nombreux circuits capables de gérer les dépendances structurelles, qu'on abordera au fur et à mesure que les occasions se présentent.

Les pipelines synchrones et asynchrones

Plus haut, nous avons dit que la plupart des pipelines utilisent des registres pour séparer les différents étages. Maintenant, il faut que les instructions progressent d'un étage à un autre au rythme adéquat, et la présence de registres aide grandement à implémenter de quoi commander le pipeline. Les transferts entre étages du pipeline peuvent être synchronisés par une horloge, ou de manière asynchrone.

Pipeline synchrone et asynchrone.

Si le pipeline est synchronisé sur l'horloge du processeur, on parle de pipeline synchrone. Chaque étage met un cycle d'horloge pour effectuer son travail, à savoir, lire le contenu du registre qui le relie à l'étape précédente et déduire le résultat à écrire dans le registre suivant. Ce sont ces pipelines que l'on trouve dans les processeurs Intel et AMD les plus récents.

Pipeline buffered synchrone

Sur d'autres pipelines, il n'y a pas d'horloge pour synchroniser les transferts entre étages, qui se font via un « bus » asynchrone. On parle de pipeline asynchrone. La synchronisation des échanges entre deux étages se fait grâce à un signal de requête et un signal acquittement. Le signal de requête REQ indique que l'étage précédent a terminé son travail et qu'on peut lire son résultat. Le signal d'acquittement signifie que l'étage destinataire a pris en compte la donnée transmise. Les signaux de commande de ces pipelines asynchrones peuvent se créer facilement avec des portes C.

Micropipeline-structure

Des exemples de pipeline

Découper un processeur en pipeline peut se faire de différentes manières, le nombre et la fonction des étages variant fortement d'un processeur à l'autre.

Le pipeline Fetch-Decode-Exec

En guise de premier exemple, nous allons utiliser une organisation relativement simple, avec seulement deux étages : un qui charge et décode l'instruction, l'autre qui exécute l'instruction. Elle s'implémente en séparant les deux étages par un registre, qui mémorise les signaux de commande en sortie du décodeur d'instruction. Il s'agit du pipeline le plus simple qui soit, mais il est pourtant été utilisé sur les processeurs Atmel AVR, ainsi que les processeurs PIC. Il est simplement découpé de deux étages

The Fetch-Execute Cycle

Un problème avec ce pipeline est que l'étape de Fetch et d'Exec peuvent parfois faire un accès mémoire en même temps. Le pipeline doit lire une instruction à chaque cycle d'horloge, quelque soit l'instruction. Si l'étape d'Exec exécute un accès mémoire pour lire/écrire une donnée, le processeur fait deux accès concurrents : un pour charger l'instruction, un autre pour lire/écrire la donnée. Il s'agit techniquement d'une situation de dépendance structurelle, mais passons.

La solution simple la plus simple est de passer à une architecture Harvard, avec deux mémoires séparées. Pour un processeur avec un cache, cela revient à utiliser un cache d'instruction séparé du cache de données, ce qui garantit que les deux étages ne se marcheront plus dessus et accéderont chacun à leur cache dédié. D'autres solutions existent, comme utiliser un cache unique mais multiport, mais l'essentiel est qu'on puisse lire une instruction et accéder à une donnée en même temps. Précisons que tous les pipelines ont ce problème, sans exception ! Tous les pipelines que nous verrons dans ce cours font face au même problème et les mêmes solutions sont appliquées.

Le pipeline qu'on vient de voir a l'air très simple, mais cela ne signifie pas qu'il n'est pas réaliste, au contraire. Il a été utilisé dans des processeurs commerciaux, utilisés par le grand public. Par exemple, les tout premiers processeurs ARM, jusqu'aux processeurs ARM7 utilisaient un pipeline Fetch-Decode-Exec.

Un pipeline légèrement plus compliqué utilise les trois étapes suivantes :

• chargement : chargement de l'instruction ;
• décodage : décodage de l'instruction ;
• exécution : exécute l'instruction.

Le premier étage correspond au calcul du program counter et à l'accès au cache, le second au décodage de l’instruction, le troisième à l’exécution de l'instruction par le chemin de données. Ces trois étapes sont souvent désignées sous les noms de Fetch, Decode et Exec. Nous utiliserons cette terminologie dans la suite de ce cours.

Le problème précédent revient, à savoir que le processeur charge une instruction pendant qu'il lit/écrit une donnée en RAM. La solution utilisée est encore une fois la même. Au-delà de ça, la seule difficulté d’implémentation est que ces trois étages doivent fonctionner indépendamment, à savoir qu'une instruction dans le décodeur doit être différente de celle dans le chemin de données. Il faut donc isoler ces circuits, en insérant des registres au bon endroit dans le pipeline. Pour cela, on mémorise les signaux de commandes en sortie du décodeur, et on profite du registre d'instruction entre l'étage de chargement et l'étage de décodage, qui était déjà là. L'implémentation demande donc deux registres, dont un était déjà dans le processeur.

Pipeline à trois étages

Les pipelines avec un chemin de données pipeliné

Les pipelines précédents sont de loin très simples à comprendre. Ils collent assez bien à ce qu'on a vu dans les chapitres sur la microarchitecture d'un ordinateur, la séparation entre unité de chargement, décodage et chemin de données est familière. De plus, ce pipeline a de nombreux avantages, bien que vous n'ayez pas encore les concepts pour les comprendre : absence de problèmes liés aux dépendances de données, pas de dépendances structurelles majeures. Les pipelines suivants ne sont malheureusement pas aussi simples. La raison est que le chemin de données est lui-même pipeliné, d'une manière qui n'est pas forcément intuitive. Les pipelines qui vont suivre vont aller croissant en complexité, avec un ou deux étages en plus à chaque fois.

Un exemple sépare le chemin de données en trois étages. La seule différence est que la lecture des opérandes dans les registres ou l'écriture dans les registres ont chacun leur propre étage Il contient les 6 étapes suivantes :

• PC : mise à jour du program counter ;
• chargement : chargement de l'instruction depuis la mémoire ;
• décodage : décodage de l'instruction ;
• chargement d’opérandes : les opérandes d'une instruction sont lus depuis les registres ;
• exécution : exécution de l'instruction dans l'unité de calcul ou accès mémoire ;
• enregistrement : écriture du résultat de l’instruction ou de la donnée lue dans les registres.

Ce pipeline est plus intuitif que les précédents, sauf le tout premier. En effet, la lecture des registres, l’exécution de l'instruction et l'enregistrement dans les registres sont séparés dans des étages distincts.

Pipeline à 7 étages naïf.

La séparation des étages sur un pipeline de ce genre est plus complexe, car il faut découper le chemin de données en plusieurs étapes. Pour cela, il faut rajouter des registres aux bons endroits et surtout : faire passer les bonnes informations dans ces registres. Les informations en question comprennent les les signaux de commande générés par le décodeur, qui servent à configurer le chemin de données. Comment faire pour que ces signaux de commande traversent le pipeline et soient consommés par les étages adéquats ? Relier directement les sorties de l'unité de décodage aux circuits incriminés ne marcherait pas. Les signaux de commande arriveraient immédiatement aux circuits, alors que l'instruction n'a pas encore atteint ces étages ! La réponse consiste à faire passer ces signaux de commande d'un étage à l'autre en utilisant des registres. Cette méthode sera utilisée sur tous les pipelines où le chemin de données contient plusieurs étages.

Propagation des signaux de commande dans un pipeline à 7 étages.

Notons qu'à chaque cycle, l'étage de Fetch charge une instruction, pendant que l'étage d'accès mémoire peut faire de même avec une donnée. D'où le fait que le processeur est une architecture Harvard, comme on l'a dit plus haut.

Un autre problème à résoudre est l'accès au banc de registres. Dans les pipelines vus précédemment, on y accède en lecture lors de l'étage de chargement des opérandes (ou en parallèle du décodage), avant l'étage d’exécution. Mais on y accède aussi en écriture dans le tout dernier étage. En clair, on a deux accès au banc de registre à chaque cycle. La solution qui consiste à dupliquer des circuits fonctionne assez bien dans ce cas. Non pas qu'il faille dupliquer le banc de registre. Par contre, il est possible d'utiliser un cache multiport, avec des ports de lecture séparés du port d'écriture. Il s'agit d'une forme de duplication assez spécifique, où on duplique les ports du banc de registre, pas le banc de registre lui-même.

Le pipeline RISC classique et ses variantes

Les pipelines précédents sont relativement simples et sont très pédagogiques. Il faut dire qu'ils ont été conçus pour. Mais la plupart des cours d'architecture des ordinateurs, notamment les textbooks américains, utilisent un autre pipeline à 5 étage, appelé le pipeline RISC classique. Il s'agit d'un pipeline à 5 étages, utilisé sur les premiers processeurs RISC, les tout premiers processeurs disposant d'un pipeline.

Malgré ses défauts pédagogiques certains, il est présent dans presque tous les cours qui abordent le sujet du pipeline, que ce soit pour son intérêt historique, pour son apparente simplicité qui est pourtant trompeuse, ou par habitude pédagogique. Je vais parler de ce pipeline en détail, dans ce qui suit et dans le chapitre suivant. La raison principale est que ce pipeline étant très populaire, cela vous sera utile si jamais vous souhaitez consulter d'autres sources, d'autres cours, des articles wiki ou autres. L'autre raison est que ce pipeline, malgré ses défauts, permet quand même d'aborder facilement quelques concepts simples, comme les dépendances de données ou structurelle. Enfin, une raison assez pragmatique est que l'on trouve très facilement des images de ce pipeline pour illustrer la majeure partie des concepts abordés dans la suite du cours.

Dans ce qui suit, je vais introduire ce pipeline en commençant par une version simplifiée à 4 étages, avant de présenter sa version originelle. Le pipeline suivant est le pipeline d'un d'un processeur MIPS assez simple, à 4 étages. L'architecture en question est une architecture LOAD-STORE, qui gère quelques modes d'adressage mineurs. Il contient 4 étages : chargement, décodage, exécution et écriture dans le banc de registre.

Conditional Microprocessor 2.0 Pipeline Design 1.1

L'étage de chargement dispose d'une première optimisation assez intéressante : il effectue la mise à jour du program counter en parallèle de l'accès mémoire. Le program counter est directement relié à l'entrée d'adresse du cache ou de la mémoire, son incrémenteur et les MUX pour les branchements sont situés après.

L'étage de décodage est un peu particulier, car il ne fait pas que du décodage. Il prépare aussi les opérandes à envoyer à l'unité de calcul, quitte à accéder au chemin de données. Par exemple, si l'instruction le nécessite, il effectue un accès au banc de registre, pour lire les opérandes d'un calcul ou d'un accès mémoire. C'est étrange, pas intuitif et surtout cela s'explique par des histoires de dépendances structurelles que nous ne pouvons pas aborder ici. Heureusement, les premiers processeurs RISC avaient un jeu d'instruction très simples, son encodage garantit que les noms de registres sont tous au même endroits dans les instructions. Il est alors facile de les récupérer pour les envoyer au banc de registre en parallèle du décodage.

L'étage d’exécution est composé d'une ALU et d'une unité d'accès mémoire séparées, en parallèle. Si l'instruction à effectuer est un calcul, elle passe par l'ALU. Si c'est une instruction d'accès mémoire, elle passe dans l'unité d'accès mémoire. L'implémentation de certains modes d'adressage mémoire avec ces pipelines est un peu complexe. Les modes d'adressage qui demandent un calcul d'adresse posent problème car l'ALU ne peut pas faire le calcul d'adresse avant de l'envoyer à l'unité d'accès mémoire. La seule solution est d'intégrer de quoi faire des calculs d'adresse dans l'unité d'accès mémoire, soit de se passer de ces modes d'adressage. Le pipeline RISC classique règle ce problème, mais au prix d'un pipeline moins simple à comprendre.

Enfin, la dernière étape enregistre dans les registres : soit la donnée lue en mémoire, soit le résultat fournit par l'ALU. Il correspond au port d'écriture du banc de registre, ainsi qu'à quelques MUX qui configurer le chemin de données. Les instructions d'écritures n'utilisent pas cet étage, qui est formellement facultatif. La modification du registre d'état et des registres de prédicats a aussi lieu dans cet étage, s'ils existent.

Pipeline MIPS à quatre étages, plus détaillé.

Le pipeline précédent gère mal les modes d'adressages avec calcul d'adresse. Mais le pipeline suivant corrige ce problème, en mettant l'ALU en série avec l'unité de communication mémoire, dans deux étages séparés. Il s'agit du pipeline RISC classique proprement dit, c'est encore une fois le pipeline d'un processeur MIPS assez simple et c'est un pipeline à 5 étages. Les 5 étages sont les suivants : chargement, décodage, calcul, accès mémoire (LOAD-STORE), enregistrement dans les registres. En clair, les étages sont les mêmes que pour le pipeline précédent, à la différence que l'étage d’exécution a été dupliqué et modifié.

MIPS Architecture (Pipelinée)

Il n'est pas des plus intuitif et a pas mal de défauts pour l'enseignement, malgré sa simplicité. La raison est qu'outre la lecture des opérandes qui se fait en parallèle du décodage, certaines étapes sont « facultatives » pour certaines instructions. Par exemple, certaines instructions n'ont pas besoin d'accéder à la mémoire et n'ont pas besoin de l'étage MEM. La plupart des instructions de calcul sont dans ce cas, pareil pour les branchements, les copies entre registres, etc. Un autre cas est celui des instructions LOAD et STORE, avec certains modes d'adressages, qui n'ont pas besoin de calcul d'adresse et n'ont pas besoin de l'ALU dans l'étage d’exécution. Les instructions concernées doivent passer par ces étages, mais ceux-ci ne doivent rien faire.

Disons pour le moment que ce genre de situation se règle soit en effectuant un NOP dans l'unité de calcul, soit en utilisant des multiplexeurs. Si on a besoin que l'ALU ne fasse rien, on lui demande de faire un NOP. Pour les autres étages, on utilise un multiplexeur qui choisit entre : la sortie de l'unité associée à l'étage, le registre de pipeline précédent.

Inactivation d'un étage de pipeline avec des multiplexeurs

La performance d'un pipeline

Revenons un peu sur les pipelines synchrones. L'usage d'un pipeline augmente les performances, mais essayons de comprendre pourquoi. La raison est que l'on peut exécuter plusieurs instructions en même temps. Mais il se pourrait que cela aie d'autres effets, par exemple sur le temps d’exécution des instructions ou la fréquence. Pour comprendre toutes les conséquences de l'usage d'un pipeline, le mieux est d'étudier l'impact du pipeline sur divers paramètres du processeur : fréquence, temps d’exécution, parallélisme d'instruction, et autres. Nous allons nous focaliser sur la fréquence, le temps d’exécution d'une instruction et le nombre d'instructions exécutées en parallèle.

La performance théorique d'un pipeline idéal (approche simplifiée)

Pour commencer, nous allons voir cas d'un pipeline idéal, c'est à dire que nous allons négliger le fait qu'il y a des registres entre les étages du pipeline. Ils ont un temps de propagation non-nul, et ont donc un effet sur la fréquence et sur la latence des instructions. Mais pour simplifier les calculs, nous allons négliger le temps de propagation des registres inter-étages.

De plus, nous allons supposer que les étages sont assez bien équilibrés, de manière à avoir le même temps de propagation. Dans la réalité, les étages ne sont pas forcément équilibrés à la perfection, mais c'est une bonne approximation. Le pipeline étudié est donc un cas irréaliste de pipeline, idéal. Prenons un processeur qui exécute toutes ses instructions en un seul cycle sur un processeur et découpons ce processeur en 5 étages équilibrés. Voici ce que l'on obtient :

Effet de l'usage d'un pipeline sur la fréquence d'un processeur.

Le schéma précédent montre que la fréquence change entre les deux situations car le cycle d'horloge n'est pas déterminé par l'instruction entière, mais par le temps de propagation d'un étage. Et cette durée correspond à la durée d'un cycle, divisée par le nombre d'étages. On passe donc c'un processeur dont la fréquence est de :

$f={1 \over t}$, avec t le temps d’exécution d'une instruction (sans pipeline).

à un processeur de fréquence :

$f_{\text{pipeline}}={\frac {1}{t \over N}}=N\times f$, avec N le nombre d'étages.

On voit que la fréquence a été multipliée par le nombre d'étages avec un pipeline ! En clair, l'usage d'un pipeline permet donc de multiplier la fréquence par un coefficient plus ou moins proportionnel aux nombres d'étages.

Par contre, le temps d’exécution d'une instruction ne change pas avec ou sans pipeline ! Le pipeline permet d’exécuter plusieurs instructions en même temps, mais chaque instruction met presque autant de temps à s’exécuter avec un pipeline idéal. Elle est juste découpées en plusieurs étapes courtes au lieu d'être faite en une fois. Une autre manière de le voir est de remarquer que si la fréquence est multipliée par N, c'est compensée par le fait que l'instruction prend maintenant N étages pour s’exécuter, et donc N cycles d'horloge.

Étudier l'effet de tout cela sur la performance du processeur n'est pas trivial. Peut-être avez-vous pensé à utiliser l'équation vue dans le chapitre sur la performance d'un ordinateur :

${\text{Temps d'execution d'un programme}}=N_{instructions}\times {\frac {CPI}{f}}$, avec f la fréquence, CPI le nombre de cycles moyen par instruction, et $N_{instructions}$ le nombre d'instructions à exécuter.

Mais l'équation en question ne fonctionne que si on suppose que les instructions sont éxecutées l'une après l'autre. Un bon moyen de s'en rendre compte est de remarquer qu'avec un pipeline, f et CPI sont tous les deux multipliés par N, ce qui fait que le terme de droite ne change pas, de même que le terme N reste le même. Mais alors d'où vient l'amélioration de performance tant promise ? Pour comprendre, prenons une version modifiée de l'équation précédente, avec

${\text{Temps d’exécution d'un programme}}={\frac {N_{instructions}}{IPC\times f}}$, avec f la fréquence et IPC le nombre d'instruction exécutées par cycle.

La fréquence est multipliée par N, mais IPC est plus complexe à calculer. Déjà, la durée d'un cycle est divisée par N car la fréquence augmente alors que le temps d’exécution d'une instruction ne change pas. Ce qui fait que l'IPC est divisé par N. Mais d'un autre côté, on peut charger une nouvelle instruction à chaque cycle d'horloge, ce qui donne une instruction dans chaque étage. Cela multiplie l'IPC par N, ce qui compense. Au final, l'IPC reste stable et la fréquence est multiplié par N : le temps d’exécution est divisé par N.

Pour résumer, la puissance de calcul a été multipliée par le nombre d'étages du pipeline, mais pas pour la raison qu'on s'imagine. Il ne réduit pas le temps d’exécution d'une instruction, mais profite de la hausse de fréquence de manière indirecte. Le pipeline augmente les performances par le fait que plusieurs instructions puisse s’exécuter en même temps. Si la latence reste la même, le débit du processeur augmente.

La performance théorique d'un pipeline avec des registres inter-étages

En théorie, le raisonnement précédent nous dit que le temps d’exécution d'une instruction est le même sans ou avec un pipeline. Cependant, il faut prendre en compte les registres intercalés entre étages du pipeline, qui ajoutent un petit peu de latence. Nous allons noter $\tau$ le temps de propagation d'un de ces registres. Refaisons donc les calculs précédents, en commençant par le temps de propagation d'un étage. Il suffit d'ajouter la latence du registre à l'équation précédente, ce qui donne :

$t_{\text{étage}}={\frac {t}{N}}+\tau$

En multipliant par N, on obtient le le temps d’exécution d'une instruction. On voit que ce dernier est égal au temps sans pipeline, auquel on ajoute la latence des registres inter-étages. Le temps d’exécution d'une instruction est donc allongé avec un pipeline.

$T=N\times \left({\frac {t}{N}}+\tau \right)=t+\tau \times N$

La fréquence du processeur est l'inverse de $t_{\text{étage}}$, ce qui donne :

$f={\frac {1}{{\frac {t}{N}}+\tau }}={\frac {N}{t+\tau \times N}}$

On retrouve le résultat précédent, mais seulement dans les grandes lignes. La fréquence du processeur avec un pipeline augmente, comparé à la fréquence du même processeur mais sans pipeline. Et elle augmente d'autant plus que le nombre d'étages est grand. La raison est qu'un étage de pipeline a un temps de propagation plus petit qu'un processeur complet, ce qui permet d'en augmenter la fréquence. Les latences des registres réduisent cependant les gains en fonction du nombre d'étages : passer de 1 étage à 5 donne un gain en fréquence, mais passer de 20 à 25 aura un effet beaucoup plus faible. Les rendements sont rapidement décroissants, la durée d'un étage étant de plus en plus dominée par la latence des registres.

On peut calculer le gain en comparant la fréquence avec et sans pipeline :

${\frac {f_{\text{Avec pipeline}}}{f_{\text{Sans pipeline}}}}={\frac {Nt}{N\tau +t}}={\frac {N}{{N\tau \over t}+1}}$

Le résultat est inférieur à N et on voit l'influence des N registres. Le terme ${Nr \over t}$ correspond au pourcentage de temps passé à traverser les registres par rapport au temps de propagation sans les registres. Par exemple, si le temps de propagation des registres prend la moitié du temps de propagation, alors ce terme vaut 1 et la fréquence est divisée par deux.

L'hétérogénéité des latences entre étages

Sur les processeurs réels, les raisonnements précédents sont cependant invalides, vu que certains étages possèdent un chemin critique plus long que d'autres. On est alors obligé de se caler sur l'étage le plus lent, ce qui réduit quelque peu le gain. La durée d'un cycle d'horloge doit être supérieure au temps de propagation de l'étage le plus lent.

Pipelining hétérogène d'un circuit

Le monde réel : l'exemple des processeurs Intel

Les développements précédents nous ont appris que l'usage d'un pipeline permet au mieux de multiplier la fréquence par le nombre d'étages, moins en pratique. Tous les calculs précédents sont très intéressants, mais il reste à voir ce que cela donne dans le monde réel. Pour cela, on doit comparer la fréquence des processeurs en fonction de la longueur de leur pipeline, et voir ce que cela donne. Évidemment, il faut tenir compte que la finesse de gravure de ces processeurs n'est pas les mêmes. Vu que la fréquence du processeur est très fortement influencée par la finesse de gravure, cela fausse les comparaisons. Mais il est possible de déterminer une une fréquence relative, à savoir la fréquence à finesse de gravure égale. Il est difficile de la calculer, mais on peut l'utiliser pour comparer des processeurs entre eux, à condition de prendre la fréquence d'un processeur de référence

Et on s’aperçoit que cette fréquence relative est fortement reliée aux nombres d'étages du pipeline. Un processeur à haute fréquence relative a un pipeline plus long que ses concurrents de fréquence relative plus basse. La relation n'est pas proportionnelle, pour des raisons que l'on verra plus bas. Par exemple, regardons la fréquence relative des processeurs Intel d'avant le Pentium 4 (les seuls pour lesquels j'ai les données, on pourrait comparer avec les processeurs suivants sans que cela change la logique). Voici ce qu'on obtient :

Fréquences relatives processeurs Intel pré-Pentium 4

Et comparons la longueur de leur pipeline :

Processeur	Longueur du pipeline
286	5
386
486
Pentium
Pentium 2/3	14
Pentium 4	31 à 20 selon les modèles

On s’aperçoit qu'il n'y a pas proportionnalité exacte, mais que la tendance est bonne. La fréquence a triplé au passage au Pentium 2/3, mais cela s'est traduit par une hausse de fréquence de seulement 50%. Pour le Pentium 4, sa fréquence a sextuplé par rapport aux premiers CPU Intel, mais la fréquence a été multipliée par seulement 2,5 %.

Cela a poussé certains fabricants de processeurs à créer des processeurs ayant un nombre d'étages assez élevé pour les faire fonctionner à très haute fréquence. Avant les années 2000, la fréquence était un argument marketing puissants, sans compter que l'augmenter permettait des gains de performances assez importants. Par exemple, c'est ce qu'a fait Intel avec le Pentium 4, dont le pipeline faisait 20 étages pour les Pentium 4 basés sur l'architecture Willamette et Northwood, et 31 étages pour ceux basés sur l'architecture Prescott et Cedar Mill. Cela avait cependant son nombre de défauts, comme on le verra plus bas.

En effet, n'allez pas croire que plus on augmente la longueur du pipeline, meilleure est la performance. Les pipelines ont tous des défauts assez importants qui font que les performances sont inférieures aux performances théoriques. Les prochains chapitres vont vous expliquer pourquoi les pipelines ne sont pas une solution miracle, et quels correction les concepteurs de processeur ont à leur disposition.

Les défauts des pipelines : les dépendances entre instructions

Avec ce qu'on a dit plus haut, il semblerait que l'implémentation d'un pipeline soit assez simple. Mais dans la réalité, tous les pipelines ont des problèmes assez peu intuitifs. Les problèmes en question ont tous la même origine : le modèle d’exécution normal suppose qu'une instruction n'est démarrée que lorsque la précédente est terminée, ce qui n'est pas le cas sur un pipeline. Un programme est codé en partant du principe que les instructions s'exécutent de manière séquentielle, l'une après l'autre, que la première soit terminée avant qu'on en démarre une autre. Mais le pipeline charge une nouvelle instruction à chaque cycle, sans attendre que la précédente soit terminée, pareil pour l'exécution dans l'ALU.

En théorie, le pipeline ne pose pas de problèmes si deux instructions consécutives sont indépendantes, mais c'est rarement le cas en pratique. Les instructions ont des dépendances très variées, mais on peut les résumer comme suit : deux instructions ont une dépendance quand elles manipulent la même ressource. En clair, quand elles manipulent en même temps le même registre, la même unité de calcul, la même adresse mémoire, etc. Il existe divers types de dépendances, appelées dépendances structurales, de contrôle et de données. Il est possible de les décrire de manière abstraite, même les explications ne sont pas très parlantes. Essayons quand même.

Les dépendances de données

Les dépendances de données sont les plus intuitives. Le cas typique est celui où une instruction a besoin du résultat d'une instruction précédente pour s’exécuter. La seconde doit alors s'exécuter après la première. Mais il y a d'autres types de dépendances de données bien moins intuitifs. Deux instructions ont une dépendance de données quand elles accèdent (en lecture ou écriture) au même registre ou à la même adresse mémoire. Nous détaillerons ce type de dépendances, leurs problèmes et les solutions apportées, dans des chapitres dédiés.

Le moyen le plus simple pour corriger les problèmes liés au pipeline est de retarder l'exécution d'une instruction tant que les conditions nécessaires pour son exécution ne sont pas réunies. Par exemple, prenons le cas où une instruction a pour opérande le résultat d'une autre. La première instruction calcule le résultat, la seconde l'utilise. Dans ce cas, la seconde doit attendre que le résultat de la première soit calculé, elle doit donc être retardée durant quelques cycles pour cela.

La mise en attente se fait au niveau de l'unité de décodage. Durant ce temps d'attente, on insère des vides après l'unité de décodage : certains étages seront inoccupés et n'auront rien à faire. Ces vides sont appelés des calages (stall), ou bulles de pipeline (pipeline bubble). De plus, les étages qui précédent l'unité de décodage sont bloqués en empêchant l'horloge d'arriver aux étages antérieurs au décodage.

Pipeline bubble

Dans la suite du cours, nous verrons de nombreux cas dans lesquels insérer des bulles de pipeline est une obligation si on veut que le processeur fonctionne correctement. Il s'agit là d'une fonctionnalité très importante de tous les pipelines, anciens comme modernes. Évidemment, les bulles de pipeline sont une source de perte de performance : le pipeline ne fait rien tant qu'une instruction n'est pas terminée, ce qui va à l'encontre du principe du pipeline. Et de nombreuses techniques d'optimisations visent à réduire l'utilisation de ces bulles de pipeline le plus possible. Et expliquer comment font ces explications est le sujet des 10 prochains chapitres !

Les micro-opérations mémoire

Les pipelines vus plus haut sont conçus pour des instructions qui font un seul cycle d'horloge. Et les accès mémoire ne font pas exception. Mais dans le monde réel, les accès mémoire prennent plus de cycles. Un accès au cache peut prendre deux à trois cycles d’horloge, un accès au cache L2 prend facilement 10 cycles, et un accès en RAM une centaine. Les latences en question ne sont pas compatibles avec un pipeline. Et surtout, les latences sont variables, ce qui ne colle pas avec un pipeline avec un nombre fixe d'étapes !

Les accès mémoire posent donc un double un problème : leur latence est très variable, souvent supérieure à celle du pipeline complet. Pour régler le problème, on n'a pas d'autre choix que de recourir à des bulles de pipeline. Si l'unité de décodage s'aperçoit qu'elle vient de décoder une micro-opération mémoire, il l'envoie dans le pipeline, mais émet des bulles de pipelines tant que l'accès mémoire n'est pas terminé. Les unités de communication avec la mémoire vont alors effectuer l'accès au cache, éventuellement gérer un défaut de cache. Quand la micro-opération mémoire est terminée, la donnée lue est disponible ou l'écriture est finie. Elle prévient alors le décodeur d'instruction, qui cesse d'émettre des bulles de pipeline et reprendre l'exécution.

Les dépendances structurelles

Les dépendances structurelles apparaissent quand deux instructions veulent utiliser le même circuit en même temps. Nous avions un cas de ce genre précédemment : le pipeline charge une instruction à chaque cycle, les accès mémoires se font en plus, deux instructions peuvent accéder à la mémoire en même temps. Le tout se corrige avec l'usage d'une mémoire multiport ou deux mémoires/caches séparés pour les instructions et les données. Il en est de même avec le banc de registre : accédé en lecture lors de l'étape adéquate, en écriture lors de l'étape d'écriture à la fin du pipeline. La solution est encore une fois de séparer/dupliquer une ressource matérielle, ici les ports de lecture/écriture. Mais il existe d'autres dépendances structurelles aux origines moins intuitives, comme on le verra dans la suite du cours.

Les dépendances structurelles sont gérées comme les dépendances de données : si une instruction a une dépendance structurelle avec une autre, une des deux s'exécute, l'autre attend que la dépendance structurelle disparaisse. La solution est assez générale : dès qu'une instruction a une dépendance avec une instruction précédente, on peut retarder l'instruction tant que l'instruction précédente n'a pas quitté le pipeline et écrit son résultat dans les registres. Autrement dit, on attend qu'une instruction précédente soit terminée avant de démarrer l'instruction courante.

Les problèmes liés aux branchements, interruptions et exceptions

Les dépendances de contrôle sont liés aux branchements. En théorie, les instructions qui suivent un branchement ne doivent pas être chargées ou exécutée tant que le branchement n'est pas terminé. Il faut dire qu'il ne sait pas si le branchement est pris ou non, ni quelle adresse charger suite au branchement. Mais le problème est qu'un branchement ne s'exécute pas immédiatement, il faut quelques cycles pour calculer l'adresse à laquelle brancher Et pendant ce temps, des instructions sont chargées à tort dans le pipeline. Les instructions qui suivent le branchement en mémoire sont chargées dans le pipeline à sa suite, à raison d'une instruction par cycle.

Notons qu'il n'y a pas le même problème avec les interruptions et exceptions matérielles. En effet, peu importe qu'une interruption ou une exception soit décalée de quelques cycles d'horloge. La routine d'interruption est un programme totalement indépendant du programme interrompu. Que le programme interrompu puisse exécuter quelques instructions en plus avant de passer la main à la routine d'interruption/exception n'est en soi pas un gros problème. Il y a cependant des techniques pour empêcher cela, que l'on verra dans quelques chapitres. Pour le moment, mettons-les de côté.

Pour les branchements, une solution tout simple délègue le problème aux compilateurs/programmeurs. Ils doivent faire suivre les branchements de quelques NOPs, des instructions qui ne font rien, pour éviter tout problème. Ainsi, si l'adresse de destination du branchement est connue N cycles après le chargement, on a juste à insérer N NOPs à la suite de chaque branchement. Pas idéal, aussi mieux vaut trouver une solution purement matérielle pour annuler les instructions chargées à tort.

Une autre méthode consiste à identifier les branchements à l'étape de décodage. Si l'étape de décodage décode un branchement, elle sait qu'elle a potentiellement chargé des instructions à tort. Après, tout dépend de si le branchement est conditionnel ou non.

S'il s'agit d'un branchement inconditionnel, le processeur est certain qu'il a chargé à tord des instructions. Précisément N instructions, avec N le nombre d'étages entre le chargement et le décodage (inclus). Dans ce cas, par sécurité, les N instructions suivantes sont tout simplement annulés, elles sont remplacées par des NOPs. Notons qu'il ne s'agit pas de bulles de pipeline. Une bulle de pipeline retarde une instruction, elle la bloque dans l'unité de décodage. Ici, les instructions sont annulées.

Pour les branchements conditionnels, la technique doit être quelque peu adaptée pour tenir compte du cas où le branchement est non-pris, mais les modifications sont mineures. Le cas des branchements conditionnels est résolu avec l'ajout de bulles de pipeline à la technique précédente. L'idée est de ne pas exécuter d'instruction tant que le résultat du branchement n'est pas connu. Une fois le résultat connu, on décide s'il faut annuler ou non les instructions chargées à tord. Il y a une petite subtilité quant à l'envoi des bulles de pipeline. Quand le processeur décode un branchement, il envoie le branchement aux unités de calcul. Il émet des bulles de pipeline immédiatement après. Les bulles de pipeline commencent à l'instruction suivante. En clair, les instructions qui suivent le branchement sont bloquées à l'étape de décodage, en attendant son résultat.

Voilà, vous avez maintenant une petite idée des problèmes que l'on doit résoudre pour obtenir un processeur avec pipeline fonctionnel. Vous aurez remarqué que la majorité de ces problèmes sont résolus avec des bulles de pipeline, et avec la perte de performance qui va avec. Mais de nombreuses optimisations permettent d'éviter cela. Et préparez-vous : les 10 chapitres qui vont suivre expliqueront comment ces optimisations sont implémentées.