Cache da CPU

O cache da CPU é o cache usado pela CPU de um computador para reduzir o tempo médio de acesso à memória . É um tipo de memória pequeno, mas muito rápido, que mantém cópias dos dados acessados ​​com mais frequência na memória principal . Isso faz parte do processador e está localizado muito próximo a ele. Ele não pode ser visualizado pelo software , mas é controlado e gerenciado pelo hardware . Isso está incluído em Smartphones e Tablets e pode ser visto diretamente no software.

Características

Comparação entre memória RAM e memória cache da CPU

O diagrama à esquerda mostra duas memórias, a principal e a cache. Cada local de memória cache contém dados (uma linha de cache ), que entre os diferentes tipos de cache varia entre 512 bytes e 8 MB . Cada local de memória possui um índice, que é um identificador exclusivo usado para se referir a esse local específico. O índice de um local na memória principal é chamado de endereço de memória. Cada local de cache também possui uma tag que contém o índice de memória principal dos dados carregados lá. Em caches de dados, esses valores são chamados de blocos de cache ou linhas de cache. Desde que a maioria dos acessos à memória seja para dados em cache, a latência média de acesso à memória será mais próxima da latência de cache do que a memória principal, portanto, o desempenho será melhor.

Quando o processador precisa ler ou escrever em um determinado local da memória principal, ele inicialmente verifica se o conteúdo desse local está carregado no cache. Isso é feito comparando o endereço do local de memória com quaisquer rótulos no cache que possam conter dados nesse endereço. Se o processador descobrir que a localização da memória está no cache, isso é chamado de acerto de cache, caso contrário, falta de cache. No caso de um acerto de cache, o processador imediatamente lê ou grava os dados na linha de cache. A proporção de acertos de cache para acertos totais também é chamada de taxa de acerto e é uma medida indireta da eficácia do algoritmo de cache.

No caso de um cache miss, segue-se (para a maioria dos caches) a criação de uma nova entidade, que inclui o rótulo que acabou de ser solicitado pelo processador e uma cópia dos dados na memória principal. Essa falha é relativamente lenta, pois exige a transferência dos dados da memória principal, em alguns casos após a exclusão dos dados que não são mais válidos.

É por isso que um cache muito grande, mesmo se gerenciado com um algoritmo eficiente, pode ser contraproducente em termos de desempenho em algumas circunstâncias. Na verdade, o processo de excluir dados expirados e inválidos no cache e carregar os dados corretos no cache normalmente demora mais do que quando a CPU lê os dados diretamente da memória principal sem usar o cache. Em outras palavras, um cache grande pode levar, em situações computacionais específicas, por exemplo, não iterativas, a um número maior de erros de cache do que de acertos de cache, com uma degradação significativa do desempenho.

Alguns detalhes operacionais

Para abrir espaço para novos dados no caso de um cache miss , o cache geralmente precisa excluir o conteúdo de uma das linhas. A heurística que ele usa para escolher quais dados excluir é chamada de política de substituição. O problema fundamental com qualquer política de substituição é ter que prever os dados de cache que terão menos probabilidade de serem solicitados no futuro.

Prever o futuro é difícil, especialmente para caches de hardware que precisam explorar regras que podem ser facilmente implementadas nos circuitos, então há uma série de políticas de substituição e nenhuma delas pode ser considerada perfeita. Um dos mais populares, o LRU (do inglês Least Recentemente Used , que é usado menos recentemente ), substitui, de fato, os dados acessados ​​menos recentemente.

Quando os dados são gravados no cache, eles ainda devem ser gravados na memória principal após algum tempo . A decisão de quando essa redação deve ocorrer é controlada pela política de redação. Em um cache write-through , cada gravação no cache resulta em uma gravação simultânea na memória principal. Alternativamente, um cache de write-back não executa esta ação imediatamente: pelo contrário, o cache mantém o controle das linhas que contêm dados a serem atualizados definindo adequadamente o que é chamado de bit sujo . Na verdade, os dados são gravados na memória apenas quando precisam ser limpos do cache para liberar espaço para novas informações. Por esse motivo, uma pesquisa com falha em um cache de write-back geralmente gera dois acessos à memória: um para ler os novos dados e outro para gravar as informações antigas (se indicado pelo bit sujo). Tanto o write-back quanto o write-through servem para manter a consistência entre os níveis de memória.

Existem também algumas políticas intermediárias. Por exemplo, o cache pode ser write-through, mas as gravações podem ser enfileiradas temporariamente, de modo a processar várias gravações juntas, otimizando o acesso ao barramento .

Os dados na memória principal, dos quais existe uma cópia no cache, podem ser modificados por outras causas (evento não improvável, por exemplo, em um sistema multiprocessador ), portanto os dados no cache podem se tornar obsoletos. Os protocolos de comunicação entre os sistemas de gerenciamento de cache que mantêm a consistência dos dados são chamados de protocolos de consistência.

O tempo gasto para ler os dados da memória (latência de leitura) é importante, porque muitas vezes uma CPU pode completar sua fila de operações enquanto espera a chegada dos dados solicitados. Quando um microprocessador atinge esse estado, é chamado de parada da CPU. À medida que os microprocessadores aceleram, a perda de cache desperdiça muito poder de computação; CPUs modernas, de fato, podem executar centenas de instruções no mesmo tempo que leva para carregar um único dado da memória. Portanto, várias técnicas foram estudadas para "manter a CPU ocupada" durante esta fase. Alguns microprocessadores, como o Pentium Pro , tentam realizar as operações que seguem aquele que está aguardando os dados, se independentes dele (por isso são chamados de fora de ordem em inglês ). O Pentium 4 usa multithreading simultâneo (chamado HyperThreading na terminologia Intel ), que permite que outro programa use a CPU enquanto um primeiro programa espera que os dados cheguem da memória principal.

Associatividade

Quais locais de memória podem ser carregados em quais locais de cache

A política de substituição decide onde no cache uma cópia de um local de memória específico pode residir. Se a política de substituição for livre para escolher em qual linha de cache carregar os dados, o cache é chamado de totalmente associativo (ou mesmo totalmente associativo). Por outro lado, se algum dado na memória só puder ser colocado em uma linha de cache específica, ele é chamado de mapeamento direto (ou mesmo mapeamento direto). A maioria dos caches, no entanto, implementa um trade-off chamado conjunto associativo (ou mesmo parcialmente associativo). Por exemplo, o cache de dados de nível 1 do AMD Athlon é associativo de conjunto de 2 vias , ou seja, um local de memória específico pode ser armazenado em cache em dois locais distintos no cache de dados de nível 1.

Se cada local na memória principal pode ser carregado em dois locais diferentes, surge a pergunta: quais? O esquema usado com mais frequência é mostrado no diagrama ao lado: os bits menos significativos do índice de localização de memória são usados ​​como índices para o cache e duas linhas de cache são associadas a cada um desses índices. Uma boa propriedade deste esquema é que os rótulos dos dados carregados no cache não devem incluir aquela parte do índice já codificada pela linha de cache escolhida. Como as tags são expressas em menos bits, elas ocupam menos memória e o tempo para processá-las é menor.

Outros esquemas foram sugeridos, como o skewed cache , onde o índice do caminho 0 é direto, como acima, enquanto o índice do caminho 1 é calculado por meio de uma função hash. Uma boa função hash tem a propriedade de que os endereços que entram em conflito com o mapeamento direto tendem a não colidir quando mapeados para a função hash, portanto, é menos provável que um programa sofra um número imprevisivelmente grande de colisões devido a uma função hash. método particularmente patológico de Acesso. A desvantagem é o atraso adicional necessário para calcular o resultado da função hash. Além disso, quando for necessário carregar uma nova linha e excluir uma antiga, pode ser difícil determinar qual das linhas existentes foi usada menos recentemente, pois a nova linha entra em conflito com diferentes "conjuntos" de linhas para cada " caminho"; na verdade, o traçado LRU é normalmente calculado para cada conjunto de linhas.

A associatividade é um compromisso. Se houver dez posições, a política de substituição pode preencher uma nova linha, mas ao procurar um dado, todas as 10 posições devem ser verificadas. Controlar várias posições requer mais poder, área e tempo. Por outro lado, caches com mais associatividade sofrem menos erros de cache (veja também abaixo). A regra geral é que duplicar a associatividade tem aproximadamente o mesmo efeito na taxa de acertos que dobrar o tamanho do cache, de 1 via ( mapeamento direto ) para 4 vias. Aumentos na associatividade além do 4-way têm muito menos efeito na taxa de acerto e geralmente são usados ​​por outros motivos (veja alias virtual, abaixo).

Uma das vantagens do cache mapeado direto é que ele permite uma execução especulativa rápida e fácil . Uma vez calculado o endereço, sabe-se qual linha de cache pode conter os dados. Isso pode ser lido e o processador pode continuar trabalhando com esses dados antes de terminar de verificar se o rótulo realmente corresponde ao endereço solicitado.

A ideia de que o processador usa os dados no cache antes mesmo de verificar a correspondência entre o rótulo e o endereço também pode ser aplicada aos caches associativos. Um subconjunto do rótulo, chamado de dica em inglês , pode ser usado para escolher temporariamente uma das linhas de cache associadas ao endereço solicitado. Esses dados podem ser usados ​​pela CPU em paralelo, enquanto o rótulo é totalmente verificado. Essa técnica funciona melhor quando usada no contexto de tradução de endereços, conforme explicado abaixo.

Perda de cache

Cache miss refere-se a uma tentativa malsucedida de ler ou gravar um dado no cache, o que resulta em uma latência muito maior no acesso à memória principal. Para uma falha na leitura do cache de instruções, o processador deve esperar ( stall ) até que a instrução seja carregada da memória principal. Uma falha de cache causada pelo carregamento de dados pode ser menos dolorosa, pois outras instruções não relacionadas a ele ainda podem ser executadas, desde que a operação que exige que os dados sejam carregados possa ser executada. No entanto, os dados geralmente são usados ​​imediatamente após a instrução de carregamento. O último caso de um cache miss , ou seja, uma falha de gravação, é o menos preocupante, porque a gravação geralmente é armazenada em buffer. O processador pode continuar com segurança até que o buffer esteja cheio. (Não há falha ao gravar no cache de instruções porque eles são somente leitura.)

Para minimizar a taxa de falta de cache , muitas análises foram feitas no comportamento do cache para encontrar a melhor combinação de tamanho, associatividade, tamanho de bloco e assim por diante. As seqüências de referência de memória criadas pelos programas de referência são salvas como rastreamentos de endereço . Uma análise mais aprofundada simula muitas possibilidades diferentes de implementação de cache com base nesses rastreamentos de endereços longos . Entender como várias variáveis ​​alteram a taxa de acertos do cache pode ser bastante confuso. Uma contribuição significativa foi feita por Mark Hill, que separou as várias falhas de cache em três categorias (conhecidas como "os três Cs" ):

• As faltas obrigatórias são aquelas falhas causadas pela primeira referência a um dado. O tamanho do cache e a associatividade não fazem diferença no número de faltas obrigatórias . A pré-busca pode ajudar aqui, assim como tamanhos de bloco de cache grandes (que é um tipo de pré-busca).
• Faltas de capacidade são aquelas falhas que um cache de um determinado tamanho terá, independentemente da associatividade ou tamanho do bloco. A curva da frequência de faltas de capacidade versus o tamanho do cache fornece alguma medida da localização temporária de um fluxo de referência específico.
• As falhas de conflito são aquelas falhas que poderiam ter sido evitadas se o cache não tivesse limpado os dados anteriormente. As falhas de conflito podem ser divididas em falhas de mapeamento , que são inevitáveis ​​dada uma associatividade específica, e falhas de substituição , que são causadas pela escolha específica da regra de substituição.

Taxa de falta vs tamanho do cache na parte inteira do SPEC CPU2000

O gráfico à direita resume o desempenho do cache visto pelos benchmarks da porção inteira de um SPEC CPU2000, obtidos por Hill e Cantin [1] . Esses benchmarks servem para representar o tipo de carga de trabalho que uma estação de trabalho pode experimentar em um determinado dia. Neste gráfico podemos ver os diferentes efeitos dos três Cs .

Na extrema direita, quando o tamanho do cache recebe um valor "Inf" (que, em outras palavras, tende ao infinito), temos erros obrigatórios . Se quiséssemos melhorar os recursos do SpecInt2000, aumentar o tamanho do cache além de 1 MB seria praticamente inútil.

A taxa de falha do cache totalmente associativo representa totalmente a taxa de faltas de capacidade . Nas simulações, foi escolhida uma regra de substituição LRU: isso mostra que uma regra de substituição perfeita seria necessária para minimizar a frequência de faltas de capacidade , como se, por exemplo, um vidente pesquisasse no futuro para encontrar uma localização de cache que não ser usado.

Observe como, em nossa aproximação da frequência de faltas de capacidade , o gráfico tem uma queda acentuada entre 32KB e 64KB. Isso indica que o benchmark tem um conjunto de trabalho de aproximadamente 64 KB. Um designer de cache olhando para esses benchmarks seria fortemente tentado a definir o tamanho do cache um pouco acima de 64 KB, em vez de um pouco abaixo desse valor. Deve-se notar também que, nesta simulação, nenhum tipo de associatividade pode rodar um cache de 32KB assim como um 4-way de 64KB, ou mesmo um 128KB mapeado diretamente.

Por fim, observe que entre 64 KB e 1 MB há uma grande diferença entre o cache de mapeamento direto e o cache totalmente associativo. Essa diferença é a frequência de falhas de conflito . De acordo com dados de 2004, os caches de segundo nível montados diretamente no chip do processador tendem a permanecer nessa faixa, pois os caches pequenos são rápidos o suficiente para serem caches de primeiro nível, enquanto os maiores são muito caros para serem montados de forma barata no próprio chip ( o Itanium 2 tem um cache de terceiro nível de 9 MB, o maior cache on-chip disponível no mercado em 2004). Do ponto de vista da frequência de faltas de conflito , verifica-se que a cache de segundo nível tira um grande benefício da alta associatividade.

Esse benefício era bem conhecido no final da década de 1980 e início da década de 1990 , quando os projetistas de CPU não conseguiam encaixar grandes caches em chips e não tinham largura de banda suficiente para implementar alta associatividade em caches fora do chip do processador. Várias soluções foram tentadas: o MIPS R8000 usou caros SRAMs off -chip dedicados , que incluíam comparadores de rótulos e drivers grandes, para implementar um cache associativo de 4 MB de 4 vias. O MIPS R10000 usava chips SRAM comuns para as etiquetas. O acesso aos rótulos, nos dois sentidos, exigia dois ciclos: para reduzir a latência, o R10000, a cada acesso, tentava prever qual modo de cache seria o correto.

Cache hit

Acerto de cache refere-se ao sucesso do processador em encontrar o endereço do local de memória entre os vários rótulos de cache que podem contê-lo. Se for bem-sucedido, o processador pode ler ( Cache Read Hit ) ou gravar ( Cache Write Hit ) os dados na linha de cache.

No caso de um read hit , o processador lê a palavra diretamente do cache sem envolver a memória principal. Quanto ao hit de gravação , consulte a análise detalhada sobre a política de cache de gravação

Tradução de endereços

As CPUs mais usadas implementam algum tipo de memória virtual . Na prática, cada programa rodando na máquina vê seu próprio espaço de memória, que contém código e dados para o próprio programa, de forma simplificada. Cada programa coloca tudo em seu próprio espaço de memória sem se preocupar com o que os outros programas fazem em seus respectivos espaços de memória.

A memória virtual requer que o processador traduza os endereços virtuais gerados pelo programa em endereços físicos na memória principal. A parte do processador que faz essa tradução é conhecida como unidade de gerenciamento de memória (MMU). A MMU pode acessar rapidamente a tabela de tradução por meio do Translation Lookaside Buffer (TLB), que é um cache de mapeamentos para a tabela de páginas do sistema operacional .

A tradução de endereços tem três características importantes:

• Latência: Geralmente, a MMU disponibiliza o endereço físico alguns ciclos após o endereço virtual ser computado pelo gerador de endereços.
• Aliasing: Vários endereços virtuais podem se referir ao mesmo endereço físico. A maioria dos processadores garante que todas as atualizações no único endereço físico sejam feitas em ordem. Para permitir isso, o processador deve garantir que apenas uma cópia de cada endereço físico exista no cache a qualquer momento.
• Granularidade: O espaço de endereçamento virtual é dividido em páginas. Por exemplo, um espaço de endereço virtual de 4 GB pode ser dividido em 1048576 páginas de 4 KB, cada uma das quais pode ser referenciada independentemente. Para suporte de páginas de tamanho variável, consulte a entrada de memória virtual .

Uma nota histórica: os primeiros sistemas de memória virtual eram muito lentos, exigindo um acesso à tabela de páginas (residente na memória) antes de qualquer acesso agendado à memória. Sem cache, isso reduz pela metade a velocidade de acesso à memória da máquina. Por esse motivo, o primeiro cache de hardware usado em um computador não era um cache de dados ou instruções, mas sim um TLB.

A existência de endereços físicos e virtuais levanta a questão de qual deles usar para rótulos e índices de cache. A motivação para o uso de endereços virtuais é a velocidade: um cache de dados com índices e rótulos virtuais exclui a MMU de carregar e usar dados da memória. O atraso causado pelo carregamento de dados da RAM ( load latency ) é crucial para o desempenho da CPU: por esse motivo, a maioria dos caches de nível 1 são indexados com endereços virtuais, permitindo que a MMU pesquise o TLB em paralelo com a recuperação de dados do cache da RAM.

O endereçamento virtual nem sempre é a melhor escolha: introduz, por exemplo, o problema dos aliases virtuais , ou seja, o cache pode armazenar o valor do mesmo endereço físico em vários locais. O custo de gerenciamento de aliases virtuais aumenta com o tamanho do cache e, como resultado, a maioria dos caches de nível 2 e superiores são indexados com endereços físicos.

No entanto, o uso de endereços virtuais para rótulos ( marcação virtual ) não é comum. Se a busca no TLB terminasse antes da busca no cache de RAM, o endereço físico estaria disponível a tempo para a comparação dos rótulos e, portanto, não seria necessária a marcação virtual. Caches grandes, portanto, tendem a ser marcados fisicamente e apenas caches pequenos com baixa latência são marcados virtualmente. Em CPUs mais recentes, a marcação virtual foi substituída por vhints , conforme descrito abaixo.

Indexação virtual e aliases virtuais

A maneira típica de o processador garantir que os aliases virtuais funcionem corretamente é ordená-los para que, a qualquer momento, apenas um alias virtual possa estar no cache.

Cada vez que um novo valor é adicionado ao cache, o processador procura outros aliases virtuais e os remove. Isso só é feito em caso de falha de cache. Nenhum trabalho especial é necessário durante um acerto de cache, o que ajuda a manter o caminho rápido no cache o mais rápido possível.

A maneira mais fácil de encontrar aliases é mapeá-los para a mesma área de cache. Isso acontece, por exemplo, se o TLB tiver páginas de 4 KB e o cache for mapeado diretamente em 4 KB ou menos.

Os caches de nível superior modernos são muito maiores que 4 KB, mas as páginas de memória virtual permaneceram do mesmo tamanho. Se, por exemplo, o cache for de 16 KB e indexado virtualmente, cada endereço físico poderá ser endereçado a partir de 4 locais diferentes no cache, para o mesmo número de endereços virtuais. Se o cache falhar, todos os quatro locais devem ser verificados para ver se seus endereços físicos correspondentes realmente correspondem ao endereço físico do login com falha.

Esses controles são os mesmos controles que um conjunto de cache associativo usa para selecionar uma correspondência específica. Portanto, se um cache indexado virtualmente de 16 KB, associativo de conjunto de 4 vias, for usado com páginas de memória virtual de 4 KB, nenhum trabalho adicional será necessário para eliminar os aliases virtuais em caso de falta de cache, pois as verificações já foram feitas. .

Vamos usar um AMD Athlon novamente como exemplo: ele possui um cache de dados de nível superior de 64 KB, com páginas de 4 KB, conjunto associativo de 2 vias. Quando o cache de dados de nível superior falha, 2 dos 16 (= 64 KB / 4 KB) possíveis aliases virtuais já foram verificados e sete ciclos adicionais do loop de verificação de rótulos são necessários para concluir a eliminação dos aliases virtuais adicionais.

Tags virtuais e dicas

A marcação virtual também é possível. A grande vantagem do tag virtual é que, para caches associativos, eles permitem o casamento de rótulos antes que a tradução do virtual para o físico seja feita. De qualquer forma,

• As verificações de consistência e remoção apresentam um endereço físico por ação. O hardware deve ter algum método para converter o endereço físico em um endereço de cache, geralmente armazenando rótulos físicos, bem como rótulos virtuais. Para comparação, um cache marcado fisicamente não precisa manter rótulos virtuais, o que é mais simples.
• Quando uma referência virtual para física é excluída do TLB, as informações de cache com esses endereços virtuais precisarão ser esvaziadas de alguma forma. Se as informações de cache forem permitidas em páginas não mapeadas pelo TLB, essas informações precisarão ser limpas quando os direitos de acesso nessas páginas forem alterados na tabela de páginas.

É possível que o sistema operacional garanta que vários aliases virtuais residam simultaneamente no cache. O sistema operacional garante isso forçando a coloração da página descrita abaixo. Alguns processadores RISC recentes (SPARC, RS/6000) adotaram essa abordagem. Ele não foi usado recentemente, pois o custo do hardware para descobrir e remover aliases virtuais diminuiu enquanto a complexidade e o preço do desempenho do software de coloração de páginas perfeitas aumentaram.

Pode ser útil distinguir as duas funções de marcação em um cache associativo: elas são usadas para determinar qual modo do conjunto de informações selecionar e são usadas para determinar se o cache falha ou não. A segunda função deve estar sempre correta, mas a primeira função pode adivinhar e errar a resposta ocasionalmente.

Alguns processadores (como SPARC recente) têm caches com rótulos virtuais e físicos. Os rótulos virtuais são usados ​​para seleção de modo e os rótulos físicos são usados ​​para determinar o centro ou a falha. Esse tipo de cache favorece a vantagem de latência de um cache de rótulo virtual e a interface de software simples de um cache de rótulo físico. No entanto, ele suporta o custo adicional de rótulos duplicados. Mesmo durante os processos de falha, os modos alternativos da linha de cache devem ser verificados quanto a aliases virtuais e quaisquer correspondências removidas.

A área extra (e alguma latência) pode ser atenuada mantendo dicas virtuais com qualquer informação de cache em vez de rótulos virtuais. Essas dicas são um subconjunto ou hash de um rótulo virtual e são usadas para selecionar o modo de cache pelo qual buscar um dado e um rótulo físico. Com um cache virtualmente marcado, pode haver uma correspondência de dica virtual, mas uma incompatibilidade de rótulo físico, neste caso as informações no cache com a correspondência de dica devem ser removidas para que ele acesse o cache após o preenchimento do cache neste endereço. tem uma única correspondência de dica. Como as dicas têm menos bits do que os rótulos virtuais para diferenciá-las, um cache com dicas virtuais sofre mais deficiências de conflito do que um cache de rótulo virtual.

Talvez a redução final das dicas virtuais possa ser encontrada no Pentium 4 (núcleos Willamette e Northwood). Nesses processadores, a dica virtual é na verdade apenas 2 bits e o cache é associativo de 4 vias. Com efeito, o hardware mantém uma permutação simples de endereços virtuais para endereços de cache, de modo que nenhum CAM é necessário para selecionar o caminho certo dos quatro modos de recuperação.

Coloração de página

Caches indexados fisicamente grandes (geralmente caches secundários) encontram um problema: o sistema operacional, e não os aplicativos, controla quais páginas colidem umas com as outras no cache. As diferenças na alocação de páginas de um programa levam ao próximo nível de diferenças nos caminhos de colisão de cache, o que pode levar a diferenças muito grandes no desempenho do programa. Essas diferenças podem tornar muito difícil obter um tempo de referência consistente e repetível para a execução de programas, levando os engenheiros pagos e desconsolados a exigir que os autores do sistema operacional corrijam o problema.

Para entender o problema, considere uma CPU com 1 MB de cache de nível 2 de mapeamento direto indexado fisicamente e 4 KB de páginas de memória virtual. As páginas físicas sequenciais são mapeadas para locais sequenciais no cache até que, após 256 páginas, o caminho seja revertido para si mesmo. Podemos rotular cada página física com uma cor de 0 a 255 para indicar onde ela pode ir no cache. Locais em páginas físicas com cores diferentes não podem entrar em conflito no cache.

Um programador que deseja fazer uso máximo do cache pode organizar seus acessos ao programa de modo que apenas 1 MB de dados precise ser armazenado em cache por vez, evitando falhas de capacidade. Mas também deve garantir que os logins não tenham falhas de conflito. Uma maneira de pensar sobre esse problema é subdividir as páginas virtuais que o programa usa e atribuir cores virtuais a elas da mesma forma que as cores físicas eram atribuídas às páginas físicas anteriormente. O programador pode então organizar os acessos de seu código de modo que duas páginas com a mesma cor virtual não estejam em uso ao mesmo tempo. Existe uma extensa literatura sobre essas otimizações (por exemplo , otimização de ninho de loop ), principalmente proveniente da comunidade de computação de alto desempenho (HPC).

O conceito é que, embora todas as páginas em uso em um determinado momento possam ter cores virtuais diferentes, algumas podem ter a mesma cor física. muito provável que algumas páginas tenham a mesma cor física e, portanto, as posições dessas páginas coincidem no cache (este é o paradoxo do aniversário ).

A solução é fazer com que o sistema operacional tente atribuir páginas físicas de cores diferentes a cores virtuais diferentes, uma técnica chamada coloração de página . Embora o mapeamento de cores virtual para físico real seja irrelevante para o desempenho do sistema, mapeamentos estranhos são difíceis de rastrear e têm pequenos benefícios, portanto, a maioria das abordagens de coloração de páginas simplesmente tenta manter as páginas físicas e virtuais coloridas da mesma maneira.

Se o sistema operacional puder garantir que cada página física se refira a uma única cor virtual, não haverá aliases virtuais e o processador poderá usar caches virtualmente indexados sem a necessidade de verificações extras de aliases virtuais durante o gerenciamento de falhas. Como alternativa, o sistema operacional pode limpar uma página do cache mesmo que ela mude de uma cor virtual para outra. Como mencionado anteriormente, essa abordagem foi usada por alguns projetos recentes de SPARC e RC / 6000.

Hierarquia de cache em um processador moderno

Os processadores modernos têm vários caches no chip para interagir. Duas razões em particular levaram ao desenvolvimento da atual hierarquia de cache.

Caches especializados

A primeira razão é que as CPUs com pipeline acessam a memória de vários pontos no pipeline: recuperação de instruções, tradução de endereço virtual para físico e recuperação de dados. Para um exemplo simples: Pipeline RISC clássico . A implementação natural é usar diferentes caches físicos para cada um desses pontos, de modo que nenhum recurso físico precise ser programado para atender a dois pontos no pipeline. Embora o pipeline naturalmente termine com pelo menos três caches separados (instruções, TLB e dados), cada um é especializado em uma função específica.

Cache de vítimas

Um cache de vítima é um cache usado para manter blocos removidos do cache da CPU devido a um conflito ou falta de capacidade. O cache da vítima está localizado entre o cache primário e a memória subjacente e mantém apenas os blocos removidos após uma falha. Esta técnica é usada para reduzir a penalidade por uma falha de cache, porque pode acontecer que os dados que estão no cache da vítima sejam solicitados algum tempo depois e, em vez de declarar uma falta, e ir para a memória para recuperar esses dados, o O cache da vítima é verificado e os dados que ainda estão nele são usados.

O cache original da vítima em um HP PA7200 era um cache pequeno e totalmente associativo. Processadores posteriores, como AMD Athlon , Athlon XP e Athlon 64 , usam o cache secundário muito grande como cache de vítima, para evitar a repetição de armazenamentos de contexto no cache primário.

Cache de rastreamento

Um dos exemplos mais extremos de especialização de cache é o cache de rastreamento usado nos microprocessadores Pentium 4 . Um cache de rastreamento é um mecanismo para aumentar a largura de banda de busca de instruções armazenando rastreamentos de instruções que já foram armazenadas. O mecanismo foi proposto pela primeira vez por Eric Rotenberg , Steve Bennett e Jim Smith em seu artigo de 1996: " Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching " .

Um cache de rastreamento armazena instruções mesmo depois de executadas ou retiradas. Geralmente, as instruções são adicionadas aos caches de rastreamento em grupos que representam blocos individuais básicos e rastreamentos de instruções dinâmicos. Um bloco base consiste em um grupo de instruções não ramificadas (individidas) que terminam em uma ramificação. Um rastreamento dinâmico ("trace path" ou "trace of the path") consiste apenas nas instruções cujo resultado é realmente usado e elimina as seguintes instruções que recebem ramificações (já que não são executadas); uma trilha dinâmica pode ser a concatenação de múltiplos de blocos básicos. Isso permite que a unidade de recuperação de instruções recupere vários blocos básicos, sem a preocupação de ramificar no fluxo de execuções.

As linhas de rastreamento são armazenadas no cache de rastreamento com base no contador de programa da primeira instrução no rastreamento e em um conjunto de previsões de ramificação. Isso permite o armazenamento de diferentes rastreamentos de caminho começando com o mesmo endereço, cada um representando diferentes resultados de ramificação. No estágio de armazenamento de instruções de um pipeline de instruções , o contador de programa atual, juntamente com um conjunto de previsões de ramificação, é verificado no cache de rastreamento para uma ocorrência. Se ocorrer uma ocorrência, uma linha de rastreamento é fornecida para recuperar qual delas não precisa ir para um cache ou memória regular para essas instruções. o cache de rastreamento continua a alimentar a unidade de busca até que a linha de rastreamento termine ou até que haja uma previsão incorreta no pipeline. Se houver uma falha, uma nova faixa começa a ser criada. A vantagem sobre os caches de código normais é que todas as instruções que seguem uma ramificação que são incondicionais ou previstas como não seguidas não são armazenadas em cache: o resultado é que não são formadas "bolhas" de código não utilizado que desperdiçam espaço.

Os caches de rastreamento também são usados ​​em processadores como o Intel Pentium 4 para armazenar micro operações já decodificadas ou traduções de instruções x86 complexas, para que na próxima vez que a mesma instrução for solicitada, ela não precise ser decodificada.

A ideia por trás do cache de rastreamento é que em processadores CISC que usam instruções RISC internamente , como o Pentium 4, decodificar as instruções é uma operação extremamente cara, e seu resultado deve ser explorado ao máximo. Usar um cache de rastreamento em vez de um cache normal tem exatamente esta vantagem: não ter que decodificar uma instrução já encontrada durante a execução de um programa.

O cache de rastreamento não tem recebido muito favor ultimamente devido a algumas falhas. A primeira é que muitas instruções RISC são traduzidas em uma única instrução CISC em um único ciclo de clock, e as instruções que requerem vários ciclos de clock para serem traduzidas em múltiplas instruções RISC são relativamente poucas e infrequentes, então o benefício real do cache de rastreamento é limitado. . A isso se soma o fato de que, no caso da arquitetura Intel, as instruções CISC geralmente têm um comprimento variável entre 1 e 6 bytes (entre 8 e 48 bits), enquanto todas as instruções RISC usadas internamente têm um comprimento fixo de 118 bits. . Portanto, com o mesmo tamanho, um cache de rastreamento contém muito menos instruções do que um cache normal. Essas desvantagens levaram a Intel a não usar o cache de rastreamento em suas arquiteturas mais recentes: Intel Core e Intel Core 2 .

Ver texto do artigo de Smith, Rotenberg e Bennett . Recuperado em 30 de novembro de 2019 (arquivado do original em 3 de abril de 2008) . em Citeseer .

Cache multinível

A segunda razão é a troca fundamental entre a latência do cache e a taxa de acertos. Caches maiores são mais lentos e têm melhores taxas de acerto. Para melhorar essa compensação , muitos sistemas usam vários níveis de cache, com caches pequenos e rápidos apoiados em caches maiores e mais lentos. À medida que a diferença de latência entre a memória principal e os caches mais rápidos se tornou maior, alguns processadores também começaram a usar três níveis de cache no chip. Por exemplo, em 2003, o Itanium II começou a ser distribuído com um cache on-chip unificado de nível 3 de 6 MB. A série IBM Power 4 possui 256 MB de cache de nível 3 fora do chip, compartilhado entre vários processadores.

Os caches multinível geralmente operam verificando primeiro os caches de nível 1; se ocorrer uma ocorrência, o processador será executado em alta velocidade. Se o cache menor "falhar", então o maior é verificado e assim por diante, até que a memória principal precise ser acessada.

Os caches multinível introduzem um novo modelo de tomada de decisão. Por exemplo, em alguns processadores (como Intel Pentium 2 , 3 e 4 , bem como muitos RISCs ), os dados no cache L1 também podem estar no cache L2. Esses caches são chamados de inclusivos. Outros processadores (como o AMD Athlon ) possuem caches exclusivos onde é garantido que os dados estejam no máximo em um dos caches L1 ou L2.

A vantagem dos caches exclusivos é que eles armazenam mais dados. Essa vantagem aumenta com caches maiores (as implementações Intel x86 não são). Uma vantagem dos caches inclusivos é que quando dispositivos externos ou outros processadores em um sistema multiprocessador desejam remover uma linha de cache do processador, eles devem fazer com que o processador verifique apenas o cache L2. Nas hierarquias de cache que não usam inclusão, os caches L1 também devem ser verificados. Existe uma correlação entre a associatividade das caches L1 e L2: se as caches L2 não tiverem pelo menos tantos modos quanto todas as L1s juntas, a associatividade real das caches L1 é limitada.

Outra vantagem dos caches inclusivos é que caches maiores podem usar linhas de cache maiores, o que reduz o tamanho dos rótulos de cache secundários. Se o cache secundário for de uma ordem de magnitude maior que o primário e os dados do cache forem de uma ordem de magnitude maior que os rótulos do cache, esses rótulos de dados salvos podem ser comparados à área incremental necessária para armazenar os dados. Cache L1 e L2.

Como mencionado anteriormente, computadores grandes às vezes têm outro cache entre L2 e a memória principal, chamado de cache L3. Esse cache geralmente é implementado em um chip separado da CPU e, como em 2004 , tem capacidade de 2 MB a 256 MB. Esses caches custarão bem mais de US$ 1.000 para serem construídos, e seus benefícios dependerão dos caminhos de acesso dos aplicativos. As estações de trabalho e servidores x86 de última geração agora estão disponíveis com uma opção de cache L3.

Por fim, do outro lado da hierarquia de memória, o arquivo CPU Register pode ser considerado o menor e mais rápido cache do sistema, com o recurso especial sendo chamado pelo software - normalmente por um compilador, pois aloca registradores que devem conter valores recuperados da memória principal.

Exemplo: Arquitetura AMD K8

Para ilustrar tanto a especialização quanto o multinível de caches, aqui está a hierarquia de cache de um AMD Athlon 64 , cuja implementação principal é conhecida como arquitetura K8 .

Exemplo de uma hierarquia, o K8

O K8 possui 4 caches especializados: um cache de instruções, um cache de instruções TLB , um cache de dados e um cache de dados TLB. Cada um desses caches é especializado:

1. O cache de instruções mantém cópias de linha de 64 bytes da memória e recupera 16 bytes por ciclo. Cada byte neste cache é armazenado em 10 bits em vez de 8, com os bits extras marcando os limites das instruções (este é um exemplo de pré-codificação). O cache só tem proteção por paridade ao invés de ECC , pois a paridade é menor, e quaisquer dados corrompidos podem ser substituídos por dados novos da memória (que sempre tem uma cópia atualizada das instruções).

1. A instrução TLB mantém uma cópia das informações na tabela de páginas (PTE). Cada ciclo de busca de instruções tem seu endereço virtual traduzido através deste TLB em um endereço físico. Cada informação tem 4 e 8 bytes na memória. Cada TLB é dividido em duas seções, uma para manter o mapeamento PTE em 4 KB e outra para manter o mapeamento PTE em 4 MB ou 2 MB. A subdivisão permite um circuito simples para uma comparação totalmente associativa em cada seção. O sistema operacional mapeia diferentes seções do espaço de endereço virtual com diferentes tamanhos de PTE.

1. O TLB de dados possui duas cópias diferentes que contêm as mesmas informações. As duas cópias permitem dois acessos aos dados para cada ciclo para traduzir endereços virtuais em físicos. Assim como a instrução TLB, esta TLB é dividida em dois tipos de informação.

1. O cache de dados mantém cópias de memória de linhas de 64 bytes. Ele é dividido em 8 bancos (cada um armazena 8 KB de dados) e pode recuperar dois dados de 8 bytes por ciclo, desde que esses dados estejam em bancos diferentes. Existem duas cópias dos rótulos, porque cada linha de 64 bytes está espalhada por todos os 8 bancos. Cada cópia da etiqueta gerencia um dos dois acessos por ciclo.

O K8 também possui cache multinível. Existem TLBs de instrução e dados de segundo nível, que armazenam apenas mapeamentos PTE de 4 KB. Tanto os caches de instrução e dados, quanto os vários TLBs, podem ser preenchidos pelo grande cache unificado de nível 2. Esse cache é exclusivo para os caches de dados e instruções L1, o que significa que qualquer linha de 8 bytes pode residir. os caches de instruções L1, cache de dados L1 ou cache L2. No entanto, é possível que uma linha no cache de dados tenha um PTE que também resida em um dos caches TLB — o sistema operacional é responsável por manter os TLBs consistentes baixando partes deles quando a tabela de páginas na memória é atualizada.

O K8 armazena informações que nunca são armazenadas na memória – informações de previsão. Esses caches não são mostrados no diagrama anterior. Como é usual para esta classe de CPU, o K8 tem uma previsão de ramificação bastante complexa , com tabelas que ajudam a prever quais caminhos são tomados e outras tabelas que prevêem caminhos e destinos de salto. Algumas dessas informações estão associadas a instruções, tanto no cache de instruções L1 quanto no L2 unificado.

O K8 usa um mecanismo interessante para armazenar informações de previsão com instruções no cache secundário. As linhas no cache secundário são protegidas contra corrupção de dados inadvertida (por exemplo , partículas alfa atingidas via ECC ou paridade , dependendo se essas linhas foram removidas do cache de dados ou de instrução. de paridade ocupa menos bits que ECC, linhas do cache de instrução têm alguns bits restantes. Esses bits são usados ​​para calcular as previsões de caminho associadas às instruções. O resultado final é que o preditor de caminho tem um histórico de tabela grande, portanto, tem melhor precisão.

Outras hierarquias

Outros processadores têm outros tipos de preditores. (por exemplo, o preditor de bypass store-to-load no DEC Alpha 21264), e vários outros preditores especializados são prontamente concebíveis para serem integrados em processadores futuros.

Esses preditores são caches no sentido de que armazenam informações que são caras para computar. Algumas das terminologias usadas na discussão de preditores são as mesmas para caches (referidas como ocorrências no preditor de caminho), mas os preditores geralmente não são ponderados como parte da hierarquia de cache.

O K8 mantém as instruções e os dados de cache consistentes no hardware, o que significa que um armazenamento em uma instrução logo após a instrução ser armazenada alterará a próxima instrução. Outros processadores, como os da família Alpha e MPS, são baseados em software para manter os caches de instruções consistentes. Não há garantia de que os armazenamentos sejam vistos no fluxo de instruções, a menos que um programa chame uma opção do sistema operacional para garantir a consistência. A ideia é poupar a complexidade do hardware na suposição de que o código automodificável é raro.

A hierarquia de cache se expande se considerarmos tanto o software quanto o hardware. O arquivo de registradores no núcleo de um processador pode ser considerado um cache muito pequeno e rápido que acertos, falhas e preenchimentos são previstos pelo compilador com antecedência. (Veja especialmente otimização de ninho de loop .) Arquivos de registro às vezes também têm uma hierarquia: O Cray-1 (por volta de 1976) tinha 8 registradores escalares e 8 registradores de endereço que eram geralmente utilizáveis, ele também tinha 64 registradores escalares e 64 endereços do tipo "B" registros. Os registradores do tipo "B" podiam ser carregados mais rapidamente do que os da memória principal, pois o Cray-1 não tinha cache de dados.

Implementação

Como as leituras de cache são operações bastante comuns que levam mais de um único ciclo, a recorrência de uma carga de uma instrução para a própria instrução tende a ser o caminho mais crítico em um bom projeto de processador, de modo que os dados nesse caminho são perdidos. que possível. Como resultado, o cache L1 é o componente mais sensível à latência do chip.

O cache mais simples é um cache de mapeamento direto indexado virtualmente. O endereço virtual é calculado com um somador, a parte mais significativa do endereço é extraída e utilizada para indexar uma SRAM, que retorna os dados armazenados. Os dados são alinhados por byte em um byte shifter e, a partir daí, são passados ​​para a próxima operação. Não há necessidade de qualquer verificação de rótulo no loop interno - na verdade, os rótulos nem precisam ser lidos. Mais tarde no pipeline, mas antes que a instrução seja realmente carregada, a tag para os dados carregados deve ser lida e verificada com o endereço virtual para garantir que houve um acerto no cache. Se isso falhar, o cache será atualizado com a linha solicitada e o pipeline será reiniciado.

Um cache associativo é muito mais complicado, pois alguns elementos de dados devem ser lidos para determinar qual ponto de cache selecionar, um cache de nível 1 de N-way associativo geralmente lê todos os N rótulos e N dados possíveis em paralelo, após o que escolhe os dados associados ao rótulo correspondente. Os caches de nível 2 às vezes economizam energia lendo o rótulo primeiro, de modo que apenas uma parte dos dados seja lida da SRAM.

Caminho de leitura para um cache associativo de 2 vias

O diagrama à direita serve para esclarecer como os vários campos de endereço são usados. O diagrama mostra a SRAM, indexação e multiplexação para um cache associativo de conjunto bidirecional de 4KB virtualmente etiquetado e indexado com 64B linhas, uma leitura ampla de 32b e um endereço virtual de 32b.

Como o cache tem 4KB e 64B linhas, há apenas 64 linhas no cache, e lemos duas de cada vez de um rótulo SRAM que tem 32 linhas, cada um com alguns rótulos de 21 bits. Embora qualquer função de endereço virtual de bit 31 a 6 possa ser usada para indexar rótulos e dados SRAM, é mais fácil usar os bits menos significativos.

Da mesma forma, como o cache tem 4 KB e um caminho de leitura de 4 B e lê dois modos para cada endereço, os dados SRAM têm 512 linhas de 8 bytes de largura.

Um cache mais moderno poderia ter 16 KB, associação de conjunto de 4 vias, indexado virtualmente, virtualmente sugerido e marcado fisicamente, com linhas de 32B, leituras de 32b e endereços físicos de 36 bits. A ocorrência de caminhos de leitura para esses tipos de caches se parece muito com o caminho acima. Em vez de rótulos, vhints são lidos e comparados a um subconjunto de endereços virtuais. Mais tarde no pipeline, o endereço virtual é traduzido em um endereço físico pelo TLB e o rótulo físico é lido (apenas um, pois o vhint fornece qual caminho do cache deve ser lido). Finalmente, o endereço físico é comparado com o endereço do rótulo para determinar se ocorreu um acerto.

Algumas implementações SPARC melhoraram a velocidade de seus caches L1 em ​​alguns atrasos ao reduzir o somador de endereço virtual nos decodificadores SRAM.

Itens relacionados

• Cache
• Memória cache
• Consistência de cache
• CPU

Outros projetos

Outros projetos

• Wikimedia Commons

• O Wikimedia Commons contém imagens ou outros arquivos no cache da CPU

Links externos

• ( PT ) Avaliando Associatividade em Caches de CPU - Hill e Smith - 1989 - Introduz capacidade, conflito e classificação obrigatória.
• ( PT ) Desempenho de Cache para Benchmarks SPEC CPU2000 . - Hill e Cantin - 2003 - Este documento de referência foi atualizado várias vezes. Ele apresentou resultados de simulação completos e lúcidos para um conjunto razoavelmente amplo de benchmarks e organizações de cache.
• ( PT ) Hierarquia de Memória em Sistemas Baseados em Cache ( PDF ) (arquivado do original em 15 de setembro de 2009) . , de Ruud van der Pas, 2002, Sun Microsystems, é um bom artigo introdutório ao cache de memória da CPU.
• ( PT ) A Cache Primer ( PDF ) (arquivado a partir do original em 25 de julho de 2008) . por Paul Genua, PE, 2004, Freescale Semiconductor, outro artigo introdutório.