Organização e Políticas de Cache

A organização de cache refere-se a como um cache mapeia blocos de memória para armazenamento — seu posicionamento e associatividade — e as políticas que governam a substituição e as escritas, que juntas determinam a frequência de acertos do cache e como ele interage com a memória principal.

Definition

Organização e políticas de cache são as escolhas estruturais e de gerenciamento de um cache — onde os blocos podem ser colocados, qual bloco é despejado em caso de falha e como as escritas são propagadas para níveis inferiores — que governam sua taxa de acertos e comportamento.

Scope

Este tópico abrange o design interno de um único cache: posicionamento direto mapeado, associativo por conjunto e totalmente associativo; políticas de substituição como LRU e suas aproximações; políticas de escrita (write-through versus write-back) e alocação de escrita; tamanho do bloco; e a classificação de falhas em compulsórias, de capacidade e de conflito. Exclui a coerência multi-cache (protocolos de coerência de cache) e a tradução de endereços (memória virtual e paginação).

Core questions

• Como o posicionamento direto mapeado, associativo por conjunto e totalmente associativo diferem em custo e comportamento de conflito?
• Qual política de substituição deve despejar um bloco em caso de falha, e como ela é aproximada de forma econômica?
• Como as políticas write-through e write-back diferem em tráfego e complexidade?
• Como as falhas são classificadas e quais mudanças de design reduzem cada tipo?

Key concepts

• cache direto mapeado
• cache associativo por conjunto
• cache totalmente associativo
• substituição menos recentemente usada (LRU)
• write-through vs write-back
• write-allocate
• tamanho do bloco (linha)
• falhas compulsórias, de capacidade e de conflito

Key theories

Modelo de falhas dos Três Cs

As falhas de cache podem ser categorizadas como compulsórias (primeiro acesso), de capacidade (cache muito pequeno para o conjunto de trabalho) e de conflito (pouca associatividade), uma estrutura que liga cada parâmetro de design — tamanho, tamanho do bloco, associatividade — às falhas que ele reduz.

Mechanisms

Um endereço de memória é dividido em campos de tag, índice e offset. O índice seleciona um conjunto, a tag identifica o bloco dentro dele, e a associatividade define quantos blocos compartilham um conjunto. Em caso de falha, o cache busca o bloco e despeja outro escolhido por uma política de substituição (frequentemente uma aproximação do menos recentemente usado). As escritas podem atualizar a memória principal imediatamente (write-through) ou marcar o bloco como sujo e adiar a atualização (write-back).

Clinical relevance

A organização do cache governa o desempenho efetivo porque as penalidades por falha são grandes em relação aos acertos. Os programadores melhoram o comportamento do cache através do layout de dados, bloqueio e padrões de acesso que aumentam a localidade, enquanto os arquitetos ajustam a associatividade, o tamanho do bloco e a política de escrita para equilibrar a taxa de acertos com a área, o consumo de energia e a largura de banda.

History

Wilkes propôs a memória escrava (cache) em 1965, e os caches foram rapidamente adotados comercialmente. A pesquisa de Alan Jay Smith de 1982 sintetizou medições extensivas de posicionamento, substituição e políticas de escrita, estabelecendo o vocabulário de design ainda usado hoje. O modelo dos três Cs posteriormente forneceu uma maneira estruturada de raciocinar sobre as causas e soluções das falhas.

Key figures

• Maurice Wilkes
• Alan Jay Smith
• John L. Hennessy
• David A. Patterson

Seminal works

• smith1982cache
• hennessy2019

Frequently asked questions

Qual é a diferença entre caches write-through e write-back?

Um cache write-through atualiza tanto o cache quanto a memória principal em cada escrita, mantendo a memória atualizada, mas gerando mais tráfego. Um cache write-back atualiza apenas o cache, marcando o bloco como sujo, e o escreve na memória somente quando despejado, reduzindo o tráfego ao custo de uma contabilidade extra.

Por que usar caches associativos por conjunto em vez de caches direto mapeados?

Um cache direto mapeado permite a cada bloco exatamente uma localização, então blocos que mapeiam para o mesmo slot entram em conflito. A associatividade por conjunto dá a cada bloco várias localizações possíveis dentro de um conjunto, reduzindo as falhas de conflito ao custo de mais hardware de comparação e acertos ligeiramente mais lentos.