Français
Menu

Cache à correspondance directe vs associatif par ensembles vs totalement associatif

Un cache doit déterminer où chaque bloc de mémoire peut être stocké. Dans un cache à correspondance directe, chaque bloc n'a qu'une seule ligne possible, ce qui est simple et rapide mais provoque des conflits lorsque deux blocs partagent une ligne. Dans un cache totalement associatif, un bloc peut aller n'importe où, ce qui évite les conflits mais exige une comparaison avec chaque ligne. Un cache associatif par ensembles est le compromis : un bloc peut aller dans l'une des quelques voies d'un ensemble. La plupart des caches de CPU sont associatifs par ensembles.

CritèreCorrespondance directeAssociatif par ensemblesTotalement associatif
Emplacement possible d'un blocExactement une ligne, choisie par les bits d'indexN'importe laquelle des voies (par exemple 4 ou 8) d'un ensembleN'importe quelle ligne du cache
Comparaisons de tags par accèsUneUne par voie (par exemple 8)Toutes les lignes à la fois, en parallèle
Temps d'accès en cas de succèsLe plus rapideLégèrement plus lentLe plus lent
Coût matériel et consommationLes plus faiblesModérésLes plus élevés : un comparateur par ligne
Défauts de conflitLes plus fréquentsRéduits à mesure que le nombre de voies augmenteAucun : seuls les défauts obligatoires et de capacité subsistent
Politique de remplacementInutile : un seul choix possibleChoix au sein de l'ensemble (LRU ou approximations)Choix parmi toutes les lignes
Usages typiquesPetits caches simples et certains microcontrôleursCaches L1, L2 et L3 de la plupart des CPU, généralement de 4 à 16 voiesPetites structures comme les TLB et les victim caches

Les valeurs indiquées sont des ordres de grandeur typiques et varient selon la génération de procédé et le produit.

Quand choisir l'un ou l'autre ?

Correspondance directe
Lorsque la simplicité, la faible consommation et la vitesse comptent plus que le taux de succès.
Associatif par ensembles
Le choix pratique pour la plupart des caches, car quelques voies suppriment la plupart des défauts de conflit pour un coût modeste.
Totalement associatif
Pour les très petites structures où le taux de succès est critique et où le coût des comparaisons est acceptable.

Questions fréquentes

Qu'est-ce qu'un défaut de conflit ?

Un défaut de cache qui survient parce que deux blocs correspondent au même emplacement alors que d'autres lignes du cache sont libres. Les caches à correspondance directe en souffrent le plus, et les caches totalement associatifs n'en ont aucun.

Combien de tags un cache à 8 voies compare-t-il par accès ?

Huit, un pour chaque voie de l'ensemble sélectionné.

Pourquoi la plupart des caches de CPU sont-ils associatifs par ensembles ?

Quelques voies suppriment la plupart des défauts de conflit pour un coût modeste, alors qu'un cache totalement associatif nécessite un comparateur par ligne.

Où utilise-t-on un cache totalement associatif ?

Dans de petites structures comme les TLB et les victim caches, où le taux de succès compte le plus et où le coût des comparaisons est acceptable.

Vérifier vos connaissances

Pour un cache à correspondance directe avec des adresses de 32 bits, une capacité de 32 KB et des lignes de 64 octets, combien de bits comporte l’étiquette ?

  1. A15 bits
  2. B19 bits
  3. C17 bits
Afficher la réponse et l'explication

Réponse : C. 17 bits

Une ligne de 64 octets = 2⁶ donne un déplacement de 6 bits. Le nombre de lignes est 32 KB ÷ 64 B = 32768 ÷ 64 = 512 = 2⁹ ; en correspondance directe, le nombre de lignes est égal au nombre d’ensembles, d’où un index de 9 bits. Le reste constitue l’étiquette : 32 − 9 − 6 = 17 bits. La valeur de 19 bits correspond à un cache associatif à 4 voies dont l’index perd 2 bits ; elle ne s’applique pas à la correspondance directe.

Combien d’ensembles comporte un cache associatif à 4 voies avec des adresses de 32 bits, une capacité de 32 KB et des lignes de 64 octets ?

  1. A128
  2. B512
  3. C32
Afficher la réponse et l'explication

Réponse : A. 128

Le nombre de lignes est 32 KB ÷ 64 B = 512. Avec 4 voies, chaque ensemble contient 4 lignes ; le nombre d’ensembles est donc 512 ÷ 4 = 128 = 2⁷, d’où un index de 7 bits et une étiquette de 32 − 7 − 6 = 19 bits. 512 est le nombre de lignes lui-même, c’est-à-dire le nombre d’ensembles en correspondance directe. Augmenter l’associativité réduit le nombre d’ensembles, ce qui accroît d’autant la taille de l’étiquette et le nombre de comparateurs. 32 résulte de la division erronée de la taille de ligne 64 par le nombre de voies.

Dans un cache totalement associatif, combien de bits de l’adresse sont utilisés pour l’index (partie qui sélectionne l’ensemble) ?

  1. A6 bits, déterminés par la taille de ligne
  2. BAutant de bits que de lignes
  3. C0 bit
Afficher la réponse et l'explication

Réponse : C. 0 bit

Dans un cache totalement associatif, toute donnée peut être placée à n’importe quel emplacement du cache ; il n’existe donc qu’un seul ensemble. Aucune sélection d’ensemble n’étant nécessaire, l’index compte 0 bit : l’adresse se divise uniquement en déplacement et étiquette, et chaque accès compare les étiquettes de toutes les lignes. Cela exige de nombreux comparateurs ; cette organisation ne convient pas aux grands caches et sert pour de petites structures comme le TLB. La taille de ligne détermine le nombre de bits du déplacement, et non celui de l’index.

  1. Dans un cache à correspondance directe, les éléments de deux tableaux correspondent au même emplacement du cache et s’évincent mutuellement à chaque accès alterné. Dans quelle catégorie se classe ce défaut ?
  2. Quel changement se produit lors du passage d’un cache à correspondance directe à un cache associatif par ensembles ?
  3. Dans un cache associatif à 8 voies, combien d’étiquettes sont comparées en parallèle à chaque accès ?

Questions d'entraînement sur Hiérarchie mémoire

Termes clés expliqués

Correspondance directe (direct-mapped)
Organisation de cache où chaque adresse ne peut être placée qu'à un seul emplacement. Circuit simple et temps d'accès court en cas de succès, mais les défauts par conflit sont fréquents.
Cache associatif par ensembles
Organisation de cache où une donnée peut être placée dans n'importe lequel des emplacements (voies) d'un ensemble déterminé par l'adresse. Avec n voies, n étiquettes sont comparées en parallèle à chaque accès.
Cache entièrement associatif
Organisation de cache où toute donnée peut être placée à n'importe quel emplacement. Il n'y a pas de défauts de conflit, mais toutes les étiquettes doivent être comparées, ce qui ne convient pas aux grands caches. Utilisé notamment pour les TLB.
Ligne de cache
Unité de transfert de données entre le cache et le niveau inférieur, aussi appelée bloc de cache. Elle fait 64 octets sur la plupart des CPU ; les bits de poids faible de l'adresse donnent la position (offset) dans la ligne.

Comparatifs associés