# Hierarquia e caches

Localidade, mapeamento direto e associativo, os três Cs, políticas de escrita e o AMAT.

Página: https://resumos.rgo.pt/cadeiras/ac/hierarquia-cache/

A memória que um programa vê é grande, mas a memória grande é lenta. A hierarquia de memória resolve esta contradição com um facto empírico: em cada momento, o programa só precisa de uma pequena fração dos seus dados. A cache guarda essa fração numa memória pequena e rápida junto ao processador, e o programa corre quase à velocidade da memória rápida com a capacidade da memória lenta.

## Localidade

Os programas acedem à memória com dois padrões. A **localidade temporal** diz que um endereço acedido agora tem boa probabilidade de ser acedido outra vez em breve (contadores, variáveis de ciclo, o topo da pilha). A **localidade espacial** diz que os vizinhos de um endereço acedido também vão ser precisados (instruções seguidas, elementos seguidos de um vetor).

A cache explora ambas: guarda o dado acedido (temporal) e traz com ele um **bloco** inteiro de vizinhos, tipicamente 32 a 128 bytes (espacial). Quando o processador pede um endereço, a cache responde de imediato se o bloco já lá estiver (**hit**); se não estiver, vai buscar o bloco à memória seguinte (**miss**), paga a **penalidade de falta** e só depois continua.

![Hierarquia da memória: o CPU acede às caches L1 de instruções e de dados em cerca de 1 ciclo, à L2 em cerca de 10, à RAM em cerca de 100 e ao disco em milissegundos.](https://resumos.rgo.pt/cadeiras/ac/hierarquia-cache/figura-1.svg)

## Onde cabe cada bloco

Uma cache com $2^n$ conjuntos e blocos de $2^b$ bytes divide cada endereço em três campos: os $b$ bits baixos escolhem o byte dentro do bloco (**offset**), os $n$ bits seguintes escolhem o conjunto (**índice**) e os restantes identificam qual dos muitos blocos da memória ali cabe (**etiqueta**, _tag_).

Há três organizações, do mais rígido ao mais livre:

*   **Mapeamento direto**: cada bloco da memória cabe num único conjunto e cada conjunto guarda um só bloco. A etiqueta decide se o bloco presente é o pedido. É simples e rápido, mas dois blocos que calhem no mesmo conjunto expulsam-se um ao outro sem parar.
*   **Associativa por conjuntos** (_n-way_): cada conjunto guarda $n$ blocos e o bloco pode ocupar qualquer um deles. Compara-se a etiqueta com as $n$ em paralelo. É o compromisso que quase todos os processadores usam (tipicamente 4 a 8 vias).
*   **Totalmente associativa**: um só conjunto com todos os blocos; qualquer bloco cabe em qualquer posição. Só é viável em estruturas pequenas, como os _buffers_ de tradução de endereços.

Um exemplo de repartição. Cache de 8 KiB, blocos de 64 bytes, associativa de 4 vias: há $8192 / 64 = 128$ blocos no total, logo $128 / 4 = 32$ conjuntos. Com endereços de 32 bits: offset de 6 bits ($\log_2 64$), índice de 5 bits ($\log_2 32$) e etiqueta de $32 - 5 - 6 = 21$ bits. Vê como cada parâmetro se obtém por divisões e logaritmos, nunca de cor.

![Endereço de 32 bits repartido em etiqueta de 21 bits (31 a 11), índice de 5 bits (10 a 6) e offset de 6 bits (5 a 0).](https://resumos.rgo.pt/cadeiras/ac/hierarquia-cache/figura-2.svg)

## Os três Cs e o que fazer a cada um

As faltas dividem-se em três causas, os **três Cs**:

*   **Compulsórias** (_cold_): o primeiro acesso a cada bloco. Não há como as evitar com esta cache; só blocos maiores (mais vizinhos de cada vez) as reduzem, até certo ponto.
*   **De capacidade**: a cache é demasiado pequena para o conjunto de trabalho do programa. Aumentar a cache resolve-as.
*   **De conflito**: caberia na cache, mas calha sempre no conjunto ocupado por outro bloco. Mais associatividade (ou uma cache maior) resolve-as.

O diagnóstico manda na cura: se as faltas forem de conflito, duplicar a cache desperdiça área quando bastava passar de mapeamento direto para 2 vias. Em teste, classifica a falta antes de propor a solução.

Quando um bloco novo precisa de um lugar ocupado, a **política de substituição** escolhe a vítima. As opções habituais são a **aleatória** (escolhe ao acaso, barata e surpreendentemente decente), a **FIFO** (expulsa o bloco há mais tempo na cache) e a **LRU** (_least recently used_, expulsa o bloco há mais tempo sem ser acedido). A LRU pura é cara de implementar, por isso as caches reais usam aproximações com um ou dois bits por bloco. A política só importa nas faltas de conflito e de capacidade: nas compulsórias, qualquer vítima serve porque o bloco pedido nunca esteve lá.

## Políticas de escrita

Ler da cache é simples; escrever levanta duas decisões. Na escrita (_write hit_), o **write-through** escreve na cache e na memória seguinte ao mesmo tempo: simples, mas cada escrita paga o custo da memória lenta. O **write-back** escreve só na cache e marca o bloco como **sujo** (_dirty_); a escrita na memória fica adiada para a expulsão do bloco. É mais rápido, mas exige o bit de sujo e escritas de blocos inteiros na expulsão.

Na falta de escrita (_write miss_), o **write-allocate** traz o bloco para a cache como numa leitura, e o **no-write-allocate** escreve diretamente na memória sem trazer nada. A combinação habitual é write-back com write-allocate (aproveita a localidade das escritas) ou write-through com no-write-allocate (não polui a cache com dados que não vão ser lidos).

## Porque a memória principal é tão lenta: a DRAM

A penalidade de 100 ciclos do exemplo abaixo não é um número mágico: vem da anatomia da **DRAM**, a tecnologia da memória principal. Cada bit vive num condensador minúsculo que se descarrega sozinho e precisa de ser refrescado milhares de vezes por segundo. Os bits organizam-se em **linhas** (_rows_): para ler, o controlador abre uma linha inteira para uma fila de amplificadores (_row buffer_), lê as colunas pedidas em **rajada** (_burst_) e fecha a linha para a próxima.

Abrir uma linha custa dezenas de ciclos, e se a linha aberta não for a pedida paga-se fechar e abrir de novo. É por isso que acessos seguidos à mesma linha são rápidos e acessos saltados são lentos. Os chips dividem-se ainda em **bancos** independentes, para que uma leitura num banco se sobreponha à abertura de linha noutro. A cache esconde quase tudo isto; os 100 ciclos são o preço dos acessos que escapam.

## Quanto custa cada acesso: o AMAT

O **tempo médio de acesso** combina a velocidade dos hits com a frequência e o custo das faltas:

$$
\text{AMAT} = \text{tempo de hit} + \text{taxa de faltas} \times \text{penalidade de falta}
$$

Um exemplo. Cache com hit de 1 ciclo, taxa de faltas de 5% e penalidade de 100 ciclos:

$$
\text{AMAT} = 1 + 0{,}05 \times 100 = 6\ \text{ciclos}
$$

Confirma a conta e estende-a a dois níveis, com uma L2 de 10 ciclos de hit e 20% de faltas para a memória de 100 ciclos:

```python
hit_l1, falta_l1 = 1, 0.05
hit_l2, falta_l2, mem = 10, 0.2, 100
print(1 + falta_l1 * mem)
amat_l2 = hit_l2 + falta_l2 * mem
print(amat_l2)
print(hit_l1 + falta_l1 * amat_l2)
```

O programa imprime `6.0`, depois `30.0` (o AMAT da L2) e por fim `2.5`: a L2 corta o custo médio de 6 para 2,5 ciclos.

Repara: apesar de 95% dos acessos acertarem, o tempo médio é 6 vezes o tempo de hit, porque cada falta custa 100 vezes mais. Esta é a aritmética que justifica caches maiores, mais associativas e multinível: tudo o que baixe a taxa ou a penalidade paga-se depressa. Com dois níveis, aplica a fórmula em cascata: a penalidade da L1 é o AMAT da L2.

Para fechar o círculo com a página de [desempenho](https://resumos.rgo.pt/cadeiras/ac/hierarquia-cache/desempenho/): cada acesso à memória do programa custa em média AMAT ciclos, por isso o CPI efetivo cresce com a taxa de faltas. Uma otimização que corte as faltas a metade pode valer mais do que duplicar a frequência.

[Vídeo: Como a memória e as caches do CPU funcionam, Computerphile](https://www.youtube.com/watch?v=SAk-6gVkio0)

A miniatura vem do YouTube. O vídeo só carrega quando clicas. [Abrir no YouTube](https://www.youtube.com/watch?v=SAk-6gVkio0)

Como resolver um exercício de caches

Divide o endereço em etiqueta, índice e offset e confirma que a soma dos bits fecha. Depois pergunta: o bloco está na cache (hit)? Se não, que tipo de falta é (compulsória, capacidade, conflito)? Só então calcula tempos com o AMAT. Etiqueta primeiro, classificação depois, contas no fim.

## Para saber mais

*   [Simulador interativo de cache](https://eecs370.github.io/simulators/cache/): experimenta índice, etiqueta e faltas com os teus próprios acessos.