Chapitre 9 Au-delà du modèle de von Neumann

Introduction

La recherche de performances a inspiré des tentatives pour contourner la loi d'airain de l'architecture de von Neumann : une seule instruction à la fois. Ces tentatives se classent en deux catégories : radicales et pragmatiques. Le présent chapitre en fait un bref tour d'horizon. Les architectures qui remettent fortement en cause le principe de von Neumann n'existent aujourd'hui que dans quelques laboratoires (même si elles sont sans doute promises à un avenir meilleur et si certaines d'entre elles ont un passé respectable), et celles qui sont des extensions pratiques de ce principe ne remettent pas en cause la sémantique du modèle de calcul, même si elles en compliquent considérablement la mise en oeuvre technique pour le bénéfice d'une amélioration non moins considérable des performances.

9.1 Architectures révolutionnaires

Les tentatives radicales visent à créer de nouveaux modèles de calcul en imaginant des ordinateurs capables d'exécuter un grand nombre d'instructions simultanément. Ces modèles révolutionnaires se classent selon diverses catégories :

9.1.1 SIMD (Single Instruction Multiple Data)

Comme le nom le suggère, il s'agit d'ordinateurs capables d'appliquer à un moment donné la même opération à un ensemble de données, ce qui postule une certaine similarité de celles-ci. Ce postulat est rarement satisfait dans le cas général, mais il s'applique bien à un cas particulier important, celui du calcul vectoriel ou matriciel, qui a de nombreuses applications pratiques en météorologie, en aérodynamique, en calcul de structures, en océanographie, en sismologie, bref dans tous les domaines pour lesquels la physique ne donne pas de solution analytique simple mais où un modèle heuristique étalonné sur des données recueillies pour des problèmes à solution connue et appliqué à un ensemble de données empiriques aussi vaste que possible permet d'atteindre une solution approchée satisfaisante. Le modèle SIMD a connu un certain succès sous le nom d'ordinateur vectoriel.

En réalité un processeur vectoriel ne dispose que d'un seul additionneur (ou respectivement multiplieur, diviseur, etc.), l'exécution des opérations sur les données multiples n'est donc pas exactement simultanée, mais elle repose sur une technique de pipe-line que nous décrirons ci-dessous à la section 9.2.2. La réalisation d'un tel ordinateur pose des problèmes théoriques raisonnablement solubles ; il en va de même pour la programmation.

Les super-ordinateurs Cray, Fujitsu, NEC, les mini-super Convex, les processeurs spécialisés Floating Point Systems ont connu de réels succès jusque dans les années 1980 et 1990 en employant à des degrés divers la technologie vectorielle.

Si la baisse de prix des processeurs ordinaires les a peu à peu éliminées, ces architectures pourraient revenir en scène lorsque les progrès de la technologie classique rencontreront des obstacles sérieux, et s'appliquer assez bien à tous les problèmes de traitement et de création d'images. D'ailleurs le développement extraordinaire des jeux vidéo, qui sont aujourd'hui (en 2002) l'aiguillon le plus aiguisé de la recherche micro-électronique, a nécessité la conception de processeurs graphiques époustouflants qui recyclent pas mal de technologie vectorielle.

9.1.2 Architectures cellulaires et systoliques

Le modèle SIMD poussé à son extrême donne le modèle cellulaire, conçu pour exploiter un parallélisme de données massif : on a toujours un processeur par donnée, les processeurs sont très simples mais ils se comptent par dizaines de milliers. Il y eut surtout des prototypes de laboratoire, excepté le premier modèle de la Connection Machine de l'entreprise modestement nommée Thinking Machines Corporation. Cet ordinateur, doté de 65 536 processeurs, chacun flanqué d'une mémoire locale de 65 536 bits, avait été conçu par Daniel Hillis, un étudiant en intelligence artificielle au MIT et réalisé grâce à une commande du DoD (ministère de la Défense américain). Il s'en vendit une vingtaine d'exemplaires (dont deux en France) pour un coût unitaire équivalent à une dizaine de millions de dollars.

Une variante du modèle cellulaire est l'ordinateur systolique, qui exploite en outre un parallélisme de flux de données : un vecteur de données passe par des processeurs successifs qui correspondent à des étapes successives de calcul et qui effectuent chacun un type d'opération.

Il convient également de mentionner la conception et la réalisation de processeurs systoliques spécialisés pour certaines applications, notamment la comparaison de séquences biologiques. La plupart de ces processeurs, par exemple le réseau systolique linéaire SAMBA de 256 processeurs pour la comparaison de séquences biologiques développé par Dominique Lavenier à l'IRISA de Rennes, implémentent l'algorithme classique de Smith et Waterman (un algorithme dit de « programmation dynamique »).

La comparaison de séquences biologiques est une comparaison inexacte : il s'agit de savoir si deux chaînes de caractères représentant deux séquences d'ADN (l'alphabet est ATGC) ou deux séquences de protéines (l'alphabet est alors plus vaste pour représenter les vingt acides aminés et quelques autres informations) sont suffisamment semblables, au prix de quelques disparités de caractères (de possibles mutations), de quelques décalages (insertions ou délétions).

Le système est constitué de plusieurs processeurs capables surtout de comparer deux caractères entre eux. Les processeurs sont disposés en série ; s'il y en a cent on peut placer dans la mémoire locale de chacun d'eux un caractère d'une séquence de cent caractères que l'on veut étudier en la comparant à une collection de séquences connues par ailleurs. On fait défiler les séquences de la collection (généralement nommée banque) dans les processeurs qui détiennent la séquence étudiée (la cible). Il n'est pas possible d'exposer ici le détail de l'algorithme, mais cette architecture est très bien adaptée à cet algorithme. Malheureusement elle est limitée à un seul algorithme.

9.1.3 MIMD (Multiple Instructions Multiple Data)

Les machines MIMD sont des ordinateurs capables d'exécuter simultanément de nombreuses instructions quelconques appliquées à des données également quelconques. En fait il y a de multiples processeurs qui se partagent une mémoire unique, parfois ils ont chacun en plus une mémoire locale, quelquefois ils n'ont qu'une mémoire locale. L'interconnexion de tous ces processeurs, leur synchronisation et le maintien de la cohérence de la mémoire partagée posent des problèmes absolument passionnants de conception du matériel et du système d'exploitation : une fois ceux-ci résolus il reste à programmer tout ça, et c'est là qu'achoppe l'ambition de ces tentatives. La complexité de la programmation est telle que le temps qu'elle absorbe suffit aux processeurs ordinaires pour combler l'écart de performance que l'architecture MIMD était censée creuser. Ces architectures connaîtront une nouvelle faveur lorsque la courbe inexorable du progrès des processeurs de von Neumann s'infléchira.

Parmi les réalisations MIMD les plus achevées on retiendra les dernières Connection Machines de Thinking Machines Corporation, entreprise disparue durant les cruelles années 1990. Citons aussi les Transputers de la société britannique Inmos, destinés à former les éléments de base d'architectures plus complexes, inspirés des travaux de C.A.R. Hoare¹ sur les processus séquentiels communicants. Le Transputer a connu un certain succès, notamment dans le domaine industriel.
Ce rapide tour d'horizon des architectures non von Neumann illustre leur échec général dû à la difficulté de leur programmation. À leur apparition elles ont souvent énormément séduit, mais la nécessité de recourir à des méthodes et à des langages de programmation peu répandus et maîtrisés par peu d'ingénieurs a vite découragé industriels et clients. D'où le succès, en revanche, de contournements du principe de von Neumann par des voies moins radicales, qui recherchaient le même résultat tout en conservant la sémantique classique et que nous allons examiner maintenant.

9.2 Architectures réformistes

Parmi les différentes réformes apportées à l'architecture de von Neumann pour en améliorer les performances tout en conservant un comportement extérieur apparent identique, la plus importante par ses conséquences est peut-être la substitution à la mémoire centrale unique d'une hiérarchie de mémoires de temps d'accès décroissants, depuis le cache de niveau 1 incorporé au processeur jusqu'à la mémoire auxiliaire de pages sur disque : mais cette notion de hiérarchie de mémoire dépasse le cadre du présent chapitre et elle est abordée dans plusieurs chapitres du corps de cet ouvrage. Nous examinerons ici les architectures en « pipe-line » et super-scalaires. Mais auparavant nous devons donner un peu plus de détails sur le déroulement des instructions que nous ne l'avions fait à la sous-section ??.

9.2.1 Séquence d'exécution d'une instruction

Dans l'exposé du principe de l'ordinateur à la sous-section ?? nous avons considéré chaque instruction machine comme une opération indivisible dans le temps, atomique, et il en est bien ainsi selon von Neumann. En fait la plupart des instructions sont effectuées selon une séquence temporelle identique et régulière dont nous allons exposer un exemple.

L'exécution des instructions successives de notre architecture a lieu selon la séquence suivante. Notons que cet exemple, pour une raison que nous allons voir, postule des instructions à format fixe.

Étape de lecture FETCH : l'unité de contrôle va chercher en mémoire la prochaine instruction à exécuter. Comment sait-on où aller la chercher ? L'unité de contrôle maintient cette information dans un compteur de programme (PC) qui à chaque instant contient l'adresse en mémoire de l'instruction suivante. Dans le cas le plus simple (pas de débranchement) c'est l'adresse du mot qui suit l'instruction en cours. Dans le cas d'un débranchement : eh bien l'instruction de débranchement consiste précisément à placer dans le PC l'adresse de l'instruction à laquelle le programme doit se poursuivre (doit « sauter » : les débranchements sont aussi appelés sauts ; on distingue les branchements conditionnels et les sauts simples, inconditionnels).

Le PC peut résider dans un registre de l'unité centrale. Dans notre exemple simple il serait possible de lui réserver R qui n'est pas utilisé à autre chose. Dans beaucoup de processeurs le PC est une partie du PSW (Program Status Word) qui conserve différents indicateurs fondamentaux du processeur.
Étape de décodage DEC : l'unité de contrôle analyse le code opération (5 premiers bits dans notre exemple de la section ??) et détermine ainsi le circuit logique qui correspond à l'instruction désirée. Simultanément au décodage, l'unité de contrôle effectue la lecture des registres impliqués dans l'instruction. Cette simultanéité impose des instructions à format fixe, où le nombre et l'emplacement des bits qui désignent les registres soient toujours les mêmes. Le contenu des registres est recopié dans des registres de travail temporaires.
Étape d'exécution EXEC : l'instruction déterminée à l'étape de décodage est exécutée ; s'il doit y avoir un accès mémoire l'adresse effective est calculée ; s'il s'agit d'un branchement conditionnel le contenu du registre lu à l'étape précédente permet de déterminer si le branchement doit être « pris » et si oui l'adresse de branchement est calculée.
Étape d'accès mémoire MEM : cette étape a lieu pour les opérations de chargement et de rangement en mémoire et pour les branchements. Les chargement ou rangements ont lieu, ou la valeur convenable est placée dans le PC. Ces opérations ont lieu dans le cache, ce qui explique que cette étape ait une durée comparable aux autres.
Étape d'écriture du résultat RES dans les registres affectés.

9.2.2 Le pipe-line

Principe du pipe-line

Pour l'exemple de processeur que nous venons de donner, l'exécution d'une instruction se décompose en cinq étapes plus élémentaires. À part l'exécution proprement dite (étape EXEC), ces étapes sont les mêmes quelle que soit l'instruction particulière qui doit être exécutée. L'idée est venue de confier chaque étape à une unité de circuits logiques spécifique : unité de lecture, unité de décodage, unité d'exécution, unité d'accès mémoire, unité de livraison du résultat. Ainsi le processeur peut commencer à traiter une instruction avant que la précédente soit terminée, en utilisant les unités libérées par la terminaison des premières étapes. Soient i₁,i₂,... i₆ six instructions consécutives, elles seront traitées ainsi :

i₁	`FETCH`	`DEC`	`EXEC`	`MEM`	`RES`
i₂		`FETCH`	`DEC`	`EXEC`	`MEM`	`RES`
i₃			`FETCH`	`DEC`	`EXEC`	`MEM`	`RES`
i₄				`FETCH`	`DEC`	`EXEC`	`MEM`	`RES`
i₅					`FETCH`	`DEC`	`EXEC`	`MEM`	`RES`
i₆						`FETCH`	`DEC`	`EXEC`	`MEM`	`RES`

Cette structure s'appelle un pipe-line, parce qu'elle évoque un tuyau dans lequel les instructions s'engouffrent les unes derrière les autres sans attendre que la précédente soit sortie. Nos instructions sont découpées en cinq étapes, ce qui fait que notre pipe-line à un moment donné contient cinq instructions en cours d'exécution : on dit que c'est un pipe-line à cinq étages. Certains processeurs ont des pipe-lines avec sept ou huit étages, voire plus : le Pentium III a douze étages de pipe-line, le Pentium IV en a vingt.

Cycle de processeur, fréquence d'horloge

Qu'est-ce qu'un cycle de processeur ? Toutes les opérations dans un processeur sont synchronisées par une horloge, ce qui permet de savoir à quel moment le résultat d'une micro--opération va être disponible. J'appelle micro--opération une opération moins complexe qu'une instruction, par exemple une étape d'instruction telle que décrite à la section 9.2.1. Il est nécessaire de savoir à quel instant précis telle modification de tel registre sera disponible et stable, pour pouvoir enchaîner la micro--opération suivante : c'est le rôle de l'horloge.

Comment fonctionne l'horloge du processeur ? Elle repose sur un dispositif à quartz, qui régule un circuit oscillant selon une fréquence extrêmement précise. À chaque fin de période le circuit oscillant émet un signal. On rappelle que la période est l'inverse de la fréquence : si un circuit a une période de 1/50 de seconde, on dit que sa fréquence est de 50 Herz (Hz). La sortie du circuit logique correspondant à une micro--opération est couplée à une entrée d'un circuit ET dont l'autre entrée est couplée à l'horloge. À chaque top d'horloge la porte ET délivre un résultat. Ainsi toutes les opérations sont synchronisées. Ce que l'on appelle la fréquence d'un processeur est la fréquence de son horloge.

Processeurs asynchrones

Ce cadencement des opérations simplifie grandement la conception des circuits, mais on peut imaginer qu'il fait perdre du temps à certains endroits : toutes les micro-opérations ne durent pas le même temps et certains résultats obtenus ne sont pas disponibles parce qu'on attend le top d'horloge. Aussi existe-t-il un domaine de recherche prometteur, les processeurs asynchrones. La synchronisation est remplacée par la signalisation : un élément de circuit qui obtient un résultat prévient le consommateur de ce résultat par l'émission d'un signal, ce qui nous place dans une logique assez semblable à celle des protocoles de réseau, où l'on ignore toujours ce qui se passe « à l'autre bout ». Parmi les avantages collatéraux fournis par l'asynchronisme, signalons une consommation électrique et des interférences électromagnétiques réduites.

Comme beaucoup de techniques avancées, les processeurs asynchrones sont aujourd'hui un domaine assez confidentiel, mais qui pourrait connaître une grande expansion au fur et à mesure que les progrès des processeurs classiques deviendront plus laborieux.

Apport de performances par le pipe-line

Le pipe-line est un facteur considérable d'accélération des processeurs, et notamment d'augmentation de la fréquence nominale.

Supposons une architecture classique où le temps total d'exécution d'une instruction simple telle qu'un chargement de registre ou une addition registre à registre correspond à un ou deux cycles (même si des instructions complexes peuvent prendre dix ou vingt cycles).

Prenons maintenant une architecture avec un pipe-line à cinq étages, comme dans notre exemple, et avec des éléments micro--électroniques aussi rapides que notre architecture classique hypothétique. Notre instruction va prendre le même temps pour s'exécuter, mais elle est maintenant cadencée par le passage dans les cinq étages du pipe-line. Chaque étage correspond à un cycle. L'instruction qui s'exécutait en deux cycles s'exécute maintenant en cinq cycles, toujours dans le même temps : c'est que chaque cycle est plus court. La fréquence a été multipliée par 2,5. C'est ainsi que le pipe-line est l'arme secrète qui permet les fréquences élevées des processeurs contemporains.

Certes, pour une instruction donnée chaque cycle « fait » moins de choses, mais ce n'est pas une escroquerie : à chaque fin de cycle il y a bien livraison du résultat d'une instruction. Enfin presque. Parce qu'il y a quand même des difficultés qui s'opposent parfois au fonctionnement continu du pipe-line.

Limite du pipe-line : les branchements

La première difficulté inhérente au pipe-line est de bon sens : on commence à exécuter plusieurs instructions consécutives, mais s'il y a un débranchement au milieu l'ordre d'exécution sera modifié. Notre processeur aura commencé à exécuter des instructions dont la suite des événements montre que ce n'était pas les bonnes.

Quand sait-on si un branchement conditionnel a effectivement lieu ? Lors de l'étape EXEC. Quand est-il exécuté ? Lors de l'étape MEM.

Si par exemple i₃ est un branchement conditionnel et que le chemin choisi soit effectivement le débranchement, cette condition est connue lors de l'étape EXEC de i₃. À ce stade, i₄ est déjà passée par les étapes FETCH et DEC, i₅ par l'étape FETCH. Rien d'irrémédiable n'a été accompli, ni accès mémoire ni écriture de résultat, mais on a perdu du temps, en exécutant des étapes pour des instructions inutiles et il faut « vider » la suite du pipe-line pour le recharger avec d'autres instructions.

Il est assez clair que si les débranchements sont fréquents le gain de performances procuré par le pipe-line va fortement diminuer. Plus le pipe-line a d'étages plus la pénalité sera forte, et dans certains cas il sera nécessaire de restituer à certains registres leur valeur antérieure, modifiée par une exécution trop hardiment anticipatrice. Le processeur devra comporter des circuits logiques destinés à traiter ces situations de retour en arrière. On le voit, tout gain de performance a un coût qui en atténue l'avantage.

Les architectes de processeurs déploient des techniques très subtiles pour éviter l'occurrence trop fréquente de ces situations de débranchement (de saut) où le pipe-line « cale » (to stall). La prédiction de branchement consiste à essayer de savoir à l'avance, par l'examen anticipé du texte du programme, si un branchement va avoir lieu, et dans ce cas modifier l'ordre des instructions pour annuler le branchement. Dans le cas d'une section de programme répétitive, l'historique des exécutions permet de savoir quels sont les branchements les plus probables et de réorganiser le texte du programme pour que le cas le plus fréquent se déroule sans branchements. En désespoir de cause on peut recourir à la technique du « branchement retardé » qui consiste à insérer une instruction nulle derrière le branchement, ce qui évite d'avoir à commencer des instructions qu'il faudra annuler : ceci n'est jamais nécessaire dans notre exemple de pipe-line à cinq étages, mais peut l'être avec un plus grand nombre d'étages ; dans ce cas la détection de branchement pourrait intervenir après que les instructions suivantes auront modifié des registres, qu'il faudrait alors restaurer à leur valeur précédente, ce qui serait extrêmement complexe.

Les auteurs de compilateurs sont aussi mis à contribution dans la lutte contre les branchements. Ils sont invités à produire du code machine aussi exempt de branchements que possibles, à anticiper les cas les plus probables pour leur réserver l'exécution la plus linéaire possible. Évidemment ces efforts ne réussissent pas toujours et il reste des branchements à détecter dynamiquement, c'est-à-dire lors de l'exécution (par opposition à une détection statique, par l'examen du texte du programme).

Limite du pipe-line : les interruptions

La seconde difficulté de réalisation d'un pipe-line efficace est d'une nature voisine de celle que nous venons d'examiner, mais encore plus redoutable. Nous avons bien des difficultés avec les débranchements, mais au moins ce sont des événements internes à un programme, à un processus et à un processeur. Mais qu'en est-il lorsque survient un événement asynchrone, dont le type par excellence est l'interruption ?

Dans une architecture traditionnelle, von-Neumannienne de stricte obédience, le processeur à un instant donné exécute au plus une instruction. La valeur du compteur ordinal (PC, eip...) désigne exactement la limite entre ce qui est déjà exécuté et ce qui reste à exécuter. C'est en général après la terminaison de chaque instruction que le processeur scrute les registres de contrôle des interruptions pour savoir s'il y en a une en attente, auquel cas il décide de la traiter, ou de ne pas la traiter d'ailleurs si les interruptions sont masquées à ce moment. Le cas des interruptions pour faute de page est un exemple de situation un peu différente, où le PC après l'interruption doit pointer sur l'instruction qui a causé la faute afin qu'elle puisse être exécutée à nouveau, la page étant désormais en mémoire. Le problème est assez bien circonscrit.

Avec une architecture à pipe-line, l'interruption survient dans un contexte où plusieurs instructions sont en cours d'exécution à des stades variés. La valeur du compteur ordinal ne rend pas forcément fidèlement compte de la limite entre ce qui est exécuté et ce qui ne l'est pas. Sans doute, elle donne l'adresse de la prochaine instruction à introduire dans le pipe-line, plus probablement que celle de la dernière instruction exécutée. Bref, après avoir traité l'interruption le processeur devra déterminer où il s'était arrêté dans le pipe-line et trouver un état bien déterminé pour redémarrer, ce qui ne sera pas simple.

Nous n'entrerons pas dans les détails de ce problème, qui relève de l'architecture matérielle plus que du système d'exploitation, mais sachons que pour mieux le cerner les processeurs modernes ont souvent deux types d'interruptions : les interruptions précises qui laissent le processeur dans un état bien défini (PC sauvegardé en un endroit connu, instructions antérieures à celle pointée par le PC totalement exécutées, instructions ultérieures non entamées, état de l'instruction courante connu), et les interruptions imprécises qui laissent tout en chantier, charge au programmeur de système de reconstituer une situation de redémarrage cohérente à partir des informations d'état que le processeur aura obligeamment déversées sur la pile. Il y a des cas où une interruption imprécise fait très bien l'affaire, par exemple si elle correspond à une erreur fatale l'état ultérieur du programme importe peu.

Pour prendre un exemple, l'architecture ARC 700 lancée en 2004 comporte un modèle d'interruptions précises qui permet, au choix, de forcer la terminaison de toutes les instructions qui précèdent celle qui a provoqué l'exception ; d'annuler l'instruction fautive avant de valider son résultat ; d'avertir la routine de traitement des exceptions de la cause de l'exception ; et de relancer le pipe-line après le traitement de l'exception dans l'état où il se trouvait auparavant.

Les interruptions précises augmentent considérablement la complexité des circuits matériels dévolus au contrôle des interruptions, et de ce fait les architectes essayent de les éviter. Les interruptions imprécises sont de plus en plus populaires parmi les architectes de processeurs, et comme d'habitude la complexité est renvoyée aux concepteurs de systèmes d'exploitation, ce qui est après tout de bonne politique : il est plus facile de modifier un paragraphe de programme qu'un morceau de silicium (déjà installé dans le salon du client de surcroît).

Lorsque nous aborderons le modèle d'exécution super-scalaire quelques pages plus bas, nous verrons que les difficultés causées par un contexte mal déterminé lors d'une interruption sont encore plus graves.

9.2.3 RISC, CISC et pipe-line

L'idée du pipe-line est apparue assez tôt ; l'IBM 7030 Stretch (1960), une machine à mots de 64 bits, est considéré comme la première machine à pipe-line. Le Stretch succédait au 704 et devait être 100 fois plus puissant. Il n'en a été construit que seize exemplaires ² mais cette machine a représenté une étape importante avec beaucoup d'innovations.

Le Control Data 6600, une autre machine novatrice apparue en 1964, considérée comme le premier super-ordinateur et dont l'architecte principal était Seymour Cray, comportait aussi une structure de pipe-line, et ses concepteurs avaient compris que pour qu'elle fonctionne efficacement il fallait des instructions simples, de longueur fixe, toutes à peu près de la même durée d'exécution, si possible en un cycle. Seymour Cray poussera ces principes à l'extrême dans les super-ordinateurs vectoriels qu'il construira sous son nom pour Cray Research, et qui furent les plus puissants de leur époque.

Cette technique du pipe-line et l'évolution consécutive des techniques de compilation se sont beaucoup développées avec l'apparition à la fin des années 1980 des processeurs à architecture RISC (Reduced Instruction Set Computer), par opposition à la mode précédente rétrospectivement baptisée CISC (Complex Instruction Set Computer).

Les machines CISC qui ont connu leur apogée au début des années 1980 (VAX de Digital Equipment Corporation, 68000 de Motorola) avaient un jeu d'instructions très vaste (plus de 300 pour le VAX) et très complexe, avec des instructions de longueurs différentes, et même parfois de longueur variable selon les opérandes. La richesse du jeu d'instructions était censée faciliter la tâche des programmeurs qui utilisaient le langage assembleur et, surtout, des auteurs de compilateurs pour langages évolué, en leur fournissant des instructions machine qui ressemblaient déjà à du langage évolué, plus facile et maniable pour le programmeur. D'ailleurs le langage C, langage évolué de bas niveau (on a pu le qualifier d'assembleur portable, la notion de portabilité désignant l'aptitude à fonctionner sur des ordinateurs d'architectures différentes), est assez largement inspiré de l'assembleur des ordinateurs PDP, ancêtres des VAX.

Cette richesse et cette complexité du jeu d'instructions avaient bien sûr un coût en termes de complexité et de lenteur du processeur. Le risque était notamment que les instructions simples (chargement de registre depuis la mémoire, copie de registre vers la mémoire, addition registre à registre) soient condamnées à s'exécuter aussi lentement que les opérations complexes (copie de zone mémoire à zone mémoire de longueur variable, opérations complexes en mémoire). Le VAX notamment n'esquivait guère ce risque.

Dans la seconde moitié des années 1970 des chercheurs ont fait des statistiques sur la composition en instructions des programmes en langage machine, soit qu'ils aient été directement écrits en assembleur, soit qu'ils aient été produits par un compilateur. Citons notamment les travaux de D.A. Fairclough, (A unique microprocessor instruction set, IEEE Micro, mai 1982 [24]). Ils constatèrent d'abord que 43% des instructions étaient des déplacements de données d'un endroit à un autre, que le quart des instructions étaient des branchements, ensuite que pour chaque programme le nombre d'instructions utilisées était très réduit, enfin que seules les instructions les plus simples étaient largement utilisées. Une autre constatation était que les opérations de loin les plus coûteuses étaient l'appel de sous-programme (un programme lance l'exécution d'un autre programme en lui communiquant des paramètres) et le retour d'un sous-programme au programme principal.

Sur la base de ces constatations ils préconisèrent de concevoir des processeurs avec un jeu réduit d'instructions plus simples. La notion de processeur RISC était née, et le premier processeur de ce type, l'IBM 801, fut réalisé par John Cocke en 1979. La société MIPS, fondée par John Hennessy, pionnier du RISC à l'Université Stanford, fut créée en 1985. Hewlett-Packard fut le premier grand constructeur d'ordinateurs à réaliser toute sa gamme en architecture RISC en 1986. Sun et Digital Equipment suivirent. Le livre emblématique de la révolution RISC, Computer architecture: a quantitative approach [28], a été écrit par John L. Hennessy, l'architecte des processeurs MIPS, et David A. Patterson, originaire du campus de Berkeley, l'architecte des processeurs SPARC de Sun. Les processeurs MIPS ont été les premiers à défricher la voie, et les plus hardiment innovateurs : nous l'avons vu au chapitre 4 à propos de l'utilisation du TLB. Il faudrait ajouter à ce répertoire Richard L. Sites, l'architecte des processeurs Alpha de Digital.

Les traits les plus frappants initialement dans les architectures RISC étaient le petit nombre d'instructions, avec l'absence d'instructions mémoire--mémoire : il n'y avait que des chargements de mémoire dans un registre, des copies de registre vers la mémoire et des opérations dans les registres.

D'autres traits se révélèrent bientôt aussi importants : longueur et format d'instruction fixes, usage intensif du pipe-line. Pour tirer parti correctement d'une architecture aussi ascétique une grande part de la complexité était reportée sur les compilateurs, qui devaient produire un code capable d'utiliser efficacement les registres et le pipe-line.

La nouvelle architecture se révéla bientôt extrêmement rapide, et doublement rapide : en effet, pour tirer parti d'un progrès de la micro-électronique, il ne suffit pas de concevoir un processeur rapide, il faut aussi que le délai nécessaire à sa conception ne soit pas trop long. La simplicité du RISC était aussi un atout de ce côté. Actuellement il faut à peu près trois ans à une équipe de 100 à 200 ingénieurs pour concevoir un nouveau processeur. Une usine entièrement équipée pour le construire coûtera de l'ordre de quatre milliards de dollars. La conception d'une architecture novatrice demande une douzaine d'années.

La technologie CISC parut condamnée, ce qui fut effectivement le cas pour les gammes VAX et Motorola 68000. Tout le monde attendait la chute de l'architecture x86 d'Intel, sur laquelle reposent les dizaines de millions de PC vendus chaque année. C'était compter sans les efforts qu'Intel pouvait mobiliser grâce à la rente du PC. Les Pentium actuels sont en fait des processeurs constitués d'un noyau RISC autour duquel des circuits supplémentaires et du micro-code (notion introduite ci-dessous à la section 9.2.4) simulent l'ancienne architecture CISC afin de préserver la compatibilité avec les systèmes et les programmes existants.

Quant à la gamme des grands systèmes IBM, l'immense stock de programmes existants dont la conversion exigerait des dépenses phénoménales semble la vouer à une immortalité dont l'érosion ne se fait qu'au gré du changement lent des applications.

Même si l'évolution actuelle suggère un demi-échec de l'architecture RISC dont la remplaçante VLIW (Very Long Instruction Word) entre en scène avec l'architecture IA-64 conçue conjointement par Intel et Hewlett-Packard, tous les processeurs modernes ont intégré sa leçon. Le mouvement RISC a profondément révolutionné la conception des processeurs et aussi, de façon moins spectaculaire mais aussi profonde, celle des techniques de compilation. En fait, hommage du vice à la vertu, tous les processeurs modernes comportent un coeur RISC entouré de circuits qui procurent un décor différent, Pentium par exemple. Même les grands systèmes IBM sont maintenant animés par des microprocesseurs qui implémentent leur jeu d'instructions traditionnel en RISC.

9.2.4 Micro-code : le retour

Le micro-code était un élément architectural intermédiaire entre le logiciel et le matériel, caractéristique des processeurs CISC, à peu près disparu sur les processeurs RISC. En fait il s'agissait d'une couche de logiciel de très bas niveau qui simulait certains éléments de matériel pour les présenter au logiciel. Ainsi l'architecture 360 comportait 16 registres généraux, mais les modèles les plus petits comme le 360/20 n'en avaient que deux (un accumulateur et un registre). La couche de micro-code, stockée dans une mémoire spéciale, présentait au système d'exploitation une machine virtuelle à 16 registres, implantée sur la machine réelle à deux registres. Une disquette permettait de charger en mémoire une nouvelle version du micro-code. Le BIOS des PCs Intel joue un peu le même rôle, il sert notamment à présenter les périphériques au système sous un aspect différent de leur réalité physique, ce qui permet par exemple de voir tous les disques de la même façon, avec un adressage linéaire des blocs de données, quelle que soit leur structure réelle. Le micro-code était un facteur de complexité et de lenteur, ce pourquoi la révolution RISC en a fait table rase. Mais ne survit-il pas en fait à l'intérieur du processeur ? Si bien sûr : les processeurs modernes sont si complexes et embarquent tellement de mémoire sur le chip (la puce proprement dite) que leur réalisation est elle-même micro-programmée. Le processeur Intel Pentium, de la famille CISC, est construit autour d'un coeur RISC entouré de micro-code qui simule l'architecture officielle. Le micro-code est aussi présent dans les contrôleurs de disques et autres périphériques. À l'heure où il a officiellement disparu, il n'a jamais autant existé.

9.2.5 Super-scalaire

La décomposition des instructions en étapes plus élémentaires que nous avons examinée à la section 9.2.1 permet le pipe-line, mais aussi une autre forme de simultanéité que l'on appelle « super-scalaire », et qui consiste à avoir plusieurs unités d'exécution actives simultanément, selon le modèle de la figure 9.1. Ce modèle d'exécution se combine avec le pipe-line dans les architectures modernes.

Figure 9.1 : Modèle de l'exécution super-scalaire.

Les instructions sont décodées à l'avance et emmagasinées dans le buffer, qui est en fait un jeu de registres. Dès qu'une unité d'exécution se libère, une instruction est extraite du buffer pour être exécutée. L'architecture super-scalaire de la figure 9.1 peut exécuter quatre instructions par cycle. Si de plus le pipe-line a divisé le temps de cycle par trois, la combinaison de ces deux techniques a multiplié la vitesse de notre processeur par 12 à technologie micro-électronique constante. Évidemment, ceci est vrai en l'absence de dépendances entre les données manipulées par les instructions successives, parce que si le pipe-line introduisait des problèmes en cas de branchement, le traitement super-scalaire introduit des risques de collisions de données. Supposons une machine à seize registres, deux unités d'exécution et le programme suivant :

N°	Buffer	Unité	Unité
d'ordre		d'exécution 1	d'exécution 2
1	R2 + R3 ® R4
2	R5 - R6 ® R7
3	LOAD R8, COUNT
4	R8 * R2 ® R3
		R2 + R3 ® R4	R5 - R6 ® R7
	conflit de données ®	LOAD R8, COUNT
	potentiel évité ici	R8 * R2 ® R3

Le conflit de données est le suivant : l'instruction 3 charge le registre R8 avec la valeur contenue à l'adresse mémoire COUNT. L'instruction 4 effectue la multiplication des contenus des registres R8 et R2 et écrit le résultat dans R3. L'écriture rigoureusement fidèle à von Neumann de notre programme stipule une exécution séquentielle, l'instruction 4 suit l'instruction 3 et utilise dans R8 la valeur que cette dernière y aura déposée.

Si nous lançons l'instruction 3 dans l'unité d'exécution 1 et, simultanément, l'instruction 4 dans l'unité d'exécution 2, quelle sera la valeur du contenu de R8 utilisée par l'instruction 4 ? Celle qui résulte de l'exécution de l'instruction 3, ou celle qu'il contenait auparavant ? La réponse à cette question est indéterminée, et pour maintenir la sémantique d'une machine de von Neumann le processeur doit contenir une logique capable de détecter ce problème et de décider de ne pas exécuter ces deux instructions simultanément, ce qu'illustre notre figure. Cette détection doit avoir lieu dynamiquement, à la volée, pour chaque exécution de cette séquence d'instructions.

L'évitement des conflits de données complique le circuit et diminue le bénéfice attendu de l'architecture super-scalaire. Ce bénéfice reste néanmoins suffisant pour que tous les processeurs modernes utilisent ces techniques, même au prix d'une complexité proprement diabolique. La section suivante nous montrera comment les architectes de processeurs se sont débarrassés de cette complexité et ont passé la patate chaude aux auteurs de compilateurs.

Bien évidemment, les difficultés que nous avons signalées à la section 9.2.2 au sujet du pipe-line et qui procèdent de la survenue d'événements asynchrones (les interruptions) dans un contexte où plusieurs instructions sont en cours d'exécution à des stades variés d'achèvement, ces difficultés se retrouvent encore aggravées par l'exécution super-scalaire, puisque ce modèle respecte encore moins l'ordre d'exécution que le pipe-line.

9.2.6 Architecture VLIW (Very Long Instruction Word)

Les modèles d'exécution en pipe-line et super-scalaire ont l'avantage considérable sur les architectures SIMD ou MIMD de préserver la sémantique de l'architecture de von Neumann, ce qui permet de continuer à utiliser les langages de programmation traditionnels avec les méthodes et les compétences qui existent et qui sont éprouvées. Le prix à payer pour cet avantage, c'est d'avoir à faire de la prédiction de branchement, de la prévention de conflits de données et du traitement d'interruptions imprécises, et nous avons vu que ce n'était pas précisément simple.

L'espoir forcément est né de bénéficier des avantages sans avoir à supporter les inconvénients. La différence entre le monde de la technique et celui des relations humaines, c'est que dans le premier une telle idée est vertueuse.

Pour faire fonctionner pipe-line et multiples unités d'exécution sans arrêts brutaux, il suffirait que le programme (ou plutôt le compilateur qui traduit le programme en langage machine) « dise » au processeur quelles sont les instructions susceptibles d'être exécutées simultanément sans risque de conflit de branchement ou de données, et que le processeur soit équipé d'un format d'instruction capable de recevoir ces informations.

Les ingénieurs de Hewlett-Packard et d'Intel ont réuni leurs efforts pour concevoir une telle architecture, connue sous le nom propre IA-64, qui est une architecture VLIW (Very Long Instruction Word). La conception de IA-64 a pris une douzaine d'années avant de déboucher en 2001 sur la livraison d'un premier processeur, Itanium.

Parallélisme explicite

La méthode mise en oeuvre par IA-64 s'appelle EPIC (Explicitly Parallel Instruction Computing). Le processeur reçoit du compilateur une liasse (bundle) de 128 bits. Chaque liasse comporte trois instructions de 41 bits et un masque (template) de 5 bits. Chaque instruction comporte trois numéros de registre de sept bits chacun (ce qui autorise 2⁷=128 registres), six bits de registre de prédicat (predicate register) et un code opération de 13 bits.
Liasse (bundle) IA-64

Instruction	Instruction	Instruction	Masque (5 bits)
(41 bits)	(41 bits)	(41 bits)	(template)

Instruction IA-64

code	n° registre prédicat	n° registre 1	n° registre 2	n° registre 3
opération	(predicate register)

Les cinq bits de masque indiquent quelles sont les instructions qui peuvent s'exécuter en parallèle, ainsi que l'éventualité du chaînage de cette liasse avec une autre liasse qui en contiendrait la suite. Les compilateurs peuvent placer dans ce masque des valeurs qui indiquent au processeur les instructions à lancer en parallèle³.

Confier au compilateur tout ce travail auparavant réalisé par le processeur présente plusieurs avantages. Le processeur ne possède aucune information a priori sur le programme qu'il exécute, il ne peut que les déduire du texte binaire au fur et à mesure qu'il en décode les instructions, tandis que l'auteur du compilateur peut se conformer à une stratégie systématique d'organisation des instructions.

De plus, le compilateur peut passer beaucoup de temps à optimiser le code, en principe le programme n'est compilé que par son auteur, ou par celui qui l'installe sur un ordinateur, alors qu'il sera exécuté par de nombreux utilisateurs. Il est efficace de consacrer du temps à la compilation pour en gagner à l'exécution.

Élimination de branchements

Imaginons le fragment de programme suivant en pseudo--langage évolué :

Si I égale 0
   Alors
      instruction 1
   Sinon
      instruction 2

que le compilateur traduirait en pseudo--assembleur pour un processeur RISC classique (non--EPIC) :

       COMPARE I à 0
       SAUTE   à l'étiquette SINON si non-égal
ALORS: instruction 1
       SAUTE   à l'étiquette SUITE
SINON: instruction 2
SUITE:

Voici comment procédera un processeur EPIC :

COMPARE I à 0
commence à décoder instruction 1, 
     le prédicat positionné pour pointer sur le registre de
     prédiction P1
commence à décoder instruction 2, 
     le prédicat positionné pour pointer sur le registre de
     prédiction P2
si I égale 0, positionner le registre P1 à vrai (1),
              positionner le registre P2 à faux (0)
calculer et délivrer les résultats de toutes les 
     instructions dont le prédicat pointe sur le 
     registre dont la valeur est vrai (1), en 
     l'occurrence P1.

Le processeur n'exécute aucun saut (débranchement), il commence à exécuter simultanément les branches ALORS et SINON comme s'il s'agissait d'instructions en séquence.

IA-64 prévoit 64 registres de prédicat susceptibles de recevoir les valeurs vrai ou faux (0 ou 1). Le champ registre de prédicat de chaque instruction pointe sur un registre de prédicat. Quand le processeur a fini de comparer I à 0, seuls les résultats des instructions qui pointent sur un registre de prédicat qui vaut vrai (1) sont délivrés.

Considérons ce qui se passe : d'abord, il n'y a aucun risque à commencer l'exécution simultanée des branches ALORS et SINON de ce programme, il n'y a par construction aucune dépendance entre elles puisqu'elles sont exclusives l'une de l'autre. Ensuite nous pouvons observer que notre pseudo--code EPIC ne comporte plus de branchement : ce n'est pas un tour de passe-passe, cette suppression de la plupart des branchements est un fondement du modèle EPIC.

Mais, pourra objecter le lecteur vigilant, en quoi cette suppression des branchements peut-elle être bénéfique pour les performances ? Après tout le processeur EPIC, en commençant à exécuter les deux branches du programme, effectue deux fois plus de travail qu'un processeur classique qui essaie de prévoir quelle branche va être exécutée réellement (et il faut savoir que les processeurs modernes sont capables de faire une prédiction juste dans 90% des cas), et la moitié de ce travail est inutile, puisque finalement seule une des branches sera retenue.

= .9@percentPremier temps de la réponse à l'objection : d'abord exécuter les deux branches en parallèle ne fait pas perdre de temps, puisqu'elles sont indépendantes l'une de l'autre et que notre processeur dispose de tous les bons dispositifs super-scalaires, notamment des unités d'exécution multiples, pour que le parallélisme soit effectif. Ensuite, pour les 10% de cas dans lesquels le processeur classique prédit la mauvaise branche le gain est considérable, puisqu'alors le processeur classique doit tout reprendre au départ. Enfin puisque le texte du programme ne contient plus de branchements il n'est plus divisé en petits blocs ALORS/SINON, ce qui autorise les instructions des branches à être placées dans des liasses ou des chaînes de liasses, associées aux instructions précédentes ou suivantes. Associées signifie ici éligibles pour le parallélisme explicite. = .15@percent

Optimisation des accès mémoire : chargement anticipé

Dans le modèle VLIW, comme dans le modèle RISC, les opérandes d'une instruction doivent être chargés dans des registres avant d'être traités. L'exécution efficace de l'instruction LOAD est donc un élément crucial de l'architecture. Pour en comprendre les ressorts nous invitons le lecteur à se remettre tout d'abord en mémoire ce qui a été écrit sur la technique du cache à la section 4.6.1.

Les développements sur le cache ont montré l'extrême importance de sa bonne gestion. Si par malheur au moment où le processeur essayait d'exécuter une instruction LOAD la zone mémoire recherchée n'était pas dans le cache il en résulterait une pénalité de l'ordre de 20 cycles au moins, autant dire que le fruit de tous nos efforts de parallélisme et de pipe-lining serait anéanti, et au-delà. Il est donc crucial d'éviter de telles situations. Pour ce faire un processeur moderne (EPIC comme l'Itanium, mais aussi RISC comme l'Alpha ou CISC comme l'AMD Athlon) aura recours au chargement anticipé dans le cache L1 des zones mémoires qui seront nécessaires aux instructions appelées à s'exécuter dans les quelques dizaines de cycles qui suivent. C'est le chargement spéculatif.

De la programmation VLIW

Arrivé ici, le lecteur sera en droit de penser que les notions qu'il pouvait avoir de la programmation des ordinateurs viennent de recevoir un sacré surcroît de complexité, et il n'aura pas tort. Il pourra alors se dire que cette activité qui lui semblait banale prend enfin des couleurs attrayantes, ou au contraire que c'est trop effrayant et qu'il renonce à son projet de s'y engager.

En fait, ce qui se complique, c'est la programmation en langage machine ou en assembleur. Aujourd'hui pratiquement personne ne programme plus en langage machine, et quand on le fait ce sont des programmes très brefs, comme une séquence d'amorçage (boot). Quant à la programmation en assembleur, elle est réservée aux auteurs de systèmes d'exploitation et aux auteurs de compilateurs. L'immense majorité des programmes sont écrits de nos jours en langage évolué, et sont traduits en assembleur, puis en langage machine, par un compilateur. Beaucoup de programmes embarqués (à bord d'avions, de voitures, de fours à micro-ondes, de téléphones portables) étaient encore il y a peu écrits en assembleur pour des raisons de performance et d'encombrement : les progrès de la micro-électronique permettent aujourd'hui de les écrire dans des langages hyper-évolués tels que Java ou Ada. Certains compilateurs ne sont pas écrits en assembleur et ne produisent pas directement de l'assembleur : il traduisent le langage source auquel ils sont destinés vers un langage cible de plus bas niveau, qui dispose lui-même d'un compilateur vers l'assembleur, appelé compilateur en mode natif.

Pour nous résumer, le lecteur qui se sent irrésistiblement attiré par les subtilités de la programmation en assembleur pour une architecture VLIW doit se tourner vers l'écriture de compilateurs ou de systèmes d'exploitation. Il n'aura pas à le regretter, ce sont des domaines passionnants, en évolution rapide et où le chômage ne menace pas. Le lecteur que la complexité de ces techniques rebuterait peut être rassuré : l'auteur de programmes en langage évolué n'a pas à se préoccuper de détails techniques d'aussi bas niveau, les langages modernes procurent tous à leurs programmeurs un niveau d'abstraction qui leur permet de se consacrer au problème à programmer plutôt qu'aux détails techniques de l'ordinateur.

1: Le Britannique C. Antony R. Hoare est à l'origine de quelques contributions de premier plan. Des études universitaires de tonalité plutôt littéraire lui ont donné l'occasion de partir en stage en 1960 dans le laboratoire de Kolmogorov à l'Université de Moscou pour travailler sur un projet de traduction automatique. Pour réaliser un dictionnaire électronique nécessaire à ce projet (par ailleurs vite abandonné) il inventa l'algorithme de tri « Quicksort » que tout étudiant en informatique se doit d'avoir étudié en détail et programmé. Ce stage lui avait donné le goût de la programmation, mais, comme il le raconte lui-même avec humour, il eut la chance que sa formation initiale lui fermât les portes du UK National Physical Laboratory, et il entra dans l'industrie. C'est là qu'il eut l'occasion de participer au développement de systèmes d'exploitation, domaine pour lequel il élabora la méthode des moniteurs de Hoare afin de contrôler les accès concurrents et exclusifs à des ressources partagées et la théorie des processus séquentiels communicants, encore aujourd'hui le seul modèle complet et cohérent qui excède réellement le modèle de von Neumann.
2: La console de l'un d'eux, acquis par le CEA, figure dans les réserves du Musée National des Techniques au Conservatoire National des Arts et Métiers, d'où elle est parfois extraite pour des expositions temporaires.
3: Pour ce faire, le processeur Itanium, premier de l'architecture IA-64, possède deux unités d'exécution d'instructions arithmétiques entières, deux unités d'exécution d'instructions arithmétiques à virgule flottante, trois unités de chargement -- déchargement de registre, un pipe-line à dix étages.