TLB e páginas grandes

Antes de uma leitura chegar ao cache ela precisa de um endereço físico, e a tradução tem seu próprio cache pequeno, o TLB, com só cerca de 64 entradas. Um programa que pula entre mais páginas que isso pode errar no TLB em quase toda leitura, mesmo quando seus caches de dados vão bem. Esta aula constrói um TLB e mostra como uma página de 2 MB transforma 250 páginas em uma.

Os endereços que um programa usa são virtuais: cada programa acredita possuir uma longa fila de memória começando em zero. A máquina guarda a memória real em endereços físicos e corta os dois mundos em páginas. Uma tabela na memória, a tabela de páginas, diz qual página física guarda cada página virtual. Toda leitura precisa primeiro dessa tradução: pegar o número da página do endereço virtual, procurá-lo e manter a posição do byte dentro da página. É a mesma divisão da linha de um cache, com um bloco maior.

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. 1O número da página é o endereço dividido pelo tamanho da página; o resto é o byte dentro da página.

Percorrer a tabela de páginas na memória a cada leitura dobraria o custo de um acesso à memória, então o processador guarda suas últimas traduções numa tabela pequena e rápida chamada TLB. Uma leitura cuja página está no TLB é um acerto e quase não custa nada. Uma leitura cuja página não está lá é uma falta de TLB e dispara um percurso da tabela de páginas, dezenas de nanossegundos. Um TLB de dados de primeiro nível guarda cerca de 64 entradas. Além de guardar páginas em vez de linhas, funciona como os caches anteriores: sai primeiro a menos recentemente 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

Um laço sobre 48 ou 64 páginas só falha na primeira rodada. Uma página a mais, 65, e o TLB falha em toda leitura das 5 rodadas: 325 faltas em 325. É o mesmo precipício do LRU do tópico dos conjuntos de trabalho, agora com páginas. O que importa é o alcance: quanta memória o TLB cobre de uma vez.

Pegue uma tabela de 2000 registros de 512 bytes cada: um dia de dados mais campos extras. Ela ocupa 1000 KB, ou seja, 250 páginas de 4 KB, quase quatro vezes as 64 páginas que o TLB comporta. Ler os registros em ordem é suave: oito registros dividem cada página, então o TLB falha uma vez por página, 250 vezes. Lê-los em ordem aleatória é duro: cada leitura pode cair em qualquer das 250 páginas e o TLB guarda só 64. O código abaixo mede os dois, com páginas de 4 KB e 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

Em ordem, as páginas de 4 KB custam 250 faltas. Embaralhadas, custam 1541 faltas em 2000 leituras, 77% das leituras, seis vezes mais. Com páginas de 2 MB os 1000 KB cabem numa só página: uma falta qualquer que seja a ordem. A 30 ns por percurso, a leitura embaralhada gasta 46 microssegundos só em traduções, o que daria para 100 000 somas.

O laboratório segue a aula: a página de um endereço, o TLB com substituição LRU, a contagem de faltas, as páginas que um rastro toca, os endereços de registros numa ordem, a comparação de tamanhos de página e o estudo sobre os registros do SPY.

• Função · perguntaBaseia-se em
• page_of(address, page_bytes)Qual página contém este endereço?A divisão inteira
• TLB(entries).access(address, page_bytes)Esta tradução é um acerto de TLB?page_of
• tlb_misses(trace, entries, page_bytes)Quantas faltas de TLB um rastro custa?TLB
• pages_touched(trace, page_bytes)Quantas páginas diferentes um rastro toca?page_of
• record_trace(order, record_bytes)Quais endereços a leitura dos registros nesta ordem toca?Aritmética simples
• compare_pages(trace, entries)Quanto ajudam as páginas grandes?tlb_misses
• study(bars)O que as páginas grandes economizam nos registros do SPY?compare_pagespages_touchedrecord_trace

Próximo tópico: até agora havia um programa e um núcleo. Em Falso compartilhamento e preenchimento dois núcleos escrevem em duas variáveis diferentes que estão na mesma linha de cache, e a linha vai e volta entre eles. Você conta as invalidações e as corrige com preenchimento.