Como as linhas de cache funcionam?

168

Entendo que o processador traz dados para o cache por meio de linhas de cache, que - por exemplo, no meu processador Atom - traz cerca de 64 bytes por vez, independentemente do tamanho dos dados reais que estão sendo lidos.

Minha pergunta é:

Imagine que você precise ler um byte da memória, quais 64 bytes serão trazidos para o cache?

As duas possibilidades que vejo são: os 64 bytes iniciam no limite mais próximo de 64 bytes abaixo do byte de interesse ou os 64 bytes estão espalhados ao redor do byte de alguma maneira predeterminada (por exemplo, metade abaixo, metade acima ou tudo acima).

Qual é?

Norswap
fonte
22
Leia isto: O que todo programador deve saber sobre memória . Então leia novamente. Melhor fonte (pdf) aqui .
andersoj

Respostas:

129

Se a linha de cache que contém o byte ou a palavra que você está carregando ainda não estiver presente, sua CPU solicitará os 64 bytes que começam no limite da linha de cache (o maior endereço abaixo do que você precisa é múltiplo de 64) .

Os modernos módulos de memória de PC transferem 64 bits (8 bytes) de cada vez, em uma explosão de oito transferências , de modo que um comando aciona uma leitura ou gravação de uma linha de cache completa da memória. (O tamanho da transferência de burst DDR1 / 2/3/4 SDRAM é configurável até 64B; as CPUs selecionam o tamanho da transferência de burst para corresponder ao tamanho da linha de cache, mas 64B é comum)

Como regra geral, se o processador não puder prever um acesso à memória (e pré-buscá-lo), o processo de recuperação poderá demorar ~ 90 nanossegundos ou ~ 250 ciclos de clock (da CPU sabendo o endereço até a CPU que está recebendo dados).

Por outro lado, um acerto no cache L1 tem uma latência de uso de carga de 3 ou 4 ciclos e um recarregamento de loja tem uma latência de encaminhamento de loja de 4 ou 5 ciclos nas modernas CPUs x86. As coisas são semelhantes em outras arquiteturas.

Leitura adicional: O que todo programador deve saber sobre memória, de Ulrich Drepper . O conselho sobre pré-busca de software está um pouco desatualizado: os pré-buscadores modernos de HW são mais inteligentes e o hyperthreading é muito melhor do que em dias P4 (portanto, um encadeamento de pré-busca é geralmente um desperdício). Também o O tag wiki possui muitos links de desempenho para essa arquitetura.

Eugene Smith
fonte
1
Esta resposta não faz absolutamente nenhum sentido. O que a largura de banda da memória de 64 bits (que também está errada a esse respeito) tem a ver com o byte de 64 bytes (!) Pouco a fazer? Além disso, os 10 a 30 ns também estão totalmente errados se você acertar o Carneiro. Pode ser verdade para o cache L3 ou L2, mas não para a RAM, onde é mais parecido com 90ns. O que você quer dizer é o tempo de explosão - o tempo para acessar o próximo quad-palavra no modo burst (que é realmente a resposta correta)
Martin Kersten
5
@MartinKersten: Um canal de SDRAM DDR1 / 2/3/4 usa uma largura de barramento de dados de 64 bits. Uma transferência intermitente de uma linha de cache inteira leva oito transferências de 8B cada e é o que realmente acontece. Ainda pode estar correto que o processo seja otimizado transferindo primeiro o bloco alinhado com 8B que contém o byte desejado, ou seja, iniciando o burst lá (e contornando se não foram os primeiros 8B do tamanho da transferência de burst). Porém, as CPUs modernas com caches de vários níveis provavelmente não fazem mais isso, porque isso significaria retransmitir o (s) primeiro (s) bloco (s) do burst até o cache L1 mais cedo.
Peter Cordes
2
Haswell tem um caminho de 64B entre o cache L2 e L1D (ou seja, uma largura total da linha de cache), portanto, a transferência do 8B que contém o byte solicitado tornaria o uso ineficiente desse barramento. O @Martin também está correto sobre o tempo de acesso a uma carga que precisa ir para a memória principal.
Peter Cordes
3
Boa pergunta sobre se os dados sobem na hierarquia de memória de uma só vez ou se L3 espera uma linha completa da memória antes de começar a enviá-la para L2. Existem buffers de transferência entre diferentes níveis de cache, e cada falta pendente reivindica um. Portanto, ( adivinhação total ) provavelmente o L3 coloca os bytes do controlador de memória em seu próprio buffer de recebimento ao mesmo tempo em que os coloca no buffer de carga apropriado para o cache L2 desejado. Quando a linha é totalmente transferida da memória, L3 notifica o L2 que a linha está pronta e copia-a em sua própria matriz.
Peter Cordes
2
@ Martin: Eu decidi ir em frente e editar esta resposta. Eu acho que é mais preciso agora, e ainda simples. Futuros leitores: ver também a pergunta de Mike76 e minha resposta: stackoverflow.com/questions/39182060/...
Peter Cordes
22

Se as linhas de cache tiverem 64 bytes de largura, elas corresponderão a blocos de memória que começam em endereços divisíveis por 64. Os 6 bits menos significativos de qualquer endereço são deslocados para a linha de cache.

Portanto, para qualquer byte, a linha de cache que deve ser buscada pode ser encontrada limpando os seis bits menos significativos do endereço, o que corresponde ao arredondamento para o endereço mais próximo divisível por 64.

Embora isso seja feito por hardware, podemos mostrar os cálculos usando algumas definições de macro C de referência:

#define CACHE_BLOCK_BITS 6
#define CACHE_BLOCK_SIZE (1U << CACHE_BLOCK_BITS)  /* 64 */
#define CACHE_BLOCK_MASK (CACHE_BLOCK_SIZE - 1)    /* 63, 0x3F */

/* Which byte offset in its cache block does this address reference? */
#define CACHE_BLOCK_OFFSET(ADDR) ((ADDR) & CACHE_BLOCK_MASK)

/* Address of 64 byte block brought into the cache when ADDR accessed */
#define CACHE_BLOCK_ALIGNED_ADDR(ADDR) ((ADDR) & ~CACHE_BLOCK_MASK)
Kaz
fonte
1
Eu tenho dificuldade para entender isso. Eu sei que é 2 anos depois, mas você pode me dar um exemplo de código para isso? uma ou duas linhas.
Nick
1
@ Nick A razão pela qual este método funciona está no sistema de números binários. Qualquer potência de 2 possui apenas um bit definido e todos os bits restantes são limpos; portanto, para 64, 0b1000000observe que os últimos 6 dígitos são zeros, portanto, mesmo quando você tiver algum número com qualquer um desses 6 (que representam número % 64), limpá-los fornecerá o endereço de memória alinhado de 64 bytes mais próximo.
precisa saber é o seguinte
21

Primeiro de tudo, o acesso à memória principal é muito caro. Atualmente, uma CPU de 2GHz (a mais lenta uma vez) possui ticks de 2G (ciclos) por segundo. Uma CPU (núcleo virtual hoje em dia) pode buscar um valor de seus registros uma vez por tick. Como um núcleo virtual consiste em várias unidades de processamento (ALU - unidade lógica aritmética, FPU etc.), ele pode realmente processar determinadas instruções em paralelo, se possível.

Um acesso à memória principal custa cerca de 70ns a 100ns (DDR4 é um pouco mais rápido). Dessa vez, é basicamente procurar o cache L1, L2 e L3 e depois bater na memória (comando send para o controlador de memória, que o envia para os bancos de memória), aguardar a resposta e pronto.

100ns significa cerca de 200 carrapatos. Então, basicamente, se um programa sempre perder os caches que cada memória acessa, a CPU gasta cerca de 99,5% de seu tempo (se apenas lê memória) ociosa aguardando a memória.

Para acelerar as coisas, existem os caches L1, L2, L3. Eles usam a memória sendo diretamente colocada no chip e usando um tipo diferente de circuitos de transistor para armazenar os bits fornecidos. Isso requer mais espaço, mais energia e é mais caro do que a memória principal, pois uma CPU geralmente é produzida usando uma tecnologia mais avançada e uma falha de produção na memória L1, L2, L3 tem a chance de tornar a CPU sem valor (defeito). caches grandes de L1, L2, L3 aumentam a taxa de erro que diminui o rendimento que diminui diretamente o ROI. Portanto, há uma grande troca quando se trata do tamanho do cache disponível.

(atualmente, cria-se mais caches L1, L2, L3 para poder desativar determinadas porções para diminuir a chance de um defeito de produção real ser a área de memória de cache que processa o defeito da CPU como um todo).

Para dar uma ideia de tempo (fonte: custos para acessar caches e memória )

  • Cache L1: 1ns a 2ns (2-4 ciclos)
  • Cache L2: 3ns a 5ns (6-10 ciclos)
  • Cache L3: 12ns a 20ns (24-40 ciclos)
  • RAM: 60ns (120 ciclos)

Como misturamos diferentes tipos de CPU, essas são apenas estimativas, mas dá uma boa idéia do que realmente está acontecendo quando um valor de memória é buscado e podemos ter um acerto ou um erro em determinada camada de cache.

Portanto, um cache basicamente acelera bastante o acesso à memória (60ns vs. 1ns).

Buscar um valor, armazená-lo no cache para a possibilidade de relê-lo é bom para variáveis ​​que são frequentemente acessadas, mas para operações de cópia em memória ainda seria lento, pois basta ler um valor, gravar o valor em algum lugar e nunca ler o valor novamente ... nenhum acerto no cache, lento (ao lado disso pode acontecer em paralelo, pois temos execução fora de ordem).

Essa cópia de memória é tão importante que existem diferentes meios para acelerá-la. Nos primeiros dias, a memória costumava copiar memória fora da CPU. Ele foi tratado diretamente pelo controlador de memória, portanto, uma operação de cópia de memória não poluiu os caches.

Mas, além de uma cópia simples da memória, outro acesso serial à memória era bastante comum. Um exemplo é analisar uma série de informações. Ter uma matriz de números inteiros e calcular a soma, média, média ou até mais simples encontrar um determinado valor (filtro / pesquisa) foi outra classe muito importante de algoritmos executados sempre em qualquer CPU de uso geral.

Portanto, analisando o padrão de acesso à memória, ficou claro que os dados são lidos sequencialmente com muita frequência. Havia uma alta probabilidade de que se um programa ler o valor no índice i, que o programa também leia o valor i + 1. Essa probabilidade é um pouco maior que a probabilidade de o mesmo programa também ler o valor i + 2 e assim por diante.

Portanto, dado um endereço de memória, foi (e ainda é) uma boa idéia para ler adiante e buscar valores adicionais. Esta é a razão pela qual existe um modo de impulso.

O acesso à memória no modo de aumento significa que um endereço é enviado e vários valores são enviados seqüencialmente. Cada envio de valor adicional leva apenas 10ns adicionais (ou mesmo abaixo).

Outro problema foi um endereço. Enviar um endereço leva tempo. Para endereçar uma grande parte da memória, é necessário enviar endereços grandes. Nos primeiros dias, isso significava que o barramento de endereços não era grande o suficiente para enviar o endereço em um único ciclo (tick) e era necessário mais de um ciclo para enviar o endereço, adicionando mais atraso.

Uma linha de cache de 64 bytes, por exemplo, significa que a memória é dividida em blocos distintos (sem sobreposição) de memória, com tamanho de 64 bytes. 64 bytes significa que o endereço inicial de cada bloco tem os seis bits de endereço mais baixos a serem sempre zeros. Portanto, não é necessário enviar esses seis bits zero a cada vez, aumentando o espaço de endereço 64 vezes para qualquer número de largura do barramento de endereços (efeito de boas-vindas).

Outro problema que a linha de cache resolve (além de ler adiante e salvar / liberar seis bits no barramento de endereços) está na maneira como o cache é organizado. Por exemplo, se um cache seria dividido em blocos (células) de 8 bytes (64 bits), é necessário armazenar o endereço da célula de memória para a qual essa célula de cache mantém o valor. Se o endereço também tiver 64 bits, isso significa que metade do tamanho do cache é consumida pelo endereço, resultando em uma sobrecarga de 100%.

Como uma linha de cache tem 64 bytes e uma CPU pode usar 64 bits - 6 bits = 58 bits (não há necessidade de armazenar os zero bits corretamente), podemos armazenar em cache 64 bytes ou 512 bits com uma sobrecarga de 58 bits (11% de sobrecarga). Na realidade, os endereços armazenados são ainda menores que isso, mas existem informações de status (como a linha de cache é válida e precisa, suja e precisa ser gravada novamente no ram etc.).

Outro aspecto é que temos cache associativo definido. Nem todas as células de cache conseguem armazenar um determinado endereço, mas apenas um subconjunto desses. Isso torna os bits de endereço armazenados necessários ainda menores, permite acesso paralelo ao cache (cada subconjunto pode ser acessado uma vez, mas independente dos outros subconjuntos).

Mais especificamente, quando se trata de sincronizar o acesso ao cache / memória entre os diferentes núcleos virtuais, suas múltiplas unidades de processamento independentes por núcleo e, finalmente, vários processadores em uma placa principal (na qual existem placas com até 48 processadores e mais).

Essa é basicamente a ideia atual de por que temos linhas de cache. O benefício de ler adiante é muito alto e o pior caso de ler um único byte de uma linha de cache e nunca ler o resto novamente é muito pequeno, pois a probabilidade é muito pequena.

O tamanho da linha de cache (64) é uma escolha acertada entre linhas de cache maiores, tornando improvável que o último byte seja lido também no futuro próximo, a duração necessária para buscar a linha de cache completa da memória (e para gravá-lo de volta) e também a sobrecarga na organização do cache e a paralelização do acesso ao cache e à memória.

Martin Kersten
fonte
1
Um cache associativo a conjunto usa alguns bits de endereço para selecionar um conjunto, para que as tags possam ser ainda mais curtas que o seu exemplo. Obviamente, o cache também precisa acompanhar qual tag combina com qual matriz de dados no conjunto, mas geralmente há mais conjuntos do que maneiras dentro de um conjunto. (por exemplo, cache L1D associativo de 32kB e 8 vias, com linhas de 64B, em CPUs Intel x86: deslocamento de 6 bits, índice de 6 bits. Os tags precisam ter apenas 48-12 bits de largura, porque x86-64 (por enquanto) possui apenas 48 bits). mordeu endereços físicos Como eu tenho certeza que você sabe, não é uma coincidência que a baixa de 12 bits é o deslocamento de página, de modo L1 pode ser VIPT sem aliasing)..
Peter Cordes
incrível resposta bud ... existe um botão "like" em algum lugar?
Edgard Lima
@EdgardLima, não o botão de votação?
Pacerier 10/07
6

Os processadores podem ter caches de vários níveis (L1, L2, L3) e diferem em tamanho e velocidade.

No entanto, para entender o que exatamente ocorre em cada cache, você terá que estudar o preditor de ramificação usado por esse processador específico e como as instruções / dados do seu programa se comportam contra ele.

Leia sobre o preditor de ramificação , o cache da CPU e as políticas de substituição .

Esta não é uma tarefa fácil. Se no final do dia tudo o que você deseja é um teste de desempenho, você pode usar uma ferramenta como o Cachegrind . No entanto, como se trata de uma simulação, seu resultado pode diferir em algum grau.

jweyrich
fonte
4

Não posso dizer com certeza que todo hardware é diferente, mas normalmente é "64 bytes começam no limite mais próximo de 64 bytes abaixo", pois essa é uma operação muito rápida e simples para a CPU.

borda
fonte
2
Eu posso dizer com certeza. Qualquer design de cache razoável terá linhas com tamanhos com uma potência de 2 e naturalmente alinhados. (por exemplo, alinhado a 64B). Não é apenas rápido e simples, é literalmente gratuito: você simplesmente ignora os baixos 6 bits do endereço, por exemplo. Os caches costumam fazer coisas diferentes com diferentes intervalos de endereços. (por exemplo, cerca de cuidados de cache tag e índice para a detecção de acerto vs falta, em seguida, usando apenas o deslocamento dentro de uma linha de cache para a inserção / extracção de dados)
Pedro Cordes