Hierarquia e caches

Um ciclo lê as palavras consecutivas de um vetor. Se cada acesso fosse até à DRAM, a memória principal poderia atrasar o processador dezenas de ciclos. A cache guarda blocos próximos do CPU, para que uma transferência sirva várias leituras.

Os registos e a SRAM, memória RAM estática, são rápidos mas caros por bit. A DRAM, memória RAM dinâmica, permite uma memória principal maior. Ambas são voláteis: perdem o conteúdo sem alimentação. O armazenamento conserva-o. A hierarquia combina estes níveis, transferindo blocos, também chamados linhas.

Localidade e organização

Localidade temporal: voltar a usar um dado recente. Localidade espacial: usar endereços próximos. Um ciclo percorre um vetor contíguo e pode reutilizar a linha que contém vários elementos.

Uma cache guarda dados, etiqueta e bit de validade. A etiqueta identifica o bloco da memória; validade distingue uma entrada utilizável de dados antigos sem significado. Uma cache write-back guarda também um bit dirty, explicado em Políticas de cache.

Organização	Onde pode entrar um bloco?	Escolha da vítima
Mapeamento direto	Uma única entrada	Determinada pelo índice
Associativa por conjuntos de $A$ vias	Qualquer via do seu conjunto	Necessária quando o conjunto está cheio
Totalmente associativa	Qualquer entrada	Necessária quando a cache está cheia

Um acesso acerta, ou é um hit, quando encontra uma entrada válida com a etiqueta pedida; caso contrário há uma falta, ou miss. Numa cache de $A$ vias comparam-se as $A$ etiquetas do conjunto selecionado, não as de todos os conjuntos.

O número de conjuntos é $S=C/(B A)$, com capacidade de dados $C$, bytes por bloco $B$ e associatividade $A$. Distingue conjunto, via e bloco da memória.

Decompor um endereço

Constrói primeiro por divisão inteira e só depois lê os bits. Para linha de 64 bytes e 32 conjuntos, com endereço $E$:

$$\text{bloco} = E // 64, \quad \text{offset} = E \bmod 64, \quad \text{índice} = \text{bloco} \bmod 32, \quad \text{etiqueta} = \text{bloco} // 32.$$

Para 0x12345678, bloco 0x48D159, offset 56, índice 25 e etiqueta 0x2468A. O início da linha é 0x12345640. Confere sempre que índice e offset cabem nos bits previstos antes de comparar etiquetas.

A divisão separa três decisões: o bloco determina que bytes transferir; o índice escolhe onde procurar; a etiqueta confirma se essa posição contém o bloco pedido.

Para endereços de $n$ bits, com $B=2^b$ bytes por bloco e $S=2^s$ conjuntos:

$$\underbrace{\text{etiqueta}}_{n-s-b}\quad\underbrace{\text{índice}}_s\quad\underbrace{\text{deslocamento}}_b.$$

As contas seguintes usam endereços de byte. Se um exercício fornece endereços de palavras de 4 B, converte primeiro para bytes, multiplicando por 4, ou expressa o tamanho da linha em palavras. Não mistures as duas unidades.

O deslocamento escolhe o byte dentro da linha, não uma linha. Para palavras de 4 bytes, os dois bits baixos escolhem um byte dentro da palavra; os restantes bits de deslocamento escolhem a palavra.

Uma cache direta de 2 KiB, com linhas de 64 B e endereços de 32 bits, tem 32 linhas, portanto 5 bits de índice, 6 de deslocamento e 21 de etiqueta.

No desenho, os 6 bits baixos escolhem o byte, os 5 seguintes escolhem uma das 32 linhas e os 21 restantes distinguem blocos que concorrem por essa linha. Para o endereço do exemplo, $(25\times64)+56=1656$ são os 11 bits baixos. A etiqueta recupera o resto:

$$E=(\mathtt{0x2468A}\times32+25)\times64+56=\mathtt{0x12345678}.$$

Esta reconstrução permite conferir a decomposição e, numa substituição, recuperar o endereço da linha antiga.

Seguir uma sequência de leituras

Modelo: cache direta, 4 linhas de 16 B, inicialmente inválida. Lê os endereços 0,4,64,0,16,20:

Acesso	Bloco da memória	Índice	Etiqueta	Resultado e alteração
0	0	0	0	Falta; carregar linha 0, etiqueta 0
4	0	0	0	Acerto; mesma linha
64	4	0	1	Falta; substituir linha 0 pela etiqueta 1
0	0	0	0	Falta; repor etiqueta 0 na linha 0
16	1	1	0	Falta; carregar linha 1
20	1	1	0	Acerto; mesma linha

São 4 leituras de blocos na memória principal e 2 acertos. Alterar só o deslocamento não provoca substituição.

Em uma cache de 2 vias com a mesma capacidade, há 2 conjuntos. Os blocos 0 e 4 continuam no mesmo conjunto, mas cabem simultaneamente, por isso a leitura posterior de 0 pode acertar. Maior associatividade permite evitar conflitos, mas não elimina faltas por capacidade nem garante melhor tempo de acesso.

Aumentar a linha também não garante melhoria. Com capacidade fixa, linhas maiores aproveitam vizinhos, mas deixam menos linhas disponíveis e transferem mais bytes em cada falta. Dados sem localidade espacial podem expulsar dados úteis sem compensar esse custo.

Substituição e tipos de falta

Segue um conjunto de 2 vias, inicialmente vazio, com a sequência A, B, A, C:

Acesso	LRU: menos para mais recente	FIFO: chegada mais antiga para mais nova
A	[A]	[A]
B	[A, B]	[A, B]
A	[B, A]	[A, B]
C	[A, C], expulsa B	[B, C], expulsa A

O acerto em A atualiza a recência LRU, mas não a chegada FIFO. As listas representam a ordem da política, não a posição física das vias.

LRU substitui o bloco usado há mais tempo. FIFO substitui o carregado há mais tempo; um acerto altera LRU, mas não a ordem de chegada FIFO. Usa primeiro uma via inválida. O estado da política faz parte do traço.

Uma falta é compulsória na primeira referência a um bloco: nenhum estado anterior da cache a evitaria. É de capacidade se ocorreria mesmo numa cache totalmente associativa de igual capacidade sob a política de referência. É de conflito se resulta apenas do mapeamento restrito. Esta classificação exige comparar modelos, não adivinhar a partir de um único endereço.

A escolha da vítima em uma falta compulsória pode mudar faltas futuras. Em caches partilhadas, invalidações acrescentam faltas por coerência.

Contar os bits físicos

Para 8 linhas diretas de 16 B e endereços 24 bits: $b=4,s=3,t=17$. Sem dirty ou outros metadados:

$$8\times(16\times8+17+1)=1168\ \text{bits}=146\ \text{bytes}.$$

A capacidade anunciada de dados é só 128 B. Para write-back, acrescenta 8 bits dirty; para uma política de substituição, considera também o seu estado, se pedido.

Endereços de uma matriz

Em C, uma matriz contígua em ordem por linhas A[R][K] tem endereço base + (iK+j)×tamanho. Variar j percorre dados adjacentes; variar i salta uma linha inteira. Trocar a ordem dos ciclos pode melhorar localidade, desde que conserve dependências e significado. Processar pequenos blocos de uma matriz permite reutilizar dados antes de os expulsar, mas o bloco deve caber no nível relevante da cache.

Considera A[8][8] de palavras de 4 B, base 0, e uma cache direta de duas linhas de 16 palavras. A palavra (i,j) tem número $8i+j$. O bloco é $(8i+j)//16$ e o índice é esse bloco módulo 2. A cache começa vazia em cada percurso.

Percurso	Primeiros números de palavra	Blocos correspondentes	Faltas em 64 leituras
Por linhas	0, 1, 2, …, 15, 16, …	16 referências a cada bloco, de 0 a 3	4
Por colunas	0, 8, 16, 24, 32, 40, 48, 56	0, 0, 1, 1, 2, 2, 3, 3	32

Por linhas, cada bloco carregado serve 16 leituras consecutivas. Por colunas, 2 expulsa 0 e 3 expulsa 1; a coluna seguinte volta aos blocos expulsos. Há quatro faltas por coluna, embora o programa leia as mesmas 64 palavras. A diferença está na ordem dos acessos.