Políticas de colocação de cache - Cache placement policies

Não deve ser confundido com políticas de substituição de cache .

Um cache de CPU é uma memória que contém os dados recentemente utilizados pelo processador. Um bloco de memória não pode necessariamente ser colocado aleatoriamente no cache e pode ser restrito a uma única linha de cache ou um conjunto de linhas de cache pela política de colocação de cache . Em outras palavras, a política de colocação de cache determina onde um bloco de memória específico pode ser colocado quando vai para o cache.

Existem três políticas diferentes disponíveis para a colocação de um bloco de memória no cache: mapeado direto, totalmente associativo e associativo de conjunto. Originalmente, esse espaço de organizações de cache foi descrito usando o termo "mapeamento de congruência".

Cache mapeado diretamente

Em uma estrutura de cache mapeado diretamente, o cache é organizado em vários conjuntos com uma única linha de cache por conjunto. Com base no endereço do bloco de memória, ele só pode ocupar uma única linha de cache. O cache pode ser enquadrado como uma matriz de coluna (n * 1).

Para colocar um bloco no cache

  • O conjunto é determinado pelos bits de índice derivados do endereço do bloco de memória.
  • O bloco de memória é colocado no conjunto identificado e a tag é armazenada no campo da tag associada ao conjunto.
  • Se a linha do cache estiver ocupada anteriormente, os novos dados substituirão o bloco de memória no cache.

Para pesquisar uma palavra no cache

  • O conjunto é identificado pelos bits de índice do endereço.
  • Os bits de tag derivados do endereço do bloco de memória são comparados com os bits de tag associados ao conjunto. Se a tag corresponder, haverá um acerto de cache e o bloco de cache será retornado ao processador. Caso contrário, ocorre uma falha no cache e o bloco de memória é obtido da memória inferior ( memória principal , disco ).

Vantagens

  • Esta política de posicionamento é eficiente em termos de energia, pois evita a pesquisa em todas as linhas de cache.
  • A política de colocação e a política de substituição são simples.
  • Requer hardware barato, pois apenas uma tag precisa ser verificada por vez.

Desvantagem

  • Ele tem uma taxa de acerto de cache mais baixa, pois há apenas uma linha de cache disponível em um conjunto. Cada vez que uma nova memória é referenciada para o mesmo conjunto, a linha do cache é substituída, o que causa perda de conflito.

Exemplo

Cache mapeado diretamente

Considere uma memória principal de 16 kilobytes, que é organizada como blocos de 4 bytes, e um cache mapeado diretamente de 256 bytes com um tamanho de bloco de 4 bytes. Como a memória principal é de 16kB, precisamos de no mínimo 14 bits para representar exclusivamente um endereço de memória.

Como cada bloco de cache tem 4 bytes, o número total de conjuntos no cache é 256/4, o que equivale a 64 conjuntos.

O endereço de entrada para o cache é dividido em bits para deslocamento , índice e tag .

  • O deslocamento corresponde aos bits usados ​​para determinar o byte a ser acessado a partir da linha do cache. Como as linhas de cache têm 4 bytes de comprimento, há 2 bits de deslocamento .
  • O índice corresponde aos bits usados ​​para determinar o conjunto do Cache. Existem 64 conjuntos no cache e, como 2 ^ 6 = 64, existem 6 bits de índice.
  • O tag corresponde aos bits restantes. Isso significa que há 14 - (6 + 2) = 6 bits de tag , que são armazenados no campo de tag para corresponder ao endereço na solicitação de cache.

Abaixo estão os endereços de memória e uma explicação de para qual linha de cache eles mapeiam:

  1. O endereço 0x0000(tag - 0b00_0000, índice - 0b00_0000, deslocamento - 0b00) corresponde ao bloco 0 da memória e mapeia para o conjunto 0 do cache.
  2. O endereço 0x0004(tag - 0b00_0000, index - 0b00_0001, offset - 0b00) corresponde ao bloco 1 da memória e mapeia para o conjunto 1 do cache.
  3. O endereço 0x00FF(tag - 0b00_0000, índice - 0b11_1111, deslocamento - 0b11) corresponde ao bloco 63 da memória e mapeia para o conjunto 63 do cache.
  4. O endereço 0x0100(tag - 0b00_0001, index - 0b00_0000, offset - 0b00) corresponde ao bloco 64 da memória e mapeia para o conjunto 0 do cache.

Cache totalmente associativo

Em um cache totalmente associativo, o cache é organizado em um único conjunto de cache com várias linhas de cache. Um bloco de memória pode ocupar qualquer uma das linhas de cache. A organização do cache pode ser enquadrada como uma matriz de linha (1 * m).

Para colocar um bloco no cache

  • A linha do cache é selecionada com base no bit válido associado a ela. Se o bit válido for 0, o novo bloco de memória pode ser colocado na linha do cache, caso contrário, ele deve ser colocado em outra linha do cache com o bit válido 0.
  • Se o cache estiver completamente ocupado, um bloco é removido e o bloco de memória é colocado nessa linha de cache.
  • O despejo do bloco de memória do cache é decidido pela política de substituição.

Para pesquisar uma palavra no cache

  • O campo Tag do endereço de memória é comparado com bits de tag associados a todas as linhas de cache. Se corresponder, o bloco está presente no cache e é uma ocorrência do cache. Se não corresponder, é uma falha de cache e deve ser buscado na memória inferior.
  • Com base no deslocamento, um byte é selecionado e retornado ao processador.
Cache totalmente associativo

Vantagens

  • A estrutura de cache totalmente associativa nos fornece a flexibilidade de colocar o bloco de memória em qualquer uma das linhas de cache e, portanto, a utilização total do cache.
  • A política de posicionamento fornece melhor taxa de acerto de cache.
  • Ele oferece a flexibilidade de utilizar uma ampla variedade de algoritmos de substituição se ocorrer uma falha de cache

Desvantagem

  • A política de posicionamento é lenta, pois leva tempo para iterar por todas as linhas.
  • A política de localização consome muita energia, pois precisa iterar em todo o conjunto de cache para localizar um bloco.
  • O mais caro de todos os métodos, devido ao alto custo do hardware de comparação associativa.

Exemplo

Considere uma memória principal de 16 kilobytes, que é organizada como blocos de 4 bytes, e um cache totalmente associativo de 256 bytes e um tamanho de bloco de 4 bytes. Como a memória principal é de 16kB, precisamos de no mínimo 14 bits para representar exclusivamente um endereço de memória.

Como cada bloco de cache tem 4 bytes, o número total de conjuntos no cache é 256/4, o que equivale a 64 conjuntos ou linhas de cache.

O endereço de entrada para o cache é dividido em bits para deslocamento e tag.

  • O deslocamento corresponde aos bits usados ​​para determinar o byte a ser acessado a partir da linha do cache. No exemplo, existem 2 bits de deslocamento, que são usados ​​para endereçar os 4 bytes da linha de cache
  • O tag corresponde aos bits restantes. Isso significa que há 14 - (2) = 12 bits de tag , que são armazenados no campo de tag para corresponder ao endereço na solicitação de cache.

Uma vez que qualquer bloco de memória pode ser mapeado para qualquer linha de cache, o bloco de memória pode ocupar uma das linhas de cache com base na política de substituição.

Cache associativo de conjunto

O cache associativo definido é uma troca entre o cache mapeado diretamente e o cache totalmente associativo.

Um cache de conjunto associativo pode ser imaginado como uma matriz (n * m). O cache é dividido em 'n' conjuntos e cada conjunto contém 'm' linhas de cache. Um bloco de memória é primeiro mapeado em um conjunto e, em seguida, colocado em qualquer linha de cache do conjunto.

A gama de caches de mapeamento direto a totalmente associativo é um continuum de níveis de associatividade de conjunto. (Um cache mapeado diretamente é associativo por conjunto unilateral e um cache totalmente associativo com m linhas de cache é associativo por conjunto m ).

Muitos caches de processador nos projetos atuais são mapeados diretamente, conjuntos associativos bidirecionais ou associativos de quatro vias.

Para colocar um bloco no cache

  • O conjunto é determinado pelos bits de índice derivados do endereço do bloco de memória.
  • O bloco de memória é colocado em uma linha de cache disponível no conjunto identificado, e a tag é armazenada no campo de tag associado à linha. Se todas as linhas de cache do conjunto estiverem ocupadas, os novos dados substituirão o bloco identificado pela política de substituição .

Para localizar uma palavra no cache

  • O conjunto é determinado pelos bits de índice derivados do endereço do bloco de memória.
  • Os bits de tag são comparados com os tags de todas as linhas de cache presentes no conjunto selecionado. Se a tag corresponder a qualquer uma das linhas de cache, é um acerto de cache e a linha apropriada é retornada. Se a tag não corresponder a nenhuma das linhas, é um erro de cache e os dados são solicitados do próximo nível na hierarquia de memória.

Vantagens

  • A política de posicionamento é uma troca entre o cache mapeado diretamente e o totalmente associativo.
  • Ele oferece a flexibilidade de usar algoritmos de substituição se ocorrer uma falha de cache.

Desvantagens

  • A política de posicionamento não usará efetivamente todas as linhas de cache disponíveis no cache e sofre com a perda de conflito .

Exemplo

Considere uma memória principal de 16 kilobytes, que é organizada como blocos de 4 bytes, e um cache associativo de conjunto de 2 vias de 256 bytes com um tamanho de bloco de 4 bytes. Como a memória principal é de 16kB, precisamos de no mínimo 14 bits para representar exclusivamente um endereço de memória.

Como cada bloco de cache tem 4 bytes e é associativo de conjunto bidirecional, o número total de conjuntos no cache é 256 / (4 * 2), o que equivale a 32 conjuntos.

Set-Associative Cache

O endereço de entrada para o cache é dividido em bits para deslocamento, índice e tag.

  • O deslocamento corresponde aos bits usados ​​para determinar o byte a ser acessado a partir da linha do cache. Como as linhas de cache têm 4 bytes de comprimento, há 2 bits de deslocamento .
  • O índice corresponde aos bits usados ​​para determinar o conjunto do Cache. Existem 32 conjuntos no cache e, como 2 ^ 5 = 32, existem 5 bits de índice.
  • O tag corresponde aos bits restantes. Isso significa que há 14 - (5 + 2) = 7 bits , que são armazenados no campo do tag para corresponder ao endereço na solicitação de cache.

Abaixo estão os endereços de memória e uma explicação de qual linha de cache em que conjunto eles mapeiam:

  1. O endereço 0x0000(tag - 0b000_0000, índice - 0b0_0000, deslocamento - 0b00) corresponde ao bloco 0 da memória e mapeia para o conjunto 0 do cache. O bloco ocupa uma linha do cache no conjunto 0, determinado pela política de substituição do cache.
  2. O endereço 0x0004(tag - 0b000_0000, índice - 0b0_0001, deslocamento - 0b00) corresponde ao bloco 1 da memória e mapeia para o conjunto 1 do cache. O bloco ocupa uma linha de cache no conjunto 1, determinada pela política de substituição do cache.
  3. O endereço 0x00FF(tag - 0b000_0000, índice - 0b1_1111, deslocamento - 0b11) corresponde ao bloco 63 da memória e mapeia para o conjunto 31 do cache. O bloco ocupa uma linha de cache no conjunto 31, determinada pela política de substituição para o cache.
  4. O endereço 0x0100(tag - 0b000_0001, index - 0b0_0000, offset - 0b00) corresponde ao bloco 64 da memória e mapeia para o conjunto 0 do cache. O bloco ocupa uma linha de cache no conjunto 0, determinada pela política de substituição do cache.

Cache associativo enviesado bidirecional

Outros esquemas foram sugeridos, como o cache distorcido , onde o índice para o caminho 0 é direto, como acima, mas o índice para o caminho 1 é formado com uma função hash . Uma boa função hash tem a propriedade de que os endereços que entram em conflito com o mapeamento direto tendem a não entrar em conflito quando mapeados com a função hash e, portanto, é menos provável que um programa sofra de um número inesperadamente grande de erros de conflito devido a um acesso patológico padronizar. A desvantagem é a latência extra do cálculo da função hash. Além disso, quando chega a hora de carregar uma nova linha e remover uma linha antiga, pode ser difícil determinar qual linha existente foi usada menos recentemente, porque a nova linha entra em conflito com dados em índices diferentes em cada forma; O rastreamento de LRU para caches não distorcidos geralmente é feito por conjunto. No entanto, os caches associativos enviesados ​​têm grandes vantagens sobre os conjuntos associativos convencionais.

Cache pseudo-associativo

Um verdadeiro cache de conjunto associativo testa todas as maneiras possíveis simultaneamente, usando algo como uma memória endereçável por conteúdo . Um cache pseudo-associativo testa cada forma possível, uma de cada vez. Um cache hash-rehash e um cache associativo de coluna são exemplos de um cache pseudo-associativo.

No caso comum de encontrar um acerto na primeira forma testada, um cache pseudo-associativo é tão rápido quanto um cache mapeado diretamente, mas tem uma taxa de falha de conflito muito menor do que um cache mapeado diretamente, mais próximo da taxa de falha de um cache totalmente associativo.

Veja também

Referências