Un cache ne va jamais chercher un seul octet. Il va chercher une ligne entière de 64 octets, donc la valeur voisine de celle que vous venez de lire est déjà là. Ce cours construit un cache, montre que lire dans l'ordre coûte huit fois moins que sauter d'une ligne à chaque fois, et l'applique à une table de prix.
La mémoire vient par lignes
Aller chercher en mémoire coûte autant, quel que soit le nombre d'octets demandés, donc le matériel en demande beaucoup d'un coup. La mémoire est découpée en blocs de 64 octets, et le cache charge et évince toujours des blocs entiers. Imaginez un ascenseur qui monte 64 octets vers le cache : s'il monte de toute façon, emmener vos voisins ne coûte rien, et la prochaine fois que vous avez besoin de l'un d'eux, il est déjà en haut.
Un bloc d'octets consécutifs, 64 sur la plupart des processeurs, que le cache charge et évince comme une seule unité. La ligne n contient les octets de 64n à 64n + 63.
Chaque octet a une adresse, un nombre qui dit où il se trouve. Pour trouver la ligne d'une adresse, divisez par la taille de ligne et ignorez le reste. Le code ci-dessous affiche la ligne de quatre adresses.
line_bytes = 64for address in (0, 63, 64, 130): print(address, "is in line", address // line_bytes)
0 is in line 0 63 is in line 0 64 is in line 1 130 is in line 2
Les adresses 0 et 63 partagent la ligne 0 : une fois l'une chargée, l'autre est gratuite. L'adresse 64 commence la ligne 1 et 130 est dans la ligne 2. Tout ce sujet découle de cette division entière.
Un cache est une table d'emplacements
Le cache le plus simple est une table avec un emplacement par ligne qu'il peut contenir. Un cache de 32 Ko à lignes de 64 octets a 512 emplacements. Chaque ligne de mémoire n'a droit qu'à un seul emplacement, trouvé par un reste : numéro de ligne modulo le nombre d'emplacements. C'est un cache à correspondance directe. Comme beaucoup de lignes partagent un emplacement, celui-ci garde aussi une étiquette qui dit quelle ligne il contient en ce moment.
- 1Trouver la ligneDivisez l'adresse par la taille de ligne.
- 2Trouver l'emplacementPrenez le numéro de ligne modulo le nombre d'emplacements.
- 3Comparer l'étiquetteSi l'emplacement contient cette ligne, c'est un succès.
- 4Remplacer en cas de défautChargez la ligne dans l'emplacement et oubliez celle qui y était.
C'est tout le cache. La classe ci-dessous en est une version complète et fonctionnelle en quinze lignes. Nous lisons quatre valeurs voisines, puis la ligne suivante, puis nous revenons à l'adresse 0.
def line_of(address, line_bytes): return address // line_bytesclass Cache: def __init__(self, size_bytes, line_bytes): self.line_bytes = line_bytes self.n_lines = size_bytes // line_bytes self.tags = [None] * self.n_lines self.hits = 0 self.misses = 0 def access(self, address): line = line_of(address, self.line_bytes)1 slot = line % self.n_lines if self.tags[slot] == line:2 self.hits += 1 return True self.misses += 1 self.tags[slot] = line return Falsecache = Cache(size_bytes=512, line_bytes=64)reads = [0, 8, 16, 24, 64, 72, 0, 512, 0]print([cache.access(a) for a in reads])print(cache.hits, "hits and", cache.misses, "misses")
[False, True, True, True, False, True, True, False, False] 5 hits and 4 misses
- 1L'emplacement est le numéro de ligne modulo le nombre d'emplacements.
- 2Un succès signifie que l'étiquette de l'emplacement est cette même ligne.
Lisez la liste des indicateurs : la première lecture échoue et charge la ligne 0, les trois suivantes réussissent car elles sont dans la ligne 0, 64 échoue et charge la ligne 1, 72 réussit, et revenir à 0 réussit encore car la ligne 0 n'a pas été évincée. Puis l'adresse 512 est la ligne 8, qui correspond aussi à l'emplacement 0 (8 modulo 8), donc elle évince la ligne 0, et la dernière lecture de l'adresse 0 échoue de nouveau : un conflit nous a coûté un défaut.
Un cache de 512 octets à lignes de 64 octets n'a que 8 emplacements, pas 512. Oublier de diviser la taille par la taille de ligne est la façon habituelle de construire un cache qui paraît énorme et se comporte mal.
Lire dans l'ordre contre sauter
Utilisons maintenant le cache. Une valeur float64 prend 8 octets, donc une ligne en contient huit. Lisez un tableau dans l'ordre : la première lecture de chaque ligne échoue et les sept suivantes réussissent, soit un défaut sur huit. Lisez-le avec un pas, c'est-à-dire en sautant un nombre fixe de valeurs entre les lectures, et les lectures tombent dans des lignes différentes. Le code suivant mesure le taux de défauts pour des pas de 1, 2, 4, 8 et 16 valeurs.
def sequential_trace(n, elem_bytes): return [i * elem_bytes for i in range(n)]def strided_trace(n, elem_bytes, stride): return [i * stride * elem_bytes for i in range(n)]def miss_rate(trace, size_bytes=32768, line_bytes=64): cache = Cache(size_bytes, line_bytes) for address in trace: cache.access(address) return cache.misses / len(trace)n = 4096for stride in (1, 2, 4, 8, 16): print("stride", stride, "values:", miss_rate(strided_trace(n, 8, stride)))
stride 1 values: 0.125 stride 2 values: 0.25 stride 4 values: 0.5 stride 8 values: 1.0 stride 16 values: 1.0
Le taux de défauts double à chaque doublement du pas jusqu'à atteindre 1,0 : avec un pas de 8 valeurs le saut est de 64 octets, une ligne entière, donc chaque lecture ouvre une nouvelle ligne et le cache n'économise rien. Un pas plus grand ne peut pas être pire, seulement égal. Le motif est la formule ci-dessous.
Sur presque toutes les puces x86 et ARM serveur, oui. Certaines puces utilisent 128 octets dans un cache externe : mesurez donc la taille de ligne de la machine visée. Notre cache la prend en paramètre pour que vous puissiez essayer les deux.
La disposition d'une table décide du pas
Une table de barres quotidiennes a cinq nombres par jour : ouverture, plus haut, plus bas, clôture et volume. Stockez-la ligne par ligne, comme font la plupart des programmes, et les cinq nombres d'un jour sont côte à côte. Pour ne lire que les clôtures, vous sautez alors quatre valeurs entre les lectures : un pas de 5, soit 40 octets. Stockez chaque colonne à part et les clôtures se suivent : un pas de 1. Mêmes nombres, mêmes lectures, disposition différente.
closes = 1000as_column = miss_rate(sequential_trace(closes, 8))as_rows = miss_rate(strided_trace(closes, 8, 5))print("column layout:", as_column)print("row layout: ", as_rows)
column layout: 0.125 row layout: 0.625
Cinq fois plus de lectures échouent quand les clôtures sont espacées. Cela ne change pas la réponse de votre programme, seulement sa vitesse, et aucune ligne d'arithmétique du profileur ne le montrera : le temps en plus est passé à attendre la mémoire.
Ce que vous allez construire
Le labo demande les éléments que vous venez de lire, dans le même ordre, et se termine par l'étude sur la vraie table SPY.
- Fonction · questionS'appuie sur
- line_of(address, line_bytes)Quelle ligne contient cette adresse ?La division entière
- Cache(size_bytes, line_bytes).access(address)Cette lecture est-elle un succès ?line_of
- sequential_trace(n, elem_bytes)Quelles adresses une lecture dans l'ordre touche-t-elle ?De l'arithmétique simple
- strided_trace(n, elem_bytes, stride)Quelles adresses une lecture par sauts touche-t-elle ?De l'arithmétique simple
- miss_rate(trace, size_bytes, line_bytes)Quelle part d'une trace échoue ?Cache
- study(bars)Que coûte la disposition en lignes pour les clôtures de SPY ?miss_ratestrided_trace
Sujet suivant : un cache à correspondance directe a une faiblesse que ce cours a effleurée, le conflit entre lignes qui partagent un emplacement. Dans Associativité et défauts de conflit, vous donnez plusieurs places à chaque emplacement et voyez pourquoi une table dont les lignes sont espacées de 4096 octets peut ruiner un cache.
Lab : ce qui est noté
6 tâches · 100 pts- La ligne d'une adresse10 pts
- Un cache à correspondance directe25 pts
- Une lecture dans l'ordre10 pts
- Une lecture avec pas10 pts
- Le taux de défauts d'une trace20 pts
- L'étude sur la table SPY25 pts