Analysis and optimization of cache-related parameters for real-time systems

Abstract

As memórias cache são fundamentais nos sistemas ciberfísicos contemporâneos devido às penalidades temporais incorridas por falhas da cache. Pesquisas anteriores se concentraram principalmente em políticas de substituição de linha e particionamento da cache em sistemas em tempo real para mitigar o impacto das falhas no Pior Tempo de Execução (\emph{Worst Case Execution Time} - WCET). Esta dissertação explora extensivamente várias políticas de substituição de linhas da cache em sistemas de tempo real, com o objetivo central de avaliar de forma abrangente o seu desempenho em termos de falhas e escalonabilidade ? duas métricas cruciais na otimização de sistemas de tempo real. Os resultados da pesquisa confirmam que o tamanho da partição da cache e o número \emph{ways} da cache exercem uma influência profunda no desempenho e na escalonabilidade da aplicação. O impacto do tamanho da partição da cache nas políticas de substituição de linha é particularmente significativo. Os resultados experimentais ilustram que a modificação do tamanho da partição da cache pode levar a melhorias significativas no tempo de execução em aplicações específicas. Por exemplo, a aplicação \texttt{pca-small} obteve uma melhoria impressionante de 40\% no tempo de execução com uma partição de 128 KB simplesmente alterando a política de substituição, destacando o papel crítico de otimizar políticas de substituição de linhas da cache e tamanhos de partição adaptados a tarefas específicas. O número de formas da cache também desempenha um papel crucial nas políticas de substituição da cache. A transição de um número menor para um número maior de \emph{ways} pode resultar em aumentos substanciais de desempenho em determinados cenários. Por exemplo, a aplicação \texttt{svd3-large} obteve uma melhoria de desempenho de aproximadamente 12\% ao passar de quatro \emph{ways} para 16 \emph{ways}, atribuída principalmente à adoção da política LIP e de uma partição da cache de 64 KB. Essas observações enfatizam a influência significativa do número de \emph{ways} da cache no comportamento e no desempenho da política de substituição de cache. A escalonabilidade, uma consideração importante em sistemas de tempo real, é profundamente influenciada por essas otimizações da cache. Mesmo em cenários moderados de aceleração da cache, melhorias de escalonamento de até 5\% podem ser alcançadas para casos não preemptivos. Em cenários com as maiores acelerações da cache, as melhorias na capacidade de escalonamento chegam a mais de 40\% para casos não preemptivos em conjuntos de tarefas de alta utilização. A contribuição central da dissertação reside no desenvolvimento de um algoritmo projetado para otimizar a utilização e escalonabilidade da cache em sistemas de tempo real, alocando dinamicamente partições da cache. Este algoritmo supera consistentemente o algoritimo de particionamento da cache ideal (\emph{Optimal Cache Partitioning Algorithm} - OCPA) alcançando ganhos de até 2\%. Concluindo, esta pesquisa ressalta a importância dos parâmetros da cache no aumento da previsibilidade, eficiência e desempenho geral em sistemas de tempo real, ao mesmo tempo em que destaca o potencial para melhorias substanciais na escalonabilidade. Essas descobertas estabelecem as bases para futuras explorações e inovações no campo da otimização da cache em sistemas de tempo real.

Abstract: Cache memories are pivotal in contemporary cyber-physical systems due to the temporal penalties incurred from cache failures. Previous research has primarily focused on cache line replacement policies and cache partitioning in real-time systems to mitigate cache failures' impact on Worst Case Execution Time (WCET). However, the broader implications of cache parameters on these policies, especially in the context of cache partitions, have received limited attention. This dissertation extensively explores various cache line replacement policies in real-time systems, with a central objective to comprehensively assess their performance in terms of cache misses and schedulability?two crucial metrics in optimizing real-time systems. The research findings confirm that cache partition size and the number of cache ways exert a profound influence on both application performance and schedulability. Cache partition size's impact on cache policies is particularly significant. Experimental results illustrate that modifying the cache partition size can lead to significant runtime improvements in specific applications. For instance, the \texttt{pca-small} application achieved an impressive 40\% runtime improvement with a 128 KB cache partition simply by changing the replacement policy, highlighting the critical role of optimizing cache replacement policies and partition sizes tailored to specific tasks. The number of cache ways also plays a crucial role in cache replacement policies. Transitioning from a lower to a higher number of cache ways can result in substantial performance boosts in certain scenarios. For example, the \texttt{svd3-large} application saw a performance improvement of approximately 12\% when moving from four cache ways to 16 cache ways, primarily attributed to adopting the LIP policy and a 64 KB cache partition. These observations emphasize the significant influence of the number of cache ways on cache replacement policy behavior and performance. Schedulability, a key consideration in real-time systems, is profoundly influenced by these cache optimizations. Even under moderate cache acceleration scenarios, schedulability improvements of up to 5\% can be achieved for non-preemptive cases. In scenarios with the highest cache accelerations, schedulability improvements soar to over 40\% for non-preemptive cases in high-utilization task sets. The dissertation's central contribution lies in the development of an algorithm designed to optimize cache utilization and schedulability in real-time systems by dynamically allocating cache partitions. This algorithm consistently outperforms the Optimal Cache Partitioning Algorithm (OCPA) achieving gains of up to 2\%. In conclusion, this research underscores the significance of cache parameters in enhancing predictability, efficiency, and overall performance in real-time systems while highlighting the potential for substantial schedulability improvements. These findings lay the foundation for future exploration and innovation in the field of cache optimization within real-time systems.