Fonctionnement d'un ordinateur/La cohérence des caches
Introduisons la cohérence des caches par un exemple. Prenons deux 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.
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. Sur les architectures NUMA, une donnée lue depuis la RAM d'un autre ordinateur peut être mise en mémoire cache. Une donnée peut être présente dans les caches de plusieurs ordinateurs. Et la moindre modification sur l'ordinateur initial 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.
 |
 |
Le problème des architectures multicoeurs n'en est qu'un exemple. 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 deux méthodes de cohérence des caches : par répertoire ou par espionnage du bus
[modifier | modifier le wikicode]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 trois problèmes impliquent une forme de communication entre les caches du processeur. Et pour cela, voyons par quel intermédiaire ils communiquent. Deux grandes solutions sont possibles : l'usage d'un bus déjà existant, l'ajout d'une nouvelle structure.
Les protocoles à espionnage du bus
[modifier | modifier le wikicode]Une première solution fait un meilleur usage du matériel existant, sans rajouter de répertoire dédié pour la cohérence des caches. Le matériel existant est un bus qui est partagé avec tous les caches. Et là, deux cas sont possibles. Le premier est celui d'une architecture où chaque processeur dispose de sa mémoire cache, tous reliés à la mémoire RAM. 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. Un processeur multicœur typique a une architecture avec trois niveaux de cache : L1, L2 et L3. Pour simplifier les explications, on va partir qu'il y a deux niveaux de caches : chaque processeur a un cache L1, mais le cache L2 est partagé entre tous les cœurs. 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.
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 technique présentée dans le paragraphe précédent porte le nom d'espionnage du bus, un 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.
Les protocoles à répertoire
[modifier | modifier le wikicode]Une solution alternative ajoute un circuit séparé qui prend en charge la cohérence des caches. Le circuit séparé est appelé un répertoire. Il mémorise, pour chaque ligne de cache, si elle contient une donnée valide ou invalide. De plus, il connait, pour chaque donnée, la liste des processeurs qui ont une copie de la donnée dans leur cache. A chaque fois qu'un processeur veut lire ou écrire une donnée dans le cache, il consulte ce répertoire pour savoir si la ligne de cache est valide ou non. Si la ligne est valide, l'accès est autorisé. Mais si elle est invalide, le répertoire redirige l'accès au cache qui contient la donnée valide, et la donnée est alors lue/écrite dans ce cache.
Avec un répertoire centralisé', on a un répertoire unique pour tous les processeurs. À chaque défaut de cache, le répertoire est consulté pour localiser la copie valide, pour la mettre à jour. Le répertoire doit répondre aux demandes de tous les processeurs et devient rapidement un goulot d'étranglement quand les défauts de cache sont nombreux. La solution est utilisée pour un nombre de processeurs assez limités, disons moins d'une dizaine.
Avec un répertoire décentralisé, il y a plusieurs répertoires qui fonctionnent plus ou moins indépendamment les uns des autres. Le répertoire centralisé est alors dispersé dans plusieurs répertoires séparés. Les répertoires communiquent entre eux via le réseau d'interconnexion qui connecte les caches entre eux. La version la plus décentralisée possible utilise un répertoire pour chaque processeur. Elle est très utilisée sur les architectures NUMA et COMA.
Mais il y a des cas intermédiaires où le répertoire est réparti dans un arbre. Chaque répertoire (nœud) indique quel sous-arbre il faut vérifier pour obtenir la donnée demandée. Avec cette méthode, le répertoire utilise peu de bits (de mémoire) pour mémoriser les informations nécessaires. Mais le nombre d'accès mémoire peut rapidement dépasser celui obtenu avec les autres solutions.
Les avantages et inconvénients des deux méthodes
[modifier | modifier le wikicode]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.
Les états d'une ligne de cache : identifier les données invalides
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]
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
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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. Une écriture dans un cache déclenche une transmission sur le bus partagé, afin de prévenir les autres caches pour invalider les copies de la ligne de cache modifiée. De plus, il faut aussi mettre à jour les copies en question avec une donnée valide.
La mise à jour et l'invalidation sur écriture
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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. Aussi, les protocoles à répertoire sont utilisés au-delà d'un certain nombre de processeurs. Ils sont aussi utilisés sur les architectures distribuées, où il n'y a pas de bus qui connecte la mémoire à tous les autres processeurs, ce qui rend les protocoles à base d'espionnage de bus inopérants.
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é. Avec un répertoire, le réseau d'interconnexions entre mémoire et caches sont volontairement laissées vagues, et elle peut être absolument n'importe quoi : un bus partagé, un réseau en anneau, un réseau crossbar, peu importe. Par contre, il doit donner l'illusion que chaque cache est connecté à tous les autres via un ensemble de liaisons point-à-point. Et il peut être implémenté avec de telles liaisons point-à-point, même si cela ne tient pas la route dès qu'on dépasse les 2 à 4 caches.
L'essentiel est que les caches peuvent communiquer indépendamment. Un cache peut envoyer une donnée à un autre, sans que cela bloque la transmission entre deux autres caches. Il n'y a pas une transmission à la fois, plusieurs transmissions entre caches peuvent avoir lieu en même temps. Et l'idée est que les signaux d'invalidation sont envoyés uniquement aux caches 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 transmission 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.
Avec un répertoire, 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. 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 à ceux qui en ont besoin. 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.
Le répertoire, version centralisée et décentralisée
[modifier | modifier le wikicode]Un répertoire est une table de correspondance qui mémorise, pour chaque ligne de cache, toutes les informations nécessaires pour maintenir sa cohérence. Ce répertoire mémorise :
- l'état de la ligne de cache (exclusive, shared, invalid, empty, etc) ;
- la liste des processeurs dont le cache contient une copie de la ligne de cache.
Avec les répertoires centralisés, le répertoire doit mémoriser la liste des processeurs qui contiennent la donnée invalide, afin de les prévenir qu'ils doivent invalider la ligne de cache. Dans le cas le plus simple, le répertoire est une mémoire RAM, dont chaque entrée (chaque byte) mémorise les informations pour une ligne de cache : on parle de répertoire basé sur une mémoire.
Il existe plusieurs manières d'implémenter un répertoire basé sur une mémoire, mais toutes mémorisent une liste de lignes de cache, associée chacune à l'état de la ligne de cache. La plus simple mémorise, pour chaque ligne de cache, quel processeur dispose de la ligne de cache. Pour cela, elle utilise des bits de présence. Il y a un bit par processeur, qui indique si le cache du processeur a une copie de la donnée : le énième bit de présence indique si le énième processeur a une copie de la donnée 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 lignes de cache.
La méthode précédente pose problème quand le nombre de processeur augmente trop. Ce problème peut être résolu en n'autorisant qu'un nombre maximal de copies d'une ligne de cache : soit un invalide automatiquement une copie quand ce nombre est dépassé, soit on interdit toute copie une fois ce maximum atteint. Une autre solution consiste à autoriser les copies en trop, mais toute invalidation de ces copies sera envoyée à tous les processeurs, même s'ils n'ont pas de copie de la donnée invalide.
Ces solutions sont cependant assez lourdes, et des alternatives existent. Ces alternatives consistent à 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.
