Associatividade e faltas por conflito

Num cache com uma posição por linha, duas linhas muito usadas que dividem uma posição se expulsam repetidamente. Dê várias vias a cada posição e o problema quase some, a menos que as linhas da sua tabela estejam separadas por exatamente 4096 bytes. Esta aula constrói um cache associativo por conjuntos e mostra como um tamanho de linha que é potência de dois pode fazer 100% das leituras falharem.

No cache de mapeamento direto do tópico anterior cada linha de memória tem exatamente uma posição. Se o seu programa continua usando duas linhas que vão para a mesma posição, digamos a linha 0 e a linha 8 num cache de 8 posições, cada leitura de uma expulsa a outra, embora as outras sete posições possam estar vazias. O tamanho do cache não é o problema: as linhas disputam um lugar pequeno demais. Uma falta desse tipo se chama falta por conflito.

A solução é agrupar as posições. As posições são reunidas em conjuntos, e cada posição dentro de um conjunto é uma via. Uma linha de memória pertence a um conjunto, achado pelo mesmo resto de antes, mas pode ficar em qualquer via desse conjunto. Duas linhas que colidem agora dividem um conjunto com lugar para as duas. O número de conjuntos sai dos tamanhos:

Um endereço agora se divide em três partes. O deslocamento é o byte dentro da linha. O índice do conjunto diz a que conjunto a linha pertence. A tag é o resto do número da linha, e é o que o cache compara para saber se uma via contém esta linha. A função abaixo divide um endereço para um cache com linhas de 64 bytes e 64 conjuntos.

def split_address(address, line_bytes, n_sets):    line = address // line_bytes    return line // n_sets, line % n_sets, address % line_bytes1print(split_address(74565, 64, 64))

(18, 13, 5)

1. 1Tag, índice do conjunto e deslocamento: cada um é uma divisão inteira ou um resto do endereço.

O endereço 74565 é o byte 5 da linha 1165. A linha 1165 vai para o conjunto 13 (1165 módulo 64), e 18 é o que sobra do número da linha, a tag. Toda linha cujo conjunto é 13 disputará as oito vias desse conjunto, qualquer que seja a sua tag.

Quando um conjunto está cheio e chega uma linha nova, uma das linhas precisa sair. A regra habitual é LRU: remove-se a linha usada menos recentemente. Podemos guardar cada conjunto como uma lista Python ordenada da menos recentemente usada para a mais recentemente usada.

1. 1
   Achar o conjuntoO número da linha módulo o número de conjuntos.
2. 2
   Olhar em cada viaEm caso de acerto, mova a linha para a ponta das mais recentemente usadas.
3. 3
   Adicionar em caso de faltaPonha a linha nova na ponta das mais recentemente usadas.
4. 4
   Descartar a mais antigaSe o conjunto tem mais linhas que vias, remova a primeira.

Aqui está o cache inteiro. A execução no fim lê duas linhas, os endereços 0 e 256, que colidem num cache de 256 bytes com linhas de 64 bytes, primeiro com uma via e depois com duas.

class SetAssocCache:    def __init__(self, size_bytes, line_bytes, ways):        self.line_bytes = line_bytes        self.ways = ways        self.n_sets = size_bytes // (line_bytes * ways)        self.sets = [[] for _ in range(self.n_sets)]        self.hits = 0        self.misses = 0    def access(self, address):        line = address // self.line_bytes        lines = self.sets[line % self.n_sets]        if line in lines:            lines.remove(line)            lines.append(line)1            self.hits += 1            return True        self.misses += 1        lines.append(line)        if len(lines) > self.ways:            lines.pop(0)2        return Falsefor ways in (1, 2):    cache = SetAssocCache(size_bytes=4 * 64, line_bytes=64, ways=ways)    flags = [cache.access(a) for a in [0, 256, 0, 256, 0, 256]]    print(ways, "way:", flags)

1 way: [False, False, False, False, False, False]
2 way: [False, False, True, True, True, True]

1. 1Mover para o fim uma linha que acerta mantém a lista em ordem: a primeira entrada é sempre a menos recentemente usada.
2. 2O conjunto cheio perde sua primeira entrada, a linha menos recentemente usada.

Com uma via as duas linhas se expulsam e as seis leituras falham. Com duas vias as duas linhas cabem no seu conjunto: depois das duas primeiras faltas a frio, toda leitura acerta. Acrescentar uma via eliminou todas as faltas por conflito desse padrão.

Agora a armadilha. Uma tabela de 512 colunas float64 tem linhas de exatamente 4096 bytes. Ler uma coluna é ler os endereços 0, 4096, 8192 e assim por diante. No nosso cache o índice do conjunto é o número da linha módulo 64, e 4096 bytes são exatamente 64 linhas, então todos esses endereços têm o mesmo índice de conjunto. O código mostra o conjunto das seis primeiras linhas para um tamanho de linha de 4096 bytes e de 4160 bytes, que é 4096 mais uma linha extra.

n_sets = 64for row_bytes in (4096, 4160):    sets = [(i * row_bytes // 64) % n_sets for i in range(6)]    print(row_bytes, "->", sets)

4096 -> [0, 0, 0, 0, 0, 0]
4160 -> [0, 1, 2, 3, 4, 5]

Com linhas de 4096 bytes todos os fechamentos de uma coluna disputam o conjunto 0. Com linhas de 4160 bytes eles percorrem os conjuntos 0, 1, 2, 3 e assim por diante, usando todo o cache. O código a seguir lê 96 fechamentos duas vezes e mede a taxa de faltas com 1, 2, 4 e 8 vias.

def column_trace(n_rows, row_bytes, passes):    return [i * row_bytes for i in range(n_rows)] * passesdef miss_rates_by_ways(trace, size_bytes, line_bytes, ways_list):    rates = {}    for ways in ways_list:        cache = SetAssocCache(size_bytes, line_bytes, ways)        for address in trace:            cache.access(address)        rates[ways] = cache.misses / len(trace)    return ratesfor row_bytes in (4096, 4160):    print(row_bytes, miss_rates_by_ways(column_trace(96, row_bytes, 2), 32768, 64, [1, 2, 4, 8]))

4096 {1: 1.0, 2: 1.0, 4: 1.0, 8: 1.0}
4160 {1: 0.5, 2: 0.5, 4: 0.5, 8: 0.5}

A tabela com preenchimento só falha na primeira passada: 0,5 de todas as leituras, qualquer que seja o número de vias. A tabela alinhada falha em toda leitura, mesmo com 8 vias, porque 96 linhas precisam de 96 lugares e o conjunto tem 8. Pior, o LRU sempre remove a linha que você vai ler em seguida num padrão cíclico, então a segunda passada não encontra nada. Mais vias só ajudariam ao alcançar o número de linhas.

O laboratório segue a aula: a divisão do endereço, o cache LRU, os dois tipos de rastro, a comparação por número de vias e o estudo sobre a tabela real do SPY.

• Função · perguntaBaseia-se em
• split_address(address, line_bytes, n_sets)Que tag, conjunto e deslocamento tem um endereço?A divisão inteira
• SetAssocCache(size_bytes, line_bytes, ways).access(address)Esta leitura é um acerto num cache LRU com várias vias?Conjuntos de linhas em ordem LRU
• conflict_trace(n_lines, line_bytes, n_sets, rounds)Quais endereços colidem todos num conjunto?Aritmética simples
• column_trace(n_rows, row_bytes, passes)Quais endereços a leitura de uma coluna toca?Aritmética simples
• miss_rates_by_ways(trace, size_bytes, line_bytes, ways_list)Como mais vias mudam a taxa de faltas?SetAssocCache
• study(bars)Quanto custam linhas a 4096 bytes uma da outra?column_tracemiss_rates_by_ways

Próximo tópico: o cache agora guarda as linhas certas quando elas não colidem, mas por quanto tempo as linhas continuam úteis? Em Localidade temporal e conjuntos de trabalho você mede quão cedo um valor é lido de novo e acha o tamanho de cache a partir do qual um programa cabe.