Pipeline et aléas

Dans le chapitre sur le cycle fetch–decode–execute, le CPU exécutait chaque instruction du début à la fin avant de passer à la suivante. Cela gaspille l’essentiel du matériel : pendant que l’ALU calcule, la logique de fetch attend, et pendant qu’on lit l’instruction suivante, l’ALU attend.

Le pipeline corrige cela comme une chaîne de montage. L’exécution est découpée en étages, chacun confié à son propre morceau de matériel, et une nouvelle instruction entre dans le premier étage à chaque cycle pendant que les plus anciennes avancent. L’idée est ancienne : le Stretch d’IBM (1959) lisait déjà les instructions à l’avance dans un tampon de préchargement, ce qui coupait l’exécution en deux. Un pipeline pousse ce découpage plus loin.

Les cinq étages classiques

Le pipeline de référence des manuels, utilisé par les premiers processeurs RISC comme MIPS, a cinq étages :

Ce sont les étapes du chapitre fetch–decode–execute, désormais dotées chacune de leur propre matériel. Le premier exemple de pipeline de Tanenbaum découpe le travail un peu différemment (fetch, decode, lecture des opérandes, exécution, écriture), mais le principe est le même. Le découpage ci-dessus est celui que la plupart des ouvrages utilisent pour les aléas, car l’accès mémoire y a son propre étage.

Entre chaque paire d’étages se trouve un registre de pipeline : un ensemble de bascules qui mémorise, au front d’horloge, les résultats intermédiaires d’une instruction. C’est ce qui permet à chaque étage de travailler sur une instruction différente.

Le diagramme ci-dessous exécute un programme dans l’émulateur, puis trace le parcours de chaque instruction exécutée à travers le pipeline, une colonne par cycle d’horloge :

Lisez-le en diagonale. Au cycle 5, cinq instructions sont en cours en même temps : la n°1 écrit son résultat, la n°2 est en MEM, la n°3 en EX, la n°4 en ID, et la n°5 est en cours de lecture.

Latence et débit

Le pipeline ne rend aucune instruction plus rapide. Chacune prend toujours cinq cycles de IF à WB : c’est sa latence. Ce qui change, c’est le débit : une fois le pipeline rempli, une instruction se termine à chaque cycle.

Avec n étages et un temps de cycle T :

• latence = n × T par instruction ;
• débit = une instruction par T ;
• N instructions prennent N + n − 1 cycles au lieu de N × n.

Ci-dessus, cela fait 6 + 4 = 10 cycles au lieu de 30.

Le pipeline permet aussi d’accélérer l’horloge. Le chapitre sur le chemin de données a montré que la période d’horloge doit couvrir le chemin le plus lent. Avec des registres de pipeline intercalés, l’horloge ne doit plus couvrir que l’étage le plus lent, une fraction du chemin complet. Le gain n’est pas parfait : chaque registre de pipeline ajoute un petit délai, et les étages ne sont jamais parfaitement équilibrés.

Les aléas

Le cas idéal — une instruction par cycle, indéfiniment — se brise dès qu’une instruction ne peut pas passer à l’étage suivant à temps. Ces situations s’appellent des aléas (hazards), et il en existe trois sortes :

1. Aléas structurels : deux instructions ont besoin du même matériel au même cycle.
2. Aléas de données : une instruction a besoin d’un résultat qu’une instruction précédente n’a pas encore produit.
3. Aléas de contrôle : le pipeline ne sait pas quelle instruction vient ensuite, car un branchement n’est pas encore tranché.

Quand un aléa survient, le pipeline se bloque (stall) : l’instruction attend dans son étage, et tout ce qui la suit aussi. Les cases vides qui descendent alors le pipeline s’appellent des bulles.

Aléas structurels

Dans le diagramme ci-dessus, au cycle 4, l’instruction n°1 est en MEM et la n°4 en IF. Si la mémoire n’avait qu’un seul port, les deux en auraient besoin en même temps. C’est de nouveau le goulot d’étranglement de von Neumann, et une raison de plus pour laquelle les CPU ont des caches L1 séparés pour les instructions et les données : la lecture d’instruction et le chargement ont chacun leur port.

Aléas de données et forwarding

Ici, chaque instruction utilise le résultat de la précédente — une dépendance lecture après écriture (RAW, read after write). Le diagramme démarre avec le forwarding désactivé :

Sans aide, add eax, eax ne peut lire eax en ID qu’une fois que l’instruction précédente l’a écrit en WB. Le banc de registres est écrit dans la première moitié d’un cycle et lu dans la seconde : la lecture peut donc avoir lieu dans le même cycle que l’écriture, mais pas avant. Chaque instruction dépendante attend 2 cycles, marqués ·.

Passez maintenant Forwarding sur on. Les attentes disparaissent. Le résultat d’une addition existe dès la fin de EX, deux cycles avant WB. Le forwarding (ou bypass, court-circuit) ajoute des fils et des multiplexeurs qui le renvoient directement du registre de pipeline vers l’entrée de l’ALU pour l’instruction suivante. Le banc de registres est toujours écrit en WB, mais plus personne n’a à l’attendre.

La bulle load-use

Le forwarding ne peut pas tout faire. Un chargement obtient sa valeur de la mémoire à la fin de MEM, un étage plus tard qu’un résultat d’ALU :

Même avec le forwarding, add eax, 1 doit attendre 1 cycle : quand elle est prête pour EX, le chargement est seulement en train de lire la mémoire. C’est l’aléa load-use (chargement puis utilisation).

La solution ne demande pas de matériel : placer une instruction indépendante entre le chargement et son utilisation. Les compilateurs le font en permanence, et cela s’appelle l’ordonnancement des instructions (instruction scheduling) :

Mêmes instructions, mêmes résultats, un cycle de moins. Quand un code optimisé semble entrelacer sans raison des calculs sans rapport, c’est souvent pour cela.

RAW est la seule vraie dépendance. Deux autres ordres — écriture après lecture (WAR) et écriture après écriture (WAW) — ne comptent que lorsqu’un CPU exécute les instructions dans le désordre, le sujet d’un chapitre ultérieur.

Aléas de contrôle

Ici, un saut conditionnel est tranché en EX. À ce moment-là, l’étage de fetch a déjà lu les deux instructions suivantes dans l’ordre de la mémoire. Si le saut est pris, ces deux instructions sont sur le mauvais chemin et doivent être annulées (flush) :

Chaque jl pris laisse une ligne wrong path de ✕ : deux lectures d’instructions jetées. Le dernier jl, non pris, ne coûte rien, car l’étage de fetch a parié « non pris » et avait raison.

Deux cycles par branchement pris, c’est beaucoup : dans un code typique, on trouve un branchement toutes les cinq à sept instructions. Les concepteurs attaquent les aléas de contrôle par plusieurs côtés :

• Trancher plus tôt. Comparer les registres et calculer la cible dès ID ramène la pénalité à un cycle.
• Branchements retardés. Les premiers RISC comme MIPS et SPARC exécutaient toujours l’instruction qui suit un branchement, le delay slot, pris ou non, et laissaient au compilateur le soin d’y placer quelque chose d’utile.
• Prédire. Deviner le résultat et la cible avant même que le branchement soit décodé, et ne payer que lorsque la prédiction est fausse. C’est ce que font les CPU modernes, et c’est le sujet du chapitre sur la prédiction de branchement, plus loin dans ce niveau.

Plus profond, plus large

Deux façons d’aller plus loin :

• Les pipelines plus profonds découpent le travail en étages plus nombreux et plus courts, pour que l’horloge batte plus vite. Le Pentium 4 est passé à 20 étages, puis 31. Mais chaque étage entre le fetch et la résolution d’un branchement alourdit le coût d’une mauvaise prédiction, et les pipelines très profonds ont perdu ce pari. Les cœurs x86 actuels se situent quelque part entre 14 et 20 étages.
• Les pipelines plus larges — processeurs superscalaires — lancent plusieurs instructions par cycle. Le Pentium d’origine (1993) avait deux pipelines entiers, u et v. Le pipeline v n’acceptait que des instructions simples, et des règles d’appariement fixes décidaient quand deux instructions voisines pouvaient partir ensemble. Les cœurs actuels peuvent lancer quatre à huit µops ou plus par cycle.

Le 486 (1989) a été le premier x86 doté d’un pipeline classique à cinq étages. Tous les x86 depuis sont pipelinés, et la plupart des modèles hautes performances depuis le Pentium Pro (1995) exécutent aussi dans le désordre.

Le mesurer

Le chiffre qui résume la santé d’un pipeline est le CPI — cycles par instruction — ou son inverse, l’IPC. Un pipeline scalaire idéal atteint un CPI de 1. Attentes et annulations le font monter au-dessus de 1, et les cœurs superscalaires peuvent le faire descendre en dessous.

Sous Linux, perf stat ./prog affiche l’IPC d’une exécution réelle, sur la ligne insn per cycle. Une valeur basse signifie généralement que le pipeline attend — la mémoire, sujet du chapitre sur les caches, ou les branchements.

À retenir

• Un pipeline fait se chevaucher les instructions en étages — IF, ID, EX, MEM, WB — séparés par des registres de pipeline.
• Il conserve la latence de chaque instruction mais porte le débit jusqu’à une instruction par cycle, et permet une horloge plus rapide.
• Les aléas structurels sont des conflits de matériel ; des caches d’instructions et de données séparés suppriment le cas classique.
• Les aléas de données (RAW) sont en grande partie masqués par le forwarding, sauf la bulle load-use, que les compilateurs masquent par l’ordonnancement.
• Les aléas de contrôle annulent les instructions du mauvais chemin après un branchement pris ; résolution précoce, delay slots et prédiction en réduisent le coût.