Políticas de cache e desempenho

O CPU escreve 7 no endereço 0 e volta a lê-lo. Se a cache conservar o valor novo, essa leitura pode acertar mesmo que a RAM ainda tenha o valor antigo. A política de escrita determina quando a modificação chega ao nível seguinte; a política de alocação determina o que fazer quando a escrita falha.

Write-through e write-back

Write-through (WT): uma escrita que acerta atualiza a cache e envia a escrita para o nível seguinte. Write-back (WB): altera a cache e marca a linha dirty; o nível seguinte pode ficar desatualizado até a linha ser descarregada.

Dirty não significa inválido. V=1,D=1 contém dados válidos e modificados. V=0 não é uma linha utilizável, mesmo que o bit D antigo seja 1.

O modelo WT/no-allocate não instala uma linha por uma escrita que falha. WB/allocate instala-a. São combinações frequentes, não uma equivalência lógica: política de escrita e de alocação são decisões distintas.

Operação	WT, no-allocate	WB, allocate
Leitura com acerto	Ler cache	Ler cache
Leitura com falta	Carregar linha; V=1	Descarregar vítima válida dirty, se houver; carregar linha; V=1,D=0
Escrita com acerto	Atualizar cache e nível seguinte	Atualizar cache; D=1
Escrita com falta	Escrever no nível seguinte; cache fica igual	Descarregar vítima válida dirty; instalar linha, alterar os bytes escritos; V=1,D=1

Em uma escrita parcial de uma linha, a alocação normalmente lê os bytes restantes do nível seguinte. No modelo adotado, se a escrita substitui a linha inteira, não é necessário lê-la antes. Por exemplo, uma cache com uma palavra por linha pode instalar uma escrita de palavra completa sem uma leitura adicional. Esta condição muda a contagem de acessos.

Um traço com vítimas modificadas

Uma falta com vítima dirty tem duas tarefas: conservar o bloco antigo e instalar o pedido. Segue cache e RAM lado a lado, pois uma leitura que acerta devolve o valor mais recente da cache. O traço usa cache direta WB com 2 linhas de 4 B, inicialmente inválida, e operações de palavra completa, com E a escrever e L a ler.

Operação	Índice, etiqueta	Eventos no nível seguinte	Estado relevante depois
E0=7	0,0	Nenhum; escrita cobre a linha	Linha 0: tag 0, V 1, D 1, valor 7
L0	0,0	Nenhum	Devolve 7
E8=9	0,1	Escrever vítima no endereço 0	Linha 0: tag 1, V 1, D 1, valor 9
L4	1,0	Ler linha que começa em 4	Linha 1: tag 0, V 1, D 0
L0	0,0	Escrever vítima no endereço 8 e ler linha 0	Linha 0: tag 0, V 1, D 0, valor 7

Total: duas leituras e duas escritas de linhas na memória principal. O último acesso devolve 7 porque a primeira vítima já tinha atualizado a memória.

O endereço de uma vítima é reconstruído com a etiqueta antiga, o índice da entrada e deslocamento zero. Usar a etiqueta do pedido escreveria os dados da vítima no sítio errado.

Aplica WT/no-allocate ao mesmo traço. E0 escreve na RAM sem instalar nada; L0 carrega a linha 0. E8 escreve na RAM e mantém na cache o bloco 0; L4 carrega a linha 4; a última L0 acerta.

Os totais coincidem, duas escritas e duas leituras, mas por causas diferentes:

Acesso final	WB: o que acontece	WT: o que acontece
L0 final	Falta; descarrega 9 e carrega 0	Acerto na linha guardada
E8	Sem tráfego; só marca dirty	Escrita direta na RAM

No traço WB, a leitura final falha e provoca dois acessos; em WT, acerta.

Para reconstruir a vítima no acesso L0, a etiqueta antiga é 1, o índice é 0 e cada linha tem 4 B: $(1\times2+0)\times4=8$. É nesse endereço que se descarrega 9 antes de ler 0.

O que se pode conhecer da memória

Uma linha WB válida e limpa permite conhecer os bytes correspondentes na memória principal, se nenhum agente externo os alterou. Uma linha válida dirty permite conhecer o valor que o processador lê, mas não o valor antigo na memória. Uma etiqueta diferente ou V=0 não prova nada sobre os dados desse endereço na memória.

Um buffer de escrita pode deixar o CPU continuar enquanto uma escrita WT avança. Se o exercício diz que não existe buffer, cobra a espera por escrita. Se existe, considera a capacidade e as condições de bloqueio fornecidas; não acrescentes sempre a latência inteira ao CPI.

Tempo médio de acesso

O modelo seguinte atende cada pedido antes do seguinte, sem sobrepor faltas. Para um nível, se a penalidade é o tempo adicional depois de verificar a falta:

$$TMAM=t_{\rm acerto}+m\,p_{\rm falta}.$$

Com acerto de 1 ns, taxa de falta 5% e penalidade 20 ns, o TMAM é 2 ns. Se os 20 ns já incluíssem a procura inicial, a conta teria de evitar contá-la duas vezes.

De taxas de falta para CPI

Este modelo soma ciclos de espera que não se sobrepõem e não estão já no CPI de base. Caches I e D separadas; uma obtenção de instrução por instrução e fração $r$ de instruções com um acesso a dados:

$$CPI=CPI_{\rm base}+m_Ip_I+r\,m_Dp_D.$$

Com base 1,2; $m_I=0,01$; $m_D=0,04$; $r=0,30$ e ambas as penalidades 80 ciclos:

$$CPI=1,2+0,01\times80+0,30\times0,04\times80=2,96.$$

Para uma cache unificada, o número médio de acessos é $1+r$: $CPI_{\rm prot}=(1+r)mp$. Instruções que realizem vários acessos exigem a sua contagem real. Penalidades dirty podem ser uma parcela adicional, ponderada pela frequência dessas vítimas.

Recuperar a mistura a partir das esperas

A equação também permite obter uma grandeza que não foi medida diretamente. Num CPU de 2 GHz, cada ciclo demora 0,5 ns, por isso uma falta que acrescenta 50 ns custa 100 ciclos.

Suponhamos uma cache unificada com taxa de falta 9% por acesso e 12 ciclos de espera por instrução. Cada instrução faz uma obtenção e, se for load/store, mais um acesso a dados.

Se $r$ é a fração de instruções que são loads/stores, com uma obtenção por instrução e no máximo um acesso a dados, as esperas são:

$$12=(1+r)\times0,09\times100.$$

Divide primeiro pela espera média de um acesso:

$$1+r=\frac{12}{9}=\frac43.$$

A obtenção obrigatória explica o primeiro acesso. Subtraí-la dá $r=1/3$, ou 33,33% de instruções com acesso a dados. Se fossem caches I/D separadas e os 12 ciclos contassem apenas dados, não haveria esse 1: o denominador e a equação seriam outros.

Neste modelo, $0\le r\le1$. Um resultado fora desse intervalo indica que os dados não cabem nas hipóteses: pode haver várias operações de memória por instrução, ou custos de escrita não incluídos. Também é necessário partir só da parcela de esperas. Usar o CPI total como se toda a execução fosse protelamento mistura grandezas diferentes.

Se a fonte dá uma razão entre acertos e faltas, transforma-a antes de calcular. Acertos nove vezes mais frequentes que faltas significam $h=9m$ e $h+m=1$, logo $m=1/10$. A taxa de falta não é $1/9$: essa razão tem acertos no denominador.

Vários níveis de cache

Uma falta em L1 consulta L2. Taxa local de L2 é a fração dessas consultas que falha. Taxa global de L2 é a fração de todos os pedidos originais que chega à memória. Se há um pedido por instrução, $m_{2,g}=m_1m_{2,l}$.

$$TMAM=t_1+m_1(t_2+m_{2,l}p_{\rm RAM}).$$

Exemplo: $t_1=1$ ciclo, $m_1=0,10$, $t_2=8$ ciclos, $m_{2,l}=0,20$, RAM 80 ciclos adicionais. O TMAM é $1+0,10(8+0,20\times80)=3,4$ ciclos. A taxa global que chega à RAM é 2%, não 20%.

Para CPI de CPU a 4 GHz, base 1, faltas L1 de 2% por instrução, consulta L2 de 5 ns e faltas RAM globais 0,5% com 100 ns adicionais: $p_2=20,p_R=400$ ciclos. Logo $CPI=1+0,02\times20+0,005\times400=3,4$. Sem L2 seria $1+0,02\times400=9$. A rapidez relativa é $9/3,4=2,647$, se $N$ e a frequência forem iguais.

Tráfego entre níveis com write-back

Uma falta em L1 e uma escrita na RAM são eventos diferentes. Em WB, uma escrita pode falhar para carregar uma linha e só enviar a modificação mais tarde, ao substituir a vítima. Saber a taxa de faltas não basta para contar descargas: é preciso saber quantas vítimas válidas estão dirty e se há flush final.

Segue duas escritas de palavra, E0=7 e E64=9, com estas hipóteses: L1 direta WB/allocate de uma linha de 16 B; L2 direta WT de quatro linhas de 16 B; ambas vazias. Escritas parciais em L1 leem a linha antes de a alterar. Cada descarga de L1 entrega a linha inteira a L2; L2 envia essa escrita inteira à RAM. Não há buffers nem flush final. A memória em ambos os endereços começa a zero.

Passo	Pedido	Efeito na RAM
1	E0 falha em L1; L1 pede a linha 0 a L2, que também falha	Leitura da linha 0
2	L1 modifica a palavra 0 para 7	Nenhum; L1 fica dirty
3	E64 falha em L1; a vítima 0 é descarregada para L2	L2 acerta e, por WT, escreve a linha 0 na RAM
4	L1 pede a linha 64; L2 falha e substitui a sua linha 0 limpa	Leitura da linha 64
5	L1 modifica a palavra 64 para 9	Nenhum; L1 fica dirty

São duas leituras e uma escrita de linha na RAM. A descarga da vítima atravessou L2 num acerto, mas gerou escrita porque L2 é WT. A RAM termina com 7 no endereço 0 e ainda 0 no endereço 64; o CPU lê 9 nesse último por acerto em L1. Um flush final acrescentaria outra escrita de linha na RAM, segundo as mesmas regras.

A taxa global $m_1m_{2,l}$ conta pedidos de leitura que faltam nos dois níveis, quando cada taxa usa o seu denominador. Não a apliques a todas as escritas WB. Para contar tráfego de escritas, segue separadamente carregamentos, descargas e a alocação de cada nível.