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

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

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

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

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

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 caches non bloquants sont de deux types, 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 miss status handling registers

Pour rendre un cache non-bloquant, on n'ajoute pas vraiment de circuits dans le cache lui-même, le cache lui-même n'est pas modifié. En réalité, les caches non-bloquants sont des caches bloquants normaux, auxquels on ajoute des circuits autour, qui servent d'interface entre le processeur et le cache lui-même. Ils sont regroupés sous le terme de Miss Handling Architecture.

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. Leur rôle est de mettre en attente les défauts de cache. Le cache restant le même, il ne peut gérer qu'un défaut de cache à la fois, idem pour le bus mémoire. Charger une ligne de cache depuis la RAM passe effectivement par le bus mémoire, il n'est pas optimisé pour effectuer plusieurs chargements simultanés. Un cache non-bloquant est donc un cache dans lequel un seul défaut de cache s’exécute, mais où les suivants sont en réalité mis en attente dans les MSHR.

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 bien séparer ce qui relève des caches non-bloquants et ce qui relève de la désambiguïsation mémoire, les deux étant assez similaires. Les unités d'accès mémoire peuvent effectuer des accès mémoires dans le désordre, mais mémorisent l'ordre des lectures et écritures, afin de remettre les accès mémoire dans l'ordre. Un cache non-bloquant permet d'effectuer des accès au cache dans le désordre, mais ne conserve pas toujours l'ordre des accès au cache dans les MSHR.

Les accès simultanés à une même ligne de cache

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

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

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

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

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

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.