N-way set associative cache
N-way set associative cache.
Il s'agit d'un compromis entre le "mapping" direct et complètement associatif
essayant d'allier la simplicité de l'un et l'efficacité de l'autre.
La mémoire cache est divisée en ensembles (sets) de N lignes de cache. Un
ensemble est représenté sur la figure ci-jointe par l'union des rectangles rouges. Une
ligne de la mémoire de niveau supérieur est affectée à un ensemble, elle peut par
conséquent être écrite dans n'importe laquelle des voies i.e. des N lignes de
l'ensemble. Ceci permet d'éviter de nombreux défauts de cache conflictuels. À
l'intérieur d'un ensemble, le mapping est Direct Mapped, alors que le mapping des N
Sets est Fully Associative. En général, la sélection de l'ensemble est effectuée
par : Ensemble = Adresse mémoire mod (Nombre d'ensembles).
Reprenons l'exemple de la section précédente (mémoire cache de kibioctets) mais
constitué de voies. Le nombre de voies est en effet toujours une puissance de 2 afin
d'obtenir un découpage simple de l'adresse mémoire. La mémoire cache contient
donc bits par voie. Sachant qu'une ligne représente 256 bits, il y a donc entrées par
ensemble. L'index est donc de s-n+5 bits.
Les mémoires considérées ici sont adressables par octet. Par conséquent, les
adresses de 32 bits donnent accès à une mémoire de bits, soit l'équivalent
de lignes de mémoire cache. Ainsi, chaque ensemble de la mémoire cache
contient lignes distinctes. Le tag est donc de 22-s+n bits. Le découpage de l'adresse
est alors :
Adresse N way.
Caches unifiés ou caches séparés
Pour fonctionner, un processeur a besoin de données et d'instructions. Il existe donc
deux solutions pour l'implémentation des mémoires cache :
le cache unifié : données et instructions sont enregistrées dans la même mémoire
cache ;
les caches séparés de données et d'instructions.
Séparer données et instructions permet notamment d'augmenter la fréquence de
fonctionnement du processeur, qui peut ainsi accéder simultanément à une donnée
et une instruction. Cette situation est particulièrement courante pour des Load/Store.
Ceci explique que le cache unifié est souvent le maillon faible du système. De plus,
dans un cache unifié, une logique supplémentaire donnant la priorité aux données ou
aux instructions doit être introduite, ce qui n'est pas le cas pour les caches séparés.
Là où on sait que les instructions ne sont pas modifiables par le programme (ce qui
fait partie des bonnes pratiques), on pourrait en théorie se passer du dirty bit.
Cependant les programmes demandant des performances élevées (pilotes de
périphériques rapides, par exemple) prennent parfois des libertés à cet égard, ce qui
oblige à la prudence. Tout au plus, on sait que les instructions - à la différence des
données - seront rarement ou très rarement modifiées, et on peut optimiser les
circuits en conséquence.
En cas de modifications des instructions par le programme, les caches séparés
introduisent un problème de cohérence du cache d'instructions: le programme doit
alors invalider lui-même les entrées correspondantes dans le cache d'instruction pour
provoquer leur mise à jour avant d'exécuter les instructions modifiées, sans quoi une
version précédente de ces instructions pourrait être prise en compte et exécutée par
le processeur (voire quelque mélange imprévisible des nouvelles instructions et des
anciennes).
En 2011, la solution la plus répandue est la séparation des caches, car elle permet
entre autres d'appliquer des optimisations spécifiques à chaque cache en fonction de
son type d'accès.
Politique d'écriture dans la mémoire de niveau supérieur
Quand une donnée se situe dans le cache, le système en possède deux copies : une
dans la mémoire de niveau supérieur (disons la mémoire principale) et une dans la
mémoire cache. Quand la donnée est modifiée localement, plusieurs politiques de
mise à jour existent :
Écriture immédiate (write-through)
la donnée est écrite à la fois dans le cache et dans la mémoire principale. La
mémoire principale et le cache ont à tout moment une valeur identique, simplifiant
ainsi de nombreux protocoles de cohérence ;
Écriture différée (write-back)
l'information n'est écrite dans la mémoire principale que lorsque la ligne disparaît du
cache (invalidée par d'autres processeurs, évincée pour écrire une autre ligne...).
Cette technique est la plus répandue car elle permet d'éviter de nombreuses écritures
mémoires inutiles. Pour ne pas avoir à écrire des informations qui n'ont pas été
modifiées (et ainsi éviter d'encombrer inutilement le bus), chaque ligne de la mémoire
cache est pourvue d'un bit indiquant la modification (bit dirty). Lorsque la ligne est
modifiée dans le cache, ce bit est positionné à 1, indiquant qu'il faudra réécrire la
donnée dans la mémoire principale. L'écriture différée nécessite bien entendu des
précautions particulières lorsqu'on l'utilise pour des supports amovibles ("Retrait du
volume en toute sécurité" avec purge - flush - du cache).
Algorithme Write-through
Algorithme Write-back
Algorithmes de remplacement des lignes de cache
Article détaillé : Algorithme de mise en cache.
Les caches associatifs de N voies et complètement associatifs impliquent le
mapping de différentes lignes de la mémoire de niveau supérieur sur le même
set. Ainsi, lorsque le set de lignes de la mémoire cache, où une ligne de la
mémoire supérieure peut être mappée, est rempli, il faut désigner la ligne qui
sera effacée au profit de la ligne nouvellement écrite. Le but de l'algorithme
de remplacement (dit aussi politique de remplacement ou politique d'éviction)
des lignes de cache est de choisir cette ligne de manière optimale. Ces
algorithmes doivent être implémentés en hardware pour les mémoires caches
de bas niveau afin d'être les plus rapides possible et de ne pas ralentir le
processeur. Cependant, ils peuvent être implémentés en software pour des
caches de niveau supérieur.
La majorité des algorithmes reposent sur le principe de localité pour tenter de
prévoir le futur à partir du passé. Certains des algorithmes de remplacement
des lignes de mémoire cache les plus répandus sont :
aléatoires pour la simplicité de la création de l'algorithme ;
FIFO (First In, First Out) pour sa simplicité de conception ;
LRU (Least Recently Used) qui mémorise la liste des derniers éléments accédés
et exclut l'élément accédé il y a le plus de temps.
La politique LRU peut paraître la plus naturelle, car elle favorise les éléments
les plus récemment utilisés donc a priori ceux qui sont en cours d'utilisation
fréquente, mais elle a pu paraître difficile à réaliser efficacement en matériel,
d'où l'existence de politiques « pseudo-LRU ».