Associativité et défauts de conflit

Dans un cache à un emplacement par ligne, deux lignes très utilisées qui partagent un emplacement s'évincent encore et encore. Donnez plusieurs voies à chaque emplacement et le problème disparaît en grande partie, sauf si les lignes de votre table sont espacées d'exactement 4096 octets. Ce cours construit un cache associatif par ensembles et montre comment une taille de ligne puissance de deux peut faire échouer 100 % des lectures.

Dans le cache à correspondance directe du sujet précédent, chaque ligne de mémoire a exactement un emplacement. Si votre programme utilise sans cesse deux lignes qui correspondent au même emplacement, disons la ligne 0 et la ligne 8 dans un cache de 8 emplacements, chaque lecture de l'une évince l'autre, alors que les sept autres emplacements sont peut-être vides. La taille du cache n'est pas en cause : les lignes se disputent une place trop petite. Un défaut de ce genre s'appelle un défaut de conflit.

La solution est de regrouper les emplacements. Les emplacements sont réunis en ensembles, et chaque emplacement d'un ensemble est une voie. Une ligne de mémoire appartient à un ensemble, trouvé par le même reste qu'avant, mais elle peut se placer dans n'importe quelle voie de cet ensemble. Deux lignes en collision partagent maintenant un ensemble qui a de la place pour les deux. Le nombre d'ensembles découle des tailles :

Une adresse se découpe maintenant en trois parties. Le déplacement est l'octet dans la ligne. L'indice d'ensemble dit à quel ensemble la ligne appartient. L'étiquette est le reste du numéro de ligne, et c'est ce que le cache compare pour savoir si une voie contient cette ligne. La fonction ci-dessous découpe une adresse pour un cache à lignes de 64 octets et 64 ensembles.

def split_address(address, line_bytes, n_sets):    line = address // line_bytes    return line // n_sets, line % n_sets, address % line_bytes1print(split_address(74565, 64, 64))

(18, 13, 5)

1. 1Étiquette, indice d'ensemble et déplacement : chacun est une division entière ou un reste de l'adresse.

L'adresse 74565 est l'octet 5 de la ligne 1165. La ligne 1165 va dans l'ensemble 13 (1165 modulo 64), et 18 est ce qui reste du numéro de ligne, l'étiquette. Toute ligne dont l'ensemble est 13 se disputera les huit voies de cet ensemble, quelle que soit son étiquette.

Quand un ensemble est plein et qu'une nouvelle ligne arrive, l'une des lignes doit partir. La règle habituelle est LRU : évincer la ligne utilisée le moins récemment. On peut garder chaque ensemble comme une liste Python ordonnée de la moins récemment utilisée à la plus récemment utilisée.

1. 1
   Trouver l'ensembleLe numéro de ligne modulo le nombre d'ensembles.
2. 2
   Regarder dans chaque voieEn cas de succès, déplacez la ligne vers le bout des plus récemment utilisées.
3. 3
   Ajouter en cas de défautPlacez la nouvelle ligne au bout des plus récemment utilisées.
4. 4
   Éliminer la plus ancienneSi l'ensemble contient plus de lignes que de voies, retirez la première.

Voici le cache complet. L'exécution en bas lit deux lignes, aux adresses 0 et 256, qui entrent en collision dans un cache de 256 octets à lignes de 64 octets, d'abord avec une voie puis avec deux.

class SetAssocCache:    def __init__(self, size_bytes, line_bytes, ways):        self.line_bytes = line_bytes        self.ways = ways        self.n_sets = size_bytes // (line_bytes * ways)        self.sets = [[] for _ in range(self.n_sets)]        self.hits = 0        self.misses = 0    def access(self, address):        line = address // self.line_bytes        lines = self.sets[line % self.n_sets]        if line in lines:            lines.remove(line)            lines.append(line)1            self.hits += 1            return True        self.misses += 1        lines.append(line)        if len(lines) > self.ways:            lines.pop(0)2        return Falsefor ways in (1, 2):    cache = SetAssocCache(size_bytes=4 * 64, line_bytes=64, ways=ways)    flags = [cache.access(a) for a in [0, 256, 0, 256, 0, 256]]    print(ways, "way:", flags)

1 way: [False, False, False, False, False, False]
2 way: [False, False, True, True, True, True]

1. 1Déplacer une ligne qui réussit à la fin garde la liste ordonnée : la première entrée est toujours la moins récemment utilisée.
2. 2L'ensemble plein perd sa première entrée, la ligne la moins récemment utilisée.

Avec une voie, les deux lignes s'évincent et les six lectures échouent. Avec deux voies, les deux lignes tiennent dans leur ensemble : après les deux premiers défauts à froid, chaque lecture réussit. Ajouter une voie a supprimé tous les défauts de conflit de ce motif.

Voici le piège. Une table de 512 colonnes float64 a des lignes d'exactement 4096 octets. Lire une colonne revient à lire les adresses 0, 4096, 8192 et ainsi de suite. Dans notre cache, l'indice d'ensemble est le numéro de ligne modulo 64, et 4096 octets font exactement 64 lignes : toutes ces adresses ont donc le même indice d'ensemble. Le code affiche l'ensemble des six premières lignes pour une taille de ligne de 4096 octets et pour 4160 octets, soit 4096 plus une ligne de plus.

n_sets = 64for row_bytes in (4096, 4160):    sets = [(i * row_bytes // 64) % n_sets for i in range(6)]    print(row_bytes, "->", sets)

4096 -> [0, 0, 0, 0, 0, 0]
4160 -> [0, 1, 2, 3, 4, 5]

Avec des lignes de 4096 octets, toutes les clôtures d'une colonne se disputent l'ensemble 0. Avec des lignes de 4160 octets, elles parcourent les ensembles 0, 1, 2, 3 et ainsi de suite, en utilisant tout le cache. Le code suivant lit 96 clôtures deux fois et mesure le taux de défauts pour 1, 2, 4 et 8 voies.

def column_trace(n_rows, row_bytes, passes):    return [i * row_bytes for i in range(n_rows)] * passesdef miss_rates_by_ways(trace, size_bytes, line_bytes, ways_list):    rates = {}    for ways in ways_list:        cache = SetAssocCache(size_bytes, line_bytes, ways)        for address in trace:            cache.access(address)        rates[ways] = cache.misses / len(trace)    return ratesfor row_bytes in (4096, 4160):    print(row_bytes, miss_rates_by_ways(column_trace(96, row_bytes, 2), 32768, 64, [1, 2, 4, 8]))

4096 {1: 1.0, 2: 1.0, 4: 1.0, 8: 1.0}
4160 {1: 0.5, 2: 0.5, 4: 0.5, 8: 0.5}

La table remplie ne rate qu'au premier passage : 0,5 de toutes les lectures, quel que soit le nombre de voies. La table alignée rate à chaque lecture, même avec 8 voies, car 96 lignes ont besoin de 96 places et l'ensemble en a 8. Pire, LRU évince toujours la ligne que vous lirez ensuite dans un motif cyclique, donc le second passage ne trouve rien. Plus de voies n'aideraient qu'en atteignant le nombre de lignes.

Le labo suit le cours : le découpage de l'adresse, le cache LRU, les deux sortes de traces, la comparaison selon le nombre de voies et l'étude sur la vraie table SPY.

• Fonction · questionS'appuie sur
• split_address(address, line_bytes, n_sets)Quelle étiquette, quel ensemble et quel déplacement une adresse a-t-elle ?La division entière
• SetAssocCache(size_bytes, line_bytes, ways).access(address)Cette lecture est-elle un succès dans un cache LRU à plusieurs voies ?Des ensembles de lignes en ordre LRU
• conflict_trace(n_lines, line_bytes, n_sets, rounds)Quelles adresses entrent toutes en collision dans un ensemble ?De l'arithmétique simple
• column_trace(n_rows, row_bytes, passes)Quelles adresses la lecture d'une colonne touche-t-elle ?De l'arithmétique simple
• miss_rates_by_ways(trace, size_bytes, line_bytes, ways_list)Comment davantage de voies changent-elles le taux de défauts ?SetAssocCache
• study(bars)Que coûtent des lignes espacées de 4096 octets ?column_tracemiss_rates_by_ways

Sujet suivant : le cache garde maintenant les bonnes lignes quand elles n'entrent pas en collision, mais combien de temps les lignes restent-elles utiles ? Dans Localité temporelle et ensembles de travail, vous mesurez à quelle vitesse une valeur est relue et trouvez la taille de cache à partir de laquelle un programme tient.