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 ! modifier

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

 
Pipeline : principe.

Pour comprendre ce que cela signifie, comparons l’exécution de cette instruction sans et avec pipeline. Pour l'exemple, nous allons utiliser une organisation relativement générale, où chaque instruction passe par les étapes suivantes :

  • chargement : on charge notre instruction depuis la mémoire ;
  • décodage : décodage de l'instruction ;
  • exécution : on exécute l'instruction ;
  • accès mémoire : accès à la mémoire RAM ;
  • enregistrement : si besoin, le résultat de l’instruction est enregistré en mémoire.

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.

L'isolation des étages du pipeline modifier

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. Il est donc impossible de réutiliser un circuit dans plusieurs étapes, comme on le fait dans certains processeurs sans pipeline. 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. De même, l'étage de chargement peut entrer en conflit avec d'autres étages pour l'accès à la mémoire ou au cache, notamment pour les instructions d'accès mémoire. On peut résoudre ce conflit entre étage de chargement et étage d’accès mémoire en dupliquant le cache L1 en un cache d'instructions et un cache de données.

Et ce principe est général : il est important de séparer les circuits en charge de chaque étape. 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.

Les pipelines synchrones et asynchrones modifier

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

La performance théorique d'un pipeline modifier

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) modifier

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. Ceux-ci ont un temps de propagation non-nul, et ont donc un effet sur la fréquence et sur la latence des instructions. Pour simplifier les calculs, nous allons négliger le temps de propagation de ces 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.

La fréquence avec et sans pipeline modifier

La fréquence du processeur augmente avec un pipeline, comparé à la fréquence du même processeur mais sans pipeline. Mieux : elle augmente d'autant plus que le nombre d'étages est important. 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. Et pour un pipeline à N étages, la fréquence est multipliée par à peu-près N. Pour comprendre pourquoi, démontrons-le avec des mathématiques très simples.

Sur un processeur sans pipeline, on suppose que l'instruction met un cycle d'horloge à l’exécuter (pour simplifier). La fréquence du processeur est donc l'inverse du temps d’exécution de l'instruction, soit :

 , avec t le temps d’exécution d'une instruction (sans pipeline).

Sur un processeur avec pipeline, le temps de latence d'un étage est égal, par définition, à la durée d'un cycle d'horloge. La fréquence est l'inverse de cette durée, ce qui fait qu'elle vaut :

 , avec   le temps de propagation d'un étage du pipeline.

Le temps de propagation d'un étage de pipeline est naturellement plus faible que le temps de propagation d'un processeur complet. Pas étonnant donc que la fréquence avec un pipeline soit plus grande. Maintenant, supposons que les étages aient un temps de propagation équilibré, à savoir identique pour tous les étages. Avec cette hypothèse, le temps de propagation d'un étage est donc égal au temps d’exécution d'une instruction, divisée par le nombre d'étage N. On a donc :

 , avec t le temps d’exécution d'une instruction (sans pipeline) et N le nombre d'étages.

En combinant les trois équations précédentes, on a :

 

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.

Le temps d’exécution ne change pas avec un pipeline idéal modifier

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 ou sans pipeline (idéal, sans compter l'influence des registres entre les étages). Et si cela parait incompatible avec l'augmentation de la fréquence, ça ne l'est pas après une analyse minutieuse. En effet, la fréquence est multipliée par N, mais cela est compensée par le fait que l'instruction prend N étages pour s’exécuter, et donc N cycles d'horloge. L’augmentation de la fréquence est donc compensée par le fait qu'il faut plusieurs cycles d'horloge pour exécuter une instruction.

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

Sur un pipeline, une instruction doit passer par   étages pour s’exécuter. Son temps d’exécution total est donc :

 , avec   le temps d’exécution de l’instruction avec pipeline en secondes.

On utilise alors la formule  , vue plus haut :

 , avec t le temps d’exécution d'une instruction sans pipeline.

Pour résumer, le temps d’exécution d'une instruction ne change pas : l'augmentation de la fréquence compense l'augmentation du nombre d'étages.

Une autre manière de voir les choses est de partir de l'équation suivante, qui donne le temps d’exécution d'une instruction en fonction du nombre de cycle d'horloge qu'elle met pour s’exécuter (le CPI - cycles per instruction).

 

Avec un pipeline, la fréquence est multipliée par N, mais le CPI est aussi multiplié par N. Au final, les deux se compensent et le temps d’exécution reste identique.

 

Le nombre d'instructions par secondes modifier

Maintenant, nous allons voir quel est l'impact d'un pipeline sur le nombre d'instructions par secondes, abrévié IPS. Pour rappel, nous avions vu dans le chapitre sur la performance d'un ordinateur que cette unité correspond au nombre d'instructions que le processeur peut exécuter chaque seconde. Pour un processeur sans pipeline, celui-ci est égal à :

 

Mais sur un processeur avec un pipeline, on peut charger une nouvelle instruction à chaque cycle d'horloge, ce qui donne une instruction dans chaque étage. Les équations précédentes doivent donc être multipliée par N, ce qui donne :

 

On voit que la puissance de calcul a été multipliée par le nombre d'étages du pipeline. Par contre, le fait que plusieurs instructions puisse s’exécuter en même temps augmente les performances : si la latence reste la même, le débit du processeur augmente. Dit autrement, l'augmentation en performance provient de l'augmentation de l'IPC, le nombre d'instructions par cycle d'horloge. Plus un pipeline a d'étage, plus sa puissance de calcul théorique maximale est importante.

La performance d'un pipeline non-idéal, avec des registres inter-étages modifier

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

 

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.

 

La fréquence du processeur est l'inverse de  , ce qui donne :

 

Le débit, à savoir le nombre d'instructions exécutées par secondes, s'exprime à partir l'équation précédente. Pour un processeur sans pipeline, ce débit est simplement égal à  . Le pipeline peut exécuter   instructions en même temps, ce qui multiplie le débit par  , ce qui donne :

 

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

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. Mais dans tous les cas, l'usage d'un pipeline permet au mieux de multiplier la fréquence par le nombre d'étages. 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. 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.

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

Les pipelines de longueur fixe modifier

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. Dans ce qui va suivre, nous allons utiliser une organisation relativement générale, où chaque instruction passe par les é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 : si besoin, les opérandes sont lus depuis la mémoire ou les registres ;
  • exécution: exécution de l'instruction ;
  • accès mémoire : accès à la mémoire RAM ;
  • enregistrement : si besoin, le résultat de l’instruction est enregistré en mémoire.

L'étage de PC gère le program counter. L'étage de chargement utilise l'interface de communication avec la mémoire. L'étage de décodage contient l'unité de décodage d'instruction. L'étage de lecture de registre contient le banc de registres. L'étage d'exécution contient l'ALU, l'étage d’accès mémoire a besoin de l'interface avec la mémoire et l'étage d’enregistrement a besoin des ports d'écriture du banc de registres. Naïvement, on peut être tenté de relier l'ensemble de cette façon.

 
Pipeline à 7 étages naïf.

Le chemin de données modifier

Toutes les instructions n'ont pas besoin d’accéder à la mémoire, tout comme certaines instructions n'ont pas à utiliser l'ALU ou lire des registres. Par exemple, certaines instructions n'ont pas besoin d’accéder à la RAM : on doit donc court-circuiter l'étage d’accès mémoire. De même, l'ALU aussi doit être court-circuitée pour les opérations qui ne font pas de calculs. En clair, certains étages sont « facultatifs » pour certaines instructions. L'instruction doit passer par ces étages, mais ceux-ci ne doivent rien faire, être rendus inactifs. Pour inactiver ces circuits, il suffit juste que ceux-ci puisse effectuer une instruction NOP, qui ne fait que recopier l'entrée sur la sortie. Pour les circuits qui ne s'inactivent pas facilement, on peut les court-circuiter en utilisant diverses techniques, la plus simple d'entre elle consistant à utiliser des multiplexeurs.

 
Inactivation d'un étage de pipeline avec des multiplexeurs.

La lecture dans les registres peut être court-circuitée lors de l'utilisation de certains modes d'adressage. C'est notamment le cas lors de l'usage du mode d'adressage absolu. Pour le gérer, on envoie l'adresse fournie par l'unité de décodage sur l’entrée d'adresse de l'interface de communication avec la mémoire. Le principe est le même avec le mode d'adressage immédiat, sauf que l'on envoie une constante sur une entrée de l'ALU. On peut aller relativement loin comme cela.

L'illustration ci-dessous montre ce que peut donner un pipeline MIPS à 5 étages qui gère les modes d'adressage les plus courants.

 
MIPS Architecture (Pipelinée)

Les signaux de commande modifier

Les signaux de commande qui servent à configurer le chemin de données sont générés par l'unité de décodage, dans le second étage du pipeline. Comment faire pour que ces signaux de commande traversent le pipeline ? 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.

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

Les pipelines de longueur variable modifier

Avec un pipeline de longueur fixe, toutes les instructions ont le même nombre d'étages, les étages inutiles étant court-circuités ou inactivés. Par exemple, si je prends une instruction qui effectue une addition entre deux registres, un des étages ne servira à rien : l'étage MEM. Normal, notre instruction n'accédera pas à la mémoire. Et on peut trouver beaucoup d'exemples de ce type. Par exemple, si je prends une instruction qui copie le contenu d'un registre dans un autre, ai-je besoin de l'étage d'Exec ou de MEM ? Non ! En clair : c'est un peu du gâchis. Si on regarde bien, on s’aperçoit que ce problème de nombre de micro-opérations variable vient du fait qu'il existe diverses classes d'instructions, qui ont chacune des besoins différents.

Sur un processeur non pipeliné, on peut éviter ces étapes inutiles en faisant varier le nombre de micro-opérations par instruction, certaines instructions pouvant prendre 7 cycles, d'autres 9, d'autres 25, etc. Il est possible de faire la même chose sur les processeurs pipelinés, dans une certaine limite, en utilisant plusieurs pipelines de longueurs différentes. Avec cette technique, le pipeline du processeur est décomposé en plusieurs parties. La première partie, l’amont (front end), prend en charge les étages communs à toutes les instructions : la mise à jour du program counter, le chargement, l'étage de décodage, etc. L'amont est suivi par le chemin de données, découpé en plusieurs unités adaptées à un certain type d'instructions, chacune formant ce qu'on appelle un aval (back end). Un aval est spécialisé dans une classe d'instructions : un pour les instructions arithmétiques et logiques, un autre pour les opérations d'accès mémoire, un autre pour les instructions d'échange de données entre registres, et ainsi de suite.

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

La longueur de l’aval peut varier suivant le type d'instructions.

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

Les pipelines variables des processeurs load-store modifier

Les processeurs load-store peuvent se contenter de deux avals : un pour les accès mémoire et un pour les calculs.

 
Pipeline à deux aval de type load-store.

On peut aussi utiliser une unité de calcul séparée pour les instructions de tests et branchements.

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

Il est possible de scinder les avals précédents en avals plus petits. Par exemple, l'aval pour les instructions arithmétiques peuvent être scindés en plusieurs avals séparés pour l'addition, la multiplication, la division, etc. Niveau accès mémoire, certains processeurs utilisent un aval pour les lectures et un autre pour les écritures.

Mais la séparation des avals n'est pas optimale pour les instructions qui se pipelinent mal, auxquelles il est difficile de leur créer un aval dédié. C'est notamment le cas de la division, dont les unités de calcul ne sont jamais totalement pipelinées, voire pas du tout. Il n'est ainsi pas rare d'avoir à gérer des unités de calcul dont chaque étage peut prendre deux à trois cycles pour s’exécuter : il faut attendre un certain nombre de cycles avant d'envoyer une nouvelle instruction dans l’aval.

Les pipelines variables des processeurs non load-store modifier

Les modes d'adressage complexes se marient mal avec un pipeline, notamment pour les modes d'adressages qui permettent plusieurs accès mémoire par instructions. Une méthode possible est de découper les instructions machines à mode d'adressage complexes en une suite de micro-instructions directement exécutables par le pipeline. Il va de soi que cette organisation complique pas mal le fonctionnement du séquenceur.

Les optimisations du pipeline modifier

Sur certains pipeline, des optimisations permettent de se passer de certains étages du pipeline. Par se passer de certains étages, on veut dire que certaines instructions ne passeront pas par certaines étages, ce qui rend leur exécution plus rapide. Le cas d'étude le plus impressionnant est celui du loop stream detector, présent sur les processeurs Intel depuis la micro-architecture Skylake.

Le Loop Stream Detector modifier

Le loop stream detector détecte certaines boucles et les conserve dans un cache situé tôt dans le pipeline. L'intérêt de ce cache est qu'il permet d'éviter que les instructions de la boucle soient chargées et décodées plusieurs fois de suite. Les instructions de la boucle sont lues dans le cache de boucle et sont injectées directement dans la suite du pipeline, dans le back-end. Le fait de ne pas avoir à charger et décoder des instructions fait que le processeur consomme moins d'énergie, sans compter qu'on peut avoir un gain en performance du fait du raccourcissement du pipeline. Le gain est d'autant plus important si les instructions ont un encodage complexe, ou si les instructions sont à longueur variable. Globalement, plus le chargement et le décodage sont complexes, plus le loop stream detector fait des merveilles.

Le cache en question est situé soit après l'étage de chargement (fetch), soit après l'étape de décodage. Il était présent entre l'étage de chargement et de décodage sur les processeurs Core 2, mais est passé après l'étage de décodage sur les processeurs ultérieurs. S'il est situé après l'étage de chargement, il contient les instructions de la boucle, avant qu'elles soient décodées. Mais s'il est placé après l'étage de décodage, il contient les micro-instructions qui constituent la boucle. Évidemment, la taille du loop stream detector n'est pas infinie, comme pour tout cache. Le cache ne peut contenir qu'un nombre limité d'instruction, ce qui fait qu'il ne fonctionne que pour des boucles de petite taille. D'après la documentation d'Intel, le cache ne peut contenir que 18 instructions pour le processeur Core, 28 micro-instructions sur les processeurs Core i7. Il y a aussi des contraintes quant au nombres de branchements à l'intérieur de la boucle et le nombre d'accès mémoire.

Dans les deux cas, l'étage de chargement peut être éteint, les branchements non-alignés ne posent plus de problèmes de performance, et il est même possible qu'une partie du cache d'instruction puisse être éteint temporairement. Mais les deux solutions ont des avantages et inconvénients. Si le cache est placé après l'étage de chargement, les instructions doivent quand même être décodées, ce qui réduit les gains en consommation énergétique et en performance. À l'inverse, mettre le cache après l'étage de décodage fait que les instructions ne doivent plus être décodées et renommées fait que le front-end du pipeline peut être complètement éteint, ce qui entraîne un gain important en performance et en consommation d'énergie. Le gain est d'autant plus important si le programme utilise des instruction micro-codées ou des instructions complexes à décoder comme les instructions de longueur variable. D'un autre coté, l'encodage des instructions est plus compact que la ou les micro-instruction équivalente, ce qui fait que le cache est plus petit s'il est placé avant l'étage de décodage, ce qui entraîne un gain de circuits et de place, et réduit un petit peu la consommation énergétique du cache.