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

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche

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. Les lectures et écritures sont émises dans l'ordre du programme. Au niveau du processeur, elles sont accumulées dans une FIFO, en attendant que la mémoire RAM ou le cache soient libres, celle-ci servant de station de réservation dédiée aux accès mémoires. Chaque entrée de la FIFO contient des bits qui indiquent si la donnée à lire ou écrire est disponible, ou si l'adresse d'accès est connue. L'unité d'accès mémoire vérifie à chaque cycle si un accès mémoire est en cours et si les adresses et la donnée à écrire sont disponibles. Une fois l'accès mémoire terminé, la mémoire ou le cache vont envoyer un signal pour indiquer que l'accès est fini. Dans le cas d'une lecture, la donnée lue est alors envoyée à l'étage d’enregistrement, de même que le registre de destination de la donnée lue.

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

Désambigüisation de la mémoire[modifier | modifier le wikicode]

Cette méthode est conservatrice et ne tient pas compte du fait que des accès mémoires indépendants peuvent être réordonnancés. Or, 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).

File d'écriture[modifier | modifier le wikicode]

Pour éviter tout problème avec la désambiguïsation de la mémoire, deux conditions doivent être remplies. Premièrement, on ne 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 suffit de mettre en attente les écritures dans une FIFO, une sorte de tampon de réordonnancement dédié aux écritures : la file d'écriture (store queue). Celle-ci mémorise, pour chaque écriture, l'adresse et la donnée de l'écriture, ainsi que des bits pour indiquer la disponibilité de celles-ci. Ensuite, une lecture doit lire la donnée provenant de l'écriture la plus récente qui a eu lieu à cette adresse mémoire. 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.

Lecture par contournement[modifier | modifier le wikicode]

S'il est impossible de déplacer une lecture avant une écriture si les deux instructions ont une dépendance (partagent la même adresse), cela 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.

Réacheminement écriture-vers-lecture[modifier | modifier le wikicode]

On peut aussi é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.

Calcul anticipé des adresses[modifier | modifier le wikicode]

Il est aussi 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.

Exécution spéculative des accès mémoires[modifier | modifier le wikicode]

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. Dans le cas des lectures et écritures en mémoire, 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.

Tampon de résolution d’adresse[modifier | modifier le wikicode]

Il existe une première méthode pour gérer cette spéculation. Pour la comprendre, il faut se souvenir que 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 : il faut bloquer le pipeline si aucune FIFO n'est disponible. 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.

File de lecture[modifier | modifier le wikicode]

Une autre technique consiste à ajouter des circuits à une file d’écriture, pour la rendre capable d’exécution spéculative. Pour pouvoir fonctionner correctement, notre processeur doit vérifier qu'il n'y a pas d'erreur, ce qui demande de conserver, 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 une seul gros circuit appelé la file de lecture-écriture (load-store queue).

Prédiction de dépendances mémoires[modifier | modifier le wikicode]

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édire 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.

Prédiction agressive[modifier | modifier le wikicode]

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 contrintuitivement, 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.

Mémorisation des instructions fautives[modifier | modifier le wikicode]

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 rencontre ceux-ci, 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 immédiatement. 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).

Ensembles d’écritures[modifier | modifier le wikicode]

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.

Autres techniques[modifier | modifier le wikicode]

D'autres technique de prédiction des dépendances mémoire ont étés 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. Quoiqu'il en soit, la recherche sur le sujet est assez riche, comme toujours quand il s'agit d'architecture des ordinateurs.

Prédiction d'adresse[modifier | modifier le wikicode]

Comme on peut s'en douter, connaitre l'adresse d'une lecture à l'avance permet de fortement limiter la casse, et permet à nos mécanismes de Memory Disambiguation 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 ne se fait pas tout seul. Il faut que les opérandes de ce calcul soient disponibles. Et ce n'est pas garantit. Il arrive que certaines 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 faire pire. On peut spéculer sur l'adresse d'une lecture ou écriture ! Tenter de prédire à l'avance cette adresse peut améliorer les performances assez facilement. Reste à savoir comment faire pour prédire cette adresse. Et encore une fois, on peut tenter de prédire celle-ci en utilisant des régularités de nos accès mémoires.

Prédiction de la donnée lue[modifier | modifier le wikicode]

Pour implémenter cette technique, on peut remarquer que ce problème est similaire à celui de la prédiction de branchement : 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. Premièrement, il suffit d'avoir un équivalent du cache de destination de branchement : il suffit de stocker un historique pour chaque instruction dans un cache. Ce cache stocke l'adresse lue pour chaque instruction mémoire récemment utilisée. 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 pour prédire l'adresse d'une lecture/écriture : supposer que cette lecture/écriture va accéder à des adresses séparées par des intervalles réguliers. Ce genre d'accès doit vous rappeler le chapitre sur le préchargement. 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 le Stride pour chaque adresse, et d'ajouter quelques circuits pour gérer le stride (ceux-ci sont inspirés de ceux vus dans le chapitre sur le préchargement). Ce Stride sera la distance entre une adresse, et celle accédée précédemment par notre instruction. Ce Stride est déterminé par le circuit chargé de la prédiction. Celui-ci garde en mémoire la dernière adresse accédée par notre instruction, et il fait la différence avec l'adresse lue. Il en déduit le Stride, et stocke celui-ci dans notre mémoire cache. A chaque accès, ce Stride est ajouté à l'adresse contenue dans notre cache. 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 se permettent de faire un tout petit peu mieux. Ceux-ci 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 aucun Stride. 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.

Validation de la prédiction[modifier | modifier le wikicode]

Bien sûr, il est rare qu'une instruction de lecture ou d'écriture accède à la même case mémoire plusieurs fois de suite. On doit donc trouver un moyen de savoir si notre 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 venir de machins qui arrivent lorsqu'on compile du code qui provient de plusieurs librairies, bref.

La seconde technique suppose que l'instruction peut, ou non accéder à la même adresse. Elle tentera alors 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.

Conclusion[modifier | modifier le wikicode]

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. Quoiqu'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ées 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.

Prédiction de la donnée lue[modifier | modifier le wikicode]

On l'a vu précédemment, l’exécution spéculative est assez efficace. Du moins, elle l'est dans des cas où le résultat de la prédiction est simple. Par exemple, la prédiction de branchement est de l’exécution spéculative : on suppose que le branchement sera pris ou non-pris, et on exécute les instructions qui correspondent à ce qu'on a supposé. Les techniques de Memory Disambiguation qui cherchent à prédire si deux instructions accèdent à la même adresse, sont aussi de l’exécution spéculative. D'ordinaire, le processeur parie sur des choses simples, pour lesquelles il a peu de chances de se tromper. Un branchement est pris ou non-pris, deux adresses sont dépendantes ou ne le sont pas, etc. Dans les cas précédemment cités, on n'a que deux possibilités : pris/non-pris, dépendantes/indépendantes. De plus, on peut optimiser ces techniques de façon à utiliser certaines régularités dans nos programmes, afin de prendre de meilleures décisions, et obtenir au final de bons résultats. Mais cette fois-ci, on change totalement de plan. Je vais vous parler des techniques de Value Prediction (prédiction de valeur), qui consistent à prédire quelle est la valeur présente dans un registre ou une adresse mémoire à laquelle on veut accéder. Oui, vous avez bien lus : 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é de façon spéculative. Si le pari est correct, alors on continue l’exécution. Sinon, on est obligé de faire comme lorsque l'on se trompe lors d'une prédiction de branchement ou une prédiction de dépendances d'adresses mémoires : on vide le pipeline, et on recommence avec la bonne valeur.

Précisions[modifier | modifier le wikicode]

Au premier abord, cette technique semble franchement mal parti. 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, et dans la majorité des cas, le processeur refuse de parier. Il ne spécule pas, et n’exécute pas d'instructions en pariant sur les données qu'elle vont manipuler. Mais dans certains cas bien précis, on peut spéculer sur le résultat fourni par une instruction. Ces cas bien précis concernent souvent le résultat fourni par une instruction de lecture en mémoire. Par exemple, on peut parier qu'une instruction de lecture qui s’exécute plusieurs fois de suite à la même adresse peut renvoyer la même valeur à chaque fois : c'est parfaitement possible si il n'y a eu aucune écriture à cette adresse entre temps. Mais ce n'est pas toujours le cas : on est donc obligé de parier. Cette technique qui consiste à parier sur le résultat d'une lecture s'appelle la Load Value Prediction. Nous allons nous intéresser à cette technique dans la suite de ce tutoriel, et nous ne parlerons pas des technique qui essayent de prédire le résultats d'autres instructions (arithmétiques, etc).

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 toute ! Mais cela n'est possible que dans un monde parfait. Dans la réalité, on fait face à quelques limites, qui seront détaillées dans la liste suivante.

  • Cela notamment 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 instructions 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. A 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 Load Value Prediction fonctionnent bien.

Implémentation[modifier | modifier le wikicode]

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 Load Value Prediction Table. Cette unité consiste simplement en une mémoire cache qui associe le Program Counter de l'instruction à des compteurs à saturation. A 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 caches a pour tag, l'adresse à laquelle lire. Cette mémoire cache s'appelle la Load Value Table. 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 Load Value Prediction Table, 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 Load Value Table, 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 Load Value Prediction Table 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 la Constant Verification Unit.

Conclusion[modifier | modifier le wikicode]

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. Quoiqu'il en soit, l'efficacité de cette technique a déjà été étudiées grâce à des simulateurs. Suivant les études ou les programmes, on trouve des résultats qui varient pas mal. Dans certains cas, la performances baisse un peu, et dans d'autres, on peut avoir des gains de plus de 60% ! 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.