Pipeline (informatique)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Pipeline.
Plan d'un pipeline générique à trois étapes

Un pipeline (fr. chaîne de traitement[1]), dans la microarchitecture d'un processeur, est l'élément dans lequel l'exécution des instructions est découpée en étages. Le premier ordinateur à utiliser cette technique est l'IBM Stretch, conçu en 1961. Avec un pipeline, le processeur peut commencer à exécuter une nouvelle instruction sans attendre que la précédente soit terminée. Chacune de ces étapes est réalisée dans un circuit séparé des autres. Le circuit qui permet d'effectuer une étape s'appelle un étage de pipeline. 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.

Analogie[modifier | modifier le code]

Le pipeline est un concept s'inspirant du fonctionnement d'une ligne de montage. Considérons que l'assemblage d'un véhicule se compose en trois étapes : Installation du moteur - Installation du capot - Pose des pneumatiques (dans cet ordre, avec éventuellement des étapes intermédiaires).

Un véhicule dans cette ligne de montage ne peut se trouver que dans une seule position à la fois. Une fois le moteur déposé, le véhicule Y continue pour une installation du capot, laissant le poste « dépose moteur » disponible pour un prochain véhicule X. Le véhicule Z se fait installer ses pneumatiques (roues) tandis que le second (Y) est à l'étape d'installation du capot. Dans le même temps un véhicule X commence l'étape d'installation du moteur.

Si l'installation du moteur, du capot et des roues prennent respectivement 20, 5 et 10 minutes, la réalisation de trois véhicules prendra, si ils occupent un à un toute la chaîne de production, 105 minutes (1 h 45) = (20 + 5 + 10) x 3 = 105. Si on place un véhicule dans la chaîne de production dès que l'étage auquel le véhicule doit accéder est libre (principe du pipelining), le temps total pour réaliser les trois véhicules est de 75 minutes (1 h 15).

Pipeline RISC classique[modifier | modifier le code]

Pour donner un exemple de pipeline, nous allons aborder un pipeline parmi les plus connus. Celui-ci s'appelle le Classic RISC pipeline. Il s'agit du pipeline créé par David Patterson, inventeur des processeurs RISC et du concept de pipeline. Ce pipeline est utilisé dans de nombreux documents (cours de David Patterson, notamment) comme une introduction au concept de pipeline.

Avec ce pipeline, 5 étapes sont nécessaires pour accomplir une instruction[2] :

  1. IF (Instruction Fetch) charge l'instruction à exécuter dans le pipeline.
  2. ID (Instruction Decode) décode l'instruction et adresse les registres.
  3. EX (Execute) exécute l'instruction (par la ou les unités arithmétiques et logiques).
  4. MEM (Memory), dénote un transfert depuis un registre vers la mémoire dans le cas d'une instruction du type STORE (accès en écriture) et de la mémoire vers un registre dans le cas d'un LOAD (accès en lecture).
  5. WB (Write Back) stocke le résultat dans un registre. La source peut être la mémoire ou bien un registre.

En supposant que chaque étape met 1 cycle d'horloge pour s'exécuter, il faut normalement 5 cycles pour exécuter une instruction, 15 pour 3 instructions :

Séquençage des instructions dans un processeur sans pipeline. Il faut 15 cycles pour exécuter 3 instructions.

En utilisant la technique du pipeline, notre processeur peut alors contenir plusieurs instructions, chacune à une étape différente.

Séquençage des instructions dans un processeur doté d'un pipeline à 5 étages. Il faut 9 cycles pour exécuter 5 instructions. À t = 5, tous les étages du pipeline sont sollicités, et les 5 opérations ont lieu en même temps.

Les 5 instructions s'exécuteront en 9 cycles, et le processeur sera capable de terminer une instruction par cycle à partir de la cinquième, bien que chacune d'entre elles nécessite 5 cycles pour s'exécuter complètement. Au 5e cycle, tous les étages sont en cours d'exécution.

Autres pipelines[modifier | modifier le code]

Ce pipeline n'est pas la seule organisation possible.

On pourrait par exemple créer des pipelines à seulement deux étages. Par exemple, on pourrait découper nos instructions en seulement deux étapes  :

  • Une étape nommée Fetch, qui charge et décode une instruction, et qui met à jour du Program Counter ;
  • et une étape nommée Exec, qui effectuerait l'opération proprement dite (avec les accès à la mémoire et/ou aux registres).

Ce type de pipeline est notamment utilisé sur certains micro-contrôleurs Atmel AVR et PIC.

Autre exemple de pipeline : celui de l'IBM Stretch project composé des trois étapes suivantes :

  • Fetch : chargement de l'instruction depuis la mémoire et mise à jour du Program Counter ;
  • Decode : décodage de l'instruction ;
  • Exec : exécution de l'instruction, avec éventuellement des accès mémoires.

On pourrait aussi créer un pipeline à 7 étages :

  • PC : mise à jour du Program Counter ;
  • Fetch : chargement de l'instruction depuis la mémoire ;
  • Decode : décodage de l'instruction ;
  • Register Read : lecture des opérandes dans les registres ;
  • Exec : calcul impliquant l'ALU ;
  • MEM : accès mémoire en lecture ou écriture ;
  • Writeback : écriture du résultat d'une lecture ou d'un calcul dans les registres.

Bref, de nombreuses variations sont possibles.

Il faut noter que certaines fonctionnalités de la micro-architecture d'un processeur nécessitent l'ajout d'étages de pipelines supplémentaires. Par exemple, un processeur implémentant le renommage de registres demandera une étape supplémentaire pour renommer les registres. En pratique, les processeurs les plus performants utilisent des pipelines extrêmement longs (de l'ordre d'une vingtaine d'étages) pour ajouter de nombreuses étapes augmentant les performances (exécution dans le désordre) et augmenter la fréquence d'horloge (moins de travail à chaque étage).

Quelques profondeurs de pipeline[modifier | modifier le code]

Aujourd'hui tous les microprocesseurs sont pipelinés :

Processeur Profondeur du pipeline
Intel Pentium 4 Prescott 31
Intel Pentium 4 20
AMD K10 16
IBM POWER5 16
IBM PowerPC 970 16
Intel Core 2 Duo 14
Intel Pentium II 14
Sun UltraSPARC IV 14
Sun UltraSPARC IIi 14
AMD Opteron 1xx 12
AMD Athlon 12
IBM POWER4 12
Intel Pentium III 10
Intel Itanium 10
MIPS R4400 8
Motorola PowerPC G4 7

Certaines architectures ont largement augmenté le nombre d'étages, celui-ci pouvant aller jusqu'à 31 pour la microarchitecture Prescott d'Intel. Une telle architecture sera appelée superpipelinée. Voici par exemple le pipeline des premiers Pentium 4, à 20 étages :


Implémentation[modifier | modifier le code]

Dans un processeur doté de pipeline, chaque étape d'une instruction doit être effectuée dans un circuit séparé des autres. Cela n'est pas toujours possible, et il arrive que certains circuits communs doivent malgré tout être partagés, comme les ports d'accès au cache, et qu'il soit possible de bloquer le pipeline pour attendre un résultat précédent. Mais, en principe, un pipeline dispose d'un circuit pour traiter chaque étape.

En électronique, les pipelines sont une classe de circuit bien plus importante que ce que l'on appelle « pipeline » dans un processeur : il s'agit de tout type de circuit où des données progressent. Tous les circuits électroniques comportent donc des pipelines, avec des structures parfois complexes (des boucles et des embranchements par exemple).

Le pipeline traitant les instructions d'un processeur est plus complexe qu'un pipeline où les instructions avanceraient d'étage en étage : il comporte des étapes d'interaction avec les registres, la mémoire et les unités de calcul, et souvent la possibilité de bloquer la progression des données pour attendre la résolution d'une instruction.

Reste que les données doivent passer d'un étage à un autre. Pour ce faire, il existe trois grands types d'implémentations :

  • les pipelines synchrones ;
  • les pipelines asynchrones ;
  • les pipelines à vagues.

Pipelines synchrones[modifier | modifier le code]

Pipeline buffered synchrone.

Les différents étages sont séparés par des registres tampons, qui sont tous reliés au signal d'horloge du processeur. À chaque cycle d'horloge, les registres deviennent accessibles en écritures, ce qui fait que les données passent à l'étage suivant.

C'est de loin la technique la plus utilisée.

Pipelines asynchrones[modifier | modifier le code]

Pipeline buffered asynchrone.

Les différents étages sont séparés par des registres tampons, et les transferts entre registres sont décidés par un protocole asynchrone.

Pipelines à vagues[modifier | modifier le code]

Il n'y a pas de registres entre les étages : en contrôlant leur vitesse de propagation, les données envoyées une par une dans le pipeline sont récupérées dans l'ordre à l'autre bout sans nécessiter de mémorisation temporaire.

Problèmes[modifier | modifier le code]

Les pipelines provoquent de nouveaux problèmes, en particulier d'interdépendance, ils ne sont pas tous listés ci-dessous, juste deux cas simples sont abordés.

Dépendances structurelles[modifier | modifier le code]

Il arrive que dans certains cas bien précis, plusieurs étages du pipeline aient besoin d’accéder à la même ressource matérielle. Cette ressource peut être la mémoire, un registre, une unité de calcul, ou tout autre chose encore.

Si celle-ci n'est pas conçue pour cela, deux instructions entrent en concurrence pour l'accès à cette ressource. Une des deux doit passer avant l'autre, et l'autre instruction doit être mis en attente. Dans ce cas, il peut être nécessaire de bloquer tout les étages du pipeline qui précédent l'instruction bloquée.

Idéalement, ce genre de dépendance se règle souvent en dupliquant la ressource à partager. Il suffit de dupliquer la ressource fautive en autant d'exemplaire qu'il peut en avoir besoin simultanément dans le pipeline. Ceci dit, ce n'est pas toujours possible, notamment pour les accès mémoires.

Dépendances de données[modifier | modifier le code]

Deux instructions ont une dépendance de donnée si elle veulent lire ou écrire dans le même registre ou la même adresse mémoire. Différents cas se présentent alors, suivant que les deux instructions écrivent ou lisent cette donnée.

Dépendances de données
Type Effets
Read after Read Nos deux instructions doivent lire la même donnée, mais pas en même temps !
Read after write La première instruction va écrire son résultat dans un registre ou dans la RAM, et un peu plus tard, la seconde va lire ce résultat et effectuer une opération dessus.
Write after Read La première instruction va lire un registre ou le contenu d'une adresse en RAM, et la seconde va écrire son résultat au même endroit un peu plus tard.
Write after Write Nos deux instructions effectuent des écritures au même endroit : registre ou adresse mémoire.

Ces dépendances imposent un certain ordre d’exécution pour nos instructions. L'ordre d’exécution des lectures et des écritures ne doit pas changer, sous peine de se retrouver avec des résultats faux. Or, sur les processeurs dotés de pipeline, il se peut que les lectures et écritures changent d'ordre : les lectures et écritures dans les registres ne se font pas aux même étages, et une instruction peut donc lire une donnée pas encore écrite, etc.

Respecter l'ordre des lecture/écriture en mémoire et dans les registre peut être très complexe et nécessite la présence de circuits capables de maintenir cet ordre. Diverses optimisations existent pour rendre la situation plus supportable. Certaines dépendances peuvent être éliminée via renommage de registres, ou par des mécanismes de Memory disambiguation. D'autres techniques comme le Forwarding/Bypassing permettent de diminuer l'impact de ces dépendances sur les performances.

Dépendances de contrôle[modifier | modifier le code]

Exception et pipeline

Les branchements, ainsi que leurs cousins exceptions matérielles et interruptions posent quelques problèmes. Lorsqu'un branchement entre dans le pipeline, l'adresse à laquelle brancher n'est connue que quelques cycles plus tard, vers la fin de l'étage de Decode dans le meilleur des cas. La même chose arrive lors de la levée d'une exception ou d'une interruption.

Pourtant, entre le moment où le branchement entre dans le pipeline et celui où l'adresse est connue, le processeur aura continué de charger des instructions dans son pipeline. En clair, des instructions sont chargées par erreur dans notre pipeline. Sur le schéma de droite, ce sont les instructions en jaune.

Pour réduire ce genre de problèmes, nos processeurs peuvent fournir diverses fonctionnalités, comme des Branchs delays slots, ou des mécanismes de prédiction de branchement.

Architecture superscalaire[modifier | modifier le code]

Une architecture superscalaire contient plusieurs pipelines en parallèle. Il est possible d'exécuter plusieurs instructions simultanément. Sur un processeur superscalaire de degré 2, deux instructions sont chargées depuis la mémoire simultanément. C'est le cas des processeurs récents conçus pour maximiser la puissance de calcul. Notons toutefois qu'en général, chaque pipeline est spécialisé dans le traitement d'un certain type d'instruction : aussi seules des instructions de types compatibles peuvent être exécutées simultanément.

Séquençage des instructions dans un processeur superscalaire de degré 2. Il faut 9 cycles pour exécuter 10 instructions. A t = 5, toutes les unités du processeurs sont sollicitées.

Architecture vectorielle[modifier | modifier le code]

Sur de tels processeurs, une instruction va s'appliquer à un ensemble de données, appelé vecteur. Une seule instruction va donc exécuter la même opération de façon parallèle sur tout le vecteur. Ce genre d'architecture est efficace pour les applications de calcul scientifique et s'est notamment trouvée dans les superordinateurs comme les Cray.

Notes et références[modifier | modifier le code]

  1. www3.obs-mip.fr/.../fiche_poste_CDD_Analyse_Scientifique_Pilot-1.pdf
  2. Les étages IF, ID, EX, MEM et WB sont ceux de l'exemple classique du DLX présenté dans Computer Architecture, A Quantitative Approach, John L. Hennessy et David A. Patterson, Morgan-Kaufmann

Articles connexes[modifier | modifier le code]