Hiérarchie mémoire et caches

Un cache fonctionne parce que le prochain accès mémoire est souvent lié à un accès récent. Pendant un court intervalle, la plupart des programmes n’utilisent qu’une petite partie de leur espace d’adressage. Cette propriété est la localité. Un cache garde cette partie active près du processeur, où il peut traiter rapidement les accès.

Réutilisation dans le temps et dans l’espace

La localité temporelle consiste à réutiliser un élément peu après y avoir accédé. Une boucle charge à plusieurs reprises les instructions de son corps. Un total cumulé est lu et mis à jour de nombreuses fois. Garder ces éléments disponibles évite de les chercher à nouveau dans un niveau plus lent.

La localité spatiale consiste à accéder à des éléments situés à des adresses proches. Le parcours d’un tableau lit des éléments adjacents, et un code sans branchement charge des instructions successives. Un cache exploite cette propriété en chargeant un bloc entier, aussi appelé ligne de cache, lors d’un défaut. Les octets voisins arrivent avant que le programme ne les demande.

Ces propriétés peuvent se manifester ensemble. Les instructions d’une boucle sont adjacentes et s’exécutent à plusieurs reprises : le flux d’instructions présente donc une localité spatiale et temporelle. Un élément de tableau lu exactement une fois ne présente aucune réutilisation temporelle, même si le parcours du tableau environnant présente une localité spatiale.

Compter les blocs lors du parcours d’un tableau

Considère cette boucle C avec des entiers de 4 octets et des blocs de cache de 64 octets :

for (int i = 0; i < 1000; i++) {
    sum += a[i];
}

Un bloc contient $64\mathrm{/}4=16$ entiers. Le tableau occupe $1000\times 4=4000$ octets. Si son premier élément est aligné sur une frontière de bloc, le parcours touche $\lceil 4000\mathrm{/}64\rceil =63$ blocs : 62 blocs entiers et un bloc partiel.

Dans un cache initialement vide, sans préchargement ni interférence, le premier accès à chaque bloc produit un défaut. Les accès aux autres éléments de ce bloc réussissent. Le tableau provoque donc 63 défauts en 1000 accès, soit environ 6,3 %. Compter un défaut par élément reviendrait à ignorer toutes les données voisines utiles chargées à chaque défaut.

Les variables du code source sum et i sont fréquemment réutilisées. Un compilateur les conserve toutefois généralement dans des registres ; leur réutilisation dans le code source ne produit donc pas nécessairement d’accès au cache de données. Pour estimer le trafic du cache, analyse les accès mémoire exécutés par le programme compilé.

L’ensemble de travail doit tenir et ses blocs doivent coexister

L’ensemble de travail est l’ensemble des blocs utilisés pendant une fenêtre de temps choisie. S’ils tiennent dans le cache et que les règles de placement leur permettent de coexister, les accès répétés réussissent pour la plupart après les chargements initiaux. La fenêtre de temps compte : un programme entier peut être immense alors qu’une boucle active n’utilise que quelques blocs.

La capacité seule ne suffit pas. Deux blocs très utilisés peuvent correspondre à une même entrée d’un cache à correspondance directe et s’évincer mutuellement alors que d’autres entrées restent vides. Un ensemble de travail peut donc tenir dans le cache en nombre d’octets sans pouvoir y rester.

Les nœuds dispersés d’une liste chaînée et les recherches aléatoires dans une grande table de hachage présentent souvent une faible localité spatiale. Un parcours par colonnes d’un tableau rangé par lignes saute également de nombreux éléments voisins. Ces schémas chargent des octets qui risquent de ne pas être utilisés avant leur éviction. Le matériel exploite la localité du schéma d’accès ; modifier l’organisation ou le parcours du programme peut rendre utile une plus grande partie de chaque bloc chargé.

Les technologies de mémoire font des compromis entre vitesse, densité, coût et persistance. Le processeur a besoin d’accéder rapidement à une petite quantité de données et de disposer d’un espace abordable pour une quantité bien plus grande. Les mémoires SRAM, DRAM et flash répondent chacune à une partie de ce besoin.

Comparer les cellules

Une cellule SRAM est rapide, mais occupe une surface importante, ce qui rend la SRAM relativement coûteuse par bit. Les cellules DRAM sont plus petites, de sorte que la DRAM offre une capacité supérieure à un coût par bit inférieur. Leur charge se dissipe. Le rafraîchissement lit et restaure les lignes dans un délai fixe ; la DDR4 à température normale utilise un délai de 64 ms. Dans SRAM, « statique » signifie que le rafraîchissement est inutile, et non que les données persistent après une coupure d’alimentation.

Pourquoi le temps d’accès à la DRAM varie

La DRAM est organisée en banques, chacune comportant des lignes et des colonnes. L’activation d’une ligne la copie dans un tampon de ligne. Les lectures et les écritures sélectionnent ensuite des colonnes de cette ligne ouverte. Pour ouvrir une autre ligne dans la même banque, celle-ci doit d’abord être préchargée. Un accès à une ligne déjà ouverte évite ce changement de ligne.

Des colonnes consécutives peuvent être transférées en rafale, ce qui convient au chargement d’un bloc de cache. Répartir les demandes entre les banques et les canaux permet aux transferts de se chevaucher. La mémoire DDR transfère des données sur les deux fronts d’horloge. Ces caractéristiques augmentent le débit de livraison des données sans supprimer l’attente des premières données.

Distinguer latence et bande passante

La latence est le délai avant l’arrivée des premières données. La bande passante est la quantité transférée par unité de temps. Une interface à forte bande passante peut malgré tout présenter un long délai initial.

Par exemple, un canal DDR5-4800 doté d’un chemin de données total de 64 bits transporte 8 octets par transfert. Son débit de crête est de $4800\times {10}^6\times 8=\mathrm{38,4}\times {10}^9$ octets/s, soit 38,4 GB/s. La bande passante soutenue d’une application peut être inférieure, car les commandes, les changements de ligne et d’autres opérations prennent du temps.

Si une requête attend 60 ns puis reçoit un bloc de 64 octets à 16 GB/s, le débit de transfert est de 16 octets/ns. Le transfert prend $64\mathrm{/}16=4$ ns, soit environ 64 ns au total. Améliorer seulement la bande passante réduit les 4 ns du transfert, pas les 60 ns initiaux.

La mémoire flash conserve les données mais traite différemment les écritures

La mémoire flash NAND lit et programme des pages de plusieurs KiB. Pour réutiliser une page programmée, il faut effacer le bloc d’effacement plus grand qui la contient, composé de nombreuses pages. La lecture d’une page prend généralement des dizaines de microsecondes, sa programmation de quelques centaines de microsecondes à quelques millisecondes, et l’effacement des millisecondes.

Les cycles de programmation et d’effacement usent les cellules. La mémoire flash dense à plusieurs bits supporte souvent quelques milliers de cycles, tandis que les cellules à un bit peuvent en supporter environ 100 000. Les contrôleurs utilisent la répartition de l’usure pour distribuer les écritures entre les blocs.

Pour donner un ordre de grandeur, l’accès à la SRAM prend environ 1 ns, celui à la DRAM environ 50 à 100 ns, la lecture en mémoire flash NAND environ 25 à 100 µs et l’accès au disque environ 5 à 10 ms. Les valeurs varient selon les appareils. La hiérarchie associe ces technologies parce qu’aucune ne peut réunir à elle seule leurs avantages en matière de vitesse, de capacité et de prix.

La hiérarchie mémoire place de petits espaces de stockage rapides près du processeur et des espaces de plus en plus grands à mesure que l’on s’en éloigne. La localité permet aux petits niveaux de traiter une grande partie des demandes, tandis que les niveaux inférieurs fournissent la capacité.

Niveaux et unités de transfert

Un parcours typique passe par les registres, L1, L2, L3, la mémoire principale et le stockage. L1 possède généralement des caches séparés pour les instructions et les données, d’environ 32 à 64 KiB chacun par cœur. L2 occupe souvent plusieurs centaines de KiB à quelques MiB par cœur, tandis que L3 est souvent partagé et contient plusieurs à plusieurs dizaines de MiB. La mémoire principale contient de nombreux GiB et le stockage plusieurs centaines de GB ou plus. Les tailles et les modes de partage varient selon les conceptions.

Sur un processeur fonctionnant à près de 3 GHz, les latences de chargement représentatives sont d’environ 4 à 5 cycles pour L1, 12 à 15 pour L2, 30 à 50 pour L3 et 200 à 300 pour la DRAM. Un cache L1 peut accepter une nouvelle demande à chaque cycle même lorsqu’une demande prend plusieurs cycles pour aboutir : le débit et la latence décrivent des propriétés différentes.

Les données circulent dans les caches par blocs, généralement de 64 octets. La mémoire virtuelle utilise des pages, généralement de 4 KiB, pour transférer leur contenu entre la mémoire et le stockage. Une ligne de cache et une page remplissent des fonctions de regroupement similaires à des échelles différentes ; ce ne sont pas les mêmes unités de transfert.

Succès, défauts et durée

Un succès signifie qu’un niveau contient les données demandées. Un défaut signifie qu’il doit obtenir les données du niveau inférieur. Les deux termes concernent le niveau consulté : un défaut de L1 peut encore être un succès dans L2.

Le taux de succès est le nombre de succès divisé par le nombre d’accès, et le taux de défauts vaut un moins le taux de succès. Le temps d’accès en cas de succès comprend la consultation du niveau et la vérification du succès de la demande. La pénalité de défaut de cache est le temps supplémentaire nécessaire, lors d’un défaut, pour obtenir et fournir le bloc.

Supposons qu’un cache simplifié ait un temps d’accès en cas de succès de 1 cycle, un taux de succès de 97 % et une pénalité supplémentaire de défaut de 100 cycles. Chaque accès paie 1 cycle, tandis que 3 % paient 100 cycles de plus :

Un défaut prend 101 cycles dans cet exemple. Utiliser 100 comme temps total d’un défaut reviendrait à compter la recherche initiale de façon incohérente. Même avec un taux de succès élevé, les défauts coûteux restent visibles dans la moyenne.

Qui gère chaque niveau ?

Le compilateur affecte les valeurs appropriées aux registres. Le matériel du cache déplace automatiquement les blocs lors des chargements, des rangements et des chargements d’instructions. Les programmes désignent des adresses ; ils ne sélectionnent pas les entrées du cache. Le système d’exploitation gère les correspondances de la mémoire virtuelle avec l’aide du matériel et traite les pages qui doivent être chargées en mémoire principale.

Séparer les instructions des données dans L1 permet à un pipeline de charger une instruction et d’accéder à des données en même temps sans se disputer un port de cache. Les caches inférieurs sont généralement unifiés et stockent à la fois des blocs d’instructions et de données.

Certaines hiérarchies sont inclusives : un bloc présent à un niveau supérieur possède aussi une copie à un niveau inférieur. D’autres sont exclusives ou non inclusives ; une copie dans chaque cache inférieur n’est donc pas garantie. Représente la hiérarchie comme un chemin de recherche et de transfert, et non comme une garantie que tous les niveaux contiennent des sous-ensembles identiques.

Agrandir L1 peut réduire les défauts, mais augmenter le délai d’accès et la consommation d’énergie. L’ajout de caches inférieurs plus grands permet de garder L1 rapide tout en traitant un grand nombre de ses défauts avant d’atteindre la DRAM. Évalue ce compromis à l’aide du temps d’accès, pas seulement de la capacité.

Une adresse d’octet désigne un octet en mémoire. Un cache charge un bloc entier : la recherche repère donc d’abord ce bloc, puis sélectionne les octets demandés à l’intérieur. Dans un cache à correspondance directe, chaque bloc ne possède qu’une seule entrée possible.

Décomposer l’adresse selon le rôle des champs

Pour une taille de bloc de $2^b$ octets, les $b$ bits de poids faible de l’adresse forment le déplacement. Diviser l’adresse de l’octet par la taille du bloc et ignorer le reste donne l’adresse du bloc. Le reste est le déplacement.

Si le cache possède $E$ entrées, l’index de l’entrée est

Lorsque le nombre d’entrées est une puissance de deux, l’index est le groupe de bits de l’adresse situé immédiatement au-dessus du déplacement. Les bits de poids fort restants forment l’étiquette, qui indique au cache lequel des nombreux blocs partageant un index est présent.

L’ordre des champs, des bits de poids fort aux bits de poids faible, est étiquette | index | déplacement. Pour une adresse de $A$ bits :

Utilise le nombre d’entrées pour calculer l’index. Prendre le logarithme de la capacité en octets reviendrait à compter une seconde fois les bits de déplacement.

Étudier un exemple de 16 KiB

Un cache à correspondance directe de 16 KiB avec des blocs de 64 octets possède $16384\mathrm{/}64=256$ entrées. Le déplacement occupe 6 bits, l’index 8 bits et l’étiquette $32-8-6=18$ bits pour des adresses de 32 bits.

Pour l’adresse d’octet 0x1234ABCD, les 6 bits de poids faible donnent le déplacement 13, soit 0x0D. Retirer ces bits donne l’adresse de bloc 0x48D2AF. Ses 8 bits de poids faible sont 0xAF ; l’index est donc 175. Les bits restants donnent l’étiquette 0x48D2.

L’adresse de l’octet peut être reconstruite à partir de ces champs : concatène l’étiquette, l’index de 8 bits et le déplacement de 6 bits. La largeur des champs compte, car un chiffre hexadécimal représente 4 bits ; les frontières ne tombent pas nécessairement entre deux chiffres hexadécimaux.

Une étiquette correspondante exige une entrée valide

Chaque entrée stocke des données, une étiquette et un bit de validité. L’index sélectionne l’entrée. Un succès exige à la fois un bit de validité activé et l’égalité entre l’étiquette stockée et l’étiquette demandée. Au démarrage, une entrée peut contenir des bits quelconques ; le bit de validité empêche de les prendre pour un bloc chargé.

Une fois le bloc présent, les accès à ses autres octets réussissent aussi. Un succès ne nécessite pas l’adresse exacte de l’octet utilisé pour charger le bloc.

Compter les métadonnées séparément

La capacité indiquée d’un cache ne compte normalement que les données. Ici, chaque entrée contient 512 bits de données, 18 bits d’étiquette et 1 bit de validité, soit 531 bits. Le stockage total est de

Les données seules utilisent 131 072 bits. Les étiquettes et la validité ajoutent 4 864 bits, soit environ 3,7 % du stockage des données. Une conception à écriture différée nécessite aussi des bits de modification ; des conceptions plus complexes nécessitent d’autres états de contrôle.

L’index utilise les bits de poids faible de l’adresse du bloc afin que les blocs successifs se répartissent sur des entrées successives. Une adresse plus large ne modifie pas la largeur du déplacement et de l’index lorsque la capacité et la taille des blocs restent fixes ; les bits supplémentaires allongent l’étiquette.

Une trace de cache indique comment chaque accès modifie les blocs stockés. Garde un état distinct pour chaque entrée et mets-le à jour immédiatement après chaque défaut. La demande suivante utilise le cache mis à jour, et non son état initial.

Préparer la trace

Prenons un cache à correspondance directe de 64 octets comportant quatre entrées de 16 octets. Il est initialement vide. Pour chaque adresse d’octet, divise par 16 pour trouver le bloc, puis calcule le numéro de bloc modulo 4 pour obtenir l’index. L’étiquette est le numéro de bloc divisé par 4, sans sa partie fractionnaire. Le déplacement occupe 4 bits et l’index 2 bits.

Lors d’une lecture, examine l’entrée sélectionnée. Si elle est valide et que l’étiquette correspond, consigne un succès. Sinon, consigne un défaut, remplace le bloc et l’étiquette de cette entrée, puis active son bit de validité. Dans un cache à correspondance directe, aucun choix de remplacement n’est possible.

Suivre les huit accès

Le premier accès remplit l’entrée 0 avec le bloc 0. L’adresse suivante, 0x04, se trouve toujours dans ce bloc de 16 octets : l’accès réussit donc bien qu’elle désigne un autre octet. 0x40 appartient au bloc 4. Il a le même index que le bloc 0, mais une étiquette différente ; il remplace donc le bloc 0.

Le second accès à 0x00 échoue donc. Une utilisation antérieure ne suffit pas à garantir un succès : le bloc doit encore être présent. La demande à l’adresse 0x14 charge le bloc 1 dans l’entrée 1, sans modifier l’entrée 0.

Ensuite, 0x44 charge à nouveau le bloc 4 dans l’entrée 0. 0x08 nécessite le bloc 0 et évince le bloc 4. Enfin, 0x84 charge le bloc 8 dans cette même entrée. À la fin, l’entrée 0 contient le bloc 8 et l’entrée 1 contient le bloc 1 ; les entrées 2 et 3 restent invalides.

Interpréter le comportement

Il y a un succès et sept défauts ; le taux de succès est donc de $1\mathrm{/}8=\mathrm{12,5}\mathrm{\%}$. Les blocs 0, 4 et 8 se disputent l’entrée 0. Le cache possède quatre entrées, mais ce schéma d’accès n’en utilise que deux. Les évictions répétées sont dues à des conflits de correspondance, et non à un manque de stockage total pour les quatre blocs distincts.

Le chargement d’un bloc rend tous ses octets disponibles. Lors d’un parcours séquentiel, un défaut peut donc servir de nombreux éléments suivants. Ici, les accès en conflit suppriment à plusieurs reprises cet avantage avant que l’octet voisin suivant ne soit demandé.

Pour obtenir une trace fiable, indique explicitement les adresses d’octets et les numéros de blocs. Appliquer directement le modulo 4 à l’adresse d’octet omet la division par la taille du bloc et envoie les demandes vers les mauvaises entrées. Consigne le remplacement même lorsque le nouveau bloc a déjà été chargé auparavant : chaque défaut installe le bloc demandé et son étiquette dans l’entrée sélectionnée.

Un cache associatif par ensembles offre plusieurs entrées possibles à un bloc sans chercher dans tout le cache. L’index sélectionne un ensemble, et le bloc peut occuper n’importe quelle voie de cet ensemble. Cela réduit les conflits entre les blocs qui partagent un index.

Calculer les ensembles et les champs

Pour une capacité de données $C$, une taille de bloc $B$ et une associativité $n$ :

L’index de l’ensemble est l’adresse du bloc modulo le nombre d’ensembles. Le déplacement dépend toujours uniquement de la taille du bloc. L’étiquette contient les bits de poids fort restants.

Un cache de 32 KiB à 8 voies avec des blocs de 64 octets possède 512 blocs et 64 ensembles. Avec des adresses de 32 bits, le déplacement, l’index et l’étiquette occupent 6, 6 et 20 bits. L’adresse 0x1234ABCD a pour déplacement 13, ensemble 47 et étiquette 0x1234A.

À capacité et taille de bloc constantes, doubler l’associativité divise par deux le nombre d’ensembles. Un bit d’index devient un bit d’étiquette ; aucune capacité de données n’est ajoutée.

La recherche compare en parallèle l’étiquette à toutes les étiquettes valides de l’ensemble choisi. Une voie dont l’étiquette correspond fournit les données par l’intermédiaire d’un sélecteur. Davantage de voies exigent davantage de comparaisons et de matériel de sélection, ce qui peut augmenter le temps d’accès en cas de succès et la consommation d’énergie.

Ne remplacer un bloc que lorsque l’ensemble est plein

Utilise d’abord une voie invalide. Lorsque toutes les voies sont occupées, LRU évince le bloc dont l’accès le plus récent est le plus ancien. Mets à jour l’ordre d’utilisation aussi bien lors des succès que des chargements. Un ensemble à 2 voies ne nécessite qu’un bit pour repérer sa voie LRU ; les ensembles plus grands utilisent souvent des approximations pseudo-LRU.

FIFO évince le bloc chargé en premier, même s’il a été utilisé récemment. Le remplacement aléatoire choisit une victime sans conserver l’ordre complet des utilisations. Il est simple et peut offrir des performances proches de LRU dans les grands caches.

Reprendre la petite trace avec deux voies

Le cache de 64 octets avec des blocs de 16 octets possède maintenant deux ensembles de deux voies. Les blocs 0, 4 et 8 correspondent à l’ensemble 0, tandis que le bloc 1 correspond à l’ensemble 1. Pour 0x00, 0x04, 0x40, 0x00, 0x14, 0x44, 0x08, 0x84, les résultats sont défaut, succès, défaut, succès, défaut, succès, succès, défaut.

Les blocs 0 et 4 peuvent coexister ; les accès répétés à ces blocs réussissent donc. Juste avant le dernier accès, le bloc 0 a été utilisé plus récemment que le bloc 4. Avec LRU, le chargement du bloc 8 évince le bloc 4. Quatre accès sur huit réussissent, contre un dans la version à correspondance directe.

L’associativité ne peut ni supprimer les défauts à froid ni faire tenir un ensemble de travail plus grand que la capacité. Elle ne peut pas non plus empêcher les conflits lorsque plus de n blocs très utilisés se disputent un ensemble à n voies. Un cycle répété de n+1 blocs de ce type peut provoquer un défaut LRU à chaque accès. Ajouter du remplissage aux tableaux peut modifier leur correspondance avec les ensembles ; augmenter le nombre de voies n’est qu’une réponse possible à un problème de conflit.

Un défaut de cache est un événement qui possède à la fois un mécanisme et une cause. Le mécanisme décrit comment la demande est traitée. La cause explique pourquoi le bloc nécessaire était absent et quelle modification de conception pourrait aider.

Traiter un défaut en lecture

Dans un pipeline simple à exécution dans l’ordre, le cache détecte une entrée invalide ou une étiquette non correspondante, et le processeur se bloque. Le cache demande le bloc au niveau suivant. Si la victime choisie est modifiée, ses données modifiées doivent être conservées par écriture différée. Le bloc qui arrive est installé avec son étiquette et son bit de validité, puis l’accès en attente se termine. De même, lors d’un défaut du cache d’instructions, le processeur attend le bloc de l’instruction puis charge à nouveau celle-ci.

La technique du mot critique en premier demande en premier le mot nécessaire dans le bloc renvoyé. Le redémarrage anticipé permet à l’exécution de reprendre dès l’arrivée de ce mot. Un cache non bloquant peut traiter d’autres succès et suivre les défauts en attente pendant qu’un processeur à exécution dans le désordre effectue un travail indépendant. Ces mécanismes réduisent l’attente ; ils ne font pas disparaître la dépendance initiale aux données.

Utiliser les trois C

Applique d’abord le test du premier accès. Le premier accès à un bloc produit un défaut à froid même si son entrée de destination est déjà occupée. Pour les défauts ultérieurs, compare le cache réel à un cache LRU totalement associatif de même capacité de données et de même taille de bloc, les deux recevant le même historique d’accès.

Dans la trace précédente à quatre entrées, les blocs 0, 4, 1 et 8 provoquent chacun un défaut à froid. Le cache à correspondance directe subit aussi des défauts lors des accès répétés aux blocs 0 et 4. Un cache totalement associatif à quatre entrées peut conserver les quatre blocs distincts : ces trois défauts sur des accès répétés sont donc des défauts de conflit. Il n’y a pas de défaut de capacité.

Choisir une modification qui traite la cause

Augmenter la capacité peut permettre de conserver un ensemble de travail plus grand. Augmenter l’associativité peut permettre à des blocs en conflit de coexister. Augmenter la taille des blocs peut exploiter la localité spatiale en chargeant davantage de données voisines utiles à chaque remplissage.

La taille des blocs produit des effets opposés. À capacité de données fixe, des blocs plus grands signifient moins de blocs présents. Les octets inutilisés occupent de l’espace dans le cache, des blocs utiles sans rapport peuvent être évincés et chaque transfert peut prendre plus de temps. Le taux de défauts baisse souvent d’abord lorsque la taille des blocs augmente, puis remonte quand ces coûts dépassent le bénéfice de la localité spatiale.

Un cache plus grand peut aussi avoir un temps de recherche plus long, et des voies supplémentaires nécessitent davantage de matériel de comparaison. Évalue les modifications à partir du temps d’accès moyen, en tenant compte du temps d’accès en cas de succès et de la pénalité de défaut, au lieu de supposer qu’un taux de défauts plus bas garantit une conception plus rapide.

Dans les systèmes multicœurs, l’invalidation consécutive à l’écriture d’un autre cœur peut provoquer des défauts de cohérence. Le préchargement peut charger un bloc avant son premier accès sur demande, masquant un défaut sur demande qu’une capacité supplémentaire seule ne peut pas éviter.

Un rangement modifie une valeur ; la hiérarchie a donc besoin d’une règle pour transmettre cette modification vers le niveau inférieur. Deux choix distincts interviennent : que faire lorsque le rangement réussit et que faire lorsqu’il échoue.

Écriture simultanée et écriture différée

Un bit de modification indique qu’un bloc à écriture différée contient des changements qui n’ont pas encore été écrits au niveau suivant. Une victime non modifiée n’a pas besoin d’être réécrite. Les données modifiées d’une victime doivent être conservées avant que son entrée puisse être réutilisée. Les chargements du processeur obtiennent la nouvelle valeur dans le cache même lorsque la copie du niveau inférieur est plus ancienne.

Pour 100 rangements dans une même variable de 4 octets présente dans le cache, l’écriture simultanée sans regroupement envoie 100 écritures, soit 400 octets de données utiles. L’écriture différée peut réunir ces modifications dans une seule écriture d’un bloc de 64 octets lors de son éviction. Cette comparaison compte les données utiles des mises à jour, sans le chargement initial ni le surcoût du protocole.

Le bénéfice dépend de la réutilisation. Des écritures répétées dans un même bloc donnent à l’écriture différée l’occasion de regrouper les mises à jour ; des écritures dispersées sur de nombreux blocs peuvent entraîner de nombreuses évictions de blocs modifiés. Les caches inférieurs utilisent couramment l’écriture différée pour limiter le trafic vers la DRAM. Les caches de données L1 peuvent utiliser l’une ou l’autre politique.

Un tampon d’écriture masque l’attente, pas le trafic

Un tampon d’écriture met en file les écritures en attente vers le niveau inférieur. Avec l’écriture simultanée, le processeur peut continuer dès qu’un rangement est entré dans le tampon, sans attendre la fin de l’écriture en mémoire inférieure. Le niveau inférieur rattrape son retard à mesure que les écritures quittent le tampon ; il peut temporairement être en retard sur la valeur du cache.

Le tampon a une capacité limitée. Si les rangements arrivent assez longtemps plus vite que le niveau inférieur ne les accepte, il se remplit et le processeur se bloque. Un tampon modifie le moment où le processeur attend, pas la bande passante soutenable de la destination.

Sans tampon ni chevauchement, si 10 % des instructions sont des rangements et que chaque rangement ajoute 100 cycles d’attente, un CPI de base de 1 devient $1+\mathrm{0,1}\times 100=11$. Le tampon peut masquer une grande partie de ce délai lorsque la destination suit le rythme en moyenne.

Traiter séparément un défaut en écriture

L’allocation sur écriture charge le bloc absent dans le cache, puis effectue le rangement. Elle s’associe naturellement à l’écriture différée, car les accès et écritures ultérieurs peuvent réutiliser ce bloc. L’écriture sans allocation sur écriture transmet le rangement au niveau inférieur sans remplir ce cache. Elle s’associe naturellement à l’écriture simultanée et peut éviter d’évincer des blocs utiles lors d’un flux de sortie unique.

Ces choix de politique sont indépendants. Savoir qu’un cache utilise l’écriture simultanée ne suffit pas à déterminer si un défaut en écriture alloue une ligne ; une trace doit préciser les deux politiques.

Un défaut dans un cache à écriture différée qui choisit une victime modifiée implique une sortie de données en plus du chargement entrant, ce qui augmente la pénalité, sauf si des tampons ou un chevauchement masquent une partie du travail. Les autres cœurs et les périphériques d’entrée-sortie ont aussi besoin d’une vue cohérente lorsque la mémoire inférieure contient des données périmées. Les mécanismes de cohérence et du système coordonnent cette visibilité ; un bit de modification ne fait qu’enregistrer les changements en attente.

Un taux de succès élevé est utile, mais ne constitue pas une mesure complète de la performance. Un petit nombre de défauts coûteux peut dominer la moyenne, et une conception qui évite davantage de défauts peut tout de même être moins performante si sa recherche devient trop lente.

Partir des taux et des définitions de temps

La somme des deux proportions vaut un. Convertis les pourcentages en proportions avant de multiplier : 5 % correspond à 0,05.

Le temps moyen d’accès mémoire, ou temps attendu par accès, est

Chaque demande consulte le cache, y compris celles qui échouent. La pénalité est le délai supplémentaire après cette recherche. De manière équivalente, pondère le temps d’accès en cas de succès par la proportion de succès et le temps total en cas de défaut par la proportion de défauts ; le développement donne la même formule.

Avec un temps d’accès en cas de succès de 1 cycle, 5 % de défauts et une pénalité supplémentaire de 100 cycles, le temps moyen d’accès mémoire est de $1+\mathrm{0,05}\times 100=6$ cycles. À 2 GHz, chaque cycle dure 0,5 ns, soit 3 ns. Effectue tous les calculs en cycles ou tous en unités de temps, puis convertis le résultat final si nécessaire.

Comparer des conceptions complètes

Le cache A a un temps de recherche de 1,0 ns et 5 % de défauts. Le cache B a un temps de recherche de 1,2 ns et 3,5 % de défauts. Avec une pénalité de 50 ns :

B l’emporte, car éviter des défauts coûteux compense largement sa recherche plus lente. Si la pénalité tombe à 10 ns, A prend 1,5 ns et B prend 1,55 ns. A l’emporte alors. L’intérêt d’une baisse du taux de défauts dépend de la pénalité qu’elle évite.

Pondérer correctement les accès aux instructions et aux données

Supposons que chaque instruction produise un chargement d’instruction et 0,3 accès aux données en moyenne. Le taux de défauts des instructions est de 2 % et celui des données de 4 %. Pour 100 instructions, il y a 100 chargements d’instructions et 30 accès aux données. Le nombre de défauts attendus est de $100\times \mathrm{0,02}+30\times \mathrm{0,04}=\mathrm{3,2}$ sur 130 accès.

La proportion de défauts combinée est donc $\frac{\mathrm{0,02}+\mathrm{0,3}\times \mathrm{0,04}}{\mathrm{1,3}}\mathrm{.}$ Avec des temps d’accès en cas de succès égaux à 1 cycle et des pénalités de 100 cycles, le temps moyen d’accès mémoire est d’environ 3,46 cycles par accès mémoire. Calculer directement la moyenne de 2 % et 4 % donnerait à tort le même poids aux deux types d’accès.

Estimer une pénalité de transfert

Une demande de bloc peut comprendre une latence initiale suivie du temps de transfert. Avec une latence de 60 ns, une ligne de 64 octets et une bande passante de 16 GB/s, le transfert prend 4 ns, ce qui donne une pénalité supplémentaire d’environ 64 ns. À 3 GHz, il y a 3 cycles/ns, soit 192 cycles.

Vérifie ce que comprend le temps indiqué dans un problème. S’il donne le temps complet d’un accès en cas de défaut, soustrais le temps de recherche en cas de succès avant de traiter cette valeur comme une pénalité supplémentaire de défaut. Compter deux fois la recherche surestime le temps moyen d’accès mémoire.

Le temps moyen d’accès mémoire mesure le temps par accès mémoire. Le CPI mesure les cycles par instruction exécutée. Pour les relier, compte le nombre de demandes d’instructions et de données produites par chaque instruction ainsi que les cycles d’attente qu’elles ajoutent.

Ajouter les termes d’attente

Pour un processeur simple à exécution dans l’ordre dont les succès de cache sont inclus dans le CPI de base, un défaut sans chevauchement ajoute sa pénalité supplémentaire. Avec un taux de défauts des instructions $m_I$, un nombre d’accès aux données par instruction $f_D$, un taux de défauts des données $m_D$ et une pénalité $P$ en cycles :

Dans ce modèle, chaque instruction donne lieu à une demande de chargement d’instruction. Seuls les chargements et les rangements produisent des demandes de données : multiplie donc leur taux de défauts par leur fréquence. Si leurs pénalités diffèrent, utilise une pénalité distincte dans chaque terme.

Passer des demandes aux attentes

Soit un CPI de base de 1,0, un taux de défauts des instructions de 2 %, une fréquence de chargements et de rangements de 30 %, un taux de défauts des données de 4 % et une pénalité de défaut de 100 cycles. Les attentes liées aux instructions sont de $\mathrm{0,02}\times 100=\mathrm{2,0}$ cycles par instruction. Les attentes liées aux données sont de $\mathrm{0,3}\times \mathrm{0,04}\times 100=\mathrm{1,2}$. Le CPI total est de 4,2.

Avec un cache parfait, le CPI reviendrait à 1,0. À fréquence d’horloge et nombre d’instructions égaux, cela représenterait une accélération d’un facteur 4,2. Le taux de défauts des données est le double de celui des instructions, mais les défauts des instructions coûtent davantage de temps au total, car chaque instruction est chargée et seules 30 % accèdent aux données.

N’insère pas directement le temps moyen d’accès mémoire comme CPI. Il est calculé par accès et comprend le temps de service en cas de succès. Le calcul du CPI ici n’ajoute que les attentes au-delà de l’exécution de base déjà comptée.

Une horloge plus rapide augmente le coût en cycles de chaque attente mémoire

La latence de la DRAM en nanosecondes ne diminue pas lorsque la fréquence d’horloge du processeur augmente. Doubler cette fréquence transforme la même attente mémoire de 100 cycles en 200 cycles à la nouvelle fréquence. Le CPI de l’exemple devient

Chaque nouveau cycle dure deux fois moins longtemps ; le temps d’exécution relatif passe donc de 4,2 anciens cycles par instruction à l’équivalent de 3,7 anciens cycles. L’accélération est de $\mathrm{4,2}\mathrm{/}\mathrm{3,7}\approx \mathrm{1,14}$, bien inférieure à deux.

Les améliorations déplacent le goulot d’étranglement

Si le CPI de base passe de 1,0 à 0,5 tandis que les attentes mémoire restent à 3,2, le CPI total devient 3,7. Les attentes consomment alors $\mathrm{3,2}\mathrm{/}\mathrm{3,7}\approx 86\mathrm{\%}$ des cycles. Améliorer le cœur augmente la part du temps d’exécution occupée par le délai mémoire inchangé : c’est un exemple de la loi d’Amdahl.

Le modèle simple compte tous les délais de défaut comme des attentes. L’exécution dans le désordre et les caches non bloquants peuvent faire chevaucher les défauts avec du travail utile ou d’autres défauts. Des compteurs matériels et des mesures du temps d’exécution sont nécessaires pour évaluer ce chevauchement sur une machine réelle. Pour comparer des conceptions avec ce modèle, garde le même flux d’instructions et précise quels délais sont déjà inclus dans le CPI de base.

Un cache inférieur réduit la pénalité payée lorsque L1 subit un défaut. Il possède son propre temps de recherche et son propre taux de défauts ; le coût attendu de la hiérarchie doit donc tenir compte de la fraction des demandes qui atteint chaque niveau.

Garder le dénominateur associé au taux

Le taux de défauts local d’un niveau est son nombre de défauts divisé par le nombre de demandes reçues par ce niveau. Son taux de défauts global est son nombre de défauts divisé par toutes les demandes mémoire du processeur.

Si L1 subit des défauts dans 4 % des cas et que L2 échoue pour 25 % de ces demandes, seules $\mathrm{0,04}\times \mathrm{0,25}=\mathrm{0,01}$, soit 1 % des demandes initiales, atteignent la mémoire. Un taux de défauts local de L2 de 25 % ne dit rien à lui seul de la fraction de toutes les demandes qui atteint la mémoire : L1 a d’abord filtré le flux.

Pour deux niveaux consultés successivement :

Ici, $H_1$ et $H_2$ sont les temps de recherche, $m_1$ et $m_2$ les proportions locales de défauts et $P$ la pénalité supplémentaire d’accès à la mémoire. Seuls les défauts de L1 paient la recherche dans L2. Seuls les défauts dans les deux niveaux paient la pénalité d’accès à la mémoire.

Calculer de l’intérieur vers l’extérieur

Utilise un temps d’accès en cas de succès de L1 de 1 cycle, un taux de défauts de L1 de 4 %, un temps d’accès en cas de succès de L2 de 12 cycles, un taux de défauts local de L2 de 25 % et une pénalité d’accès à la mémoire de 200 cycles. Une demande qui atteint L2 prend en moyenne $12+\mathrm{0,25}\times 200=62$ cycles supplémentaires. Ainsi,

Sans L2, le temps moyen d’accès mémoire serait de $1+\mathrm{0,04}\times 200=9$ cycles. La recherche dans L2 ajoute du travail à chaque défaut de L1, mais évite à la plupart de ces demandes de payer le délai mémoire bien plus élevé.

Ne remplace pas $m_2$ par le taux de défauts global de L2 de 1 % dans les parenthèses. Cela reviendrait à multiplier deux fois par la proportion de défauts de L1. Une forme développée équivalente utilise directement le taux global :

Ajouter L3 selon la même logique

Avec un temps d’accès en cas de succès de L3 de 40 cycles et un taux de défauts local de 40 %, le terme de service de L3 est de $40+\mathrm{0,4}\times 200=120$ cycles. Le terme de L2 devient $12+\mathrm{0,25}\times 120=42$ cycles. Le temps moyen d’accès mémoire global est de $1+\mathrm{0,04}\times 42=\mathrm{2,68}$ cycles.

L’expression complète est $H_1+m_1(H_2+m_2(H_3+m_{3}P))\mathrm{.}$ L3 n’est compté que pour les demandes qui échouent dans les deux niveaux supérieurs. Un niveau dont la recherche est très lente ou qui donne très peu de succès peut ajouter plus de délai qu’il n’en économise.

Utiliser les taux par instruction pour le CPI

Supposons que le CPI de base soit de 1, que L1 produise 0,032 défaut par instruction et que la mémoire ajoute 100 cycles. Sans L2, le CPI est de $1+\mathrm{0,032}\times 100=\mathrm{4,2}$. Ajoutons un cache L2 de 10 cycles dont le taux de défauts local est de 25 % :

À fréquence d’horloge égale, l’accélération est de $\mathrm{4,2}\mathrm{/}\mathrm{2,12}\approx \mathrm{1,98}$. La valeur 0,032 représente déjà des défauts par instruction ; un facteur supplémentaire de fréquence d’accès compterait donc cette fréquence deux fois.

La mémoire virtuelle sépare les adresses utilisées par un programme des emplacements qui contiennent ses données en mémoire principale. Chaque processus dispose de son propre espace d’adressage virtuel. Le matériel traduit les adresses à l’aide des correspondances du système d’exploitation et vérifie si chaque accès demandé est autorisé.

Remplacer le numéro de page, conserver le déplacement

Une page est une région de taille fixe d’adresses virtuelles. Un cadre de page est un emplacement de la taille d’une page en mémoire physique. Avec des pages de 4 KiB, chaque page contient 4096 octets ; le déplacement dans la page nécessite donc 12 bits. Les bits de poids fort restants de l’adresse virtuelle forment le numéro de page virtuelle.

Une entrée de table des pages fait correspondre un numéro de page virtuelle à un numéro de page physique. La traduction remplace le numéro de page mais conserve le déplacement : la même position d’octet est sélectionnée dans le cadre physique.

Pour l’adresse virtuelle 0x00403A7C, les 12 bits de poids faible donnent le déplacement 0xA7C, et le numéro de page virtuelle est 0x00403. Si ce numéro correspond au numéro de page physique 0x02F1C, l’adresse physique est 0x02F1CA7C. Ajouter à la suite un déplacement de 12 bits revient à multiplier le numéro de page physique par 4096 et à ajouter le déplacement ; ajouter ce numéro sans le décaler donnerait une adresse erronée.

Une correspondance comprend des autorisations

Une entrée de table des pages enregistre la validité, un numéro de page physique et des autorisations telles que la lecture, l’écriture, l’exécution et l’accès utilisateur. Les bits d’accès et de modification enregistrent l’utilisation et la modification. Un registre privilégié du processeur indique la table des pages ; RISC-V utilise satp. Les programmes utilisateur ne peuvent pas réécrire librement ces correspondances.

Des tables des pages séparées permettent à une même adresse virtuelle de désigner des données physiques différentes selon les processus. Elles permettent aussi un partage choisi : deux processus peuvent faire correspondre des pages virtuelles au même cadre physique, par exemple pour partager le code en lecture seule d’une bibliothèque. L’isolation et le partage sont tous deux des conséquences de correspondances contrôlées.

Un défaut de page nécessite l’intervention du système d’exploitation

Un défaut de page est une exception levée lorsque la traduction ou ses vérifications d’autorisation ne peuvent pas se terminer normalement. Un rangement dans une correspondance en lecture seule peut provoquer un défaut même si la page est déjà en mémoire.

Lorsqu’une page nécessaire est absente de la mémoire principale, le système d’exploitation obtient un cadre physique, lit la page depuis le stockage, met à jour la correspondance et relance l’instruction. Une page victime modifiée peut d’abord devoir être réécrite. Certains défauts sont résolus sans accès au stockage, par exemple en établissant une correspondance vers une page existante ou en traitant une copie à l’écriture. Un accès que le système ne peut pas autoriser peut au contraire aboutir à une erreur du processus.

Les défauts nécessitant le stockage sont coûteux. À 3 GHz, un délai de 50 µs coûte 150 000 cycles et 1 ms coûte 3 000 000 cycles. Les grandes pages répartissent les coûts de transfert sur de nombreux octets. Une page virtuelle peut occuper n’importe quel cadre adapté, et les pages modifiées utilisent l’écriture différée, car transmettre chaque rangement au stockage serait trop lent.

Les tables des pages consomment aussi de la mémoire

Une table à un seul niveau pour des adresses virtuelles de 32 bits et des pages de 4 KiB nécessite $2^{32-12}=2^{20}$ entrées. À raison de 4 octets par entrée, cela représente 4 MiB par processus. Les conceptions réelles utilisent des tables multiniveaux pour éviter d’allouer une immense table à un seul niveau pour des espaces d’adressage peu remplis ; RISC-V Sv39 utilise trois niveaux.

La mémoire virtuelle comprend la traduction d’adresses, la protection et le partage même lorsque toutes les pages utilisées tiennent en DRAM. La pagination vers le stockage est une utilisation de ces mécanismes, pas leur seul objectif.

La traduction d’une adresse peut nécessiter plusieurs lectures de la table des pages avant qu’un accès aux données puisse se poursuivre. Les entrées de table des pages peuvent être trouvées dans les caches ordinaires, mais ces lectures ajoutent tout de même du travail. Le tampon de traduction d’adresses, ou TLB, met en cache les traductions récemment utilisées afin que la plupart des accès évitent un parcours de la table des pages.

Suivre un accès autorisé

Le numéro de page virtuelle est recherché dans le TLB. Une entrée correspondante fournit le numéro de page physique et les informations d’autorisation. Après vérification des autorisations, l’adresse physique identifie les données dans la hiérarchie de caches.

En cas de défaut du TLB, un parcours de la table des pages obtient la traduction. Si la correspondance est valide et autorise la demande, la traduction est installée dans le TLB et l’accès se poursuit. RISC-V et x86-64 utilisent normalement des dispositifs matériels de parcours ; certaines architectures utilisent des routines logicielles. Si la correspondance ne permet pas de traiter la demande, le processeur lève un défaut de page pour le système d’exploitation.

Un défaut du TLB peut donc accompagner un succès ou un défaut du cache de données. Il indique que la traduction était absente du TLB, et non que la page était absente de la DRAM. Inversement, un succès dans le TLB peut accompagner un défaut de cache ou un défaut d’autorisation pour un accès interdit. La traduction et la présence des données répondent à des questions différentes.

Compter la mémoire couverte par les traductions

La couverture du TLB est le nombre d’entrées multiplié par la taille de page. Un TLB de 64 entrées avec des pages de 4 KiB couvre 256 KiB à la fois. Avec des pages de 2 MiB, 64 entrées couvrent 128 MiB. Accéder à de nombreuses pages différentes peut épuiser la capacité de traduction même lorsque seuls quelques octets de chaque page sont utilisés.

Les TLB de premier niveau contiennent souvent plusieurs dizaines d’entrées ; les niveaux inférieurs de TLB peuvent en contenir des centaines ou des milliers. Leurs entrées comprennent des étiquettes de numéros de pages, des correspondances physiques, des autorisations et souvent des identifiants d’espace d’adressage. La localité au sein des pages et la réutilisation lors d’accès proches maintiennent les taux de succès de traduction à un niveau élevé.

Par exemple, si 1 % des accès nécessitent un parcours de 30 cycles et que le temps de succès dans le TLB est par ailleurs masqué, les parcours ajoutent en moyenne $\mathrm{0,01}\times 30=\mathrm{0,3}$ cycle par accès. Cet exemple suppose que les parcours se terminent normalement et exclut le traitement des défauts de page.

Faire chevaucher indexation et traduction

Un cache à index physique et étiquette physique attend une adresse physique avant de sélectionner son ensemble. Un cache à index virtuel et étiquette physique, ou cache VIPT, commence à lire un ensemble pendant que le TLB traduit l’adresse, puis compare les étiquettes physiques.

La conception VIPT simple prend tous les bits d’index et de déplacement dans le bloc à partir du déplacement dans la page, car la traduction conserve ces bits. Cela exige

Avec des pages de 4 KiB, un cache de 32 KiB à 8 voies possède 4 KiB par voie et respecte cette condition. Un cache de 48 KiB à 12 voies la respecte aussi. Un cache de 64 KiB à 8 voies possède 8 KiB par voie et a besoin d’un bit du numéro de page pour l’indexation ; il nécessite donc davantage de voies ou un traitement supplémentaire.

Maintenir les correspondances en cache à jour

Les traductions appartiennent à des espaces d’adressage. Un changement de contexte peut vider les anciennes entrées ou les distinguer à l’aide d’identifiants d’espace d’adressage, ou ASID. Les modifications des correspondances exigent la mise à jour correspondante du cache de traductions ; RISC-V fournit sfence.vma. Lorsqu’une page est évincée de la mémoire, son ancienne traduction ne doit pas rester utilisable dans le TLB. Le TLB contient les correspondances et les droits d’accès, tandis que les caches ordinaires contiennent les données et les instructions du programme.

Un code qui tient compte du cache utilise les octets chargés avant que leur bloc soit évincé. Commence par les adresses produites par la boucle interne. Demande-toi ensuite quelles données sont réutilisées, à quelle distance les accès se trouvent et si ces blocs peuvent coexister dans le cache.

Parcourir les tableaux dans leur ordre de stockage

Le C et le C++ stockent les tableaux rectangulaires par lignes. Les colonnes adjacentes d’une même ligne sont adjacentes en mémoire. Fortran, MATLAB et Julia utilisent un rangement par colonnes ; les tableaux NumPy sont rangés par lignes par défaut. Un parcours interne efficace suit l’organisation réelle.

Un tableau C double a[1024][1024] occupe 8 MiB. Chaque ligne occupe 8 192 octets. Avec des lignes de cache de 64 octets, chaque ligne de cache contient huit valeurs de type double. Un parcours par lignes peut utiliser les huit avant de passer à la suite, ce qui donne environ un défaut à froid pour huit accès dans un modèle simple de chargement sur demande.

Un parcours par colonnes avance de 8 192 octets entre deux accès consécutifs. Il touche 1 024 lignes de cache distinctes avant de revenir à des données proches dans la colonne suivante. Ces lignes occupent 64 KiB, ce qui dépasse un cache L1 de 32 KiB. Elles entrent aussi en conflit : dans un cache à 64 ensembles, un pas de 128 lignes de cache conserve le même index d’ensemble. Un ensemble à 8 voies ne peut pas contenir 1 024 lignes concurrentes.

Ajouter du remplissage à une ligne du tableau pour atteindre 1 032 valeurs de type double donne un pas de 8 256 octets, soit 129 lignes de cache. Les lignes successives du tableau avancent alors d’un ensemble modulo 64, ce qui répartit les demandes. Le remplissage traite les conflits de correspondance ; la quantité de données reste néanmoins importante.

Permuter les boucles lorsque le résultat est conservé

La permutation de boucles modifie la boucle exécutée à l’intérieur d’une autre. Pour une multiplication matricielle avec rangement par lignes, l’ordre i, j, k parcourt une ligne de A, mais une colonne de B. Dans un modèle de parcours de grandes matrices avec peu de réutilisation entre les passages, cela coûte environ $1\mathrm{/}8+1=\mathrm{1,125}$ défaut par itération interne.

Avec i, k, j, la boucle interne parcourt des lignes de B et de C, tandis qu’un élément de A est réutilisé. Compter un nouveau parcours pour chacune des deux lignes donne environ $1\mathrm{/}8+1\mathrm{/}8=\mathrm{0,25}$ défaut par itération, soit 4,5 fois moins. Si la ligne de C mise à jour à plusieurs reprises reste présente dans le cache, le nombre s’approche de 0,125. La capacité du cache et les conflits déterminent quelles réutilisations restent possibles.

La permutation doit préserver le comportement requis des calculs. Les dépendances, les pointeurs vers des données qui se chevauchent et l’ordre d’évaluation en virgule flottante peuvent limiter les transformations ; les compilateurs doivent prouver qu’une modification est autorisée.

Charger les champs utilisés

Un tableau de structures regroupe tous les champs d’un objet. Une structure de tableaux regroupe un même champ pour plusieurs objets. Si un enregistrement de particule contient huit valeurs de type double dans une ligne de 64 octets, additionner uniquement x sur un million d’enregistrements alignés charge environ 64 MB. Un tableau x contigu séparé charge environ 8 MB, en utilisant chaque valeur de type double chargée. Un code qui utilise ensemble tous les champs d’une particule peut tirer avantage de l’organisation initiale en structures.

Les nœuds liés peuvent être dispersés et chaque adresse suivante peut dépendre d’un pointeur qui vient d’être chargé. Des tableaux contigus ou des zones de nœuds peuvent améliorer la localité. Des champs fréquemment utilisés et compacts permettent aussi de faire tenir davantage de données actives dans chaque niveau.

Mesure le temps d’exécution et les compteurs matériels pertinents avant et après une modification. Les défauts de cache peuvent expliquer une boucle lente, mais les calculs, la bande passante ou les branchements peuvent constituer le facteur limitant. Garde des entrées et des résultats comparables afin qu’une différence de vitesse reflète la modification évaluée.

La permutation de boucles améliore l’ordre des accès. Le traitement par blocs, aussi appelé découpage en blocs, va plus loin en gardant une petite région de données active jusqu’à la fin de sa réutilisation utile. Le préchargement avance un transfert futur afin que son délai se chevauche avec du travail utile.

Garder un groupe de blocs dans le cache

Dans la multiplication par blocs de matrices carrées, un bloc de A et un bloc de B contribuent à un bloc de C. Un bloc de côté $b$ contient $b^2$ éléments. Travailler à plusieurs reprises sur ces petits blocs permet de réutiliser les données avant de passer à la région suivante.

Pour des valeurs de type double de 8 octets, trois blocs nécessitent $3b^2\times 8=24b^2$ octets. Dans un cache de 32 KiB, la limite de capacité est

Choisir un côté de 32 utilise 24 576 octets, soit 24 KiB, et laisse de la place pour d’autres données. Choisir 36 simplement parce que le calcul le permet laisse beaucoup moins de place et peut entraîner des conflits. La capacité donne une première estimation ; les tailles réelles des blocs sont ajustées par mesure.

Un parcours par blocs fait avancer la boucle externe de la taille d’un bloc. Ses bornes internes s’arrêtent à la plus petite des deux valeurs entre la fin du bloc et la taille de la matrice. Par exemple, si une dimension vaut 70 et que les blocs ont un côté de 32, le dernier bloc ne contient que six éléments selon cette dimension. Un dernier bloc de taille complète accéderait au-delà du tableau.

Estimer les économies dues à la réutilisation

Dans un modèle simplifié de grandes matrices avec des lignes de 64 octets, l’ordre naïf i, j, k produit environ $\mathrm{1,125}{N}^3$ défauts lorsque les lignes parcourues ne sont plus dans le cache au passage suivant. Une version par blocs peut réduire ce nombre à environ $N^3\mathrm{/}(4b)$, en supposant que les trois blocs de travail restent dans le cache et en ignorant les conflits.

Pour $N=1024$ et $b=32$, ces estimations sont d’environ 1,2 milliard et 8,4 millions de défauts, soit un facteur de 144. Les deux versions effectuent toujours environ $2N^3$ opérations en virgule flottante. L’économie porte sur les transferts répétés de données, pas sur le nombre d’opérations arithmétiques de la multiplication. Le modèle décrit une réutilisation idéale ; l’accélération mesurée dépend aussi de la bande passante, de l’exécution et d’autres surcoûts.

Précharger assez tôt pour masquer la latence

Les dispositifs matériels de préchargement reconnaissent des suites d’accès séquentiels ou à pas constant. Ils demandent les lignes avant que les accès sur demande en aient besoin. Le logiciel peut aussi demander des chargements à l’avance, par exemple avec __builtin_prefetch de GCC ou Clang.

Le moment compte. Une demande trop tardive laisse l’accès sur demande en attente. Une demande trop précoce peut charger une ligne qui sera évincée avant utilisation. Une demande inexacte consomme de la bande passante et de l’espace de cache sans aider le programme. Le suivi de pointeurs est plus difficile à précharger, car l’adresse suivante n’est souvent connue qu’après l’arrivée du nœud courant.

Un préchargement au bon moment peut transformer les futurs défauts sur demande en succès, mais les lignes circulent toujours dans la hiérarchie. Il masque la latence sans réduire les données utiles nécessaires à un parcours. Le traitement par blocs aide lorsque les valeurs sont réutilisées ; un parcours unique ne contient pas de données répétées à conserver et peut déjà être limité par la bande passante mémoire.