Fonctionnement d'un ordinateur/L'unité de chargement et le program counter

L'unité de contrôle s'occupe du chargement des instructions et de leur interprétation, leur décodage. Elle contient deux circuits : l'unité de chargement qui charge l'instruction depuis la mémoire, et le séquenceur qui commande le chemin de données. Les deux circuits sont séparés, mais ils communiquent entre eux, notamment pour gérer les branchements. Dans ce chapitre, nous allons nous intéresser au chargement d'une instruction depuis la RAM/ROM, nous verrons l'étape de décodage de l'instruction au prochain chapitre.

Le chargement d'une instruction

Étape de chargement.

L'étape de chargement (ou fetch) doit faire deux choses : mettre à jour le program counter et lire l'instruction en mémoire RAM ou en ROM. Les deux étapes peuvent être faites en parallèle, dans des circuits séparés. Pendant que l'instruction est lue depuis la mémoire RAM/ROM, le program counter est incrémenté et/ou altéré par un branchement.

Pour lire l'instruction, on envoie le program counter sur le bus d'adresse et on récupère l'instruction sur le bus de données pour l'envoyer sur l'entrée du séquenceur. Et cela demande de connecter le séquenceur au bus mémoire, à travers l'interface mémoire. Et sur ce point, la situation est différente selon que l'on parler d'une architecture Harvard ou Von Neumann.

Les interconnexions entre séquenceur et bus mémoire

Sur les architectures Harvard, le séquenceur et le chemin de donnée utilisent des interfaces mémoire séparées. Le séquenceur est directement relié au bus mémoire de la ROM, alors que le chemin de données est connecté à la RAM.

Microarchitecture de l'interface mémoire d'une architecture Harvard

Mais sur les architectures Von-Neumann et affiliées, le séquenceur et le chemin de donnée partagent la même interface mémoire. Et cela pose deux problèmes.

Le premier problème est que le bus mémoire doit être libéré une fois l'instruction chargée, pour un éventuel accès mémoire. Mais le séquenceur doit conserver une copie de l'instruction chargée, sans quoi il ne peut pas décoder l'instruction correctement. Par exemple, si l'instruction met plusieurs cycles à s'exécuter, le séquenceur doit conserver une copie de l'instruction durant ces plusieurs cycles. La solution à ce problème est un registre d'instruction situé juste avant le séquenceur, qui mémorise l'instruction chargée.

Registre d'instruction.

Le second problème est de gérer le flot des instructions/données entre le bus mémoire, le chemin de données et le séquenceur. Le processeur doit connecter l'interface mémoire soit au séquenceur, soit au chemin de données et cela complique le réseau d'interconnexion interne au processeur.

Une première solution utilise un bus unique qui relie l'interface mémoire, le séquenceur et le chemin de données. Pour charger une instruction, le séquenceur copie le program counter sur le bus d'adresse, attend que l'instruction lue soit disponible sur le bus de données, puis la copie dans le registre d'instruction. Le bus mémoire est alors libre et peut être utilisé pour lire ou écrire des données, si le besoin s'en fait sentir.

Il faut noter que l'usage d'un bus unique a un impact sur l'organisation interne du chemin de données. Par exemple, le chapitre précédent nous a montré comment implémenter un chemin de données basique, avec des multiplexeurs et démultiplexeurs. Et bien ces chemins de données ne marchent pas vraiment avec un bus interne unique. Il est possible de les adapter, mais au prix d'une complexité largement supérieure. Un bus interne unique marche mieux quand le banc de registre est mono-port. C'est pourquoi il a été utilisé sur d'anciennes architectures appelées des architectures à accumulateur et à pile, que nous verrons dans quelques chapitres, qui utilisaient un banc de registre mono-port.

Microarchitecture de l'interface mémoire d'une architecture von neumann

Une autre solution utilise deux bus interne séparés : un connecté au bus d'adresse, l'autre au bus de données. Le program counter est alors connecté au bus interne d'adresse, le séquenceur est relié au bus interne de données. Notons que la technique marche bien si le program counter est dans le banc de registre : les interconnexions utilisées pour gérer l'adressage indirect permettent d'envoyer le program counter sur le bus d'adresse sans ajout de circuit.

Le tout peut être amélioré en remplaçant les deux bus par des multiplexeurs et démultiplexeurs. Le bus d'adresse est précédé par un multiplexeur, qui permet de faire le choix entre Program Counter, adresse venant du chemin de données, ou adresse provenant du séquenceur (adressage absolu). De même, le bus de données est suivi par un démultiplexeur qui envoie la donnée/instruction lue soit au registre d'instruction, soit au chemin de données. Le tout se marie très bien avec les chemins de donnée vu dans le chapitre précédent. Au passage, il faut noter que cette solution nécessite un banc de registre multi-port.

Connexion du program counter sur les bus avec PC isolé

Le chargement des instructions de longueur variable

Le chargement des instructions de longueur variable pose de nombreux problèmes. Le premier est que mettre à jour le program counter demande de connaitre la longueur de l'instruction chargée, pour l'ajouter au program counter. Si la longueur d'une instruction est variable, on doit connaitre cette longueur d'une manière où d'une autre. La solution la plus simple indique la longueur de l'instruction dans une partie de l'opcode ou de la représentation en binaire de l'instruction. Mais les processeurs haute performance de nos PC utilisent d'autres solutions, qui n'encodent pas explicitement la taille de l'instruction.

Les processeurs récents utilisent un registre d'instruction de grande taille, capable de mémoriser l'instruction la plus longue du processeur. Par exemple, si un processeur supporte des instructions allant de 1 à 8 octets, comme les CPU x86, le registre d'instruction fera 8 octets. Le décodeur d'instruction vérifie à chaque cycle le contenu du registre d'instruction. Si une instruction est détectée dedans, son décodage commence, peu importe la taille de l'instruction. Une fois l'instruction exécutée, elle est retirée du registre d'instruction. Reste à alimenter le registre d'instruction, à charger des instructions dedans. Et pour cela deux solutions : soit on charge l'instruction en plusieurs fois, soit d'un seul coup.

La solution la plus simple charge les instructions par mots de 8, 16, 32, 64 bits. Ils sont accumulés dans le registre d'instruction jusqu'à détecter une instruction complète. La technique marche nettement mieux si les instructions sont très longues. Par exemple, les CPU x86 ont des instructions qui vont de 1 à 15 octets, ce qui fait qu'ils utilisent cette technique. Précisément, elle marche si les instructions les plus longues sont plus grandes que le bus mémoire.

Une autre solution charge un bloc de mots mémoire aussi grand que la plus grande instruction. Par exemple, si le processeur gère des instructions allant de 1 à 4 octets, il charge 4 octets d'un seul coup dans le registre d'instruction. Il va de soit que cette solution ne marche que si les instructions du processeur sont assez courtes, au plus aussi courtes que le bus mémoire. Ainsi, on est sûr de charger obligatoirement au moins une instruction complète, et peut-être même plusieurs. Le contenu du registre d'instruction est alors découpé en instructions au fil de l'eau.

Utiliser un registre d'instruction large pose problème avec des instructions à cheval entre deux blocs. Il se peut qu'on n'ait pas une instruction complète lorsque l'on arrive à la fin du bloc, mais seulement un morceau. Le problème se manifeste peu importe que l'instruction soit chargée d'un seul coup ou bien en plusieurs fois.

Instructions non alignées.

Dans ce cas, on doit décaler le morceau de bloc pour le mettre au bon endroit (au début du registre d'instruction), et charger le prochain bloc juste à côté. On a donc besoin d'un circuit qui décale tous les bits du registre d'instruction, couplé à un circuit qui décide où placer dans le registre d'instruction ce qui a été chargé, avec quelques circuits autour pour configurer les deux circuits précédents.

Décaleur d’instruction.

Une autre solution se passe de registre d'instruction en utilisant à la place l'état interne du séquenceur. Là encore, elle charge l'instruction morceau par morceau, typiquement par blocs de 8, 16 ou 32 bits. Les morceaux ne sont pas accumulés dans le registre d'instruction, la solution utilise à la place l'état interne du séquenceur. Les mots mémoire de l'instruction sont chargés à chaque cycle, faisant passer le séquenceur d'un état interne à un autre à chaque mot mémoire. Tant qu'il n'a pas reçu tous les mots mémoire de l'instruction, chaque mot mémoire non terminal le fera passer d'un état interne à un autre, chaque état interne encodant les mots mémoire chargés auparavant. S'il tombe sur le dernier mot mémoire d'une instruction, il rentre dans un état de décodage.

L'incrémentation du program counter

À chaque chargement, le program counter est mis à jour afin de pointer sur la prochaine instruction à charger. Sur la quasi-totalité des processeurs, les instructions sont placées dans l'ordre d’exécution dans la RAM. En faisant ainsi, on peut mettre à jour le program counter en lui ajoutant la longueur de l'instruction courante. Déterminer la longueur de l'instruction est simple quand les instructions ont toutes la même taille, mais certains processeurs ont des instructions de taille variable, ce qui complique le calcul. Dans ce qui va suivre, nous allons supposer que les instructions sont de taille fixe, ce qui fait que le program counter est toujours incrémenté de la même valeur.

Il existe deux méthodes principales pour incrémenter le program counter : soit le program counter a son propre additionneur, soit le program counter est mis à jour par l'ALU. Pour ce qui est de l'organisation des registres, soit le program counter est un registre séparé des autres, soit il est regroupé avec d'autres registres dans un banc de registre. En tout, cela donne quatre organisations possibles.

• Un program counter séparé relié à un incrémenteur séparé.
• Un program counter séparé des autres registres, incrémenté par l'ALU.
• Un program counter intégré au banc de registre, relié à un incrémenteur séparé.
• Un program counter intégré au banc de registre, incrémenté par l'ALU.

les différentes méthodes de calcul du program counter.

Les processeurs haute performance modernes utilisent tous la première méthode. Les autres méthodes étaient surtout utilisées sur les processeurs 8 ou 16 bits, elles sont encore utilisées sur quelques microcontrôleurs de faible puissance. Nous auront l'occasion de donner des exemples quand nous parlerons des processeurs 8 bits anciens, dans le chapitre sur les architectures à accumulateur et affiliées.

Le program counter mis à jour par l'ALU

Sur certains processeurs, le calcul de l'adresse de la prochaine instruction est effectué par l'ALU. L'avantage de cette méthode est qu'elle économise un incrémenteur dédié au program counter. Ce qui explique que cette méthode était utilisée sur les processeurs assez anciens, à une époque où un additionneur pouvait facilement prendre 10 à 20% des transistors disponibles. Le désavantage principal est une augmentation de la complexité du séquenceur, qui doit gérer la mise à jour du program counter. De plus, la mise à jour du program counter ne peut pas se faire en même temps qu'une opération arithmétique, ce qui réduit les performances.

Si on incrémente le program counter avec l'ALU, il est intéressant de le placer dans le banc de registres. Un désavantage est qu'on perd un registre. Par exemple, avec un banc de registre de 16 registres, on ne peut adresser que 15 registres généraux. De plus ce n'est pas l'idéal pour le décodage des instructions et pour le séquenceur. Si le processeur dispose de plusieurs bancs de registres, le program counter est généralement placé dans le banc de registre dédié aux adresses. Sinon, il est placé avec les nombres entiers/adresses.

D'anciens processeurs incrémentaient le program counter avec l'ALU, mais utilisaient bien un registre séparé pour le program counter. Cette méthode est relativement simple à implémenter : il suffit de connecter/déconnecter le program counter du bus interne suivant les besoins. Le program counter est déconnecté pendant l’exécution d'une instruction, il est connecté au bus interne pour l'incrémenter. C'est le séquenceur qui gère le tout. L'avantage de cette séparation est qu'elle est plus facile à gérer pour le séquenceur. De plus, on gagne un registre général/entier dans le banc de registre.

Le compteur programme

Dans la quasi-totalité des processeurs modernes, le program counter est un vulgaire compteur comme on en a vu dans les chapitres sur les circuits, ce qui fait qu'il passe automatiquement d'une adresse à la suivante. Dans ce qui suit, nous allons appeler ce registre compteur : le compteur ordinal. L'usage d'un compteur simplifie fortement la conception du séquenceur. Le séquenceur n'a pas à gérer la mise à jour du program counter, sauf en cas de branchements. De plus, il est possible d'incrémenter le program counter pendant que l'unité de calcul effectue une opération arithmétique, ce qui améliore grandement les performances. Le seul désavantage est qu'elle demande d'ajouter un incrémenteur dédié au program counter.

Sur les processeurs très anciens, les instructions faisaient toutes un seul mot mémoire et le compteur ordinal était un circuit incrémenteur des plus basique. Sur les processeurs modernes, le compteur est incrémenté par pas de 4 si les instructions sont codées sur 4 octets, 8 si les instructions sont codées sur 8 octets, etc. Concrètement, le compteur est un circuit incrémenteur auquel on aurait retiré quelques bits de poids faible. Par exemple, si les instructions sont codées sur 4 octets, on coupe les 2 derniers bits du compteur. Si les instructions sont codées sur 8 octets, on coupe les 3 derniers bits du compteur. Et ainsi de suite.

Il a existé quelques processeurs pour lesquelles le program counter était non pas un compteur binaire classique, mais un linear feedback shift register. L'avantage est que le circuit d'incrémentation utilisait bien moins de portes logiques, l'économie était substantielle. Mais un défaut est que des instructions consécutives dans le programme n'étaient pas consécutives en mémoire. Il existait cependant une table de correspondance pour dire : la première instruction est à telle adresse, la seconde à telle autre, etc. Un exemple de processeur de ce type est le TMS 1000 de Texas Instrument, un des premiers microcontrôleur 4 bits datant des années 70.

Une amélioration de la solution précédente utilise un circuit incrémenteur partagé entre le program counter et d'autres registres. L'incrémenteur est utilisé pour incrémenter le program counter, mais aussi pour effectuer d'autres calculs d'adresse. Par exemple, sur les architectures avec une pile d'adresse de retour, il est possible de partager l'incrémenteur/décrémenteur avec le pointeur de pile ( la technique ne marche pas avec une pile d'appel). Un autre exemple est celui des processeurs qui gèrent automatiquement le rafraichissement mémoire, grâce à, un compteur intégré dans le processeur. Il est possible de partager l'incrémenteur du program counter avec le compteur de rafraichissement mémoire, qui mémorise la prochaine adresse mémoire à rafraichir. Nous avions déjà abordé ce genre de partage dans le chapitre sur le chemin de données, dans l'annexe sur le pointeur de pile, mais nous verrons d'autres exemples dans le chapitre sur les architectures hybride accumulateur-registre 8/16 bits.

Quand est mis à jour le program counter ?

Le program counter est mis à jour quand il faut charger une nouvelle instruction. Reste qu'il faut savoir quand le mettre à jour. Incrémenter le program counter à intervalle régulier, par exemple à chaque cycle d’horloge, fonctionne sur les processeurs où toutes les instructions mettent le même temps pour s’exécuter. Mais de tels processeurs sont très rares. Sur la quasi-totalité des processeurs, les instructions ont une durée d’exécution variable, elles ne prennent pas le même nombre de cycle d'horloge pour s’exécuter. Le temps d’exécution d'une instruction varie selon l'instruction, certaines sont plus longues que d'autres. Tout cela amène un problème : comment incrémenter le program counter avec des instructions avec des temps d’exécution variables ?

La réponse est que la mise à jour du program counter démarre quand l'instruction précédente a terminée de s’exécuter, plus précisément un cycle avant. C'est un cycle avant pour que l'instruction chargée soit disponible au prochain cycle pour le décodeur. Pour cela, le séquenceur doit déterminer quand l'instruction est terminée et prévenir le program counter au bon moment. Il faut donc une interaction entre séquenceur et circuit de chargement. Le circuit de chargement contient une entrée Enable, qui autorise la mise à jour du program counter. Le séquenceur met à 1 cette entrée pour prévenir au program counter qu'il doit être incrémenté au cycle suivant ou lors du cycle courant. Cela permet de gérer simplement le cas des instructions multicycles.

Commande de la mise à jour du program counter.

Toute la difficulté est alors reportée dans le séquenceur, qui doit déterminer la durée d'une instruction. Pour gérer la mise à jour du program counter, le séquenceur doit déterminer la durée d'une instruction. Cela est simple pour les instructions arithmétiques et logiques, qui ont un nombre de cycles fixe, toujours le même. Une fois l'instruction identifiée par le séquenceur, il connait son nombre de cycles et peut programmer un compteur interne au séquenceur, qui compte le nombre de cycles de l'instruction, et fournit le signal Enable au program counter. Mais cette technique ne marche pas vraiment pour les accès mémoire, dont la durée n'est pas connue à l'avance, surtout sur les processeurs avec des mémoires caches. Pour cela, le séquenceur détermine quand l'instruction mémoire est finie et prévient le program counter quand c'est le cas.

Il existe quelques processeurs pour lesquels le temps de calcul dépend des opérandes de l'instruction. On peut par exemple avoir une division qui prend 10 cycles avec certaines opérandes, mais 40 cycles avec d'autres opérandes. Mais ces processeurs sont rares et cela est surtout valable pour les opérations de multiplication/division, guère plus. Le problème est alors le même qu'avec les accès mémoire et la solution est la même : l'ALU prévient le séquenceur quand le résultat est disponible.

Les branchements et le program counter

Un branchement consiste juste à écrire l'adresse de destination dans le program counter. L'implémentation des branchements demande d'extraire l'adresse de destination et d'altérer le program counter quand un branchement est détecté. Pour cela, le décodeur d'instruction détecte si l'instruction exécutée est un branchement ou non, et il en déduit où trouver l'adresse de destination.

L'adresse de destination se trouve à un endroit qui dépend du mode d'adressage du branchement. Pour rappel, on distingue quatre modes d'adressage pour les branchements : direct, indirect, relatif et implicite. Pour les branchements directs, l'adresse est intégrée dans l'instruction de branchement elle-même et est extraite par le séquenceur. Pour les branchements indirects, l'adresse de destination est dans le banc de registre. Pour les branchements relatifs, il faut ajouter un décalage au program counter, décalage extrait de l'instruction par le séquenceur. Enfin, les instructions de retour de fonction lisent l'adresse de destination depuis la pile. L'implémentation de ces quatre types de branchements est très différente.

L'altération du program counter dépend de si le program counter est dans un compteur séparé ou s'il est dans le banc de registre. Nous avons vu plus haut qu'il y a quatre cas différents, mais nous n'allons voir que deux cas : celui où le program counter est dans le banc de registre et est incrémenté par l'unité de calcul, celui avec un program counter séparé avec son propre incrémenteur. Les deux autres cas ne sont utilisés que sur des architectures à accumulateur ou à pile spécifiques, que nous n'avons pas encore vu à ce stade du cours et que nous verrons en temps voulu dans le chapitre sur ces architectures.

L’implémentation des branchements avec un program counter intégré au banc de registres

Le cas le plus simple est celui où le program counter est intégré au banc de registre, avec une incrémentation faite par l'unité de calcul. Charger une instruction revient alors à effectuer une instruction LOAD en adressage indirect, à deux différences près : le registre sélectionné est le program counter, l’instruction est copiée dans le registre d'instruction et non dans le banc de registre. L'incrémentation du porgram counter est implémenté avec des micro-opérations qui agissent sur le chemin de données, au même titre que les branchements indirects, relatifs et directs.

• Les branchements indirects copient un registre dans le program counter, ce qui revient simplement à faire une opération MOV entre deux registres, dont le program counter est la destination.
• L'opération inverse d'un branchement indirect, qui copie le program counter dans un registre général, est utile pour sauvegarder l'adresse de retour d'une fonction.
• Les branchements directs copient une adresse dans le program counter, ce qui les rend équivalents à une opération MOV avec une constante immédiate, dont le program counter est la destination.
• Les branchements relatifs sont une opération arithmétique entre le program counter et un opérande en adressage immédiat.

En clair, à partir du moment où le chemin de données supporte les instructions MOV et l'addition, avec les modes d'adressage adéquat, il supporte les branchements. Aucune modification du chemin de données n'est nécessaire, le séquenceur gére le chargement d'une instruction avec les micro-instructions adéquates : une micro-opération ADD pour incrémenter le program counter, une micro-opération LOAD pour le chargement de l'instruction.

Notons que sur certaines architectures, le program counter est adressable au même titre que les autres registres du banc de registre. Les instructions de branchement sont alors remplacées par des instructions MOV ou des instructions arithmétique équivalentes, comme décrit plus haut.

L’implémentation des branchements avec un program counter séparé

Étudions maintenant le cas où le program counter est dans un registre/compteur séparé. Rappelons que tout compteur digne de ce nom possède une entrée de réinitialisation, qui remet le compteur à zéro. De plus, on peut préciser à quelle valeur il doit être réinitialisé. Ici, la valeur à laquelle on veut réinitialiser le compteur n'est autre que l'adresse de destination du branchement. Implémenter un branchement est donc simple : l'entrée de réinitialisation est commandée par le circuit de détection des branchements, alors que la valeur de réinitialisation est envoyée sur l'entrée adéquate. En clair, nous partons du principe que le program counter est implémenté avec ce type de compteur :

Fonctionnement d'un compteur (décompteur), schématique

Toute la difficulté est de présenter l'adresse de destination au program counter. Pour les branchements directs, l'adresse de destination est fournie par le séquenceur. L'adresse de destination du branchement sort du séquenceur et est présentée au program counter sur l'entrée adéquate. Voici donc comment sont implémentés les branchements directs avec un program counter séparé du banc de registres. Le schéma ci-dessous marche peu importe que le program counter soit incrémenté par l'ALU ou par un additionneur dédié.

Unité de détection des branchements dans le décodeur

Les branchements relatifs sont ceux qui font sauter X instructions plus loin dans le programme. Leur implémentation demande d'ajouter une constante au program counter, la constante étant fournie dans l’instruction. Là encore, deux solutions sont possibles : réutiliser l'ALU pour calculer l'adresse, ou utiliser un additionneur séparé. L'additionneur séparé peut être fusionné avec l'additionneur qui incrémente le program counter pour passer à l’instruction suivante.

Unité de chargement qui gère les branchements relatifs.

Pour les branchements indirects, il suffit de lire le registre voulu et d'envoyer le tout sur l'entrée adéquate du program counter. Il faut alors rajouter un multiplexeur pour que l'entrée de réinitialisationr ecoive la bonne adresse de destination.

Unité de chargement qui gère les branchements directs et indirects.

Toute la difficulté de l'implémentation des branchements est de configurer les multiplexeurs, ce qui est réalisé par le séquenceur en fonction du mode d'adressage du branchement.

Les optimisations du chargement des instructions

Charger une instruction est techniquement une forme d'accès mémoire un peu particulier. En clair, charger une instruction prend au minimum un cycle d'horloge, et cela peut rapidement monter à 3-5 cycles, si ce n'est plus. L'exécution des instructions est alors fortement ralentit par la mémoire. Par exemple, imaginez que la mémoire mette 3 cycles d'horloges pour charger une instruction, alors qu'une instruction s’exécute en 1 cycle (si les opérandes sont dans les registres). La perte de performance liée au chargement des instructions est alors substantielle. Heureusement, il est possible de limiter la casse en utilisant des mémoires caches, ainsi que d'autres optimisations, que nous allons voir dans ce qui suit.

Le tampon de préchargement

La technique dite du préchargement est utilisée dans le cas où la mémoire a un temps d'accès important. Mais si la latence de la RAM est un problème, le débit ne l'est pas. Il est possible d'avoir une RAM lente, mais à fort débit. Par exemple, supposons que la mémoire puisse charger 4 instructions (de taille fixe) en 3 cycles. Le processeur peut alors charger 4 instructions en un seul accès mémoire, et les exécuter l'une après l'autre, une par cycle d'horloge. Les temps d'attente sont éliminés : le processeur peut décoder une nouvelle instruction à chaque cycle. Et quand la dernière instruction préchargée est exécutée, la mémoire est de nouveau libre, ce qui masque la latence des accès mémoire.

Tampon de préchargement d'instruction

La seule contrainte est de mettre les instructions préchargées en attente. La solution pour cela est d'utiliser un registre d'instruction très large, capable de mémoriser plusieurs instructions à la fois. Ce registre est de plus connecté à un multiplexeur qui permet de sélectionner l'instruction adéquate dans ce registre. Ce multiplexeur est commandé par le program counter et quelques circuits annexes. Ce super-registre d'instruction est appelé un tampon de préchargement.

La méthode a une implémentation nettement plus simple avec des instructions de taille fixe, alignées en mémoire. La commande du multiplexeur de sélection de l'instruction est alors beaucoup plus simple : il suffit d'utiliser les bits de poids fort du program counter. Par exemple, prenons le cas d'un registre d'instruction de 32 octets pour des instructions de 4 octets, soit 8 instructions. Le choix de l'instruction à sélectionner se fait en utilisant les 3 bits de poids faible du program counter.

Mais cette méthode ajoute de nouvelles contraintes d'alignement, similaires à celles vues dans le chapitre sur l'alignement et le boutisme, sauf que l'alignement porte ici sur des blocs d'instructions de même taille que le tampon de préchargement. Si on prend l'exemple d'un tampon de préchargement de 128 bits, les instructions devront être alignées par blocs de 128 bits. C'est à dire qu'idéalement, les fonctions et autres blocs de code isolés doivent commencer à des adresses multiples de 128, pour pouvoir charger un bloc d'instruction en une seule fois. Sans cela, les performances seront sous-optimales.

Il arrive que le tampon de préchargement ait la même taille qu'une ligne de cache.

Lorsque l'on passe d'un bloc d'instruction à un autre, le tampon de préchargement est mis à jour. Par exemple, si on prend un tampon de préchargement de 4 instructions, on doit changer son contenu toutes les 4 instructions. La seule exception est l'exécution d'un branchement. En effet, lors d'un branchement, la destination du branchement n'est pas dans le tampon de préchargement et elle doit être chargée dedans (sauf si le branchement pointe vers une instruction très proche, ce qui est improbable). Pour cela, le tampon de préchargement est mis à jour précocement quand le processeur détecte un branchement.

Le même problème survient avec du code auto-modifiant. Un code auto-modifiant est un programme qui se modifie lui-même, en remplaçant certaines instructions par d'autres, en en retirant, en en ajoutant, lors de sa propre exécution. De tels programmes sont rares, mais la technique était utilisée dans quelques cas au tout début de l'informatique sur des ordinateurs rudimentaires. Ceux-ci avaient des modes d'adressages tellement limités que gérer des tableaux de taille variable demandait d'utiliser du code auto-modifiant pour écrire des boucles. Le problème survient quand des instructions sont modifiées immédiatement après avoir été préchargées. Les instructions dans le tampon de préchargement sont l'ancienne version, alors que la mémoire RAM contient les instructions modifiées. Gérer ce genre de cas demande de vider le tampon de préchargement si le cas arrive, mais ça ne vaut que très rarement le coup, aussi les ingénieurs ne s’embêtent pas à mettre ce correctif en place. Le code automodifiant est alors buggé.

La prefetch input queue

La prefetch input queue est une sorte de cousine du tampon de préchargement, qui a été utilisée sur les processeurs Intel 8 et 16 bits, ainsi que sur le 286 et le 386. L'idée est là encore de précharger des instructions en avance. Sauf que cette fois-ci, on ne charge pas plusieurs instructions à la fois. Au contraire, les instructions sont préchargées séquentiellement, un ou deux octet à la fois. En conséquence, le tampon de préchargement est remplacé par une mémoire FIFO appelée la Prefetch Input Queue, terme abrévié en PIQ. Les instructions sont accumulées une par une dans la PIQ, elles en sortent une par une au fur et à mesure pour alimenter le décodeur d'instruction.

Pendant que le processeur exécute une instruction, on précharge la suivante. Sans prefetch input queue, le processeur chargeait une instruction, la décodait et l'exécutait, puis chargeait la suivante, et ainsi de suite. Avec un tampon de préchargement, le processeur chargeait plusieurs instruction en une seule fois, puis les exécutait les unes après les autres. Avec la prefetch input queue, pendant qu'une instruction est en cours de décodage/exécution, le processeur précharge l'instruction suivante. Si une instruction prend vraiment beaucoup de temps pour s'exécuter, le processeur peut en profiter pour précharger l'instruction encore suivante, et ainsi de suite, jusqu'à une limite de 4/6 instructions (la limite dépend du processeur).

La prefetch input queue permet de précharger l'instruction suivante à condition qu'aucun autre accès mémoire n'ait lieu. Si l'instruction en cours d'exécution effectue des accès mémoire, ceux-ci sont prioritaires sur tout le reste, le préchargement de l'instruction suivante est alors mis en pause ou inhibé. Par contre, si la mémoire n'est pas utilisée par l'instruction en cours d'exécution, le processeur lit l'instruction suivante en RAM et la copie dans la prefetch input queue. En conséquence, il arrive que la prefetch input queue n'ait pas préchargé l'instruction suivante, alors que le décodeur d'instruction est prêt pour la décoder. Dans ce cas, le décodeur doit attendre que l'instruction soit chargée.

Les instructions préchargées dans la Prefetch input queue y attendent que le processeur les lise et les décode. Les instructions préchargées sont conservées dans leur ordre d'arrivée, afin qu'elles soient exécutées dans le bon ordre, ce qui fait que la Prefetch input queue est une mémoire de type FIFO. L'étape de décodage pioche l'instruction à décoder dans la Prefetch input queue, cette instruction étant par définition la plus ancienne, puis la retire de la file.

Le premier processeur commercial grand public à utiliser une prefetch input queue était le 8086. Il pouvait précharger à l'avance 6 octets d’instruction. L'Intel 8088 avait lui aussi une Prefetch input queue, mais qui ne permettait que de précharger 4 instructions. Le 386 avait une prefetch input queue de 16 octets. La taille idéale de la FIFO dépend de nombreux paramètres. On pourrait croire que plus elle peut contenir d'instructions, mieux c'est, mais ce n'est pas le cas, pour des raisons que nous allons expliquer dans quelques paragraphes.

Architecture du 8086, du 80186 et de ses variantes.

Vous remarquerez que j'ai exprimé la capacité de la prefetch input queue en octets et non en instructions. La raison est que sur les processeurs x86, les instructions sont de taille variable, avec une taille qui varie entre un octet et 6 octets. Cependant, le décodage des instructions se fait un octet à la fois : le décodeur lit un octet, puis éventuellement le suivant, et ainsi de suite jusqu'à atteindre la fin de l'instruction. En clair, le décodeur lit les instructions longues octet par octet dans la Prefetch input queue.

Les instructions varient entre 1 et 6 octets, mais tous ne sont pas utiles au décodeur d'instruction. Par exemple, le décodeur d'instruction n'a pas besoin d'analyser les constantes immédiates intégrées dans une instruction, ni les adresses mémoires en adressage absolu. Il n'a besoin que de deux octets : l'opcode et l'octet Mod/RM qui précise le mode d'adressage. Le second est facultatif. En clair, le décodeur a besoin de lire deux octets maximum depuis la prefetch input queue, avant de passer à l’instruction suivante. Les autres octets étaient envoyés ailleurs, typiquement dans le chemin de données.

Par exemple, prenons le cas d'une addition entre le registre AX et une constante immédiate. L'instruction fait trois octets : un opcode suivie par une constante immédiate codée sur deux octets. L'opcode était envoyé au décodeur, mais pas la constante immédiate. Elle était lue octet par octet et mémorisée dans un registre temporaire placé en entrée de l'ALU. Idem avec les adresses immédiates, qui étaient envoyées dans un registre d’interfaçage mémoire sans passer par le décodeur d'instruction. Pour cela, la prefetch input queue était connectée au bus interne du processeur ! Le décodeur dispose d'une micro-opération pour lire un octet depuis la prefetch input queue et le copier ailleurs dans le chemin de données. Par exemple, l'instruction d'addition entre le registre AX et une constante immédiate était composée de quatre micro-opérations : une qui lisait le premier octet de la constante immédiate, une seconde pour le second, une troisième micro-opération qui commande l'ALU et fait le calcul.

Le décodeur devait attendre que qu'un moins un octet soit disponible dans la Prefetch input queue, pour le lire. Il lisait alors cet octet et déterminait s'il contenait une instruction complète ou non. Si c'est une instruction complète, il la décodait et lexécutait, puis passait à l'instruction suivante. Sinon, il lit un second octet depuis la Prefetch input queue et relance le décodage. Là encore, le décodeur vérifie s'il a une instruction complète, et lit un troisième octet si besoin, puis rebelote avec un quatrième octet lu, etc.

Un circuit appelé le loader synchronisait le décodeur d'instruction et la Prefetch input queue. Il fournissait deux bits : un premier bit pour indiquer que le premier octet d'une instruction était disponible dans la Prefetch input queue, un second bit pour le second octet. Le loader recevait aussi des signaux de la part du décodeur d'instruction. Le signal Run Next Instruction entrainait la lecture d'une nouvelle instruction, d'un premier octet, qui était alors dépilé de la Prefetch input queue. Le décodeur d'instruction pouvait aussi envoyer un signal Next-to-last (NXT), un cycle avant que l'instruction en cours ne termine. Le loader réagissait en préchargeant l'octet suivant. En clair, ce signal permettait de précharger l'instruction suivante avec un cycle d'avance, si celle-ci n'était pas déjà dans la Prefetch input queue.

Le bus de données du 8086 faisait 16 bits, alors que celui du 8088 ne permettait que de lire un octet à la fois. Et cela avait un impact sur la prefetch input queue. La prefetch input queue du 8088 était composée de 4 registres de 8 bits, avec un port d'écriture de 8 bits pour précharger les instructions octet par octet, et un port de lecture de 8 bits pour alimenter le décodeur. En clair, tout faisait 8 bits. Le 8086, lui utilisait des registres de 16 bits et un port d'écriture de 16 bits. le port de lecture restait de 8 bits, grâce à un multiplexeur sélectionnait l'octet adéquat dans un registre 16 bits. Sa prefetch input queue préchargeait les instructions par paquets de 2 octets, non octet par octet, alors que le décodeur consommait les instructions octet par octet. Il s’agissait donc d'une sorte d'intermédiaire entre prefetch input queue à la 8088 et tampon de préchargement.

Le 386 était dans un cas à part. C'était un processeur 32 bits, sa prefetch input queue contenait 4 registres de 32 bits, un port d'écriture de 32 bits. Mais il ne lisait pas les instructions octet par cotet. A la place, son décodeur d'instruction avait une entrée de 32 bits. Cependant, il gérait des instructions de 8 et 16 bits. Il fallait alors dépiler des instructions de 8, 16 et 32 bits dans la prefetch input queue. De plus, les instructions préchargées n'étaient pas parfaitement alignées sur 32 bits : une instruction pouvait être à cheval sur deux registres 32 bits. Le processeur incorporait donc des circuits d'alignement, semblables à ceux utilisés pour gérer des instructions de longueur variable avec un registre d'instruction.

Les branchements posent des problèmes avec la prefetch input queue : à cause d'eux, on peut charger à l'avance des instructions qui sont zappées par un branchement et ne sont pas censées être exécutées. Si un branchement est chargé, toutes les instructions préchargées après sont potentiellement invalides. Si le branchement est non-pris, les instructions chargées sont valides, elles sont censées s’exécuter. Mais si le branchement est pris, elles ont été chargées à tort et ne doivent pas s’exécuter.

Pour éviter cela, la prefetch input queue est vidée quand le processeur détecte un branchement. Pour cela, le décodeur d'instruction dispose d'une micro-opération qui vide la Prefetch input queue, elle invalide les instructions préchargées. Cette détection ne peut se faire qu'une fois le branchement décodé, qu'une fois que l'on sait que l'instruction décodée est un branchement. En clair, le décodeur invalide la Prefetch input queue quand il détecte un branchement. Les interruptions posent le même genre de problèmes. Il faut impérativement vider la Prefetch input queue quand une interruption survient, avant de la traiter.

Il faut noter qu'une Prefetch input queue interagit assez mal avec le program counter. En effet, la Prefetch input queue précharge les instructions séquentiellement. Pour savoir où elle en est rendue, elle mémorise l'adresse de la prochaine instruction à charger dans un registre de préchargement dédié. Il serait possible d'utiliser un program counter en plus du registre de préchargement, mais ce n'est pas la solution qui a été utilisée. Les processeurs Intel anciens ont préféré n'utiliser qu'un seul registre de préchargement en remplacement du program counter. Après tout, le registre de préchargement n'est qu'un program counter ayant pris une avance de quelques cycles d'horloge, qui a été incrémenté en avance.

Et cela ne pose pas de problèmes, sauf avec certains branchements. Par exemple, certains branchements relatifs demandent de connaitre la véritable valeur du program counter, pas celle calculée en avance. Idem avec les instructions d'appel de fonction, qui demandent de sauvegarder l'adresse de retour exacte, donc le vrai program counter. De telles situations demandent de connaitre la valeur réelle du program counter, celle sans préchargement. Pour cela, le décodeur d'instruction dispose d'une instruction pour reconstituer le program counter, à savoir corriger le program coutner et éliminer l'effet du préchargement.

La micro-opération de correction se contente de soustraire le nombre d'octets préchargés au registre de préchargement. Le nombre d'octets préchargés est déduit à partir des deux pointeurs intégré à la FIFO, qui indiquent la position du premier et du dernier octet préchargé. Le bit qui indique si la FIFO est vide était aussi utilisé. Les deux pointeurs sont lus depuis la FIFO, et sont envoyés à un circuit qui détermine le nombre d'octets préchargés. Sur le 8086, ce circuit était implémenté non pas par un circuit combinatoire, mais par une mémoire ROM équivalente. La petite taille de la FIFO faisait que les pointeurs étaient très petits et la ROM l'était aussi.

Un autre défaut est que la Prefetch input queue se marie assez mal avec du code auto-modifiant. Un code auto-modifiant est un programme qui se modifie lui-même, en remplaçant certaines instructions par d'autres, en en retirant, en en ajoutant, lors de sa propre exécution. De tels programmes sont rares, mais la technique était utilisée dans quelques cas au tout début de l'informatique sur des ordinateurs rudimentaires. Ceux-ci avaient des modes d'adressages tellement limités que gérer des tableaux de taille variable demandait d'utiliser du code auto-modifiant pour écrire des boucles.

Le problème avec la Prefetch input queue survient quand des instructions sont modifiées immédiatement après avoir été préchargées. Les instructions dans la Prefetch input queue sont l'ancienne version, alors que la mémoire RAM contient les instructions modifiées. Gérer ce genre de cas est quelque peu complexe. Il faut en effet vider la Prefetch input queue si le cas arrive, ce qui demande d'identifier les écritures qui écrasent des instructions préchargées. C'est parfaitement possible, mais demande de transformer la Prefetch input queue en une mémoire hybride, à la fois mémoire associative et mémoire FIFO. Cela ne vaut que très rarement le coup, aussi les ingénieurs ne s’embêtent pas à mettre ce correctif en place, le code automodifiant est alors buggé.

Le décodeur d'instruction dispose aussi d'une micro-opération qui stoppe le préchargement des instructions dans la Prefetch input queue.

Pour ceux qui ont déjà lu un cours d'architecture des ordinateurs, la relation entre prefetch input queue et pipeline est quelque peu complexe. En apparence, la prefetch input queue permet une certaines forme de pipeline, en chargeant une instruction pendant que la précédente s'exécute. Les problématiques liées aux branchements ressemblent beaucoup à celles de la prédiction de branchement. Cependant, il est possible de dire qu'il s'agit plus d'une technique de préchargement que de pipeline. La différence entre les deux est assez subtile et les frontières sont assez floues, mais le fait est que l'instruction en cours d'exécution et le préchargement peuvent tout deux faire des accès mémoire et que l'instruction en cours a la priorité. Un vrai pipeline se débrouillerait avec une architecture Harvard, non avec un bus mémoire unique pour le chargement des instruction et la lecture/écriture des données.

Le Zero-overhead looping

Nous avions vu dans le chapitre sur les instructions machines, qu'il existe des instructions qui permettent de grandement faciliter l'implémentation des boucles. Il s'agit de l'instruction REPEAT, utilisée sur certains processeurs de traitement de signal. Elle répète l'instruction suivante, voire une série d'instructions, un certain nombre de fois. Le nombre de répétitions est mémorisé dans un registre décrémenté à chaque itération de la boucle. Elle permet donc d'implémenter une boucle FOR facilement, sans recourir à des branchements ou des conditions.

Une technique en lien avec cette instruction permet de grandement améliorer les performances et la consommation d'énergie. L'idée est de mémoriser la boucle, les instructions à répéter, dans une petite mémoire cache située entre l'unité de chargement et le séquenceur. Le cache en question s'appelle un tampon de boucle, ou encore un hardware loop buffer. Grâce à lui, il n'y a pas besoin de charger les instructions à chaque fois qu'on les exécute, on les charge une bonne fois pour toute : c'est plus rapide. Bien sûr, il ne fonctionne que pour de petites boucles, mais il en est de même avec l'instruction REPEAT.