Fonctionnement d'un ordinateur/Les caches non-bloquants
Les processeurs à exécution dans le désordre peuvent avoir plusieurs accès mémoire simultanés. Les processeurs de ce type peuvent techniquement lancer des accès mémoire à chaque cycle, mais ces accès mémoires prennent du temps, ce qui fait qu'on peut avoir des accès mémoires qui ont lieu en même temps. Diverses techniques permettent au cache de gérer plusieurs accès simultanés, notamment l'usage de caches pipelinés. Et la technique la plus intéressante est l'usage de caches non-bloquants, mais il faut aussi citer les techniques liées au line fill buffer que nous allons détailler dans ce qui suit.
Le line fill buffer et les techniques associées
[modifier | modifier le wikicode]Dans ce qui suit, on part du principe qu'il y a un cache unique et une mémoire RAM, pour simplifier les explications. Mais le tout fonctionne très bien avec une hiérarchie de cache, avec quelques adaptations.
Le tampon de remplissage de ligne
[modifier | modifier le wikicode]Sur un cache bloquant, lors d'un défaut de cache, le processeur doit attendre que toute la ligne de cache soit chargée avant d'être utilisable. Or, la taille d'une ligne de cache est supérieure à la largeur du bus mémoire, ce qui fait qu'une ligne de cache est chargée en plusieurs fois, morceaux par morceaux, mot mémoire par mot mémoire. Le chargement peut se faire directement dans le cache, mais ce n'est pas une solution très pratique. À la place, beaucoup de processeurs ajoutent une mémoire tampon entre la RAM et le cache, appelée le tampon de remplissage de ligne (line-fill buffer) dans les processeurs modernes. Lors d'un défaut de cache, le processeur charge la donnée de la RAM dans le tampon de remplissage de ligne, mot mémoire par mot mémoire. Une fois plein, le tampon de remplissage de ligne est recopié dans la ligne de cache.
La même chose existe avec une hiérarchie de cache, sauf que l'on trouve une mémoire tampon entre chaque niveau de cache. Il y a un tampon de remplissage de ligne entre le cache L1 et le cache L2, entre le cache L2 et le L3, etc. Si le cache ne gère qu'un seul défaut de cache à la fois, le fil buffer est une mémoire très simple, qui ne mémorise qu'une seule ligne de cache. Et cela vaut aussi bien pour un cache bloquant que non-bloquant. Mais sur les caches capables de gérer plusieurs défauts simultanés, le tampon de remplissage de ligne est une mémoire de type FIFO ou LIFO, capable de mémoriser plusieurs lignes de cache.
Notons que le tampon de remplissage de ligne est très utile pour implémenter certaines techniques, par exemple le contournement du cache. Nous avions vu dans le chapitre sur le cache que certains accès mémoire doivent contourner le cache, pour des raisons de cohérence des caches. C'est notamment nécessaire pour accéder aux périphériques, mais c'est aussi utile pour des raisons de performances dans des cas très spécifiques. Les accès qui contournent le cache se font directement dans le tampon de remplissage de ligne : le processeur écrit ou lit les données depuis ce tampon de remplissage de ligne, sans accéder au cache.
Le contenu du tampon de remplissage de ligne
[modifier | modifier le wikicode]Le tampon de remplissage de ligne contient une ligne de cache, avec cependant quelques petits changements. On retrouve un champ pour stocker le tag, et un autre champ pour stocker la donnée chargée. Les bits de contrôle ne sont pas tous présents, vu que certains n'ont de sens que pour une ligne de cache complète. Le tampon de remplissage de ligne ne contient généralement pas de bit de validité pour toute la ligne, mais il possède quelque chose qui s'en rapproche.
Le tampon de remplissage de ligne contient un bit de validité pour chaque mot mémoire de la ligne de cache, qui indiquent si le mot mémoire a été chargé. Par exemple, prenons un processeur 64 bits, qui gère donc des mots mémoire de 8 octets, avec des lignes de cache 256 octets/32 mots mémoire. Le tampon de remplissage de ligne contiendra 32 bits de validité. Si le processeur a chargé les 6 premiers mots mémoire, les 6 premiers bits de validité seront mis à 1, les autres seront encore à 1.
Il faut noter que la disponibilité de la ligne complète se détermine assez facilement en faisant un ET logique entre tous les bits de validité. Le processeur sait ainsi quand la ligne de cache est disponible entièrement et donc quand la transférer dans le cache.
L'early restart et le critical word load
[modifier | modifier le wikicode]La présence du line buffer permet une optimisation assez intéressante, qui permet de réduire la latence des défauts de cache. L'optimisation consiste à lire un mot mémoire dans le tampon de remplissage de ligne, même si la ligne de cache complète n'a pas encore été chargée. Il existe deux manières de faire cela, qui portent les noms d'early restart et de critical word load. La première est la version la plus simple, la seconde est plus complexe mais plus performante.
Avec la technique d'early restart, la ligne de cache est chargée normalement, en partant de son premier mot mémoire. Dès que le mot mémoire lu/écrit par le processeur est copié dans le line fill buffer, il est envoyé au processeur immédiatement. Illustrons le tout par un exemple, où une ligne de cache fait 16 mots mémoire. Le processeur effectue une lecture, qui lit le 5ème mot mémoire. Sans early restart, le processeur doit charger les 16 mots mémoire avant de faire la lecture dans le cache. Avec early restart, le processeur reçoit la donnée dès que le 5ème mot mémoire est disponible. Le processeur doit attendre que les 4 premiers mots mémoire soient chargés, puis le 5ème mot mémoire arrive et est envoyé directement au processeur, il est lu directement depuis le line fill buffer. Les 11 mots mémoire suivants sont ensuite chargés dans le cache pendant que le processeur fait des calculs dans son coin.
Le critical word load est une optimisation de la technique précédente où le chargement de la ligne de cache commence directement à la donnée demandée par le processeur. Pour reprendre l'exemple précédent, où le processeur demande le 5ème mot mémoire sur 16, le critical word load charge le 5ème mot mémoire en premier et l'envoie au processeur, ce qui fait qu'il est chargé très rapidement. Pas besoin d'attendre que le processeur charge les 4 mots mémoire précédents comme avec l'early restart. Dans le détail, le processeur charge le 5ème mot mémoire en premier, puis charge les 11 suivants, et termine par les 4 mots mémoire du début. En clair, le critical word load commence par charger le mot mémoire lu, puis les blocs suivants, avant de revenir au début du bloc pour charger les blocs restants. Ainsi, la donnée demandée par le processeur sera la première disponible.
Pour cela, l'organisation du tampon de remplissage de ligne est modifiée de manière à rendre cela possible. Il a une taille égale à une ligne de cache complète, qui contient elle-même plusieurs mots mémoire. Dans le line-fill buffer, chaque mot mémoire est stocké avec un tag, qui indique l'adresse du mot mémoire stocké dans le line-fill buffer. Le line-fill buffer est donc un cache un peu particulier, qui fonctionne comme un cache du point de vue du processeur, comme une mémoire FIFO pour les transferts avec le cache. Ainsi, un processeur qui veut lire dans le cache après un défaut peut accéder à la donnée directement depuis le tampon de remplissage de ligne, alors que la ligne de cache n'a pas encore été totalement recopiée en mémoire.
Les caches non bloquants
[modifier | modifier le wikicode]Un cache bloquant est un cache auquel le processeur ne peut pas accéder pendant un défaut de cache. Il faut attendre que la lecture ou écriture en RAM soit terminée avant de pouvoir utiliser de nouveau le cache. Un cache non bloquant n'a pas ce problème : on peut l'utiliser pendant un défaut de cache. Les caches non bloquants permettent de démarrer une nouvelle lecture ou écriture alors qu'une autre est en cours, ce qui permet d'exécuter plusieurs lectures ou écritures en même temps.
Les Miss Handling Status Registers
[modifier | modifier le wikicode]Lors d'un défaut de cache, la mémoire RAM est consultée pendant le défaut de cache, mais le cache est inutilisé. Un défaut de cache n'utilise pas le cache, ce n'est qu'un accès en mémoire RAM, sur le bus mémoire (ou un accès aux niveaux de cache inférieurs, peu importe). Le cache en lui-même est laissé libre, rien n’empêche d'y accéder, il est en réalité intrinsèquement non-bloquant. Les caches, bloquants comme non-bloquants, sont en réalité composés d'une mémoire cache proprement dite, entourée de circuits qui servent d'interface entre le processeur et le cache lui-même. Et parmi les circuits tout autour, certains gèrent l'accès au cache lors d'un défaut de cache. Ils sont regroupés sous le terme de Miss Handling Architecture (MHA). La différence entre un cache bloquant et un cache non-bloquant est en réalité liée à l'implémentation de la MHA.
Les caches non-bloquants coupent volontairement l'accès au cache lors d'un défaut, car les défauts sont plus simples à gérer ainsi. Le défaut de cache rapatrie une donnée depuis la RAM, qui sera écrite dans le cache. Et il ne faut pas qu'une tentative d'accès à cette donnée ait lieu avant qu'elle ne soit chargée. Mais ce blocage est général et touche tout le cache, alors que seule une ligne de cache est concernée par le défaut de cache.
L'idée derrière un cache non-bloquant est que seule la ligne de cache est bloquée, mais les autres sont accessibles. L'idée est alors de mémoriser les lignes de cache concernées par le défaut de cache, afin d'en bloquer l'accès. A chaque accès, on vérifie si la ligne de cache est déjà réservée par un défaut de cache. La lecture/écriture est alors bloquée si c'est le cas, mais elle accepte les accès sinon. Pour cela, la Miss Handling Architecture contient des registres qui mémorisent des informations sur les défauts de cache en cours. Ils portent le nom de miss status handling registers, que j’appellerais dorénavant MSHR, qui sont aussi appelés des miss buffer.
Le contenu des MSHR varie beaucoup suivant le processeur, mais ces derniers stockent au minimum les informations suivantes :
- Le numéro de la ligne de cache dans laquelle les données sont chargées.
- Un bit de validité qui indique si le MSHR est vide ou pas, qui est mis à 0 quand le défaut de cache est résolu.
- Un ou plusieurs champs de lecture/écriture, qui contiennent des informations sur la lecture/écriture.
- Pour une lecture, elle contient des informations sur la destination de la donnée, à savoir qui prévenir quand le défaut de cache est terminé. C'est parfois un nom/numéro de registre (celui dans lequel charger la donnée), mais c'est souvent le numéro de l'entrée dans le load/store queue.
- Pour les écritures, elle contient la donnée à écrire, ou éventuellement un numéro de load/store queue où se trouve la donnée à écrire.
Il faut noter que le bus mémoire ne peut gérer qu'un seul défaut de cache à la fois. Aussi, il est intéressant de regarder ce qui se passe lorsqu'un second défaut de cache survient, pendant qu'un premier est en cours. Dans ce cas, il y a deux réponses qui correspondent à deux types de caches non-bloquants, qui portent les noms barbares de caches de type succès après défaut et défaut après défaut. Sur le premier type, il ne peut pas y avoir plusieurs défauts de cache simultanés. Dès qu'un second défaut de cache survient, le cache stoppe son activité et on ne peut plus démarrer de nouvelle lecture/écriture, tant que le premier défaut de cache n'est pas résolu. Le second type est plus souple et autorise la survenue de plusieurs défauts de cache simultanés. Du moins, jusqu'à une certaine limite, car le cache ne peut supporter qu'un nombre limité d'accès mémoires simultanés (pipelinés).
Les accès simultanés à une même ligne de cache
[modifier | modifier le wikicode]Il arrive que le processeur fasse plusieurs accès mémoire simultanés à la même ligne de cache. Si la ligne de cache en question n'a pas encore été chargée dans le cache, alors on a plusieurs défauts de cache consécutifs pour la même ligne de cache, et le cache non-bloquant doit gérer la situation. Pour la suite, il va falloir faire une petite distinction entre les défauts primaires et secondaires. Imaginons qu'un défaut de cache ait lieu et demande à charger une donnée dans la ligne de cache numéro N. Il s'agit du premier défaut impliquant cette ligne de cache précise, ce qui lui vaut le nom de défaut de cache primaire. Mais par la suite, d'autres accès mémoire à la même ligne de cache ont lieu, alors que la ligne de cache n'est pas encore disponible. Dans ce cas, il s'agit de défauts de cache secondaires.
Pour l'unité d'accès mémoire, les défauts de cache primaire et secondaire sont différents (ils prennent tous une entrée dans la load/store queue). Mais pour le cache, ils ne correspondent qu'à un seul accès au cache : celui qui demande de charger la ligne de cache demandée. Les défauts de cache primaire et secondaire à la même ligne de cache se voient attribuer un MSHR unique. La gestion des défauts de cache secondaires dépend du cache non-bloquant. La solution la plus simple ne permet pas les défauts de cache secondaires. Le cache ne permet pas deux défauts de cache simultanés pour la même ligne de cache. Les autres solutions le permettent, en fusionnant des accès simultanés à la même ligne de cache en un seul au niveau des MSHR. Dans tous les cas, détecter les défauts de cache secondaires sont un problème qu'il faut détecter.
La Miss Handling Architecture doit détecter les défauts de cache secondaire. Pour cela, elle procède comme suit. Lors de chaque défaut de cache, la MHA récupère le numéro de la ligne de cache associé. Il vérifie alors chaque MSHR pour vérifier s'il contient le numéro en question. S'il n'y a aucune correspondance dans les MSHR, alors c'est signe que le défaut de cache est un défaut primaire. Mais s'il y en a une, alors c'est un défaut secondaire. Évidemment, cela signifie que lors d'un défaut de cache, le numéro de ligne de cache est envoyé à tous les MSHR, pour comparaison. Les MSHR sont donc regroupés dans une mémoire associative, une sorte de mini-cache, faciliter l'implémentation.
Lors d'un défaut de cache primaire, l'accès à un cache non-bloquant se fait comme suit : le processeur envoie une adresse au cache, accède à celui-ci, et détecte la survenue d'un défaut de cache. Il en profite alors pour attribuer une ligne de cache dans laquelle sera chargée ce défaut. L'attribution est très simple dans le cas des caches direct mapped, ou associatifs par voie, pour lesquels l'attribution se fait assez simplement. Il mémorise alors cette information dans les MSHR, après avoir vérifié que le défaut de cache n'était pas un défaut secondaire.
Lors des accès ultérieurs à une adresse proche, censée être dans la même ligne de cache, le processeur va encore une fois rencontrer un défaut de cache. Il va alors déterminer le numéro de la ligne de cache associée à l'adresse, et comparer ce numéro avec les MSHRs. Si un MSHR contient ce numéro, c'est signe que le défaut de cache est un défaut secondaire. La MHA réagit alors différemment selon le processeur considéré. Une première solution n'autorise pas les défauts de cache secondaires. Si l'un d'entre eux survient, le processeur est gelé par un pipeline stall, une bulle de pipeline. Une autre solution fusionne les défauts de cache secondaires avec le défaut de cache primaire : tout cela ne correspond qu'à un seul défaut de cache pour lui.
Les MSHR simples
[modifier | modifier le wikicode]Un cache non-bloquant à MSHR simple contient juste plusieurs MSHR qui mémorisent juste un numéro de ligne de cache, un bit de validité, le champ de lecture/écriture, et l'adresse exacte de lecture/écriture. Avec cette organisation, il est possible d'avoir plusieurs défauts de cache séparés, mais à la condition que chaque défaut accède à une ligne de cache différente. Deux accès simultanés à une même ligne de cache ne sont pas possibles, les défauts de cache secondaires ne sont pas autorisés. Ainsi, chaque défaut de cache se voit attribuer son propre MSHR, chacun contient un numéro de ligne de cache différent.
Pour comprendre pourquoi c'est impossible de gérer les défauts secondaires, il faut regarder le champ de lecture/écriture. Si on veut effectuer plusieurs écritures consécutives à la même adresse, le MSHR n'aura pas de quoi mémoriser les deux données à écrire. Il pourra mémoriser la première donnée à écrire, pas la seconde. Même chose lors d'une lecture : le champ lecture/écriture peut mémorisr la destination de la première lecture, pas de la seconde.
L'avantage est que la MHA n'a besoin que des MSHR et de quelques circuits annexes. Les autres solutions rajoutent des circuits annexes pour gérer les défauts de cache secondaires, qui utilisent beaucoup de circuits. Le cout en circuit est donc élevé, mais le gain en performance est là. Passons maintenant aux caches non-bloquants qui autorisent les défauts de cache secondaire. La solution la plus simple consiste à utiliser
Les MSHR adressés implicitement
[modifier | modifier le wikicode]Avec les MSHR adressés implicitement, il est possible de fusionner plusieurs accès mémoire à une même ligne de cache, mais sous une condition très importante : ces accès lisent/écrivent des mots mémoire différents. Par exemple, imaginons qu'une ligne de cache contienne 8 mots mémoire de 64 bits. Si un premier accès mémoire lit le mot mémoire numéro 9, et le second le mot mémoire numéro 3, alors la fusion est possible. Mais si deux accès mémoire veulent lire/écrire le mot mémoire numéro 8, alors la fusion n'est pas possible et le processeur se bloque, un pipeline stall survient.
Un MSHR adressé implicitement est un MSHR simple, contient naturellement un numéro de ligne de cache et un bit de validité, sauf que le champ de lecture/écriture est dupliqué. Les différents champs lecture/écriture d'un MSHR sont regroupés dans une mémoire RAM/cache qui contient autant d'entrées qu'il y a de mot mémoire dans une ligne de cache. Chaque entrée de la table est associée à un mot mémoire de la ligne de cache et stocke des informations sur celui-ci. Une entrée mémorise, au minimum :
- Un champ de lecture/écriture qui contient soit la destination de la lecture, soit la donnée à écrire.
- Un bit de validité, qui dit si un défaut de cache antérieur accède à ce mot mémoire.
La fusion de deux défauts de cache est ainsi assez simple. Un défaut de cache primaire/secondaire configure l'entrée associée au mot mémoire lu/écrit. Si un défaut secondaire ultérieur lit/écrit un mot mémoire différent, pas de conflit : il configure une autre entrée, vide. Mais s'il lit/écrit un mot mémoire pour lequel l'entrée est occupée, il y a conflit, le processeur est bloqué par un pipeline stall, une bulle de pipeline. Avec cette organisation, le nombre de MSHR indique combien de lignes de cache peuvent être lues en même temps depuis la mémoire. Quant au nombre d'entrées par MSHR, il détermine combien d'accès mémoires qui ne se recouvrent pas peuvent avoir lieu en même temps.
Les MSHR adressés explicitement
[modifier | modifier le wikicode]Les MSHR adressés explicitement n'ont pas les contraintes des MSHR adressés implicitement. Avec eux, il est possible d'avoir plusieurs défauts de cache pointant vers la même ligne de cache, mais aussi vers le même mot mémoire. De tels défauts de cache apparaissent sur les processeurs à exécution dans le désordre, mais sont très rares, voire inexistants, sur les processeurs in-order.
L'idée est encore que chaque MSHR est associée à une table mémoire qui mémorise des entrées. Sauf que cette fois-ci, une entrée n'est pas associée à un mot mémoire. Une entrée est associée à un défaut de cache. Une entrée mémorise là encore la destination de la lecture, un bit de validité par entrée, mais aussi : la position du mot mémoire lu dans la ligne de cache. C'est cette dernière information qui n'était pas présente dans les MSHR adressés implicitement. De plus, le nombre d'entrée par MSHR n'est pas égal au nombre de mots mémoires dans une ligne de cache, mais peut être arbitrairement grand.
Les MSHR inversés
[modifier | modifier le wikicode]Généralement, plus on veut supporter de défauts de cache, plus le nombre de MSHR et d'entrées augmente. Mais au-delà d'un certain nombre d'entrées et de MSHR, les MSHR adressés implicitement et explicitement ont tendance à bouffer un peu trop de circuits. Utiliser une organisation un peu moins gourmande en circuits est donc une nécessité. Cette organisation plus économe se base sur des MSHR inversés.
Les MSHR inversés ne contiennent qu'une seule entrée, en quelque sorte : au lieu d’utiliser n MSHR de m entrées chacun, on va utiliser n × m MSHR inversés. La différence, c'est que plusieurs MSHR peuvent contenir un tag identique, contrairement aux MSHR adressés implicitement et explicitement. Lorsqu'un défaut de cache a lieu, chaque MSHR est vérifié. Si jamais aucun MSHR ne contient de tag identique à celui utilisé par le défaut, un MSHR vide est choisi pour stocker ce défaut, et une requête de lecture en mémoire est lancée. Dans le cas contraire, un MSHR est réservé au défaut de cache, mais la requête n'est pas lancée. Quand la donnée est disponible, les MSHR correspondant à la ligne qui vient d'être chargée vont être utilisés un par un pour résoudre les défauts de cache en attente.
Les MSHR intégrés au cache
[modifier | modifier le wikicode]Certains chercheurs ont remarqué que pendant qu'une ligne de cache est en train de subir un défaut de cache, celle-ci reste inutilisée, et son contenu est destiné à être perdu une fois le défaut de cache résolu. Ils se sont dit que, plutôt que d'utiliser des MSHR séparés, il vaudrait mieux utiliser la ligne de cache pour stocker les informations sur les défauts de cache en attente dans cette ligne de cache.
Pour éviter tout problème, il faut rajouter un bit dans les bits de contrôle de la ligne de cache, qui sert à indiquer que la ligne de cache est occupée : un défaut de cache a eu lieu dans cette ligne, et elle stocke donc des informations pour résoudre les défauts de cache.