Comment fonctionnent les lignes de cache?

169

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?

Norswap
la source
22
Lisez ceci: Ce que tout programmeur doit savoir sur la mémoire . Puis relisez-le. Meilleure source (pdf) ici .
andersoj

Réponses:

129

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). Également tag wiki a beaucoup de liens de performance pour cette architecture.

Eugène Smith
la source
1
Cette réponse n'a absolument aucun sens. Qu'est-ce que la bande passante de la mémoire 64 bits (qui est également erronée à cet égard) à faire avec les 64 octets (!) Pas à faire? De plus, les 10 à 30 ns sont également totalement faux si vous frappez le Ram. Cela peut être vrai pour le cache L3 ou L2 mais pas pour la RAM où cela ressemble plus à 90ns. Ce que vous voulez dire, c'est le temps de rafale - le temps d'accéder au quad-mot suivant en mode rafale (ce qui est en fait la bonne réponse)
Martin Kersten
5
@MartinKersten: Un canal de la SDRAM DDR1 / 2/3/4 utilise une largeur de bus de données de 64 bits. Un transfert en rafale d'une ligne de cache entière prend huit transferts de 8B chacun, et c'est ce qui se passe réellement. Il est peut-être encore correct que le processus soit optimisé en transférant d'abord le bloc aligné 8B contenant l'octet souhaité, c'est-à-dire en commençant la rafale là (et en s'enroulant si ce n'était pas le premier 8B de la taille de transfert en rafale). Les processeurs modernes avec des caches multi-niveaux ne le font probablement plus, car cela signifierait relayer le ou les premiers blocs de la rafale jusqu'au cache L1 tôt.
Peter Cordes
2
Haswell a un chemin de 64B entre le cache L2 et L1D (c'est-à-dire une largeur de ligne de cache complète), donc le transfert du 8B contenant l'octet demandé entraînerait une utilisation inefficace de ce bus. @Martin a également raison sur le temps d'accès pour une charge qui doit aller à la mémoire principale.
Peter Cordes
3
Bonne question pour savoir si les données remontent tout en haut de la hiérarchie de la mémoire ou si L3 attend une ligne complète de la mémoire avant de commencer à l'envoyer à L2. Il existe des tampons de transfert entre différents niveaux de cache, et chaque échec en attente en réclame un. Donc ( conjecture totale ) L3 place probablement les octets du contrôleur de mémoire dans son propre tampon de réception en même temps que les plaçant dans le tampon de chargement approprié pour le cache L2 qui le voulait. Lorsque la ligne est entièrement transférée de la mémoire, L3 informe le L2 que la ligne est prête et la copie dans sa propre matrice.
Peter Cordes
2
@Martin: J'ai décidé de continuer et de modifier cette réponse. Je pense que c'est plus précis maintenant, et toujours simple. Futurs lecteurs: voir aussi la question de Mike76 et ma réponse: stackoverflow.com/questions/39182060/...
Peter Cordes
22

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)
Kaz
la source
1
J'ai du mal à comprendre cela. Je sais que c'est 2 ans plus tard, mais pouvez-vous me donner un exemple de code pour cela? une ou deux lignes.
Nick
1
@Nick La raison pour laquelle cette méthode fonctionne réside dans le système de nombres binaires. Toute puissance de 2 n'a qu'un seul bit défini et tous les bits restants sont effacés, donc pour 64, vous avez 0b1000000remarqué que les 6 derniers chiffres sont des zéros, donc même lorsque vous avez un certain nombre avec l'un de ces 6 ensembles (qui représentent un nombre % 64), les effacer vous donnera l'adresse mémoire alignée sur 64 octets la plus proche.
legends2k
21

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.

Martin Kersten
la source
1
Un cache associatif à l'ensemble utilise certains bits d'adresse pour sélectionner un ensemble, de sorte que les balises peuvent être encore plus courtes que votre exemple. Bien sûr, le cache doit également garder une trace de quelle balise correspond à quel tableau de données dans l'ensemble, mais il y a généralement plus d'ensembles que de façons dans un ensemble. (par exemple, cache L1D associatif 8 voies de 32 Ko, avec 64 Go de lignes, dans les processeurs Intel x86: offset 6 bits, index 6 bits. peu d'adresses physiques. Comme vous le savez sûrement, ce n'est pas un hasard si les 12 bits inférieurs sont le décalage de page, donc L1 peut être VIPT sans alias.)
Peter Cordes
étonnant bourgeon de réponse ... y a-t-il un bouton "comme" n'importe où?
Edgard Lima
@EdgardLima, pas le bouton de vote favorable?
Pacerier
6

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.

Jweyrich
la source
4

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.

bramp
la source
2
Je peux dire avec certitude. Toute conception de cache raisonnable aura des lignes avec des tailles d'une puissance de 2 et qui sont naturellement alignées. (par exemple aligné sur 64B). Ce n'est pas seulement rapide et simple, c'est littéralement gratuit: vous ignorez simplement les 6 bits bas de l'adresse, par exemple. Les caches font souvent des choses différentes avec différentes plages d'adresses. (par exemple, le cache se soucie de la balise et de l'index pour détecter les succès par rapport aux échecs, puis en utilisant uniquement le décalage dans une ligne de cache pour insérer / extraire des données)
Peter Cordes