« Fonctionnement d'un ordinateur/Les mémoires cache » : différence entre les versions
Contenu supprimé Contenu ajouté
Ligne 147 :
L'algorithme LRU, ainsi que ses variantes approximatives, sont très efficaces dans la majorité des programmes. Du moment que notre programme respecte relativement bien la localité temporelle, cet algorithme donnera de très bons résultats : le taux de succès du cache sera très élevé. Par contre, cet algorithme se comporte assez mal dans certaines circonstances, et notamment quand on traverse des tableaux. Dans ces conditions, on n'a pas la moindre localité temporelle, mais une bonne localité spatiale. Pour résoudre ce petit inconvénient, des variantes du LRU existent. Une première de ces variante, l''''algorithme 2Q''', utilise deux caches : un cache FIFO pour les données accédées une seule fois et un second cache LRU. Évidemment, les données lues une seconde fois doivent migrer du cache FIFO vers le cache LRU : cela consomme du matériel, de l'énergie et des cycles d'horloge. Les processeurs n'utilisent donc pas cette technique, mais celle-ci est utilisée dans les caches de disque dur. D'autres variantes du LRU combinent plusieurs algorithmes à la fois et vont choisir lequel de ces algorithmes est le plus adapté à la situation. Notre cache pourra ainsi détecter s’il vaut mieux utiliser du MRU, du LRU, ou du LFU suivant la situation.
==Les caches ''Write-back'' et ''write-through''==
Les écritures se font à une adresse mémoire bien précise, qui peut ou non être chargée dans le cache. Si la donnée à écrire est chargée dans le cache, elle est modifiée directement dans le cache, mais elle ne l'est pas forcément en mémoire RAM. Suivant le processeur, les écritures sont ou non propagées en mémoire RAM. Il existe deux stratégies d'écritures, appelées respectivement le ''write-back'' et le ''write-through''.
===Write-back===▼
▲Si la donnée à mettre à jour est présente dans le cache, on écrit dans celui-ci sans écrire dans la mémoire RAM. Dans ces conditions, une donnée n'est enregistrée en mémoire que si celle-ci quitte le cache, ce qui évite de nombreuses écritures mémoires inutiles. On parle alors de caches '''Write-Back'''.
[[File:Cache write-
▲===Les caches ''Write-back''===
En suivant la procédure habituelle de remplacement des lignes de cache, on doit rapatrier la ligne en RAM avant d'en charger une nouvelle. On peut améliorer la situation en faisant l'inverse : on charge la nouvelle ligne pendant que l'ancienne donnée soit rapatriée en RAM. Ainsi, la nouvelle ligne est disponible plus tôt pour le processeur, diminuant son temps d'attente. Pour implémenter cette technique, on doit mémoriser l'ancienne ligne de cache temporairement dans un '''cache d’éviction''' (ou write-back buffer).
[[File:Cache d’éviction.png|centre|vignette|upright=2|Cache d’éviction]]
Les caches directement adressés ou associatifs par voie possèdent aussi un tampon d’écriture amélioré, qui devient un cache en supplément du cache principal. Pour limiter les défauts par conflit de ces caches, des scientifiques ont eu l'idée d'insérer un cache pour stocker les données virées du cache. En faisant ainsi, si une donnée est virée du cache, on peut alors la retrouver dans ce cache spécialisé. Ce cache s'appelle le '''cache de victime'''. Ce cache de victime est géré par un algorithme de suppression des lignes de cache de type FIFO. Petit détail : ce cache utilise un tag légèrement plus long que celui du cache directement adressé au-dessus de lui. L'index de la ligne de cache doit en effet être contenu dans le tag du cache de victime, pour bien distinguer deux adresses différentes, qui iraient dans la même ligne du cache juste au-dessus.
[[File:Victim Cache Implementation Example.svg|centre|vignette|upright=2|Cache de victime.]]
===Write-through===▼
▲[[File:Cache write-back.png|centre|Cache write-back]]
▲===Les caches ''Write-through''===
▲Ces caches ont tendance à commettre beaucoup d'écritures dans la mémoire RAM, ce qui peut saturer le bus reliant le processeur à la mémoire. De plus, on ne peut écrire dans ces caches lorsqu'une écriture en RAM a lieu en même temps : cela forcerait à effectuer deux écritures simultanées, en comptant celle imposée par l'écriture dans le cache.
Pour éviter ces temps d'attentes, certains processeurs avec un cache write-through intègrent un '''tampon d’écriture''', une mémoire FIFO dans laquelle on place temporairement les données à transférer du cache vers la RAM en attendant que la RAM soit libre. On n'a pas à se soucier du fait que la mémoire soit occupée, et on peut continuer à écrire dedans tant que celui-ci n'est pas plein, évitant les temps d'attente dus à la RAM. Par souci d'efficacité, des écritures à la même adresse en attente dans le tampon d’écriture sont fusionnées en une seule. Cela fait un peu de place dans le tampon d’écriture, et lui permet d'accumuler plus d'écritures avant de devoir bloquer le cache. Il est aussi possible de fusionner des écritures à adresses consécutives de la mémoire en une seule écriture en rafale. Ainsi, si la taille d'une ligne de cache est petite, comparée à ce qu'une mémoire accepte en écriture en rafale, on peut gagner un peu de performances. Dans les deux cas, on parle de '''combinaison d'écriture'''.
| |||