Comment fonctionnent les lignes de cache?

Je comprends que le processeur apporte des données dans le cache via des lignes de cache, qui – par exemple, sur mon processeur Atom – apportent environ 64 octets à la fois, quelle que soit la taille des données en cours de lecture.

Ma question est:

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

Les deux possibilités que je peux voir sont les suivantes: soit les 64 octets démarrent à la limite de 64 octets la plus proche en dessous de l’octet d’intérêt, soit les 64 octets sont répartis sur l’octet d’une manière prédéterminée (par exemple, 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 dont vous avez besoin multiple de 64) .

    Les modules de mémoire PC modernes transfèrent 64 bits (8 octets) à la fois, dans 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électionnent 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 access mémoire (et le pré-télécharger), le processus de récupération peut durer environ 90 nanosecondes, soit environ 250 cycles d’horloge (du processeur connaissant l’adresse au processeur recevant les données).

    En revanche, un access dans le cache L1 a une latence d’utilisation de 3 ou 4 cycles et un rechargement de magasin a une latence de transfert de 4 ou 5 cycles sur les processeurs x86 modernes. Les choses sont similaires sur d’autres architectures.

    Lectures complémentaires: Ulrich Drepper’s What What Programmer devrait savoir sur la mémoire . Les conseils de lecture anticipée des logiciels sont un peu dépassés: les pré-récupérateurs de matériel informatique modernes sont plus intelligents et l’hyperthreading est bien meilleur qu’en jours P4 (un thread de pré-extraction est donc un gaspillage). En outre, le wiki de balise x86 contient de nombreux 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 aux adresses divisibles par 64. Les 6 bits les moins significatifs de toute adresse sont un décalage dans la ligne de cache.

    Donc, pour tout octet donné, la ligne de cache qui doit être extraite peut être trouvée en effaçant les six bits les moins significatifs de l’adresse, ce qui correspond à l’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 des définitions de macro C de référence:

    #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, l’access à la mémoire principale est très coûteux. Actuellement, un processeur à 2 GHz (le plus lent une fois) a 2 cycles (cycles) par seconde. Un CPU (kernel virtuel de nos jours) peut récupérer une valeur de ses registres une fois par tick. Comme un kernel virtuel se compose de plusieurs unités de traitement (ALU – unité arithmétique et logique, FPU, etc.), il peut traiter certaines instructions en parallèle si possible.

    Un access de la mémoire principale coûte environ 70 à 100 ns (DDR4 est légèrement plus rapide). Cette fois-ci, nous recherchons essentiellement le cache L1, L2 et L3 et frappons 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 finissez.

    100ns signifie environ 200 tiques. Donc, fondamentalement, si un programme manque toujours les caches auxquels chaque mémoire accède, le processeur passe environ 99,5% de son temps (s’il ne lit que de la mémoire) en attente de la mémoire.

    Pour accélérer les choses, il existe les caches L1, L2, L3. Ils utilisent la mémoire directement placée sur la puce et utilisent 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 en utilisant une technologie plus avancée et une défaillance de production dans la mémoire L1, L2, L3 a la possibilité de rendre le CPU sans valeur. Les grandes 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 diminuer le risque qu’un défaut de production réel soit dû au fait que les zones de mémoire cache rendent le défaut du processeur dans son ensemble).

    Donner une idée temporelle (source: coûts d’access 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 combinons différents types de CPU, ce ne sont que des estimations, mais cela donne une bonne idée de ce qui se passe réellement quand une valeur de mémoire est récupérée et que nous pouvons avoir un succès ou un échec dans certaines couches de cache.

    Ainsi, un cache accélère grandement l’access à la mémoire (60ns contre 1ns).

    Récupérer une valeur en la stockant dans le cache pour la relire est utile pour les variables auxquelles on accède souvent mais pour les opérations de copie en mémoire, elle serait encore lente car on lit simplement une valeur, écrit la valeur quelque part et ne lit jamais la valeur encore une fois … pas de hits dans le cache, mort lent (à côté de cela peut se produire en parallèle puisque nous avons une exécution en panne).

    Cette copie de mémoire est tellement 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. Il a été géré directement par le contrôleur de mémoire, de sorte qu’une opération de copie de mémoire n’a pas pollué les caches.

    Mais à côté d’une simple copie de mémoire, un autre access série à la mémoire était assez courant. Un exemple est l’parsing d’une série d’informations. Avoir un tableau d’entiers et calculer la sum, moyenne, moyenne ou même plus simple trouver une certaine valeur (filtre / recherche) était une autre classe d’algorithmes très importante exécutée chaque fois sur n’importe quelle CPU à usage général.

    Ainsi, en analysant le modèle d’access à la mémoire, il était évident que les données étaient lues séquentiellement très souvent. Si un programme lit la valeur de l’indice i, le programme lit aussi 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, il é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’access à la mémoire en mode boost signifie qu’une adresse est envoyée et que plusieurs valeurs sont envoyées séquentiellement. Chaque envoi de valeur supplémentaire ne prend que 10ns supplémentaires (ou même plus bas).

    Un autre problème était une adresse. Envoyer une adresse prend du temps. Pour adresser une grande partie de la mémoire, de grandes adresses doivent être envoyées. Au début, cela signifiait que le bus d’adresse n’était pas assez grand pour envoyer l’adresse en un seul cycle (tick) et que plus d’un cycle était nécessaire pour envoyer l’adresse en ajoutant un délai supplémentaire.

    Par exemple, une ligne de cache de 64 octets signifie que la mémoire est divisée en blocs de mémoire distincts (ne se chevauchant pas) 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 zéro à chaque fois en augmentant l’espace d’adressage 64 fois pour un nombre quelconque de largeur de bus d’adresse (effet de bienvenue).

    Un autre problème résolu par la ligne de cache (en plus de la lecture anticipée et de la sauvegarde / libération de six bits sur le bus d’adresse) réside dans l’organisation du cache. Par exemple, si une antémémoire est divisée en blocs de 8 octets (64 bits) (cellules), il est nécessaire de stocker l’adresse de la cellule mémoire contenant cette valeur. Si l’adresse est également 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%.

    Comme 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 bits de zéro à droite), nous pouvons mettre en cache 64 octets ou 512 bits avec une surcharge de 11 bits. En réalité, les adresses stockées sont encore plus petites que cela, mais il y a des informations de statut (comme la ligne de cache valide et précise, sale et doit être réécrite dans ram, etc.).

    Un autre aspect est que nous avons un cache associatif. Toutes les cellules de cache ne sont pas en mesure de 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 access parallèle au cache (chaque sous-ensemble est accessible une fois mais indépendamment des autres sous-ensembles).

    Il y a plus particulièrement quand il s’agit de synchroniser l’access cache / mémoire entre les différents cœurs virtuels, leurs multiples unités de traitement indépendantes par cœur et finalement plusieurs processeurs sur une carte mère (qui contiennent des processeurs de 48 processeurs et plus).

    Ceci est fondamentalement l’idée courante pour laquelle nous avons des lignes de cache. L’avantage de la lecture anticipée est très élevé et le cas le plus défavorable de lecture d’un seul octet sur une ligne de cache et de ne plus jamais lire le rest est très mince puisque la probabilité est très mince.

    La taille de la ligne de cache (64) est un choix judicieux entre de plus grandes lignes de cache, ce qui rend peu probable la lecture du dernier octet de cette dernière, la durée nécessaire pour récupérer la ligne de cache complète de la mémoire (et pour le réécrire) ainsi que de la surcharge dans l’organisation du cache et de la parallélisation du cache et de l’access à la mémoire.

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

    Cependant, pour comprendre ce qui se passe exactement dans chaque cache, vous devez étudier le prédicteur de twig utilisé par ce processeur spécifique et la manière dont les instructions / données de votre programme s’y comportent.

    Lisez à propos des prédicteurs de twig , du cache du processeur et des stratégies de remplacement .

    Ce n’est pas une tâche facile. Si à la fin de la journée tout ce que vous voulez 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 il est généralement “64 octets commencent à la limite la plus proche de 64 octets ci-dessous” car c’est une opération très rapide et simple pour le processeur.