Localité mémoire : pourquoi l’ordre de lecture compte

Une matrice de 8 × 8 entiers est stockée en mémoire ligne après ligne. Entre elle et le processeur se trouve un cache de huit lignes de 16 octets. Calculez la somme par lignes ou par colonnes et suivez les lectures pas à pas. Chaque case indique l’unique ligne de cache où son adresse peut se placer : orange pour un défaut, vert pour un succès, une teinte pâle pour les cases voisines chargées lors d’un défaut.

Exemple résolu — Localité mémoire : pourquoi l’ordre de lecture compte

Lectures dans chaque parcours	64
Blocs de 16 octets utilisés par la matrice	16
Nombre maximal de succès possible	48 sur 64 (75,0 %)
Succès par lignes	48 sur 64 (75,0 %)
Succès par colonnes	0 sur 64 (0,0 %)
Lignes de cache utilisées par la colonne 0	4 sur 8

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Localité mémoire : pourquoi l’ordre de lecture compte

Un cache est une petite mémoire rapide qui conserve des copies de données de la mémoire principale dans des lignes. Chacune contient un bloc aligné de L octets. Une lecture dont le bloc est déjà présent dans une ligne est un succès. Toute autre lecture provoque un défaut, et le bloc entier est chargé. Dans un cache à correspondance directe de S lignes, le bloc contenant l’adresse a ne peut occuper qu’une seule ligne : la ligne ⌊a / L⌋ mod S. Une boucle qui lit successivement des adresses voisines effectue plusieurs lectures dans chaque bloc chargé : elle bénéficie de la localité spatiale.

Ce que signifie chaque symbole

L: la taille d’une ligne en octets : 16 ici, 64 sur la plupart des processeurs d’ordinateurs de bureau et de serveurs
S: le nombre de lignes : 8 ici

Suppose: Le modèle utilise un cache à correspondance directe initialement vide, des entiers de 4 octets et une matrice stockée ligne par ligne, comme en C. Fortran stocke les matrices par colonnes : le parcours le plus rapide y est donc celui par colonnes. Seules les lectures de la matrice sont comptées. Les caches de données réels de premier niveau sont plus grands et associatifs par ensembles, généralement à 8 voies : un bloc peut occuper n’importe laquelle des 8 lignes de son ensemble. Cette organisation élimine la plupart des conflits illustrés ici, mais ne résout pas un manque de capacité. La prélecture matérielle, qui charge la ligne suivante avant qu’elle soit demandée, n’est pas prise en compte.

Les mêmes 64 additions donnent 48 succès ou aucun 🖖

Cliquez sur 8 × 8 par lignes, puis sur 8 × 8 par colonnes. Les deux parcours lisent les mêmes 64 entiers aux mêmes 64 adresses ; seul l’ordre change. Par lignes, la première lecture de chaque ligne de cache de 16 octets provoque un défaut et charge quatre entiers. Les trois suivants sont donc déjà présents : 48 succès. Par colonnes, la lecture suivante passe à la ligne suivante de la matrice, 32 octets plus loin, dans une autre ligne de cache. Ici, une ligne de la matrice occupe exactement deux lignes de cache. La colonne 0 utilise donc exclusivement les lignes 0, 2, 4 et 6, et a[4][0] évince le bloc chargé par a[0][0]. Lorsque la boucle revient à a[0][1], ce bloc a disparu. Les 64 lectures provoquent un défaut. Ulrich Drepper a mesuré ce phénomène à plus grande échelle en 2007 : pour une multiplication de matrices de 1000 × 1000 sur un Intel Core 2, transposer au préalable la matrice lue par colonnes permettait de lire les deux matrices par lignes. Le calcul ne prenait alors que 23,4 % du nombre initial de cycles d’horloge.

Tant que la matrice tient dans le cache, l’ordre ne change rien 🖖

Réglez la taille sur 5 et changez l’ordre : vous obtenez 18 succès sur 25 dans les deux cas. La matrice occupe 100 octets pour un cache de 128 octets. Ses sept blocs se placent dans sept lignes distinctes ; une fois chargés, ils ne sont jamais évincés. Chaque bloc provoque un seul défaut, à sa première lecture, quel que soit le parcours. À 6 × 6, la matrice occupe 144 octets et deux de ses blocs doivent partager une ligne de cache. Les résultats divergent : 27 succès par lignes, 25 par colonnes. Sans remplissage, le parcours par colonnes reste moins performant pour toutes les tailles suivantes, jusqu’à 16 × 16.

Quatre entiers inutilisés par ligne font passer de 0 à 48 succès 🖖

Cliquez sur Lignes avec remplissage. Vous retrouvez la même matrice de 8 × 8, lue par colonnes, mais chaque ligne est suivie de quatre entiers qui ne sont jamais lus. Elle occupe ainsi 48 octets, soit trois lignes de cache au lieu de deux. Trois et huit sont premiers entre eux : la colonne 0 utilise désormais les huit lignes du cache. Ses huit blocs y coexistent, et les trois colonnes suivantes les retrouvent en place : 48 succès sur 64, autant que par lignes. Cela coûte 128 octets qui ne sont jamais lus. Le remplissage supprime les défauts de conflit, qui surviennent lorsque deux blocs se disputent une ligne de cache alors que d’autres restent vides. Il n’augmente pas la capacité du cache. Le problème résolu se termine justement sur une matrice pour laquelle cette capacité est insuffisante.

Problème entièrement résolu

Quel trafic mémoire coûte un parcours dans le mauvais ordre ? 4 étapes
Cliquez sur 8 × 8 par colonnes et expliquez les 0 succès. Considérez ensuite une matrice de 1024 × 1024 entiers de 4 octets et un cache à correspondance directe de 32 Kio, composé de lignes de 64 octets. Combien d’octets sont transférés depuis la mémoire pour calculer la somme par lignes ? Et par colonnes ? Ajouter une ligne de cache de remplissage après chaque ligne de la matrice améliore-t-il le résultat ?

Ouvrez ce problème dans l'outil
1. Dans la simulation, une ligne de la matrice occupe 8 × 4 = 32 octets, soit deux lignes de cache. La ligne i commence donc dans la ligne de cache 2i mod 8, et la colonne 0 n’utilise que les lignes 0, 2, 4 et 6. a[4][0] prend la place de a[0][0]. Lorsque la boucle atteint a[0][1], son bloc a disparu : 0 succès sur 64. Par lignes, chaque bloc de 16 octets provoque un seul défaut. Il y a 16 blocs, donc 48 succès, soit 1 − 4/16 = 75 %.
  
  $8 \times 4 = 32 bytes = 2 lines : 2 i mod 8 \in {0, 2, 4, 6}, 64 - 16 = 48 hits by rows$
2. Le grand cache compte 32 768 / 64 = 512 lignes. Par lignes, chaque ligne de cache de 64 octets contient 16 entiers et seule leur première lecture provoque un défaut : 1 048 576 / 16 = 65 536 défauts, un taux de succès de 1 − 4/64 = 93,75 % et 65 536 × 64 = 4 194 304 octets transférés. La matrice est chargée exactement une fois.
  
  $\frac{32 768}{64} = 512 lines, \frac{1 048 576}{16} = 65536 misses, 65536 \times 64 = 4194304$
3. Par colonnes, une ligne de la matrice occupe 4 096 octets, soit 64 lignes de cache. La ligne i commence donc dans la ligne de cache 64i mod 512, et une colonne n’utilise que 8 des 512 lignes. a[8][0] évince le bloc de a[0][0], bien avant que la boucle revienne à a[0][1]. Chacune des 1 048 576 lectures provoque un défaut : 67 108 864 octets sont transférés, soit 16 fois plus.
  
  $\frac{4 096}{64} = 64 : 64 i mod 512 takes 8 values, 1048576 \times 64 = 67108864$
4. Ajouter 16 entiers de remplissage après chaque ligne porte sa longueur à 4 160 octets, soit 65 lignes de cache. 65 et 512 sont premiers entre eux : une colonne utilise désormais les 512 lignes. Elle ne donne toujours aucun succès. Elle parcourt 1 024 blocs, alors que le cache ne peut en contenir que 512 ; chaque bloc est donc évincé avant que la colonne suivante en ait besoin.
  
  $\frac{4 160}{64} = 65, g cd (65, 512) = 1, 1024 blocks > 512 lines$
Réponse

4 Mio par lignes, 64 Mio par colonnes. Le remplissage répartit les blocs d’une colonne sur tout le cache, sans obtenir de succès. Il résout les conflits, mais les blocs nécessaires à chaque colonne de cette matrice dépassent la capacité totale du cache.

$4 MiB by rows, 64 MiB by columns (16 \times)$

Parcours

Comment un ordinateur exécute un programme

Références (1)

The first insight's measured case, the line size in the definition, and the 8-way first-level caches in `assumes`: Ulrich Drepper, "What Every Programmer Should Know About Memory," Red Hat, Inc., version 1.0, 21 November 2007. §3.2 (p. 15), §3.3.1 (pp. 17–18), §6.2.1 (pp. 49–50).

Par l’équipe 42Math · Vérifié sur des sources publiées. Corrections bienvenues.