Maximizing cache hits ratio through planned cache eviction policy selection

Abstract

Os processadores modernos estão continuamente avançando, criando uma diferença de desempenho cada vez maior em relação às memórias disponíveis no mercado atual. As memórias cache desempenham um papel fundamental na redução dessa diferença, mitigando a latência de acesso à memória. No entanto, a eficácia dessas caches, que possuem tamanho limitado, depende fortemente da política de substituição de cache, impactando diretamente a taxa de hits na cache. As CPUs atuais empregam uma política de substituição fixa determinada no momento do projeto, que pode não ser a ideal durante toda a execução do programa, levando a um desempenho subótimo e à redução da escalabilidade do sistema. Para abordar essa limitação, este trabalho apresenta uma estrutura destinada a aumentar as taxas de hits, selecionando e alternando dinamicamente as políticas de substituição de cache em tempo de execução. Além disso, a estrutura inclui uma descrição abrangente de uma ferramenta de código aberto para profiling, juntamente com quatro abordagens baseadas no reconhecimento de padrões de acesso à memória, que são avaliadas. Os testes realizados com a estrutura demonstram possíveis melhorias na taxa de misses de cache de até 60\% em comparação com a utilização da política de substituição LRU. Esses resultados impulsionaram melhorias adicionais na estrutura, incluindo a incorporação de políticas de substituição mais sofisticadas e a implementação de abordagens adicionais para alcançar resultados superiores.

Abstract: Modern processors are continually advancing, creating a widening performance gap relative to current market-available memories. Cache memories play a pivotal role in bridging this gap by mitigating memory access latency. However, the effectiveness of these size-constrained caches heavily relies on the cache eviction policy, directly im- pacting the hit rate. Current CPUs employ a fixed replacement policy determined at design time, which may not be optimal throughout program execution, leading to sub- optimal performance and reduced system schedulability. To address this limitation, this work introduces a framework aimed at enhancing hit ratios by dynamically selecting and switching cache eviction policies at runtime. Additionally, the framework includes a com- prehensive description of an open-source tool for profiling, along with four approaches based on memory access pattern recognition, which are evaluated. Benchmarks con- ducted with the framework demonstrate potential cache miss rate improvements of up to 60% compared to using the LRU replacement policy. These findings have spurred fur- ther enhancements to the framework, including the incorporation of more sophisticated eviction policies and the implementation of additional approaches to achieve superior results.