Hierarquia de memória e caches

Uma cache funciona porque o próximo acesso à memória muitas vezes está relacionado a um acesso recente. Durante um intervalo curto, a maioria dos programas usa apenas uma pequena parte de seu espaço de endereçamento. Esse padrão é a localidade. Uma cache mantém essa parte ativa próxima ao processador, onde pode atender rapidamente aos acessos.

Reutilização no tempo e no espaço

Localidade temporal significa reutilizar um item pouco depois de acessá-lo. Um laço busca repetidamente as instruções de seu corpo. Um total acumulado é lido e atualizado muitas vezes. Manter esses itens disponíveis evita buscá-los novamente em um nível mais lento.

Localidade espacial significa acessar itens em endereços próximos. Uma varredura de vetor lê elementos adjacentes, e código sequencial busca instruções sucessivas. Uma cache explora isso buscando um bloco inteiro, também chamado de linha de cache, em uma falta. Bytes próximos chegam antes de o programa solicitá-los.

Esses padrões podem ocorrer juntos. As instruções de um laço são adjacentes e executadas repetidamente, portanto o fluxo de instruções tem localidade espacial e temporal. Um elemento de vetor lido exatamente uma vez não tem reutilização temporal, embora a varredura do vetor ao redor tenha localidade espacial.

Conte blocos em uma varredura de vetor

Considere este laço em C com inteiros de 4 bytes e blocos de cache de 64 bytes:

for (int i = 0; i < 1000; i++) {
    sum += a[i];
}

Um bloco comporta $64\mathrm{/}4=16$ inteiros. O vetor ocupa $1000\times 4=4000$ bytes. Se seu primeiro elemento estiver alinhado ao início de um bloco, a varredura acessará $\lceil 4000\mathrm{/}64\rceil =63$ blocos: 62 blocos completos e um bloco parcial.

Em uma cache inicialmente vazia, sem pré-busca ou interferência, o primeiro acesso a cada bloco resulta em falta. Os elementos restantes desse bloco resultam em acerto. Assim, o vetor causa 63 faltas em 1000 acessos, ou cerca de 6,3%. Contar uma falta por elemento ignoraria todos os dados vizinhos úteis buscados em cada falta.

As variáveis do código-fonte sum e i são reutilizadas com frequência. No entanto, um compilador normalmente as mantém em registradores, de modo que sua reutilização no código-fonte não precisa gerar acessos à cache de dados. Analise os acessos à memória executados pelo programa compilado ao estimar o tráfego da cache.

O conjunto de trabalho deve caber e coexistir

O conjunto de trabalho é a coleção de blocos usados durante um intervalo de tempo escolhido. Se eles couberem na cache e as regras de posicionamento permitirem que coexistam, os acessos repetidos resultarão principalmente em acertos após os carregamentos iniciais. O intervalo de tempo importa: um programa inteiro pode ser enorme enquanto um laço ativo usa apenas alguns blocos.

A capacidade, por si só, não basta. Dois blocos muito usados podem ser mapeados para uma entrada de mapeamento direto e substituir um ao outro enquanto outras entradas permanecem vazias. Portanto, um conjunto de trabalho pode caber em número de bytes e ainda assim não permanecer na cache.

Nós dispersos de uma lista encadeada e consultas aleatórias em uma tabela hash grande frequentemente têm pouca localidade espacial. Um percurso por colunas em um vetor armazenado por linhas também salta muitos elementos próximos. Esses padrões trazem bytes que podem não ser usados antes da substituição. O hardware explora a localidade fornecida pelo padrão de acesso; alterar a organização ou a forma de percorrer os dados no programa pode tornar útil uma parte maior de cada bloco buscado.

As tecnologias de memória envolvem compromissos entre velocidade, densidade, custo e persistência. O processador precisa de acesso rápido a uma pequena quantidade de dados e de espaço acessível para uma quantidade muito maior. SRAM, DRAM e flash atendem a partes diferentes dessa necessidade.

Compare as células

Uma célula SRAM é rápida, mas ocupa uma área considerável, tornando a SRAM relativamente cara por bit. As células DRAM são menores, por isso a DRAM oferece mais capacidade a um custo menor por bit. Sua carga se dissipa. O refrescamento lê e restaura linhas dentro de um intervalo fixo; a DDR4 em temperatura normal usa um intervalo de 64 ms. “Estática” em SRAM significa ausência de refrescamento, não persistência após a perda de energia.

Por que o tempo de acesso à DRAM varia

A DRAM é organizada em bancos, com linhas e colunas em cada banco. Ativar uma linha copia seu conteúdo para um buffer de linha. Leituras e escritas selecionam então colunas dessa linha aberta. Para abrir outra linha no mesmo banco, ele precisa primeiro ser pré-carregado. Um acesso a uma linha já aberta evita esse trabalho de troca de linha.

Colunas consecutivas podem ser transferidas em uma rajada, adequada à busca de um bloco de cache. Distribuir requisições entre bancos e canais permite que as transferências se sobreponham. A memória DDR transfere dados nas duas bordas do clock. Esses recursos aumentam a taxa de entrega de dados sem eliminar a espera pelos primeiros dados.

Separe latência de largura de banda

Latência é o atraso até a chegada dos primeiros dados. Largura de banda é a quantidade transferida por unidade de tempo. Uma interface de alta largura de banda ainda pode ter um longo atraso inicial.

Por exemplo, um canal DDR5-4800 com um caminho de dados agregado de 64 bits transporta 8 bytes por transferência. Sua taxa de pico é $4800\times {10}^6\times 8=\mathrm{38,4}\times {10}^9$ bytes/s, ou 38,4 GB/s. A largura de banda sustentada pela aplicação pode ser menor porque comandos, mudanças de linha e outras tarefas consomem tempo.

Se uma requisição espera 60 ns e depois recebe um bloco de 64 bytes a 16 GB/s, a taxa de transferência é de 16 bytes/ns. A transferência leva $64\mathrm{/}16=4$ ns, totalizando cerca de 64 ns. Melhorar apenas a largura de banda reduz a parte de 4 ns, não os 60 ns iniciais.

A flash mantém dados, mas trata escritas de modo diferente

A flash NAND lê e programa páginas de vários KiB. Reutilizar uma página programada exige apagar seu bloco de apagamento maior, que contém muitas páginas. Leituras de página geralmente levam dezenas de microssegundos, a programação leva de centenas de microssegundos a alguns milissegundos, e o apagamento leva milissegundos.

Ciclos de programação e apagamento desgastam as células. A flash densa de vários bits geralmente suporta alguns milhares de ciclos, enquanto células de um bit podem suportar cerca de 100.000. Os controladores usam nivelamento de desgaste para distribuir as escritas pelos blocos.

Para dar uma ideia de escala, o acesso à SRAM leva aproximadamente 1 ns, à DRAM aproximadamente 50–100 ns, leituras de NAND aproximadamente 25–100 µs e o acesso a disco aproximadamente 5–10 ms. Os dispositivos reais variam. A hierarquia combina essas tecnologias porque uma única tecnologia não consegue reunir suas vantagens de velocidade, capacidade e preço.

A hierarquia de memória coloca armazenamento pequeno e rápido próximo ao processador e armazenamento progressivamente maior mais distante. A localidade permite que os níveis pequenos atendam a uma grande fração das requisições, enquanto os níveis inferiores fornecem capacidade.

Níveis e unidades de transferência

Um caminho típico é formado por registradores, L1, L2, L3, memória principal e armazenamento. A L1 geralmente tem caches separadas de instruções e dados de cerca de 32–64 KiB cada por núcleo. A L2 frequentemente tem de centenas de KiB a alguns MiB por núcleo, enquanto a L3 costuma ser compartilhada e conter de vários a dezenas de MiB. A memória principal contém muitos GiB, e o armazenamento contém centenas de GB ou mais. Os projetos diferem em tamanho e compartilhamento.

Em um processador próximo de 3 GHz, latências representativas de carga são de cerca de 4–5 ciclos para a L1, 12–15 para a L2, 30–50 para a L3 e 200–300 para a DRAM. Uma L1 pode aceitar uma nova requisição a cada ciclo mesmo quando uma requisição precisa de vários ciclos para terminar: vazão e latência descrevem propriedades diferentes.

Os dados trafegam pelas caches em blocos, geralmente de 64 bytes. A memória virtual usa páginas, geralmente de 4 KiB, ao mover o conteúdo das páginas entre a memória e o armazenamento. Uma linha de cache e uma página agrupam dados para fins semelhantes em escalas diferentes; não são a mesma unidade de transferência.

Acertos, faltas e tempos

Um acerto significa que um nível contém os dados solicitados. Uma falta significa que ele deve obter os dados de um nível inferior. Ambos os termos se referem ao nível verificado: uma falta na L1 ainda pode ser um acerto na L2.

A taxa de acertos é o número de acertos dividido pelo número de acessos, e a taxa de faltas é um menos a taxa de acertos. O tempo de acerto inclui a verificação do nível e a decisão sobre se a requisição acerta. A penalidade por falta é o tempo adicional necessário em uma falta para obter e entregar o bloco.

Suponha que uma cache simplificada tenha tempo de acerto de 1 ciclo, taxa de acertos de 97% e penalidade adicional por falta de 100 ciclos. Todo acesso paga 1 ciclo, enquanto 3% pagam outros 100:

Uma falta leva 101 ciclos neste exemplo. Usar 100 como o tempo completo da falta cobraria a consulta de acerto de maneira inconsistente. Mesmo uma taxa de acertos alta deixa faltas caras visíveis na média.

Quem gerencia cada nível?

O compilador atribui valores adequados aos registradores. O hardware da cache move blocos automaticamente durante cargas, armazenamentos e buscas de instruções. Os programas usam endereços; eles não selecionam entradas da cache. O sistema operacional gerencia os mapeamentos da memória virtual com suporte do hardware e trata as páginas que precisam ser trazidas para a memória principal.

Separar as instruções dos dados na L1 permite que um pipeline busque uma instrução e acesse dados simultaneamente, sem competir por uma única porta da cache. As caches inferiores geralmente são unificadas e armazenam blocos de instruções e de dados.

Algumas hierarquias são inclusivas: um bloco presente acima também tem uma cópia abaixo. Outras são exclusivas ou não inclusivas, portanto uma cópia em cada cache inferior não é garantida. Desenhe uma hierarquia como um caminho de busca e transferência, não como uma promessa de que todos os níveis contêm subconjuntos idênticos.

Aumentar a L1 pode reduzir faltas, mas aumentar o atraso de acesso e o consumo de energia. Acrescentar caches inferiores maiores permite manter a L1 rápida e atender a muitas de suas faltas antes da DRAM. Avalie esse compromisso pelo tempo de acesso, não apenas pela capacidade.

Um endereço de byte identifica um byte na memória. Uma cache busca um bloco inteiro, portanto a consulta primeiro identifica esse bloco e depois seleciona os bytes solicitados dentro dele. Em uma cache de mapeamento direto, cada bloco tem exatamente uma entrada possível.

Divida o endereço por função

Para um bloco de $2^b$ bytes, os $b$ bits menos significativos do endereço formam o deslocamento. Dividir o endereço do byte pelo tamanho do bloco e descartar o resto fornece o endereço do bloco. O resto é o deslocamento.

Se a cache tem $E$ entradas, o índice da entrada é

Quando o número de entradas é uma potência de dois, o índice é o grupo de bits do endereço imediatamente acima do deslocamento. Os bits mais significativos restantes formam a etiqueta, que informa à cache qual dos muitos blocos que compartilham um índice está presente.

A ordem dos campos, dos bits mais aos menos significativos, é etiqueta | índice | deslocamento. Para uma largura de endereço de $A$ bits:

Use o número de entradas para calcular o índice. Calcular o logaritmo da capacidade em bytes contaria os bits de deslocamento uma segunda vez.

Resolva um exemplo de 16 KiB

Uma cache de mapeamento direto de 16 KiB com blocos de 64 bytes tem $16384\mathrm{/}64=256$ entradas. O deslocamento ocupa 6 bits, o índice 8 bits e a etiqueta $32-8-6=18$ bits para endereços de 32 bits.

Para o endereço de byte 0x1234ABCD, os 6 bits menos significativos dão o deslocamento 13, ou 0x0D. Remover esses bits fornece o endereço de bloco 0x48D2AF. Seus 8 bits menos significativos são 0xAF, portanto o índice é 175. Os bits restantes fornecem a etiqueta 0x48D2.

O endereço do byte pode ser reconstruído a partir desses campos: concatene a etiqueta, o índice de 8 bits e o deslocamento de 6 bits. As larguras dos campos importam porque um dígito hexadecimal representa 4 bits; os limites não precisam ficar entre dígitos hexadecimais.

Uma etiqueta correspondente precisa de uma entrada válida

Cada entrada armazena dados, uma etiqueta e um bit de validade. O índice seleciona a entrada. Um acerto exige tanto um bit de validade definido quanto igualdade entre a etiqueta armazenada e a etiqueta solicitada. Na inicialização, uma entrada pode conter bits arbitrários; o bit de validade impede que esses bits sejam confundidos com um bloco carregado.

Quando o bloco está presente, acessos a outros bytes desse bloco também resultam em acerto. Um acerto não exige o mesmo endereço de byte usado para buscar o bloco.

Conte os metadados separadamente

A capacidade de cache informada normalmente conta apenas os dados. Aqui, cada entrada contém 512 bits de dados, 18 bits de etiqueta e 1 bit de validade, ou 531 bits. O armazenamento total é

Somente os dados usam 131.072 bits. Etiquetas e validade acrescentam 4.864 bits, cerca de 3,7% do armazenamento de dados. Um projeto com escrita de volta também precisa de bits de modificação; projetos mais complexos precisam de mais informações de controle.

O índice usa bits menos significativos do endereço do bloco para que blocos sucessivos se distribuam por entradas sucessivas. Um endereço mais largo mantém inalteradas as larguras do deslocamento e do índice quando a capacidade e o tamanho do bloco permanecem fixos; os bits adicionais ampliam a etiqueta.

Um rastro de acessos à cache registra como cada acesso altera os blocos armazenados. Mantenha um estado separado para cada entrada e atualize esse estado imediatamente após cada falta. A próxima requisição usa a cache atualizada, não a cache como estava no início.

Prepare o rastro

Considere uma cache de mapeamento direto de 64 bytes com quatro entradas de 16 bytes. Ela começa vazia. Para cada endereço de byte, divida por 16 para encontrar o bloco e depois calcule o bloco módulo 4 para obter o índice. A etiqueta é o número do bloco dividido por 4, com a parte fracionária descartada. Há 4 bits de deslocamento e 2 bits de índice.

Em uma leitura, examine a entrada selecionada. Se ela for válida e a etiqueta corresponder, registre um acerto. Caso contrário, registre uma falta, substitua o bloco e a etiqueta dessa entrada e defina seu bit de validade. Em uma cache de mapeamento direto, não há escolha de substituição.

Acompanhe todos os oito acessos

O primeiro acesso preenche a entrada 0 com o bloco 0. O endereço seguinte, 0x04, ainda está dentro desse bloco de 16 bytes, portanto resulta em acerto apesar de indicar um byte diferente. 0x40 pertence ao bloco 4. Ele tem o mesmo índice do bloco 0, mas uma etiqueta diferente, portanto substitui o bloco 0.

O segundo 0x00 resulta, portanto, em falta. O uso anterior, por si só, não garante um acerto: o bloco ainda precisa estar presente. A requisição a 0x14 carrega o bloco 1 na entrada 1, deixando a entrada 0 inalterada.

Em seguida, 0x44 carrega novamente o bloco 4 na entrada 0. 0x08 precisa do bloco 0 e substitui o bloco 4. Por fim, 0x84 carrega o bloco 8 nessa mesma entrada. Ao final, a entrada 0 contém o bloco 8 e a entrada 1 contém o bloco 1; as entradas 2 e 3 permanecem inválidas.

Interprete o comportamento

Há um acerto e sete faltas, portanto a taxa de acertos é $1\mathrm{/}8=\mathrm{12,5}\mathrm{\%}$. Os blocos 0, 4 e 8 competem pela entrada 0. A cache tem quatro entradas, mas esse padrão de acesso usa apenas duas delas. As substituições repetidas são causadas por conflitos de mapeamento, não por falta de armazenamento total para os quatro blocos distintos.

O carregamento de um bloco disponibiliza todos os seus bytes. Em uma varredura sequencial, uma falta pode, portanto, atender a muitos dos elementos seguintes. Aqui, os acessos conflitantes eliminam repetidamente esse benefício antes de o próximo byte próximo ser solicitado.

Para obter um rastro confiável, identifique explicitamente endereços de byte e números de bloco. Aplicar módulo 4 diretamente ao endereço do byte ignora a divisão pelo tamanho do bloco e envia requisições às entradas erradas. Registre a substituição mesmo quando o novo bloco já tiver sido carregado antes: toda falta instala o bloco solicitado e sua etiqueta na entrada selecionada.

Uma cache associativa por conjunto oferece a um bloco várias entradas possíveis sem precisar pesquisar toda a cache. O índice seleciona um conjunto, e o bloco pode ocupar qualquer via desse conjunto. Isso reduz conflitos entre blocos que compartilham um índice.

Calcule conjuntos e campos

Para capacidade de dados $C$, tamanho de bloco $B$ e associatividade $n$:

O índice do conjunto é o endereço do bloco módulo o número de conjuntos. O deslocamento continua dependendo apenas do tamanho do bloco. A etiqueta contém os bits mais significativos restantes.

Uma cache de 32 KiB e 8 vias com blocos de 64 bytes tem 512 blocos e 64 conjuntos. Com endereços de 32 bits, as larguras do deslocamento, do índice e da etiqueta são de 6, 6 e 20 bits. O endereço 0x1234ABCD tem deslocamento 13, conjunto 47 e etiqueta 0x1234A.

Com capacidade e tamanho de bloco fixos, dobrar a associatividade reduz o número de conjuntos à metade. Um bit de índice se torna um bit de etiqueta; nenhuma capacidade de dados é acrescentada.

A consulta compara a etiqueta em paralelo com todas as etiquetas válidas no conjunto escolhido. Uma via com etiqueta correspondente fornece os dados por um seletor. Mais vias exigem mais comparações e hardware de seleção, o que pode aumentar o tempo de acerto e o consumo de energia.

Substitua um bloco somente quando o conjunto estiver cheio

Use primeiro uma via inválida. Quando todas as vias estiverem ocupadas, a LRU, ou substituição do bloco menos recentemente usado, remove o bloco cujo acesso mais recente ocorreu há mais tempo. Atualize a informação de uso recente tanto em acertos quanto em carregamentos. Um conjunto de 2 vias precisa de apenas um bit para registrar sua via LRU; conjuntos maiores frequentemente usam aproximações pseudo-LRU.

A FIFO remove o bloco carregado primeiro, mesmo que ele tenha sido acessado recentemente. A substituição aleatória escolhe uma vítima sem manter todas as informações de uso recente. Ela é simples e pode ter desempenho próximo ao da LRU em caches grandes.

Retome o pequeno rastro com duas vias

A cache de 64 bytes com blocos de 16 bytes agora tem dois conjuntos de duas vias. Os blocos 0, 4 e 8 são mapeados para o conjunto 0, enquanto o bloco 1 é mapeado para o conjunto 1. Para 0x00, 0x04, 0x40, 0x00, 0x14, 0x44, 0x08, 0x84, os resultados são falta, acerto, falta, acerto, falta, acerto, acerto, falta.

Os blocos 0 e 4 podem coexistir, portanto seus acessos repetidos resultam em acerto. Pouco antes do último acesso, o bloco 0 foi usado mais recentemente que o bloco 4. Pela LRU, carregar o bloco 8 substitui o bloco 4. Quatro dos oito acessos resultam em acerto, em comparação com um na versão de mapeamento direto.

A associatividade não pode eliminar faltas compulsórias nem fazer caber um conjunto de trabalho maior que a capacidade. Ela também não pode impedir conflitos quando mais de n blocos muito usados competem por um conjunto de n vias. Um ciclo repetido de n+1 desses blocos pode fazer a LRU apresentar falta todas as vezes. Acrescentar preenchimento aos vetores pode mudar seus mapeamentos de conjunto; escolher mais vias é apenas uma possível resposta a um problema de conflito.

Uma falta na cache é um evento que tem tanto um mecanismo quanto uma causa. O mecanismo descreve como a requisição é atendida. A causa explica por que o bloco necessário estava ausente e qual mudança de projeto poderia ajudar.

Trate uma falta de leitura

Em um pipeline simples com execução em ordem, a cache detecta uma entrada inválida ou uma etiqueta diferente, e o processador para. A cache solicita o bloco ao próximo nível. Se a vítima escolhida estiver modificada, seus dados alterados devem ser preservados por meio da escrita de volta. O bloco recebido é instalado com sua etiqueta e seu bit de validade, e o acesso que aguardava é concluído. Uma falta na cache de instruções também espera pelo bloco da instrução e depois busca a instrução novamente.

A técnica de palavra crítica primeiro solicita primeiro a palavra necessária no bloco que está sendo transferido. O reinício antecipado permite que a execução recomece assim que essa palavra chega. Uma cache não bloqueante pode atender a outros acertos e acompanhar faltas pendentes enquanto um processador com execução fora de ordem realiza trabalho independente. Esses mecanismos reduzem a espera; eles não fazem desaparecer a dependência original dos dados.

Use os três Cs

Aplique primeiro o teste de primeiro acesso. O primeiro acesso a um bloco é compulsório mesmo que sua entrada de destino já esteja ocupada. Para faltas posteriores, compare a cache real com uma cache LRU totalmente associativa de mesma capacidade de dados e mesmo tamanho de bloco, ambas recebendo o mesmo histórico de acessos.

No rastro anterior com quatro entradas, os blocos 0, 4, 1 e 8 causam, cada um, uma falta compulsória. A cache de mapeamento direto também apresenta faltas nos acessos repetidos aos blocos 0 e 4. Uma cache totalmente associativa de quatro entradas consegue manter os quatro blocos distintos, portanto essas três faltas repetidas são de conflito. Não há faltas de capacidade.

Escolha uma mudança que trate a causa

Aumentar a capacidade pode manter um conjunto de trabalho maior. Aumentar a associatividade pode permitir que blocos conflitantes coexistam. Aumentar o tamanho do bloco pode explorar a localidade espacial ao trazer mais dados vizinhos úteis a cada carregamento.

O tamanho do bloco tem efeitos opostos. Com capacidade de dados fixa, blocos maiores significam menos blocos residentes. Bytes não usados consomem espaço na cache, blocos úteis não relacionados podem ser deslocados e cada transferência pode demorar mais. A taxa de faltas frequentemente cai no início à medida que o tamanho do bloco aumenta e depois sobe quando esses custos superam o benefício da localidade espacial.

Uma cache maior também pode ter uma consulta mais longa, e vias adicionais exigem mais hardware de comparação. Avalie as mudanças pelo tempo médio de acesso, incluindo o tempo de acerto e a penalidade por falta, em vez de supor que uma taxa de faltas menor garante um projeto mais rápido.

Em sistemas de múltiplos núcleos, a invalidação após a escrita de outro núcleo pode causar faltas de coerência. A pré-busca pode trazer um bloco de primeiro uso antes de seu acesso por demanda, ocultando uma falta por demanda que a capacidade adicional, por si só, não pode evitar.

Uma instrução de armazenamento altera um valor, portanto a hierarquia precisa de uma regra para transmitir essa mudança ao nível inferior. Há duas escolhas separadas: o que fazer quando uma escrita resulta em acerto e o que fazer quando resulta em falta.

Escrita direta e escrita de volta

Um bit de modificação registra que um bloco com escrita de volta contém alterações ainda não escritas no próximo nível. Uma vítima não modificada não precisa de escrita de volta. Os dados alterados de uma vítima modificada devem ser preservados antes que sua entrada possa ser reutilizada. As leituras do processador obtêm o novo valor da cache mesmo enquanto a cópia inferior está desatualizada.

Para 100 escritas em uma variável de 4 bytes armazenada na cache, a escrita direta sem agrupamento envia 100 escritas, ou 400 bytes de dados úteis. A escrita de volta pode combinar essas alterações em uma escrita de bloco de 64 bytes na substituição. Essa comparação conta os dados úteis das atualizações, excluindo o carregamento inicial e a sobrecarga de protocolo.

O benefício depende da reutilização. Escritas repetidas em um bloco dão à escrita de volta a oportunidade de combinar atualizações; escritas espalhadas por muitos blocos podem levar a muitas substituições de blocos modificados. Caches inferiores geralmente usam escrita de volta para limitar o tráfego em direção à DRAM. Caches L1 de dados podem usar qualquer uma das políticas.

Um buffer de escrita oculta a espera, não o tráfego

Um buffer de escrita enfileira escritas pendentes para o nível inferior. Com escrita direta, o processador pode continuar assim que uma escrita entra no buffer, em vez de esperar a memória inferior terminar. O nível inferior se atualiza à medida que as escritas no buffer são processadas; ele pode ficar temporariamente atrás do valor na cache.

O buffer tem capacidade finita. Se as escritas chegarem mais rápido do que o nível inferior consegue aceitá-las por tempo suficiente, ele enche e o processador para. Um buffer altera quando o processador espera, não a largura de banda sustentável do destino.

Sem buffer ou sobreposição, se 10% das instruções forem de armazenamento e cada uma acrescentar 100 ciclos de espera, um CPI básico de 1 passa a ser $1+\mathrm{0,1}\times 100=11$. O buffer pode ocultar grande parte desse atraso quando o destino acompanha o ritmo em média.

Trate uma falta de escrita separadamente

A alocação na escrita busca o bloco ausente para a cache e depois aplica a escrita. Ela combina naturalmente com a escrita de volta porque acessos e escritas posteriores podem reutilizar esse bloco. A política sem alocação na escrita, também chamada de write-around, envia a escrita ao nível inferior sem carregar o bloco nessa cache. Ela combina naturalmente com a escrita direta e pode evitar o deslocamento de blocos úteis durante uma sequência de saída usada uma única vez.

Essas são escolhas independentes de política. Saber que uma cache usa escrita direta não informa, por si só, se uma falta de escrita aloca uma linha; um rastro deve especificar as duas políticas.

Uma falta em uma cache com escrita de volta que seleciona uma vítima modificada envolve dados de saída além do carregamento de entrada, aumentando a penalidade, a menos que buffers ou sobreposição ocultem parte do trabalho. Outros núcleos e dispositivos de entrada e saída também precisam de uma visão consistente quando a memória inferior está desatualizada. A coerência e os mecanismos do sistema coordenam essa visibilidade; um bit de modificação apenas registra alterações pendentes.

Uma taxa de acertos alta é útil, mas não é uma medida completa de desempenho. Um pequeno número de faltas caras pode dominar a média, e um projeto que evita mais faltas ainda pode perder se sua consulta ficar lenta demais.

Comece com as definições de taxas e tempos

As duas frações somam um. Converta porcentagens em frações antes de multiplicar: 5% é 0,05.

O tempo médio de acesso à memória, ou AMAT, é

Toda requisição verifica a cache, inclusive as que resultam em falta. A penalidade é o atraso adicional após essa consulta. De modo equivalente, pondere o tempo de acerto pela fração de acertos e o tempo total de falta pela fração de faltas; desenvolver a expressão fornece a mesma fórmula.

Com tempo de acerto de 1 ciclo, 5% de faltas e penalidade adicional de 100 ciclos, o AMAT é $1+\mathrm{0,05}\times 100=6$ ciclos. A 2 GHz, cada ciclo dura 0,5 ns, portanto isso equivale a 3 ns. Faça toda a aritmética em ciclos ou toda em tempo e depois converta o resultado final, se necessário.

Compare projetos completos

A cache A tem consulta de 1,0 ns e 5% de faltas. A cache B tem consulta de 1,2 ns e 3,5% de faltas. Com penalidade de 50 ns:

B vence porque evitar faltas caras compensa mais do que a consulta mais lenta. Se a penalidade cair para 10 ns, A levará 1,5 ns e B levará 1,55 ns. Agora A vence. Uma melhoria na taxa de faltas tem valor proporcional à penalidade que evita.

Pondere corretamente os acessos a instruções e dados

Suponha que cada instrução produza uma busca de instrução e, em média, 0,3 acesso a dados. A taxa de faltas de instruções é de 2%, e a taxa de faltas de dados é de 4%. Em 100 instruções, há 100 buscas e 30 acessos a dados. As faltas esperadas são $100\times \mathrm{0,02}+30\times \mathrm{0,04}=\mathrm{3,2}$ em 130 acessos.

A fração combinada de faltas é, portanto, $\frac{\mathrm{0,02}+\mathrm{0,3}\times \mathrm{0,04}}{\mathrm{1,3}}\mathrm{.}$ Com tempos de acerto iguais de 1 ciclo e penalidades de 100 ciclos, o AMAT é de cerca de 3,46 ciclos por acesso à memória. Calcular diretamente a média de 2% e 4% daria erroneamente o mesmo peso aos dois tipos de acesso.

Estime uma penalidade de transferência

Uma requisição de bloco pode incluir a latência inicial seguida pelo tempo de transferência. Com latência de 60 ns, uma linha de cache de 64 bytes e largura de banda de 16 GB/s, a transferência leva 4 ns, resultando em uma penalidade adicional de cerca de 64 ns. A 3 GHz, há 3 ciclos/ns, portanto isso equivale a 192 ciclos.

Verifique o que os tempos de um problema incluem. Se ele fornecer o tempo completo de acesso com falta, subtraia a consulta de acerto antes de tratar esse número como uma penalidade adicional por falta. Cobrar a consulta duas vezes superestima o AMAT.

O AMAT mede o tempo por acesso à memória. O CPI mede os ciclos por instrução executada. Para relacioná-los, conte quantas requisições de instrução e de dados cada instrução produz e quantos ciclos de parada essas requisições acrescentam.

Some os termos de parada

Para um processador simples com execução em ordem cujos acertos na cache estão incluídos no CPI básico, uma falta sem sobreposição acrescenta sua penalidade adicional. Com taxa de faltas de instruções $m_I$, acessos a dados por instrução $f_D$, taxa de faltas de dados $m_D$ e penalidade $P$ em ciclos:

Nesse modelo, cada instrução tem uma requisição de busca de instrução. Apenas cargas e armazenamentos fazem requisições de dados, portanto multiplique sua taxa de faltas por sua frequência. Se suas penalidades forem diferentes, use uma penalidade separada em cada termo.

Passe das requisições às paradas

Considere CPI básico de 1,0, taxa de faltas de instruções de 2%, frequência de carga e armazenamento de 30%, taxa de faltas de dados de 4% e penalidade por falta de 100 ciclos. As paradas por instruções são $\mathrm{0,02}\times 100=\mathrm{2,0}$ ciclos por instrução. As paradas por dados são $\mathrm{0,3}\times \mathrm{0,04}\times 100=\mathrm{1,2}$. O CPI total é 4,2.

Com uma cache perfeita, o CPI voltaria a 1,0. Com o mesmo clock e a mesma contagem de instruções, isso representaria uma aceleração de 4,2 vezes. A taxa de faltas de dados é o dobro da taxa de faltas de instruções, mas as faltas de instruções custam mais tempo no total porque toda instrução é buscada e apenas 30% acessam dados.

Não insira o AMAT diretamente como CPI. O AMAT é por acesso e inclui o tempo de atendimento do acerto. O cálculo de CPI aqui acrescenta apenas as paradas além da execução básica já contabilizada.

Um clock mais rápido faz cada espera pela memória custar mais ciclos

A latência da DRAM em nanossegundos não diminui quando o clock do processador aumenta. Dobrar o clock converte a mesma espera de 100 ciclos pela memória em 200 ciclos no novo clock. O CPI do exemplo passa a ser

Cada novo ciclo tem metade da duração, portanto o tempo de execução relativo muda de 4,2 ciclos antigos por instrução para o equivalente a 3,7 ciclos antigos. A aceleração é $\mathrm{4,2}\mathrm{/}\mathrm{3,7}\approx \mathrm{1,14}$, muito abaixo de dois.

Melhorias deslocam o gargalo

Se o CPI básico cair de 1,0 para 0,5 enquanto as paradas de memória permanecerem em 3,2, o CPI total passará a ser 3,7. As paradas passam a consumir $\mathrm{3,2}\mathrm{/}\mathrm{3,7}\approx 86\mathrm{\%}$ dos ciclos. Melhorar o núcleo faz com que o atraso inalterado da memória represente uma parcela maior do tempo de execução, um exemplo da lei de Amdahl.

O modelo simples conta todos os atrasos de faltas como paradas. A execução fora de ordem e as caches não bloqueantes podem sobrepor faltas a trabalho útil ou a outras faltas. Contadores de hardware e medições de tempo de execução são necessários para avaliar essa sobreposição em uma máquina real. Ao comparar projetos com esse modelo, mantenha o mesmo fluxo de instruções e informe quais atrasos já estão incluídos no CPI básico.

Uma cache inferior reduz a penalidade paga quando há uma falta na L1. Ela tem seu próprio tempo de consulta e sua própria taxa de faltas, portanto o custo esperado da hierarquia deve acompanhar a fração de requisições que chega a cada nível.

Relacione a taxa ao seu denominador

A taxa local de faltas de um nível é seu número de faltas dividido pelas requisições a esse nível. Sua taxa global de faltas é seu número de faltas dividido por todas as requisições de memória do processador.

Se a L1 apresentar falta em 4% das vezes e a L2 apresentar falta em 25% dessas requisições, apenas $\mathrm{0,04}\times \mathrm{0,25}=\mathrm{0,01}$, ou 1% das requisições originais, chegarão à memória. Uma taxa local de faltas da L2 de 25% não informa, por si só, a fração de todas as requisições que chega à memória: a L1 filtrou o fluxo primeiro.

Para dois níveis verificados sequencialmente:

Aqui, $H_1$ e $H_2$ são tempos de consulta, $m_1$ e $m_2$ são frações locais de faltas, e $P$ é a penalidade adicional da memória. Apenas faltas na L1 pagam pela consulta à L2. Apenas faltas nos dois níveis pagam a penalidade da memória.

Avalie de dentro para fora

Use tempo de acerto da L1 de 1 ciclo, taxa de faltas da L1 de 4%, tempo de acerto da L2 de 12 ciclos, taxa local de faltas da L2 de 25% e penalidade da memória de 200 ciclos. Uma requisição que chega à L2 leva, em média, $12+\mathrm{0,25}\times 200=62$ ciclos adicionais. Assim,

Sem a L2, o AMAT seria $1+\mathrm{0,04}\times 200=9$ ciclos. A consulta à L2 acrescenta trabalho a cada falta na L1, mas impede que a maioria dessas requisições pague o atraso muito maior da memória.

Não substitua $m_2$ dentro dos parênteses pela taxa global de faltas da L2 de 1%. Isso multiplicaria pela fração de faltas da L1 duas vezes. Uma forma expandida equivalente usa diretamente a taxa global:

Acrescente a L3 usando a mesma lógica

Com tempo de acerto da L3 de 40 ciclos e taxa local de faltas de 40%, o termo de atendimento da L3 é $40+\mathrm{0,4}\times 200=120$ ciclos. O termo da L2 passa a ser $12+\mathrm{0,25}\times 120=42$ ciclos. O AMAT total é $1+\mathrm{0,04}\times 42=\mathrm{2,68}$ ciclos.

A expressão completa é $H_1+m_1(H_2+m_2(H_3+m_{3}P))\mathrm{.}$ A L3 é cobrada apenas das requisições que resultam em falta nos dois níveis superiores. Um nível com consulta muito lenta ou pouquíssimos acertos pode acrescentar mais atraso do que economiza.

Use taxas por instrução para o CPI

Suponha que o CPI básico seja 1, que a L1 produza 0,032 falta por instrução e que a memória acrescente 100 ciclos. Sem L2, o CPI é $1+\mathrm{0,032}\times 100=\mathrm{4,2}$. Acrescente uma L2 de 10 ciclos cuja taxa local de faltas seja de 25%:

Com o mesmo clock, a aceleração é $\mathrm{4,2}\mathrm{/}\mathrm{2,12}\approx \mathrm{1,98}$. O valor 0,032 já representa faltas por instrução, portanto outro multiplicador de frequência de acesso contaria essa frequência duas vezes.

A memória virtual separa os endereços usados por um programa das posições que contêm seus dados na memória principal. Cada processo recebe seu próprio espaço de endereçamento virtual. O hardware traduz endereços usando mapeamentos do sistema operacional e verifica se cada acesso solicitado é permitido.

Substitua o número da página e preserve o deslocamento

Uma página é uma região de tamanho fixo de endereços virtuais. Um quadro de página é uma posição do tamanho de uma página na memória física. Com páginas de 4 KiB, cada página contém 4096 bytes, portanto o deslocamento na página precisa de 12 bits. Os bits mais significativos restantes do endereço virtual formam o número da página virtual, ou VPN.

Uma entrada da tabela de páginas, ou PTE, mapeia um VPN para um número da página física, ou PPN. A tradução substitui o número da página, mas preserva o deslocamento: a mesma posição de byte é selecionada dentro do quadro físico.

Para o endereço virtual 0x00403A7C, os 12 bits menos significativos fornecem o deslocamento 0xA7C, e o VPN é 0x00403. Se esse VPN for mapeado para o PPN 0x02F1C, o endereço físico será 0x02F1CA7C. Acrescentar um deslocamento de 12 bits equivale a multiplicar o PPN por 4096 e somar o deslocamento; somar o PPN sem deslocá-lo produziria o endereço errado.

Um mapeamento inclui permissões

Uma PTE registra validade, um número de página física e permissões como leitura, escrita, execução e acesso de usuário. Bits de acesso e de modificação registram o uso e a alteração. Um registrador privilegiado do processador identifica a tabela de páginas; o RISC-V usa satp. Programas de usuário não podem reescrever livremente esses mapeamentos.

Tabelas de páginas separadas permitem que o mesmo endereço virtual se refira a dados físicos diferentes em processos diferentes. Elas também permitem compartilhamento selecionado: dois processos podem mapear páginas virtuais para o mesmo quadro físico, por exemplo, para compartilhar código de biblioteca somente de leitura. Isolamento e compartilhamento são ambos consequências de mapeamentos controlados.

Uma falta de página precisa da atenção do sistema operacional

Uma falta de página é uma exceção gerada quando a tradução ou suas verificações de permissão não podem ser concluídas normalmente. Uma escrita em um mapeamento somente de leitura pode causar uma falta mesmo que a página já esteja na memória.

Quando uma página necessária está ausente da memória principal, o sistema operacional obtém um quadro físico, lê a página do armazenamento, atualiza o mapeamento e reinicia a instrução. Uma página vítima modificada pode precisar primeiro de escrita de volta. Algumas faltas são resolvidas sem armazenamento, como ao estabelecer um mapeamento para uma página existente ou tratar cópia na escrita. Um acesso que o sistema não pode permitir pode, por sua vez, terminar em erro de processo.

Faltas que exigem acesso ao armazenamento são caras. A 3 GHz, um atraso de 50 µs custa 150.000 ciclos, e 1 ms custa 3.000.000. Páginas grandes distribuem os custos de transferência por muitos bytes. Uma página virtual pode ocupar qualquer quadro adequado, e páginas modificadas usam escrita de volta porque enviar cada escrita ao armazenamento seria lento demais.

Tabelas de páginas também consomem memória

Uma tabela plana para endereços virtuais de 32 bits e páginas de 4 KiB precisa de $2^{32-12}=2^{20}$ entradas. Com 4 bytes por entrada, isso equivale a 4 MiB por processo. Projetos reais usam tabelas multinível para evitar alocar uma tabela plana enorme para espaços de endereçamento esparsos; o RISC-V Sv39 usa três níveis.

A memória virtual inclui tradução de endereços, proteção e compartilhamento mesmo quando todas as páginas usadas cabem na DRAM. A paginação para o armazenamento é um uso desse mecanismo, não sua finalidade completa.

A tradução de endereços pode exigir várias leituras da tabela de páginas antes que um acesso a dados prossiga. Entradas da tabela de páginas podem resultar em acerto nas caches comuns, mas essas leituras ainda acrescentam trabalho. O buffer de tradução de endereços, ou TLB, armazena traduções usadas recentemente para que a maioria dos acessos possa evitar um percurso da tabela de páginas.

Acompanhe um acesso permitido

O número da página virtual é procurado na TLB. Uma entrada correspondente fornece o número da página física e informações de permissão. Após as verificações de permissão, o endereço físico identifica os dados na hierarquia de cache.

Em uma falta na TLB, um percurso da tabela de páginas obtém a tradução. Se o mapeamento for válido e permitir a requisição, a tradução será instalada na TLB e o acesso continuará. RISC-V e x86-64 normalmente usam mecanismos de percurso em hardware; algumas arquiteturas usam rotinas de software. Se o mapeamento não puder atender à requisição, o processador gerará uma falta de página para o sistema operacional.

Uma falta na TLB pode, portanto, acompanhar um acerto ou uma falta na cache de dados. Ela indica que a tradução estava ausente da TLB, não que a página estava ausente da DRAM. Por outro lado, um acerto na TLB pode acompanhar uma falta na cache ou uma falta de permissão para um acesso proibido. Tradução e presença dos dados respondem a perguntas diferentes.

Calcule a memória coberta pelas traduções

A cobertura da TLB é o número de entradas multiplicado pelo tamanho da página. Uma TLB de 64 entradas com páginas de 4 KiB cobre 256 KiB de uma vez. Com páginas de 2 MiB, 64 entradas cobrem 128 MiB. Acessar muitas páginas diferentes pode esgotar a capacidade de tradução mesmo quando apenas alguns bytes de cada página são usados.

TLBs de primeiro nível frequentemente contêm dezenas de entradas; níveis inferiores de TLB podem conter centenas ou milhares. Suas entradas incluem etiquetas de número de página, mapeamentos físicos, permissões e, muitas vezes, identificadores de espaço de endereçamento. A localidade dentro das páginas e a reutilização em acessos próximos mantêm altas as taxas de acertos de tradução.

Por exemplo, se 1% dos acessos exigirem um percurso de 30 ciclos e o tempo de acerto na TLB estiver oculto, os percursos acrescentarão, em média, $\mathrm{0,01}\times 30=\mathrm{0,3}$ ciclos por acesso. Esse exemplo supõe que os percursos sejam concluídos normalmente e exclui o atendimento a faltas de página.

Sobreponha a indexação à tradução

Uma cache com índice físico e etiqueta física espera por um endereço físico antes de selecionar seu conjunto. Uma cache com índice virtual e etiqueta física, ou cache VIPT, começa a ler um conjunto enquanto a TLB traduz e depois compara as etiquetas físicas.

O projeto VIPT simples obtém todos os bits de índice e de deslocamento no bloco do deslocamento na página, pois a tradução preserva esses bits. Isso exige

Com páginas de 4 KiB, uma cache de 32 KiB e 8 vias tem 4 KiB por via e atende à condição. Uma cache de 48 KiB e 12 vias também atende. Uma cache de 64 KiB e 8 vias tem 8 KiB por via e precisa de um bit do número da página para indexação, portanto exige mais vias ou tratamento adicional.

Mantenha atualizados os mapeamentos armazenados

As traduções pertencem a espaços de endereçamento. Uma troca de contexto pode esvaziar entradas antigas ou distingui-las com identificadores de espaço de endereçamento, ou ASIDs. Mudanças nos mapeamentos exigem a manutenção correspondente da cache de traduções; o RISC-V fornece sfence.vma. Quando uma página é removida da memória, sua tradução antiga não deve continuar utilizável na TLB. A TLB contém mapeamentos e direitos de acesso, enquanto caches comuns contêm os dados e as instruções do programa.

Código que considera o funcionamento da cache aproveita os bytes buscados antes que seu bloco seja substituído. Comece pelos endereços gerados pelo laço interno. Depois, pergunte quais dados são reutilizados, qual é a distância entre os acessos e se esses blocos podem coexistir na cache.

Percorra vetores na ordem de armazenamento

C e C++ armazenam vetores retangulares por linhas. Colunas adjacentes de uma linha são adjacentes na memória. Fortran, MATLAB e Julia usam armazenamento por colunas; vetores NumPy usam armazenamento por linhas por padrão. O percurso interno eficiente segue a organização real dos dados.

Um vetor em C double a[1024][1024] ocupa 8 MiB. Cada linha da matriz ocupa 8.192 bytes. Com linhas de cache de 64 bytes, cada uma comporta oito valores double. Um percurso por linhas pode usar todos os oito antes de avançar, resultando em aproximadamente uma falta de início a frio a cada oito acessos em um modelo simples de busca por demanda.

Um percurso por colunas avança 8.192 bytes entre acessos consecutivos. Ele acessa 1.024 linhas de cache distintas antes de voltar a dados próximos na coluna seguinte. Essas linhas ocupam 64 KiB, ultrapassando uma L1 de 32 KiB. Elas também entram em conflito: em uma cache de 64 conjuntos, um passo de 128 linhas de cache preserva o índice do conjunto. Um conjunto de 8 vias não consegue conter 1.024 linhas concorrentes.

Acrescentar preenchimento a uma linha da matriz até ela ter 1.032 valores double faz seu passo chegar a 8.256 bytes, ou 129 linhas de cache. Linhas sucessivas da matriz avançam então um conjunto módulo 64, distribuindo as requisições. O preenchimento trata conflitos de mapeamento; a quantidade de dados continua importando.

Intercambie laços quando o resultado for preservado

O intercâmbio de laços muda qual laço é executado dentro de outro. Para multiplicação de matrizes armazenadas por linhas, a ordem i, j, k percorre uma linha de A, mas uma coluna de B. Em um modelo de varredura de dados grandes com pouca reutilização entre passagens, isso custa cerca de $1\mathrm{/}8+1=\mathrm{1,125}$ falta por iteração interna.

Com i, k, j, o laço interno percorre linhas de B e C, enquanto um elemento de A é reutilizado. Contar uma nova sequência para ambas as linhas resulta em cerca de $1\mathrm{/}8+1\mathrm{/}8=\mathrm{0,25}$ falta por iteração, 4,5 vezes menos. Se a linha de C atualizada repetidamente permanecer na cache, a contagem se aproximará de 0,125. A capacidade da cache e os conflitos determinam qual reutilização é preservada.

O intercâmbio deve preservar o comportamento exigido da computação. Dependências, ponteiros sobrepostos e ordem de avaliação de ponto flutuante podem restringir transformações; compiladores precisam de prova de que uma mudança é permitida.

Busque os campos que você usa

Um vetor de estruturas agrupa todos os campos de um objeto. Uma estrutura de vetores agrupa um campo ao longo dos objetos. Se um registro de partícula contiver oito valores double em uma linha de cache de 64 bytes, somar apenas x em um milhão de registros alinhados buscará cerca de 64 MB. Um vetor x contíguo e separado buscará cerca de 8 MB, usando cada valor double trazido. Código que usa todos os campos de cada partícula juntos pode favorecer a organização original em estruturas.

Nós encadeados podem estar espalhados, e cada próximo endereço pode depender de um ponteiro recém-carregado. Vetores contíguos ou áreas de alocação de nós podem melhorar a localidade. Campos compactos usados com frequência também permitem que mais dados ativos caibam em cada nível.

Meça o tempo de execução e os contadores de hardware relevantes antes e depois de uma mudança. Faltas na cache podem explicar um laço lento, mas computação, largura de banda ou desvios podem ser o fator limitante. Mantenha comparáveis a entrada e os resultados para que uma diferença de velocidade reflita a mudança avaliada.

O intercâmbio de laços melhora a ordem de acesso. A blocagem, também chamada de tiling, vai além ao manter uma pequena região de dados ativa até que sua reutilização útil termine. A pré-busca antecipa uma transferência futura para que seu atraso se sobreponha a trabalho útil.

Mantenha um grupo de blocos residente

Na multiplicação com blocagem de matrizes quadradas, um bloco de A e um bloco de B contribuem para um bloco de C. Um bloco de lado $b$ contém $b^2$ elementos. Trabalhar repetidamente nesses blocos pequenos reutiliza dados antes de passar à próxima região.

Para valores double de 8 bytes, três blocos exigem $3b^2\times 8=24b^2$ bytes. Em uma cache de 32 KiB, o limite de capacidade é

Escolher um lado de 32 usa 24.576 bytes, ou 24 KiB, deixando algum espaço para outros dados. Escolher 36 apenas porque a aritmética permite deixa muito menos espaço e pode provocar conflitos. A capacidade é uma estimativa inicial; os tamanhos reais dos blocos são ajustados por medição.

Um percurso com blocagem avança o laço externo pelo tamanho do bloco. Seus limites internos param no menor valor entre o fim do bloco e o tamanho da matriz. Por exemplo, se uma dimensão for 70 e os blocos tiverem lado 32, o bloco final terá apenas seis elementos nessa dimensão. Um bloco final de tamanho completo acessaria posições além do vetor.

Estime o que a reutilização economiza

Em um modelo simplificado de matrizes grandes com linhas de cache de 64 bytes, a ordem ingênua i, j, k apresenta cerca de $\mathrm{1,125}{N}^3$ faltas quando as linhas percorridas já não estão na cache na passagem seguinte. Uma versão com blocagem pode reduzir isso para cerca de $N^3\mathrm{/}(4b)$, supondo que os três blocos de trabalho permaneçam na cache e ignorando conflitos.

Para $N=1024$ e $b=32$, essas estimativas são de cerca de 1,2 bilhão e 8,4 milhões de faltas, um fator de 144. Ambas as versões ainda realizam cerca de $2N^3$ operações de ponto flutuante. A economia está na movimentação repetida de dados, não na contagem de operações aritméticas da multiplicação. O modelo descreve uma reutilização ideal; a aceleração medida também depende da largura de banda, da execução e de outras sobrecargas.

Faça a pré-busca cedo o suficiente para ocultar a latência

Mecanismos de pré-busca em hardware reconhecem sequências como acessos sequenciais ou com passo constante. Eles solicitam linhas antes que acessos por demanda precisem delas. O software também pode solicitar buscas antecipadas, por exemplo, com __builtin_prefetch do GCC ou do Clang.

O momento importa. Uma requisição feita tarde demais deixa o acesso por demanda esperando. Uma requisição feita cedo demais pode trazer uma linha apenas para que ela seja substituída antes do uso. Uma requisição imprecisa consome largura de banda e espaço na cache sem ajudar o programa. O seguimento de ponteiros é mais difícil de antecipar porque o próximo endereço muitas vezes só é conhecido após a chegada do nó atual.

Uma pré-busca feita no momento certo pode transformar faltas posteriores por demanda em acertos, mas as linhas ainda trafegam pela hierarquia. Ela oculta a latência em vez de reduzir os dados úteis necessários a uma passagem sequencial. A blocagem ajuda quando valores são reutilizados; uma passagem única não tem dados repetidos a manter e já pode ser limitada pela largura de banda da memória.