Hierarquia de cache, ou cache multinível, é uma arquitetura de memória que usa uma hierarquia de armazenamentos de memória baseada em diferentes velocidades de acesso para armazenar dados em cache. Dados altamente solicitados são armazenados em cache em armazenamentos de memória de acesso rápido, permitindo acesso mais rápido pelos núcleos da unidade central de processamento (CPU).
A hierarquia de cache é uma forma e parte da hierarquia de memória e pode ser considerada uma forma de armazenamento em camadas. Este projeto foi concebido para permitir que os núcleos da CPU processassem mais rapidamente, apesar da latência de memória do acesso à memória principal. O acesso à memória principal pode atuar como um gargalo para o desempenho do núcleo da CPU, pois a CPU espera pelos dados, enquanto tornar toda a memória principal de alta velocidade pode ser proibitivamente caro. Os caches de alta velocidade são um compromisso que permite acesso rápido aos dados mais utilizados pela CPU, permitindo um clock da CPU mais rápido.
Antecedentes Na história do desenvolvimento de computadores e chips eletrônicos, houve um período em que os aumentos na velocidade da CPU superaram as melhorias na velocidade de acesso à memória.Ronald D. Miller; Lars I. Eriksson; Lee A Fleisher, 2014. Miller's Anesthesia E-Book. Elsevier Health Sciences. p. 75. . A diferença entre a velocidade das CPUs e da memória significava que a CPU ficaria frequentemente ociosa.Albert Y. Zomaya, 2006. Handbook of Nature-Inspired and Innovative Computing: Integrating Classical Models with Emerging Technologies. Springer Science & Business Media. p. 298. . As CPUs eram cada vez mais capazes de executar maiores quantidades de instruções em um determinado tempo, mas o tempo necessário para acessar os dados da memória principal impedia que os programas se beneficiassem totalmente dessa capacidade.Richard C. Dorf, 2018. Sensors, Nanoscience, Biomedical Engineering, and Instruments: Sensors Nanoscience Biomedical Engineering. CRC Press. p. 4. . Este problema motivou a criação de modelos de memória com taxas de acesso mais altas para realizar o potencial dos processadores mais rápidos.David A. Patterson; John L. Hennessy, 2004. Computer Organization and Design: The Hardware/Software Interface, Third Edition. Elsevier. p. 552. .
Isso resultou no conceito de memória cache, proposto pela primeira vez por Maurice Wilkes, um cientista da computação britânico da Universidade de Cambridge em 1965. Ele chamou esses modelos de memória de "memória escrava". Entre aproximadamente 1970 e 1990, artigos de Anant Agarwal, Alan Jay Smith, Mark D. Hill, Thomas R. Puzak e outros discutiram melhores projetos de memória cache. Os primeiros modelos de memória cache foram implementados na época, mas mesmo enquanto os pesquisadores investigavam e propunham melhores projetos, a necessidade de modelos de memória mais rápidos continuava. Essa necessidade resultou do fato de que, embora os primeiros modelos de cache melhorassem a latência de acesso aos dados, devido a custos e limitações técnicas, não era viável para o cache de um sistema de computador se aproximar do tamanho da memória principal. A partir de 1990, ideias como adicionar outro nível de cache (segundo nível), como um backup para o cache de primeiro nível, foram propostas. Jean-Loup Baer, Wen-Hann Wang, Andrew W. Wilson e outros conduziram pesquisas sobre este modelo. Quando várias simulações e implementações demonstraram as vantagens dos modelos de cache de dois níveis, o conceito de caches multinível se popularizou como um modelo novo e geralmente melhor de memórias cache. Desde 2000, os modelos de cache multinível receberam ampla atenção e atualmente são implementados em muitos sistemas, como os caches de três níveis presentes nos produtos Intel Core i7.
Cache multinível Acessar a memória principal para cada execução de instrução pode resultar em processamento lento, com a velocidade do clock dependendo do tempo necessário para localizar e buscar os dados. Para esconder essa latência de memória do processador, o cache de dados é usado.Shane Cook, 2012. CUDA Programming: A Developer's Guide to Parallel Computing with GPUs. Newnes. pp. 107–109. . Sempre que os dados são necessários ao processador, eles são buscados da memória principal e armazenados na estrutura de memória menor chamada cache. Se houver qualquer necessidade adicional desses dados, o cache é pesquisado primeiro antes de ir para a memória principal.Bruce Hellingsworth; Patrick Hall; Howard Anderson; 2001. Higher National Computing. Routledge. pp. 30–31. . Esta estrutura reside mais próxima do processador em termos do tempo necessário para pesquisar e buscar dados em relação à memória principal.Reeta Sahoo, Gagan Sahoo. Infomatic Practices. Saraswati House Pvt Ltd. pp. 1–. . As vantagens do uso de cache podem ser comprovadas calculando o tempo médio de acesso (AAT) para a hierarquia de memória com e sem o cache.Phillip A. Laplante; Seppo J. Ovaska; 2011. Real-Time Systems Design and Analysis: Tools for the Practitioner. John Wiley & Sons. pp. 94–95. .
Tempo médio de acesso (AAT) Os caches, por serem pequenos, podem resultar em falhas frequentes – quando uma busca no cache não fornece a informação procurada – resultando em uma chamada à memória principal para buscar dados. Assim, o AAT é afetado pela taxa de falha de cada estrutura na qual ele pesquisa os dados.
O AAT para a memória principal é dado pelo Tempo de acertomemória principal. O AAT para caches pode ser dado por:
Tempo de Acertocache + (Taxa de Falhacache × Penalidade de Falhatempo levado para ir à memória principal após falha no cache).
O tempo de acerto para caches é menor que o tempo de acerto para a memória principal, portanto o AAT para recuperação de dados é significativamente menor ao acessar dados através do cache do que através da memória principal.Cetin Kaya Koc, 2008. Cryptographic Engineering. Springer Science & Business Media. pp. 479–480. .
Compromissos Embora o uso do cache possa melhorar a latência da memória, nem sempre resulta na melhoria necessária para o tempo gasto na busca de dados devido à forma como os caches são organizados e percorridos. Por exemplo, caches de mapeamento direto do mesmo tamanho geralmente têm uma taxa de falha maior do que caches totalmente associativos. Isso também pode depender do benchmark do computador que testa o processador e do padrão das instruções. Mas usar um cache totalmente associativo pode resultar em maior consumo de energia, pois precisa pesquisar todo o cache a cada vez. Devido a isso, o compromisso entre consumo de energia (e calor associado) e o tamanho do cache torna-se crítico no projeto do cache.
Evolução
No caso de uma falha de cache, o propósito de usar tal estrutura será inútil e o computador terá que ir à memória principal para buscar os dados necessários. No entanto, com um cache multinível, se o computador falhar no cache mais próximo do processador (cache de nível um ou L1), ele pesquisará então o(s) próximo(s) nível(is) de cache e irá para a memória principal apenas se esses métodos falharem. A tendência geral é manter o cache L1 pequeno e a uma distância de 1–2 ciclos de clock do processador, com os níveis inferiores de cache aumentando em tamanho para armazenar mais dados do que o L1, sendo assim mais distantes, mas com uma taxa de falha menor. Isso resulta em um AAT melhor.David A. Patterson; John L. Hennessy; 2008. Computer Organization and Design: The Hardware/Software Interface. Morgan Kaufmann. pp. 489–492. . O número de níveis de cache pode ser projetado pelos arquitetos de acordo com seus requisitos após verificar os compromissos entre custo, AATs e tamanho.Harvey G. Cragon, 2000. Computer Architecture and Implementation. Cambridge University Press. pp. 95–97. .Baker Mohammad, 2013. Embedded Memory Design for Multi-Core and Systems on Chip. Springer Science & Business Media. pp. 11–14. .
Ganhos de desempenho Com o escalonamento da tecnologia que permitiu que sistemas de memória fossem acomodados em um único chip, a maioria dos processadores modernos tem até três ou quatro níveis de cache. A redução no AAT pode ser compreendida por este exemplo, onde o computador verifica o AAT para diferentes configurações até caches L3.
Exemplo: memória principal = 50 , L1 = 1 ns com 10% de taxa de falha, L2 = 5 ns com 1% de taxa de falha, L3 = 10 ns com 0,2% de taxa de falha. Sem cache, AAT = 50 ns Cache L1, AAT = 1 ns + (0,1 × 50 ns) = 6 ns Caches L1–2, AAT = 1 ns + (0,1 × [5 ns + (0,01 × 50 ns)]) = 1,55 ns Caches L1–3, AAT = 1 ns + (0,1 × [5 ns + (0,01 × [10 ns + (0,002 × 50 ns)])]) = 1,5101 ns
Desvantagens A memória cache tem um custo marginal maior do que a memória principal e, portanto, pode aumentar o custo do sistema como um todo.Vojin G. Oklobdzija, 2017. Digital Design and Fabrication. CRC Press. p. 4. . Os dados em cache são armazenados apenas enquanto a energia é fornecida ao cache. Aumento da área no chip necessária para o sistema de memória. Os benefícios podem ser minimizados ou eliminados no caso de programas grandes com baixa localidade temporal, que acessam frequentemente a memória principal.
Propriedades
Banqueado versus unificado Em um cache banqueado, o cache é dividido em um cache dedicado ao armazenamento de instruções e um cache dedicado a dados. Em contraste, um cache unificado contém ambas as instruções e dados no mesmo cache.Yan Solihin, 2015. Fundamentals of Parallel Multicore Architecture. CRC Press. p. 150. . Durante um processo, o cache L1 (ou o cache de nível mais alto em relação à sua conexão com o processador) é acessado pelo processador para recuperar tanto instruções quanto dados. Exigir que ambas as ações sejam implementadas ao mesmo tempo requer múltiplas portas e mais tempo de acesso em um cache unificado. Ter múltiplas portas requer hardware e fiação adicionais, levando a uma estrutura significativa entre os caches e as unidades de processamento.Steve Heath, 2002. Embedded Systems Design. Elsevier. p. 106. . Para evitar isso, o cache L1 é frequentemente organizado como um cache banqueado, o que resulta em menos portas, menos hardware e tempos de acesso geralmente menores.
Processadores modernos têm caches divididos, e em sistemas com caches multinível, os caches de nível inferior podem ser unificados enquanto os de nível superior são divididos.Alan Clements, 2013. Computer Organization & Architecture: Themes and Variations. Cengage Learning. p. 588. .
Políticas de inclusão
Se um bloco presente na camada de cache superior também pode estar presente no nível de cache inferior é regido pela política de inclusão de cache do sistema de memória, que pode ser inclusiva, exclusiva ou não inclusiva não exclusiva (NINE).
Com uma política inclusiva, todos os blocos presentes no cache de nível superior também devem estar presentes no cache de nível inferior. Cada componente de cache de nível superior é um subconjunto do componente de cache de nível inferior. Neste caso, como há uma duplicação de blocos, há algum desperdício de memória. No entanto, a verificação é mais rápida.
Sob uma política exclusiva, todos os componentes da hierarquia de cache são completamente exclusivos, de modo que qualquer elemento no cache de nível superior não estará presente em nenhum dos componentes de cache inferiores. Isso permite o uso completo da memória cache. No entanto, há uma alta latência de acesso à memória.
As políticas acima exigem um conjunto de regras a serem seguidas para implementá-las. Se nenhuma delas for forçada, a política de inclusão resultante é chamada de não inclusiva não exclusiva (NINE). Isso significa que o cache de nível superior pode ou não estar presente no cache de nível inferior.
Políticas de escrita Existem duas políticas que definem a maneira como um bloco de cache modificado será atualizado na memória principal: write through e write back.