Pré-busca

Uma falta só custa 80 ns se o programa tiver de esperar por ela. Um pré-buscador pede uma linha antes do programa, de modo que a espera já acabou quando a leitura chega. Esta aula constrói dois pré-buscadores, os avalia com cobertura e precisão, e mostra onde funcionam, em laços com passo regular, e onde não conseguem, em leituras em ordem imprevisível.

Até agora o cache carregava uma linha quando uma leitura falhava. Uma pré-busca a carrega antes. Se o palpite estiver certo, a leitura que vem depois encontra a linha já no cache e acerta. Todo processador moderno tem pré-buscadores de hardware que vigiam os endereços das leituras e adivinham o que vem. O palpite mais simples: quem leu a linha L vai querer a linha L + 1 em seguida. Nosso cache fornecido tem um método fill que carrega uma linha sem contar acerto nem falta, que é exatamente uma pré-busca.

def baseline_misses(trace):    cache = Cache()    for address in trace:        cache.access(address)    return cache.missesdef next_line_misses(trace):    cache = Cache()    for address in trace:        cache.access(address)        cache.fill((address // LINE_BYTES + 1) * LINE_BYTES)1    return cache.missestrace = [8 * i for i in range(800)]print("no prefetch:", baseline_misses(trace), "- next line:", next_line_misses(trace))jumps = [i * 4096 for i in range(50)]print("jumps of 4096 bytes:", baseline_misses(jumps), "- next line:", next_line_misses(jumps))

no prefetch: 100 - next line: 1
jumps of 4096 bytes: 50 - next line: 50

1. 1Pré-buscar a linha seguinte não custa nada aqui: fill não conta como acerto nem como falta.

Lendo 800 valores em ordem, um cache simples falha uma vez por linha, 100 vezes. Com o pré-buscador da linha seguinte ele falha uma vez no total: depois da primeiríssima leitura, a linha de que se precisa em seguida já está sempre lá. O segundo caso mostra o limite. Se o programa pula 4096 bytes de cada vez, a linha depois da atual é inútil e o pré-buscador não economiza nada: continuam 50 faltas em 50 leituras.

Os pré-buscadores reais procuram um padrão nas linhas que um programa lê. O mais comum é um passo constante: o programa lê as linhas 0, 3, 6, 9, pulando três linhas cada vez. Um detector de passos lembra a última linha e o último salto. Quando o novo salto é igual ao anterior, é um padrão e a próxima linha é a atual mais o salto. São precisos dois saltos iguais para ter certeza, então ele nunca adivinha nas duas primeiras leituras.

1. 1
   Ignorar uma repetiçãoLer a mesma linha de novo não diz nada sobre um passo.
2. 2
   Calcular o saltoA linha nova menos a última linha.
3. 3
   Comparar com o último saltoSaltos iguais significam um padrão: preveja a linha nova mais o salto.
4. 4
   LembrarGuarde o novo salto e a nova linha para a próxima leitura.

class StridePrefetcher:    def __init__(self):        self.last_line = None        self.last_delta = None    def observe(self, line):        if line == self.last_line:            return None        prediction = None        if self.last_line is not None:            delta = line - self.last_line            if delta == self.last_delta and line + delta >= 0:1                prediction = line + delta            self.last_delta = delta        self.last_line = line        return predictionp = StridePrefetcher()print([p.observe(line) for line in [0, 3, 6, 9, 12]])p = StridePrefetcher()print([p.observe(line) for line in [5, 5, 5, 6, 7]])

[None, None, 9, 12, 15]
[None, None, None, None, 8]

1. 1Dois saltos iguais seguidos: é um passo, então a próxima linha é a atual mais o salto.

A primeira sequência é um passo de três linhas. O detector não diz nada nas duas primeiras leituras e depois prevê 9, 12 e 15, sempre um passo à frente. Na segunda sequência as leituras repetidas da linha 5 são ignoradas e o passo de 1 só é confirmado na última leitura. Um bom detector é cauteloso: um palpite errado tem um preço, como veremos a seguir.

Dois números avaliam um pré-buscador. A cobertura diz quanto do problema ele resolveu. A precisão diz quanto do seu trabalho foi útil. Para medi-los passamos o rastro pelo cache, fazemos uma leitura, perguntamos ao pré-buscador o que carregar em seguida, lembramos quais linhas foram pré-buscadas e contamos quando uma leitura acerta numa delas.

def run_with_prefetcher(trace, prefetcher):    cache = Cache()    marked = set()    prefetches = 0    useful = 0    for address in trace:        line = address // LINE_BYTES        if cache.access(address):            if line in marked:                useful += 1                marked.discard(line)        else:            marked.discard(line)        target = prefetcher.observe(line)        if target is not None and not cache.contains(target * LINE_BYTES):            cache.fill(target * LINE_BYTES)            prefetches += 1            marked.add(target)    return {"demand_misses": cache.misses, "prefetches": prefetches, "useful": useful}def quality(trace):    baseline = baseline_misses(trace)    run = run_with_prefetcher(trace, StridePrefetcher())    coverage = 1 - run["demand_misses"] / baseline    accuracy = run["useful"] / run["prefetches"] if run["prefetches"] else 0.0    return baseline, run, round(coverage, 3), round(accuracy, 3)import randomordered = [8 * i for i in range(2000)]shuffled = [8 * p for p in random.Random(1).sample(range(2000), 2000)]print("in order:", quality(ordered))print("shuffled:", quality(shuffled))

in order: (250, {'demand_misses': 3, 'prefetches': 248, 'useful': 247}, 0.988, 0.996)
shuffled: (250, {'demand_misses': 250, 'prefetches': 1, 'useful': 0}, 0.0, 0.0)

Na leitura em ordem o pré-buscador elimina 98,8% das faltas e 99,6% das suas pré-buscas são usadas. Na leitura embaralhada ele não faz nada: sem um passo repetido quase nunca emite uma pré-busca (só uma), e assim também não faz mal. É o comportamento desejado. Um pré-buscador que adivinhasse o tempo todo encheria o cache de linhas que ninguém lê.

O laboratório lê 2000 fechamentos de três jeitos: guardados um após o outro e lidos em ordem, guardados dentro de linhas de cinco valores (um passo de 40 bytes), e guardados um após o outro mas lidos em ordem de volume de negociação crescente. Os dois primeiros têm um padrão regular; o terceiro visita os dias numa ordem que parece aleatória, porque o volume de um dia não diz nada sobre o volume do seguinte.

A pista está na pergunta que o pré-buscador responde: o que vem a seguir? Se a resposta está no padrão dos endereços, o hardware a acha de graça. Se a ordem depende dos dados, como ao visitar linhas ordenadas por volume, nada consegue adivinhá-la. A correção por software é mudar a disposição dos dados para que o acesso volte a ser regular, por exemplo ordenando as linhas uma vez e depois lendo-as em ordem.

O laboratório constrói os dois pré-buscadores, a simulação que os avalia e o estudo sobre os três jeitos de ler os fechamentos do SPY.

• Função · perguntaBaseia-se em
• baseline_misses(trace)Quantas faltas sem pré-busca?Cache
• next_line_misses(trace)Quantas com um pré-buscador da linha seguinte?Cache.fill
• StridePrefetcher().observe(line)Qual linha vem a seguir?A última linha e o último salto
• run_with_prefetcher(trace, prefetcher)O que aconteceu: faltas, pré-buscas, úteis?Cache
• quality(trace)Que cobertura e precisão ele atinge?baseline_missesrun_with_prefetcher
• study(bars)Onde o pré-buscador ajuda nos fechamentos do SPY?qualitynext_line_misses

Próximo tópico: até agora um endereço era uma linha e só importava um acerto de cache. Em TLB e páginas grandes todo endereço precisa antes ser traduzido de uma página virtual para uma física, e um pequeno cache de traduções, o TLB, também pode falhar, de um jeito que depende do tamanho da página.