Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Architecture des ordinateurs

Hiérarchies de caches : AMAT multiniveau, préchargement et découpage en blocs

Temps d'accès moyen multiniveau avec démonstration, taux locaux et globaux, caches inclusifs et exclusifs, écriture différée, caches non bloquants et préchargement, découpage en blocs démontré.

https://www.electronics-engineering.com/fr/hierarchies-de-caches-amat-multiniveau-blocs/

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

Un processeur moderne peut exécuter une instruction en un tiers de nanoseconde, alors qu’un accès à la DRAM en prend une centaine. Entre les deux se trouve une hiérarchie de caches à plusieurs niveaux, et les performances dépendent de son efficacité plus que de toute autre chose. Le cours de Systèmes d’élaboration a présenté le cache, la localité et le temps d’accès moyen. Dans cette leçon, nous regardons les hiérarchies à plusieurs niveaux avec la démonstration de la formule du temps d’accès moyen, les taux de défaut locaux et globaux, les politiques d’écriture, les caches non bloquants et le préchargement, et la technique du découpage en blocs avec la démonstration du trafic économisé.

La hiérarchie à plusieurs niveaux

Hiérarchie mémoire à trois niveaux de cache avec temps d'accès typiques
Du cache de niveau un, petit et rapide, à la DRAM, grande et lente : à chaque niveau, seuls les défauts m passent au niveau suivant. Le temps d’accès moyen se calcule en emboîtant les contributions.

Un processeur typique a un cache de niveau un (L1) de 32-64 Ko pour les données et un pour les instructions, accessibles en 4-5 cycles ; un L2 privé par cœur de 1-2 Mo, en une quinzaine de cycles ; un L3 partagé entre les cœurs de plusieurs dizaines de mégaoctets, en 40-60 cycles ; puis la DRAM.

Théorème. Avec des temps d’accès t_i et des taux de défaut locaux m_i (la fraction des accès arrivant au niveau i qui n’y trouvent pas la donnée), le temps d’accès moyen à la mémoire d’une hiérarchie à trois niveaux est

    \[ AMAT = t_1 + m_1\big(t_2 + m_2(t_3 + m_3\,t_{mem})\big) \]

Démonstration. Chaque accès passe t_1 en L1. Avec la probabilité m_1, il ne trouve pas la donnée et continue : à partir de là, le temps attendu est le temps d’accès moyen de la hiérarchie qui commence en L2, c’est-à-dire t_2 plus, avec la probabilité m_2, le temps moyen de la hiérarchie qui commence en L3, et ainsi de suite jusqu’à la mémoire, où la donnée est toujours présente. En appliquant la même règle à chaque niveau, on obtient l’expression emboîtée. ∎

Exemple. Avec t_1 = 1 ns, m_1 = 5\ \%, t_2 = 4 ns, m_2 = 30\ \%, t_3 = 12 ns, m_3 = 40\ \%, t_{mem} = 80 ns :

    \[ AMAT = 1 + 0.05\big(4 + 0.3(12 + 0.4\cdot 80)\big) = 1 + 0.05\cdot 17.2 \approx 1.86\ \text{ns} \]

Le temps moyen est proche de celui de L1, bien que la DRAM soit 80 fois plus lente.

Taux locaux et globaux

Le taux local d’un niveau paraît souvent élevé : 30-40 % pour un L2 ou un L3. Ce n’est pas un défaut : seuls les accès que L1 a déjà manqués, c’est-à-dire les difficiles, arrivent à ces niveaux. Ce qui compte est le taux global, la fraction de tous les accès du processeur qui arrivent à la mémoire : m_1m_2m_3, dans l’exemple 0.05\cdot 0.3\cdot 0.4 = 0.6\ \%. Pour comparer deux L2, il faut regarder combien d’accès globaux ils économisent.

Les caches sont dits inclusifs si chaque donnée d’un niveau est aussi dans le niveau inférieur (cela simplifie la cohérence), exclusifs si une donnée n’est que dans un seul niveau (cela exploite mieux la capacité totale).

Les écritures

Un cache à écriture immédiate (write-through) écrit chaque modification aussi dans le niveau inférieur : simple et toujours cohérent, mais il génère beaucoup de trafic, atténué par un tampon d’écriture qui met les écritures en file. Un cache à écriture différée (write-back) n’écrit en mémoire que quand le bloc modifié est évincé, en le marquant d’un bit « sale » (dirty) : beaucoup moins de trafic, parce qu’une donnée modifiée cent fois n’est écrite qu’une fois. Presque tous les caches des processeurs sont à écriture différée ; la cohérence entre les cœurs devient alors le problème de la leçon dédiée.

Aux trois causes classiques de défauts (obligatoires, de capacité, de conflit), les multicœurs en ajoutent une quatrième : les défauts de cohérence, quand un autre cœur a invalidé le bloc.

Caches non bloquants et préchargement

Un processeur à exécution dans le désordre ne s’arrête pas à un défaut : il continue avec des instructions indépendantes, et peut générer d’autres accès. Les caches non bloquants gèrent plusieurs défauts à la fois, en les suivant dans des registres dédiés (MSHR) : les attentes se chevauchent et le temps perdu sur chacune diminue. Le parallélisme au niveau de la mémoire compte autant que le parallélisme au niveau des instructions.

Le préchargement (prefetching) amène des données dans le cache avant qu’elles ne soient nécessaires. Les préchargeurs matériels reconnaissent les accès à pas constant (un tableau lu séquentiellement, une colonne d’une matrice) et demandent à l’avance les blocs suivants. Les compilateurs peuvent insérer des instructions explicites de préchargement. Cela marche si c’est opportun (la donnée arrive à temps) et précis (il n’évince pas des données utiles pour des données inutiles).

Écrire du code adapté aux caches

Le programmeur peut beaucoup. Le produit de deux matrices n\times n sous la forme classique à trois boucles lit l’une des deux matrices par colonnes : si n est grand, chaque élément lu est dans un bloc différent, et le nombre de défauts est de l’ordre de n^3.

Le découpage en blocs (blocking ou tiling) divise les matrices en sous-matrices b\times b assez petites pour tenir ensemble dans le cache (3b^2 éléments, moins que la capacité) et calcule le produit bloc par bloc.

Théorème. Avec le découpage en blocs, le nombre d’éléments transférés depuis la mémoire est de l’ordre de 2n^3/b, au lieu de n^3.

Démonstration. Le produit se décompose en (n/b)^3 produits de blocs b\times b : pour chaque bloc du résultat on additionne n/b produits, et il y a (n/b)^2 blocs de résultat. Chaque produit de blocs charge un bloc de chaque matrice, 2b^2 éléments, puis travaille dans le cache, en effectuant b^3 multiplications sans autre transfert. Le total est (n/b)^3\cdot 2b^2 = 2n^3/b, plus les n^2 éléments du résultat. ∎

Le trafic est réduit d’un facteur proportionnel à b : avec un L1 de 32 Ko et des nombres de 8 octets, b \approx 36, un ordre de grandeur de moins. Les bibliothèques d’algèbre linéaire optimisées appliquent le découpage en blocs à plusieurs niveaux, un par cache, et s’approchent de la performance de crête du processeur. C’est le même principe que l’intensité arithmétique du modèle roofline (leçon sur le SIMD et les GPU).

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