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.

MMU avec une TLB.

Le TLB 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.

Contenu de la 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 TLB.

Les entrées de la TLB

La TLB est un cache comme un autre, dont chaque ligne de cache contient une correspondance entre une adresse logique et une adresse physique. Dans ce qui va suivre, une ligne de cache de la TLB sera appelée une entrée de la TLB. Intuitivement, une entrée correspond plus ou moins à une entrée de la table des pages. Mais son format dépend du processeur, alors que la table des pages dépend de l'OS. Aussi, il y a parfois de petites différences. Certains bits utiles pour l'OS ne le sont pas pour la traduction d'adresse.

Les droits d'accès de la protection mémoire

Les entrées de la TLB peuvent contenir les droits d'accès à chaque page. Par droits d'accès, on veut parler des droits d'accès liés à la protection mémoire. La plupart des TLB incorporent trois bits, qui indiquent si la page est accessible en lecture, écriture ou exécutable. D'autres se passent d'un bit pour l'accès en lecture et considèrent que toute page est accessible en lecture. Ce qui est assez intelligent, car il est très rare pour une page de ne pas être accessible en lecture. De même, l'incorporation de certaines techniques de protection mémoire comme le "Write XOR Execute" peuvent être implémentée ou non dans la TLB.

Les bits dirty et accessed

La TLB contient, pour chaque entrée, un bit Valid qui indique si l'entrée contient une correspondance ou non. Il indique si l'entrée est vide ou occupée. Son interprétation n'est pas du tout la même que le bit de même nom dans la table des pages, les deux n'ayant pas du tout la même fonction et sont en réalité deux bits différents qui portent le même nom par simplicité de nommage.

Une entrée de la TLB contient aussi le bit Dirty de la page associée. Pour rappel, ce bit indique si la page a été accédée en écriture. Lors de chaque écriture, le processeur doit contourner la TLB et accéder en RAM, pour mettre ce bit à 1. S'il devait faire cela à chaque écriture, beaucoup d'accès mémoire inutiles auraient lieu. Pour éviter cela, le bit dirty est mémorisé dans la TLB. Si une écriture a lieu, le processeur vérifie le bit dirty dans la TLB. S'il est à 0, alors il met à jour la table des pages, il met à jour le bit dirty en mémoire RAM. S'il est déjà à 1, alors le bit est déjà à la bonne valeur en RAM : il n'accède pas à la mémoire RAM, il laisse la table des pages tranquille.

Le bit accessed, aussi appelé bit ref pour referenced, n'est pas systématiquement mémorisé dans la TLB. Il peut servir pour implémenter l'algorithme de remplacement LRU, mais encore faut-il que cet algorithme soit implémenté. C'est possible sur les TLB de niveau L2 (car oui, comme nous le verrons plus bas, il y a une hiérarchie de TLB, comme pour les autres caches), mais pas sur celles de niveau L1.

Description des bits de contrôle d'une entrée de TLB, sans les bits de protection mémoire.

Les bits de gestion de la multi-programmation

De nos jours, tous les systèmes d'exploitation sont multi-programmés et les processus ont chacun leur propre espace d'adressage. La correspondance adresse logique - physique n'est pas la même d'un processus à l'autre, donc le contenu de la TLB n'est pas censé être le même d'un processus à l'autre. La solution utilisée autrefois était de vider complétement la TLB à chaque changement de processus. Mais les performances s'en ressentent, vider la TLB n'est pas gratuit.

A la place, chaque entrée de la TLB contient un identifiant de processus qui précise pour quel processus, pour quel espace d'adressage, la correspondance est valide. Le processeur vérifie que l'identifiant du processus en cours correspond à chaque accès à la TLB, pour trouver la bonne entrée de la TLB. Le TLB n'a plus besoin d'être réinitialisé à chaque changement de processus. Mais il arrive que les OS n'utilisent pas toujours ce système d'identifiant de processus CPU.

Chaque entrée de la TLB contient aussi un bit global, qui indique que la correspondance est valide dans tous les espaces d'adressage. L'intérêt n'est pas évident, mais il le devient quand on se rappelle que le noyau de l'OS est mappé dans le haut de l'espace d'adressage. Et peu importe l'espace d'adressage, le noyau est toujours mappé de manière identique, les mêmes adresses logiques adressant la même adresse mémoire. En conséquence, les correspondances adresse physique-logique sont les mêmes pour le noyau, peu importe l'espace d'adressage. Le bit global accélère rapidement la traduction d'adresse pour l'accès au noyau.

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

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.

Page table actions

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. 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. Vu que le système d'exploitation gère l'accès à la table des pages, il peut utiliser le format de table des pages voulu.

Sur les architectures à plusieurs processeurs, chaque cœur ou processeur a son propre PTW.

La gestion des bits de statut de la table des pages

Les PTW gérent aussi la gestion des bits de statut, qui mémorisent des informations sur chaque page, est gérée par le PTW. Par exemple, c'est leur rôle de mettre à jour les bits dirty et accessed directement dans la table des pages. Pour rappel, ces deux bits indiquent qu'une page a été accédée récemment pour le bit accessed, ou qu'elle a été accédée en écriture pour le bit dirty. Ils sont présents à la fois dans la TLB et dans la table des pages. Et pour faire leur travail, ils doivent être modifiés en RAM lors de chaque lecture/écriture.

Le bit dirty est mis à jour, comme indiqué dans la section précédente, lorsqu'on fait une écriture dans une page clean, non-dirty, où ce bit est à 0. La TLB détecte un tel accès, vu qu'elle mémorise ce bit pour chaque entrée.

Le bit accessed est lui mis à jour lors d'un défaut de TLB, pour des questions de performance. En théorie, on devrait le mettre à jour à chaque accès mémoire, peu importe que ce dernier passe par la TLB ou non, mais cela réduirait les performances à un point où les TLB seraient inutiles. Les TLB servent à éliminer des accès mémoire, en passant par le cache. Si chaque accès devait mettre à jour ce bit, la TLB n'éliminerait aucun accès mémoire, elle en réduirait juste la taille (pas besoin de lire les correspondances d'adresse).

L'implémentation matérielle des PTW

Toutes les informations nécessaires pour gérer les défauts de TLB sont stockées dans des registres spécialisés appelés des tampons de PTW (PTW buffers). Le plus important est celui qui mémorise la position de la table des pages en mémoire RAM. Les PTW ont besoin, pour faire leur travail, de mémoriser l'adresse physique 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. Cette adresse est mémorisée dans un registre spécialisé, manipulé seulement par le système d'exploitation.

Sur certains processeurs, dont certains processeurs ARM, il y a deux registres : un pour la table des pages du processus en cours d'exécution, et un autre pour une table des pages globale, partagée avec tous les processus. Typiquement, la seconde table des pages sert pour la partie du noyau mappée dans l'espace d'adressage. Le premier registre est modifié à chaque changement de processus, l'autre ne l'est pas, car il n'a pas besoin de l'être.

Les PTW sont généralement implémentés avec des circuits séquentiels spécifiques, nommés machines à état, qui contiennent les tampons de PTW. Mais l'implémentation dépend fortement du format de la table des pages.

• 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 calculer la fonction de hashage, 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 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 étant que la taille des lignes de cache n'est pas la même. Les TLB renvoient un numéro de page physique, alors que les caches de la MMU fournissent en sortie une adresse mémoire complète, plus longue.

Les MMU utilisent presque toujours un cache par 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. Aussi, nous parlerons de cache MMU de niveau 1, de niveau 2, etc ; pour désigner ces caches. 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 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...

Les deux types de caches MMU

L'accès aux caches MMU peut se faire de deux manières différentes, suivant le processeur. Soit on effectue le parcours de la table des pages normalement, mais on accélère chaque étape grâce à son cache dédié, soit on accède aux caches en parallèle et on prend le résultat le plus avancé, celui associé au niveau de table des pages le plus bas.

La première méthode est celle des page walk caches des processeurs AMD. Les page walk caches effectuent un parcours normal de la page des tables, mais accélèrent chaque étape. On effectue toujours 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 ; mais chaque lecture se fait dans le cache et non en mémoire RAM. Les caches sont accédés dans l'ordre normal d'un parcours de la table des pages, dans le même ordre que sans cache de MMU.

Vu que le page table walker génère des adresses physiques, ces caches sont nécessairement physiquement tagués. En clair, ils reçoivent l'adresse physique de l'entrée de la table des pages, et fournissent en sortie l'adresse physique de la table des pages suivante, du niveau suivant.

Les paging structure cache d'Intel permettent de sauter des étapes et de prendre des raccourcis, en accédant aux caches des différents niveaux en parallèle. Ils permettent par exemple de commencer le parcours de la table des pages en RAM directement dans le second ou troisième niveau, si le contenu des caches le permet. Avec cette méthode, lors d'un TLB miss, on accède à tous les paging structure cache en parallèle : celui de la table de niveau 1, celui de la table de niveau 2, etc. Le résultat provenant du cache associé à la table de niveau le plus bas, sert de point de départ pour parcourir la table des pages hiérarchique. Ce qui rend le parcours de la table des pages beaucoup plus rapide.

Mais tout cela dépend de si les entrées adéquates sont dans le cache. Si l'on commence directement dans le premier niveau, les paging structure cache perdent de leur intérêt. La raison est qu'ils sont plus lents que les page walk caches. On accéde en parallèle à tous les caches des différents niveaux en parallèle, et on doit attendre que le dernier réponde, ce qui allonge le temps d'accès au cache. Avec les page walk caches, on accède à chaque cache séquentiellement, mais chaque accès est plus rapide. Et ce d'autant plus qu'on atterrit haut dans la hiérarchie des différents niveaux.

Vu que les caches sont accédés en parallèle, on doit utiliser l'adresse virtuelle. Avec un page walk cache, le cache MMU de niveau 2 est accédé avec l'adresse physique de l'entrée à lire. Mais ici, on ne dispose pas de cette adresse physique, vu qu'on doit accéder au cache de niveau 1 pour. La seule solution est d'utiliser une adresse virtuelle, non-traduite. Les paging structure cache sont donc des caches virtuellement tagués, qui adressent leurs caches avec certains bits de l'adresse virtuelle à lire/écrire, avant accès à la TLB. Les bits de poids fort sont utilisés pour adresser la table de premier niveau, les bits précédents servent à adresser la table de second niveau, et ainsi de suite

Une hiérarchie de TLB

Pour des raisons de performances, la TLB est parfois découpée en plusieurs sous-caches L1, L2, L3, etc. La politique de remplacement change suivant les niveaux de la hiérarchie de TLB. Les TLB L2 peuvent se permettre d'utiliser du LRU, du pseudo-LRU, FIFO, ou autre, comme tout cache de grande taille. Par contre, la TLB L1 doit être la plus rapide possible, et le remplacement des lignes de cache doit être rapide avant tout, même s'il est inefficace. Il n'est pas rare que les TLB L1 utilisent un algorithme de remplacement pseudo-aléatoire.

Les TLB L1 sont séparées pour les instructions et les données

De plus, 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.

La ou les TLB des processeurs multicoeurs

Sur les processeurs multicœurs, qui regroupent plusieurs processeurs dans une même puce électronique, la TLB doit être adaptée. Il est possible d'utiliser une TLB unique pour tous les processeurs, ou bien une TLB séparée par processeur. Les deux solutions ont des avantages et inconvénients différents.

Avec une TLB partagée, la TLB doit avoir assez de ports d'accès pour servir tous les processeurs, ce qui fait qu'elle est un peu plus lente. De plus, la TLB est placée en dehors des cœurs/processeurs, elle est assez éloignée de certains processeurs et proches des autres, ce qui rajoute un peu de latence. Par contre, une correspondance adresse physique-logique dans la TLB est accessible à tous les cœurs. C'est très utile si un même processus s'exécute sur plusieurs processeurs/cœurs, notamment si plusieurs threads s'exécutent en même temps et accèdent aux mêmes zones de mémoire.

Avec une TLB par processeur, une correspondance adresse physique-logique dans la TLB n'est pas accessible à tous les cœurs/processeurs, mais seulement au processeur/cœur attitré. Par contre, la TLB peut être placé directement dans le processeur/cœur, sans compter qu'elle a moins de ports. Elle est donc très rapide.

L'organisation actuelle utilise un mélange des deux méthodes précédentes, adaptée à une hiérarchie de deux niveaux de TLB. Elle utilise une TLB partagée entre tous les cœurs pour le niveau L2, mais deux TLB de niveau L1 par cœur (une pour les instructions, l'autre pour les données). Les TLB de niveau 1 doivent être rapides, ce qui fait qu'on utilise des TLB séparées par cœur/processeur. Par contre, les TLB de niveau L2 peuvent être plus lentes, mais doivent utiliser leur capacité au mieux, ce qui fait qu'il vaut mieux la partager entre les cœurs/processeurs.

L'invalidation de la TLB

La TLB mémorise des correspondances entre adresses physiques et adresses logiques, pour chaque processus. Les correspondances ne sont pas les mêmes d'un processus à l'autre, ce qui fait que la TLB est complètement vidée, sauf si les optimisations adéquates sont implémentées. Mais il existe d'autres circonstances qui font que la TLB doit être invalidée, à savoir que son contenu doit être vidé entièrement ou partiellement.

Les circonstances qui mènent à une invalidation de la TLB

Au-delà du changement de processus, il faut aussi invalider la TLB quand la table des pages est modifiée. Si une modification a lieu dans la table des pages, elle n'est pas propagée automatiquement dans la TLB. Il y a alors un problème dit de cohérence des caches, à savoir que le contenu du cache (ici, la TLB) et de la RAM, ne concorde pas.

Le cas le plus simple est celui où une ou plusieurs correspondances d'adresse sont modifiées. Dans ce cas, la correspondance est mise à jour dans la mémoire RAM, mais n'est pas propagée automatiquement dans la TLB. Les traductions d'adresses ultérieures peuvent donc être fausses, si jamais elles utilisent la correspondance non-mise à jour dans la TLB. Mais il y a d'autres raisons, une entrée de la table des pages ne contenant pas que des correspondances d'adresse.

Modifier les bits accessed ou dirty peut mener à une invalidation de la TLB, mais sous certaines conditions. Mettre à 1 ces bits ne posera pas de problèmes, même si la mise à jour n'est pas propagée dans la TLB. Vu qu'ils sont mis à 1 automatiquement par le processeur, le pire qui puisse arriver est que le PTW mettra ces bits à 1 alors qu'ils le sont déjà. Par contre, les mettre à 0 demande de vider la TLB. Sans cela, le processeur croira que ces bits sont à 1 et ne les mettra pas à 1 si la situation le nécessite. Et cela causera des problèmes pour le système d'exploitation.

Une modification des droits d'accès d'une page mémoire peut mener à une invalidation, ou au contraire n'avoir aucune conséquence. Si les droits d'accès sont réduits, à savoir qu'on interdit une opération auparavant possible, la TLB doit être invalidée. Mais si on augmente les droits, pas besoin d'invalidation. Un accès supposé invalide déclenchera un défaut d epage, ce qui activera le PTW et mettra à jour la TLB automatiquement. L'instruction fautive aura alors accès aux droits d'accès corrects, et autorisera l'accès.

Les TLB ne sont pas gardées cohérentes

Les situations précédentes font qu'une entrée de la table des pages en RAM et sa copie dans la TLB ne concordent pas. On dit qu'il y a un défaut de cohérence des caches. Ce n'est pas spécifique à la TLB et nous avions vu il y a quelques chapitres que des situations similaires existent : nous avions vu le cas des transferts DMA il y a quelques chapitres, nous verrons aussi des situations similaires sur les architectures multicœurs. D'ailleurs, une section dans le chapitre sur les caches était dédiée à l'invalidation des caches, cette section en est l'équivalent pour la TLB.

S'il est en théorie possible d'utiliser des mécanismes de cohérence des caches, qu'on verra dans le chapitre sur les CPU multicœurs, ce n'est pas le cas en pratique. Ne pas garder ces caches cohérents permet de gagner grandement en performances et d'économiser des circuits. Aussi, on doit recourir à la solution présentée dans le chapitre sur les mémoires caches : invalider le cache.

Les méthodes de cohérence des caches demandent que la TLB vérifie tous les accès mémoire, pour détecter les accès aux entrées de la page des tables. Mais pour cela, la TLB devrait mémoriser l'adresse physique des entrées de la table des pages qu'elle cache. Or, ce n'est pas le cas. Elles cachent des numéros de page physiques et logiques, pas plus. Incorporer cette adresse physique dans la TLB ne résout pas tous les problèmes. Il faudrait accéder à toute la TLB à chaque accès mémoire pour implémenter la cohérence des caches, ce qui se marie mal avec des TLB associatives par voie. Les techniques pour résoudre ce problème n'en valent pas la peine, et le système de mémoire virtuelle dispose à la place de techniques pour invalider le contenu de la TLB quand c'est nécessaire.

Quand l'OS modifie la table des pages, il utilise une procédure qui invalide la TLB. La procédure varie grandement d'un processeur à l'autre. Elle permet soit de vider la TLB entière, parfois de n'invalider qu'une seule correspondance. Sur les processeurs ARM récents, l'invalidation est réalisée par une instruction spécifique. Suivant ses arguments, l'instruction invalide toute la TLB ou seulement l'entrée voulue. Sur les anciens processeurs ARM et sur les processeurs x86, il faut écrire dans un registre de contrôle spécifique pour invalider la TLB.

Sur les systèmes multiprocesseurs, l'invalidation de la TLB peut soit toucher la TLB d'un seul cœur, soit invalider les TLB de tous les cœurs en même temps. Sur les processeurs ARM récents, l'instruction d'invalidation de TLB impacte tous les cœurs, sans exception, il n'y a pas moyen de n'invalider la TLB que d'un seul cœur. Sur les processeurs IBM PowerPC, il y a une instruction spécifique pour chaque cas : l'instruction tlbiel invalide la TLB du cœur qui exécute l'instruction, l'instruction tlbie invalide toutes les TLB. Les processeurs x86 utilisent un autre mécanisme, basé sur des interruptions inter-processeur.

Il faut noter que si la TLB est invalidée, les caches de la MMU doivent aussi l'être.

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. Dans ce qui va suivre, nous allons parler de TLB multi-taille pour désigner une TLB qui peut gérer des pages de taille différentes.

Les trois implémentations possibles

L'implémentation la plus simple d'une TLB multi-taille modifie un cache totalement associatif. L'idée est que chaque entrée contient un masque qui dépend de la taille de la page. Quand un accès à la TLB a lieu, toutes les entrées sont accédées en parallèle, comme sur tout cache associatif. Lors de l'accès, le masque est appliqué à l'adresse virtuelle, et le résultat est comparé au Tag de la ligne de cache. Le problème est que les TLB n'utilisent pas de cache totalement associatif, car de tels caches sont assez lents, sans compter qu'ils trop gourmands en énergie, en circuits.

Il faut donc trouver un moyen d'implémenter une TLB multi-taille avec un cache associatif par voie. Les deux techniques principales 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.

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. Ils l'utilisaient pour les pages de 4Kb et de 2 Mb, mais pas pour les pages de 1 gigas.

L'inconvénient des deux méthodes est que les accès aux pages larges subissent une perte de performance notable, leur temps d'accès étant allongé. Le problème est que le temps d'accès à la TLB est crucial pour l'accès aux mémoires caches, qui sont actuellement virtuellement adressées et physiquement tagués. De tels caches demandent que la TLB fournisse son résultat avant la comparaison des Tags, ce qui demande que le temps d'accès à la TLB soit gardé très petit.

La seconde technique, celle 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 skew-associative où chaque voie est dédiée à une taille de page bien définie. Un cache associatif à six voies pourra ainsi avoir deux voies pour les pages de 4 kibioctets, deux voies pour les pages de 2 mébioctets et deux voies 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.

Accélérer l'accès à une TLB multi-taille

Les techniques précédentes ont comme défaut de ralentir l'accès à la TLB. Mais 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.

Une autre 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.

Mais la technique a des défauts. Déjà, le temps d'accès en cas de succès de TLB L2 reste cependant le même. De plus, cette méthode rajoute un accès mémoire spéculatif, ce qui utilise le débit binaire de la mémoire, qui pourrait être utilisé autrement. Une méthode pour limiter la casse est de l'effectuer ce accès que si la mémoire RAM est libre, qu'aucun accès n'est en cours.

Une dernière 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 TLB, 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. L'instruction d'accès mémoire est située à une adresse, disponible 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). 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 utilise le fait que les adresses virtuelles sont souvent calculées à partir d'une adresse de base, à laquelle on ajoute un décalage ou bien un indice. Les modes d'adressage Base+Index ou Base+offset fournissent l'adresse de base dans un registre, les autres opérandes étant codé dans l'instruction (décalage) ou dans un registre. L'idée est que le décalage et l'indice sont souvent petits, ce qui fait que l'adresse finale reste assez proche de l'adresse de base. L'idée est donc d'associer la taille de la page au contenu du registre de base, là encore avec un cache dédié. Le contenu du registre de base est lu pour faire le calcul d'adresse, mais il est aussi envoyé au cache de prédiction, qui l'utilise pour déterminer la taille de la page adressée.

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.