Fonctionnement D'un Ordinateur/Le Pipeline - Wikilivres

Dans ce chapitre, nous allons voir la technique du pipeline d'instruction, qui est utilisée sur tous les processeurs modernes. L'introduction du pipeline a eu lieu sur les premiers mainframes et les supercalculateurs, dans les années 60-70. Elle a ensuite été reprise pour les premiers processeurs RISC commerciaux. Cependant, elle s'est démocratisée aux processeurs CISC modernes. Introduire un pipeline entraine une modification profonde de la microarchitecture du processeur, ainsi que l'ajout de nombreuses optimisations qui ne seraient pas possibles dans pipeline : exécution superscalaire, exécution dans le désordre, prédiction de branchements, etc. Nous passerons une dizaine de chapitre à parler du pipeline des processeurs modernes, ainsi que toutes les techniques qui vont avec.

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

[modifier | modifier le wikicode]

Pour expliquer ce qu'est un pipeline d'instructions, il faut faire un 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, de l'instruction, du mode d'adressage, etc.

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

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.

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

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

Les étages du pipeline

[modifier | modifier le wikicode]

Mettre en oeuvre un pipeline nécessite des modifications profondes de la micro-architecture du 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 avec un pipeline, on ne peut pas se le permettre, chaque étape doit utiliser son propre additionneur. 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.

Le nombre d'étapes par 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 : 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, 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

[modifier | modifier le wikicode]

Il faut que les instructions progressent d'un étage à un autre au rythme adéquat. Pour cela, la plupart des pipelines intercalent des registres entre les étages, pour les isoler mais aussi pour synchroniser leurs échanges. Les registres en question seront appelés des registres de pipeline dans ce qui suit. Un registre de pipeline s'intercale entre deux étages consécutifs. L'étage précédant ce registre écrit son résultat dedans, l'étage suivant lit son contenu quand c'est son tour, généralement au cycle d'horloge suivant.

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.

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.

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.

Les pipelines n'utilisant pas de registres sont assez rares, mais ils existent, ce sont les pipelines à vague. Ils se contentent d'enchainer des étages les uns à la suite des autres, et laissent les données se propager librement d'un étage à l'autre. Ils jouent sur un timing très précis pour propager les données entre étages au bon timing, de manière à ce que le tout fonctionne comme un pipeline. Leur conception est cependant très complexe, ce qui fait qu'ils ne sont jamais utilisés en pratique. La règle est clairement de séparer les étages dans des circuits séparés, interfacés par des registres.

Segmenter un processeur en plusieurs étages de pipeline

[modifier | modifier le wikicode]

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 suit, nous allons voir quelques pipelines simples, faciles à étudier. Ils ont tous un point commun : ils ne gèrent pas les instructions multicycles, qui mettent plusieurs cycles d'horloge pour s'exécuter.

Concrètement, les opérations arithmétiques sont exécutées en un seul cycle d'horloge dans l'ALU. Le processeur ne gère pas d'instruction "complexe" comme les multiplications ou divisions, qui prennent entre 2 et 50 cycles pour s'exécuter. De plus, les accès mémoire se font aussi en un seul cycle d'horloge, par simplicité. On suppose que les accès mémoire se font dans la mémoire cache et que celle-ci est assez rapide pour qu'une lecture/écriture se fasse en un cycle. Nous faisons ces simplifications, car la présence d'instructions multicycles complexifie grandement le pipeline. Un chapitre entier sera dédié aux pipelines qui gèrent les instructions multi-cycle.

Le pipeline Fetch-Exec

[modifier | modifier le wikicode]

En guise de premier exemple, nous allons utiliser une organisation relativement simple, portant le nom de pipeline Fetch-Execute. IL a seulement deux étages : un qui charge et décode l'instruction, l'autre qui exécute l'instruction. En clair, il sépare le séquenceur et le chemin de données dans deux étages séparés. Il 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. Les deux étages sont respectivement nommés Fetch et Exec, ce qui donne son nom au pipeline. Il s'agit du pipeline le plus simple qui soit, mais il a pourtant été utilisé sur les processeurs Atmel AVR, ainsi que les processeurs PIC.

Un problème avec ce pipeline est que les deux étages peuvent parfois faire un accès mémoire en même temps. Le pipeline doit lire une instruction à chaque cycle d'horloge, quelle que 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é. Une solution alternative utiliser un cache unique 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 la même solution est appliquée.

Le pipelining du séquenceur

[modifier | modifier le wikicode]

Le pipeline précédent est de loin le plus simple. Tous les pipelines qui existent ne sont qu'une amélioration de celui-ci. Par amélioration, on veut dire que l'étage de Fetch est découpé en plusieurs sous-étages, idem avec l'étage d'Exec. Cependant, découper le séquenceur ne se fait pas de la même manière que le découpage du chemin de données. Nous allons voir les deux séparément, en commençant par le découpage du séquenceur.

Le pipeline Fetch-Decode-Exec sépare l'unité de chargement de l'unité de décodage d'instruction dans deux étages séparés. Le résultat est un pipeline à trois étages : 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, termes que nous utiliserons dans la suite de ce cours. Encore une fois, ils donnent leur nom au pipeline. Le pipeline est donc le suivant :

• Fetch : chargement de l'instruction ;
• Decode : décodage de l'instruction ;
• Exec : exécute l'instruction.

Bien que très simple, le pipeline Fetch-Decode-Exec a été utilisé dans des processeurs commerciaux grand public. Par exemple, les tout premiers processeurs ARM jusqu'aux processeurs ARM7 utilisaient un pipeline Fetch-Decode-Exec.

La seule difficulté d’implémentation est de séparer l'unité de chargement et le décodeur d'instruction avec un registre. Pour cela, 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 est donc terriblement simple.

Il est possible de scinder l'étape de chargement en deux étapes séparées : la mise à jour du program counter et l'accès au cache d'instruction. La première étape ne fait pas que calculer le program counter, mais gère aussi les branchements au sens large. Elle incorpore des techniques de prédictions de branchement que nous verrons dans le chapitre suivant. En tout cas, elle fait suffisamment de travail pour avoir un étage dédié, le travail prenant facilement un cycle d'horloge complet. Le pipeline devient alors le suivant :

• PC Update : mise à jour du program counter ;
• Fetch : accès au cache d'instruction ;
• Decode : décodage de l'instruction ;
• Exec : exécute l'instruction.

Précisons cependant une chose importante : la gestion des branchements se fait dans plusieurs étages. Le calcul des conditions est réalisé dans l'unité de calcul, donc dans l'étage d'Exec. Mais une fois l'adresse de destination connue, celle-ci doit être écrite dans le program counter en passant à travers des multiplexeurs, multiplexeurs qu'il faut configurer. Et bien ces multiplexeurs et leur configuration est le fait de l'étage de PC Update.

Dans l'exemple précédent, l'accès au cache d'instruction ne prend qu'un seul cycle d'horloge. Mais sur les processeurs modernes, l'accès au cache d'instruction prend deux à trois cycles. Et ce n'est pas incompatible avec la présence d'un pipeline, à condition que le cache lui aussi soit pipeliné. Lire une instruction se fait alors en plusieurs étapes. Nous verrons comment c'est possible dans un chapitre dédié nommé "Le parallélisme mémoire au niveau du cache". Toujours est-il que les processeurs modernes ont un pipeline de 8-20 étages, dont au moins un étage pour le calcul du program counter et 2 à 4 cycles pour l'accès au cache d'instruction.

Il est aussi possible de faire la même chose avec les décodeurs d'instruction. Le décodeur est pipeliné, à savoir scindé en deux ou trois circuits consécutifs, séparés par des registres de pipeline. Et il est même possible de faire la même avec l'étape de calcul du program counter. Pour donner un exemple, le processeur Pentium Pro avait un pipeline de 14 étages, dont 7 étaient liés au décodage/chargement : deux étages pour le calcul du program counter, trois pour l'accès au cache d'instruction, deux pour le décodage des instructions.

Les processeurs modernes implémentent de nombreuses optimisations, qui partent du principe que le calcul du program counter, l'accès au cache d'instruction, et le décodage sont trois étapes séparées. Mais nous verrons cela en temps voulu, dans le chapitre nommé "Les optimisations du chargement des instructions". Pour le moment, retenez que le début du pipeline peut être scindé en trois étapes nommées PC, Fetch et Decode, qui peuvent elles-mêmes être séparées en sous-étapes pipelinées.

Le pipelining du chemin de données

[modifier | modifier le wikicode]

Les pipelines précédents sont très simples à comprendre, car ils collent avec la séparation entre Program counter, unité de chargement, décodage et chemin de données, qui nous est familière. Les pipelines qui vont suivre pipelinent leur chemin de données, d'une manière qui est moins intuitive. Autant découper le séquenceur en plusieurs circuits séparés est simple, autant découper le chemin de données ne l'est pas. Pour simplifier, nous allons prendre le cas d'un processeur RISC, pour éliminer les instructions load-op, qui sont particulièrement problématiques avec un pipeline.

Le chemin de données contient au minimum une unité de calcul, un banc de registres et l'unité mémoire (et un paquet d'interconnexion qu'on met sous le tapis). Intuitivement, on se dit qu'il faudrait leur donner un étage chacun, et ce n'est pas une mauvaise idée. La seule subtilité est que le banc de registre est multiport, avec des ports de lecture et d'écriture séparés.. De plus, ils ne sont pas utilisés en même temps : la lecture des opérandes se fait en premier, puis les calculs/accès mémoire, et enfin l'enregistrement du résultat dans les registres. Le chemin de données est alors découpé en quatre étapes :

• Read Operands (RO) : lecture des opérandes dans les registres ;
• Execution (EXEC) : exécution d'un calcul dans l'unité de calcul ;
• Memory (MEM) : accès mémoire dans l'unité mémoire, facultatif ;
• Writeback (WB) : enregistrement d'une donnée dans les registres.

Cependant, il faut tenir compte d'un détail : il y a des instructions qui n'utilisent pas l'unité de calcul, d'autres qui n'utilisent pas l'unité mémoire. Par exemple, sur un processeur RISC, les instructions arithmétiques n'utilisent pas l'unité mémoire. Et c'est pareil pour les branchements, les copies entre registres, etc. L'étage MEM est donc facultatif, seules les instructions LOAD et STORE l'utilisent. Les autres instructions doivent traverser cet étage, mais l'étage ne doit rien faire. L'étage MEM doit juste propager le résultat de l'ALU d'un registre de pipeline vers le suivant. Pour cela, il faut ajouter un multiplexeur qui choisit entre : la sortie de l'unité mémoire, le registre de pipeline précédent.

L'unité mémoire n'est pas la seule dans ce cas. Par exemple, certaines instructions mémoire n'utilisent pas l'ALU entière. L'exemple type est l'instruction MOV qui copie un registre dans un autre. Ou encore, les instructions LOAD et STORE avec certains modes d'adressage, qui ne demandent pas de calculer des adresses. Ce genre de situation se règle en effectuant un NOP dans l'unité de calcul. Si on a besoin que l'ALU ne fasse rien, on lui demande de faire un NOP. Le pipeline devient alors le suivant :

Un avantage de ce pipeline est qu'il implémente certains modes d'adressage très facilement. Les modes d’adressage en question demandent de faire des calculs d'adresse. Par exemple, les modes d'adressage indicés demandent de calculer une adresse à partir d'une adresse de base et d'un indice, pour ensuite faire un accès mémoire. Les instructions mémoire avec calcul d'adresse sont alors implémentées simplement : le calcul d'adresse est réalisé dans l'unité de calcul, puis l'étage suivant s'occupe de l'accès mémoire.

Le cas des instructions LOAD dépend du mode d'adressage utilisé.

• Les modes d'adressage indicés demandent de calculer une adresse à partir d'une adresse de base et d'un indice, pour ensuite faire un accès mémoire. Le calcul d'adresse est réalisé dans l'unité de calcul entière, puis l'accès mémoire est exécuté par l'unité mémoire. Le pipeline précédent marche à merveille pour les lectures : le premier étage lit l'adresse de base et l'indice, le second calcul l'adresse, le troisième fait la lecture, le dernier enregistre la donnée lue dans les registres.
• Avec le mode d'adressage indirect à registre, l'adresse à lire est lue dans les registres, il n'y a pas de calcul d'adresse. L'unité de calcul est inutilisée, seule l'unité mémoire l'est.
• Avec le mode d'adressage absolu, l'adresse est fournie par le séquenceur, ce qui fait que l'unité de calcul n'est pas utilisée, mais le banc de registre ne l'est pas non plus ! L'étage Read Operands est donc inutile, il ne fait rien.

Le dernier étage enregistre dans les registres : soit la donnée lue en mémoire, soit le résultat fournit par l'ALU. Il regroupe le port d'écriture du banc de registre, et quelques MUX. Et il est facultatif. En effet, l'instruction STORE n'enregistre pas de données dans les registres, contrairement à l'instruction LOAD. Pareil avec les branchements : ils n'enregistrent rien dans les registres et ne font que transmettre leur résultat au séquenceur et au program counter. Le dernier étage est utilisé par les instructions arithmétiques et l'instruction LOAD, mais il ne fait rien pour une instruction STORE ou un branchement.

La propagation des signaux de commande dans le pipeline

[modifier | modifier le wikicode]

Découper le chemin de données demande de placer des registres de pipeline au bon endroit. Les registres propagent les données adéquates, mais aussi les signaux de commande générés par le décodeur, qui configurent le chemin de données. En effet, relier l'unité de décodage aux circuits incriminés directement ne marcherait pas. Les signaux de commande arriveraient immédiatement aux circuits, alors que l'instruction n'a pas encore atteint ces étages ! Les signaux de commande doivent traverser le pipeline et être consommés par les étages adéquats, et doivent donc être propagé d'étage en étage, via les registres de pipeline. Cette méthode sera utilisée sur tous les pipelines où le chemin de données contient plusieurs étages.

Il faut noter que quand on parle de signaux de commande, on parle dans un sens très large. Et cela inclus les constantes immédiates du mode d'adressage immédiat. les constantes sont fournies par le séquenceur et sont propagées d'étage en étage jusqu'à atteindre l'étage avec l'unité de calcul. Il en est de même pour le mode d'adressage absolu, qui fournit une adresse mémoire dans l'instruction. L'adresse est extraite par le décodeur d'instruction, propagée dans le pipeline jusqu'à atteindre l'unité mémoire.

L'optimisation du pipeline de données

[modifier | modifier le wikicode]

Le pipeline vu juste avant est conçu pour être logiques, avec une séparation entre chargement/décodage/exécution/accès au registre qui est relativement intuitive. Mais une implémentation réelle n'aurait pas de bonnes performances, pour diverses raisons. Cependant, le pipeline précédent est un bon point de départ, qu'on peut améliorer. De simples modifications permettent de simplifier grandement le pipeline. Voyons lesquelles.

L'équilibrage du pipeline

[modifier | modifier le wikicode]

Idéalement, il faudrait répartir également le travail entre les étages, mais il y a toujours un étage qui est plus lent que les autres et la durée d'un cycle d'horloge devra se caler sur cet étage. Nous l'appellerons l'étage limitant, terme qui est assez parlent. L'étage limitant est souvent l'étage MEM, vu que les accès au cache de données sont assez lents. Les autres étages peuvent en profiter pour faire plus de travail, afin de se caler sur l'étage limitant.

Il est intéressant de fusionner deux étages consécutifs pour obtenir un étage certes plus lent, mais moins lent que l'étage limitant. Par exemple, il est possible de fusionner l'étage de lecture des opérandes avec l'étage d'exécution. Le banc de registre et l'unité de calcul sont dans l'étage d'exécution. Il s'agit là d'un exemple où l'on regroupe deux opérations qui auraient pu tenir dans un seul étage.

Sans l'optimisation précédente, l'unité de calcul doit caler sa rapidité sur celle d'un cycle d'accès mémoire. Elle peut en profiter pour faire des calculs complexes, comme les multiplication ou divisions. Précisons qu'il y a des pipelines qui gèrent les instructions multi-cycles, tous les processeurs modernes sont dans ce cas-là. Mais ils seront vus dans des chapitres à part. Pour le moment, nous devons nous concentrer sur les pipelines 1-cycle, où toutes les opérations se font en un seul cycle d'horloge.

La mise en parallèle des unités de calcul

[modifier | modifier le wikicode]

Dans la section précédente, on a vu que certains étages sont « facultatifs » pour certaines instructions. Les instructions concernées doivent passer par ces étages, mais ceux-ci ne doivent rien faire. Pourrait-on améliorer le pipeline en rajoutant des interconnexions, pour éliminer des étages facultatifs ? Pas complétement, mais quelques optimisations peuvent aider.

Pour cela, une idée est de déplacer l'unité mémoire dans l'étage d'exécution, afin qu'elle travaille en parallèle de l'unité de calcul. Une instruction arithmétique passe par l'ALU entière, mais n'utilise pas l'unité mémoire. Par contre, une instruction mémoire passe dans l'unité d'accès mémoire et laisse l'ALU entière tranquille. Le chemin de données est alors scindé en trois étages :

• chargement d’opérandes : lecture des opérandes depuis les registres ;
• exécution : exécution de l'instruction dans l'unité de calcul ou l'unité mémoire ;
• enregistrement : écriture du résultat dans les registres.

L'avantage est que l'étage d'exécution est toujours utilisé par n'importe quelle instruction. À la rigueur, les instructions MOV de copie entre registre n'utilisent ni l'unité de calcul ni l'unité mémoire, mais ce n'est pas le cas si l'ALU entière incorpore l'opération pass through qui recopie une entrée sur sa sortie. On a donc éliminé un étage facultatif. Mais n'allez pas croire qu'il s'agit d'une optimisation miracle, elle a quelques défauts qu'on va voir immédiatement.

Un désavantage est l'implémentation des modes d'adressage qui demandent de faire des calculs d'adresse. Les calculs d'adresse ne peuvent pas être fait dans l'ALU entière, vu qu'elle est en parallèle de l'unité mémoire, pas avant elle. La seule solution est d'utiliser une unité de calcul d'adresse dédiée, placée avant l'unité mémoire. L'unité de calcul d'adresse est très simple, plus économe en circuit et plus rapide qu'une ALU entière vraie. Il y a donc une petite duplication de circuit, mais elle est nécessaire si on veut mettre en parallèle l'unité mémoire et l'ALU entière.

Une autre solution demande la coopération du jeu d'instruction. Il faut que le jeu d'instruction ne supporte pas les modes d'adressages indicés. Il peut gérer le mode d'adressage indirect à registre, absolu ou d'autres modes d'adressage qui ne font pas de calcul d'adresse. Dans ce cas, pas besoin d'ajouter une unité de calcul d'adresse, l'unité mémoire est utilisée directement. En soi, ce n'est pas un problème, mais moins pratique pour les programmeurs/compilateurs.

Il faut noter que cette optimisation ne s'applique pas qu'à l'unité mémoire. Il est possible de mettre plusieurs unités en parallèle dans le même étage d'exécution. Par exemple, de nombreux processeurs ont une unité de calcul dédiée aux branchements, qui est placée dans l'étage d'exécution. L'unité est la seule à être reliée au séquenceur, l'unité de calcul normale ne l'est pas. Cela simplifie grandement la conception du processeur, sans impact sur les performances.

Avec trois unités en parallèle, il est possible de les utiliser en même temps. Par exemple, pour exécuter un calcul dans l'ALU entière, pendant que l'unité mémoire fait une lecture/écriture. Une possibilité vient des modes d'adressage à post-incrément. Ils demandent d'incrémenter un pointeur en parallèle d'un accès mémoire. L'incrémentation est faite dans l'ALU pendant que l'accès mémoire a lieu. Pour l'unité de branchement, une possibilité est d'optimiser les branchements relatifs : l'unité pour les branchements fait une comparaison, pendant que l'ALU entière fait l'addition du décalage au program counter.

Le pipeline RISC classique et ses variantes

[modifier | modifier le wikicode]

Les pipelines précédents sont conçus pour être relativement simples et pédagogiques. Mais la plupart des autres cours, notamment les textbooks américains, préfèrent utiliser un pipeline appelé le pipeline RISC classique. Il a été utilisé sur les premiers processeurs RISC : les CPU MIPS, SPARC, le 88000 et quelques autres, des processeurs très influents et très populaire à leur époque. Le pipeline RISC 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é, ou par habitude pédagogique.

Le pipeline RISC classique est cependant loin d'être idéal au niveau pédagogique. Sa simplicité apparente est trompeuse et il a de nombreuses particularités qui ne sont pas évidentes à comprendre. Il permet d'aborder précocement les concepts de dépendances de données/structurelles, mais nous n'utiliserons pas cette approche dans ce cours/wikilivres. Je vais cependant parler du pipeline RISC classique rapidement, ce qui vous sera utile si jamais vous souhaitez consulter d'autres sources, des cours, des articles wiki ou autres.

Il s'agit d'un pipeline à 5 étages, qui met l'ALU et l'unité mémoire dans deux étages consécutifs. Quelques cours utilisent parfois une version simplifiée à 4 étages, qui fusionne l'étage d'exécution et d'accès mémoire. Les 5 étages sont les suivants :

• Instruction Fetch (IF) pour l'étage de Fetch ;
• Instruction Decode (ID) pour l'étage de décodage ;
• Execution (EXEC) pour l'étage d'execution ;
• Memory (MEM) pour l'étage d'accès mémoire ;
• Writeback (WB) pour l'étage d'enregistrement dans les registres ;

Il est conçu pour une architecture RISC, qui gère quelques modes d'adressage mineurs. L'unité de décodage est très simple, elle n'a pas de microcode. C'est nécessaire pour que le décodage se fasse en un seul cycle d'horloge. De plus, les processeurs RISC utilisent des encodages simples, faciles à décoder. Leurs instructions sont de taille fixes, elles étaient toutes codées sur 32 bits sur les processeurs avec ce pipeline.

La lecture des opérandes se fait en parallèle du décodage

[modifier | modifier le wikicode]

Une subtilité est que la lecture des opérandes se fait en parallèle du décodage, et non après. C'est étrange, pas intuitif, et cela complexifie le pipeline. Les raisons derrière ce choix sont multiples, mais nous ne pouvons pas en parler ici. La première est que cela permet d'exécuter les branchements conditionnels en avance. La seconde est une histoire de dépendances structurelles que nous ne pouvons pas aborder ici.

Avec ce choix, l'équilibrage du pipeline n'est pas parfait, vu que l'étage de décodage fait beaucoup de choses. Il faut dire qu'on a fusionné l'étage de décodage avec l'étage Read Operand. Rien qui ne puisse être compensé par l'ajout des multiplications dans l'ALU, ceci dit. Mais le vrai problème est que le décodage devient beaucoup plus compliqué, car il faut extraire des numéros/noms de registre précocement lors du décodage.

Heureusement, le pipeline RISC classique était prévu initialement pour des processeurs MIPS, des processeurs RISC avec un encodage très simple. Le décodage des instructions était très simple, les opcodes étaient tous à la même place, les noms/numéros de registres aussi, on pouvait extraire l'opcode et le noms/numéros de registre au tout début du décodage. Les noms/numéros de registre étaient extraits simplement avec quelques multiplexeurs, puis envoyés au banc de registre pendant que l'unité de décodage finissait son travail. Mais notons que cela ne fonctionne que sur des processeurs RISC, et encore : il faut que l'encodage des instructions soit assez simple pour le permettre. C'est un détail qui ne se généralise pas.

Les branchements, leur exécution et leur décodage

[modifier | modifier le wikicode]

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. Par contre, la gestion des branchements est assez complexe.

Les architectures MIPS peuvent faire un branchement qui s'exécute si deux registres sont égaux. Le calcul d'un branchement demande donc de comparer deux registres, puis de décider s'il faut brancher selon le résultat. Une première possibilité, la plus intuitive, place le comparateur dans l'étage d'exécution. D'autres implémentations utilisent l'unité de calcul entière pour faire la comparaison, ce qui est équivalent.

Une solution alternative exécute la comparaison dans l'unité de décodage, juste après la lecture des registres ! L'avantage de faire ainsi n'est pas évident, mais le deviendra dans le chapitre suivant. Mais cela se fait au prix d'un étage de décodage bien chargé, le pipeline est très déséquilibré. LLe schéma précédent montre un exemple, mais sur une variante 4 étages du pipeline RISC classique.

Un autre détail est que le calcul des branchements relatifs est réalisé dans l'unité de calcul. Quelques processeurs exécutaient les branchements conditionnels dans l'ALU entière. Pour rappel, les branchements relatifs ajoutent une constante au contenu du program counter, afin de brancher X adresses après/avant l’instruction courante. Il y a donc une addition à faire, qui est réalisée par un additionneur dédié dans l'unité de chargement, du moins dans la majorité des cas. Mais le pipeline RISC préfère utiliser l'additionneur de l'ALU entière pour cela, pour diverses raisons. Le program counter est donc propagé dans le pipeline, et est connecté à un multiplexeur en entrée de l'ALU entière.

La performance d'un pipeline

[modifier | modifier le wikicode]

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 | modifier le wikicode]

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.

Sur les processeurs réels, 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.

Cependant, nous allons supposer que les étages sont assez bien équilibrés, de manière à avoir le même temps de propagation. Le pipeline qu'on va étudier 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 :

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 t {\displaystyle f={1 \over t}} , avec t le temps d’exécution d'une instruction (sans pipeline).

à un processeur de fréquence :

f pipeline = 1 t N = N × f {\displaystyle 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'impact 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 :

Temps d'execution d'un programme = N i n s t r u c t i o n s × C P I f {\displaystyle {\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 i n s t r u c t i o n s {\displaystyle N_{instructions}} le nombre d'instructions à exécuter.

Mais l'équation en question ne fonctionne que si on suppose que les instructions sont exécuté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 ?

Elle vient du fait que le pipeline exécute plusieurs instructions simultanées, au lieu d'une seule sans pipeline. il y a précisément une instruction dans chaque étage maximum, ce qui multiple la puissance de calcul maximale par le nombre d'étages du pipeline. En clair, le pipeline ne réduit pas le temps d’exécution d'une instruction, mais augmente les performances en en exécutant plusieurs presque simultanément. 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

[modifier | modifier le wikicode]

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 τ {\displaystyle \tau } le temps de propagation d'un de ces registres et refaire les calculs précédents, en tenant compte de ce terme. Le temps de parcours d'un étage devient :

t étage = t N + τ {\displaystyle 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 × ( t N + τ ) = t + τ × N {\displaystyle T=N\times \left({\frac {t}{N}}+\tau \right)=t+\tau \times N}

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

f = 1 t N + τ = N t + τ × N {\displaystyle f={\frac {1}{{\frac {t}{N}}+\tau }}={\frac {N}{t+\tau \times N}}}

L'équation précédente nous dit que la fréquence du processeur avec un pipeline augmente, comparé à la fréquence du même processeur mais sans pipeline, mais pas autant que dans le cas idéal précédent. Elle n'est pas multipliée par le nombre d'étage, mais un peu en-dessous. Passer de 1 étage à 2 donne un gain en fréquence, mais passer de 20 à 40 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 :

f Avec pipeline f Sans pipeline = N t N τ + t = N N τ t + 1 {\displaystyle {\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 N τ t {\displaystyle {N\tau \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.

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

[modifier | modifier le wikicode]

Les développements précédents sont très intéressants, mais il reste à voir ce que cela donne dans le monde réel. Pour cela, il faut prendre un échantillon de processeurs et comparer leur fréquence en fonction de la longueur de leur pipeline. Mais il faut tenir compte de la finesse de gravure, qui impacte fortement la fréquence du processeur et fausse les comparaisons. Il est possible de déterminer une une fréquence relative, à savoir la fréquence à finesse de gravure égale, par rapport à 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, du fait des registres inter-étages et de l’hétérogénéité des latences intra-étage. Par exemple, regardons la fréquence relative des processeurs Intel d'avant le Pentium 4 (les seuls pour lesquels j'ai les données). Voici ce qu'on obtient :

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 profondeur du pipeline a presque 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.

Avant les années 2000, la fréquence était un argument marketing puissant. Ce qui a poussé certains fabricants de processeurs à créer des processeurs avec un nombre d'étages élevé pour les faire fonctionner à très haute fréquence. C'est ce qu'a fait Intel avec le Pentium 4, dont le pipeline faisait 20 étages pour les Pentium 4 basés sur les architectures Willamette et Northwood, 31 étages pour ceux basés sur les architectures Prescott et Cedar Mill. L'approche a rapidement montré ces limites, poussant Intel à revenir à un nombre d'étages raisonnables pour les processeurs Core 2 Duo.

Les exceptions précises

[modifier | modifier le wikicode]

Les processeurs avec un pipeline ont un petit problème avec des exceptions matérielles. Le problème se manifeste pour toutes les interruptions, que ce soit les exceptions matérielles, les interruptions matérielles et les interruptions logicielles. Mais le problème se manifeste surtout pour les exceptions matérielles, pas pour les interruptions matérielles. Les interruptions logicielles sont à part, elles sont techniquement des branchements et nous reparlerons des branchements plus tard dans ce chapitre.

Les exceptions précises et imprécises

[modifier | modifier le wikicode]

Les exceptions stoppent l’exécution du programme en cours et effectuent un branchement vers une routine d'interruption. Mais avant que l'exception n'ait été détectée, le processeur a chargé des instructions dans le pipeline en avance. Lorsque l'exception est détectée, elle mémorise le program counter de la dernière instruction chargée, et reprendre à cet endroit là. La conséquence est que les exceptions sont décalées de quelques cycles par rapport à un processeur sans pipeline.

Et ce décalage de quelques cycles d'horloge est problématique. La majeure partie des exceptions sont traitées comme suit : la routine de l'exception traite la situation, puis le processeur redémarre l'instruction fautive. Un exemple est le cas d'une instruction d'accès mémoire qui déclenche un défaut de page : le défaut de page déclenche une exception, la routine d'exception traite le problème en chargeant la page voulue en RAM, puis re-démarre l'instruction mémoire. Mais re-démarrer l'instruction fautive implique de reprendre l'exécution du programme juste après l'instruction qui a déclenché l'exception. Si des instructions ont été chargées/exécutées en avance, ce n'est pas le cas : on reprend plusieurs instructions après.

En soi, le processeur peut très bien ne rien faire contre ce problème, les exceptions sont alors dites imprécises. Le problème peut être géré de manière purement logicielle. Au pire, cela peut poser quelques problèmes à quelques programmes comme les débuggers, même si les cas sont rares. Par contre, cela implique que l'on ne peut pas traiter les exceptions en re-démarrant l'instruction fautive. Et cela complexifie grandement la gestion des exceptions, le système d'exploitation est plus complexe, le cout logiciel est là. Pour régler ce petit problème, les concepteurs de processeur ont fait en sorte que le processeur gère lui-même exceptions et interruptions correctement. Ils permettent une gestion des exceptions précises.

Le hardware pour les exceptions précises

[modifier | modifier le wikicode]

Supporter les exceptions précises demande des modifications assez mineures du processeur. L'idée est que les instructions chargées en avance sont juste annulées, elles n'enregistrent pas leur résultat dans les registres et n’accèdent pas à la mémoire. En effet, si une instruction n'enregistre pas son résultat, que ce soit dans les registres ou la RAM, c'est comme si elle n'avait rien fait. Si une exception a lieu, il suffit de ne pas enregistrer les résultats des instructions suivantes dans les registres, jusqu’à ce que toutes les instructions fautives aient quitté le pipeline.

Les exceptions précises sont gérées dans le dernier étage du pipeline, l'étage de writeback, celui d'écriture dans les registres. Pour cela, tout étage fournit à chaque cycle un indicateur d'exception, un groupe de quelques bits qui indiquent si une exception a eu lieu et laquelle le cas échéant. Ces indicateurs sont propagés dans le pipeline, ils passent à l'étage suivant à chaque cycle. Une fois arrivé à l'étage d’enregistrement, un circuit combinatoire vérifie ces bits pour détecter si une exception a été levée, et interdit l'écriture dans les registres en cas d'exception. Si les écritures sont interdites, elles le sont durant un certain nombre de cycles, dépendant de l'exception levée. On dit qu'on vide le pipeline des instructions fautives.

Il faut aussi qu'une fois l'exception terminée, le programme reprenne là où il faut. Pour cela, il faut restaurer le program counter pour qu'il pointe vers l’instruction adéquate. Il s'agit de l'instruction qui a déclenché l'exception. Pour cela, même solution : le program counter est propagé dans le pipeline et est restauré en cas d'exception en prenant le program counter disponible à l'étage d'enregistrement.

Les écritures mémoire sont retardées avec des exceptions précises

[modifier | modifier le wikicode]

Il faut préciser une chose importante : toutes les écritures sont annulées, y compris les écritures en mémoire RAM, y compris celles dans le cache de données. Mais cela pose un problème : les instructions STORE sont censées être exécutées dans l'étage MEM ou Exec, soit avant l'étage de Writeback. Notez bien le censé : ce n'est pas le cas avec les exceptions précises. En réalité, avec des exceptions précises, les instructions STORE font leur écriture dans l'étage de Writeback, l'étage final.

Mais cela implique que l'étage MEM s'occupe des lectures, et l'étage Writeback des écritures proprement dit. Ils font tous deux un accès au cache, ce qui est une dépendance structurelle. Une solution intuitive, utilise un cache de données multiport. Il a un port de lecture séparé du port d'écriture. Le port de lecture est utilisé pour l'étage MEM, alors que le port d'écriture est utilisé dans l'étage de Writeback.

Mais, il faut aussi propager les écritures d'un étage de pipeline au suivant, jusqu'à atteindre l'étage de Writeback. Pour cela, il est possible d'enchainer plusieurs registres de pipeline. Mais nous avons vu dans le chapitre sur les mémoires FIFO qu'enchainer plusieurs registres à la suite est équivalent à utiliser une mémoire FIFO. Aussi, une solution équivalente une mémoire FIFO qui met en attente les écritures dans le cache. Elle est appelée la Write Queue, file d'écriture en français.

La file d'écriture font nous parlons ici ne doit pas être confondue avec le Write buffer présent dans la hiérarchie mémoire. Les deux sont traduit dans ce cours avec le terme file d'écriture, mais il s'agit de deux choses différentes.

La file d'écriture est une simple mémoire FIFO, contenant quelques entrées. Une entrée contient une donnée et l'adresse d'écriture. L'idée est la suivante : l'étage MEM fait l'écriture dans la file d'écriture, puis l'étage de Writeback transfère la donnée de la file d'écriture vers le cache. L'écriture est mise en attente dans l'étage MEM, et est finalisée dans l'étage de Writeback. Si une exception est détectée, l'étage de Writeback vide la file d'écriture, ce qui annule les écritures mises en attente, faites à tord.

La file d'écriture peut mettre en attente plusieurs écritures. Le nombre d'écriture à mettre en attente dépend du pipeline. Le nombre exact est égal au nombre d'étages situés entre l'étage MEM et l'étage Writeback, plus 1. Par exemple, les pipelines précédents n'ont pas d'étages entre MEM et Writeback, ce qui fait que la Write Queue n'a qu'une seule entrée. Il peut être remplacé par un simple registre, mais ce n'est que rarement fait. Mais de nombreux pipelines ont des étages entre les étages MEM et Writeback. Par exemple, s'il y a 4 étages entre les deux, il faut que la file d'écriture puisse mettre en attente 5 écritures. Un autre point est que l'étage MEM peut lui-même prendre plusieurs cycles d'horloge, ce qui est possible si le cache est pipeliné. Dans ce cas, ce nombre de cycle s'ajoute au nombre d'entrées.

Étages MEM			Étages autres				Étage de Writeback
MEM 1	MEM 2	MEM 3	X	X	X	X	Writeback
File d'écriture
Entrée 1	Entrée 2	Entrée 3	Entrée 4	Entrée 5	Entrée 6	Entrée 7	Entrée 8

Pour résumer,

Capacité de la file d'écriture = Nombre d'étages MEM + Nombre d'étages entre MEM et WB + 1 {\displaystyle {\text{Capacité de la file d'écriture}}={\text{Nombre d'étages MEM}}+{\text{Nombre d'étages entre MEM et WB}}+1}

Les utilisations détournées du système d'exception précise

[modifier | modifier le wikicode]

Une utilisation "détournée" du système d'exceptions précise est la gestion des défauts de cache. Un défaut de cache demande de geler le processeur tant que les données adéquates ne sont pas chargées dans le cache. Pour cela, l'unité mémoire peut émettre un signal qui gèle le pipeline en cas de défaut de cache. Lorsque le pipeline est gelé, les instructions stagnent dans le pipeline, elle ne passent plus à l'étage suivant et restent dans l'étage courant. Geler le pipeline est assez simple, il suffit de clock gate les registres d’interfaçage, entre autres. Les registres d’interfaçage restent bloqués tant que le signal de clock gate est maintenu, donc durant tout le défaut de cache.

Mais une autre solution se passe complètement de ce système. L'idée est qu'un défaut de cache lève une exception matérielle. Les instructions qui suivent la lecture/écriture fautive sont alors propagées dans le pipeline et sont annulées à la toute fin. Une fois le pipeline vidé, l'instruction fautive est re-exécutée une fois que le défaut de cache est terminé. En clair, on vide le pipeline avant de le re-démarrer. Un simple compteur est utilisé pour temporiser le re-démarrage du pipeline.

Les exceptions précises sont aussi utilisées pour corriger des problèmes liés aux branchements, ce qui nous amène au sujet du chapitre suivant.

◄ Retour vers « Le Translation Lookaside Buffer »

Sommaire du livre

Continuer vers « La prédiction de branchement » ►