Mémoire hiérarchiqueEdit

La mémoire hiérarchique est une optimisation matérielle qui tire les bénéfices de la localité spatiale et temporelle et peut être utilisée sur plusieurs niveaux de la hiérarchie de la mémoire. La pagination bénéficie évidemment de la localité temporelle et spatiale. Un cache est un exemple simple d’exploitation de la localité temporelle, car il s’agit d’une zone de mémoire spécialement conçue, plus rapide mais plus petite, généralement utilisée pour conserver les données récemment référencées et les données proches des données récemment référencées, ce qui peut conduire à des augmentations potentielles de performance.

Les éléments de données dans un cache ne correspondent pas nécessairement aux éléments de données qui sont spatialement proches dans la mémoire principale ; cependant, les éléments de données sont amenés dans le cache une ligne de cache à la fois. Cela signifie que la localité spatiale est à nouveau importante : si un élément est référencé, quelques éléments voisins seront également amenés dans le cache. Enfin, la localité temporelle joue un rôle au niveau le plus bas, puisque les résultats qui sont référencés de manière très rapprochée peuvent être conservés dans les registres de la machine. Certains langages de programmation (comme le C) permettent au programmeur de suggérer que certaines variables soient conservées dans les registres.

La localité des données est une caractéristique typique de la référence mémoire des programmes réguliers (bien que de nombreux schémas d’accès mémoire irréguliers existent). Elle rend rentable la disposition hiérarchique de la mémoire. Dans les ordinateurs, la mémoire est divisée en une hiérarchie afin d’accélérer les accès aux données. Les niveaux inférieurs de la hiérarchie de la mémoire ont tendance à être plus lents, mais plus grands. Ainsi, un programme obtiendra de meilleures performances s’il utilise la mémoire pendant qu’elle est mise en cache dans les niveaux supérieurs de la hiérarchie de la mémoire et s’il évite d’introduire dans les niveaux supérieurs de la hiérarchie d’autres données qui déplaceront des données qui seront utilisées sous peu dans le futur. Il s’agit d’un idéal, qui ne peut parfois pas être atteint.

Hiérarchie de mémoire typique (les temps d’accès et les tailles de cache sont des approximations de valeurs typiques utilisées en 2013 pour les besoins de la discussion ; les valeurs réelles et les nombres réels de niveaux dans la hiérarchie varient) :

• Registres de l’unité centrale (8-256 registres) – accès immédiat, avec la vitesse du cœur le plus interne du processeur
• L1 caches de l’unité centrale (32 KiB à 512 KiB) – accès rapide, avec la vitesse du bus de mémoire le plus interne appartenant exclusivement à chaque cœur
• L2 caches de l’unité centrale (128 KiB à 24 MiB) – accès légèrement plus lent, avec la vitesse du bus mémoire partagé entre des jumeaux de cœurs
• L3 caches CPU (2 MiB à 32 MiB) – accès encore plus lent, avec la vitesse du bus mémoire partagé entre encore plus de cœurs du même processeur
• Mémoire physique principale (RAM) (256 MiB à 64 GiB) – accès lent, dont la vitesse est limitée par les distances spatiales et les interfaces matérielles générales entre le processeur et les modules de mémoire sur la carte mère
• Disque (mémoire virtuelle, système de fichiers) (1 GiB à 256 TiB) – très lent, en raison du canal de données plus étroit (en largeur de bit), physiquement beaucoup plus long, entre la carte principale de l’ordinateur et les dispositifs de disque, et en raison du protocole logiciel étranger nécessaire en plus de l’interface matérielle lente
• Mémoire distante (autres ordinateurs ou nuage) (pratiquement illimitée) – la vitesse varie de très lente à extrêmement lente

Les machines modernes ont tendance à lire des blocs de mémoire inférieure dans le niveau suivant de la hiérarchie de la mémoire. Si cela déplace la mémoire utilisée, le système d’exploitation essaie de prédire quelles données seront les moins accédées (ou les plus tardives) et les déplace vers le bas de la hiérarchie de la mémoire. Les algorithmes de prédiction ont tendance à être simples pour réduire la complexité matérielle, bien qu’ils deviennent un peu plus compliqués.

Multiplication matricielleEdit

Un exemple commun est la multiplication matricielle :

for i in 0..n for j in 0..m for k in 0..p C = C + A * B;

En changeant l’ordre de bouclage pour j et k, l’accélération des grandes multiplications matricielles devient dramatique, au moins pour les langages qui mettent des éléments de tableau contigus dans la dernière dimension. Cela ne change pas le résultat mathématique, mais améliore l’efficacité. Dans ce cas, « grand » signifie, approximativement, plus de 100 000 éléments dans chaque matrice, ou suffisamment de mémoire adressable pour que les matrices ne tiennent pas dans les caches L1 et L2.

for i in 0..n for k in 0..p for j in 0..m C = C + A * B;

La raison de cet accroissement de vitesse est que dans le premier cas, les lectures de A sont dans le cache (puisque l’indice k est la dernière dimension contiguë), mais B ne l’est pas, il y a donc une pénalité de cache miss sur B. C n’est pas pertinent, parce qu’il peut être hissé hors de la boucle interne — la variable de boucle ici est k.

for i in 0..n for j in 0..m temp = C for k in 0..p temp = temp + A * B; C = temp

Dans le second cas, les lectures et les écritures de C sont toutes deux en cache, les lectures de B sont en cache, et la lecture de A peut être hissée hors de la boucle interne.

for i in 0..n for k in 0..p temp = A for j in 0..m C = C + temp * B;

Donc, le second exemple n’a pas de pénalité de cache miss dans la boucle interne alors que le premier exemple a une pénalité de cache.

Sur un processeur de l’année 2014, le second cas est environ cinq fois plus rapide que le premier cas, lorsqu’il est écrit en C et compilé avec gcc -O3. (Un examen attentif du code désassemblé montre que dans le premier cas, GCC utilise des instructions SIMD et dans le second cas, il ne le fait pas, mais la pénalité de cache est bien pire que le gain SIMD.)

La localité temporelle peut également être améliorée dans l’exemple ci-dessus en utilisant une technique appelée blocage. La plus grande matrice peut être divisée en sous-matrices de taille égale, de sorte que les plus petits blocs peuvent être référencés (multipliés) plusieurs fois pendant qu’ils sont en mémoire.

for (ii = 0; ii < SIZE; ii += BLOCK_SIZE) for (kk = 0; kk < SIZE; kk += BLOCK_SIZE) for (jj = 0; jj < SIZE; jj += BLOCK_SIZE) maxi = min(ii + BLOCK_SIZE, SIZE); for (i = ii; i < maxi; i++) maxk = min(kk + BLOCK_SIZE, SIZE); for (k = kk; k < maxk; k++) maxj = min(jj + BLOCK_SIZE, SIZE); for (j = jj; j < maxj; j++) C = C + A * B;

La localité temporelle de la solution ci-dessus est assurée parce qu’un bloc peut être utilisé plusieurs fois avant de passer à autre chose, de sorte qu’il est déplacé dans et hors de la mémoire moins souvent. La localité spatiale est améliorée parce que les éléments ayant des adresses mémoire consécutives ont tendance à être tirés ensemble vers le haut de la hiérarchie mémoire.