Faux partage et remplissage

Quatre threads mettent chacun à jour leur propre compteur, rien n'est partagé, et pourtant la boucle tourne 40 fois plus lentement qu'elle ne le devrait. La raison est que les quatre compteurs sont dans une même ligne de cache et que les cœurs se la disputent. Ce cours construit un petit modèle de cohérence de cache, montre ce que coûte le faux partage dans une boucle pilotée par les dates de la table SPY, et le corrige avec quelques octets de remplissage.

Jusqu'ici un programme tournait sur un cœur. Une vraie machine a plusieurs cœurs, chacun avec son propre petit cache rapide. Cela crée un problème : si le cœur 0 et le cœur 1 détiennent une copie d'une ligne et que le cœur 0 la modifie, le cœur 1 ne doit pas continuer à lire l'ancienne valeur. La règle matérielle qui l'empêche est la cohérence de cache. La façon la plus simple de l'imposer : avant qu'un cœur écrive dans une ligne, la copie de cette ligne dans tous les autres cœurs est jetée. C'est une invalidation.

1. 1
   Regarder dans son propre cacheSi la ligne n'y est pas, cet accès est un défaut.
2. 2
   En écriture, évincer les autresChaque autre cœur qui détient la ligne perd sa copie : une invalidation chacun.
3. 3
   Garder la ligneEnsuite la ligne est dans le cache de ce cœur, prête pour son prochain accès.

La classe ci-dessous garde, pour chaque cœur, l'ensemble des lignes qu'il détient. Nous rejouons trois étapes : le cœur 0 écrit l'octet 0, le cœur 1 écrit l'octet 8 (la même ligne), puis le cœur 0 écrit de nouveau l'octet 0.

class CoherentCaches:    def __init__(self, n_cores):        self.lines = [set() for _ in range(n_cores)]        self.misses = 0        self.invalidations = 0    def access(self, core, address, write):        line = address // LINE_BYTES        hit = line in self.lines[core]        if not hit:            self.misses += 1        if write:            for other, held in enumerate(self.lines):1                if other != core and line in held:                    held.discard(line)                    self.invalidations += 1        self.lines[core].add(line)        return hitcaches = CoherentCaches(2)print(caches.access(0, 0, True), caches.access(1, 8, True), caches.access(0, 0, True))print("misses:", caches.misses, "invalidations:", caches.invalidations)

False False False
misses: 3 invalidations: 2

1. 1Une écriture retire la ligne de chaque autre cœur qui la détient et compte une invalidation par copie.

Les trois accès échouent. L'écriture du cœur 1 invalide la copie du cœur 0, et la nouvelle écriture du cœur 0 invalide à son tour la copie du cœur 1. Les cœurs 0 et 1 n'ont jamais écrit le même octet, seulement des octets voisins, et pourtant ils se prennent la ligne à chaque écriture.

Une façon courante de compter des événements en parallèle est de donner à chaque cœur son propre compteur, pour qu'aucun cœur n'attende un autre. Les compteurs font 8 octets chacun. Rangez-les les uns après les autres dans un tableau et quatre tiennent dans une ligne de 64 octets. Nous construisons les écritures de 50 tours de mises à jour, une écriture par cœur à chaque tour, et les rejouons avec les compteurs espacés de 8 octets (compacts) et de 64 octets (remplis). Le temps est de 1 ns pour un accès dans le cache du cœur et de 60 ns pour un défaut qui va chercher la ligne dans un autre cœur.

def counter_address(core, stride_bytes):    return core * stride_bytesdef update_trace(n_cores, n_updates, stride_bytes):    return [(core, "w", counter_address(core, stride_bytes)) for _ in range(n_updates) for core in range(n_cores)]def run_trace(trace, n_cores):    caches = CoherentCaches(n_cores)    for core, op, address in trace:        caches.access(core, address, op == "w")    return {"accesses": len(trace), "misses": caches.misses, "invalidations": caches.invalidations}def time_ns(stats):    return (stats["accesses"] - stats["misses"]) * HIT_NS + stats["misses"] * MISS_NSfor name, stride in (("packed", 8), ("padded", 64)):    stats = run_trace(update_trace(4, 50, stride), 4)    print(name, stats, time_ns(stats), "ns")

packed {'accesses': 200, 'misses': 200, 'invalidations': 199} 12000.0 ns
padded {'accesses': 200, 'misses': 4, 'invalidations': 0} 436.0 ns

Compacts, les 200 écritures échouent toutes et 199 d'entre elles invalident le dernier écrivain : 12 000 ns. Remplis, chaque cœur garde son compteur dans une ligne à lui : quatre défauts à froid au début, puis chaque écriture réussit, et aucune invalidation : 436 ns. C'est 27 fois plus rapide pour exactement la même arithmétique, car les quatre cœurs ne se prennent plus la ligne.

Pour donner à chaque compteur une ligne à lui, la distance entre deux compteurs doit être un multiple de la taille de ligne : la taille de l'élément est donc arrondie au multiple de 64 supérieur. Un compteur de 8 octets prend 64 octets, ce qui en gaspille 56. Un élément de 65 octets en prend 128. La fonction ci-dessous fait l'arrondi.

def padding_needed(item_bytes):    return math.ceil(item_bytes / LINE_BYTES) * LINE_BYTESprint([padding_needed(size) for size in (8, 63, 64, 65, 100)])

[64, 64, 64, 128, 128]

Dans le labo, quatre cœurs comptent chacun les jours de bourse dont ils s'occupent, et le jour numéro i de la table SPY va au cœur jour de la semaine % 4. Les 1 000 premiers jours pilotent les écritures dans l'ordre des dates. Comme les jours suivent le calendrier, le même cœur écrit rarement deux fois de suite et la ligne est reprise sans cesse. Avec les compteurs compacts, 818 des 1 000 écritures échouent et 817 invalident un autre cœur ; avec les compteurs remplis, seules les quatre premières écritures échouent.

Le labo construit le modèle de cohérence, les traces de compteurs par cœur avec un pas donné, le rejeu, la règle de remplissage, le modèle de temps et l'étude sur les dates de SPY.

• Fonction · questionS'appuie sur
• CoherentCaches(n_cores).access(core, address, write)Succès ou défaut, et qui perd une copie ?De l'arithmétique simple
• counter_address(core, stride_bytes)Où vit le compteur d'un cœur ?De l'arithmétique simple
• update_trace(n_cores, n_updates, stride_bytes)Quelles écritures les cœurs font-ils ?counter_address
• run_trace(trace, n_cores)Combien de défauts et d'invalidations ?CoherentCaches
• padding_needed(item_bytes)À quelle distance doivent être les éléments ?De l'arithmétique simple
• time_ns(stats)Combien de temps dure l'exécution ?Les coûts de succès et de défaut
• study(bars)Que coûte le faux partage sur les dates de SPY ?run_tracepadding_neededtime_ns

Sujet suivant : le faux partage concerne des cœurs qui partagent un socket. Sur une machine à deux sockets, la mémoire elle-même est coupée en deux : une partie est proche d'un cœur, une autre est loin. Dans Effets NUMA, vous placez des pages sur des nœuds, comptez les accès locaux et distants et chiffrez la différence.