TLB und große Seiten

Bevor ein Lesezugriff den Cache erreicht, braucht er eine physische Adresse, und die Übersetzung hat einen eigenen kleinen Cache, den TLB, mit nur etwa 64 Einträgen. Ein Programm, das zwischen mehr Seiten springt, kann bei fast jedem Lesezugriff den TLB verfehlen, selbst wenn seine Daten-Caches gut arbeiten. Diese Lektion baut einen TLB und zeigt, wie eine 2-MB-Seite 250 Seiten zu einer macht.

Die Adressen, die ein Programm benutzt, sind virtuell: Jedes Programm glaubt, eine lange Reihe Speicher ab null zu besitzen. Die Maschine hält den echten Speicher in physischen Adressen und zerlegt beide Welten in Seiten. Eine Tabelle im Speicher, die Seitentabelle, sagt, welche physische Seite jede virtuelle Seite enthält. Jeder Lesezugriff braucht zuerst diese Übersetzung: die Seitennummer der virtuellen Adresse nehmen, nachschlagen und die Byteposition in der Seite behalten. Es ist dieselbe Aufteilung wie bei der Zeile eines Caches, nur mit einem größeren Block.

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. 1Die Seitennummer ist die Adresse geteilt durch die Seitengröße; der Rest ist das Byte in der Seite.

Bei jedem Lesezugriff die Seitentabelle im Speicher zu durchlaufen würde die Kosten eines Speicherzugriffs verdoppeln, also hält der Prozessor seine letzten Übersetzungen in einer kleinen, schnellen Tabelle, dem TLB. Ein Lesezugriff, dessen Seite im TLB liegt, ist ein Treffer und kostet fast nichts. Ein Lesezugriff, dessen Seite nicht darin liegt, ist ein TLB-Fehlzugriff und löst einen Seitentabellen-Durchlauf aus, Dutzende Nanosekunden. Ein Daten-TLB der ersten Ebene fasst etwa 64 Einträge. Außer dass er Seiten statt Zeilen hält, arbeitet er wie die Caches zuvor: Die am längsten nicht benutzte geht zuerst.

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

Eine Schleife über 48 oder 64 Seiten verfehlt nur in der ersten Runde. Eine Seite mehr, 65, und der TLB verfehlt bei jedem Lesezugriff der 5 Runden: 325 Fehlzugriffe bei 325. Das ist dieselbe LRU-Klippe wie im Thema Arbeitsmengen, jetzt mit Seiten. Entscheidend ist die Reichweite: wie viel Speicher der TLB auf einmal abdeckt.

Nehmen Sie eine Tabelle mit 2.000 Datensätzen zu je 512 Byte: ein Tag Daten plus Zusatzfelder. Sie belegt 1.000 KB, also 250 Seiten zu 4 KB, fast viermal so viele wie die 64 Seiten, die der TLB halten kann. Die Datensätze der Reihe nach zu lesen ist sanft: Acht Datensätze teilen sich jede Seite, der TLB verfehlt also einmal pro Seite, 250-mal. Sie in zufälliger Reihenfolge zu lesen ist hart: Jeder Lesezugriff kann auf jeder der 250 Seiten landen, und der TLB behält nur 64. Der Code unten misst beides, mit 4-KB- und mit 2-MB-Seiten.

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

In Reihenfolge kosten die 4-KB-Seiten 250 Fehlzugriffe. Gemischt kosten sie 1.541 Fehlzugriffe bei 2.000 Lesezugriffen, 77 % der Zugriffe, sechsmal so viel. Mit 2-MB-Seiten passen alle 1.000 KB in eine einzige Seite: ein Fehlzugriff, gleich welche Reihenfolge. Bei 30 ns pro Durchlauf verbringt das gemischte Lesen allein 46 Mikrosekunden mit Übersetzungen, genug für 100.000 Additionen.

Das Labor folgt der Lektion: die Seite einer Adresse, der TLB mit LRU-Ersetzung, die Zählung der Fehlzugriffe, die von einer Spur berührten Seiten, die Adressen von Datensätzen in einer Reihenfolge, der Vergleich der Seitengrößen und die Studie an den SPY-Datensätzen.

• Funktion · FrageBaut auf
• page_of(address, page_bytes)Welche Seite enthält diese Adresse?Die ganzzahlige Division
• TLB(entries).access(address, page_bytes)Ist diese Übersetzung ein TLB-Treffer?page_of
• tlb_misses(trace, entries, page_bytes)Wie viele TLB-Fehlzugriffe kostet eine Spur?TLB
• pages_touched(trace, page_bytes)Wie viele verschiedene Seiten berührt eine Spur?page_of
• record_trace(order, record_bytes)Welche Adressen berührt das Lesen der Datensätze in dieser Reihenfolge?Einfache Arithmetik
• compare_pages(trace, entries)Wie viel helfen große Seiten?tlb_misses
• study(bars)Was sparen große Seiten bei den SPY-Datensätzen?compare_pagespages_touchedrecord_trace

Nächstes Thema: Bisher gab es ein Programm und einen Kern. In False Sharing und Padding schreiben zwei Kerne in zwei verschiedene Variablen, die in derselben Cache-Zeile liegen, und die Zeile wandert zwischen ihnen hin und her. Sie zählen die Invalidierungen und beheben sie durch Padding.