Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Systèmes informatiques

Mémoire cache : hiérarchie, localité et temps d'accès moyen

La hiérarchie mémoire, la localité, le cache à correspondance directe avec découpage de l'adresse, l'AMAT avec exemples, l'associativité, les politiques d'écriture, l'ordre des boucles.

https://www.electronics-engineering.com/fr/memoire-cache-hierarchie-localite-temps-d-acces-moyen/

Pas encore de vote : soyez le premier à noter cette page.

Un processeur moderne exécute une instruction en moins d’une nanoseconde, mais lire une valeur dans la mémoire principale (DRAM) prend environ 80 ns : sans contre-mesures, il passerait presque tout son temps à attendre. La solution est une hiérarchie mémoire : des mémoires petites et très rapides près du processeur, grandes et lentes plus loin. Elle fonctionne grâce à une propriété des programmes, la localité. Dans cette leçon, nous voyons comment est construit un cache, comment on calcule le temps d’accès moyen et comment la manière d’écrire le code change son efficacité.

La hiérarchie

Hiérarchie mémoire avec les temps d'accès typiques
De haut en bas : registres, caches de premier, deuxième et troisième niveau, mémoire DRAM et disque SSD. En descendant, la capacité croît et le coût par octet diminue, mais le temps d’accès passe de quelques centaines de picosecondes à une centaine de microsecondes.

Les mémoires rapides (SRAM, dans les caches) sont chères par bit et occupent beaucoup de surface ; les grandes (DRAM, flash) sont bon marché mais lentes. Chaque niveau contient une copie des parties les plus récemment utilisées du niveau inférieur.

La localité

  • Localité temporelle : un élément utilisé récemment sera probablement réutilisé bientôt (les variables d’une boucle, les instructions de la boucle elle-même).
  • Localité spatiale : si un élément est utilisé, ses voisins le seront probablement aussi (les éléments suivants d’un tableau, les instructions suivantes).

Pour exploiter cette dernière, le cache ne copie pas des octets isolés mais des blocs (ou lignes) de 64 octets : lire le premier élément d’un tableau amène aussi les suivants dans le cache.

Le cache à correspondance directe

Chaque bloc de mémoire ne peut vivre que dans une seule ligne du cache, choisie par une partie de l’adresse. L’adresse est découpée en trois champs.

Exemple. Un cache de 32 Kio avec des blocs de 64 octets et des adresses de 32 bits : il y a 32\,768/64 = 512 lignes.

  • déplacement (offset, 6 bits, car 2^6 = 64) : quel octet dans le bloc ;
  • index (9 bits, car 2^9 = 512) : quelle ligne du cache ;
  • étiquette (tag, les 32 - 6 - 9 = 17 bits restants) : lequel des nombreux blocs qui correspondent à cette ligne est présent.
Découpage de l'adresse et recherche dans un cache à correspondance directe
L’adresse de 32 bits est découpée en étiquette (17 bits), index (9 bits) et déplacement (6 bits). L’index sélectionne l’une des 512 lignes ; l’étiquette stockée dans cette ligne est comparée à celle de l’adresse : si elles coïncident et que le bit de validité vaut 1, la donnée est dans le cache (succès) et le déplacement sélectionne l’octet dans le bloc de 64 octets.

Chaque ligne contient le bloc, l’étiquette et un bit de validité. À l’accès, l’index choisit la ligne et l’étiquette est comparée : si elle coïncide (et que la ligne est valide), c’est un succès (hit), sinon un défaut (miss) : le bloc est lu dans le niveau inférieur et remplace celui qui était présent.

Temps d’accès moyen à la mémoire

    \[ \mathrm{AMAT} = t_{hit} + m\cdot t_{miss} \]

où m est le taux de défauts et t_{miss} le temps pour aller chercher le bloc.

Exemple. Un cache à 1 cycle, 5 % de défauts, 100 cycles pour atteindre la DRAM : AMAT = 1 + 0.05\cdot 100 = 6 cycles. En ajoutant un cache de second niveau de 10 cycles qui trouve 80 % des blocs manqués au premier niveau : AMAT = 1 + 0.05\cdot(10 + 0.2\cdot 100) = 2.5 cycles. Le second niveau plus que divise par deux le temps moyen.

Même des taux de défauts qui semblent petits pèsent lourd : passer de 2 % à 4 % de défauts, avec une pénalité de 100 cycles, fait passer l’AMAT de 3 à 5 cycles.

Associativité et types de défauts

Dans un cache à correspondance directe, deux blocs utilisés en alternance qui correspondent à la même ligne s’évincent sans cesse. Les caches associatifs par ensembles à n voies permettent à chaque bloc de vivre dans n lignes différentes (un ensemble), en comparant n étiquettes en parallèle, et quand l’ensemble est plein ils remplacent le bloc le moins récemment utilisé (LRU). Les caches de premier niveau ont typiquement 8 voies.

Les défauts se classent en « trois C » : obligatoires (le premier accès à un bloc), de capacité (les données utilisées ne tiennent pas toutes), de conflit (des blocs en compétition pour le même ensemble).

Écritures. Avec une politique d’écriture simultanée (write-through), chaque écriture va aussi au niveau inférieur ; avec une écriture différée (write-back), seul le cache est écrit, et le bloc modifié (marqué par un bit « sale », dirty) est recopié en mémoire quand il est remplacé. Cette dernière réduit beaucoup le trafic vers la mémoire et c’est celle qu’utilisent les caches des processeurs.

Le code compte

En C, les matrices sont stockées par lignes : les éléments d’une ligne sont contigus.

/* fast: walks memory in order */
for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        s += a[i][j];

/* slow: jumps N elements on every access */
for (j = 0; j < N; j++)
    for (i = 0; i < N; i++)
        s += a[i][j];

Les deux versions font exactement les mêmes calculs, mais avec une grande matrice la seconde peut être plusieurs fois plus lente : chaque accès tombe dans un bloc différent, et quand on revient à la même ligne, son bloc a déjà été remplacé. Organiser les données et les boucles pour exploiter la localité est l’une des optimisations les plus efficaces de toutes, et la base des bibliothèques numériques rapides (qui travaillent sur des blocs qui tiennent dans le cache).

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x