TLB et grandes pages

Avant qu'une lecture n'atteigne le cache, il lui faut une adresse physique, et la traduction a son propre petit cache, le TLB, avec seulement environ 64 entrées. Un programme qui saute entre plus de pages que cela peut rater le TLB à presque chaque lecture, même quand ses caches de données vont bien. Ce cours construit un TLB et montre comment une page de 2 Mo transforme 250 pages en une seule.

Les adresses qu'utilise un programme sont virtuelles : chaque programme croit posséder une longue file de mémoire à partir de zéro. La machine garde la vraie mémoire en adresses physiques et découpe les deux mondes en pages. Une table en mémoire, la table des pages, dit quelle page physique contient chaque page virtuelle. Toute lecture a d'abord besoin de cette traduction : prendre le numéro de page de l'adresse virtuelle, le chercher, et garder la position de l'octet dans la page. C'est le même découpage que la ligne d'un cache, avec un bloc plus gros.

page_bytes = 4096for address in (0, 4095, 4096, 123456789):    print(address, "-> page", address // page_bytes, "byte", address % page_bytes)1

0 -> page 0 byte 0
4095 -> page 0 byte 4095
4096 -> page 1 byte 0
123456789 -> page 30140 byte 3349

1. 1Le numéro de page est l'adresse divisée par la taille de page ; le reste est l'octet dans la page.

Parcourir la table des pages en mémoire à chaque lecture doublerait le coût d'un accès mémoire : le processeur garde donc ses dernières traductions dans une petite table rapide appelée TLB. Une lecture dont la page est dans le TLB est un succès et ne coûte presque rien. Une lecture dont la page n'y est pas est un défaut de TLB et déclenche un parcours de la table des pages, des dizaines de nanosecondes. Un TLB de données de premier niveau contient environ 64 entrées. À part qu'il garde des pages au lieu de lignes, il fonctionne comme les caches précédents : la moins récemment utilisée part d'abord.

class TLB:    def __init__(self, entries):        self.entries = entries        self.pages = []        self.hits = 0        self.misses = 0    def access(self, address, page_bytes):        page = address // page_bytes        if page in self.pages:            self.pages.remove(page)            self.pages.append(page)            self.hits += 1            return True        self.misses += 1        self.pages.append(page)        if len(self.pages) > self.entries:            self.pages.pop(0)        return Falsedef tlb_misses(trace, entries, page_bytes):    tlb = TLB(entries)    for address in trace:        tlb.access(address, page_bytes)    return tlb.missesfor n_pages in (48, 64, 65, 80):    trace = [page * 4096 for page in range(n_pages)] * 5    print(n_pages, "pages, 5 rounds:", tlb_misses(trace, 64, 4096), "misses")

48 pages, 5 rounds: 48 misses
64 pages, 5 rounds: 64 misses
65 pages, 5 rounds: 325 misses
80 pages, 5 rounds: 400 misses

Une boucle sur 48 ou 64 pages n'échoue qu'au premier tour. Une page de plus, 65, et le TLB échoue à chaque lecture des 5 tours : 325 défauts sur 325. C'est la même falaise LRU que dans le sujet des ensembles de travail, mais avec des pages. Ce qui compte est la portée : la quantité de mémoire que le TLB couvre d'un coup.

Prenez une table de 2 000 enregistrements de 512 octets chacun : un jour de données plus des champs supplémentaires. Elle occupe 1 000 Ko, soit 250 pages de 4 Ko, presque quatre fois les 64 pages que le TLB peut contenir. Lire les enregistrements dans l'ordre est doux : huit enregistrements partagent chaque page, le TLB échoue donc une fois par page, 250 fois. Les lire dans un ordre aléatoire est dur : chaque lecture peut tomber sur l'une des 250 pages et le TLB n'en garde que 64. Le code ci-dessous mesure les deux, avec des pages de 4 Ko et de 2 Mo.

import randomorder = list(range(2000))shuffled = random.Random(7).sample(order, len(order))for name, records in (("in order", order), ("shuffled", shuffled)):    trace = [record * 512 for record in records]    print(name, "4 KB pages:", tlb_misses(trace, 64, 4096), "- 2 MB pages:", tlb_misses(trace, 64, 2 * 1024 * 1024))

in order 4 KB pages: 250 - 2 MB pages: 1
shuffled 4 KB pages: 1541 - 2 MB pages: 1

Dans l'ordre, les pages de 4 Ko coûtent 250 défauts. Mélangé, elles coûtent 1 541 défauts sur 2 000 lectures, 77 % des lectures, six fois plus. Avec des pages de 2 Mo, les 1 000 Ko tiennent dans une seule page : un défaut quel que soit l'ordre. À 30 ns par parcours, la lecture mélangée passe 46 microsecondes rien qu'en traductions, de quoi faire 100 000 additions.

Le labo suit le cours : la page d'une adresse, le TLB à remplacement LRU, le décompte des défauts, les pages qu'une trace touche, les adresses d'enregistrements dans un ordre, la comparaison des tailles de page et l'étude sur les enregistrements SPY.

• Fonction · questionS'appuie sur
• page_of(address, page_bytes)Quelle page contient cette adresse ?La division entière
• TLB(entries).access(address, page_bytes)Cette traduction est-elle un succès de TLB ?page_of
• tlb_misses(trace, entries, page_bytes)Combien de défauts de TLB une trace coûte-t-elle ?TLB
• pages_touched(trace, page_bytes)Combien de pages différentes une trace touche-t-elle ?page_of
• record_trace(order, record_bytes)Quelles adresses touche la lecture des enregistrements dans cet ordre ?De l'arithmétique simple
• compare_pages(trace, entries)Que gagnent les grandes pages ?tlb_misses
• study(bars)Que font gagner les grandes pages sur les enregistrements SPY ?compare_pagespages_touchedrecord_trace

Sujet suivant : jusqu'ici il y avait un programme et un cœur. Dans Faux partage et remplissage, deux cœurs écrivent dans deux variables différentes qui se trouvent dans la même ligne de cache, et la ligne fait des allers-retours entre eux. Vous comptez les invalidations et les supprimez par remplissage.