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 pas encore vu comment s'exécutent les accès mémoire sur un processeur à exécution dans le désordre.

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. Lors de l'émission, le scoreboard 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.

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 stination 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

Il faut tenir compte du fait que l'adresse 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. Pire : les lectures ou écriture doivent parfois calculer l'adresse à lire/écrire, elle n'est pas fournie sur un plateau.

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.

Les adresses peuvent être calculées par les ALU généralistes, ce qui fait que la LSQ unifiée est connectée au réseau de contournement pour récupérer les adresses et données à écrire. Elle est aussi reliée aux registres pour gérer les modes d'adressage indirects. Et enfin, elle est reliée aux unités de calcul d'adresse intégrée dans l'unité mémoire, qui peuvent calculer certaines adresses.

Load Store Queue unifiée

Une solution plus pratique scinde la LSQ en deux mémoires FIFO, l'une faisant office de fenêtre d’instruction, l'autre faisant office de mise en attente pour régler les dépendances. Pour faire simple, on a une fenêtre d'instruction, suivie par un circuit d'accès au banc de registre et une unité de calcul d'adresse, suivi par la seconde FIFO.

La première mémoire FIFO vérifie la disponibilité des opérandes/adresses, à savoir que les registres à lire sont disponibles et ont bien les adresses/opérandes voulues. Une instruction quitte cette FIFO quand ses opérandes sont prêts, ce qui correspond à deux cas. Soit l'adresse à lire/écrire est connue : elle a été lue depuis les registres ou obtenue via le réseau de contournement. Soit les opérandes qui permettent de calculer l'adresse sont dans ce cas les opérandes sont lues depuis les registres et l'adresse est calculée par une unité de calcul d'adresse en aval de la station de réservation.

Une fois les adresses connues, les instructions sont ajoutées dans une mémoire FIFO, qui ressemble beaucoup à la LSQ. La différence est que toutes les entrées de cette mémoire FIFO contiennent l'adresse à lire/écrire, 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é.

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 LSQQ 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.

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.