« Fonctionnement d'un ordinateur/Les mémoires cache » : différence entre les versions

m
On pourrait croire qu'un seul cache est largement suffisant pour compenser la lenteur de la mémoire. Hélas, les processeurs sont devenus tellement rapides que les caches sont eux mêmes très lents ! Pour rappel, plus une mémoire peut contenir de données, plus elle est lente. Et les caches ne sont pas épargnés. Si on devait utiliser un seul cache, celui-ci serait très gros et donc trop lent. La situation qu'on cherche à éviter avec la mémoire RAM revient de plus belle.
 
Même problème, même solution : si on a décidé de diviser la mémoire principale en plusieurs mémoires de taille et de vitesse différentes, on peut bien faire la même chose avec la mémoire cache. Depuis environ une vingtaine d'années, un processeur contient plusieurs caches de capacités très différentes : les caches L1, L2 et parfois un cache L3. Certains de ces caches sont petits, mais très rapides : c'est ceux auxquels on va accéder en priorité. Viennent ensuite d'autres caches, de taille variable, mais plus lents. Les processeurs ont donc une hiérarchie de caches qui se fait de plus en plus complexe avec le temps,. avecCette dehiérarchie plusest en pluscomposée de plusieurs niveaux de cache, qui vont des niveaux inférieurs proches de la mémoire RAM à des niveaux supérieurs proches du processeur. Plus on monte vers les niveaux supérieurs, plus les caches sont petits et rapides.
 
===Le fonctionnement d'une hiérarchie de caches===
 
Un accès mémoire dans une hiérarchie de cache fonctionne comme suit : on commence par vérifier si la donnée recherchée est dans le cache le plus rapide, à savoir le cache L1. Si c'est le cas,n on la charge depuis ce cache directement. Si elle n’y est pas, on vérifie si elle est dans le cache de niveau inférieur, le cache L2. Et rebelote ! Si elle n'y est pas, on vérifie le cache du niveau inférieur. Et on répète cette opération, jusqu’à avoir vérifié tous les caches. Si la donnée n'est dans aucun cache, on doit alors aller chercher la donnée en mémoire.
[[File:Hiérarchie de caches.png|centre|vignette|upright=2|Hiérarchie de caches]]
 
===Les caches exclusifs et inclusifs===
Notons que du point de vue de cette vérification, il faut distinguer les caches inclusifs et exclusifs. Ils se distinguent par le fait que les caches inclusifs ont des données en doublon dans plusieurs niveaux de cache, alors que les caches exclusifs font que la donnée est présente dans un seul cache, pas les autres.
 
EtNotons enfinque du point de vue de cette vérification, jeil mefaut doisdistinguer les caches inclusifs et exclusifs. Avec les caches inclusifs, si une donnée est présente dans un cache, alors elle est présente dans les caches des niveaux inférieurs, ce qui implique l'existence de parlerdonnées en doublon dans plusieurs niveaux de cache. A l'opposé, les caches exclusifs font que toute donnée est présente dans un seul cache, pas les autres. Il existe aussi des caches qui ne sont ni inclusifs, ni exclusifs. Sur ces caches, chaque niveau de cache gère lui-même ses données, sans se préoccuper du contenu des autres caches. Pas besoin de mettre à jour les niveaux de cache antérieurs en cas de mise à jour de son contenu, ou en cas d'éviction d'une ligne de cache. La conception de tels caches est bien plus simple.
Dans les '''caches exclusifs''', le contenu d'un cache n'est pas recopié dans le cache de niveau inférieur.Il n'y a pas de donnée en double et on utilise 100 % de la capacité du cache, ce qui améliore le taux de succès. Par contre, le temps d'accès est un peu plus long. La raison est que si une donnée n'est pas dans le cache L1, on doit vérifier l'intégralité du cache L2, puis du cache L3. De plus, assurer qu'une donnée n'est présente que dans un seul cache nécessite aux différents niveaux de caches de communiquer entre eux pour garantir que l'on a pas de copies en trop d'une ligne de cache, ce qui peut prendre du temps.
 
Dans les '''caches exclusifs''', le contenu d'un cache n'est pas recopié dans le cache de niveau inférieur. Il n'y a pas de donnée en double et on utilise 100 % de la capacité du cache, ce qui améliore le taux de succès. Par contre, le temps d'accès est un peu plus long. La raison est que si une donnée n'est pas dans le cache L1, on doit vérifier l'intégralité du cache L2, puis du cache L3. De plus, assurer qu'une donnée n'est présente que dans un seul cache nécessite aux différents niveaux de caches de communiquer entre eux pour garantir que l'on a pas de copies en trop d'une ligne de cache, ce qui peut prendre du temps.
 
[[File:Caches exclusifs.png|centre|vignette|upright=2|Caches exclusifs]]
[[File:Caches inclusifs.png|centre|vignette|upright=2|Caches inclusifs]]
 
Ce genre de cache a un avantage : le temps d'accès à une donnée est plus faible. La raison est qu'il ne faut pas vérifier tout un cache, mais seulement la partie qui ne contient pas de donnée en doublon. Par exemple, si la donnée voulue n'est pas dans le cache L1, on n'est pas obligé de vérifier la partie du cache L2 qui contient la copie du L1. Ainsi, pas besoin de vérifier certaines portions du cache, ce qui est plus rapide et permet de simplifier les circuits de vérification. En contrepartie, l'inclusion fait que qu'une partie du cache contient des copies inutiles, comme si le cache était plus petit. De plus, maintenir l'inclusion demande de respecter des contraintes assez fortes, ce qui ne se fait pas facilement.
Maintenir cette inclusion demande toutefois d'échanger des données entre mémoires cache, toute éviction de donnée devant être propagée aux caches de niveau inférieur et supérieur. Premièrement, toute donnée chargée dans un cache doit aussi l'être dans tous les caches de niveau inférieur. Cette contrainte est respectée en maintenant une hiérarchie entre caches lors des accès. Par exemple, si un défaut de cache a lieu dans le L1, celui-ci doit déclencher une lecture dans le L2, lecture qui déclenchera potentiellement un défaut de cache dans le L3, et ainsi de suite jusqu'à trouver la bonne donnée : tous les caches seront parcourus dans l'ordre descendant jusqu'à trouver la donnée. Chaque défaut de cache chargera la donnée dans le cache correspondant, ce qui fait que tous les caches parcourus auront une copie de la donnée.
 
Premièrement, toute donnée chargée dans un cache doit aussi l'être dans les caches de niveau inférieur. Ensuite, quand une donnée est présente dans un cache, elle doit être maintenue dans les niveaux de cache inférieurs. De plus, toute donnée effacée d'un cache doit être effacée des niveaux de cache supérieurs : si une donnée quitte le cache L2, elle doit être effacée du L1. Ces trois contraintes posent des problèmes si chaque cache décide du remplacement des lignes de cache en utilisant un algorithme comme LRU, LFU, MRU, ou autre, qui utilise l'historique des accès. En effet, dans ce cas, le cache décide de remplacer les lignes de cache selon l'historique des accès, historique qui varie suivant chaque niveau de cache. Par exemple, une donnée rarement utilisée dans le L2 peut parfaitement être très fréquemment utilisée dans le L1 : la donnée sera alors remplacée dans le L2, mais sera maintenue dans le L1. On remarqueobserve queaussi cedes genreproblèmes dequand chosesil n'aexiste pasplusieurs lieucaches surà lesun cachesseul adressés directementniveau : ilchaque n'existecache qupeut remplacer les lignes de cache d'une seulemanière politiqueindépendante dedes remplacementautres quicaches n’utilisedu pasmême l'historiqueniveau, desdonnant accèslieu au même type de problème.
 
Pour résoudremaintenir ce problèmel'inclusion, les caches doivent communiquer entre eux, et se transmettre des informations qui permettent de maintenir l'inclusion. Par exemple, les caches de niveaux inférieurs doivent prévenir les niveaux de cache supérieurs quand ils décident de remplacerremplacent une ligne de cache. OuDe alorsplus, lestoute cachesmise deà niveaujour inférieursdans doiventun gardercache endoit mémoireêtre répercutée dans les lignesniveaux de cache présentesinférieurs danset/ou lesupérieurs. niveauOn supérieurdoit etdonc refusertransférer des informations de remplacermise celles-ci.à Dejour même,entre les écrituresdifférents dans un niveauniveaux de cache. doiventGénéralement, êtrele propagéescontenu dansdes lescaches niveauxd'instruction inférieursn'est (oupas duinclus moins,dans les niveauxcaches de cacheniveau inférieurs, doiventafin être prévenusd'éviter que leurles versioninstructions deet lales donnéedonnées n'estse pasmarchent sur les valide)pieds.
 
On observe aussi des problèmes quand il existe plusieurs caches à un seul niveau : chaque cache peut remplacer les lignes de cache d'une manière indépendante des autres caches du même niveau, donnant lieu au même type de problème. Enfin, il faut aussi savoir que la taille des lignes de cache n'est pas la même suivant les niveaux de cache : le L2 peut avoir des lignes plus grandes que celles du L1. Dans ce cas, l'inclusion est plus difficile à maintenir, pour des raisons assez techniques.
 
===CachesLes caches d'instructions===
Ce genre de cache a un avantage : le temps d'accès à une donnée présente dans le cache est plus faible. Cela est dû en partie à la présence des copies des caches de niveaux supérieurs dans les caches de niveaux inférieurs (mais pas que). Pour expliquer pourquoi, prenons un exemple : si la donnée voulue n'est pas dans le cache L1, on n'est pas obligé de vérifier la partie du cache L2 qui contient la copie du L1. Ainsi, les circuits qui doivent vérifier si une adresse correspond bien à une donnée placée dans le cache peuvent être simplifiés et ne pas vérifier certaines portions du cache. Ce qui donne un résultat plus rapide.
 
Sur certains processeurs, il y a deux caches L1 séparés : un cache dédié aux instructions, et un autre pour les données. Ils sont reliés au reste du processeur par des bus séparés, ce qui permet de charger une instruction et manipuler une donnée en même temps, ce qui est un gros avantage en termes de performances.
En contrepartie, une partie des caches de niveau inférieur contient les données contenues dans le cache de niveau supérieur, qui sont donc en double. Cette redondance fait qu'une partie du cache est mal utilisée, comme si le cache était plus petit. De plus, la mise à jour du contenu d'un niveau de cache doit être répercutée dans les niveaux de cache inférieurs et/ou supérieurs. On doit donc transférer des informations de mise à jour entre les différents niveaux de cache. Généralement, le contenu des caches d'instruction n'est pas inclus dans les caches de niveau inférieurs, afin d'éviter que les instructions et les données se marchent sur les pieds.
 
Rien n’empêche aux deux mémoires cache L1 de vouloir lire ou écrire dans le cache L2 simultanément. Si le cache L2 gère ces écritures/lectures simultanées, pas de problème.
Et enfin, je me dois de parler des caches qui ne sont ni inclusifs, ni exclusifs. Sur ces caches, chaque niveau de cache gère lui-même ses données, sans se préoccuper du contenu des autres caches. Pas besoin de mettre à jour les niveaux de cache antérieurs en cas de mise à jour de son contenu, ou en cas d'éviction d'une ligne de cache. La conception de tels caches est bien plus simple.
 
[[File:Cache d'instructions.png|centre|vignette|upright=2|Cache d'instructions.]]
===Caches d'instructions===
 
Mais s'il ne peut pas, on doit effectuer un arbitrage pour décider quel cache a la priorité.
Au fait, sur certains processeurs, le cache L1 est segmenté en deux sous-caches : un qui contient des instructions, et un autre qui ne contient que des données. Ces deux caches étant dans des mémoires séparées et étant reliés au reste du processeur par des bus séparés, on peut charger une instruction et manipuler une donnée en même temps, ce qui est un gros avantage en termes de performances. Ceci dit, cette organisation pose parfois de légers problèmes : rien n’empêche aux deux mémoires cache L1 de vouloir lire ou écrire dans le cache L2 simultanément. Si le cache L2 gère ces écritures/lectures simultanées, pas de problème. Mais s'il ne peut pas, on doit effectuer un arbitrage pour décider quel cache a la priorité. Cet arbitrage est effectué par un circuit spécialisé.
 
[[File:Circuit d'arbitrage du cache.png|centre|vignette|upright=2|Circuit d'arbitrage du cache.]]
<gallery widths="400px" heights="400px">
Cache d'instructions.png|Cache d'instructions.
Circuit d'arbitrage du cache.png|Circuit d'arbitrage du cache.
</gallery>
 
Le cache L1 dédié aux instructions est souvent en « lecture seule » : on ne peut pas modifier son contenu, mais juste le lire ou charger des instructions dedans. Cela posecomplique parfoisla quelques légers problèmes quand on cherche à utilisergestion du code automodifiant, c'est-à-dire undes programme dont certaines instructions vont aller en modifier d'autres, ce qui sert pour faire de l'optimisation ou est utilisé pour compresser voireou cacher un programme (les virus informatiques utilisent beaucoup de genre de procédés). Quand le processeur exécute ce genre de code, il ne peut pas écrire dans ce cache L1 d'instructions, mais va devoir écrire en mémoire cache L2 ou en RAM, et va ensuite devoir recharger les instructions modifiées dans le cache L1, ce qui prend du temps ! Et pire : cela peut parfois donner lieu à des erreurs si le cache L1 n'est pas mis à jour.
 
Sur certains processeurs, l'étape de décodage est assez complexe et lente. Pour accélérer cette étape, certains concepteurs de processeurs ont décidés d'utiliser la (ou les) mémoire cache dédiée aux instructions pour accélérer ce décodage. Lorsque ces instructions sont chargées depuis la RAM ou les niveaux de cache inférieurs, celles-ci sont partiellement décodées. On peut par exemple rajouter des informations qui permettent de délimiter nosles instructions ou déterminer leur taille, ce qui est utile pour décoder les instructions de taille variable. Bref, notrele cache d'instructions peut se charger d'une partie du décodage des instructions, grâce à un circuit séparé de l'unité de décodage d'instruction.
 
===CacheLe cache de boucle===
Enfin, il existe une dernière solution pour limiter les effets de la hiérarchie mémoire. Pour les caches de grande capacité, il arrive souvent que le temps de propagation des signaux varie fortement suivant la ligne de cache à lire. D'ordinaire, on se cale sur la ligne de cache la plus lente pour caler la fréquence d'horloge du cache, mais cela gâche les faible latences des lignes de cache qui sont tout près du contrôleur de cache. Certains chercheurs ont alors décidé de ruser : ils acceptent d'avoir une latence différente pour chaque ligne d'un même cache. Les caches qui fonctionnent sur ce principe sont appelés des '''caches à accès non uniforme'''. La première version de ce genre de caches a une correspondance ligne de cache → bloc de mémoire statique : on ne peut pas déplacer le contenu d'une ligne de cache dans une autre portion de mémoire plus rapide suivant les besoins. Mais des versions plus optimisées en sont capables : la correspondance entre une ligne de cache et un bloc de mémoire cache peut varier à l’exécution. Ainsi, les lignes de cache les plus utilisées peuvent migrer dans un bloc de mémoire plus rapide : cela demande juste de copier les données entre blocs de mémoire et de mettre à jour la correspondance entre ligne de cache et bloc de mémoire.
 
===Cache de boucle===
 
Il est possible d'optimiser le fonctionnement des boucles sur les processeurs pipelinés. D'ordinaire, lorsqu'une instruction doit être exécutée plusieurs fois dans un temps très court, elle doit être chargée depuis la mémoire et décodée, puis exécutée plusieurs fois. Sur les processeurs qui disposent de pipelines, ce chargement répété peut être omis en utilisant un cache de boucle, un cache chargé de stocker les dernières instructions chargées et/ou décodées. Si une instruction doit être réexécutée (signe d'une boucle), il suffit d'aller chercher l'instruction directement dans le cache de boucle, au lieu de la recharger. Néanmoins, ce cache ne peut stocker qu'un nombre limité d'instructions, ce qui limite la taille des boucles pouvant profiter de ce cache.
 
===Les caches à accès non-uniforme===
 
Enfin, il existe une dernière solution pour limiter les effets de la hiérarchie mémoire. PourSur les caches de grande capacité, il arrive souvent que le temps de propagation des signaux varie fortement suivant la ligne de cache à lire. D'ordinaire, on se cale sur la ligne de cache la plus lente pour caler la fréquence d'horloge du cache, mais cela gâche les faible latences des lignes de cache qui sont tout près du contrôleur de cache. Certains chercheurs ont alors décidé de ruser : ils acceptent d'avoir une latence différente pour chaque ligne d'un même cache. Les caches qui fonctionnent sur ce principe sont appelés des '''caches à accès non uniforme'''. La première version de ce genre de caches a une correspondance ligne de cache → bloc de mémoire statique : on ne peut pas déplacer le contenu d'une ligne de cache dans une autre portion de mémoire plus rapide suivant les besoins. Mais des versions plus optimisées en sont capables : la correspondance entre une ligne de cache et un bloc de mémoire cache peut varier à l’exécution. Ainsi, les lignes de cache les plus utilisées peuvent migrer dans un bloc de mémoire plus rapide : cela demande juste de copier les données entre blocs de mémoire et de mettre à jour la correspondance entre ligne de cache et bloc de mémoire.
 
==Caches non bloquants==
39 497

modifications