TLB y páginas grandes

Antes de que una lectura llegue a la caché necesita una dirección física, y la traducción tiene su propia caché pequeña, el TLB, con solo unas 64 entradas. Un programa que salta entre más páginas que esas puede fallar en el TLB en casi cada lectura, aunque sus cachés de datos vayan bien. Esta lección construye un TLB y muestra cómo una página de 2 MB convierte 250 páginas en una.

Las direcciones que usa un programa son virtuales: cada programa cree poseer una larga fila de memoria que empieza en cero. La máquina guarda la memoria real en direcciones físicas y corta ambos mundos en páginas. Una tabla en memoria, la tabla de páginas, dice qué página física contiene cada página virtual. Toda lectura necesita primero esta traducción: tomar el número de página de la dirección virtual, buscarlo y conservar la posición del byte dentro de la página. Es la misma división que la línea de una caché, con un bloque mayor.

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. 1El número de página es la dirección dividida por el tamaño de página; el resto es el byte dentro de la página.

Recorrer la tabla de páginas en memoria en cada lectura duplicaría el coste de un acceso a memoria, así que el procesador guarda sus últimas traducciones en una tabla pequeña y rápida llamada TLB. Una lectura cuya página está en el TLB es un acierto y casi no cuesta nada. Una lectura cuya página no está es un fallo de TLB y dispara un recorrido de la tabla de páginas, decenas de nanosegundos. Un TLB de datos de primer nivel guarda unas 64 entradas. Salvo por guardar páginas en lugar de líneas, funciona como las cachés anteriores: sale primero la menos recientemente usada.

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

Un bucle sobre 48 o 64 páginas solo falla en la primera ronda. Una página más, 65, y el TLB falla en cada lectura de las 5 rondas: 325 fallos de 325. Es el mismo precipicio LRU del tema de los conjuntos de trabajo, ahora con páginas. Lo que importa es el alcance: cuánta memoria cubre el TLB a la vez.

Tome una tabla de 2000 registros de 512 bytes cada uno: un día de datos más campos extra. Ocupa 1000 KB, es decir 250 páginas de 4 KB, casi cuatro veces las 64 páginas que cabe en el TLB. Leer los registros en orden es suave: ocho registros comparten cada página, así que el TLB falla una vez por página, 250 veces. Leerlos en orden aleatorio es duro: cada lectura puede caer en cualquiera de las 250 páginas y el TLB conserva solo 64. El código siguiente mide ambos, con páginas de 4 KB y de 2 MB.

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

En orden, las páginas de 4 KB cuestan 250 fallos. Mezcladas, cuestan 1541 fallos de 2000 lecturas, el 77 % de las lecturas, seis veces más. Con páginas de 2 MB los 1000 KB caben en una sola página: un fallo sea cual sea el orden. A 30 ns por recorrido, la lectura mezclada gasta 46 microsegundos solo en traducciones, lo que daría para 100 000 sumas.

El laboratorio sigue la lección: la página de una dirección, el TLB con reemplazo LRU, el recuento de fallos, las páginas que toca una traza, las direcciones de registros en un orden, la comparación de tamaños de página y el estudio sobre los registros de SPY.

• Función · preguntaSe apoya en
• page_of(address, page_bytes)¿Qué página contiene esta dirección?La división entera
• TLB(entries).access(address, page_bytes)¿Esta traducción es un acierto de TLB?page_of
• tlb_misses(trace, entries, page_bytes)¿Cuántos fallos de TLB cuesta una traza?TLB
• pages_touched(trace, page_bytes)¿Cuántas páginas distintas toca una traza?page_of
• record_trace(order, record_bytes)¿Qué direcciones toca leer los registros en este orden?Aritmética simple
• compare_pages(trace, entries)¿Cuánto ayudan las páginas grandes?tlb_misses
• study(bars)¿Qué ahorran las páginas grandes en los registros de SPY?compare_pagespages_touchedrecord_trace

Siguiente tema: hasta ahora había un programa y un núcleo. En Falso compartir y relleno dos núcleos escriben en dos variables distintas que están en la misma línea de caché y la línea rebota entre ellos. Cuenta las invalidaciones y las arregla con relleno.