Fonctionnement d'un ordinateur/Désambigüisation de la mémoire

L’exécution dans le désordre modifie l'ordre des instructions pour gagner en efficacité, et le renommage de registres améliore la situation en supprimant certaines dépendances. Mais cela n'est valable que pour les instructions travaillant sur des registres, pas sur celles qui accèdent à la mémoire. Jusqu'à présent, nous n'avons vu que des processeurs qui n’utilisent pas d'exécution dans le désordre pour les accès mémoire. Ils exécutent les accès mémoire dans l'ordre du programme.

L'unité d'accès mémoire d'un processeur in order peut accepter plusieurs accès mémoires simultanés. Mais attention, cela ne veut pas forcément dire que plusieurs accès mémoire ont réellement lieu en même temps, la mémoire RAM ne le permet peut-être pas. Sur la plupart des systèmes, on ne peut faire qu'une lecture ou une écriture à la fois, les mémoires multiports étant une exception. En réalité, les accès mémoire ont lieu un par un, dans l'ordre du programme. C'est juste que l'unité d'accès mémoire ne bloque pas le processeur si on lui demande d'effectuer un accès mémoire en plus.

Pour cela, les lectures et écritures sont accumulées dans une FIFO qui met en attente les accès mémoire. Le fait que la mise en attente soit faite par une FIFO garantit que les accès mémoire s’exécutent dans l'ordre du programme. Chaque entrée de la FIFO contient des bits qui indiquent si l'adresse d'accès est connue, et aussi si la donnée à écrire est disponible pour une écriture. L'unité d'accès mémoire vérifie à chaque cycle si un accès mémoire est en cours ou non. Si la mémoire est libre, l'unité d'accès mémoire lit l'accès mémoire le plus ancien dans la FIFO et l’exécute. Une fois l'accès mémoire terminé, la mémoire ou le cache envoient un signal pour indiquer que l'accès est fini. Dans le cas d'une lecture, la donnée lue est alors envoyée sur le bus interne du processeur, ou alors mise en attente dans une mémoire FIFO là encore.

Unité de gestion des accès mémoires dans l’ordre.

La désambiguïsation de la mémoire

La méthode précédente est conservatrice et ne tient pas compte du fait que des accès mémoires indépendants peuvent être réordonnancés. Diverses techniques réordonnancent les accès mémoires, exactement comme l’exécution dans le désordre le fait pour les autres instructions. Ces techniques sont ce qu'on appelle des techniques de désambiguïsation de la mémoire (memory disambiguation). Avec ces techniques, la mémoire FIFO plus haut disparait ou est fortement altérée.

La file d'écriture

Pour éviter tout problème avec la désambiguïsation de la mémoire, deux conditions doivent être remplies. Premièrement, on doit pas écrire dans la mémoire tant que l'on ne sait pas si l'écriture a bien lieu, pour éviter tout problème en cas de mauvaise prédiction de branchement ou d'exception. Pour cela, il faut mettre en attente les écritures dans une FIFO qui sert de tampon de réordonnancement dédié aux écritures : la file d'écriture (store queue). Celle-ci mémorise, pour chaque écriture, l'adresse à laquelle écrire, la donnée à écrire, ainsi que des bits pour indiquer si la donnée et l'adresse sont disponible ou pas encore calculées.

Une lecture doit lire la donnée provenant de l'écriture la plus récente qui a eu lieu à l'adresse lue. Ce qui peut se régler avec plusieurs solutions : lecture depuis la file d'écriture, blocage des lectures tant qu'une écriture est en attente dans la file d'écriture, ou autre.

La lecture par contournement

Il est impossible de déplacer une lecture avant une écriture si les deux instructions ont une dépendance (partagent la même adresse), mais c'est parfaitement possible dans le cas contraire. La technique de la lecture par contournement (load bypassing) conserve l'ordre entre écritures et entre lectures, mais pas l'ordre entre écritures et lectures. Dit autrement, si une lecture n'a aucune dépendance avec les écritures mises en attente dans la file d'écriture, on la démarre immédiatement. Elle doit être mise en attente dans le cas contraire. Pour cela, on rajoute un ensemble de stations de réservation dédiées aux lectures : la file de lecture (load queue).

Exécution dans le désordre des lectures.

Le réacheminement écriture-vers-lecture

On peut éviter de bloquer la lecture en lisant la donnée depuis la file d'écriture, sans attendre que l'écriture soit terminée. Cette optimisation s'appelle le réacheminement écriture-vers-lecture (store-to-load forwarding). Solution efficace, mais qui demande d'annuler les effets de la lecture si l'écriture n'a pas lieu, en cas de mauvaise prédiction de branchement.

Pour implémenter cette technique, on construit souvent la file d'écriture sous la forme d'un cache, chaque ligne mémorisant une donnée, et ayant pour tag l'adresse à lire ou écrire. Toute lecture va déclencher automatiquement un accès à ce cache. S'il y a succès de cache, c'est que la lecture a une dépendance avec une écriture de la file d'attente : on renvoie la ligne de cache associée à cette écriture. En cas de défaut de cache, la lecture est effectuée en mémoire RAM ou dans le cache.

Mais il faut gérer le cas où plusieurs écritures à la même adresse sont mises en attente dans la file d'écriture. Dans ce cas, la file d'écriture renvoie la dernière donnée écrite, celle fournie par l'écriture la plus récente : cela permet de renvoyer la donnée la plus à jour. En exécutant les lectures dans l'ordre du programme, cela ne pose aucun problème.

Le calcul anticipé des adresses

Il est possible de séparer les accès à la mémoire en deux parties, en deux micro-instructions : une pour le calcul d'adresse et l'autre pour les accès mémoire. Cela permet de vérifier à l'avance si l'adresse calculée a des dépendances avec celles des autres instructions. La détection des dépendances est ainsi anticipée de quelques cycles, permettant un accès anticipé sûr des accès mémoire. On parle de calcul anticipé des dépendances.

Cette technique peut s'implémenter facilement avec la file d’écriture qu'on a vue au-dessus, les instructions pouvant être exécutées directement l'étant, alors que les autres sont mises en attente dans la file d'écriture. Mais on peut aussi utiliser des matrices de dépendances, qui permettent de repérer de façon optimale toutes les dépendances entre accès mémoires, sans en laisser passer une seule. Ces matrices forment une espèce de tableau carré, organisé en lignes et en colonnes. Chaque ligne et chaque colonne se voit attribuer une instruction. À l'intersection d'une ligne et d'une colonne, on trouve un bit qui indique si l'instruction de la ligne et celle de la colonne ont une dépendance.

Commençons par voir la version la plus simple de ces matrices de dépendances. Avec celles-ci, on vérifie juste si toutes les adresses des écritures précédentes sont connues ou non. Si elles ne sont pas toutes connues, les lectures vont attendre avant de pouvoir s’exécuter. Dans le cas contraire, on peut alors démarrer nos accès mémoires. La vérification des dépendances (est-ce que deux accès mémoires se font à la même adresse) se fait alors avec une file d’écriture ou dans des circuits spécialisés. Lorsque le processeur démarre une écriture dont il ne connait pas l'adresse de la donnée à écrire, il va d'abord insérer cette écriture dans ce tableau carré dans une ligne. Cette ligne sera celle d'indice i. Puis, il va mettre tous les bits de la colonne de même indice (i) à 1. Cela permet de dire que notre écriture peut potentiellement avoir une dépendance avec chaque instruction en attente. Vu qu'on ne connait pas son adresse, on ne peut pas savoir. Lorsque cette adresse est alors connue, les bits de la colonne attribuée à l'écriture sont remis à zéro. Quand tous les bits d'une ligne sont à zéro, la lecture ou écriture correspondante est envoyée vers les circuits chargés de gérer les lectures ou écritures. Ceux-ci se chargeront alors de vérifier les adresses des lectures et écritures, grâce à une file d’écriture et au réacheminement écriture-vers-lecture associé.

Cette technique peut être améliorée, et gérer la détection des dépendances elle-même, au lieu de les déléguer à une file d’écriture. Dans ce cas, on doit commencer par ajouter l'adresse à laquelle notre instruction va lire ou écrire pour chaque ligne. Puis, à chaque fois qu'une adresse est ajoutée dans une ligne, il suffit de la comparer avec les adresses des autres lignes et mettre à jour les bits de notre matrice en conséquence. Cette technique n'est pas très efficace : il est en effet peu probable que toutes les adresses des écritures précédant une lecture soient connues lorsqu'on veut lire notre donnée. Autant dire que cette technique n'est pas utilisée seule, et elle est augmentée d'autres techniques plus ou moins complémentaires.

L'exécution spéculative des accès mémoires

Pour diminuer l'effet des dépendances mémoires, de nombreux processeurs utilisent l’exécution spéculative : ils exécutent des instructions de façon anticipée, en supposant certaines choses, et en remettant le processeur à zéro si la supposition se révèle être fausse. La prédiction de branchement est un cas d’exécution spéculative assez connu, mais on peut faire la même chose avec les accès mémoire. Dans ce cas, le processeur suppose qu'il n'y a aucune dépendance mémoire et démarre les accès mémoires en conséquence. Le processeur vérifie s'il a fait une erreur de prédiction, en vérifiant les adresses à écrire ou lire. En cas d'erreur, il élimine les modifications, comme dans le cas d'une mauvaise prédiction de branchement. Reste que cela peut se faire de différentes manières.

Le tampon de résolution d’adresse

Voyons d'abord la première méthode. En théorie, les accès mémoires à une même adresse doivent s'effectuer dans l'ordre du programme, mais pas les accès à des adresses différentes. Ainsi, on peut gérer les dépendances en utilisant une FIFO par adresse. Le problème est que le nombre de FIFO peut ne pas suffire, les adresses étant vraiment très nombreuses. Si aucune FIFO n'est disponible, il faut bloquer le pipeline. Cette méthode est celle qui est utilisée par le tampon de résolution d’adresse (address resolution buffer ou ARB). Cette technique, utilise une seule mémoire pour mémoriser toutes les FIFO : la mémoire est divisée en banques, chaque banque correspondant à une FIFO, et chaque mot mémoire correspondant à une lecture ou une écriture mise en attente. Mais ces détails d'implémentation ne sont pas vraiment utiles.

La file de lecture

Une autre technique consiste à ajouter des circuits à la file d’écriture, pour la rendre capable d’exécution spéculative. Pour vérifier qu'il n'y a pas d'erreur de spéculation, le processeur conserve, pour chaque lecture spéculative l'adresse de la lecture effectuée, ainsi que la donnée lue (et éventuellement le program counter). Il faut conserver ces informations jusqu'à ce que toutes les instructions précédant la lecture dans l'ordre du programme soient terminées. Pour cela, on modifie la file de lecture, qui devient un cache : les tags de ce cache mémorisent les adresses, et le reste de chaque ligne de cache s'occupe de la donnée lue.

Pour chaque écriture, il faut vérifier si une lecture qui a accédé à la même adresse se trouve dans la file de lecture. Rien de bien compliqué : on compare l'adresse de l'écriture avec les tags de la file de lecture, qui contiennent l'adresse à laquelle notre lecture a accédé. S'il y a correspondance (un succès de cache), c'est qu'il y a eu erreur : on doit supprimer du pipeline toutes les instructions exécutées depuis la lecture fautive. Petit détail : sur certains processeurs, la file de lecture et la file d'écriture sont fusionnées dans un seul gros circuit appelé la file de lecture-écriture (load-store queue).

La prédiction de dépendances mémoires

Certains processeurs essayent de prédire si deux accès mémoires sont dépendants : ils incorporent une unité qui va fonctionner comme une unité de prédiction de branchement, à la différence qu'elle prédit les dépendances mémoires. Si cette unité prédit que deux accès mémoires sont indépendants, le processeur les exécute dans le désordre, et les exécute dans l'ordre du programme dans le cas contraire. Il faut prendre en compte les erreurs de prédiction, ce qui est fait comme pour les mauvaises prédictions de branchement : on vide le pipeline.

Beaucoup de techniques de prédiction des dépendances mémoire ont été inventées et en faire une revue exhaustive serait long et fastidieux. On pourrait citer les ensembles colorés (color sets), et bien d'autres techniques. Mais nous n'allons parler que des techniques les plus élémentaires. Quoi qu’il en soit, la recherche sur le sujet est assez riche, comme toujours quand il s'agit d'architecture des ordinateurs.

La prédiction agressive

La première méthode consiste à supposer que les lectures n'ont pas de dépendance : une lecture démarre avant même que les écritures qui la précédent dans l'ordre du programme soient connues. Et aussi bizarre que cela puisse paraître, cela donne de bons résultats. Il faut dire que les situations où une lecture suit de près une écriture sont rares : même pas 2 à 3 % des lectures.

La prédiction avec mémorisation des instructions fautives

On peut améliorer cette technique en mémorisant les instructions qui ont causé une mauvaise prédiction de dépendance mémoire. La prochaine fois qu'on exécute ces instructions, on sait qu'il y a de grandes chances qu'il se produise une erreur de prédiction, ce qui pousse à ne pas les exécuter de manière spéculative. On peut pour cela réutiliser les techniques de prédiction de branchement, tels des compteurs à saturations, mis à jour en cas d'erreurs de prédiction de dépendances mémoire. Dans tous les cas, on trouve un cache, équivalent au branch target buffer, qui mémorise les instructions fautives (leur Program Counter), avec d'autres informations comme les adresses des instructions dépendantes. La première classe de techniques du genre consiste à mémoriser les lectures qui ont causé une violation de dépendance, tandis que l'autre ne mémorise que les écritures. Cette dernière est l'approche utilisée par le cache de barrières d’écriture (store barrier cache).

La prédiction par ensembles d’écritures

Enfin, nous allons conclure avec une dernière technique : celle des ensembles d’écritures (store sets). Cette technique est capable de gérer le cas où une lecture dépend de plusieurs écritures : le processeur mémorise l'ensemble des écritures avec lesquelles la lecture a déjà eu une dépendance. Cet ensemble d'écritures associées à une lecture est appelé tout simplement un ensemble d’écritures, et reçoit un identifiant (un nombre) par le processeur. Cette technique demande d'utiliser deux tables :

• une qui assigne un identifiant d’ensemble d’écritures à l'instruction en cours ;
• une autre qui mémorise les ensembles d’écritures sous la forme d'une liste chainée : le début de la liste correspond à l'écriture la plus ancienne de l’ensemble. Cela permet d'obtenir l'écriture la plus ancienne dans cet ensemble d’écritures directement.

Quand le processeur détecte une violation de dépendance entre une lecture et une écriture, elle ajoute l'écriture dans l’ensemble d’écritures adéquat. Le déroulement d'une lecture demande d'accéder à la première table pour récupérer l'identifiant de l’ensemble d’écritures, et l'utiliser pour adresser la seconde table. S'il y a dépendance, cet accès renvoie l'écriture fautive en cas de dépendance. Quand une écriture est envoyée à l'unité mémoire, celle-ci va accéder à la table de correspondances de la même manière qu'une lecture, et va récupérer l'identifiant de l’ensemble d’écritures auquel elle appartient, identifiant qui est utilisé pour vérifier s'il y a une écriture en cours d’exécution. Si c'est le cas, cela signifie que l'écriture en cours d’exécution doit s’exécuter avant l'écriture qui a consulté la table : cette dernière est mise en attente.

La prédiction d'adresse

Connaitre l'adresse d'une lecture à l'avance permet de fortement limiter la casse, et permet aux mécanismes de désambiguïsation mémoire de fonctionner plus efficacement. Si jamais cette adresse est connue plus tôt, on détecte les dépendances plus rapidement et on peut agir en conséquence. Reste que le calcul de cette adresse demande que les opérandes de ce calcul soient disponibles, et ce n'est pas garantit. Il arrive que des instructions doivent attendre que l'adresse à lire/écrire soit calculée. Et pendant ce temps, le processeur peut faire des ravages en spéculant trop. Pour rendre ce calcul d'adresse plus rapide, on peut améliorer les circuits chargés du calcul de ces adresses, mais on peut aussi spéculer sur l'adresse d'une lecture ou écriture ! Reste à savoir comment faire pour prédire cette adresse, en utilisant des régularités de nos accès mémoires.

A ce stade, je dois préciser que cette technique n'est pas encore tout à fait mature, et qu’aucun processeur ne l'implémente encore. En tout cas, la recherche sur le sujet est encore en cours, et même si aucun processeur n'a encore implémenté de technique de ce genre, cela ne saurait tarder. Quoi qu’il en soit, ces unités de prédiction sont tout de même utilisées dans d'autres circonstances. Des variantes de ces unités de prédiction d'adresse sont utilisées dans les Prefetchers, ceux utilisés pour précharger des données depuis le cache de donnée. Et leur efficacité est assez bonne, voire excellente dans certains cas. Mais pour le moment, ces unités de prédiction d'adresse ne sont pas encore utilisées pour prédire les adresses à lire depuis le cache vers les registres - ce qui est le sujet de cette sous-partie.

La prédiction de la donnée lue

Prédire l'adresse d'une lecture est similaire à prédire l'adresse de destination d'un branchement. Les techniques vues dans le chapitre sur la prédiction de branchement peuvent ainsi être réutilisées telles qu'elles pour faire la prédiction d'adresse de lecture. Ces techniques demandent d'utiliser un équivalent du branch target buffer, qui stocke l'adresse lue pour chaque instruction mémoire récente. Pour faire l'association instruction <-> adresse lue/écrite, il suffit de mettre l'adresse de notre instruction (le program Counter) dans le Tag.

Autre méthode : supposer que cette lecture/écriture va accéder à des adresses séparées par des intervalles réguliers, des accès en enjambées. Implémenter cette technique est facile et relativement similaire à ce qu'on a vu dans le chapitre sur le préchargement. Il suffit de rajouter dans le cache de quoi stocker l’enjambée pour chaque adresse, et d'ajouter quelques circuits pour gérer l'enjambée. L'enjambée est déterminée par le circuit chargé de la prédiction, qui mémorise la dernière adresse lue par l'instruction et fait la différence avec l'adresse lue. À chaque accès, l'enjambée est ajoutée à l'adresse contenue dans le cache et le résultat sert d'adresse prédite. L'ancienne adresse dans le cache est remplacée par la nouvelle une fois qu'on dispose de l'adresse valide.

Certains prédicteurs d'adresse font mieux et sont capables de repérer des accès mémoires qui se répètent de façon régulière et cyclique, même s'ils n'ont aucune enjambée. Ce genre d'accès se trouve assez souvent lorsque l'on manipule des listes chainées ou des structures de données assez irrégulières comme des arbres, des graphes, etc. Pour gérer ces accès, on stocke plusieurs adresses par instruction dans le cache. Plus précisément, on stocke les dernières adresses accédées dans le cache. Le tout est complété par une unité de prédiction qui se charge de déterminer laquelle de ces adresses est la bonne. Le tout est ensuite complété par une unité chargée de mettre à jour la mémoire cache qui contient les adresses de chaque instruction. L'implémentation de ces unités peut fortement varier suivant les processeurs, aussi je ne rentrerais pas dans les détails.

La validation de la prédiction

Il est rare qu'une instruction de lecture ou d'écriture accède à la même case mémoire plusieurs fois de suite. Or, les prédicteurs utilisent diverses techniques pour savoir si une instruction accède plusieurs fois à la même adresse ou pas. Commençons par aborder la première technique. Celle-ci suppose que toute instruction de lecture accède toujours à la même adresse. On pourrait se demander pourquoi une lecture ou écriture irait accéder plusieurs fois à la même adresse. Pour répondre à cela, il faut savoir que nos programmes sont parfois obligés d’accéder à la même adresse à cause du compilateur. Il arrive que les compilateurs n'arrivent pas à gérer efficacement les accès mémoires. Diverses raisons existent pour cela : certaines dépendances entre instructions forcent certaines données à être relues depuis la mémoire. Cela arrive notamment lorsque l'on utilise des pointeurs ou des références : divers phénomènes complexes d'aliasing des pointeurs peuvent générer des relectures intempestives de données en mémoire. Cela peut aussi arriver lorsqu'on compile du code qui provient de plusieurs librairies, bref.

La seconde technique tente de prédire si l'adresse dans le cache est valide ou non. Pour cela, on ajoute des compteurs à saturation pour chaque instruction (chaque ligne de cache). Ces compteurs sont incrémentés à chaque fois qu'une instruction réutilise la même adresse, et décrémenté en cas de changements. Vu que les instructions qui accèdent toujours à la même adresse sont rares, il est préférable d’initialiser ces compteurs de façon à ce qu'ils disent que toute nouvelle instruction change d'adresse.

La prédiction de la donnée lue

L’exécution spéculative est assez efficace dans les cas où le résultat de la prédiction est simple. C'est le cas pour la prédiction de branchement (un branchement est pris ou non-pris), pour la prédiction de dépendance mémoire (deux adresses sont dépendantes ou ne le sont pas), etc. De plus, on peut utiliser certaines régularités des programmes pour obtenir au final de bons résultats. Mais les techniques que nous allons aborder ne sont pas dans ce cas. Je vais vous parler des techniques de prédiction de valeur (Value Prediction), qui consistent à prédire quelle est la valeur présente dans un registre ou une adresse mémoire. Oui, vous avez bien lu : le processeur est capable de parier sur la valeur qui sera chargée depuis la mémoire et tenter de décider si cette valeur vaut 0, 1, 1024, etc. Une fois son pari fait, il exécute les instructions du programme avec la valeur qu'il a pariée de façon spéculative. Si le pari est correct, alors on continue l’exécution. Sinon, on est obligé de vider le pipeline et de recommencer avec la bonne valeur.

Comme pour la prédiction d'adresse mémoire, cette technique n'est pas encore mature et aucun processeur ne l'implémente encore. La recherche sur le sujet est encore en cours et l'efficacité de cette technique a été étudiée grâce à des simulateurs. Suivant les études ou les programmes, on trouve des résultats qui varient pas mal. Dans certains cas, la performance baisse un peu, et dans d'autres, on peut avoir des gains de plus de 10% ! Mais dans des cas normaux, on trouve des gains de 4-5% environ. Ce qui est tout de même pas mal à l'heure actuelle.

La prédiction de valeur lue

Au premier abord, cette technique semble franchement mal partie. Tenter de prédire quelle sera la valeur stockée dans un registre de 32 bits parmi les 4 294 967 296 valeurs que ce registre peut stocker semble être une aberration. Les chances de se tromper sont tellement énormes ! Mais le fait est que, dans certains cas, il est possible de spéculer correctement. Bon, évidemment, ces cas sont plutôt rares, ce qui fait que le processeur ne doit pas faire d’exécution spéculative sur les données chargées dans la majorité des cas. Comme exemple, on peut parier qu'une instruction de lecture qui s’exécute plusieurs fois de suite à la même adresse renvoie la même valeur à chaque fois. C'est parfaitement possible s’il n'y a eu aucune écriture à cette adresse entre-temps, mais ce n'est pas toujours le cas. La technique qui consiste à parier sur le résultat d'une lecture s'appelle la prédiction de valeur lue.

On peut se demander quelles sont les raisons qui font qu'une instruction de lecture renvoie la même valeur à chaque fois. Après tout, autant lire une seule fois la donnée et la garder dans un registre une bonne fois pour toutes ! Mais dans la réalité, on fait face à quelques limites, qui seront détaillées dans la liste suivante.

• Cela peut arriver quand on n'a pas assez de registres pour stocker toutes nos données : certaines données doivent temporairement être déplacées en mémoire pour libérer des registres, puis sont remises dans les registres une fois qu'on a des registres de libres. On peut parfaitement spéculer que lorsqu'une instruction en lecture s’exécute après une instruction d'écriture à la même adresse, la lecture renverra le résultat qui a été écrit juste avant.
• Cela arrive aussi quand on stocke des constantes en mémoire. Par exemple, sur les processeurs x86, les constantes flottantes ne peuvent pas être intégrées dans nos instructions via le mode d'adressage immédiat. À la place, on les stocke en mémoire et on les charge dans les registres à chaque fois qu'on en a besoin.
• Il arrive aussi que les compilateurs n'arrivent pas à gérer efficacement les accès mémoires. Diverses raisons existent pour cela : certaines dépendances entre instructions forcent certaines données à être relues depuis la mémoire. Cela arrive notamment lorsque l'on utilise des pointeurs ou des références : divers phénomènes complexes d'aliasing des pointeurs peuvent générer des relectures intempestives de données en mémoire. Cela peut aussi venir de machins qui arrivent lorsqu'on compile du code qui provient de plusieurs librairies, bref.
• Enfin, certains branchements indirects doivent relire l'adresse à laquelle il doive brancher depuis la mémoire régulièrement. Quand vous utilisez des switch ou des fonctions virtuelles dans votre langage objet préféré, votre compilateur va relire l'adresse à laquelle brancher (l'adresse de la fonction ou du case) depuis la mémoire à chaque accès. Il faut dire que cette adresse peut changer a tout moment, et qu'on est donc obligé d'aller la relire à chaque fois. Mais vu que cette adresse change peu, et qu'elle est souvent la même, les techniques de prédiction de valeur lue fonctionnent bien.

Implémentation

Pour implémenter cette technique, il suffit d'intégrer dans notre processeur une mémoire cache un peu spéciale. De la même façon qu'un utilise un Branch Target Buffer lorsqu'on parie sur les branchements, on doit utilise un cache équivalent pour la spéculation sur les lectures. Pour commencer, la première chose à faire, c'est de disposer d'un moyen pour prédire correctement si une lecture va renvoyer le même résultat que la dernière fois. Pour cela, notre processeur incorpore une unité de prédiction des valeurs lues, aussi appelée Table de prédiction de valeur lue. Cette unité consiste simplement en une mémoire cache qui associe le Program Counter de l'instruction à des compteurs à saturation. À chaque cycle, le contenu du Program Counter sera comparé au contenu de la mémoire cache : si l'adresse contenue dans le Program Counter correspond à une adresse stockée dans le cache, cela signifie qu'une instruction de lecture déjà exécutée l'est une fois de plus. Il suffit alors de regarder le résultat du ou des compteurs à saturation pour voir si on peut prédire notre instruction de lecture ou pas.

Il nous faut aussi se souvenir de quelle était la valeur lue lors des dernières exécutions de notre lecture. Pour cela, rien de plus facile : on utilise une autre mémoire cache, qui contient cette valeur. Cette mémoire cache a pour tag, l'adresse à laquelle lire. Cette mémoire cache s'appelle la Table de valeur lue. Elle peut être améliorée pour conserver nos pas la dernière valeur lue, mais les n dernières valeurs lues depuis la mémoire. Cela permet de mieux s'adapter au contexte, mais est d'une utilité assez limitée en pratique. Et cela nécessite des changements dans la Table de prédiction de valeur lue, qui doit prédire quelle est la bonne valeur à utiliser.

Et enfin, il faut bien vérifier que notre prédiction était correcte. Pour cela, rien de plus simple : il suffit de comparer la donnée fournie par la Table de valeur lue, et celle fournie par la lecture. Si elles sont identiques, la prédiction était correcte. Sinon, la prédiction était fausse, et on doit vider le pipeline. Dans tous les cas, on prévient la Table de prédiction de valeur lue pour qu'elle mette à jour ses estimations et les compteurs à saturation. Cette vérification est effectuée par une unité spécialisée nommée l'unité de vérification de constante.