Préchargement

Un défaut ne coûte 80 ns que si le programme doit l'attendre. Un préchargeur demande une ligne avant le programme, de sorte que l'attente est terminée quand la lecture arrive. Ce cours construit deux préchargeurs, les note par couverture et précision, et montre où ils marchent, dans des boucles à pas régulier, et où ils ne peuvent rien, dans des lectures dans un ordre imprévisible.

Jusqu'ici le cache chargeait une ligne quand une lecture échouait. Un préchargement la charge plus tôt. Si le pari est bon, la lecture qui vient plus tard trouve la ligne déjà dans le cache et réussit. Tous les processeurs modernes ont des préchargeurs matériels qui surveillent les adresses des lectures et devinent la suite. Le pari le plus simple : celui qui a lu la ligne L voudra ensuite la ligne L + 1. Notre cache fourni a une méthode fill qui charge une ligne sans compter ni succès ni défaut, ce qui est exactement un préchargement.

def baseline_misses(trace):    cache = Cache()    for address in trace:        cache.access(address)    return cache.missesdef next_line_misses(trace):    cache = Cache()    for address in trace:        cache.access(address)        cache.fill((address // LINE_BYTES + 1) * LINE_BYTES)1    return cache.missestrace = [8 * i for i in range(800)]print("no prefetch:", baseline_misses(trace), "- next line:", next_line_misses(trace))jumps = [i * 4096 for i in range(50)]print("jumps of 4096 bytes:", baseline_misses(jumps), "- next line:", next_line_misses(jumps))

no prefetch: 100 - next line: 1
jumps of 4096 bytes: 50 - next line: 50

1. 1Précharger la ligne suivante ne coûte rien ici : fill ne compte ni comme un succès ni comme un défaut.

En lisant 800 valeurs dans l'ordre, un cache simple échoue une fois par ligne, soit 100 fois. Avec le préchargeur de ligne suivante, il n'échoue qu'une fois au total : après la toute première lecture, la ligne nécessaire ensuite est toujours déjà là. Le second cas montre la limite. Si le programme saute de 4096 octets à chaque fois, la ligne qui suit la courante est inutile et le préchargeur n'économise rien : toujours 50 défauts sur 50 lectures.

Les vrais préchargeurs cherchent un motif dans les lignes qu'un programme lit. Le plus courant est un pas constant : le programme lit les lignes 0, 3, 6, 9, en sautant trois lignes à chaque fois. Un détecteur de pas retient la dernière ligne et le dernier écart. Quand le nouvel écart égale le précédent, c'est un motif et la ligne suivante est la courante plus l'écart. Il faut deux écarts égaux pour être sûr : il ne devine donc jamais aux deux premières lectures.

1. 1
   Ignorer une répétitionRelire la même ligne ne dit rien sur un pas.
2. 2
   Calculer l'écartLa nouvelle ligne moins la dernière ligne.
3. 3
   Comparer avec le dernier écartDes écarts égaux signifient un motif : prédisez la nouvelle ligne plus l'écart.
4. 4
   Se souvenirGardez le nouvel écart et la nouvelle ligne pour la lecture suivante.

class StridePrefetcher:    def __init__(self):        self.last_line = None        self.last_delta = None    def observe(self, line):        if line == self.last_line:            return None        prediction = None        if self.last_line is not None:            delta = line - self.last_line            if delta == self.last_delta and line + delta >= 0:1                prediction = line + delta            self.last_delta = delta        self.last_line = line        return predictionp = StridePrefetcher()print([p.observe(line) for line in [0, 3, 6, 9, 12]])p = StridePrefetcher()print([p.observe(line) for line in [5, 5, 5, 6, 7]])

[None, None, 9, 12, 15]
[None, None, None, None, 8]

1. 1Deux écarts égaux de suite : c'est un pas, donc la ligne suivante est la courante plus l'écart.

La première séquence est un pas de trois lignes. Le détecteur ne dit rien aux deux premières lectures, puis prédit 9, 12 et 15, toujours un pas devant. Dans la seconde séquence, les lectures répétées de la ligne 5 sont ignorées, et le pas de 1 n'est confirmé qu'à la dernière lecture. Un bon détecteur est prudent : une mauvaise prédiction a un prix, comme nous le verrons.

Deux nombres notent un préchargeur. La couverture dit quelle part du problème il a résolue. La précision dit quelle part de son travail était utile. Pour les mesurer, nous passons la trace dans le cache, faisons une lecture, demandons au préchargeur ce qu'il faut charger ensuite, retenons quelles lignes ont été préchargées et comptons quand une lecture réussit sur l'une d'elles.

def run_with_prefetcher(trace, prefetcher):    cache = Cache()    marked = set()    prefetches = 0    useful = 0    for address in trace:        line = address // LINE_BYTES        if cache.access(address):            if line in marked:                useful += 1                marked.discard(line)        else:            marked.discard(line)        target = prefetcher.observe(line)        if target is not None and not cache.contains(target * LINE_BYTES):            cache.fill(target * LINE_BYTES)            prefetches += 1            marked.add(target)    return {"demand_misses": cache.misses, "prefetches": prefetches, "useful": useful}def quality(trace):    baseline = baseline_misses(trace)    run = run_with_prefetcher(trace, StridePrefetcher())    coverage = 1 - run["demand_misses"] / baseline    accuracy = run["useful"] / run["prefetches"] if run["prefetches"] else 0.0    return baseline, run, round(coverage, 3), round(accuracy, 3)import randomordered = [8 * i for i in range(2000)]shuffled = [8 * p for p in random.Random(1).sample(range(2000), 2000)]print("in order:", quality(ordered))print("shuffled:", quality(shuffled))

in order: (250, {'demand_misses': 3, 'prefetches': 248, 'useful': 247}, 0.988, 0.996)
shuffled: (250, {'demand_misses': 250, 'prefetches': 1, 'useful': 0}, 0.0, 0.0)

Sur la lecture dans l'ordre, le préchargeur supprime 98,8 % des défauts et 99,6 % de ses préchargements sont utilisés. Sur la lecture mélangée, il ne fait rien : sans pas répété il ne lance presque jamais de préchargement (un seul), et ne fait donc pas de mal non plus. C'est le comportement voulu. Un préchargeur qui devinerait tout le temps remplirait le cache de lignes que personne ne lit.

Le labo lit 2 000 clôtures de trois façons : rangées les unes après les autres et lues dans l'ordre, rangées dans des lignes de cinq valeurs (un pas de 40 octets), et rangées les unes après les autres mais lues par volume d'échanges croissant. Les deux premières ont un motif régulier ; la troisième visite les jours dans un ordre qui paraît aléatoire, car le volume d'un jour ne dit rien du volume du suivant.

L'indice est dans la question à laquelle répond le préchargeur : que vient ensuite ? Si la réponse est dans le motif des adresses, le matériel la trouve gratuitement. Si l'ordre dépend des données, comme quand on visite des lignes triées par volume, rien ne peut le deviner. La correction côté logiciel consiste à changer la disposition des données pour que l'accès redevienne régulier, par exemple en triant les lignes une fois puis en les lisant dans l'ordre.

Le labo construit les deux préchargeurs, la simulation qui les note et l'étude sur les trois façons de lire les clôtures de SPY.

• Fonction · questionS'appuie sur
• baseline_misses(trace)Combien de défauts sans préchargement ?Cache
• next_line_misses(trace)Combien avec un préchargeur de ligne suivante ?Cache.fill
• StridePrefetcher().observe(line)Quelle ligne vient ensuite ?La dernière ligne et le dernier écart
• run_with_prefetcher(trace, prefetcher)Que s'est-il passé : défauts, préchargements, utiles ?Cache
• quality(trace)Quelles couverture et précision atteint-il ?baseline_missesrun_with_prefetcher
• study(bars)Où le préchargeur aide-t-il sur les clôtures de SPY ?qualitynext_line_misses

Sujet suivant : jusqu'ici une adresse était une ligne et seul comptait un succès de cache. Dans TLB et grandes pages, toute adresse doit d'abord être traduite d'une page virtuelle en page physique, et un petit cache de traductions, le TLB, peut aussi échouer, d'une manière qui dépend de la taille des pages.