Il était une fois la Révolution

De la puce-artisane...

Les premiers processeurs grand public se caractérisaient par une méthode de travail très "artisanale" car basée sur une logique séquentielle.
Pour ces derniers, en effet, les instructions se trouvaient exécutées l'une après l'autre, chaque exécution réclamant un nombre variable de cycles d'horloge.
 

Nous avons vu i4 en plein travail et avons découvert à cette occasion comment un processeur de son espèce procédait à l'exécution d'une instruction. Pour rappel, ce processus débutait par une suite d'allers-et-retours en mémoire afin de rassembler l'instruction et son (ses) éventuel(s) opérande(s) puis se poursuivait par l'exécution de l'instruction proprement dite pour se terminer par la mise à jour des registres de la puce ou d'une adresse en mémoire.
 

Ainsi, pour ces vénérables processeurs-ci, un cycle d'exécution pouvait être décomposé en trois phases successives:

• Une phase de lecture en mémoire (que nous noterons "LEC") de l'instruction et de ses éventuels opérandes
   
• Une phase d'exécution de l'instruction ("EXE") proprement dite
   
• Une phase de mise à jour en mémoire ("MAJ") des éventuels résultats générés

Ceci dit, nous pourrions alors illustrer très schématiquement le fonctionnement d'un processeur de type séquentiel:

Ce cheminement obligatoire des instructions par chacun de ces stades implique bien évidemment que chaque instruction réclamait plusieurs cycles d'horloge pour être exécutée.
Néanmoins, les incessants progrès technologiques permirent peu à peu d'abaisser le nombre moyen de cycles d'horloge nécessaire à l'exécution des instructions.

Ainsi, le processeur 8086 de Intel nécessitait en moyenne 12 cycles d'horloge pour exécuter une instruction, mais avec le 80286, cette moyenne chutait à 4,5 cycles par instruction.

... A la puce-ouvrière

Frederick Winslow Taylor [1859-1915] est ce qu'on peut appeler un obsédé du rendement, un monomaniaque de la productivité, un fétichiste du chronomètre.
Sans Monsieur Taylor et sans ses travaux de "sociologie industrielle", pas de Ford T, pas de machines-outils, pas de société de consommation, et donc, ni Elvis, ni BigMac et ni PC (la machine, pas le parti ! ...quoique...)

Bref, un monde de larmes et de ténèbres...
 

En deux mots, le taylorisme, c'est "l'Organisation Scientifique du Travail", la traque et l'élimination des gestes inutiles, la quête éperdue du rendement.
La théorie se matérialise très concrètement par une chaîne de montage; un premier ouvrier place un écrou sur une pièce, un deuxième ouvrier le visse et un troisième vérifie que les deux premiers ont bien travaillé. Et bis repeta, ad lib...
Les ouvriers ont bien une légère tendance à devenir complètement dingues, mais chacune des soixante secondes de chaque minute est mise à profit, et le prix de la pièce usinée se trouve ainsi suffisamment abaissée pour que lesdits ouvriers puissent se l'offrir sans trop s'endetter, quittes à n'en avoir aucun besoin.
Il est beau, il est beau, il est beau mon rêve américain !

Et c'est là que Charlot intervient ! En appliquant au processeur le très tayloriste concept de "travail à la chaîne", le rendement de la puce se trouve d'un coup démultiplié:

Vivent les cadences infernales !
My Taylor is speed...

Le pipeline d'exécution

Entrez dans la lumière (du pipeline)

Comme nous venons de la voir, un processeur à pipeline d'exécution est tout simplement une puce fonctionnant sur le très mécanique principe de la chaîne de montage.
 

Le principe reste effectivement le même, à savoir diviser le processus d'exécution des instructions en un nombre donné d'étapes fonctionnellement indépendantes.
A chacune de ces étapes correspond un "poste de travail" chargé d'une tâche bien définie et qui constitue alors un étage du pipeline.
 

L'indépendance des différents étages du pipeline permet au processeur de traiter plusieurs instructions simultanément, chacune d'entre elles se trouvant à un stade différent du cycle d'exécution.
Les gens bien appellent ce procédé de recouvrement des tâches parallélisme par anticipation.

Il est facile de comprendre qu'un processeur à pipeline réclame une architecture bien plus complexe qu'un processeur séquentiel, de par les contraintes inhérentes à son mode de fonctionnement: synchronisation entre les différents étages, processus de contrôle, accès partagés aux unités fonctionnelles...
De même, la complexité du pipeline sera d'autant plus poussée que son nombre d'étages sera grand.
 

Autre facteur d'efficacité: dans l'idéal, les différents étages du pipeline devront réclamer le même délai pour être traversés afin de rendre le flux des instructions le plus fluide possible. En effet, il est facile de comprendre que le "débit" d'un pipeline sera directement lié à son étage le plus "lent".

Le pipeline du 80486: un tube de légende !

En +34 après Bill Gates (1989 donc), Monsieur Intel sort son processeur 80486. La bête est séduisante et se trouve être la première puce "grand public" conçue sur le révolutionnaire principe du pipelining.
 

Très pratiquement, le pipeline du 80486 est divisé en cinq étages successifs et fonctionnellement (quasi) indépendants:

• Etage PREFETCH (PF) correspondant à la lecture de l'instruction depuis la mémoire
   
• Etage DECODE-1 (D1) se chargeant du décodage de l'opcode de l'instruction et de son (ses) éventuel(s) opérandes
   
• Etage DECODE-2 (D2) terminant le décodage proprement dit en convertissant l'instruction en signaux de contrôle
   
• Etage EXECUTE (EX) correspondant à l'exécution proprement dite de l'instruction (calcul, transferts, comparaisons...)
   
• Etage WRITE-BACK (WB) au cours duquel sont mis à jour les différents registres et, éventuellement, la mémoire

... chacun de ces stades nécessitant un ou deux cycles d'horloge.

Bien évidemment, le nombre d'étages du pipeline n'est pas limité à cinq. Comme nous allons le voir, l'augmentation de ce nombre d'étages est d'ailleurs une évolution majeure des processeurs ultérieurs, et ce pour une raison très mathématique que nous allons voir de ce pas (si, si... nous insistons)

Pour exemples, le processeur Athlon XP dispose d'un pipeline à 10 étages, le Pentium 4 d'un pipeline à 20 (!) étages

Le pipeline, un bon tuyau ?

A vue de nez, le principe du pipeline d'exécution semble être somme toute assez efficace. Mais dans quelle mesure ?
Petite démonstration mathématique en bonne et due forme, avec des inconnues et tout et tout...
 

Considérons deux processeurs dont le point commun est d'exécuter, en moyenne, une instruction en K cycles d'horloge. Le premier est un processeur séquentiel classique (type i4), et le second un processeur à pipeline d'exécution à K étages.
Bien. Comparons maintenant les deux machines, comme dans une bête publicité pour une lessive...

Petite explicitation pour ceux qui viennent de se lever ou qui ne sont pas encore couchés: Au coeur d'un processeur pipeliné, quand la première instruction s'apprête à quitter le pipeline (c'est-à-dire le dernier étage), l'instruction qui lui succède est déjà à l'avant-dernier stade du cycle d'exécution. Il ne lui faudra donc qu'un petit cycle pour traverser le dernier étage et quitter à son tour le pipeline.
Idem le même pour l'instruction qui lui succède.
 

Par un habile rapport mathématique [NK / (K+N-1)], nous pouvons mesurer l'efficacité comparée des deux méthodes de fonctionnement et constater, ébahis, que lorsque N est suffisamment grand (ce qui est le cas de tout programme un tant soit peu utile), ce rapport est voisin de K.

La conclusion est immédiate et ébaubiante: le gain de temps procuré par un processeur à pipeline est directement proportionnel à son nombre d'étages.

Trous, purges et dépendances

Les ravages de la dépendance

Le fait est que la belle théorie du pipeline se heurte en pratique à des aléas qui grippent cette mécanique bien huilée. Ces accidents de parcours sont appelés dépendances et surviennent quand une instruction ne peut s'exécuter avant le complet achèvement de l'instruction qui la précède.

Malheureusement, ces "trous d'air" dans le pipeline ont de multiples causes...

Dépendances de ressource

Dans notre description du processeur pipeliné idéal, nous avons précisé que les différents étages du pipeline devaient être fonctionnellement indépendants. Hélas, cette exigence était un voeu pieu.

Le problème est le suivant: un pipeline aura beau disposer d'un nombre important d'étages, les unités fonctionnelles du processeur (UAL, registres, mémoire cache, décodeur-séquenceur...) seront toujours, elles, en nombre limité.
De ce fait, il est très possible que deux instructions, même à des stades d'exécution différents, sollicitent simultanément une même unité fonctionnelle. Dans ce cas, pas si extraordinaire, la seconde instruction devra attendre que la première en ait terminé pour poursuivre son propre cheminement.

Dépendances de données

Autre scénario enclin à perturber le long flux tranquille à l'intérieur du pipeline: une instruction intéragit avec un registre que l'instruction immédiatement suivante utilise également pour son propre cycle d'exécution.

Vous aurez remarqué la subtile nuance entre ce type de dépendance et la dépendance de ressource. Dans ce cas-ci, le registre n'est pas nécessairement occupé par l'instruction précédente, mais il n'est pas encore rempli avec la bonne valeur, celle qui résultera de la complète exécution de la première instruction.

Dépendances de contrôle (ou de procédure)

Quiconque a taquiné un tant soit peu la programmation sait que tout programme informatique qui se respecte comporte un nombre important de sauts en tous genres: appels de fonction, boucles, branchements avec ou sans tests...
Quelles que soient ces "ruptures de séquence", la conséquence est la même: le programme "saute" brutalement à un autre endroit du programme.
 

Comment mettre le doigt de manière intelligence sur le gros problèmes causé par un branchement sur un processeur à pipeline ?
Bon ! Imaginez un programme de tir au contrôleur des impôts. Vous gagnez quand vous avez blasté dix contrôleurs des impôts, et vous avez alors droit à une magnifique animation ainsi qu'à un faux passeport monégasque.
Le programme s'exécute donc paisiblement, et alors que vous venez de châtier votre dernier ennemi, le programme teste s'il s'agit du dixième. Le test est positif: vous avez droit à votre belle scène finale mais voilà, dans le pipeline, le jeu a déjà prévu l'envoi d'une autre cible !
Mais comment cesser ce carnage ?
Réponse: par une bonne purge !

Symptomatologie de la dépendance

Dépendances de ressource et de données ne sont que vétilles et peccadilles dans la vie d'un pipeline, car le flux des instructions ne se trouve pas rompu.

Après tout, qu'une instruction doive attendre que celle qui la précède sorte totalement du pipeline... Quoi de grave ? Le flux d'instructions stoppe une fraction d'instant. Le pipeline hoquette. Un "trou" apparait sur la ligne de montage. Et puis la puce s'en repart, tout en sifflotant...

Les dépendances de procédures sont un tantinet plus fâcheuses.
Imaginez... Alors que pupuce s'est laborieusement engagée à exécuter cette séquence-ci d'instructions, contre-ordre soudain, il faut tout laisser tomber et passer à autre chose !
Les instructions postérieures à l'ordre de branchement mais déjà introduites dans le pipeline deviennent d'un coup aussi utiles qu'un string thermolactyl. Il faut se résoudre à purger le pipeline puis le recharger avec les instructions situées à l'adresse du branchement !

Le pipeline, censé nous faire gagner du temps, nous en fait perdre lamentablement. Et, qui plus est, le contretemps est d'autant plus interminable que le pipeline est profond, de par le nombre d'étages à purger !

Dans les labos d'IBM et confrères, on organisa très vite un séminaire de travail sur le thème: "Traque et élimination des sauts de nos puces".
Compte-rendu du brainstorming dans une page à venir...

En concevant le pipeline d'exécution, les ingénieurs-architectes avaient boosté d'un coup les performances de leurs drôles de machine. L'idée était simple, restait pour eux à la concrétiser en circuits imprimés et interconnexions silicées et multiplier les étages de leurs chaînes de montage miniaturisées. Ce qu'ils firent zèlement.
Que pouvait-on faire de mieux ? Quel mécanisme pourrait être plus efficace qu'un pipeline ?

Deux pipelines, bien sûr ! L'ingénierie informatique est si simple !
L'ordinateur entrait fièvreusement dans l'ère prometteuse des processeurs superscalaires.

 Architecture superscalaire (ça vient, ça vient...)