Fonctionnement d'un ordinateur/Le Translation Lookaside Buffer

Dans le chapitre sur la mémoire virtuelle, nous avions abordé la pagination. Nous avions vu que la traduction des adresses virtuelles en adresses physiques se fait grâce à une table des pages située en mémoire RAM, qui contient les correspondances entre adresses physiques et virtuelles. Pour éviter d'avoir à lire la table des pages en mémoire RAM à chaque accès mémoire, les concepteurs de processeurs ont décidé d'implanter un cache dédié, le translation lookaside buffer, ou TLB. Il stocke de quoi faire la traduction entre adresse virtuelle et adresse physique, à savoir une correspondance entre numéro de page logique et numéro de page physique.

MMU avec une TLB.

Si elles ont quelques spécificités, qui leur valent un chapitré dédié dans ce cours, les TLB n'en restent pas moins des caches tout ce qu'il y a de plus normaux. Leur conception interne est presque identique à celle d'un cache normal, leurs performances sont influencées par les mêmes paramètres. Tout ce qu'on a vu sur les caches dans le chapitre dédié s'applique aussi aux TLB. Les caches consomment beaucoup d'énergie et la TLB ne fait pas exception. Diverses estimations montrent que les TLB sont très consommatrices en énergie. Près de 5 à 15% de la consommation d'énergie d'un processeur provient de sa TLB et des circuits associés. Pour réduire cette consommation tout en gardant des performances très importantes, la TLB est conçue avec ces contraintes en tête. Notamment, la TLB est généralement un cache associatif par voie ou directement adressé, et non un cache totalement associatif. Le cout en énergie des caches totalement associatifs ne vaut pas les performances gagnées, pour une LTB.

Pour des raisons de performances, la TLB est parfois découpée en plusieurs sous-caches L1, L2, L3, etc. Sur les architectures Harvard et Harvard modifiées, on trouve parfois deux TLB séparés : un pour les accès aux instructions, et un pour les accès aux données. L'architecture standard pour les TLBs actuelles est la suivante : une TLB de niveau 1 pour les instructions, une autre TLB de niveau 1 pour les données, puis une TLB de niveaux 2 partagée entre instructions et données. La séparation en une TLB L1 pour les instructions et une pour les données est nécessaire sur les architectures à hautes performances. Les processeurs modernes peuvent exécuter plusieurs instructions simultanément, ce qui fait qu'ils accèdent souvent à des données en même temps qu'ils chargent une ou plusieurs instructions. Une TLB unique devrait gérer plusieurs dizaines d'accès en même temps pour alimenter le processeur en données/instructions. La TLB doit alors être une mémoire multiports avec beaucoup de ports, beaucoup trop de ports pour être performante. Utiliser deux TLB séparées élimine ce problème, en limitant le nombre de ports sur chaque TLB. Un autre problème est que le programme prend moins de place que les données, ce qui se marie mal avec une TLB unique mais colle assez bien avec une TLB d'instruction plus petite que celle pour les données.

Hiérarchie de TLB.

L'accès à la TLB : succès et défauts d'accès

À chaque accès mémoire, le processeur vérifie si le TLB contient l'adresse physique à laquelle accéder. Si c'est le cas, le processeur n'a pas à accéder à la table des pages en mémoire RAM et lit directement l'information nécessaire depuis ce TLB. On dit que l'on a un succès d'accès à la TLB. Si la TLb ne contient pas l'adresse physique demandée, on fait face à un défaut d'accès à la TLB. L'accès à la table des pages en mémoire RAM est alors inévitable.

La traduction d'adresse avec la TLB

Page table actions

La traduction d'une adresse avec une TLB a lieu comme suit. Premièrement, le processeur (sa MMU) interroge la TLB : il envoie l'adresse virtuelle et la TLB répond. Si la TLB contient l'adresse physique associée, elle la fournit directement et le processeur au cache ou à la RAM directement. Si ce n'est pas le cas, le processeur accède à la table des pages en mémoire RAM. Si la page est en RAM, alors la table des pages renvoie l'adresse physique voulue et la TLB est mise à jour. Par contre, si la page n'est pas en RAM, mais a été swappée sur le disque dur, la page est recopiée en mémoire RAM, la table des pages est mise à jour, puis la TLB l'est ensuite.

Steps In a Translation Lookaside Buffer

Les page table walkers

Les défauts d'accès à la TLB sont gérés de deux façons : soit le processeur gère tout seul la situation, soit il délègue cette tâche au système d’exploitation. Sur les processeurs anciens, le système d'exploitation gère le défaut d'accès à la TLB. En cas de défaut, le processeur lève une exception matérielle spécialisée, qui exécute une routine d'interruption qui accède à la table des pages en RAM et effectue la traduction d'adresse. Mais cette solution logicielle n'a pas de bonnes performances. D'autres processeurs gèrent eux-mêmes le défaut d'accès à la TLB et vont chercher d'eux-mêmes les informations nécessaires dans la table des pages. Ils disposent de circuits, les page table walkers (PTW), qui s'occupent eux-mêmes du défaut.

L'avantage en termes de performance est certain : plus besoin de lever une exception matérielle, plus besoin de lever une interruption couteuse à chaque défaut de TLB. Un autre avantage est que la gestion des bits de statut, qui mémorisent des informations sur chaque page, est gérée par le PTW. Sur les processeurs superscalaires à exécution dans le désordre qu'on abordera dans quelques chapitres, les PWT peuvent gérer un défaut de TLB pendant que le processeur fait d'autres opérations en parallèle, ce que ne permet pas la solution logicielle. Mieux : les PWT et TLB modernes sont conçus pour gérer plusieurs défauts simultanés, ce qui permet de grandement gagner en performance par rapport à l'approche logicielle. Le défaut principal des PWT est qu'ils sont conçus pour un format bien précis de table des pages, éventuellement deux ou trois autres, mais guère plus. Il est rare qu'ils gèrent plusieurs types de tables des pages différents. Leur flexibilité est donc assez faible. En comparaison, la solution logicielle n'a pas de limites précises, tant que le système d'exploitation gère le format de table des pages voulu.

Les PTW sont généralement implémentés avec des circuits séquentiels spécifiques, nommés machines à état. Ils ont besoin, pour faire leur travail, de mémoriser l'adresse de la table des pages, ou du moins l'adresse de la table des pages de niveau 1 pour des tables des pages hiérarchiques. L'adresse de la table des pages est mémorisée dans un registre spécialisé, manipulé seulement par le système d'exploitation. Les informations nécessaires pour gérer chaque défaut de TLB sont stockées dans des registres spécialisés appelés des tampons de PTW (PTW buffers). Sur les architectures à plusieurs processeurs, chaque cœur ou processeur a son propre PTW.

Dans le cas le plus simple, la table des pages est une table des pages simple, unique, qui contient des numéros de page physique. Le PTW a juste besoin de calculer une adresse et de faire une lecture pour récupérer le numéro de page physique. Dans le cas où la table des pages est hiérarchique, le processus doit être répété plusieurs fois, autant de fois qu'il faut passer d'une table des pages à la suivante. Dans le cas d'une table des pages inversée, le PTW doit parcourir automatiquement la mémoire pour lire chaque entrée de la table des pages une par une, faire une comparaison pour détecter la bonne entrée, puis déclencher une lecture une fois la bonne entrée détectée. Le processus est donc simple sur une table des pages unique, mais plus complexe dans les autres cas. La difficulté est de parcourir la mémoire. Pour le cas des pages des tables inversées, parcourir la mémoire en lisant des adresses consécutives est simple : un simple compteur d'adresse suffit. Par contre, le processus est plus complexe pour les tables des pages hiérarchiques, et demande généralement une implémentation avec du microcode. Le PWT communique alors avec le séquenceur pour lui demander d’exécuter une suite d’instructions microcodée pour gérer le défaut.

Les Page walk caches

Pour accélérer le parcours des tables des pages hiérarchiques, l'unité de gestion mémoire (la MMU) des processeurs modernes incorpore des caches spécialisés, appelés des MMU caches ou encore caches de la MMU en français. Ils sont systématiquement utilisés en complément d'une TLB. La différence principale entre TLB et cache de la MMU tient dans leur contenu. Les TLB stockent des correspondances adresse logique-physique obtenues une fois qu'on a parcouru l'ensemble des niveaux d'une table des pages à la recherche d'une adresse physique précise, elles stockent le résultat de la traduction d'adresse. Les caches de la MMU, quant à eux, mémorisent non pas le résultat final, mais les résultats des étapes intermédiaires. Elles mémorisent les entrées de la table des pages accédées lors des défauts de TLB les plus récents, qui ne sont pas déjà dans la TLB. Ils stockent les entrées de la table de niveau 1 ou les autres tables des pages de niveau supérieur, mais pas les entrées qui contiennent un numéro de page physique.

Cette différence de contenu se traduit par de nombreuses différences pratiques. La première est que la taille des lignes de cache n'est pas la même. Les TLB prennent un numéro de page logique et renvoient un numéro de page physique, les deux ayant la même taille. Les caches de la MMU prennent en entrée des numéros de page logique ou des morceaux de celle-ci (tout dépend de sa conception, comme on le verra plus bas), mais fournissent en sortie une adresse mémoire complète. La différence de taille entre numéro de page physique et adresse complète fait que la sortie d'une TLB et d'un cache de MMU n'a pas la même taille. Même chose pour les entrées, mais à un degré moindre. L'usage qui est fait par la MMU de la sortie du cache est aussi très différent, au vu de la nature différente des données stockées.

Les caches de la MMU sont très utiles, car les accès mémoires ont une bonne localité spatiale, ce qui fait que des accès consécutifs ont des chances d’accéder aux mêmes entrées de la table de niveau 1 et de niveau 2, voire des niveaux 3 et 4. Il faut dire que sur les ordinateurs x86 64 bits, une entrée de la table des pages de premier niveau correspond à 512 gibioctets de mémoire...

Il existe plusieurs manières de concevoir les caches de la MMU. La première est tout simplement d'associer une entrée de la table des pages avec son adresse physique, l'adresse physique servant de tag et l'entrée prenant une ligne de cache. C'est ce qui est fait sur les page walk caches des processeurs AMD. Ils se marient bien avec le fonctionnement normal du page table walker, qui génère des adresses physiques. Une autre approche associe certains bits de l'adresse virtuelle à lire/écrire avec une entrée, au lieu de l'adresse physique de l'entrée. Par exemple, les bits de poids fort qui sont utilisés pour adresser la table de premier niveau sont utilisés comme tag dans le cache de la MMU. Même chose pour les bits précédents, qui servent à adresser la table de second niveau, et ainsi de suite. C’est ce qui est fait sur les paging structure cache des processeurs Intel. Une troisième approche est celle du translation path cache.

Si on compare les page walk caches avec les paging structure cache, les page walk caches sont plus simples à fabriquer mais plus lents, alors que c'est l'inverse pour les paging structure caches. Les page walk caches sont des caches normaux, sans particularité notable si ce n'est qu'ils sont intégrés à la MMU et qu'ils stockent des entrées des tables de haut niveau de la table des pages. Ils sont donc aussi faciles à fabriquer/concevoir que n'importe quel autre cache, voire plus facile vu que les entrées sont petites et ont peu de bits à stocker. Par contre, un défaut de TLB entraine plusieurs lectures consécutives dans un page walk caches. Une première lecture pour récupérer l'entrée de la table de premier niveau, une seconde pour l'entrée adéquate de la table de second niveau, et ainsi de suite jusqu'à effectuer la lecture en mémoire. Le parcours de la table des pages s'effectue normalement, dans le même ordre que sans cache de MMU. Les paging structure cache permettent d'optimiser la recherche en sautant des étapes, ce qui rend le parcours de la table des pages beaucoup plus rapide si les entrées adéquates sont dans le cache. Les paging structure cache utilisent des tags plus petits que leurs concurrents, ce qui fait qu'ils prennent moins de place et de portes logiques à capacité égale et sont moins consommateurs en énergie.En clair, à part la simplciité de conception, les paging structure cache ont de meilleures performances pour un budget en circuits et énergie plus faible.

Il est possible d'utiliser un seul cache, qui mémorise les entrées des différents niveaux de la table des pages. Une autre possibilité est d'utiliser un cache pour chaque niveau de la table des pages. On a ainsi un cache pour la table de niveau 1, un autre pour les tables de niveau 2, etc. Faire ainsi facilite l'implémentation du remplacement des lignes de cache et améliore son efficacité. Un autre avantage est qu'il est plus facile de gérer plusieurs défauts simultanés. On peut accéder au cache pour la table de premier niveau en même temps qu'au cache pour les tables de second niveau, et idem pour les autres caches.

Les pages larges et leur impact sur la TLB

Les processeurs actuels gèrent plusieurs tailles différentes pour les pages : 4 kibioctets par défaut, 2 mébioctets, voire 1 à 4 gibioctets pour les pages les plus larges. Les pages larges ont l'avantage d'utiliser la TLB de manière optimale. Pour une capacité de TLB identique, on peut adresser beaucoup plus de mémoire avec des pages larges, ce qui rend les défauts de TLB plus rares. Par contre, ces différentes tailles se marient mal avec une TLB unique. Un des problèmes est que les numéros de page physique n'ont pas le même nombre de bits suivant la taille des pages, ce qui pose des problèmes avec l'associativité de la TLB. Ce problème fait que l'usage d'une TLB unique est possible, mais pas forcément optimal.

L'usage de plusieurs TLB, chacune dédiée à une taille de page

L'usage d'une TLB unique pour toutes les tailles de page est possible et même courant pour la TLB de niveau 2 (L2). Mais les TLB de niveau 1 sont souvent séparées en plusieurs TLB, une par taille de page possible. Les TLB pour les pages larges sont souvent plus petites que la TLB pour les pages de 4 kibioctets, afin de profiter des économies de TLB liées aux pages larges. Un problème est que la taille de la page n'est connue du processeur qu'une fois la traduction d'adresse terminée, réalisée par la TLB. Pour résoudre ce problème, toutes les TLB L1 sont accédées en parallèle lors d'un accès mémoire et le processeur sélectionne ensuite le résultat de celle qui correspond à la taille de page voulue.

TLB pour plusieurs tailles de page

L'usage d'une TLB unique pour toutes les tailles de page

Les TLB de niveau 2 gèrent plusieurs tailles de page en même temps. Mais les techniques pour faire cela sont assez couteuses en circuits et en performances. Aussi, les techniques utilisées pour gérer plusieurs tailles de page sont couramment implémentées sur les TLB de niveau 2, mais sont impraticables sur les TLB de niveau 1. Les deux techniques qui permettent cela sont appelées le hash-rehashing et le skewing. Elles répondent à un problème assez simple à 'expliquer : la taille de la page n'est connue du processeur qu'une fois la traduction d'adresse terminée, réalisée par la TLB. On doit accéder à la TLB en postulant que la page a une certaine taille, donc en précisant un numéro de page d'une certaine taille, pour ensuite avoir un défaut ou un succès de TLB.

Le hash-rehashing

La première technique, celle du hash-rehashing, consiste simplement à accéder la TLB en supposant que la page voulue a la taille usuelle, à savoir 4 kibioctets. En cas de succès de TLB, la page avait bien la taille supposée. Dans le cas contraire, on effectue un second accès en supposant que sa taille est de 2 mébioctets, et rebelote pour une page de 1-2 gibioctets en cas de défaut de TLB. Une fois toutes les tailles essayées, on accède à la table des pages en mémoire RAM. C'était la technique utilisée sur les processeurs Intel d’architecture Skylake et Broadwell. L'inconvénient est que les accès aux pages larges subissent une perte de performance notable, leur temps d'accès étant allongé. Cela est contrebalancé par le fait que ces tailles de page ont été inventées pour réduire le nombre de défauts de TLB, mais ces défauts sont assez rares pour l'impact soit seulement mitigé, pas compensé. L'allongement du temps d'accès peut être compensé par diverses méthodes.

La première méthode est celle des accès simultanés à la TLB. Les TLB sont des caches assez performants, qui sont conçus pour être capables d'effectuer plusieurs accès en parallèle. On peut alors profiter de cette particularité pour lancer plusieurs accès au TLB en même temps, un par taille de page. Avec cette technique, les accès se faisant en parallèle et non l'un après l'autre, le temps d'accès est presque le même que si la TLB ne gérait qu'une seule taille de page. Le désavantage est que les multiples accès consomment de l'énergie et du courant, ce qui augmente la consommation énergétique de la TLB, qui est déjà très importante.

La seconde solution est la prédiction de taille de page. L'idée est que le processeur tente de prédire quelle sera la taille de page, afin de tomber directement sur la bonne taille de page. Au lieu de tenter d'abord pour une page de 4 kibioctets, puis 2 mébioctets et enfin 1-2 Gibioctets, le processeur testera la taille de page la plus probable, puis la seconde plus probable, avant de tester la dernière taille de page possible. Le problème est alors de concevoir un circuit capable de réaliser cette prédiction.

• Une manière simple mais extrêmement inefficace de faire cela est de mémoriser la taille des pages récemment accédées dans un cache spécialisé, qui mémorise la correspondance entre le numéro de la page et sa taille. La taille de la page est mémorisée dans ce cache, après le premier accès à cette page. Mais le défaut que le temps d'accès à ce cache de prédiction s'ajoute au temps d'accès à la TLBL2, ce qui en ruine totalement l'intérêt. Aussi, il faut trouver une solution alternative.
• Une autre solution n'utilise pas le numéro de page, mais l'instruction responsable de l'accès à la TLB. Un accès à la TLB signifie un accès en mémoire RAM, qui est réalisé par une instruction. Instruction qui est identifiée par une adresse, elle-même située dans le program counter. L'idée est que si une instruction est exécutée plusieurs fois, elle a tendance à accéder aux données d'une même page (localité spatiale). Ce n'est pas systématique, mais c'est une bonne supposition. On peut donc associer cette instruction à la taille de la page accédée récemment. Le cache de prédiction mémorise donc l'association entre adresse de cette instruction et taille de la page. Lors de l'accès mémoire, le program counter est récupéré et envoyé au cache de prédiction. En cas de succès d'accès, on obtient la taille de la page prédite. Cette méthode a le défaut que si plusieurs instructions accèdent à la même page, elles prendront chacune une ligne de cache dans le cache de prédiction et rien ne sera mutualisé.
• Une solution alternative est de récupérer lune adresse virtuelle proche de l'adresse lue/écrite avant que l'accès mémoire soit démarré. L'idée est que lors du décodage de l'instruction d'accès mémoire, on récupère les registres utilisés, et on y accède pour lire en avance l'adresse virtuelle.

Une dernière méthode consiste à amortir le temps d'accès en cas de défaut dans la TLB L2. L'idée est de démarrer un accès à la table des pages en RAM en parallèle de l'accès à la TLB L2. La raison est que le temps d'accès à la TLB L2, avec hash-rehashing, est très long. Il est sensiblement proche du quart du temps de défaut de TLB. Si en plus il fallait rajouter le temps d'accès à la table des pages en cas de défaut, le temps d'accès total serait énorme. Mais en lançant une lecture spéculative de la table des pages, le temps d'accès en cas de défaut est partiellement amorti. Le temps d'accès en cas de succès de TLB L2 reste cependant le même.

Le skewing

La technique du skewing est assez simple à comprendre pour qui se rappelle ce qu'est un cache associatif par voie, et encore plus un cache skew-associative. L'idée est d'utiliser un cache associatif par voie, mais où chaque voie est dédiée à une taille de page bien définie. Un cache associatif à trois voie pourra ainsi avoir une voie pour les pages de 4 kibioctets, une voie pour les pages de 2 mébioctets et une dernière voie pour les pages de plusieurs gibioctets. Cette méthode est conceptuellement équivalente au fait d'utiliser un cache pour chaque taille, à quelques différences près. Notamment, cela permet de mutualiser des circuits qui auraient été dupliqués en utilisant des caches séparés.

Les optimisations de la TLB

Les nombreuses optimisations relatives aux caches s'appliquent aux TLB. Ces optimisations utilisent généralement le principe de localité spatiale, à savoir que si une donnée est accédée, alors les données proches en mémoire ont de bonnes chances de l'être aussi dans les accès mémoire qui vont suivre immédiatement. Ces optimisations marchent d'autant mieux quand des pages virtuelles consécutives sont associées à des pages physiques consécutives, ce qui porte le nom de contiguïté de la traduction. Si ce principe est respecté, alors de nombreuses optimisations deviennent possibles.

Maintenir la contiguïté de traduction est cependant compliqué, et demande une certaine implication des systèmes d'exploitation, des langages de programmation, des allocateurs mémoires et d'autres entités logicielles. Les allocateurs mémoires tentent de regrouper les pages d'un même programme dans des pages consécutives, en utilisant des algorithmes d'allocation mémoire adapté, en compactant la mémoire physique, etc. Le fait que plusieurs programmes s’exécutent en même temps sur un même ordinateur et que leurs demandes d'attribution/allocation mémoire se font dans le désordre n'aide clairement pas leur travail. Mais ces méthodes purement logicielles permettent cependant de maintenir un certain degré de contiguïté de traduction, qui peut être exploité par la TLB.

Le coalesing

L'exploitation de la contiguité de traduction la plus simple est appelée le coalesing, aussi appelée technique de la fusion de page. Elle consiste à regrouper plusieurs pages virtuelles/physiques consécutives dans une seule entrée de TLB. Vous avez peut-être pensé que cette méthode revient à fusionner plusieurs pages mémoires consécutives pour obtenir une seule page large, mais c'est en réalité une technique plus versatile. La différence est qu'il n'y a pas de contraintes d'alignement particulière et que la taille du regroupement peut avoir une taille quasi-arbitraire (avec juste une limite haute). Il est possible de fusionner 3, 5, 6, 8 pages mémoires consécutives, alors que cela ne suffit pas à obtenir une page large. De même, la première page virtuelle peut se situer au beau milieu d'une page large, sans que cela ne pose problème. Le coalesing est donc une version améliorée et plus générale de cette idée.

Avec cette méthode, chaque entrée de TLB mémorise un intervalle d'adresses qui commence à une adresse de base et finit à une adresse de fin. Pour cela, l'entrée de TLB mémorise généralement le numéro de la première page virtuelle et le numéro de page physique associé, ainsi que le nombre de pages consécutives regroupées dans l'entrée. Lors d'un accès à la TLB, soit toutes les entrées sont accédées en parallèle (TLB totalement associative) soit quelques entrées sont accédées (TLB directement adressée ou adressée par voies). Les entrées accédées sont associées à des circuits qui vérifient si l'adresse envoyée à la TLB est bien dans l'intervalle mémorisé dans l'entrée. Si c'est le cas, c'est un succès de TLB, et un défaut sinon. Le défi que pose la conception de tels circuits est de concevoir ces circuits de vérification, ainsi que les circuits qui détectent que plusieurs pages sont contiguës en mémoire altèrent le contenu de la TLB pour faire la fusion de page.

Cette méthode est actuellement exploitée dans des processeurs commerciaux, comme dans l'architecture AMD Zen, et les suivantes. Elle permet de réduire l'usage de la TLB, d'économiser des entrées dans la TLB et j'en passe. Son défaut principal est qu'elle requiert des circuits en plus et tout le défi est de faire en sorte que ces circuits supplémentaires aient un impact mineur. Il faut que l'augmentation de la taille des entrées ne compense pas les gains gagnés par cette optimisation, sans quoi cette optimisation perd son intérêt.

Le préchargement des entrées de TLB

Le préchargement est utilisé sur les TLB des processeurs modernes. Les techniques de préchargement utilisées pour les caches, et donc pour les TLB, ont été vues dans le chapitre sur le préchargement. Pour les TLB, seules les techniques pour le préchargement des données sont utilisées, la table des pages étant une structure de donnée des plus classiques. Il s'agit d'un simple tableau pour une table des pages simple ou inversée, d'un mélange entre arbre et tableau pour les tables des pages hiérarchiques. En conséquence, les préfetcheurs des TLB utilisent généralement le préchargement séquentiel, en enjambées, un préchargement de Markov, etc.

Le préchargement sur les TLB peut cependant causer quelques situations spécifiques, qu'il faut gérer au mieux. Notamment, il est possible que le processeur tente de précharger une portion de la table des pages qui a été swappée sur le disque dur. Dans ce cas, on a deux solutions : soit on émet un défaut de page pour que le système d'exploitation charge la partie manquante depuis le disque dur, soit on ne fait rien et le préchargement est annulé. Dans la quasi-totalité des processeurs, c'est la seconde solution qui est utilisée. Le gain de performance en cas de bonne prédiction ne vaut pas la perte liée à un accès au disque dur en cas de préchargement inutile.