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-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 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 pipeline est nommé d'après le nom de ces trois étapes, à savoir qu'on parle de pipeline Fetch-Decode-Exec.

Le pipeline Fetch-Decode-Exec 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-Exec.

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, ils ont 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, etc. Les pipelines suivants ne sont malheureusement pas aussi simples et vont aller croissant en complexité, avec un ou deux étages en plus à chaque fois. 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.

Un exemple sépare le chemin de données en trois étages : un étage de la lecture des opérandes dans les registres, un étage d'exécution dans l'ALU, un étage pour écrire le résultat dans les registres. 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.

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, il n'est utilisé que dans l'étage d'exécution. Mais cela fait deux accès au banc de registre à chaque cycle. Mais ici, le banc de registre est accédé dans deux étages séparé. Heureusement, les deux accès sont différents : on a un accès en lecture lors de l'étape de lecture des opérandes, et un accès en écriture dans l'étape d'enregistrement du résultat. La solution utilise un banc de registre 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 pipelines complexes

Avec ce qu'on vient de voir précédemment, l'implémentation d'un pipeline a l'air d'être assez simple. Mais dans les faits, les processeurs utilisent des pipelines beaucoup plus complexes. Implémenter un pipeline est plus compliqué que simplement placer des registres au bon endroit. Aussi, voyons dans le détail comment sont organisés les pipelines plus complexes.

La séparation entre front-end et back-end

Avec un pipeline, le processeur est décomposé en deux parties. La première partie, l’amont (front end), prend en charge les étages communs à toutes les instructions. Il correspond au séquenceur et à l'unité de chargement et regroupe la mise à jour du program counter, le chargement, l'étage de décodage, etc. L'amont est suivi par le chemin de données, qui est organisée en plusieurs voies, chacune formant ce qu'on appelle un aval (back end). Un aval correspond soit à une unité de calcul, soit à l'unité mémoire. Toutes les voies partagent le banc de registre, que ce soit pour lire les opérandes ou enregistrer un résultat.

Pipeline avec un aval et un amont (back-end et front-end).

Les processeurs les plus simples n'utilisent qu'un seul aval, qui se résume à une unité de calcul entière couplée à l'unité mémoire. Mais ils sont tellement rares qu'ils se résument pipelines simples vus précédemment, comme le pipeline RISC classique, guère plus. Dans les faits, les processeurs modernes utilisent plusieurs avals.

La quasi-totalité des processeurs modernes dispose d'une voie séparée pour les accès mémoire. La voie pour les accès mémoire est une unité mémoire dédiée, dont sa connexion avec le pipeline varie grandement suivant le processeur. L'unité mémoire est séparée pour une bonne raison : les accès mémoire se marient assez mal avec un pipeline. Les accès mémoire ont une latence élevée, variable et sont difficile à pipeliner de manière générale. La voie pour les accès mémoire sert donc d'exception, c'est une unité qui n'est pas tout à fait pipelinée, alors que le reste du chemin de données l'est.

Pipeline à deux aval de type load-store.

Si on omet les voies liées aux accès mémoire, les autres voies correspondent peu ou prou à une unité de calcul. Par exemple, il est fréquent d'avoir des avals séparés pour l'addition, la multiplication et les décalages (barrel shifter), vu que ces opérations sont dans des ALU entières séparées. De même, on a un aval séparé pour les instructions flottantes, lié au fait que la FPU est une unité de calcul séparée. Les instructions de branchement peuvent avoir un aval dédiée, avec une ALU pour effectuer des comparaisons. La longueur de l’aval varie suivant le type d'instructions.

Pipeline avec un nombre variable d'étages par instructions.

La destination de chaque voie peut aussi varier. Les instructions de calcul ou les lectures enregistrent un résultat dans les registres, et se terminent donc sur le port d'écriture du banc de registres. Par contre, les voies pour les branchements ou les écritures n'enregistrent rien dans les registres. La voie pour les branchement se termine dans le séquenceur et/ou dans le registre d'état, la voie pour les écritures ne finit nulle part si ce n'est dans l'unité mémoire.

Pipeline avec un aval pour les instructions arithmétiques, un aval pour les accès mémoire et un aval pour les branchements

Plus tard dans la suite du cours, nous verrons que les processeurs modernes regroupent plusieurs ALU par voie, pour des raisons assez compliquées à expliquer ici. Retenez juste que le chemin de données est composé de plusieurs voies relativement indépendantes, chacune spécialisée dans un type de micro-opération spécialisé. Les voies commencent toutes avec la lecture des opérandes, elles effectuent un calcul, puis enregistrent leurs résultats dans les registres si besoin.

Les processeurs à émission simple et multiple

Toujours est-il que le décodeur envoie des instructions décodées dans la voie appropriée. Par exemple, une instruction d'accès mémoire va dans l'unité mémoire, dans la voie spécialisée dans les accès mémoire. Une instruction de calcul va dans la voie spécialisée dans les calculs entiers simples, à savoir l'ALU entière. Et ainsi de suite. L'envoi d'une instruction/micro-opération dans une voie s'appelle l'émission. On dit qu'une instruction est émise quand elle est envoyée dans une voie.

Sur les processeurs dits à simple émission, une instruction est envoyée dans une voie à chaque cycle, soit dans une ALU, soit dans l'unité mémoire, soit dans les voies pour les branchements, etc. Il s'agit des processeurs avec un pipeline simple, basique, sans optimisation particulières. Diverses optimisations comme le renommage de registres et l'exécution dans le désordre permettent de se rapprocher de ce rythme de croisière d'une instruction lancée par cycle.

Mais il existe des processeurs à émission multiple qui sont capables d'émettre plusieurs instructions à la fois, chacune dans des voies séparée. Les processeurs dits superscalaires sont dans ce cas, mais ils ne sont pas les seules. Ils permettent de gagner en performance en utilisant au maximum les unités de calcul/voies. Si plusieurs unités de calcul sont inoccupées, un processeur à émission multiple pourra lancer une instruction dans chacune d'entre elle en même temps, ce qui permet de les occuper le plus vite possible. De moins, c'est le cas si les conditions adéquates sont réunies, mais laissons cela pour plus tard. Un chapitre entier sera dédié aux processeurs à émission multiple.

Les instructions multicycles sur les pipelines

Passons maintenant à une distinction entre trois sous-types de pipelines, qui distingue les pipeline 1-cycle, multicycle et dynamiques. La distinction porte sur l'implémentation des instructions multicycle, à savoir des instructions qui mettent plusieurs cycles à s'exécuter, et donc le nombre de cycles varie suivant l'instruction. Les instructions multicycles ne semblent pas vraiment coller avec un pipeline, qui a une longueur fixe. On s'attend à ce qu'il ait un nombre fixe d'étages, qui font chacun un cycle d’horloge. Mais implémenter les instructions multicycles sur un pipeline est possible, ce qui donne les trois possibilités mentionnées plus haut.

Les pipelines de longueur fixe et variable

La première distinction est celle entre les pipelines de longueur fixe et les pipelines de longueur variable. Sur les pipelines de longueur fixe, toutes les instructions prennent le même nombre d'étages, donc le même nombre de cycles d'horloge. A l'opposé, les pipelines de longueur variables gèrent des instructions qui sont plus longues que d'autres : certaines utilisent l'ALU durant un cycle, d'autres pendant 5 cycles, etc. Intuitivement, on se dit que les pipelines de longueur fixe ne gèrent pas les instructions multicycle, qui sont le domaine réservé des pipelines dynamiques. Mais comme nous allons le voir, c'est faux.

Une seconde distinction fait 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.

Ils sont opposés aux pipelines multicycles, qui sont de longueur fixe, mais gèrent les instructions multicycles. Ils ont une particularité : toutes les instructions s'exécutent en plusieurs cycles, le nombre de cycles est le même pour toutes les instructions. Par exemple, on peut imaginer un processeur pipeliné où les additions, multiplications et décalages font tous 5 cycles.

Pour résumer, il y a trois types de pipelines :

• Les pipelines 1-cycles où toutes les instructions s’exécutent en un cycle.
• Les pipelines multicycle où toutes les instructions s’exécutent en plusieurs cycles, le nombre de cycles est le même pour toutes les instructions.
• Les pipelines dynamiques où toutes les instructions ont des nombres de cycles variables.

	Pas d'instructions multicycles	Support des instructions multicycles
Pipeline de longueur fixe	Pipeline 1-cycle	Pipeline multicycle
Pipeline de longueur variable		Pipelines de longueur variable

La relation entre nombres d'avals et type du pipeline

Il y a une relation assez vague entre les trois types de pipelines vus précédemment, et le nombre d'avals. Peut-être avez-vous pensé que l'usage de plusieurs avals est le fait des pipelines dynamiques. Mais dans les faits, les trois types de pipelines peuvent utiliser plusieurs avals. Par contre, les pipelines dynamiques ont forcément plusieurs avals.

	Présence de plusieurs avals
Pipeline 1-cycle	Assez fréquent, dépend du processeur
Pipeline multicycle	Très fréquent, Dépend du processeur
Pipeline dynamique	Systématique

Les pipelines dynamiques utilisent des avals séparés, avec une unité de calcul par aval. Le temps de calcul dépend de l'ALU, et donc le nombre de cycles de l'instruction associée. Les pipelines dynamiques ont presque systématiquement plusieurs avals, les contre-exemples étant tellement rares qu'il vaut mieux ne pas en parler.

Pipeline avec un nombre variable d'étages par instructions.

Les pipelines multicycles sont similaires aux pipelines dynamiques, à savoir qu'ils disposent de plusieurs ALU aux temps de calcul différents. Les unités de calcul fournissent leur résultat dès que possible, mais l'enregistrement du résultat dnas le registre de destination est retardé de quelques cycles d'horloge. Le retard ajouté à la suite de l'ALU est calibré de manière à ce que toutes les instructions fassent le même nombre de cycles.

Processeur à pipeline multicycles.

Sur un processeur 1-cycle, il est possible d'utiliser des avals séparés. Par exemple, un processeur de ce type peut avoir plusieurs unités de calcul séparées. Une ALU qui est un additionneurs-soustracteur, une autre qui est un barrel shifter, une autre qui sert à faire des comparaison. L'exemple est assez limité, mais quelques processeurs MIPS assez ancien avaient une implémentation similaire.

Les accès mémoire et le pipeline

Il faut préciser que les accès mémoires sont pris en compte quand on parle des trois types de pipelines, mais d'une manière quelque peu subtile. Un pipeline 1-cycle a des accès mémoires qui font 1 cycle. C'est possible si la mémoire est très rapide et le processeur peu puissant. Une autre possibilité est que c'est le cache qui doit répondre en 1 cycle d'horloge, pas la mémoire RAM. Les défauts de cache sont alors gérés à part, en prenant autant de cycles que nécessaire.

Dans le monde réel, les accès mémoire prennent plus d'un cycle, même pour les accès au cache. Un accès au cache L1 peut prendre deux à trois cycles d’horloge, une latence qui n'est pas compatible avec un pipeline 1-cycle. Les pipelines multicycles autorisent le cache à répondre en plusieurs cycles d'horloge, et les défauts de cache sont encore une fois gérés à part. Ils gérent bien le cas d'un processeur avec un cache unique.

Les processeurs modernes incorporent une hiérarchie de mémoires caches, aux latences diverses. Un accès au cache L1 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 sont variables, ce qui ne colle pas avec un pipeline avec un nombre fixe d'étapes ! Par contre, les pipelines dynamiques gèrent des accès mémoire de longueur variable, qui prennent autant de temps que possible. Ils sont très adapté aux processeurs modernes, avec dune hiérarchie de cache qui rend le temps d'un accès mémoire imprévisible.

Toujours est-il que la gestion des accès mémoire est assez complexe avec un pipeline. Un chapitre entier sera dédié aux accès mémoires sur un pipeline.

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. Un exemple de dépendance serait le cas où une instruction a comme opérande le résultat d'une instruction précédente. L'instruction précédente doit avoir enregistré son résultat dans les registres avant que la seconde lise ses opérandes dans les registres. Et avec un pipeline, il se peut que ce ne soit pas le cas, si les deux instructions sont consécutives.

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, que nous décrirons dans la suite du chapitre. Pour résumer d'une manière très succincte :

• Les dépendances de données surviennent quand deux instructions manipulent le même registre ou la même adresse mémoire.
• Les dépendances structurelles surviennent quand deux instructions veulent utiliser le même circuit en même temps.
• les dépendances de contrôle sont liées aux branchements et aux interruptions.

Nous allons les voir en détail. Mais avant ça, nous allons devoir parler rapidement de comment le processeur réagit face à une dépendance. Qu'il s'agisse d'une dépendance de données, structurelle ou de certaines dépendances de contrôle, le processeur peut souvent résoudre la situation avec ce qui s'appelle des bulles de pipeline. Voyons cela en détail.

L'émission d'une instruction et les bulles de pipeline

Les dépendances imposent qu'une première instruction soit totalement terminée avant qu'on démarre la seconde. Le moyen le plus simple pour corriger les problèmes liés aux dépendances est donc assez intuitif. Il suffit 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é avant de démarrer, il se peut qu'elle soit retardée durant quelques cycles pour cela.

La mise en attente des instructions se fait dans ou après l'unité de décodage. Les processeurs avec un pipeline détectent les dépendances entre instructions dans un circuit spécialisé, appelé l'unité d'émission. Elle est parfois fusionnée avec l'unité de décodage d'instruction, mais nous allons surtout étudier le cas où elle est séparée. Si une instruction a une dépendance bloquante, elle est bloquée dans l'étage d'émission en attendant de pouvoir s'exécuter. Durant ce temps d'attente, on insère des vides après l'unité d'émission : certains étages seront inoccupés et n'auront rien à faire. Ces vides sont appelés des calages (stall), ou bulles de pipeline (pipeline bubble).

Pipeline bubble

Le terme "émission" reviendra souvent dans la suite du cours. On dira qu'une instruction est émise si elle est envoyée au chemin de donnée, qu'elle quitte l'unité d'émission. Une instruction peut être émise si elle n'a pas de dépendance bloquante, qu'elle peut s'exécuter. Elle rentre alors dans le chemin de donnée, lit ses opérandes et s'exécute. L'unité d'émission est donc la toute fin de l'unité de contrôle, du séquenceur, c'est le point d'entrée du chemin de données.

Sur les processeurs dit à émission dans l'ordre, le blocage des instructions dépendantes bloque tout le pipeline. Les étages qui précédent l'unité d'émission sont bloqués en empêchant l'horloge d'arriver aux étages antérieurs au décodage. Les instructions ne progressent pas dans le pipeline tant que la dépendance bloquante n'est pas résolue. Mais il existe des processeurs qui incorporent une optimisation appelée l'émission dans le désordre, qui permet de ne pas bloquer les instructions dans l'étage d'émission. Les instructions bloquées sont mises en attente dans une mémoire tampon, alors que celles sans dépendances s'exécutent immédiatement. Le problème est que les instructions s'exécutent dans le désordre, d'où le nom de la technique.

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 dépendances structurelles : l'occupation de chaque voie

En théorie, une fois qu'une instruction est décodée, elle est envoyée dans la voie adaptée. Du moins, si cette voie est libre. En effet, l'usage d'instructions multicycles fait qu'une voie peut être occupée pendant plusieurs cycles. 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

Si plusieurs instructions consécutives veulent utiliser la même voie, la même ALU, ce ne sera pas possible. La voie sera occupée par la première instruction, les autres devront attendre que la première ait terminé ses calculs. 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. Face à une dépendance structurelle, l'unité d'émission met la seconde instruction en attente, tant que la première instruction est en cours. L'unité d'émission émet des bulles de pipeline si le processeur utilise l'émission dans l'ordre.

En théorie, il est possible de concevoir le pipeline de manière à éliminer des dépendances structurelles. Une solution simple est de dupliquer la voie fautive. Prenons un exemple où c'est le circuit multiplieur qui est fautif, où 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. Mais dupliquer des circuits a un cout en transistors qui peut être prohibitif, surtout que le gain en performance est généralement faible. 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.

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 échelonné 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 instructions multicycles se suivent dans un programme. La seule exception étant les instructions mémoire, mais nous les mettons à part pour le moment. En conséquence, les dépendances structurelles ont un cout en performance assez mineur. Cela ne sert donc à rien d'utiliser beaucoup de transistors pour les résoudre, ce qui fait que les unités de calcul sont rarement dupliquées. Par contre, échelonner un circuit permet un gain de performance pour un cout en circuit modéré : il suffit d'ajouter quelques registres dans le circuit.

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.

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. Pour être plus précis, deux instructions ont une dépendance de données quand elles accèdent (en lecture ou écriture) à la même donnée, c'est à dire au même registre ou la même adresse mémoire. En tout, cela fait quatre possibilités :

• Read after read : Deux instructions lisent la même donnée, mais pas en même temps.
• Read after write : Une instruction a pour opérande le résultat d'une autre : la première lit le résultat écrit par la seconde.
• Write after write : Deux instructions écrivent dans le même registre ou la même adresse mémoire, dans un certain ordre.
• Write after read : Une instruction lit une donnée qui est modifiée ultérieurement par une autre instruction.

Pour les dépendances Read after read, on peut mettre les deux instructions dans n'importe quel ordre, cela ne pose aucun problème. Ce ne sont pas de vraies dépendances et je les présente par pur souci d'exhaustivité. Par contre, ce n'est pas le cas avec les trois autres types de dépendances, qui imposent que la première instruction s'exécute avant la seconde, au moins partiellement. Elle doit terminer son exécution, avant que la seconde soit démarrée. Quand on parle de "terminer" ou de "démarrer", on fait référence aux lectures et écritures effectuées par l'instruction. Voici comment sont gérées les trois types de dépendances :

• Read after write : La première instruction doit écrire son résultat avant que la seconde le lise.
• Write after write : La première instruction doit écrire son résultat avant la seconde.
• Write after read : La première doit effectuer la lecture avant que la seconde n'écrive, n'écrase la donnée lue.

Pour simplifier les explications, nous allons appeler ces trois dépendances : dépendances RAW, WAR et WAW. On comprend facilement qu'en cas de dépendance RAW/WAW/WAR, la seconde instruction doit être plus ou moins retardée suivant la dépendance. Avec une dépendance RAW, la première instruction doit être totalement terminée avant que la seconde démarre. Mais pour les dépendances WAW et WAR, la seconde instruction peut démarrer avant que la première soit finie, elle doit simplement être retardée d'une manière ou d'une autre. Par exemple, avec une dépendance WAR, il suffit de retarder l'écriture de la seconde instruction tant que la première n'a pas fait sa lecture. Avec une dépendance WAW, là encore, il suffit de retarder l'écriture de la seconde instruction tant que la première instruction n'est pas terminée.

Une autre distinction sépare les dépendances de registre et les dépendances d'adresse. Une dépendance de donnée survient quand deux instructions lisent/écrivent le même registre ou la même adresse mémoire. Et c'est là qu'une petite subtilité survient, car les accès mémoire se distinguent des autres instructions. Dans la suite du cours, nous allons supposer une architecture LOAD-STORE dans la plupart des cas. Une telle architecture a une séparation stricte entre accès mémoire et les autres instructions. Les accès mémoire regroupent les instructions LOAD et STORE, qui se distinguent des autres instructions. Pour simplifier, les autres instructions seront appelées des opérations, ou encore des instructions de calcul.

Les dépendances de registre surviennent quand deux instructions lisent ou écrivent le même registre. Le cas typique est celui où une instruction lit un registre et qu'une autre écrit dedans, mais il faut aussi tenir compte du cas avec deux écritures dans le même registre. Intuitivement, on se dit que de telles dépendances concernent les opérations, qui lisent leurs opérandes depuis les registres et écrivent un résultat dans un registre de destination, du moins sur les architectures LOAD-STORE. Elles effectuent donc leurs lectures et écritures dans les registres, et seulement ceux-ci, aucune adresse mémoire n'est impliquée. Mais les instructions d'accès mémoire peuvent avoir des dépendances de registre avec d'autres instructions.

L'instruction STORE lit ses opérandes dans des registres opérande (donnée à écrire et adresse), et écrit dans une adresse mémoire. Elle a donc potentiellement des dépendances de registre, à cause des registre opérande. Si une autre instruction lit/écrit ces registres opérandes, une dépendance de registre survient.

L'instruction LOAD est dans un cas similaire, mais avec encore plus de dépendances. Elle récupère l'adresse à lire dans un registre opérande (la plupart du temps), lit une adresse mémoire et écrit la donnée lue dans un registre de destination. Elle a deux sources de dépendances de registre : une avec le registre opérande, une avec le registre de destination. Si une instruction de calcul ou une autre instruction mémoire lit/écrit dans ces registres, une dépendance de donnée a lieu.

Les dépendances d'adresse surviennent quand deux instructions mémoire lisent/écrivent dans une même adresse mémoire. Là encore, on a le cas des dépendances RAW, WAW et WAR. De telles dépendances demandent que le pipeline puisse gérer plusieurs accès mémoire simultanés, ce qui est le cas sur certains pipelines complexes. Mais pour le moment, sachez que nous ne ne pouvons pas en parler car il nous manque quelques bases. Sachez que nous aborderons le sujet dans le chapitre sur la désambiguïsation mémoire.

Un point important est que la gestion des dépendances est différente entre les dépendances de registre et les dépendances d'adresse. Détecter une dépendance de registre demande de comparer les registres utilisés par deux instructions. Par contre, détecter les dépendances d'adresse demande de comparer les adresses lues/écrites. Et autant les registres lus/écrit sont connus dès que l'instruction est décodée, autant les adresses sont souvent calculées à l'exécution ou mémorisées dans des registres. Les deux types de dépendances sont donc le fait de circuits séparés, qui sont dans des étages de pipeline distincts. La gestion des dépendances d'adresse est le fait de l'unité d'accès mémoire, les autres dépendances sont gérées pendant/après l'étape de décodage d'instruction. Aussi, il est important de séparer les deux le plus possible.

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.