Linhas de cache e localidade espacial

6 min de leitura4 exemplos de código

Um cache nunca busca um único byte. Busca uma linha inteira de 64 bytes, então o valor vizinho ao que você acabou de ler já está lá. Esta aula constrói um cache, mostra que ler em ordem é oito vezes mais barato do que pular uma linha por vez e aplica isso a uma tabela de preços.

A memória vem em linhas

Buscar na memória custa o mesmo, não importa quantos bytes você peça, então o hardware pede muitos de uma vez. A memória é cortada em blocos de 64 bytes, e o cache sempre carrega e remove blocos inteiros. Imagine um elevador que sobe 64 bytes até o cache: se ele sobe de qualquer jeito, levar seus vizinhos não custa nada, e da próxima vez que precisar de um deles já estará lá em cima.

DefiniçãoLinha de cache

Um bloco de bytes consecutivos, 64 na maioria dos processadores, que o cache carrega e remove como uma só unidade. A linha n contém os bytes de 64n a 64n + 63.

Cada byte tem um endereço, um número que diz onde ele está. Para achar a linha de um endereço, divida pelo tamanho da linha e descarte o resto. O código abaixo mostra a linha de quatro endereços.

main.pyPython

line_bytes = 64for address in (0, 63, 64, 130):    print(address, "is in line", address // line_bytes)

0 is in line 0
63 is in line 0
64 is in line 1
130 is in line 2

Os endereços 0 e 63 compartilham a linha 0, então depois que um é carregado o outro é de graça. O endereço 64 começa a linha 1 e o 130 está na linha 2. Todo este tópico decorre dessa divisão inteira.

Um cache é uma tabela de posições

O cache mais simples é uma tabela com uma posição para cada linha que pode guardar. Um cache de 32 KB com linhas de 64 bytes tem 512 posições. Cada linha de memória só pode ocupar uma posição, achada por um resto: número da linha módulo o número de posições. É um cache de mapeamento direto. Como muitas linhas dividem uma posição, ela guarda também uma tag que diz qual linha ela contém no momento.

1
Achar a linhaDivida o endereço pelo tamanho da linha.
2
Achar a posiçãoTome o número da linha módulo o número de posições.
3
Comparar a tagSe a posição contém esta linha, é um acerto.
4
Substituir em caso de faltaCarregue a linha na posição e esqueça a que estava lá.

Esse é o cache inteiro. A classe abaixo é uma versão completa e funcional em quinze linhas. Lemos quatro valores vizinhos, depois a linha seguinte e depois voltamos ao endereço 0.

main.pyPython

def line_of(address, line_bytes):    return address // line_bytesclass Cache:    def __init__(self, size_bytes, line_bytes):        self.line_bytes = line_bytes        self.n_lines = size_bytes // line_bytes        self.tags = [None] * self.n_lines        self.hits = 0        self.misses = 0    def access(self, address):        line = line_of(address, self.line_bytes)1        slot = line % self.n_lines        if self.tags[slot] == line:2            self.hits += 1            return True        self.misses += 1        self.tags[slot] = line        return Falsecache = Cache(size_bytes=512, line_bytes=64)reads = [0, 8, 16, 24, 64, 72, 0, 512, 0]print([cache.access(a) for a in reads])print(cache.hits, "hits and", cache.misses, "misses")

[False, True, True, True, False, True, True, False, False]
5 hits and 4 misses

1A posição é o número da linha módulo o número de posições.
2Um acerto significa que a tag da posição é esta mesma linha.

Leia a lista de indicadores: a primeira leitura falha e carrega a linha 0, as três seguintes acertam porque estão na linha 0, 64 falha e carrega a linha 1, 72 acerta, e voltar a 0 acerta de novo porque a linha 0 não foi removida. Então o endereço 512 é a linha 8, que também vai para a posição 0 (8 módulo 8), então remove a linha 0, e a última leitura do endereço 0 falha outra vez: um conflito nos custou uma falta.

O tamanho do cache é em bytes, as posições são linhas

Um cache de 512 bytes com linhas de 64 bytes tem só 8 posições, não 512. Esquecer de dividir o tamanho pelo tamanho da linha é o jeito habitual de construir um cache que parece enorme e se comporta errado.

Ler em ordem contra pular

Agora use o cache. Um valor float64 ocupa 8 bytes, então uma linha guarda oito. Leia um array em ordem e a primeira leitura de cada linha falha e as sete seguintes acertam: uma falta a cada oito. Leia com um passo, isto é, pulando um número fixo de valores entre as leituras, e as leituras caem em linhas diferentes. O código a seguir mede a taxa de faltas para passos de 1, 2, 4, 8 e 16 valores.

main.pyPython

def sequential_trace(n, elem_bytes):    return [i * elem_bytes for i in range(n)]def strided_trace(n, elem_bytes, stride):    return [i * stride * elem_bytes for i in range(n)]def miss_rate(trace, size_bytes=32768, line_bytes=64):    cache = Cache(size_bytes, line_bytes)    for address in trace:        cache.access(address)    return cache.misses / len(trace)n = 4096for stride in (1, 2, 4, 8, 16):    print("stride", stride, "values:", miss_rate(strided_trace(n, 8, stride)))

stride 1 values: 0.125
stride 2 values: 0.25
stride 4 values: 0.5
stride 8 values: 1.0
stride 16 values: 1.0

A taxa de faltas dobra a cada dobra do passo até chegar a 1,0: com um passo de 8 valores o salto é de 64 bytes, uma linha inteira, então cada leitura abre uma linha nova e o cache não economiza nada. Um passo maior não pode ser pior, só igual. O padrão é a fórmula abaixo.

miss rate = min(1, stride × value bytes ÷ line bytes)(1)válida para uma varredura longa sobre dados novos, em que nenhuma linha é lida duas vezes

Uma linha sempre tem 64 bytes?

Em quase todos os chips x86 e ARM de servidor, sim. Alguns chips usam 128 bytes num cache externo, então meça o tamanho da linha da máquina que você visa. Nosso cache o recebe como parâmetro para você testar os dois.

A disposição de uma tabela decide o passo

Uma tabela de barras diárias tem cinco números por dia: abertura, máxima, mínima, fechamento e volume. Guarde-a linha a linha, como a maioria dos programas faz, e os cinco números de um dia ficam lado a lado. Para ler só os fechamentos você pula quatro valores entre as leituras: um passo de 5, ou seja, 40 bytes. Guarde cada coluna separada e os fechamentos ficam um após o outro: um passo de 1. Mesmos números, mesmas leituras, disposição diferente.

main.pyPython

closes = 1000as_column = miss_rate(sequential_trace(closes, 8))as_rows = miss_rate(strided_trace(closes, 8, 5))print("column layout:", as_column)print("row layout:   ", as_rows)

column layout: 0.125
row layout:    0.625

Cinco vezes mais leituras falham quando os fechamentos estão espaçados. Isso não muda a resposta do seu programa, só a sua velocidade, e nenhuma linha de aritmética do profiler vai mostrar: o tempo extra é gasto esperando a memória.

O que dizem os dados reaisFechamentos diários do SPY, 5.405 leituras

Faltas, disposição em coluna67612,5% das leituras

Faltas, disposição em linhas3,37862,5% das leituras

Parte das leituras que falham

Em coluna12.5

Em linhas62.5

O que você vai construir

O laboratório pede as peças que você acabou de ler, na mesma ordem, e termina com o estudo sobre a tabela real do SPY.

Função · perguntaBaseia-se em
line_of(address, line_bytes)Qual linha contém este endereço?A divisão inteira
Cache(size_bytes, line_bytes).access(address)Esta leitura é um acerto?line_of
sequential_trace(n, elem_bytes)Quais endereços uma leitura em ordem toca?Aritmética simples
strided_trace(n, elem_bytes, stride)Quais endereços uma leitura com saltos toca?Aritmética simples
miss_rate(trace, size_bytes, line_bytes)Que parte de um rastro falha?Cache
study(bars)Quanto custa a disposição em linhas para os fechamentos do SPY?miss_ratestrided_trace

Verificação rápida

Uma coluna de floats de 4 bytes é lida em ordem com linhas de 64 bytes. Que parte das leituras falha?

Escolha uma resposta.

Próximo tópico: um cache de mapeamento direto tem uma fraqueza que esta aula tocou, o conflito entre linhas que dividem uma posição. Em Associatividade e faltas por conflito você dá várias vagas a cada posição e vê por que uma tabela cujas linhas ficam a 4096 bytes uma da outra pode arruinar um cache.

Lab: o que é avaliado

6 tarefas · 100 pts

A linha de um endereço10 pts
Um cache de mapeamento direto25 pts
Uma leitura em ordem10 pts
Uma leitura com passo10 pts
A taxa de faltas de um rastro20 pts
O estudo com a tabela do SPY25 pts

def line_of(address, line_bytes): return address // line_bytesclass Cache: def __init__(self, size_bytes, line_bytes): self.line_bytes = line_bytes self.n_lines = size_bytes // line_bytes self.tags = [None] * self.n_lines self.hits = 0 self.misses = 0 def access(self, address): line = line_of(address, self.line_bytes) slot = line % self.n_lines if self.tags[slot] == line: self.hits += 1 return True self.misses += 1 self.tags[slot] = line return Falsecache = Cache(size_bytes=512, line_bytes=64)reads = [0, 8, 16, 24, 64, 72, 0, 512, 0]print([cache.access(a) for a in reads])print(cache.hits, "hits and", cache.misses, "misses")

def sequential_trace(n, elem_bytes): return [i * elem_bytes for i in range(n)]def strided_trace(n, elem_bytes, stride): return [i * stride * elem_bytes for i in range(n)]def miss_rate(trace, size_bytes=32768, line_bytes=64): cache = Cache(size_bytes, line_bytes) for address in trace: cache.access(address) return cache.misses / len(trace)n = 4096for stride in (1, 2, 4, 8, 16): print("stride", stride, "values:", miss_rate(strided_trace(n, 8, stride)))