Fonctionnement d'un ordinateur/La désambiguïsation mémoire

Dans les chapitres précédents, nous avons vu la mal-nommée exécution dans le désordre dans les chapitres précédents, qui devrait plutôt s'appeler l'émission dans le désordre. Elle modifie l'ordre des instructions pour gagner en efficacité, mais cela n'est valable que pour les instructions travaillant sur des registres ! Nous n'avons pas parlé de l'exécution dans le désordre des accès mémoire, car ils sont un peu à part. Et pour comprendre pourquoi, nous allons dédier ce chapitre à la gestion des accès mémoire dans le pipeline.

L’émission des accès mémoire

Avant de poursuivre, faisons un rappel rapide. Il faut distinguer deux types de dépendances de données : les dépendances de registres (deux instructions manipulent le même registre), alors que l'unité mémoire 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.

L'aliasing mémoire et les dépendances mémoire

Pour rappel, deux instructions ont une dépendance d'adresse si elles écrivent ou lisent la même adresse mémoire, ce qui interdit de changer leur ordre. Des instructions mémoires qui lisent/écrivent des adresses différentes sont 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, et cela demande de comparer des adresses.

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 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. Par contre, les autres dépendances imposent trois contraintes.

Les dépendances RAW imposent que les lectures ne doivent pas s'exécuter avant une écriture à la même adresse.
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 trois contraintes peuvent s'implémenter de plusieurs manières différentes. 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. S'il existe des techniques similaires au renommage de registre permettent de les faire disparaitre, elles sont très limitées.

La désambiguïsation mémoire

Diverses optimisations permettent d'émettre des accès mémoire dans le désordre, exactement comme l’exécution dans le désordre le fait pour les autres instructions. Elles utilisent pour cela des fenêtres d'instruction spécialisées dans les accès mémoire. 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 (memory disambiguation) pour parler de l'exécution dans le désordre des accès mémoire.

Le but de la désambiguïsation mémoire est d'exécuter les lectures le plus tôt possible. La raison est que la donnée lue est utilisée par d'autres instructions, dépendantes de la lecture. Elles sont donc à la tête d'une chaine de dépendances de données qui peut bloquer le pipeline si elle 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.

Le problème est que la désambiguïsation mémoire demande de comparer des adresses, pour détecter les dépendances d'adresse. Et cela pose de sérieuses contraintes pour son implémentation. En comparaison, l'exécution dans le désordre normale compare des registres, ce qui est beaucoup plus simple. Les registres utilisés par une instruction sont directement encodés dans l'instruction elle-même, ce qui fait qu'on peut détecter les dépendances de registre à l'émission, voire au décodage. Et elles peuvent même être éliminées par le renommage de registre pour les dépendances WAW et WAR. Par contre, les adresses sont des opérandes d'instruction, elles ne sont pas encodées dans l'instruction elle-même. Il y a certes d'exception de l'adressage absolu, mais elle est minoritaire. Avec l'adressage indirect ou indicé, les adresses sont soit lues depuis les registres, soit calculées par une unité de calcul. Les adresses ne sont donc connues qu'une fois que l'instruction a attendu suffisamment de temps dans la fenêtre d'instruction.

Le calcul anticipé des adresses mémoire

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.

Une implémentation possible effectue les calculs d'adresse dans les unités de calcul entière. L'ALU entière et l'unité mémoire sont alors dans deux avals séparés, en parallèle. La micro-opération de calcul d'adresse s'exécute dans une ALU, et son résultat est envoyé à l'unité mémoire. Pour cela, l'adresse calculée est envoyée à l'unité mémoire via un système de contournement dédié, qui relie les sorties des ALU entières à l'unité mémoire.

Une solution alternative utilise un aval unique qui s'occupe à la fois des micro-opérations entières et des micro-opérations mémoire. L'aval a alors deux étages en série, un pour l'unité de calcul, suivi par l'étage d'accès mémoire. Le pipeline RISC classique était dans ce cas, pour rappel. Cette solution permet d'avoir un pipeline dit de longueur fixe, à savoir que toutes les instructions font le même nombre de cycles d'horloge. De plus, elle garantit que les instructions mémoire sont décodées en une seule micro-opération. En clair, il y a un seul aval pour toutes les instructions. Mais elle vient avec un défaut majeur : de nombreuses instructions n'utilisent pas l'unité mémoire, mais doivent quand même traverser l'étage associé, qui passe un cycle à ne rien faire.

L’émission dans l'ordre des accès mémoire

Avant toute chose, faisons quelques rappels sur l'exécution dans le désordre. Les micro-opérations renommées sont mises en attente avant que les conditions pour leur émission soient remplies. La mise en attente peut se faire soit dans une file de micro-opération, soit dans une fenêtre d'instruction. Une file de micro-opération est une mémoire FIFO qui garde les micro-opération dans leur ordre d'émission, l'ordre du programme. Les micro-opérations sont donc émises dans l'ordre du programme, il n'y a pas d'émission dans le désordre. Par contre, les fenêtres d'instructions peuvent émettre les micro-opérations dans le désordre, dans un ordre différent de celui du programme. Dans les deux cas, les écritures sont retardées via une file d'écriture, qu'on a vu il y a quelques chapitres et sur laquelle on fera des rappels.

La file de µops mémoire

Avec l'émission dans l'ordre des accès mémoire, le processeur émet les accès mémoire dans l'ordre du programme. Cela implique que l'unité mémoire n'a pas de fenêtre d'instruction, ni de station de réservation associée. À la place, les micro-opérations mémoire sont placées dans une file de micro-opération dédiée, appelée la file de µops mémoire. Par contre, pour les unités de calcul, le processeur utilise des fenêtres d'instruction. Autant les accès mémoire se font dans l'ordre, autant les instructions arithmétiques/logiques/branchements/autres sont exécutées dans le désordre. En clair, le processeur peut supporter l'exécution dans le désordre, sauf pour les micro-opérations mémoire.

Nous avons volontairement omis le cas où le processeur n'a pas d'exécution dans le désordre, où il y a une file de micro-opération unique. Mais c'est globalement la même chose, car une file de micro-opération unifiée émet toutes les instructions dans l'ordre.

La file de µops mémoire est une mémoire FIFO, qui contient plusieurs entrées, chaque entrée pouvant accueillir une µops mémoire. Une entrée 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és en un seul, qui est interprété différemment selon que l'instruction est une lecture ou une écriture. Elle contient aussi des bits de validité, qui indique si l'adresse ou la donnée sont disponibles, ou si le champ associé est vide.

L'unité mémoire ne permet que de faire un accès mémoire à la fois. Du moins, elle a un port sur lequel on envoie la micro-opération émise, que ce soit une écriture ou une lecture. Vu de l'extérieur, il faut attendre qu'un accès mémoire soit terminé pour lancer le suivant. Avant d'émettre une micro-opération mémoire, la file de micro-opération (son scoreboard) vérifie si l'unité d'accès mémoire est libre ou non. Si elle est occupée, un accès mémoire est en cours, et on ne peut pas émettre de micro-opération mémoire. 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, et c'est au tour d'une nouvelle micro-opération mémoire.

Mais il s'agit là du comportement vu de l'extérieur de l'unité mémoire. En réalité, l'unité mémoire utilisee quelques optimisations en interne qui permettent d'exécuter dans le désordre les micro-opérations mémoire.

La file d'écriture : une FIFO de mise en attente des écritures

Afin de supporter les exceptions précises, les écritures doivent respecter deux contraintes : s'exécuter dans le tout dernier étage du pipeline, s'exécuter dans l'ordre du programme. Pour cela, les écritures sont mises en attente tant que les instructions précédentes ne sont pas terminées. Les écritures dans le cache sont mises en attente dans une mémoire FIFO, appelée la file d'écriture, ou encore la Write Queue. Nous en avions déjà parlé dans le chapitre sur le pipeline, dans la section sur les exceptions précises. Mais quelques rappels ne feront pas de mal.

L'écriture est insérée dans la file d'écriture lorsqu'elle est émise, elle en sort à l'étage de Writeback si tout se passe bien. Si une exception est détectée, l'étage de Writeback vide la file d'écriture, ce qui annule les écritures mises en attente, faites à tort. De plus, la file d'écriture est une mémoire FIFO, qui mémorise les écritures dans l'ordre du programme. En effet, les écritures sont ajoutées dans la file d'écriture lorsqu'elles sont émises, et elles sont émises dans l'ordre du programme.

La file d'écriture garantit que les écritures sont dans l'ordre du programme. Et cette propriété élimine totalement les dépendances WAW. Le fait que les écritures se font à la fin du pipeline élimine quant à elle les dépendances WAR. Il ne reste plus qu'à gérer les dépendances RAW, celles où une lecture lit une donnée écrite par une autre instruction. Une telle situation survient, car les écritures sont mises en attente pendant un certain temps, la donnée écrite peut être lue pendant ce laps de temps. La lecture ne peut pas lire la donnée dans le cache, car la donnée à lire n'y est pas encore enregistrée. Le cas est rare, car il demande de lire une donnée qu'on vient d'écrire, mais il existe. Il se manifeste surtout sur les processeurs avec peu de registre, où des données doivent régulièrement être déplacées temporairement en mémoire RAM.

Pour éviter cela, une solution consiste mettre en attente les lectures si une écriture est en attente. Les lectures sont maintenues dans la file de µops tant que la file d'écriture n'est pas vide. La file de µops mémoire est suivie d'un circuit de détection des dépendances, un scoreboard mémoire qui est assez simple. L'unité mémoire fournit un bit qui indique si la file d'écriture est vide ou non, ainsi qu'un second bit qui indique qu'elle est vide. Les deux ne sont pas compliqués à générer, ils font partie intégrante de l'interface de toute mémoire FIFO digne de ce nom. Le scoreboard mémoire utilise ces deux bits pour savoir s'il peut émettre une micro-opération mémoire. Il n'émet pas de lecture tant que la file d'écriture n'est pas vide. Il peut par contre émettre des écritures tant qu'elle n'est pas pleine.

Une meilleure solution serait d'interdire les lectures, mais seulement en cas de dépendance mémoire détectée. Et c'est là qu'intervient la technique du load bypassing. Elle autorise une lecture, si elle n'a aucune dépendance avec les écritures mises en attente dans la file d'écriture. 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. La lecture est exécutée immédiatement si aucune correspondance n'est trouvée, mais elle est mise en attente dans le cas contraire. Pour cela, la file d'écriture est modifiée et devient un mélange entre FIFO et mémoire associative. L'adresse à lire est envoyée à la file d'écriture, et celle-ci vérifie si une écriture est en attente à cette adresse. Si c'est le cas, c'est un succès de Write Queue : la lecture doit être bloquée. Sinon, c'est un défaut de Write Queue, la lecture accède au cache, là où se trouve la donnée à lire.

Dans le chapitre sur le contournement, nous avons parlé d'une forme de contournement qui corrige ce problème. Les lectures peuvent lire la donnée depuis la file d'écriture si besoin, ce qui renvoie la donnée adéquate. Pour cela, les lectures consultent à la fois le cache et la file d'écriture, comme dit plus haut. L'adresse à lire est envoyée à la file d'écriture, et celle-ci vérifie si une écriture est en attente à cette adresse. Si c'est le cas, c'est un succès de Write Queue, et celle-ci envoie alors la donnée associée à l'étage d'accès mémoire. Sinon, la lecture accède au cache, là où se trouve la donnée à lire. La solution porte le nom de Store to load Forwarding, ou encore de réacheminement écriture-vers-lecture.

La lecture est mise en attente dans l'unité mémoire, vu que c'est elle qui fait les comparaisons d'adresse. Du point de vue extérieur, le scoreboard mémoire ne voit pas s’il y a eu succès dans la file d'écriture ou non. Il voit juste que l'unité mémoire est occupée et ne peut pas accepter de nouvelle lecture. Elle reste occupée durant quelques cycles, en cas de défaut de Write Queue, le temps de faire la lecture dans le cache. Par contre, en cas de succès de Write Queue, elle reste occupée tant que la lecture n'a pas donné de résultat, ce qui inclue le temps de mise en attente.

Les processeurs haute performance implémentent tous le Store to load Forwarding, mais quelques processeurs basse performance ne le font pas. Ils se contentent du load bypassing, qui offre des performances correctes pour un cout en matériel bien plus modeste. Pour donner un exemple, la micro-architecture Jaguar d'AMD était dans ce cas. Elle a été utilisée sur les consoles de jeu de 8ème génération, comme la Xbox One et la Playstation 4.

Les processeurs haute performance préférent utiliser plus de circuits pour implémenter le Store to load Forwarding, mais l'implémentation n'est souvent pas complète. En effet, l'implémentation est souvent simple et ne prend en compte que des lectures/écritures à des adresses identiques, sans compter que la taille des données doit aussi être identique. Une écriture d'un entier de 32 bit sera contournée et envoyée à une lecture de 32 bits à la même adresse. Mais la lecture lit seulement 16 bits sur les 32 écrits, le contournement peut ne pas marcher. Concrètement, ce cas précis fonctionnera. Mais le cas inverse, avec une lecture lisant plusieurs écritures de taille plus petite, ne marchera pas sur tous les processeurs. Ne parlons pas du cas où les données écrites sont à cheval sur deux lignes de cache.

Le contournement des adresses mémoire avec une file de µops

Il faut noter qu'au moment où les instructions LOAD et STORE sont émises, leur adresse n'est pas forcément connue. Sauf en cas d'adressage absolu, mais mettons ce cas particulier de côté, il est assez rare en pratique. Les micro-opérations mémoire sont donc insérées dans la file de µops, mais l'adresse est souvent disponible plus tard. Il faut donc modifier le chemin de données pour que l'adresse soit envoyée à la file de µops mémoire.

Pour simplifier, étudions le cas d'un processeur où les instructions LOAD/STORE ne gèrent que l'adressage indirect à registre, à savoir que l'adresse est lue dans un registre. Les calculs d'adresse sont réalisés par une instruction de calcul séparée de l'instruction LOAD/STORE. Le cas déporte tout calcul d'adresse dans les unités de calcul entière. Le fait est que les micro-opérations mémoire ne font que des accès mémoire, pas de calcul d'adresse.

Au minimum, il doit y avoir une connexion entre le banc de registre et la file de µops mémoire, pour gérer le cas où l'adresse est déjà dans les registres quand l'instruction LOAD/STORE est émise. Cependant, il faut aussi gérer le cas où l'adresse est calculée par une instruction de calcul. L'adresse finira par être enregistrée dans les registres, mais elle est accessible avant via le réseau de contournement. Une implémentation basique n'en profite pas. Il faut alors attendre que les adresses soient enregistrées dans les registres pour être envoyées à la file de µops mémoire. Le cout en performance étant important, tous les processeurs modernes ajoutent un système de contournement qui envoie les adresses à la file de µops mémoire. L'ALU entière calcule l'adresse finale, l'envoie à la file de µops mémoire.

Maintenant, étudions le cas où les instructions LOAD/STORE gèrent les modes d'adressage indicés, ce qui signifie que le calcul d'adresse est intégré à l'instruction LOAD/STORE. L'instruction fait donc un calcul d'adresse avant l'accès mémoire proprement dit. Une solution basique utilise une micro-opération séparée pour le calcul d'adresse et l'accès mémoire. La micro-opération mémoire est envoyée à la file de µops mémoire, le calcul d'adresse est une opération arithmétique qui envoie son résultat à la file de µops mémoire, sans l'enregistrer dans les registres.

Le fait que le calcul d'adresse n'enregistre pas son résultat dans les registres est une source d'optimisation assez intéressante. Sans optimisation particulière, les calculs d'adresse sont réalisés par les ALU entières, le processeur n'est pas modifié et reste le même que celui du schéma précédent. Mais une autre solution utilise des ALU spécialisées dans les calculs d'adresse, appelées des Adress Generation Unit, abrévié AGU. L'avantage est que cela simplifie grandement le réseau de contournement. Seules les AGU sont connectées à la file de µops mémoire. Un autre avantage est lié à l'adressage de la destination. En utilisant des opérations entières usuelles, il faudrait préciser que le résultat est à destination de la file de µops mémoire, pour configurer le réseau de contournement. Avec des AGU, les calculs d'adresse sont des micro-opérations différentes des additions et soustraction, elles sont envoyées au AGU spécifiquement, pas besoin d'adresser la file de µops.

Lors de l'émission, la micro-opération mémoire est insérée dans la file de µops mémoire, l'opération de calcul d'adresse est émise dans la fenêtre d'instruction. Et les deux sont exécutés différemment. En effet, un calcul d'adresse est une opération arithmétique, qui est gérée par le système d'exécution dans le désordre. Elle peut s'exécuter dès que ses opérandes sont disponibles. À l'inverse de l'accès mémoire, qui lui doit se faire dans l'ordre du programme. Les adresses sont donc calculées en avance, puis insérées dans la file de µops mémoire. La µops de calcul d'adresse précise où enregistrer son résultat, le résultat est enregistré dans la bonne entrée de la file de µops mémoire.

Les techniques précédentes décodent une instruction LOAD/STORE en deux micro-opérations. Mais il est possible de la décoder en une seule. Le calcul d'adresse est alors réalisé dans l'unité mémoire. Les opérandes du calcul d'adresse sont lues depuis les registres lorsque l'instruction quitte la file de µops mémoire, du moins pour les opérandes qui n'ont pas été contournées. Là, elles sont envoyées à l'unité mémoire, qui fait le calcul d'adresse. Dans les faits, aucun processeur commercial moderne n'utilise cette technique.

Le Load Ordering, Store Ordering

Intuitivement, on dit qu'exécuter des µops mémoire dans le désordre demande de remplacer la file de µops mémoire par une fenêtre d'instruction. Et si c'est en effet une solution intéressante, nous n'allons pas la voir toute de suite. Nous allons étudier le cas où cette file deµops mémoire est scindée en deux : une file pour les lectures et une autre pour les écritures.

Les files de µops LOAD et STORE

Dans le chapitre sur l'exécution dans le désordre, nous avons vu deux possibilités pour implémenter l'exécution dans le désordre. La première utilise une fenêtre d'instruction ou une station de réservation, l'autre utilise plusieurs files de µops séparées. Et cette technique peut parfaitement s'utiliser pour les micro-opérations mémoire. Les micro-opérations mémoire sont réparties dans deux files de µops mémoire séparées, chacun émettant des micro-opérations indépendamment de l'autre. Mais comment répartir les micro-opérations mémoire dans deux files, simplement et sans que cela pose des problèmes de dépendances de données ? La réponse à ces contraintes est toute simple : on utilise une file de µops spécialisée pour les lectures, et une autre pour les écritures.

Les cours d'architecture des ordinateurs nomment souvent ces deux files en utilisant les termes de file de STORE (store queue) et de file de LOAD (load queue). Dans ce qui suit, nous parlerons de file de µops LOAD et de file de µops STORE, pour bien préciser qu'il s'agit de file de µops. La file de STORE ne doit pas être confondue avec la file d'écriture, qui est appelée write queue en anglais. Les termes store queue et write queue désignent deux choses différentes, mais il y a un risque de confusion pour qui n'est pas assez attentif. D'autant plus que la méthode que nous allons voir a une file d'écriture en plus des deux files de µops mémoire.

En effet, la file d'écriture ne mémorise pas des micro-opérations, juste des écritures déjà émises et en attente. Une entrée dans la file d'écriture contient une adresse et la donnée à écrire. Alors que dans la file de µops STORE, il se peut que l'adresse ou la donnée soient manquantes, car pas encore disponibles. De plus, la file d'écriture met en attente des écritures tant que les instructions précédentes ne sont pas terminées, alors que la file de µops STORE met en attente les micro-opérations avant leur émission. La première attend le feu vert de l'étage de Writeback, l'autre attend le feu vert de l'étage de schedule, d'un scoreboard amélioré.

Les deux files sont chacune connectées à l'unité mémoire, via un port dédié. L'unité mémoire a donc un port pour les lectures, et un port pour les écritures. Le port d'écriture est relié à la file d'écriture, le port de lecture est directement relié au cache de données. il faut noter qu'une unité mémoire à deux ports n'est pas si bizarre que cela. En effet, le cache de données a lui aussi deux ports, dans la majorité des cas, avec un port de lecture et un port d'écriture.

Le fait de séparer lectures et écriture a de nombreux avantages. Le premier est qu'une file de µops mémoire unique gâche des transistors. Une écriture a besoin de mémoriser une adresse et une donnée, avec les bits de validité pour les deux. Une lecture n'a besoin que d'une adresse et du bit de validité associé. Avec une file de µops unique, chaque entrée de la file est suffisamment large pour contenir une écriture. Si elle ne contient qu'une lecture, elle est trop large, ce qui sous-utilise les circuits de la file. Avec des files de lecture/écriture séparées, on n'a pas ce problème, chaque file contient juste ce qu'il faut. Il y a donc une économie de transistors.

Cependant, le système est moins flexible. Par exemple, prenons une file de µops mémoire unique, de 16 entrées. Elle peut mémoriser indifféremment 16 lectures, 16 écritures, ou n'importe quel mix d'écriture et de lectures tant qu'il se limite à 16 µops. Avec des files séparées, ce n'est plus le cas. Prenons par exemple le cas avec une file de µops LOAD de 10 éléments et une file de µops STORE de même capacité : impossible d'avoir 16 écritures en attente. Cependant, ce désavantage est quelque peu compensé par l'économie de transistor mentionnée précédemment, qui est réinvestie pour agrandir les files de µops. Typiquement, on agrandit la file de µops LOAD, car les lectures sont plus fréquentes que les écritures dans la majorité des programmes. En ayant une file de µops LOAD assez conséquente, le désavantage est fortement atténué, voire disparait.

La gestion des dépendances avec des files de µops mémoire séparées

L'usage de ces deux files de µops mémoire porte le nom de Load Ordering, Store Ordering. Il est intéressant de comparer cette technique avec la précédente, qui utilisait une file de µops mémoire séparée. Avec deux files séparées, 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'aliasing le permet. Les écritures peuvent prendre de l'avance sur les lectures, ou réciproquement. Et cette avance est très utile si elle permet d'exécuter des lectures en avance. En comparaison, avec une file de µops unique, ni écritures ni lectures ne peuvent prendre de l'avance. Les performances sont donc améliorées, bien que de peu.

Néanmoins, l'avance des lectures est limitée. Prenons le cas où une lecture doit être mise en attente, car son adresse n'est pas disponible. Avec une file de µops mémoire unique, la lecture bloque toutes les micro-opérations qui suivent. Avec deux files séparées, elle bloque uniquement les lectures, pas les écritures. Les écritures qui suivent la lecture peuvent s'exécuter. Le cas avec une écriture en attente est un peu différent. Une écriture en attente bloquera les écritures suivantes. Mais elle bloquera aussi les lectures postérieures : du point de vue de ces lectures, une écriture précédente a une adresse inconnue, on ne sait pas s'il y a dépendance mémoire avec et on suppose que oui dans le doute. En clair, l'avance des lectures n'a lieu que si les adresses des écritures précédentes sont connues, déjà calculées, sans quoi on ne peut pas détecter les dépendances mémoire.

Le fait que les écritures peuvent être émises en avance fait que la détection des dépendances RAW est différent. L'idée générale reste cependant la même. Lors de l'émission, une lecture doit vérifier ses dépendances avec les écritures antérieures, une écriture doit vérifier ses dépendances avec les lectures ultérieures. Avec une file de µops unique, on est certain que les écritures antérieures sont dans la file d'écriture, dans l'unité mémoire. Et lorsqu'on émet une écriture, on est certain que les lectures ultérieures seront émises après. Avec deux files séparées, ce n'est pas forcément le cas. Si les lectures ont pris de l'avance, une écriture précédente peut être en attente dans la file de µops STORE, alors qu'une lecture ultérieure a été émise. Ce qui complique la détection des dépendances RAW d'adresse. Les détecter demande non seulement de vérifier la file d'écriture, mais aussi la file de µops STORE.

Dans ce qui suit, on suppose que l'unité mémoire incorpore une file d'écriture, ce qui est toujours le cas en pratique. Le fait que les écritures se font dans l'ordre élimine les dépendances WAW et WAR. On suppose aussi que l'unité mémoire implémente le réacheminement écriture-vers-lecture (store-to-load forwarding). Ainsi, si une lecture est émise dans l'unité mémoire, les dépendances RAW avec les écritures déjà émises ne sont pas un problème. Par contre, il faut gérer les dépendances avec les écritures en attente dans la file de µops STORE, dont certaines sont antérieures à la lecture dans l'ordre du programme. Pour cela, il n'y a pas le choix : pour chaque lecture, on vérifie dans la file de µops STORE si elle a une dépendance avec une écriture antérieure. La gestion des dépendances RAW est donc gérée partiellement dans l'unité mémoire et la file de µops STORE.

Pour l'implémenter, il faut comparer l'adresse à lire avec toutes les adresses dans la file de µops STORE. 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. Pour cela, la file de µops STORE est un mélange entre FIFO et mémoire associative. Il faut préciser que la comparaison ne prend en compte que les écritures situées avant la lecture, dans l'ordre du programme. Les deux files de µops doivent donc mémoriser des informations sur l'ordre d'émission. De plus, 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.

La file de lecture met des lectures en attente, soit car elle attend ses opérandes, soit car elle attend que les lectures précédentes soient terminées, soit car l'aliasing ne lui permet pas. Elle a cependant un défaut : celui de forcer les lectures à s’exécuter dans l'ordre, ce qui est une contrainte inutile. Mais l'avantage est que l'implémentation est très simple. Une file de micro-opération est bien plus simple à implémenter qu'une fenêtre d'instruction.

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 lectures sont mises en attente, parce qu'une lecture précédente l'est, alors qu'elles auraient pu s’exécuter avant. Et ce retard sur les lectures se répercute sur les instructions lecture-dépendantes, donc sur le reste du pipeline. Pour éviter cela, la technique du Partial Ordering permet aux lectures de s'exécuter dans le désordre tant que les conditions d'aliasing sont respectées.

La Load/Store Queue

La technique s'implémente en remplaçant les files de µops mémoire par une fenêtre d'instruction spécialisée dans les µops mémoire. Elle est souvent appelée la Load/Store Queue, qui est concrètement une station de réservation spécialisée dans les micro-opérations mémoire. En tout cas, nous utiliserons beaucoup l'abréviation LSQ pour parler de la Load/Store Queue.

Une entrée de la Load/Store Queue 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 (inutile pour les écritures). Les deux derniers champs sont souvent fusionnés en un seul, qui est interprété différemment selon que l'instruction est une lecture ou une écriture.

Lorsqu'une micro-opération mémoire est émise, après renommage de registres, elle est insérée dans la Load/Store Queue. Si l'adresse à lire/écrire est disponible, elle est immédiatement lue depuis les registres, idem pour une éventuelle donnée à écrire. Sinon, la micro-opération attend dans la LSQ que son adresse soit calculée par l'ALU entière. 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.

Il faut noter que tout ce qui a été dit plus haut à propos du contournement des adresses vaut aussi avec une Load/Store Queue, à un détail près. Pour détecter les dépendances, la LSQ doit comparer les adresses à lire/écrire, ce qui fait qu'elles doivent avoir été calculées avant d'entrer dans la LSQ. En clair, il n'est pas possible de faire les calculs d'adresse dans l'unité mémoire, juste avant d’accéder au cache. Les unités de calcul d'adresse sont réalisés dans une ALU entière ou une AGU spécialisée.

Lorsqu'une instruction mémoire est émise, elle est décodée en deux micro-opérations : une pour le calcul d'adresse, une autre pour l'accès mémoire proprement dit. Le calcul d'adresse est réalisé soit dans une ALU entière, soit dans une AGU spécialisée. L'accès mémoire attend dans la Load/Store Queue que l'adresse soit calculée. Une fois l'adresse calculée, elle est envoyée à la Load/Store Queue et est enregistrée dans l'entrée adéquate. Reste qu'il faut envoyer l'adresse des ALU à la LSQ. Pour cela, on réutilise le réseau de contournement du processeur.

L'implémentation la plus simple effectue les calculs d'adresse dans les ALU entières. La sortie de toutes les ALU entière est reliée à la LSQ.

Les processeurs modernes préfèrent utiliser des unités de calcul d'adresse dédiées, afin de simplifier le réseau de contournement.

La détection des dépendances mémoire

La Load/Store Queue est couplée à un système de détection des dépendances mémoire, qui détermine quelles instructions peuvent s'exécuter sans problème. Et ce système de détection des dépendances est bien différent de celui d'une station de réservation normale. Les Load/Store Queue comparent non pas des noms de registres, mais des adresses/opérandes. Chaque micro-opération en attente compare son adresse avec celle de toutes les micro-opérations précédentes. Ou presque, la comparaison ne doit tenir compte que des écritures, et de celles situées avant dans l'ordre du programme. La Load/Store Queue doit donc mémoriser les instructions dans l'ordre du programme, tout en faisant des comparaisons d'adresse. Ça en fait une sorte hybride entre mémoire associative et mémoire FIFO.

Nous avions vu dans le chapitre "L'exécution dans le désordre" qu'il y a plusieurs manières pour implémenter une station de réservation : avec une mémoire associative, avec préplanification, avec des matrices de dépendances. Le problème est qu'on ne peut pas utiliser une mémoire associative pour la LSQ, qui utilise des comparateurs pour comparer les noms de registres/adresses. En effet, la détection des dépendances mémoire demande de faire beaucoup de comparaisons : chaque adresse est comparé à toutes les autres. Et les adresses faisant facilement 32 à 64 bits, les comparateurs sont bien plus imposants que ceux qui comparent des noms de registres de 5-10 bits. Le cout en matériel serait trop élevé, de même que le temps de calcul des dépendances. À la place, on utilise des matrices de dépendances.

La détection des dépendances mémoire utilise précisément 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'un 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é.

Une optimisation scinde la Load/Store Queue en deux structures, aux rôles légèrement différents. La première gère la disponibilité des opérandes, la seconde gère seulement les dépendances mémoire. La première est une station de réservation où les instructions sont mises en attente tant que leurs opérandes ne sont pas prêts. La seconde met en attente des micro-opérations dont les opérandes sont prêts, mais qui doivent attendre pour une autre raison : dépendance mémoire, cache occupé, etc.

L'avantage est qu'on remplace une grosse station de réservation par deux plus petites, mais l'intérêt est surtout relié au système de détection des dépendances. Sans cette optimisation, on a deux matrices énormes reliées à une Load/Store Queue unique. Avec la séparation, la matrice de disponibilité est reliée uniquement à la première station de réservation, alors que la matrice de dépendance est reliée uniquement à l'autre. Les deux matrices sont donc plus petites, car reliées à deux stations de réservation mémoire plus petites.

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

Pour rappel, le but de la désambiguïsation mémoire est d'exécuter les lectures le plus tôt possible. Les données lues sont en effet, le départ d'une série d'instructions dépendantes, généralement des instructions arithmétiques, mais parfois d'autres lectures. Quand on manipule des structures de données, il n'est pas rare qu'une lecture lise un pointeur-adresse utilisé par une autre lecture.

Les techniques de désambiguïsation mémoire que nous avons vu précédemment sont dites conservatrices, à savoir qu'elles ne changent pas l'ordre de deux instructions mémoire si elles ont une dépendance d'adresse. Elles exécutent une lecture le plus tôt possible, mais seulement si on sait que celle-ci n'aliase pas d'écritures précédentes. Et cela demande de connaitre les adresses des écritures précédentes dans l'ordre du programme. Si une lecture est précédée par une ou plusieurs écritures, les adresses à écrire doivent être connues. Il se peut en effet qu’une écriture dont on ne connait pas l'adresse aliase la lecture. La garantie est liée à la présence de la file de µops mémoire ou la file de µops STORE. Si une seule écriture a une adresse inconnue, elle reste dans la file de µops mémoire et bloque l'émission de toutes les autres micro-opérations mémoire, lecture comme écriture.

Mais il existe des techniques dites spéculatives, qui modifient l'ordre des accès mémoire sans se soucier de leurs dépendances. Elles émettent les lectures dès que leurs opérandes sont prêts, sans se préoccuper de l'aliasing avec une écriture précédente. Pour éviter tout problème, le processeur 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, 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. Il s'agit d'un cas particulier d’exécution spéculative, au même titre que la prédiction de branchement.

Toutes les techniques de ce genre exécutent des lectures dans le désordre. L'avantage est que cela permet d'exécuter les lectures en avance. Vu que la donnée lue est l'opérande d'autres instructions, 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. En termes de cout en transistors, 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.

La file de lectures

La première technique que nous allons voir reprend la technique du Load Ordering, Store Ordering, avec ses deux files de µops de lecture et d'écriture. Elle exécute les lectures sans se préoccuper des dépendances avec les écritures. Mais le processeur vérifie qu'aucune violation de dépendance n'a eu lieu après un certain temps. Une violation de dépendance peut avoir lieu pour n'importe quelle instruction précédant la lecture dans l'ordre du programme. En clair, le processeur doit conserver les lectures spéculatives tant que les instructions précédentes ne sont pas terminées. Pour cela, il faut ajouter une nouvelle file d'attente, qui mémorise les lectures terminées. Nous l’appellerons la file de vérification des lectures, ou encore la file de lectures.

Elle fonctionne sur le même principe que la file d'écriture et les deux font partie de l'unité mémoire. Les deux visent à remettre les lectures/écritures dans l'ordre du programme, afin que les instructions suivant une lecture/écriture fautive soient annulées. Les lectures sont insérées dans la file de lecture à l'émission, quand elles quittent la file de µops mémoire/LSQ, ce qui est la même chose avec les écritures pour la file d'écriture. Une différence très importante est que les écritures sont retardées alors que les lectures s'exécutent immédiatement. D'ailleurs, la file de lecture ne sert pas pour le contournement : les données lues sont immédiatement envoyées au chemin de données, pas besoin de les contourner ultérieurement. Alors que la file d'écriture est utilisée pour le contournement en cas de dépendances RAW.

Les lectures sortent de la file µops LOAD dès que leurs adresses sont calculées, sans tenir compte des dépendances mémoires. Elles sont alors ajoutées à la file de lectures et s'exécutent immédiatement, de manière spéculative. 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 lectures. Les lectures quittent la file de lecture quand toutes les instructions précédentes dans l'ordre du programme sont terminées, à savoir tant quand elles ont quitté le tampon de réordonnancement/ROB. Notons que la file de vérification des lectures contient les lectures dans l'ordre du programme. En effet, les lectures sont accumulées en sortant de la file de µops LOAD, où elles sont triées dans l'ordre du programme. Et cela permet de gérer les erreurs de prédiction parfaitement, en annulant les instructions suivant une erreur de prédiction.

Reste à détecter les erreurs de prédiction, ce qui peut être fait avec deux méthodes.

Avec la première, les violations de dépendances mémoire sont faites à chaque écriture. Précisément, la détection a lieu quand 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 s’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 après l'écriture dans l'ordre du programme (seulement ces instructions sont capables de générer une dépendance RAW).

Avec la seconde méthode, les violations de dépendance mémoire sont détectées au moment où la lecture quitte à la file de lectures et le ROB. Mais cela demande que la donnée lue soit recopiée dans la file de lecture. Quand 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 mémorisée dans la file de lecture. 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.

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.

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

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

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

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

La prédiction d'adresse et de valeur

D'autres techniques de prédiction mémoire plus élaborées que les précédentes existent. Il s'agit de la prédiction d'adresse et de la prédiction de valeur. Leur nom trahit ce qu'elles font. La première technique tente de prédire l'adresse d'une lecture/écriture, alors que la seconde tente carrément de prédire quelle sera la donnée lue.

Il y a bien de la recherche académique sur le sujet, mais il s'agit de techniques assez osées, dont on voit mal comment elles pourraient fonctionner. L'efficacité de cette technique a été étudiée grâce à des simulateurs. Suivant les études ou les programmes, on trouve des résultats qui varient pas mal. Dans certains cas, la performance baisse un peu, et dans d'autres, on peut avoir des gains de plus de 10% ! Mais dans des cas normaux, on trouve des gains de 4-5% environ. Ce qui est tout de même pas mal à l'heure actuelle.

Cependant, en Janvier 2025, à l'heure où j'écris ces lignes, il a été découvert la première utilisation de ces deux techniques dans un processeur commercial. La découverte fait suite à la publication de deux vulnérabilités matérielles sur les CPU Apple M2 et M4 et quelques CPU ARM, qui font justement usage de ces deux techniques. Les deux vulnérabilités, appelées SLAP et FLOP, sont assez similaires aux attaques Spectre et Meltdown, sauf qu'elles attaquent non pas la prédiction de branchement, mais la prédiction d'adresse et de valeur du CPU.

La prédiction d'adresse

La prédiction d'adresse tente de prédire l'adresse d'une lecture à l'avance, ce qui permet de lancer les lectures en avance. Si la prédiction est correcte, on gagne quelques cycles qui permet aux unités de calcul de faire leurs calculs plus en avance, sans compter que les mécanismes de désambiguïsation mémoire fonctionnent plus efficacement. Si jamais cette adresse est connue plus tôt, on détecte les dépendances plus rapidement et on peut agir en conséquence.

Des variantes de ces unités de prédiction d'adresse sont utilisées pour précharger des données depuis le cache de donnée. Et leur efficacité est assez bonne, voire excellente dans certains cas. La différence est que la prédiction d'adresse est utilisée pour prédire les adresses à lire depuis le cache vers les registres, ce qui est le sujet de cette sous-partie.

La prédiction d'adresse est réalisée par une sorte de cache, qui associe à chaque instruction la prochaine adresse à lire. Nous appellerons ce cache la table de prédiction d'adresse. Pour faire l'association instruction <-> adresse lue/écrite, le tag du cache utilise l'adresse de l'instruction (le program Counter), alors que la ligne de cache associée contient l'adresse prédite. Son contenu est utilisé pour faire une prédiction. Lorsqu'une lecture est émise, la table est consultée pour récupérer en avance l'adresse à lire, avant que celle-ci soit calculée par l'ALU. La lecture est alors exécutée en avance, avant que la vraie adresse soit connue, en utilisant l'adresse prédite.

Reste qu'il faut des circuits autour de cette table de prédiction d'adresse, pour déterminer si la prédiction est correcte, ainsi que pour remplir cette table avec une adresse prédite. Pour cela, il y a un circuit de prédiction d'adresse dédié. Il récupère les instructions qui quittent le ROB ou la file des lectures mémoire, afin de vérifier les lectures qui viennent de se terminer/commit et qui quittent le pipeline. Il peut contenir une table d'apprentissage, qui mémorise des informations nécessaires pour faire des prédictions d'adresse. Par exemple, un historique des dernières adresses lues pour les lectures les plus récentes, ou un historique des adresses des lectures. La table est aussi utilisée pour déterminer si les prédictions effectuées étaient correctes ou non. Pour cela, il est possible de réutiliser les techniques vues dans le chapitre sur la prédiction de branchement, notamment des compteurs à saturation.

Pour la prédiction de branchement et les autres formes de prédiction mémoire, les table d'apprentissage et pour les instructions/adresses sont fusionnées en une seule. Mais ici, il est nécessaire de les séparer pour une raison assez particulière : éliminer la pollution du cache dans la table de prédiction d'adresse. On ne peut pas allouer une ligne de cache pour chaque nouvelle instruction de lecture exécutée. Seule une minorité des lectures profitent de la prédiction d'adresse. Il est nécessaire de filtrer les lectures pour ne conserver que celles qui profitent de la prédiction d'adresse, ce qui est possible plus facilement en séparant la table d'apprentissage et les compteurs à saturation de la table de prédiction d'adresse.

Une première méthode consiste à prédire que la lecture lit toujours la même adresse, ce qui lui vaut le nom de prédiction d'adresse constante. On pourrait se demander pourquoi une telle situation surviendrait. La raison est qu'il arrive que les compilateurs n'arrivent pas à gérer les accès mémoires efficacement. Dans certaines situations un peu compliquées impliquant des pointeurs ou des références, divers phénomènes complexes d'aliasing des pointeurs peuvent générer des relectures intempestives de données en mémoire. Cela peut aussi arriver lorsqu'on compile du code qui provient de plusieurs librairies, ou quand du code lit régulièrement des constantes en mémoire ROM.

La prédiction d'adresse constante ajoute un circuit qui analyse les dernières lectures, une fois qu'elles quittent le ROB, qu'elles commit. Si, pour une instruction de lecture, l'adresse lue est toujours la même, alors l'instruction est ajoutée dans la table de prédiction d'adresse. Vu que les instructions qui accèdent toujours à la même adresse sont rares, il est préférable d'initialiser les compteurs à saturation de façon à ce qu'ils disent que toute nouvelle instruction change d'adresse. Il s'agit d'une méthode simple mais peu efficace, car cette situation est rare.

Une autre méthode détecte les accès en enjambées, là encore quand les lectures quittent le ROB. Nous l’appellerons la prédiction d'adresse en enjambées. De tels accès surviennent régulièrement quand on accède des tableaux ou d'autres structures de données semblables, ce qui rend la technique très intéressante. Implémenter cette technique est facile : il suffit d'ajouter un circuit qui détecte les accès en enjambées, au lieu de celui qui détecte les accès constants. À chaque fois qu'une lecture entraine un succès de cache dans la table de prédiction d'adresse, l'enjambée est ajoutée à l'adresse contenue dans la table de prédiction d'adresse, l'ancienne adresse prédite est remplacée par celle avec l'enjambée d'ajoutée.

Sur les Apple M2-M4, la prédiction d'adresse gére aussi bien les adresses constantes que les accès en enjambée. Le brevet qui décrit l'implémentation de l'unité de prédiction d'adresse et de valeur est potentiellement le suivant : Early load execution via constant address and stride prediction. En théorie, il est possible de faire mieux en repérant des accès mémoires qui se répètent de façon régulière et cyclique, même s'ils n'ont aucune enjambée. Ce genre d'accès se trouve assez souvent lorsque l'on manipule des listes chainées ou des structures de données assez irrégulières comme des arbres, des graphes, etc. Mais il n'y a pas encore de CPU qui implémente de telle optimisation.

La prédiction de valeur : prédire la donnée lue

Les techniques de prédiction de valeur (Value Prediction) consistent à prédire quelle est la donnée qui sera lue par une instruction de lecture. Oui, vous avez bien lu : le processeur est capable de parier sur la valeur qui sera chargée depuis la mémoire, de prédire si cette valeur vaut 0, 1, 1024, etc. Une fois son pari fait, il exécute les instructions du programme avec la valeur qu'il a pariée de façon spéculative. Si le pari est correct, le CPU continue l’exécution. Sinon, il est obligé de vider le pipeline et de recommencer avec la bonne valeur.

Au premier abord, cette technique semble franchement mal partie tellement les chances de se tromper sont tellement énormes ! Mais le fait est que, dans certains cas, il est possible de spéculer correctement. Là encore, les techniques les plus simples fonctionnent dans deux cas. Le premier est celui où une donnée est relue à l'identique à chaque fois que la lecture est exécutée. Le second est celui où la donnée est incrémentée/décrémentée d'une constante qui est toujours la même d'une exécution de la lecture à l'autre. Une sorte d'enjambée constante, mais pour les données.

Nous allons nous concentrer sur le premier cas, celui où une donnée est relue plusieurs fois sans être modifiée entre temps. L'idée de base est qu'une instruction de lecture qui s'exécute plusieurs fois de suite à la même adresse renvoie la même valeur à chaque fois. C'est parfaitement possible s’il n'y a eu aucune écriture à cette adresse entre-temps, d'où le fait qu'il faille surveiller si les prédictions constantes sont correctes.

On peut se demander quelles sont les raisons qui font qu'une instruction de lecture renvoie la même valeur à chaque fois. Après tout, autant lire une seule fois la donnée et la garder dans un registre une bonne fois pour toutes ! Mais dans la réalité, on fait face à quelques limites, qui seront détaillées dans la liste suivante. La première est que le manque de registre fait que certaines données sont conservées en RAM et sont relues fréquemment. Cela arrive quand on stocke des constantes en mémoire. Par exemple, sur les processeurs x86, les constantes flottantes ne peuvent pas être intégrées dans nos instructions via le mode d'adressage immédiat. À la place, on les stocke en mémoire et on les charge dans les registres à chaque fois qu'on en a besoin.

L'implémentation est similaire à la prédiction d'adresse, si ce n'est que c'est la donnée lue qui est prédite. Là encore, on a une table de prédiction de donnée lue, consultée lorsqu'une lecture est émise. La table de prédiction de la donnée lue est une mémoire cache qui associe le Program Counter de la lecture à la donnée prédite, éventuellement couplé à des compteurs à saturation. Elle est consultée à chaque fois qu'une lecture est émise, la donnée adéquate est récupérée lors d'un succès de cache. On trouve aussi un circuit qui insère ou retire des instructions de la table de prédiction de donnée lue. Elle détecte les lectures prédictibles, couplé à une table d’apprentissage, et quelques circuits annexes liés au ROB ou aux files de lectures. Elle contient au minimum des compteurs à saturations, associés chacun à une instruction (son program counter pour être précis).

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

Un autre exemple : les techniques de prédiction d'adresse et de valeur posent des problèmes avec les dépendances RAW. Elles permettent à une instruction mémoire de s'exécuter avant une autre, malgré la présence d'une dépendance RAW entre les deux. L'ordre entre les deux instructions change, alors que les autres processeurs ne devraient pas le voir. Et dans les faits, les processeurs qui incorporent ces techniques ont des modèles de consistance mémoire qui ne permettent pas ces optimisations en cas de dépendances RAW. Les deux techniques doivent idéalement être désactivées pour les instructions mémoire qui ont des dépendances RAW.

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.

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 écritures 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 dû ê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 dites 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 exceptionnel : 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.

◄ Retour vers « Le scoreboarding et l'algorithme de Tomasulo »

Sommaire du livre

Continuer vers « Le parallélisme mémoire au niveau du cache » ►