Fonctionnement d'un ordinateur/Les unités mémoires à exécution dans le désordre

Le chapitre précédent abordait les unités mémoires bloquantes, à savoir celles qui étaient bloquées lors d'un accès mémoire. Pendant qu'elles traitent un accès mémoire, elles ne peuvent pas accepter de nouvel accès mémoire. Mais il existe des unités mémoires non-bloquantes qui en sont capables. Mais attention, elles n'effectuent pas plusieurs accès simultanés au cache de données. A la place, elles mettent en attente les accès mémoire tant que le cache est occupé. Elles font les accès mémoire un par un, mais mettent en attente les accès mémoire. Pour cela, elles incorporent une file d'instruction ou une fenêtre d'instruction spécialisée dans les accès mémoire.

L’exécution dans le désordre proprement dite modifie l'ordre des instructions pour gagner en efficacité, mais cela n'est valable que pour les instructions travaillant sur des registres. Mais les unités mémoires non-bloquantes permettent une exécution dans le désordre des accès mémoire, si elles sont conçues pour. Les processeurs OOO assez anciens exécutaient les accès mémoire dans l'ordre, l'exécution dans le désordre est désactivée pour les accès mémoire. Les processeurs récents, quant à eux, utilisent l'exécution dans le désordre des accès mémoire, mais elle est implémentée différemment de l'exécution dans le désordre normale.

C'est l'unité d'accès mémoire qui se charge de changer l'ordre des accès mémoire toute seule dans son coin, sans l'aide d'une fenêtre d'instruction. Il faut vraiment insister sur le fait que l'exécution dans le désordre proprement dite ne se préoccupe pas des micro-opérations mémoire. Pour faire la distinction, on parle de désambiguïsation mémoire pour parler de l'exécution dans le désordre des accès mémoire.

La raison est que l'exécution dans le désordre gère les dépendances de registres (deux instructions manipulent le même registre), alors que l'unité mémoire non-bloquante gère les dépendances d'adresse (deux instructions manipulent la même adresse). La différence registre-adresse fait que la gestion des dépendances est totalement différente. Les dépendances WAW et WAR ne peuvent pas être éliminées avec renommage de registre, comparer des adresses demande l'usage de mémoires associatives complexes et non de simples scoreboard, etc.

L'unité mémoire avec l'exécution dans le désordre

Pour rappel, l'unité mémoire a un port d'entrée sur lequel on présente l'adresse à lire/écrire. L'adresse peut provenir du décodeur pour l'adressage absolu, des registres pour les modes d'adressage indirects. Pour les modes d'adressages à calcul d'adresse, les choses sont un peu compliquées, mais on va dire qu'ils proviennent des unités de calcul. Il y a aussi un port pour récupérer la donnée à écrire. Il faut aussi tenir compte du fait que les données lues sont envoyées aux registres, éventuellement aux ALU via le réseau de contournement.

Une unité mémoire est donc reliée au chemin de données via deux entrées et une sortie : une entrée d'adresse, une entrée de données, et une sortie pour les données lues. La sortie est connectée aux registres, via le port d'écriture du banc de registres, et éventuellement au réseau de contournement des ALU.

Unité d'accès mémoire LOAD-STORE.

Le Memory Order Buffer

L'intérieur de l'unité mémoire n'est pas très complexe. Elle contient le cache de données L1 et parfois des unités de calcul d'adresse pour gérer les modes d'adressage base + indice et autres. Mais pour gérer l'exécution dans le désordre des accès mémoire, il faut ajouter une sorte de fenêtre d'instruction modifiée. Elle s’appelle le Memory Order Buffer (MOB). L'unité mémoire est centrée autour de cet MOB, c'est son composant principal.

Pour la décrire rapidement, voyez-la comme une sorte d'hybride entre station de réservation et tampon de réordonnancement (ROB). Son rôle premier est de mettre en attente les micro-opérations pour faire en sorte que les accès mémoire s'exécutent dans l'ordre du programme. Ou du moins qu'ils en donnent l'impression, si le processeur les exécute dans le désordre. Il s'agit donc d'une sorte de tampon de réordonnancement (ROB) spécialisé dans les micro-opérations mémoire, séparé du ROB et qui le complète.

Au-delà de cela, elle met en attente les micro-opérations mémoire tant qu'elles ne peuvent pas s'exécuter. Soit parce qu'elles n'ont pas leur opérandes de prêtes, soit car le cache est occupé et ne peut pas accepter de nouvel accès mémoire, soit parce qu'elles ont une dépendance avec une autre instruction mémoire, soit car il faut respecter l'ordre du programme, etc. La mise en attente est nécessaire pour gérer les dépendances entre instructions mémoire, qui existent, comme on le verra plus bas. De même, elle gère les dépendances RAW entre une micro-opération mémoire et d'autres micro-opération, pour les calculs d'adresse.

Dans la suite du chapitre, nous verrons que le MOB n'est pas implémenté de la même manière suivant le processeur. Déjà, il y a une différence d'implémentation entre avec et sans exécution dans le désordre des accès mémoire. Mais il y a aussi des différences suivant la technique d'exécution dans le désordre utilisée. Nous nommerons ces différentes implémentations avec des termes comme store queue, store buffer, load-store queue, load queue, load buffer, et autres. Mais sachez que la terminologie n'est pas très fiable là-dessus et ces termes sont utilisés un peu n'importe comment. La terminologie utilisée dans ce cours risque de ne pas coller avec tous les articles académiques ou textbooks sur le sujet.

La disponibilité des opérandes

L'unité mémoire doit aussi gérer la disponibilité des opérandes pour les micro-opérations mémoire. L'adresse à lire ou écrire n'est pas nécessairement connue lors de l'émission, elle sera alors disponible plus tard. Dans ce cas, la micro-opération émise est alors mise en attente, en attendant que l'adresse à lire/écrire soit disponible. De même, il se peut qu'une écriture doive écrire une donnée qui n'est pas encore disponible, qui sera calculée dans quelques cycles. Là encore, l'unité mémoire doit mettre en attente la micro-opération d'écriture tant que la donnée n'est pas disponible.

La disponibilité des opérandes peut être gérée de deux grandes manières. La première utilise une fenêtre d'instruction centralisée qui gère la disponibilité des opérandes (adresse et donnée à écrire). Quand une ALU fournit un résultat, il est écrit dans la fenêtre d'instruction, et la micro-opération est alors envoyée aux unités de calcul de l'unité mémoire. Là, les adresses calculées sont envoyées au MOB, qui gère la situation. La méthode marche aussi bien avec des adresses calculées dans l'ALU entière ou dans des ALU de calcul d'adresse séparées.

Intel Nehalem µ-architecture.

Avec la seconde méthode, la disponibilité des opérandes est gérée avec des fenêtres d'instruction décentralisées. En général, les opérations de calcul d'adresse sont gérés comme toutes les autres opérations entières. Il y a une fenêtre d'instruction unique pour les opérations entières et les calculs d'adresse. Prenons le processeur Athlon 64, un processeur AMD sorti dans les années 2000, avait une fenêtre d'instruction pour les opérations flottantes et une fenêtre d'instruction pour le reste, pour les calculs entiers et d'adresse.

La gestion des opérations load-op

Pour rappel, les CPU CISC disposent d'opérations de type load-op, qui lisent une opérande en mémoire RAM. Sur les processeurs modernes, cela veut dire qu'une opérande est lue depuis le cache. En temps normal, de telles instructions machines sont séparées en deux micro-instructions minimum : la lecture de l'opérande et le calcul. Les processeurs qui font cela peuvent très bien avoir des fenêtres d'instruction séparées pour les accès mémoire et les calculs entiers, du moment qu'ils ont un système de contournement entre l'unité mémoire et les ALU entières.

Mais d'autres processeurs font autrement et n'utilisent qu'une seule micro-opération pour les instructions load-op. Les instructions load-op ne prennent qu'une seule entrée dans la fenêtre d'instruction, mais elles sont scindées en un calcul et un accès mémoire juste avant d'être exécutée, quand elles sont schédulées, quand elles sont émises. La fenêtre d'instruction est donc suivie par une sorte de mini-décodeur d'instruction qui gère le cas des instructions load-op, mais laisse les autres micro-opérations tranquilles. Les anciens processeurs AMD sont connus pour utiliser cette organisation.

L'exécution dans l'ordre des accès mémoire

Avec l'exécution dans l'ordre des accès mémoire, le processeur exécute les accès mémoire dans l'ordre du programme. Dans le cas le plus simple, il fait en sorte que les accès mémoire se fassent un par un pour éviter tout problème. Pour cela, il exixte deux grandes solutions.

La première bloque le pipeline lorsqu'elle rencontre deux accès mémoire consécutifs. Si elle veut émettre une micro-opération mémoire, l'unité d'émission vérifie si l'unité d'accès mémoire est libre ou non. Si elle est occupé, un accès mémoire est en cours, et on ne peut pas lancer de nouvelle instruction mémoire. Le pipeline est bloqué, l'unité d'émission émet des pipeline stall, des bulles de pipeline. Il va de soit que les performances sont assez médiocres.

Une autre solution autorise les unités d'accès mémoire à gérer plusieurs accès mémoires simultanés. Attention : cela ne signifie pas forcément qu'on peut démarrer plusieurs accès mémoire au même cycle, sauf si le cache est multiport. En réalité, les accès mémoire ont lieu un par un, mais l'unité d'accès mémoire met en attente les accès mémoire et les exécute dès que possible. Ce faisant, elle ne bloque pas le processeur si on lui demande d'effectuer un accès mémoire en plus. Gérer des accès simultanés avec une LSQ permet certaines optimisations, comme effectuer certains accès mémoire en avance. Mais nous allons d'abord voir le cas simple d'un processeur qui exécute les accès mémoire dans l'ordre, sans aucune optimisation d'aucune sorte.

Il faut bien séparer ce qui relève des caches non-bloquants et ce qui relève de la désambiguïsation mémoire, les deux étant assez similaires. Les unités d'accès mémoire peuvent effectuer des accès mémoires dans le désordre, mais mémorisent l'ordre des lectures et écritures, afin de remettre les accès mémoire dans l'ordre. Un cache non-bloquant permet d'effectuer des accès au cache dans le désordre, mais ne conserve pas toujours l'ordre des accès au cache dans les MSHR.

Précisons que si les accès mémoire se font dans l'ordre, ils peuvent se faire dans le désordre par rapport aux instructions arithmétiques/logiques/branchements/autres. Deux accès mémoire qui se suivent dans le programme s'exécuteront dans cet ordre, mais les instructions arithmétiques entre les deux peuvent être déplacées avant ou après chaque accès si les dépendances de données le permettent

La Load/Store Queue : une FIFO de mise en attente des accès mémoire

Les lectures et écritures sont émises dans l'ordre du programme par l'unité d'émission. Le fait que l'émission se fait dans l'ordre du programme garantit que les accès mémoire s’exécutent dans l'ordre du programme. Une fois émises, les lectures et écritures vont entrer dans l'unité mémoire et sont accumulées dans une mémoire FIFO, appelée la Load/Store Queue (LSQ). C’est grâce à elle que l'unité mémoire peut accepter plusieurs accès mémoire simultanés, c'est elle qui met en attente les accès mémoire. Il s'agit du MOB mentionné plus haut, du moins une version particulière spécialisée au cas qui nous intéresse ici.

Une entrée de la FIFO contient plusieurs champs : un qui précise si l'opération est une lecture ou une écriture, un pour l'adresse mémoire à lire/écrire, un autre pour la donnée à écrire (qui est vide pour une lecture), un autre pour le registre de destination des lectures. Les deux derniers champs sont souvent fusionné en un seul, qui est interprété différemment selon que l'instruction est une lecture ou 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.

Les instructions sont ajoutées à la LSQ au moment de l'émission, et la quittent une fois qu'elles quittent le ROB. La raison à cela est qu'on ne doit pas écrire dans la mémoire RAM ou le cache 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. Et ce point restera valide pour toutes les techniques qui vont suivre. Les écritures sont mises en attente dans la FIFO tant qu'on ne sait pas si elles doivent s'exécuter. Les lectures quant à elles, peuvent s'exécuter immédiatement, car lire une donnée ne change pas l'état du processeur.

FIFO utilisée pour les unités mémoire, aussi appelée Load/Store Queue.

La séparation entre fenêtre d'instruction et LSQ

L'adresse à lire/écrire n'est pas forcément connue au moment de l'émission, soit parce qu'il faut la lire dans les registres ou la calculer. Autant certains modes d'adressage fournissent l'adresse à lire/écrire directement, comme le mode d'adressage absolu, autant d'autres demandent de lire des registres pour la récupérer, comme l'adressage indirect, voire de la calculer.

Pour gérer cela, la LSQ agit un petit peu comme une une station de réservation, à mi-chemin entre une mémoire FIFO et une mémoire associative. Le point commun avec la LSQ précédente est qu'elle mémorise, pour chaque instruction, l'adresse à lire/écrire, la donnée à écrire, le registre de destination, l'opcode de l'opération mémoire. Par contre, les champs adresse et données peuvent être vides. Pour gérer ce cas, elle contient des bits de validité pour chaque champ qui indiquent si l'adresse d'accès est connue, et si la donnée à écrire est disponible pour une écriture. Le tout est appelé une Load-Store Queue unifiée.

Load Store Queue unifiée

Une solution scinde la LSQ en deux structures, aux rôles légèrement différents. La première structure est une LSQ, la seule différence étant qu'elle est plus de petite de N entrées. La seconde structure est une pseudo-LSQ qui stocke les derniers accès mémoire dont les adresses et données à écrire sont connues. En clair, elle contient des accès mémoire prêts à l'exécution, qui attendent que le cache soit libre. Les deux sont souvent appelées load-store queue pour la première et load-store buffer pour la seconde, les termes sont parfois inversés.

La différence avec la LSQ est que les entrées de cette mémoire FIFO n'ont pas besoin de bits de disponibilité pour savoir si l'adresse est connue ou non. Il y a un champ pour la donnée à écrire, et ont est certain que la donnée est dedans, pas besoin de bits de validité. L'avantage est une économie de transistors pas négligeable.

La désambiguïsation mémoire non-spéculative

L'exécution dans l'ordre des accès mémoire est une méthode très conservatrice et interdit de nombreux cas de réorganisation parfaitement légaux, ce qui fait qu'aucun processeur à exécution dans le désordre ne l'utilise. 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).

L'aliasing mémoire

Il existe plusieurs techniques de désambiguïsation mémoire, qui sont résumées dans le tableau ci-dessous. Certaines sont dites spéculatives, à savoir que l'on modifie l'ordre des accès, en prenant le risque que cela change le comportement du programme. En cas d'erreur, le processeur fait comme lors d'une prédiction de branchement ratée : il remet le pipeline en ordre et ré-exécute les accès mémoire dans le bon ordre. D'autres sont au contraire conservatives et garantissent le même résultat que si l'ordre des accès mémoire était inchangé.

Les méthodes conservatrices changent l'ordre des instructions seulement dans certains cas, mais refusent de le faire si deux instructions mémoire ont une dépendance de données, qui interdit de changer leur ordre. Deux instructions mémoire ont une dépendance si elles écrivent ou lisent la même donnée en mémoire RAM/ROM. En clair, deux instructions mémoire ont une dépendance si elles accèdent à la même adresse. Des instructions mémoires qui lisent/écrivent des adresses différentes sont naturellement indépendantes. Lorsque deux instructions mémoire lisent/écrivent à la même adresse, on parle d'aliasing mémoire. Détecter les cas d'aliasing mémoire est primordial pour gérer la désambiguïsation mémoire.

Formellement, l'aliasing mémoire n'est ni plus moins que l'application des dépendances de données aux instructions mémoire. Et comme les autres dépendances de données, il existe plusieurs types d'aliasing mémoire : RAR, RAW, WAR et WAW. Les dépendances RAW imposent que les lectures ne doivent pas s'exécuter avant une écriture dépendante. La lecture doit renvoyer la dernière donnée écrite. Les dépendances WAR imposent que l'on ne peut pas déplacer une écriture avant une lecture à la même adresse. Enfin, les dépendances WAW font que l'ordre des écritures doit être celui du programme : impossible de changer l'ordre de deux écritures. Les dépendances RAR ne posent aucun problème, les lectures peuvent changer d'ordre sans aucun problème, tant qu'il n'y a pas d'écritures entre les deux.

La désambiguïsation mémoire fonctionne d'autant mieux que les adresses à lire/écrire sont connues le plus tôt possible. Pour cela, il est possible de séparer les accès à la mémoire en deux micro-instructions : une pour le calcul d'adresse et l'autre pour les accès mémoire. Cela permet de calculer les adresses dès que possibles, et donc 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.

Les méthodes de désambiguïsation mémoire

Pour résumer, les méthodes conservatrices garantissent plusieurs choses. premièrement, les écritures se font dans l'ordre du programme. Deuxièmement, si une lecture lit une donnée modifiée par une écriture précédente, il y a interdiction de faire passer la lecture avant l'écriture. Troisièmement, interdiction de faire passer une écriture avant une lecture à la même adresse. La première règle gère les dépendances WAW, la seconde les dépendances RAW, la troisième les dépendances WAR. Et comme pour les dépendances de données normales, seules les dépendances RAW sont de vraies dépendances de données. Les deux autres dépendances viennent du fait que l'on utilise la même adresse pour stocker des valeurs différentes. Mais des techniques similaires au renommage de registre permettent de les faire disparaitre, dans une certaine mesure. Nous verrons ces technique en temps voulu, mais sachez qu'elles utilise une version modifiée de la FIFO précédente.

Les trois règles peuvent s'implémenter de plusieurs manières différentes. Dans ce qui va suivre, nous allons voir les deux implémentations principales, résumées dans ce tableau. Pour simplifier, la première utilise un pipeline unique qui gère lectures et écritures, alors que le second utilise deux pipelines séparés pour les lectures et écritures, bien que les deux communiquent fortement. Ils gèrent l'aliasing entre instructions, et notamment le cas où une lecture lit une donnée modifiée par une écriture précédente : interdiction de faire passer la lecture avant l'écriture.

Modèle de consistance	Description
Partial Ordering	Les écritures se font dans l'ordre, les lectures ont des possibilités limitées d'exécution dans le désordre. Une lecture peut d'exécuter si toutes les écritures précédentes sont terminées, qu'elles ont déjà écrit leurs données. Par écritures précédentes, on peut vouloir dire toutes les écritures, ou seulement celles se faisant à la même adresse mémoire que la lecture. Le premier cas est simple à implémenter, mais peu performant, le second cas est idéal mais un peu plus complexe à implémenter.
Load Ordering, Store Ordering	Les lectures et écritures sont traitées à part les unes des autres, mais les écritures s'exécutent dans l'ordre, les lectures s'exécutent dans l'ordre. En clair, impossible de faire passer une écriture avant une autre plus ancienne, idem pour les lectures. Par contre, on peut faire passer une lecture avant une écriture et inversement. La seule exception est quand une lecture lit une donnée écrite pas une écriture précédente.

Précisons que nous nous contentons du cas où les lectures et écritures ont leur adresse connue en entrant dans l'unité mémoire. Les différents modèles de désambiguïsation mémoire ont des implémentations différentes. Avec ces techniques, la mémoire FIFO plus haut disparait ou est fortement altérée. Voyons-les en détail.

Le Load Ordering, Store Ordering : les files d'écriture et de lecture

Avec le Load Ordering, Store Ordering, les lectures et écritures sont considérées séparément. Les lectures s'exécutent dans l'ordre, les écritures s'exécutent dans l'ordre, mais les lectures peuvent passer avant/après les écritures et réciproquement, tant que l'asliasing le permet. Il y a un cas bien précis qui empêche certaines réorganisations : si une lecture lit une donnée écrite par une écriture précédente. Pour gérer ce cas, l'unité d'accès mémoire incorpore des sécurités pour empêcher les ré-organisations problématiques.

L'implémentation utilise souvent deux unités d'accès mémoire séparées : une pour les lectures, une autre pour les écritures. Les deux ont leur propre fenêtre d'instruction, qui mémorise les instructions dans l'ordre du programme. En plus de ces deux fenêtres d'instruction, la LSQ est scindée en deux FIFOs séparées : une file d'écriture (store queue) pour les écritures et une file de lecture (load queue) pour les lectures. La file d'écriture 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 disponibles. La file de lecture mémorise pour chaque lecture, l'adresse à lire et le registre de destination, ainsi que des bits de contrôle. La file de lecture est facultative, quelques processeurs font sans.

Exécution dans le désordre des lectures.

L'idée est que les lectures peuvent s'exécuter dès que possible si leurs opérandes sont disponibles et si l'aliasing le permet. Les lectures doivent avoir lieu le plus tôt possible, car la donnée lue est généralement utilisée par d'autres instructions dépendantes. Elles sont donc à la tête d'une chaine de dépendances de données qui peut bloquer le pipeline si elles n'est pas résolue très tôt. Dès qu'une lecture peut être lancée, elle accède directement au cache de données. Par contre, si l'aliasing ne le permet pas (écriture à la même adresse pas encore effectuée) ou que l'adresse à lire n'a pas encore été calculée, la lecture attend son tour.

Précisons que la file de lecture est en théorie facultative, vu que les lectures se font le plus rapidement possible, mais nous l'ajoutons pour simplifier l'implémentation. La file de lecture permet d'accumuler des lectures ultérieures si une lecture est bloquée et attend son tour. Cela évite de bloquer l'unité de lecture et donc le reste du pipeline. Elle a cependant un défaut : celui de forcer les lectures à s’exécuter dans l'ordre, ce que la technique du partial ordering permet d'éviter.

La seule contrainte est qu'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) autorise la lecture en absence de dépendances. 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 l'implémenter, il faut comparer l'adresse à lire avec toutes les adresses dans la file d'écriture. Pour cela, la file d'écriture est modifiée et devient un mélange entre FIFO et mémoire associative. La procédure de comparaison est alors la suivante. Premièrement, on extrait l'adresse à lire de la lecture à exécuter, qui sort de la file de lecture. L'adresse est alors envoyée à la file d'écriture, et est comparée à toutes les entrées d'adresse dedans. En cas de match, la lecture est bloquée dans la file de lecture. Mais s'il n'y a aucune correspondance, alors la lecture peut s'exécuter. Précisons une chose importante : il arrive que des écritures soient dans la file d'écriture, mais que leur adresse n'ait pas encore été calculée. Dans ce cas, il y a potentiellement dépendance avec la lecture si l'adresse se révèle être la même une fois calculée : on considère que les adresses inconnues sont des correspondances/match.

Une optimisation de la technique précédente autorise la lecture à lire directement la donnée depuis la file d'écriture. 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.

L'implémentation est assez simple : il faut transformer la file d'écriture en un hybride cache-FIFO, dont chaque ligne mémorise la donnée à écrire et dont le tag est l'adresse où écrire. Toute lecture va déclenche 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. Pour gérer le cas où plusieurs écritures à la même adresse sont mises en attente dans la file d'écriture, la file d'écriture renvoie la dernière donnée écrite, celle fournie par l'écriture la plus récente.

Le Partial Ordering : la Load/Store Queue

Avec la technique précédente, les lectures s'exécutent dans l'ordre, à savoir que l'on ne peut pas déplacer une lecture avant ou après une autre. Et cette limitation a des conséquences sur la performance de l'exécution dans le désordre des accès mémoire. Pour éviter cela, la technique du Partial Ordering permet aux lectures de s'exécuter dans le désordre, même si les écritures se font toujours dans l'ordre. Il faut juste que les conditions d'aliasing soient respectées.

La technique s'implémente en supprimant la file de lecture, qui force les lectures à s'exécuter dans l'ordre. A la place, le partial ordering utilise une LSQ modifiée, qui tient plus de la mémoire associative, voire du cache, que d'une FIFO. Pour faire la différence, nous parlerons de Load/Store Buffer, abrévié en LSB. Un autre terme pourrait être celui de Memory ReOrder Buffer, plus explicite. Le LSB est couplé à un système de détection des dépendances mémoire qui détermine quelles instructions peuvent s'exécuter sans problème. Uen fois les instructions prêtes détectées, elles s'exécutent dès que possible. On peut voir la LSB comme une mini-fenêtre d'instruction spécialisée, sauf qu'elle ne détermine pas la disponibilité des opérandes, mais celle des adresses.

La technique utilise deux matrices de ce type : une matrice de disponibilité, et une matrice de dépendance. Ces matrices forment une espèce de tableau carré, organisé en lignes et en colonnes. L'instruction dans la énième entrée se voit attribuer la énième ligne et la énième colonne. À 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.

La matrice de disponibilité permet de bloquer l'exécution des lectures/écritures tant qu'une instruction précédente n'a pas calculé son adresse, tant qu'on ne peut pas vérifier les dépendances. Lorsqu'une instruction est ajoutée dans le LSB, elle met tous les bits de la colonne attribuée à 1 si l'adresse à lire/écrire est inconnue, puis les met à 0 une fois l'adresse calculée. Une instruction ne peut pas démarrer si, sur la ligne qui lui est attribuée, se trouve un 1. Plus précisément, si on trouve un 1 pour les instructions plus anciennes, ce qui fait qu'une partie de la matrice est ignorée. Les bits notés X dans le tableau suivant sont ignorés, car ils précisent la disponibilité des opérandes d'une opérande ultérieure, ce qui est inutile. En clair, les calculs d'adresse modifient les colonnes, et on vérifie les lignes pour autoriser l'exécution.

Instructions mémoire dans la LSB, triées de la plus ancienne à la plus jeune	0	1	2	3	4	5	6
0	1	X	X	X	X	X	X
1	0	0	X	X	X	X	X
2	0	1	0	X	X	X	X
3	0	1	1	1	X	X	X
4	0	0	0	0	1	X	X
5	0	0	1	0	0	1	X
6	1	1	1	1	1	1	0

Les matrices de dépendances fonctionnent sur le même principe, mais déterminent les dépendances mémoire. Lorsque le processeur a calculé une adresse, il la compare avec les adresses à lire/écrire déjà dans la LSB. Il met alors à jour les bits de la colonne de la matrice de dépendance : le bit à l'intersection d'une ligne et d'une colonne est mis à 0 si les deux instructions n'ont pas de dépendances, à 1 si elles en ont une. Une instruction mémoire est exécutée si tous les bits de sa ligne sont à 0. Là encore, on ne tient compte que des bits pour les instructions plus anciennes, la matrice a encore une fois une forme triangulaire, comme pour la matrice de disponibilité.

L'exécution spéculative des accès mémoires sans prédiction de dépendances mémoire

Pour diminuer l'effet des dépendances mémoires, de nombreux processeurs utilisent l’exécution spéculative. La prédiction de branchement est un cas d’exécution spéculative assez connu, et il est possible de faire la même chose avec les accès mémoire. Le processeur exécute des accès mémoire sans se soucier de leurs dépendances, mais vérifie si aucune dépendance mémoire n'est violée et corrige le tir dès qu'une violation est détectée. 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.

Toutes les techniques de ce genre exécutent des lectures dès que possible, dans le désordre. L'avantage est que cela permet d'exécuter les lectures en avance. La donnée lue est utilisée comme opérande de toute une chaine d’instruction, les lectures sont souvent le départ d'une chaine de dépendance, ce qui fait que les exécuter en avance fait prendre de l'avance à un paquet d'instructions. Mais il faut comparer cet avantage au risque de mauvaise prédiction. Et aussi bizarre que cela puisse paraître, cela donne de bons résultats. Il faut dire que les situations où une lecture relit une donnée tout juste écrite sont rares : même pas 2 à 3 % des lectures. Les dépendances mémoire sont donc très rares, les cas d'aliasing sont vraiment limités.

Aussi, exécuter de manière spéculative les lectures a un avantage : le hardware qui vérifie les dépendances mémoire reste globalement le même à peu de choses près. Il est juste déplacé dans le pipeline et adapté à sa nouvelle fonction. Le cout en hardware est similaire, peut-être un peu supérieur, mais les performances sont bien meilleures.

La file de vérification des lectures

Une première technique adapte l'organisation du Load Ordering, Store Ordering, avec une file d'écriture et une file de lecture séparées. Mais l'organisation est modifiée de manière à conserver les lectures déjà envoyées au cache. Pour cela, plusieurs solutions équivalentes existent. La première est d'ajouter une nouvelle file d'attente, qui mémorise les lectures envoyées au cache. Elle se situe donc en aval de la file de lecture, et n'a pas du tout le même rôle. Nous l’appellerons la file de vérification des lectures. La seconde solution fusionne cette file de vérification des lectures avec la file de lecture, mais la technique est plus compliquée à comprendre, aussi je la met de côté, vu qu'elle est quasiment équivalente. Une troisième solution fusionne la file de lecture, d'écriture et de vérification en une seule structure appelée la load-store queue, le terme est assez chargé et polysémique.

Pour vérifier qu'il n'y a pas d'erreur de spéculation, le processeur conserve l'adresse de la lecture effectuée dans la file de vérification des lectures. Il faut conserver ces informations jusqu'à ce que toutes les instructions précédant la lecture dans l'ordre du programme soient terminées. Les lectures rentrent dans la file de vérification des lectures quand elles quittent la file de lecture. Elles y rentrent avec leur adresse, mais il n'y a pas besoin d'y stocker la donnée lue. Les lectures y restent tant qu'elles n'ont pas quitté le tampon de réordonnancement/ROB.

Il n'y a pas besoin de file équivalente pour les lectures car la file d'écriture fait déjà la même chose. La file de lecture et d'écriture n'ont pas du tout le même poids. Les lectures sont exécutées immédiatement, sans tenir compte des dépendances mémoires, de manière spéculative. Le processeur ne vérifie pas si les lectures sont dépendantes des écritures au moment de les démarrer. Elles sortent de la file de lecture dès que leurs adresses sont calculées. Le rôle de la file de lecture est alors de simplement mettre en attente les lectures tant que l'adresse à lire n'est pas connue.

Pour vérifier les violations de dépendances mémoire, deux solutions sont possibles. La première vérifie les violations de dépendances mémoire à chaque écriture. Dès qu'une écriture est sur le point de quitter la file d'écriture. L'unité mémoire récupère alors l'adresse d'écriture et la compare avec toutes les lectures dans la file de vérification des lectures. Si aucune correspondance n'est trouvé, c'est que les lectures spéculatives n'ont accédé à l'adresse d'écriture. Mais si il y a correspondance, c'est qu'une lecture a lu l'adresse avant qu'elle soit écrite. Pour cela, la file de vérification des lectures est un mélange entre FIFO et cache/mémoire associative. La vérification fait cependant gaffe à ne prendre en compte que les lectures situées avant l'écriture dans l'ordre du programme, la file de vérification doit être conçue pour ça, elle doit contenir des informations sur l'ordre des instructions dans le programme, comme un identifiant d'entrée de ROB.

La seconde méthode vérifie les violations de dépendance mémoire au moment quitter la file de lecture et le ROB. La lecture quitte la file de lecture et le ROB, la lecture est ré-exécutée et la donnée relue. Le processeur compare alors la donnée lue à ce moment avec la donnée lue avant. Si la donnée est différente, alors il y a eu erreur de violation de dépendance mémoire. Évidemment, relire une donnée n'est pas gratuit. Il est possible de limiter son impact en performance en dédiant un port de lecture sur le cache rien que pour ça. Mais le cout en circuit est comparable à l'usage d'une FIFO associative de la technique précédente. Mais quoi qu'il en soit, le cache doit permettre des lectures en un seul cycle, sans quoi la méthode ne marche pas vraiment.

Le tampon de résolution d’adresse

Voyons maintenant une autre 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 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 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 désambiguïsation mémoire a des effets de bord

La désambiguïsation mémoire a une caractéristique que l'exécution dans le désordre simple n'a pas : elle a des effets qui déborde sur la mémoire. Il est possible de savoir si un processeur fait de la désambiguïsation mémoire en regardant le bus mémoire. On s’aperçoit alors que les lectures se font dans un ordre différent de celui du programme. A l'opposé, l'exécution dans le désordre n'a pas d'effets observables de ce genre. Elle améliore la performance, elle modifie les durées observables des instructions, mais cela se limite à des questions de timings. Le seul moyen de savoir si un processeur fait de l'exécution dans le désordre est de mesurer les latences/durées de chaque instruction. Mais aucun état observable au-delà des timings n'est modifié. Pas avec la désambiguïsation mémoire.

La consistance mémoire

Le fait que la désambiguïsation mémoire ait des effets observables ne pose aucun problème avec un seul processeur, ca elle est conçue pour. Par contre, les techniques de désambiguïsation mémoire peuvent poser des problèmes avec plusieurs processeurs. Il arrive que des programmes partagent une même portion de mémoire, et lisent/écrivent dedans. Avec plusieurs processeurs, chaque processeur effectue la désambiguïsation mémoire dans son coin sans se préoccuper des autres. Les opérations d'écriture peuvent être mises dans le désordre du point de vue des autres processeurs, et les lectures effectuées par les autres processeurs peuvent alors renvoyer de vielles données.

Un exemple classique est celui de deux cœurs qui partagent le même cache ou la même mémoire, mais qui utilisent chacun une file d'écriture (store buffer). Imaginons que le premier cœur effectue une écriture, puis une lecture, à des adresses différentes. L'écriture est retardée grâce au tampon d'écriture, alors que la lecture lit directement le cache. Pour le premier processeur, l'écriture s'est réalisée avant la lecture, car pour lui, la fin de l'écriture signifie écrire dans le tampon d'écriture. Mais pour le second cœur, l'ordre s'est inversé : il voit la lecture dans le cache, puis l'écriture dans le cache. La raison est qu'il n'a pas connaissance du contenu du tampon d'écriture de l'autre cœur.

Les programmeurs doivent tenir compte de ce genre de situations, dans des cas assez rares et liés à la programmation bas niveau. Pour cela, ils doivent savoir comment le processeur réorganise les accès mémoire. Concrètement, chaque processeur définit un modèle de consistance mémoire qui indique quelles optimisations sont activées et non. Il s'agit d'une sorte de contrat entre le logiciel et le matériel : les programmeurs savent comment le processeur va réorganiser les lectures et écritures et peuvent coder leurs programmes en fonction. L'implémentation du système de consistance mémoire dépend grandement de l'architecture, mais des modèles ont été standardisés afin de permettre aux programmeurs de savoir où placer les barrières mémoires. Il s'agit de vrais standards, formalisés, parfois mathématiquement, que des chercheurs étudient sur un plan mathématique et algorithmique.

Le modèle préféré des programmeurs est la consistance séquentielle, où les différents processeurs effectuent des accès mémoire dans l'ordre du programme et les accès mémoire simultanés sont interdits. La première contrainte interdit l'usage de mécanismes de désambiguïsation mémoire, la seconde interdit l'usage de caches non-bloquants. La consistance séquentielle a donc un cout en performance assez important, ce qui fait que les processeurs modernes n'utilisent pas la consistance séquentielle.

Un modèle plus flexible est le total store ordering, qui autorise la présence d'une file d'écriture et l'usage de caches non-bloquants pour les lectures (interdit d'avoir plusieurs écritures simultanées). C'est plus ou moins celui utilisé par les processeurs x86, comme on le verra plus bas. Il existe des modèles de consistance mémoire plus relâchés, appelés des modèles de consistance faible, qui autorisent diverses optimisations de spéculation mémoire, la combinaison d'écriture (fusionner deux écritures à la même adresse en une seule), etc. Ils sont supportés sur les architectures ARM et POWER.

Les barrières mémoire

Le changement d'ordre des lectures et écritures peut poser occasionnellement des problèmes avec la programmation pour les architectures multi-processeur ou multicœurs. Il existe des morceaux de code qui ne marchent que si la consistance séquentielle est respectée et il faut faire en sorte qu'ils marchent sur des processeurs avec un modèle de consistance mémoire différent. Pour cela, les processeurs incorporent des instructions appelées barrières mémoires ou Fences. Elles forcent le processeur à terminer tous les accès mémoire qui précédent dans l'ordre du programme. Certains processeurs possèdent une barrière mémoire pour les lectures et une autre pour les écritures. D'autres processeurs ajoutent des barrières mémoires dédiées à des cas particuliers. Elles permettent de forcer les accès à des données partagées à dérouler correctement.

Fences.

Leur implémentation est assez simple : elles empêchent l'émission de toute nouvelle instruction mémoire, tant qu'une condition précise n'est pas réunie. Par exemple, la barrière mémoire pour les écriture attend que la file d'écriture soit vidée avant de démarrer le moindre accès mémoire.

Un compilateur peut placer les barrières mémoires au bon endroit, avec un peu d'aide du programmeur. Certains langages de programmation permettent d'indiquer au compilateur qu'une donnée doit toujours être lue depuis la mémoire RAM, via le mot-clé volatile. C'est très utile pour préciser que cette donnée est potentiellement partagée par plusieurs processeurs ou manipulable par des périphériques. Les compilateurs peuvent placer des barrières mémoires lors des lectures ou écritures sur ces variables, mais ce n'est pas une obligation.

Il arrive aussi que le programmeur doive manipuler explicitement des barrières mémoires. Utiliser l'assembleur est alors une possibilité, mais qui est rarement exploitée, pour des raisons de portabilité. Pour limiter la casse, certains systèmes d'exploitations ou compilateurs peuvent aussi fournir des barrières mémoires explicites, encapsulées dans des bibliothèques ou cachées dans certaines fonctions.

La modèle de consistance des processeurs x86

Après avoir vu la théorie, passons maintenant à la pratique. Dans cette partie, on va voir les modèles de consistances utilisés sur les processeurs x86, ceux qu'on retrouve dans les PC actuels. Le modèle de consistance des processeurs x86 a varié au cours de l'existence de l'architecture : un vulgaire 486DX n'a pas le même modèle de consistance qu'un Core 2 duo, par exemple. Ils ont évolués au cours du temps, avec l'arrivée de nouvelles optimisations. De plus, leur formalisation a été progressive, et s'est faite au fur et à mesure.

En général, les modèles de consistance des processeurs x86 ont toujours étés assez restrictifs, si on les compare aux autres processeurs. Il s'agit de modèles de type total store ordering (TSO), au moins dans les grandes lignes. Ils permettent donc d'effectuer certaines lectures en avance, soit parce que les lectures se font à des adresses différentes, soit par utilisation de réacheminement écriture vers lecture. Les possibilités d'exécution en avance des lectures varient suivant le processeur, elles deviennent de plus en plus performantes avec le temps.

Le premier modèle de consistance est apparu sur les premiers processeurs x86 et est resté en place sur tous les processeurs de marque Pentium. Les processeurs de l'époque n'incorporaient pas beaucoup d'optimisations, le budget en transistor n'était pas assez conséquent pour ça, la mémoire n'était pas assez lente. Le modèle TSO de l'époque n'autorisaient que peu de lectures anticipées. Une lecture ne peut être exécutée en avance que sous les conditions suivantes :

• les écritures contournées se font dans la mémoire cache ;
• la lecture doit se faire dans la mémoire RAM ;
• les écritures se font à une adresse différente de la lecture ;
• aucune transaction avec un périphérique ne doit être en cours.

A partir du Pentium 4, les choses changent. Le Pentium 4 est en effet le premier processeur à implémenter des techniques permettant d’exécuter plusieurs processus en parallèle, dont l'Hyperthreading. En conséquence, le modèle de consistance a du être assoupli pour éviter de perdre bêtement en performance. Il s'agit d'un vrai modèle de type TSO, la majeure partie des contraintes sur les lectures anticipées sont réduites au minimum. Il y a aussi des contraintes supplémentaires pour les instructions dite atomiques, ainsi que pour les instructions qui accèdent aux périphériques ou aux entrées-sorties. Une optimisation séparée du TSO est que les écritures en mémoire peuvent changer d'ordre dans un cas exceptionnels : les écritures effectuées par les instructions de copie mémoire comme REPMOVSD, REPSCACB, ainsi que les instructions SSE MOVNTI, MOVNTQ, MOVNTDQ, MOVNTPS, MOVNTPD. Les écritures effectuées dans ces instructions peuvent se faire dans un désordre complet (ou presque).

Lors du passage au 64 bits, le modèle mémoire des processeurs x86 de l'époque a été formalisé dans un papier d'Intel appelé Intel® 64 Architecture Memory Ordering White Paper, mis à jour en 2008 suite à quelques problèmes techniques. La formalisation du modèle a été d'une grande aide aux programmeurs, qui devaient se débrouiller avec des documentations qui ne formalisaient pas de modèle de consistance précis. Le document décrit un modèle de consistance mémoire portant le nom barbare de total lock order + causal consistency” (TLO+CC), qui admet plus d'optimisations que le modèle TSO. Mais la description était en réalité légèrement différente du modèle mémoire réellement implémenté sur les processeurs existants, qui utilisaient du TSO, sauf en de rares occasions.

Les concepteurs de processeur font souvent cela, à savoir définir un modèle de consistance plus laxiste que réellement implémenté, pour des questions de comptabilité. Ainsi, si les futurs processeurs de la marque implémentent un modèle plus laxiste, les programmes déjà codés continuent de fonctionner. Le modèle décrit dans la documentation laisse de la marge pour le futur.