Fonctionnement d'un ordinateur/La cohérence des caches

Il est possible d'utiliser des caches avec la mémoire partagée, mais aussi sur les architectures distribuées et les architectures NUMA. Néanmoins, la gestion des caches peut poser des problèmes dits de cohérence des caches quand une donnée est présente dans plusieurs caches distincts.

Architecture à mémoire partagée avec des caches.

Architecture distribuée avec des caches.

Introduisons la cohérence des caches par un exemple. Prenons deux cœurs/processeurs qui ont chacun une copie d'une donnée dans leur cache. Si un processeur modifie sa copie de la donnée, l'autre ne sera pas mise à jour. L'autre processeur manipule donc une donnée périmée : il n'y a pas cohérence des caches, sous-entendu cohérence entre le contenu des différents caches.

Or, il faut éviter cela sous peine d'avoir des problèmes. Mais avoir des caches cohérents demande d'avoir une valeur à jour de la donnée dans l'ensemble de ses caches, ce qui implique que les écritures dans un cache doivent être propagées dans les caches des autres processeurs. Il est possible de rendre des caches cohérents avec diverses méthodes qu'on va voir dans ce chapitre. Les deux animations ci-dessous montrent l'exemple de caches non-cohérents et de caches cohérents.

Les problèmes de cohérence des caches se manifestent sur les architecture à mémoire partagée, c'est intuitif. Mais il y en a aussi pour certaines architectures distribuées, notamment sur les architectures NUMA. Et il peut même se manifester avec un seul processeur ! Le processeur fait face à un problème de cohérence de ses caches dès qu'un tier peut écrire dans la RAM, peu importe que le tier soit un autre processeur, un périphérique intégrant un contrôleur DMA, ou quoique ce soit d'autre. Nous avions déjà vu de tels problèmes avec les transferts DMA et les TLBs, mais sans en dire le nom. Par exemple, un transfert DMA modifie des données en RAM, mais les modifications ne sont pas transférées au cache. Pareil pour les TLBs : modifier la table des pages entraine une différence entre le contenu de la TLB et la table des pages en RAM.

Et jusqu'ici, les problèmes de cohérences étaient réglés de deux manières différentes. Avec les transferts DMA, on interdisait la mise en cache pour certains intervalles d'adresse utilisés pour les périphériques. Avec la TLB, on invalidait le contenu de la TLB quand les circonstances l’exigeaient. Il s'agit alors de cohérence par invalidation. La cohérence par invalidation l'avantage d'être simple à implémenter, pour un cout en performance qui dépend de la fréquence des invalidations. Plus les invalidations sont rares, plus le cout en performance est limité.

Les caches ayant peu d'invalidations sont typiquement les TLB et les caches d'instruction. Les caches d'instruction sont utilisés presque uniquement en lecture, car il est très rare de modifier à la volée le code machine d'un programme. Il en est de même avec les TLBs. Modifier le contenu d'une table des pages est peu fréquent, surtout d'une manière qui invalide le contenu d'une TLB. Cela arrive quand une page change de place, pas plus. Aussi, ce sont des candidats parfaits pour la cohérence par invalidation. Mais pour les caches de données, invalider les caches de données à chaque écriture aurait un cout en performance trop important, vu qu'elles sont écrites très souvent. Pour complémenter l'invalidation des caches, les ingénieurs ont inventé des méthodes alternatives spécifiques aux caches de données. Elles permettent de détecter les données périmées et les mettre à jour. Le tout a été formalisé dans des protocoles de cohérence des caches.

Les protocoles de cohérence des caches marquent les lignes de cache comme invalides, si elles ont une donnée périmée. Les lignes de cache invalides ne peuvent pas être lues ou écrites. Toute lecture/écriture d'une ligne de cache invalide entraine un défaut de cache automatique. Les lignes de caches sont alors mises à jour avec une donnée valide. Le rôle d'un protocole de cohérence des caches est de détecter les copies périmées et de les mettre à jour automatiquement. Les problèmes de cohérence des caches surviennent dès qu'on a plusieurs caches dans une architecture parallèle, sauf pour quelques exceptions.

Tout protocole de cohérence des caches doit répondre à plusieurs problèmes.

Premièrement : comment identifier les données invalides ?
Deuxièmement : comment les autres caches sont-ils au courant qu'ils ont une donnée invalide ?
Troisièmement : comment mettre à jour les données invalides ?

Les deux derniers problèmes impliquent une forme de communication entre les caches du processeur. Et pour cela, voyons par quel intermédiaire ils communiquent. Pour rappel, les processeurs/cœurs sont connectés entre eux soit avec un bus partagé, soit avec un réseau d'interconnexion assez complexe. Les deux situations n'utilisent pas les mêmes protocoles de cohérence des caches. Par contre, le premier implique d'associer un état valide/invalide à chaque ligne de cache, et c'est quelque chose d'indépendant de la communication entre processeurs. Voyons le premier problème avant de passer aux deux autres problèmes.

Les états d'une ligne de cache : identifier les données invalides

La cohérence des caches détecte les lignes de cache invalides. Pour cela, chaque ligne de cache a un état qui indique si elles contient une donnée périmée, une donnée valide, ou autre. Les états possibles pour une lignes de cache dépendent du protocole utilisé. Le protocole le plus simple assigne deux états à une ligne de cache : donnée valide, donnée invalide. Mais les protocoles plus élaborés ajoutent d'autres états pour des raisons d'optimisation. Et ces états sont encodés sur quelques bits, ajoutés à chaque ligne de cache.

Au minimum, on trouve un dirty bit par ligne de cache, qui indique si la donnée est invalide ou non, et qui est vérifié lors de chaque lecture. L'ajout d'un dirty bit donne le protocole de cohérence des caches le plus simple qui soit : le protocole SI. Seuls deux états suffisent pour décrire l'état d'une ligne de cache : Valid, qui indique que la ligne de cache est cohérente et Invalid, qui indique que la donnée est périmée. Voici décrit en image le fonctionnement de ce protocole. Un processeur garde une donnée valide tant qu'aucun autre processeur n'écrit dedans. Si cela arrive, la donnée devient invalide et toute lecture/écriture dedans se fait rejeter, un défaut de cache survient. Le processeur envoie alors une transaction sur le bus pour récupérer une donnée valide.

Les protocoles plus réalistes ajoutent deux-trois bits en plus pour coder les autres états. Voyons-les en détail.

Le protocole MSI

La cohérence des caches est très simple quand on a des caches write-trough, mais ces derniers sont à l'origine de beaucoup d'écritures en mémoire qui saturent le bus. Aussi, on a inventé les caches Write-back, où le contenu de la mémoire n'est pas cohérent avec le contenu du cache. Si on écrit dans la mémoire cache, le contenu de la mémoire RAM n'est pas mis à jour. On doit attendre que la donnée sorte du cache pour l'enregistrer en mémoire ou dans les niveaux de caches inférieurs (s'ils existent), ce qui évite de nombreuses écritures mémoires inutiles.

Divers protocoles de cohérence des caches existent pour les caches Write Back. Le plus simple d'entre eux est le protocole MSI. Pour simplifier, il permet à des cœurs de réserver en lecture et écriture des lignes de cache, bien que la réservation soit temporaire. Elles utilise pour cela trois états : Modified, Shared et Invalid. L'état Shared change et correspond maintenant à une donnée à jour, présente dans plusieurs caches. L'état Modified correspond à une donnée à jour, mais dont les copies des autres caches sont périmées. L'état Invalid correspond encore une fois au cas où la donnée présente dans le cache est périmée.

Le protocole permet à un cœur de réserver une ligne de cache/donnée temporairement. Tout part d'une ligne de cache en état Shared, c'est à dire accesible en lecture. Elle n'est pas réservée en écriture, mais elle est consultable par un ou plusieurs cœurs. Soit un seul coeur a chargé la donnée dans son cache, soit d'autres coeurs ont une copie de la donnée dans leur cache, peu importe. La seule contrainte est que l'on sait que tous les coeurs ont la même copie de la donnée, la cohérence des caches est donc respectée. Le protocole de cohérence doit faire en sorte de repasser dans l'état Shared après la moindre violation de cohérence des caches.

Le seul évènement capable de violer la cohérence des caches est la survenue d'une ou de plusieurs écritures. Pour qu'une écriture ait lieu, il faut qu'un cœur réserve la donnée en écriture. Pour cela, le ou les cœurs effectuent une écriture, ils tentent d'écrire dans la donnée voulue. S'il est le seul cœur à vouloir écrire à ce moment, il réservera la ligne de cache automatiquement. Mais si d'autres cœurs veulent modifier la donnée en même temps, une compétition avec les autres cœurs pour la réservation et un seul des cœurs gagnera la course. Quoiqu'il en soit, un cœur réservera la donnée et sa copie de la ligne de cache passe de l'état Shared à l'état Modified. Les autres cœurs voient leur ligne de cache passer de l'état Shared à l'état Invalid.

L'état Modified signifie que le coeur a réussît à réserver la ligne de cache aussi bien en écriture qu'en lecture. Seul lui peut lire ou écrire la donnée à sa guise. L'état Invalid, quant à lui, sert à deux choses. Premièrement, il prévint qu'un autre cœur a réservé la donnée en écriture, ce qui bloque l'écriture dans la ligne de cache par tout autre cœur. Deuxièmement, il bloque aussi les lectures. Il prévint qu'un autre coeur a modifié la donnée, que la ligne contient actuellement une donnée périmée. Tout accès mémoire à une ligne de cache Invalid déclenche alors des mesures correctives afin de rétablir la cohérence des caches. Le contenu de la ligne de cache en état Modified est alors envoyé à tous les autres caches, la cohérence est rétablie, et les lignes de cache passent toutes en état Shared, jusqu’à la prochaine écriture.

Il est possible de modifier le fonctionnement précédent pour tenir compte d'un cas très spécifique : une écriture dans une ligne de cache marquée Invalid. L'écriture est bloquée pour une ligne de cache en état Invalid, car un autre cœur l'a réservée, elle est bloquée en attendant de recevoir la donnée valide. Mais vu qu'elle sera écrasée de toute manière, autant faire passer la ligne de cache directement en état Modified.

L'optimisation est intéressante, mais il faut tenir compte du fait que dans ce cas, on a deux écritures qui se suivent dans le temps, réalisées par deux cœurs, appelons-les cœur 1 et cœur 2. La première écriture, faite par cœur 1, a marqué la ligne de cache comme invalide pour les autres, en Modified pour lui. La seconde, réalisée par le cœur 2, met sa ligne de cache en état Modified pour lui, Invalid pour les autres. Des problèmes de race condition peuvent survenir, le protocole doit gérer ce genre de cas où deux écritures se suivent de près. Dans ce cas, la dernière écriture doit fournir la donnée valide. La donnée qui était en état Modified dans le cœur 1 doit passer en état invalide, il perd la réservation en écriture. Le protocole précédent doit donc être adapté de manière à ajouter deux transitions : une de M vers I si un autre processeur écrit la donnée, et I vers M si le processeur écrit la donnée lui-même.

Notons les trois état M, S et I, pour faire simple. Avec ce système, les lectures sont possibles seulement pour les lignes de cache en état M et S. Toute lecture d'une ligne de cache en état I se termine avec un défaut de cache. Le processeur envoie alors une requête GetS pour récupérer la donnée valide dans les caches d'un autre cœur, une donnée en étant S. L'état I force donc un défaut de cache lors des lectures. Pour les écritures, c'est différent. Les écritures dans une ligne de cache en état M sont automatiquement des succès de cache. Mais les lignes de cache en état S ou I sont traitées autrement. Une telle écriture envoie un signal GetM qui demande à réserver la ligne de cache en écriture. Si la requête est acceptée, la ligne de cache passe en état M, l'écriture est un succès de cache, les autres caches invalident leur copie de la donnée.

Le protocole MESI

Le protocole MSI n'est pas parfait. Un de ses défauts est que l'état 'Shared ne fait pas la différence entre une donnée présente dans un seul cache, et une donnée partagée par plusieurs cœurs. C'est un défaut car toute écriture déclenche des opérations correctives pour gérer la cohérence des caches, qui sont inutiles si un seul cœur a une copie de la donnée. Elles préviennent les autres caches pour rien en cas d'écriture dans une donnée non-partagée. Et les communications sur le bus ne sont pas gratuites.

Pour régler ce problème, on peut scinder l'état Shared en deux états : Exclusive si les autres processeurs ne possèdent pas de copie de la donnée, Shared si la donnée est partagée sur plusieurs cœurs. Le protocole MESI ainsi créé est identique au protocole MSI, avec quelques ajouts. Par exemple, si une donnée est lue la première fois par un cœur, la ligne de cache lue passe soit en Exclusive (les autres caches n'ont pas de copie de la donnée), soit en Shared (les autres caches en possèdent déjà une copie). Une donnée marquée Exclusive peut devenir Shared si la donnée est chargée dans le cache d'un autre processeur.

Comment le processeur fait-il pour savoir si les autres caches ont une copie de la donnée ? Pour cela, il faut ajouter un fil Shared sur le bus, qui sert à dire si un autre cache a une copie de la donnée. Lors de chaque lecture, l'adresse à lire sera envoyée à tous les caches, qui vérifieront s'ils possèdent une copie de la donnée. Une fois le résultat connu, chaque cache fournit un bit qui indique s'il a une copie de la donnée. Le bit Shared est obtenu en effectuant un OU logique entre toutes les versions du bit envoyé par les caches.

Les protocoles MOSI et MOESI

Les protocoles MESI et MSI ne permettent pas de transférer des données entre caches sans passer par la mémoire. Si le processeur demande la copie valide d'une donnée, tous les caches ayant la bonne version de la donnée répondent en même temps et la donnée est envoyée en plusieurs exemplaires ! Pour éviter ce problème, on doit rajouter un état supplémentaire : l'état Owned. Si un processeur écrit dans son cache, il mettra sa donnée en Owned, mais les autres caches passeront leur donnée en version Modified, voire Shared une fois la mémoire mise à jour. Ainsi, un seul processeur pourra avoir une donnée dans l'état Owned et c'est lui qui est chargé de répondre aux demandes de mise à jour.

Divers protocoles de cohérences des caches utilisent cet état Owned. Le premier d’entre eux est le protocole MOSI, une variante du MESI où l'état exclusif est remplacé par l'état O. Lors d'une lecture, le cache vérifie si la lecture envoyée sur le bus correspond à une de ses données. Mais cette vérification va prendre du temps, et le processeur va devoir attendre un certain temps. Si au bout d'un certain temps, aucun cache n'a répondu, le processeur postule qu'aucun cache n'a la donnée demandée et va lire la donnée en mémoire. Ce temps est parfois fixé une fois pour toute lors de la création des processeurs, mais il peut aussi être variable, qui est géré comme suit :

pour savoir si un cache contient une copie de la donnée demandée, chaque cache devra répondre en fournissant un bit ;
quand le cache a terminé la vérification, il envoie un 1 sur une sortie spécifique, et un 0 sinon ;
un ET logique est effectué entre tous les bits fournis par les différents caches, et le résultat final indique si tous les caches ont effectué leur vérification.

On peut aussi citer le protocole MOESI, un protocole MESI auquel on a jouté l'état O.

La cohérence des caches par espionnage du bus

L'espionnage du bus est la technique de cohérence du cache la plus simple à comprendre, du moins sur le principe. Aussi, nous allons la voir en premier. Avec elle, les caches sont reliés à bus partagé, qui communique avec les niveaux de cache inférieurs ou avec la RAM. Faisons d'abord un rappel sur ce qu'est ce bus partagé.

Les bus partagés : rappels et implémentation de la cohérence des caches

Le premier cas est celui où plusieurs processeurs/cœurs sont connectés à la mémoire RAM à travers un bus partagé. Les processeurs disposent d'une mémoire cache chacun et ils sont tous reliés à la mémoire RAM à travers le bus mémoire. Dans ce cas, tous les caches ont connectés au bus mémoire, qui sert de point de ralliement. Sans cohérence des caches, les communications se font dans le sens cache -> mémoire ou mémoire -> cache. L'idée est alors de rajouter les communications cache- -> cache sur le bus mémoire. La mémoire ne répond pas forcément à de telles communications.

L'idée marche très bien, mais il faut l'adapter sur les processeurs multicœurs, qui ont une hiérarchie de cache assez complexe. Les caches partagés entre tous les cœurs ne posent aucun problème de cohérence car, avec eux, la donnée n'est présente qu'une seule fois dans tout le cache. Par contre, il faut gérer la cohérence entre caches dédiés.

Cohérence et caches partagés. Vous remarquerez que sur le schéma, la mémoire RAM contient encore une autre version de la donnée car on utilise un cache *Write Back*).

Le cas le plus simple est celui à deux niveaux de caches, avec des caches L1 dédiés et un cache L2 partagé entre tous les cœurs. Les caches L1 sont reliés au cache L2 partagé par un bus, qui n'a souvent pas de nom. Nous désignerons le bus entre le cache L1 et le cache L2 : bus partagé, sous-entendu partagé entre tous les caches. Sans cohérence des caches, les transferts sur ce bus se font des caches L1 vers le cache L2 partagé, ou dans l'autre sens. Là encore, l'idée est de faire communiquer les caches L1 via le bus partagé.

Dans ce qui va suivre, quand nous parlerons de bus partagé, cela voudra dire : soit on parle du bus entre le L1 et le L2 sur un processeur multicœur, soit on parle du bus mémoire sur une architecture multi-processeur/multicœurs avec des caches dédiés. L'idée est que ce bus partagé existe avec ou sans cohérence des caches. Sans cohérence, il permet d'échanger des données entre deux niveaux de la hiérarchie mémoire : cache L1 vers L2, caches vers mémoire. Avec cohérence, le bus partagé interconnecte les caches entre eux.

La mise à jour et l'invalidation sur écriture

Les protocoles à espionnage du bus sont des protocoles où les transmissions entre caches se font sur le bus partagé. Le nom qui trahit l'idée qui se cache derrière cette technique : les caches interceptent les écritures sur le bus partagé, qu'elles proviennent ou non des autres processeurs. Quand un cœur/processeur écrit une donnée dans son cache L1, un signal est envoyé sur le bus partagé pour prévenir les autres caches, afin qu'ils invalident la ligne de cache concernée. De plus, il faut aussi mettre à jour les copies en question avec une donnée valide, ce qui passe là-encore par le bus partagé.

Voyons d'abord comment la mise à jour des copies se fait. La solution la plus simple pour cela est de propager les écritures dans les niveaux de cache inférieurs, jusqu'à la mémoire. L'écriture est alors transmise sur le bus partagé, les autres caches ont juste à récupérer la donnée et l'adresse écrite. Si l'adresse match une ligne de cache, la ligne de cache est mise à jour immédiatement avec la donnée envoyée sur le bus partagé. Le cache est alors mis à jour immédiatement, la ligne de cache n'a même pas le temps d'être invalidée. On parle alors de mise à jour sur écriture. Avec elle, les caches sont mis à jour automatiquement le plus tôt possible, il n'y a pas d'invalidation proprement dit.

La solution la plus simple pour cela est d'utiliser des caches write through, qui propagent toute écriture dans les niveaux de cache inférieurs, jusqu'à la mémoire. Toute écriture dans une ligne de cache déclenche alors une mise à jour. Mais l'impact sur le débit binaire est alors très important. Aussi, la plupart des processeurs préfèrent utiliser des caches write back pour gagner en performance. Dans ce cas, les écritures qui sont propagées dépendent de l'état de la ligne de cache écrite. Écrire dans une ligne de cache en état Exclusive ne déclenchera pas de mise à jour, par exemple. Seules les écritures dans des lignes de cache en état Modified et Shared le feront.

Mais il est aussi possible de ne pas mettre à jour les lignes de cache à chaque écriture, et de préférer attendre. A la place, l'écriture est remplacée par un signal d'invalidation qui transmet uniquement l'adresse écrite et n'est pas pris en compte par le cache L2/L3 partagé. Il prévient les autres caches que telle ligne de cache a été modifiée et qu'il faut en invalider les copies. Le cache se contente de marquer la ligne de cache fautive comme invalide, mais ne la met pas à jour. Il y a alors invalidation sur écriture. La ligne de cache est mise à jour lors d'une lecture/écriture. Tout accès à une ligne de cache invalide entraine un défaut de cache et la donnée est chargée depuis la RAM et/ou depuis un autre cache.

Les deux techniques précédentes différent sur un point : la première met à jour la ligne de cache immédiatement, la seconde attend que la ligne de cache soit lue/écrite avant de mettre à jour, elle le fait au dernier moment. Le temps d'accès à une donnée est donc plus long avec ces derniers. Avec la mise à jour sur écriture, la donnée est mise à jour tout de suite, les accès ultérieurs ne déclenchent pas de défaut de cache, la donnée est accesible directement. Le temps d'accès moyen est donc plus faible.

Par contre, une partie des mises à jour sont inutiles, car les autres processeurs ne liront pas la donnée ou alors pas tout de suite. Avec l'invalidation, on met à jour les lignes de cache quand la donnée est lue, quand elle est réellement utilisée. Vu qu'une mise à jour est plus gourmande en énergie qu'une simple invalidation, on n'est pas forcément gagnant. Une mise à jour demande un accès complet au cache, avec écriture dans le plan mémoire. Alors d'une invalidation demande simplement de modifier les bits de contrôle d'une ligne de cache.

De nos jours, les caches utilisent l'invalidation sur écriture pour des raisons de complexité d'implémentation. Les protocoles à mise à jour sur écriture sont plus complexes à implémenter pour de sombres raisons de consistance mémoire.

La mise à jour en cas d'invalidation sur écriture

Avec l'invalidation sur écriture, la mise à jour des lignes de cache se fait séparément de l'invalidation. Et dans ce cas, il faut trouver où se trouve la donnée valide. La donnée valide est présente soit dans le cache d'un autre processeur, soit dans la mémoire RAM. La donnée valide est copiée depuis cette source, c'est une simple transaction mémoire. Voyons ce qu'il en est.

Le cas le plus simple est celui où plusieurs processeurs ont un cache chacun et sont reliés à une mémoire partagée. L'implémentation la plus simple lit la donnée valide depuis la RAM. Elle utilise alors des caches de type write-through, où les écritures sont propagées la mémoire RAM. Il est possible de faire la même chose avec un cache write-back, cependant. Mais il doit se comporter comme un cache write-through en propageant des écritures dans certaines situations. Dès qu'il écrit une ligne de cache en état Modified ou Shared, il propagera l'écriture dans la RAM. Par contre, s'il a une ligne de cache en état Exclusive, il n'a pas à propager les écritures dans le niveau de cache inférieur, il n'a pas à générer de signal d'invalidation du tout.

Une autre solution fait une copie depuis le cache qui contient la donnée valide, sans passer par la mémoire RAM. Les copies entre caches passent par le bus mémoire, la différence étant que la mémoire ne répond pas forcément à des transferts. Les caches étant plus rapides que la RAM, les copies entre caches sont plus rapides qu'un accès en mémoire RAM, même si les deux utilisent le même bus. L'état Owned permet d'optimiser cette situation : c'est le cache en état Owned qui répond alors à la requête mémoire.

Sur les architectures multicœurs, le cache partagé prend la place de la mémoire RAM et le bus partagé celui du bus mémoire. En général, les caches L2 sont inclusifs, à savoir que toute donnée écrite dans les caches L1 est présente dans le cache L2. La donnée valide est donc généralement lue depuis le cache partagé L2/L3.

Quand un cache a besoin d'une donnée valide, il envoie une requête de mise à jour, qui demande aux autres caches s'ils ont une donnée valide. La donnée valide est en état Modified ou Owned. Si un cache a une donnée dans cet état, il répond aux requêtes de mise à jour en envoyant la donnée voulue, éventuellement avec l'adresse. Le cache demandeur reçoit la donnée et met à jour sa ligne de cache. Les autres caches ne tiennent pas forcément compte de cette mise à jour. Du moins, pas avec "invalidation sur écriture" pure, mais certains caches sont un peu plus opportunistes et en profitent pour mettre à jour la ligne de cache au cas où. On peut les voir comme des intermédiaires entre invalidation et mise à jour sur écriture.

La cohérence des caches à base de répertoires

La cohérence des caches à base de répertoire utilise un répertoire, qui mémorise l'état de chaque ligne de cache, mais aussi quel processeur dispose de telle ou telle ligne de cache. Les processeurs envoient des requêtes au répertoire avant chaque accès au cache. Le répertoire va alors soit répondre favorablement et autoriser l'accès au cache, soit l'interdire. Une réponse favorable signifie que le processeur a une donnée valide, une réponse défavorable signifie que la ligne de cache accédée doit être mise à jour. La cohérence des caches est donc gérée par le répertoire, qui est centralisé.

L'usage d'un répertoire est la norme sur les architectures NUMA, avec plusieurs ordinateurs reliés entre eux. Avec l'arrivée des processeurs multicœurs avec une hiérarchie de cache, les architectures à mémoire partagée se sont mises à s'inspirer des protocoles à répertoire pour gagner en performance. L'usage de caches de répertoire a permis d'utiliser la technique sur les processeurs multicœurs normaux, en complément de l'espionnage du bus.

L'usage des répertoires sur les architectures NUMA

Plusieurs architectures différentes utilisent une cohérence des caches par répertoire. Leur usage le plus intuitif est celui des architectures NUMA, avec plusieurs ordinateurs reliés entre eux via réseau. Sur les architectures NUMA, une donnée lue depuis la RAM d'un autre ordinateur peut être mise en mémoire cache. Et la moindre modification d'une copie doit être propagée via réseau sur les autres ordinateurs. Autant dire que la cohérence des caches est assez compliquée sur de telles architectures. Avec elles, chaque ordinateur a une copie du répertoire, pour gérer les données provenant des mémoires des autres ordinateurs.

Les répertoires sont utilisés sur les architectures NUMA. Rappelons que sur de telles architectures, chaque processeur a une mémoire dédiée, mais qu'il a accès à toutes les mémoires de l'architecture à travers un réseau local. La mémoire dédiée au processeur est appelée la mémoire locale, alors que celles des autres processeurs sont appelées les mémoires distantes. Une partie de l'espace d'adressage est associé à la mémoire locale, mais le reste de l'espace d'adressage est associé aux mémoires distantes. Quand le processeur veut lire/écrire dans sa mémoire locale, le répertoire n'est pas consulté. Mais quand il veut lire/écrire en dehors, le répertoire est consulté pour gérer la cohérence des caches.

Espace d'adressage d'une architecture NUMA.

Voyons maintenant comment le tout fonctionne. Nous allons prendre l'architecture illustrée ci-dessous. Elle contient plusieurs ordinateurs, chacun avec une mémoire locale reliée à un ou plusieurs processeurs multicœur aux hiérarchies de caches complexes. Nous n'allons pas nous intéresser aux caches L1/L2/L3, mais allons nous concentrer sur la mémoire cache L4, partagée entre plusieurs processeurs.

Il s'agit d'une mémoire cache spécialisée dans les accès aux mémoires distantes. Elle contient des données provenant des mémoires distantes, qui ont été chargées lors d'accès antérieurs. Nous allons l'appeler le cache distant pour simplifier les explications. Les accès aux mémoires distantes se font via le réseau local d'interconnexion, mais le résultat des lectures est mémorisé dans le cache distant, ce qui évite de faire un accès réseau à chaque lecture/écriture. Le répertoire est consulté pour tout accès au cache distant, mais n'est pas consulté pour l'accès aux caches L1/L2/L3 gérés par espionnage de bus. Il l'est seulement quand un ordinateur veut accéder aux données d'une mémoire distante, lors d'un accès en dehors de l'espace d'adressage de la mémoire locale.

Pour comprendre comment le répertoire et le cache L4 sont utilisés, partons du principe qu'un processeur veuille lire une donnée située dans une mémoire distante. Le cache L4 ne contient pas la donnée en question, ce qui déclenche un défaut de cache. Une transaction réseau est alors démarrée, pour rapatrier la donnée dans le cache L4. Le rapatriement peut simplement lire la donnée dans la mémoire principale si elle n'a pas été cachée, mais elle peut aussi aller la chercher dans les caches du processeur distant si nécessaire (comme illustré ci-dessous). Les répertoires sont alors mis à jour sur tous les ordinateurs. Le répertoire permet de désigner quel processeur a une copie de la donnée voulue, et d'aller la chercher sans demander à tous les processeurs.

Intuitivement, on se dit que les futurs accès à cette donnée rapatriée se font dans le cache L4. Mais dans les faits, la donnée peut être copiée dans le cache L3/L2, voire L1 du processeur local. Maintenant, imaginons que le processeur local modifie cette donnée distante. Les protocoles de cohérence des caches par espionnage de bus propagent un signal d'invalidation jusque dans le cache L4. Il faut ensuite propager le signal d'invalidation aux autres ordinateurs qui manipulent cette donnée. Pour cela, le répertoire est consulté pour récupérer la liste des processeurs qui ont cette donnée dans leur cache. Le signal d'invalidation est ensuite transmis par le réseau d'interconnexion, et arrive aux destinataires, qui invalident la donnée dans leurs caches.

L'usage de répertoire sur les architectures multiprocesseurs et multicœurs

L'espionnage de bus est simple à implémenter. Mais il a un défaut assez flagrant : les signaux d'invalidation et les requêtes de mise à jour passent par le bus partagé, idem pour les réponses à des signaux/requêtes. Le trafic sur le bus partagé est donc augmenté, assez fortement. Et au-delà de quelques processeurs, le trafic est trop important. L'usage d'état Owned et Exclusive améliore la situation, mais pas de quoi faire des miracles. Le problème de l'espionnage de bus est que les signaux et requêtes sont envoyés à tout le monde, grâce à l'usage d'un bus partagé. Et un bus partagé est une forme assez rudimentaire d'interconnexion, qui devient inefficace dès que le nombre de composants à connecter dessus est trop important.

De nos jours, les processeurs multicœurs récents remplacent partiellement le bus partagé par un réseau d'interconnexion intra-processeur plus complexe qu'un simple bus. De même, les cartes mères multi-processeurs incorporent un réseau d'interconnexion inter-processeur, placé sur la carte mère, pour connecter les processeurs, la mémoire et les autres entrées-sorties. Le tout est illustré ci-dessous et vous remarquerez que le tout ressemble un peu à une architecture NUMA mais sans mémoire RAM, la RAM étant accédée via le réseau d'interconnexion comme l'est le GPU ou un cœur/processeur. Mais cela ne fait pas grande différence, car l'essentiel est que les mémoires caches soient là, de même que le réseau d'interconnexion. Les systèmes multicœurs/multiprocesseurs utilisent l'espionnage du bus à l'intérieur d'un cœur/processeur, mais utilisent la cohérence basée sur un répertoire entre les processeurs/cœurs.

Dans ce qui suit, le réseau d'interconnexions entre processeurs/cœurs sera volontairement laissé vague, car il peut être absolument n'importe quoi : un bus partagé, un réseau en anneau, un réseau crossbar, etc. Par contre, il doit donner l'illusion que chaque cache est connecté à tous les autres via un ensemble de liaisons point-à-point. Il n'y a pas une transmission à la fois, plusieurs transmissions entre processeurs/cœurs peuvent avoir lieu en même temps. Les signaux d'invalidation sont envoyés uniquement aux processeurs/cœurs qui ont une copie de la donnée, pas à tous. Idem pour les requêtes de mise à jour, envoyées seulement au cache qui a une copie valide de la donnée. De fait, les transmissions pour la cohérence peuvent se faire en même temps que d'autres lectures/écritures normales, ce qui fait meilleur usage du débit mémoire.

Prenons comme exemple la situation du schéma précédent, où chaque cœur dispose d'un seul cache dédié, et voyons comment est gérée la cohérence des caches sur un tel processeur. Tout écriture dans le cache dédié entraine l'émission d'un signal d'invalidation pour préciser que la ligne de cache a été modifiée. L'envoi du signal d'invalidation est cependant géré par le répertoire, qui décide quels cœurs prévenir. Le répertoire configure alors le réseau d'interconnexion pour connecter entre eux les caches qui doivent l'être, pour propager les signaux d'invalidation et les requêtes de mise à jour. Les autres caches sont laissés libres et sont disponibles pour des lectures et écritures. On économise alors du débit binaire, au prix d'une perte en temps d'accès liée à l'interrogation du répertoire.

Prenons ensuite le cas d'une lecture dans un cache dédié, illustré ci-dessous. Si un défaut de cache a lieu, alors la ligne de cache n'est pas disponible dans le cache dédié. Elle doit alors être rappatriée depuis la mémoire RAM dans le pire des cas, ou depuis un autre cache. Pour savoir dans quel cas il est, le cœur interroge le répertoire. Il sait si la ligne mémoire est cachée ou non, et dans quel cache elle se trouve si elle l'est. Le répertoire démarre alors une requête de lecture au cache adéquat, via une transaction réseau. Le cache adéquat répond à la transaction par une autre transaction réseau, à destination du cœur qui a déclenché le défaut de cache. Là encore, les trois requêtes sont envoyées uniquement aux cœurs/caches qui en ont besoin.

Le contenu du répertoire : les implémentations à base de RAM et de caches

Avant de poursuivre, un point de terminologie. Imaginez que la mémoire est découpée en blocs qui font la même taille qu'une ligne de cache, et qui sont alignés sur cette taille. Un bloc peut être copié dans le cache, éventuellement écrit par le processeur, et rapatrié en mémoire RAM une fois évincé du cache. Le bloc de mémoire sera appelé dans ce qui suit une ligne mémoire, par analogie avec une ligne de cache. Un répertoire mémorise, pour chaque ligne mémoire, la liste des processeurs dont le cache qui en a une copie. Il peut aussi mémoriser l'état de la ligne de cache associée, mais ce n'est pas obligatoire, l'état peut être stocké dans la ligne de cache elle-même.

Les répertoires basés sur une mémoire RAM

L'implémentation la plus simple mémorise, pour chaque ligne mémoire, quel processeur l'a copié dans son cache. Pour cela, elle utilise un bit de présence par processeur, qui indique si le cache du processeur a une copie de la ligne mémoire : le énième bit de présence indique si le énième processeur a la ligne mémoire dans son cache. Elle a pour défaut de rapidement faire grossir le répertoire, dont la taille est proportionnelle au nombre de processeurs et de ligne mémoire.

Une autre solution mémorise la liste des processeurs autrement. Au lieu d'utiliser un bit par processeur, elle mémorise une liste de pointeurs vers ces processeurs. Elle attribue un numéro à chaque processeur et mémorise une liste de plusieurs numéros. L'avantage est que les numéros sont assez courts. Au lieu d'utiliser N bits pour N processeurs, chaque numéro ne fait que $\log _{2}{N}$ . On gagne en mémoire si on autorise C copies, et que $C\times \log _{2}{N}\leq N$ . Un exemple sera sans doute plus parlant. Prenons 256 processeurs. Un répertoire complet demandera 256 bits. Une liste de pointeurs encodera un numéro de processeur sur 8 bits, on est gagnant tant qu'on a moins de 256/8 = 32 processeurs par ligne de cache.

Par contre, la technique n'autorise qu'un nombre maximal de numéros par ligne mémoire. Si ce nombre est dépassé, le répertoire doit gérer la situation. Et il y a plusieurs solutions possibles pour cela. La première n'autorise réellement que N copies d'une même ligne de cache et invalide les copies en trop si le nombre est dépassé. Le cout en performance est cependant élevé. Les deux autres solutions autorisent à dépasser le nombre maximal de numéros. La première se débrouille en repassant en mode broadcast une fois le nombre de numéro maximal dépassé. Le répertoire envoie alors toute invalidation de la ligne mémoire concernée à tous les processeurs, vu que le répertoire n'a pas les moyens de savoir qui a une copie valide ou non. Une autre solution déclenche une exception matérielle qui gère la situation en logiciel.

Répertoire complet et à liste de pointeur
	Adresse	État	Liste des processeurs
Représentation complète	0xFFF1244	Shared	0001 1000 0001 1100
Liste de pointeurs	0xFFF1244	Shared	3, 4, 5 12, 13

Les deux méthodes précédentes posent problème quand le nombre de processeur est élevé. Aussi, quelques optimisations permettent de limiter la casse. La première consiste à ne pas encoder toutes les informations nécessaires. Une idée possible est par exemple de regrouper les caches/processeurs par groupes de 2/3/4. Le répertoire mémorise alors quel groupe de cache/processeur contient une copie de la donnée, mais pas exactement quel cache dans ce groupe. Par exemple, avec des groupes de 2, il se peut qu'un processeur du groupe ait une copie de donnée, ou les deux, le répertoire ne fait pas la différence. Si la donnée est invalidée, il envoie des signaux d'invalidation aux deux processeurs du groupe.

Les répertoires vus plus haut sont basés sur une mémoire RAM. Elle contiennent une adresse par le ligne mémoire, l'adresse contient l'état de la ligne de cache et la liste des processeurs. La consultation du répertoire demande juste d'adresser le répertoire avec l'adresse de la ligne mémoire, ce qui peut être fait avant ou en parallèle de l'accès au cache. Mais le problème est que le répertoire est alors une mémoire très grosse. Elle est d'autant plus grosse qu'il y a de lignes mémoires et elle devient rapidement impraticable dès que la mémoire est un peu grosse.

Les répertoires basés sur une mémoire cache

Le répertoire est donc une structure assez grosse, ce qui est un problème. En pratique, les répertoires précédents sont tellement gros qu'on ne peut pas leur dédier une mémoire RAM. des tables qui sont mémorisées en mémoire RAM. Quelques processeurs ont réussit à le faire, notamment les premiers SGI Origin, qui avaient une banque de mémoire dédiée au répertoire. Mais la majeure partie des implémentations devaient placer le répertoire dans la mémoire RAM principale de l'ordinateur, un peu au même titre que la table des pages.

Mais quoi bon avoir des caches si leur accès demande de consulter un répertoire en mémoire RAM ? Et pourtant, nous avons déjà vu une situation similaire. Il est possible de faire une analogie avec la table des pages, encore que celle-ci soit grandement limitée. La table des pages est là aussi une structure très grosse, censée être consultée à chaque accès mémoire, qui mémorise des informations pour chaque page mémoire. Le répertoire est une structure similaire : remplacez ligne mémoire par page mémoire et vous aurez l'idée. Et vous vous souvenez certainement de la solution utilisée, à savoir l'usage de caches de traduction d'adresse, les fameuses TLBs.

Les caches en question sont appelés des caches de répertoire. Ils ont plusieurs entrées, mais moins qu'il n'y a de lignes mémoire. Une entrée peut être vide ou occupée. Une entrée occupée mémorise de quoi gérer la cohérence pour une ligne mémoire. Elle mémorise l'adresse de la ligne mémoire, l'état de la ligne et la liste des processeurs. Le cache de répertoire mémorise une partie du répertoire, celle en cours d'utilisation.

L'implémentation la plus simple conserve un répertoire en mémoire RAM, complété par un cache de répertoire par processeur. Les caches de répertoire sont consultés à chaque écriture, ce qui n'est pas un problème vu qu'ils sont très petits et ont un temps d'accès minuscule. Il y a plusieurs caches de répertoire, avec plusieurs niveaux de cache. Typiquement, il y a un cache de répertoire L1 associé au cache L1 de données, un cache de répertoire L2 pour le cache de données L2, etc.

Il faut cependant remarquer que le répertoire est une structure dont la majorité des entrées sont vides. En effet, les seules entrées occupées correspondent aux lignes mémoires présentes dans le cache du processeur. Il n'y a pas besoin de mémoriser autant d'entrées qu'il y a de lignes mémoires, seulement une entrée par ligne de cache. Cette simplification donne un répertoire très petit, dans lequel on a éliminé les entrées vides. Il s'agit d'une optimisation évident à laquelle vous aviez peut-être déjà pensé. Le tout est nommé avec le nom de inclusive directory cache, que nous traduirons par cache de répertoire inclusif.

Il existe deux implémentations possibles de ce cache de répertoire inclusif. La première place le répertoire dans un cache dédié, séparé des autres caches, associé au contrôleur mémoire. Le fonctionnement est alors le suivant. Pour toutes les lignes mémoires dans le cache, le cache de répertoire possède une entrée associée, qui mémorise une copie tag de la ligne de cache et la liste des processeurs. Le tag en question n'est autre que le tag utilisé dans le cache L1 (si on suppose que le L2 est partagé). Si jamais la ligne mémoire n'est pas trouvée dans ce cache, alors on suppose qu'elle est en état Invalid, ou qu'elle n'a pas été chargée depuis la mémoire. Les actions correctives sont les mêmes dans les deux cas. Un défaut est que lorsqu'une ligne de cache est évincée du cache L1, le répertoire doit être prévenu, ce qui ajoute de la complexité. En théorie, le cache devrait être un cache associatif par voie, avec un grand nombre de voies pour gérer des accès simultannés.

Une autre implémentation utilise des caches L1/L2 inclusifs. Ainsi, le répertoire a juste à mémoriser les lignes mémoires dans le cache partagé L2/L3. Mieux : il a juste à mémoriser la liste des processeurs dans la ligne de cache elle-même ! L'implémentation précédente recopiait les tag dans le répertoire, ce qui les dupliquait. Mais on n'avait pas le choix, car il fallait regrouper les tags des différents L1 dans un répertoire unique, on ne pouvait pas avoir un répertoire dispersé dans plusieurs caches L1. Mais avec des caches inclusifs, faire pareil avec les lignes de cache du L3 serait de la duplication inutile. Alors on fusionne le cache partagé L2/L3 avec le cache de répertoire. La difficulté est alors de maintenir des caches inclusifs, ce qui est plus compliqué que prévu.

Une autre solution consiste à mémoriser la liste des copies dans les caches eux-mêmes. Le répertoire n'identifie, pour chaque ligne de cache, qu'un seul processeur : plus précisément, il identifie la ligne de cache du processeur qui contient la copie. À l'intérieur d'une ligne de cache, la copie suivante (si elle existe) est indiquée dans les bits de contrôle. On parle de répertoires à base de caches.

Les avantages et inconvénients des deux méthodes

L'avantage de l'espionnage du bus est qu'il utilise peu de circuits et qu'il est facile à implémenter, car il réutilise un bus partagé qui est déjà là. Par contre, son désavantage majeur est que les écritures dans un cache sont propagées sur le bus partagé, au moins partiellement. Soit les écritures sont réellement propagées sur le bus partagée, soit un message d'invalidation est envoyé sur le bus partagé, peu importe : un message est envoyé aux autres caches pour dire qu'une écriture a eu lieu et qu'il faut potentiellement invalider des données. Le débit binaire du bus partagé est donc partiellement grignoté par les communications entre caches. Et le désavantage est d'autant plus grand qu'il y a de coeurs/processeurs, qui se partagent le bus partagé.

L'usage d'un répertoire résout ces problèmes. Le débit binaire du bus partagé n'est pas grignoté, car la liaison entre caches et répertoires est séparée. Par contre, le temps d'accès au cache est augmenté, car tout accès mémoire demande l'autorisation au répertoire. En soi, le problème est compensé par l'économie en débit binaire. Sur les architectures avec beaucoup de processeurs, le gain en débit binaire sur-compense la hausse du temps d'accès. Mais sur les architectures avec peu de cœurs, c'est l'inverse. En général, les architectures distribuées/NUMA utilisent des répertoires, alors que les architectures à mémoire partagée utilisent l'espionnage du bus. Le tout est résumé ci-dessous.

	Mémoire partagée	Architectures NUMA	Architecture distribuée
Invalidation du cache	Caches d'instruction et TLB
Espionnage du bus	X
Répertoire de cohérence	X	X	X

Remarquez que l'espionnage du bus n'a de sens que sur les architectures à mémoire partagée, alors que l'usage de répertoire est plus générale.

◄ Retour vers « Les architectures parallèles exotiques »

Sommaire du livre

Continuer vers « Les sections critiques et le modèle mémoire » ►