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

m
 
Lorsqu'on souhaite accéder au cache, il faut trouver quelle est la ligne de cache dont le tag correspond à l'adresse demandée. On peut classifier les caches selon leur stratégie de recherche de la ligne correspondante en quatre types de caches :
 
* directement adressés, ou direct mapped ;
* totalement associatifs ;
===Les caches directement adressés===
 
Avec celes genrecaches dedirectement cachesadressés, le contenu d'une adresse mémoire seraest chargée dans une ligne de cache prédéfinie, toujours la même, quelles que soient les circonstances. L'accès au cache a donc l'avantage d'être très rapide vu qu'il suffit de vérifier une seule ligne de cache : celle prédéfinie. Mais ces caches ne sont cependant pas sans défauts. Vu que le cache est plus petit que la mémoire, certaines adresses mémoires devront se partagerpartagent la même ligne de cache. Si onle processeur a besoin de manipulerd’accéder fréquemment desà donnéesces qui se partagent la même ligne de cacheadresses, chaque accès à une donnéeadresse supprimera l'autre du cache : tout accès à l'ancienne donnéeadresse se soldera par un défaut de cache. Ce genre de défauts de cache causés par le fait que deux adresses mémoires ne peuvent utiliser la même ligne de cache s'appelle un '''défaut par conflit''' (''conflict miss''). Ainsi, le taux de succès de ce genre de cache est quelque peu… comique, ce qui réduit les gains de performances gagnés de part leurassez faible temps d'accès.
 
[[File:Cache adressé directement.png|centre|vignette|upright=2|Cache adressé directement.]]
 
Les concepteurs de caches s'arrangent pour que des adresses consécutives en mémoire RAM occupent des lignes de cache consécutives, afinpar de simplifier les circuitssouci de gestion du cachesimplicité. Chaque ligne de cache possède un indice, une sorte d'adresse interne qui permet de l'identifier et la sélectionner parmi toutes les autres lignes. Il ne s'agit pas vraiment d'une adresse, vu que le cache n'est pas adressable via le bus d'adresse.
 
[[File:Cache hash table - 2.png|centre|vignette|upright=2|Cache hash table - 2]]
 
Avec cette implémentation, l'adresse mémoire doit permettre de spécifier l'index de la donnée. Le tag correspond aux bits de poids fort de l'adresse mémoire correspondant à notre ligne de cache. Le reste des bits de l'adresse représente l'index de notre ligne, et la position de la donnée dans la ligne.
 
[[File:Cache line.png|centre|vignette|upright=2|Adresse d'une ligne de cache sur un cache adressé directement.]]
 
Un cache directement adressé est conçu avec une RAM, un comparateur, et un paquet de multiplexeurs. La mémoire RAM stocke les lignes de caches et les tags. Un mot mémoire de cette RAM contient une ligne de cache, avec son tag (parfois, on utilise une mémoire séparée pour les tags). Chaque ligne étant sélectionnée par son index, on devine aisément que l'index de notre ligne de cache sera envoyée sur le bus d'adresse de notre mémoire RAM pour sélectionner celle-ci. Ensuite, il suffira de comparer le tag récupéré avec le tag de l'adresse à lire ou écrire. On saura alors si on doit faire face à un défaut de cache. Ensuite, on devra sélectionner la bonne donnée dans notre ligne de cache avec un ensemble de multiplexeurs.
 
[[File:Direct mapped cache - french.png|centre|vignette|upright=2|Cache directement adressé.]]
 
===Les caches totalement associatifs===
Avec les caches totalement associatifs, toute donnée chargée depuis la mémoire peut être placée dans n'importe quelle ligne de cache, sans aucune restriction. Ces caches ont un taux de succès très élevé, vu qu'il n’y a pas de possibilité de défaut par conflit.
 
[[File:Cache totalement associatif.png|centre|vignette|upright=2|Cache totalement associatif.]]
 
Une adresse mémoire ne peut pas servir à identifier une ligne en particulier : elle est donc découpée en un tag, et de quoi identifier la position de la donnée dans la ligne de cache correspondante. Pour déterminer l’occurrence d'un défaut de cache, il suffit de comparer le tag de l'adresse avec tout les tags présents dans le cache : si il y a une seule égalité, pas de défaut de cache. Quelques comparateurs (un par ligne de cache), et un arbre de portes ET suffit.Toutes nos lignes de caches sont reliées à un bus interne qui permettra de relier chaque ligne de cache à l’extérieur. Si les deux tags sont identiques, la ligne de cache associée est la bonne, et elle doit être connectée sur le bus : on relie donc la sortie du comparateur à des transistors chargés de connecter ou de connecter les lignes de cache sur notre bus. Ensuite, il ne reste plus qu'à sélectionner la portion de la ligne de cache qui nous intéresse, grâce à un paquet de multiplexeurs, comme pour les autres caches.
 
[[File:Organisation générale d'un cache totalement associatif.png|centre|vignette|upright=2|Organisation générale d'un cache totalement associatif.]]
 
===Les caches associatifs par voie===
Les caches précédents ont chacun leur défaut : un taux de succès médiocre pour les premiers, et un temps d'accès trop long pour les autres. Certains caches implémentent une sorte de compromis destiné à trouver un juste milieu : ce sont les caches associatifs par voie. Pour simplifier, ces caches sont composés de plusieurs caches directement adressés accessibles en parallèle, chaque cache étant appelé une voie.
 
[[File:Cache associatif par voie.png|centre|vignette|upright=2|Cache associatif par voie.]]
 
L'adresse d'une case mémoire est découpée en trois parties : un tag, un index, et un décalage, comme sur les caches directement adressés. Comme vous pouvez le voir, l'organisation est identique à celle d'un cache totalement associatif, à part que chaque ensemble tag-ligne de cache est remplacé par une mémoire RAM qui en contient plusieurs.
 
[[File:Implémentation d'un cache associatif par voie.png|centre|vignette|upright=2|Implémentation d'un cache associatif par voie.]]
 
Vous aurez remarqué que dans une voie, les lignes sont accédées en adressage direct : les défauts par conflit sont possibles sur un cache associatif par voie. Pour éviter cela, certains chercheurs ont créé des caches skew associative (ou associatifs à biais). Pour faire simple, les index des lignes de cache subissent un petit traitement avant d'être utilisés. Le traitement en question est différent suivant la voie de destination, histoire que deux adresses mémoires avec des index identiques donnent des index différents après traitement. Le traitement en question est souvent une permutation des bits de l'index, qui est différente suivant la voie prise, ou un simple XOR avec un nombre qui dépend de la voie.
 
[[File:Implémentation d'un cache skew associative.jpg|centre|vignette|upright=2|Implémentation d'un cache skew associative.]]
 
Les caches associatifs par voie sont donc une sorte de compromis entre caches directement adressés et caches totalement associatifs, avec un taux de succès et un temps d'accès intermédiaire. Pour réduire ce temps d'accès, certains chercheurs ont inventé la '''prédiction de voie''', qui consiste à faire des paris sur la prochaine voie accédée. Au lieu d'attendre que les comparaisons de tags donnent leur résultat, le processeur sélectionne automatiquement une voie et configure les multiplexeurs à l'avance. Si le processeur ne se trompe pas, le processeur va accéder à la donnée de façon précoce, et commencer à l'utiliser un à deux cycles plus tôt que prévu. S'il se trompe, le processeur devra annuler la lecture effectuée en avance, et recommencer en allant chercher la donnée dans le bon ensemble. Cette technique peut être adaptée de façon à diminuer la consommation énergétique du processeur. Pour cela, il suffit de mettre en veille tous les caches directement adressés sur lesquels le processeur n'a pas parié. C'est plus efficace que d'aller lire plusieurs données dans des mémoires différentes, et n'en garder qu'une.
 
Pour plus de simplicité, la mémoire cache des prédictions est parfois remplacée par une RAM, qui est adressée :
 
* soit par le program counter de l'instruction à l'origine de l'accès (en réalité, seulement quelques bits de poids faible de l'adresse) ;
* soit par l'adresse à accéder (là encore, quelques bits de poids faible) ;
39 502

modifications