Comment fonctionnent les lignes de cache?

Je comprends que le processeur introduit des données dans le cache via des lignes de cache, ce qui - par exemple, sur mon processeur Atom - apporte environ 64 octets à la fois, quelle que soit la taille des données réelles lues.

Ma question est:

Imaginez que vous ayez besoin de lire un octet de la mémoire, quels 64 octets seront introduits dans le cache?

Les deux possibilités que je peux voir sont que, soit les 64 octets commencent à la limite de 64 octets la plus proche en dessous de l'octet d'intérêt, soit les 64 octets sont répartis autour de l'octet d'une manière prédéterminée (par exemple, la moitié sous, la moitié au-dessus, ou tout ci-dessus).

Lequel est-ce?

Si la ligne de cache contenant l'octet ou le mot que vous chargez n'est pas déjà présente dans le cache, votre CPU demandera les 64 octets qui commencent à la limite de la ligne de cache (la plus grande adresse en dessous de celle dont vous avez besoin qui est multiple de 64) .

Les modules de mémoire pour PC modernes transfèrent 64 bits (8 octets) à la fois, en une rafale de huit transferts , de sorte qu'une commande déclenche une lecture ou une écriture d'une ligne de cache complète à partir de la mémoire. (La taille de transfert en rafale SDRAM DDR1 / 2/3/4 est configurable jusqu'à 64B; les processeurs sélectionneront la taille de transfert en rafale pour correspondre à la taille de leur ligne de cache, mais 64B est commun)

En règle générale, si le processeur ne peut pas prévoir un accès à la mémoire (et le pré-lire), le processus de récupération peut prendre ~ 90 nanosecondes, ou ~ 250 cycles d'horloge (du processeur connaissant l'adresse au processeur recevant les données).

En revanche, un hit dans le cache L1 a une latence d'utilisation de la charge de 3 ou 4 cycles, et un store-reload a une latence de transfert de stockage de 4 ou 5 cycles sur les processeurs x86 modernes. Les choses sont similaires sur d'autres architectures.

Lectures complémentaires: Ce que chaque programmeur devrait savoir sur la mémoire d' Ulrich Drepper . Le conseil de prélecture du logiciel est un peu dépassé: les prélecteurs HW modernes sont plus intelligents, et l'hyperthreading est bien meilleur que dans les jours P4 (donc un thread de prélecture est généralement un gaspillage). Égalementx86 tag wiki a beaucoup de liens de performance pour cette architecture.

Si les lignes de cache ont une largeur de 64 octets, elles correspondent alors à des blocs de mémoire qui commencent sur des adresses qui sont divisibles par 64. Les 6 bits les moins significatifs de toute adresse sont un décalage dans la ligne de cache.

Ainsi, pour tout octet donné, la ligne de cache qui doit être récupérée peut être trouvée en effaçant les six bits les moins significatifs de l'adresse, ce qui correspond à un arrondi à l'adresse la plus proche divisible par 64.

Bien que cela soit fait par le matériel, nous pouvons montrer les calculs en utilisant certaines définitions de macro de référence C:

#define CACHE_BLOCK_BITS 6
#define CACHE_BLOCK_SIZE (1U << CACHE_BLOCK_BITS)  /* 64 */
#define CACHE_BLOCK_MASK (CACHE_BLOCK_SIZE - 1)    /* 63, 0x3F */

/* Which byte offset in its cache block does this address reference? */
#define CACHE_BLOCK_OFFSET(ADDR) ((ADDR) & CACHE_BLOCK_MASK)

/* Address of 64 byte block brought into the cache when ADDR accessed */
#define CACHE_BLOCK_ALIGNED_ADDR(ADDR) ((ADDR) & ~CACHE_BLOCK_MASK)

Tout d'abord, un accès à la mémoire principale est très coûteux. Actuellement, un processeur à 2 GHz (le plus lent une fois) a 2G ticks (cycles) par seconde. Un CPU (noyau virtuel de nos jours) peut extraire une valeur de ses registres une fois par tick. Étant donné qu'un cœur virtuel se compose de plusieurs unités de traitement (ALU - unité arithmétique et logique, FPU, etc.), il peut en fait traiter certaines instructions en parallèle si possible.

Un accès à la mémoire principale coûte environ 70 ns à 100 ns (la DDR4 est légèrement plus rapide). Cette fois, il s'agit essentiellement de rechercher le cache L1, L2 et L3 et de frapper la mémoire (envoyer la commande au contrôleur de mémoire, qui l'envoie aux banques de mémoire), attendez la réponse et c'est fait.

100ns signifie environ 200 ticks. Donc, fondamentalement, si un programme manquait toujours les caches auxquels chaque accès en mémoire, le processeur passerait environ 99,5% de son temps (s'il ne lit que la mémoire) inactif à attendre la mémoire.

Afin d'accélérer les choses, il y a les caches L1, L2, L3. Ils utilisent une mémoire placée directement sur la puce et utilisant un type différent de circuits à transistors pour stocker les bits donnés. Cela prend plus de place, plus d'énergie et est plus coûteux que la mémoire principale car un processeur est généralement produit à l'aide d'une technologie plus avancée et une défaillance de production dans la mémoire L1, L2, L3 a la possibilité de rendre le processeur sans valeur (défaut). Les grands caches L1, L2, L3 augmentent le taux d'erreur, ce qui diminue le rendement, ce qui diminue directement le retour sur investissement. Il y a donc un énorme compromis en ce qui concerne la taille du cache disponible.

(actuellement, on crée plus de caches L1, L2, L3 afin de pouvoir désactiver certaines parties pour réduire le risque qu'un défaut de production réel soit les zones de mémoire cache rende le défaut CPU dans son ensemble).

Pour donner une idée de timing (source: coûts d'accès aux caches et à la mémoire )

• Cache L1: 1ns à 2ns (2-4 cycles)
• Cache L2: 3ns à 5ns (6-10 cycles)
• Cache L3: 12ns à 20ns (24-40 cycles)
• RAM: 60ns (120 cycles)

Puisque nous mélangeons différents types de CPU, ce ne sont que des estimations, mais donnent une bonne idée de ce qui se passe réellement lorsqu'une valeur de mémoire est récupérée et que nous pourrions avoir un succès ou un échec dans certaines couches de cache.

Ainsi, un cache accélère considérablement l'accès à la mémoire (60ns contre 1ns).

Récupérer une valeur, la stocker dans le cache pour avoir la chance de la relire, c'est bien pour les variables qui sont souvent accédées mais pour les opérations de copie mémoire, ce serait encore trop lent car on lit juste une valeur, écrit la valeur quelque part et ne lit jamais la valeur encore une fois ... pas de hits de cache, très lent (à côté de cela, cela peut arriver en parallèle car nous avons une exécution dans le désordre).

Cette copie mémoire est si importante qu'il existe différents moyens pour l'accélérer. Au début, la mémoire était souvent capable de copier de la mémoire en dehors du processeur. Elle était gérée directement par le contrôleur de mémoire, donc une opération de copie de mémoire n'a pas pollué les caches.

Mais à côté d'une copie de mémoire ordinaire, d'autres accès en série de la mémoire étaient assez courants. Un exemple est l'analyse d'une série d'informations. Avoir un tableau d'entiers et calculer la somme, la moyenne, la moyenne ou même plus simple trouver une certaine valeur (filtre / recherche) était une autre classe très importante d'algorithmes exécutés à chaque fois sur n'importe quel processeur à usage général.

Ainsi, en analysant le modèle d'accès à la mémoire, il est apparu que les données sont lues séquentiellement très souvent. Il y avait une forte probabilité que si un programme lit la valeur à l'index i, le programme lira également la valeur i + 1. Cette probabilité est légèrement supérieure à la probabilité que le même programme lise également la valeur i + 2 et ainsi de suite.

Donc, étant donné une adresse mémoire, c'était (et est toujours) une bonne idée de lire à l'avance et de récupérer des valeurs supplémentaires. C'est la raison pour laquelle il existe un mode boost.

L'accès à la mémoire en mode boost signifie qu'une adresse est envoyée et plusieurs valeurs sont envoyées séquentiellement. Chaque envoi de valeur supplémentaire ne prend que 10 ns supplémentaires (voire moins).

Un autre problème était une adresse. L'envoi d'une adresse prend du temps. Afin d'adresser une grande partie de la mémoire, de grandes adresses doivent être envoyées. Dans les premiers temps, cela signifiait que le bus d'adresses n'était pas assez grand pour envoyer l'adresse en un seul cycle (coche) et que plus d'un cycle était nécessaire pour envoyer l'adresse, ajoutant plus de retard.

Une ligne de cache de 64 octets par exemple signifie que la mémoire est divisée en blocs distincts (sans chevauchement) de mémoire d'une taille de 64 octets. 64 octets signifie que l'adresse de début de chaque bloc a les six bits d'adresse les plus bas pour être toujours des zéros. Il n'est donc pas nécessaire d'envoyer ces six bits de zéro à chaque fois en augmentant l'espace d'adressage 64 fois pour n'importe quel nombre de largeur de bus d'adresse (effet de bienvenue).

Un autre problème que la ligne de cache résout (à côté de la lecture anticipée et de la sauvegarde / libération de six bits sur le bus d'adresse) est la manière dont le cache est organisé. Par exemple, si un cache est divisé en blocs (cellules) de 8 octets (64 bits), il faut stocker l'adresse de la cellule de mémoire pour laquelle cette cellule de cache contient la valeur avec elle. Si l'adresse était également de 64 bits, cela signifie que la moitié de la taille du cache est consommée par l'adresse, ce qui entraîne une surcharge de 100%.

Étant donné qu'une ligne de cache est de 64 octets et qu'un processeur peut utiliser 64 bits - 6 bits = 58 bits (pas besoin de stocker les zéro bits trop à droite), nous pouvons mettre en cache 64 octets ou 512 bits avec une surcharge de 58 bits (11% de surcharge). En réalité, les adresses stockées sont encore plus petites que cela mais il y a des informations d'état (comme la ligne de cache est-elle valide et précise, sale et doit être réécrite en RAM, etc.).

Un autre aspect est que nous avons un cache associatif d'ensembles. Toutes les cellules de cache ne peuvent pas stocker une certaine adresse mais seulement un sous-ensemble de celles-ci. Cela rend les bits d'adresse stockés nécessaires encore plus petits, permet un accès parallèle au cache (chaque sous-ensemble peut être consulté une fois mais indépendamment des autres sous-ensembles).

Il y a plus particulièrement quand il s'agit de synchroniser l'accès cache / mémoire entre les différents cœurs virtuels, leurs multiples unités de traitement indépendantes par cœur et enfin plusieurs processeurs sur une même carte mère (dont il existe des cartes abritant jusqu'à 48 processeurs et plus).

C'est essentiellement l'idée courante pour laquelle nous avons des lignes de cache. L'avantage de la lecture à l'avance est très élevé et le pire des cas de lecture d'un seul octet sur une ligne de cache et de ne plus jamais relire le reste est très mince car la probabilité est très faible.

La taille de la ligne de cache (64) est un compromis judicieusement choisi entre des lignes de cache plus grandes, il est peu probable que le dernier octet de celui-ci soit lu également dans un proche avenir, la durée nécessaire pour récupérer la ligne de cache complète à partir de la mémoire (et pour l'écrire) et aussi la surcharge dans l'organisation du cache et la parallélisation du cache et l'accès à la mémoire.

Les processeurs peuvent avoir des caches à plusieurs niveaux (L1, L2, L3), et ceux-ci diffèrent par leur taille et leur vitesse.

Pourtant, pour comprendre ce qui se passe exactement dans chaque cache, vous devrez étudier le prédicteur de branche utilisé par ce processeur spécifique, et comment les instructions / données de votre programme se comportent par rapport à lui.

En savoir plus sur le prédicteur de branche , le cache du processeur et les politiques de remplacement .

Ce n'est pas une tâche facile. Si à la fin de la journée tout ce que vous voulez, c'est un test de performance, vous pouvez utiliser un outil comme Cachegrind . Cependant, comme il s'agit d'une simulation, son résultat peut différer dans une certaine mesure.

Je ne peux pas dire avec certitude que chaque matériel est différent, mais c'est typiquement "64 octets commencent à la limite de 64 octets la plus proche ci-dessous" car c'est une opération très rapide et simple pour le CPU.