2025/03/20 by Sophie Kahlen, Jan Reineke, Kahlen, Sophie +1
Computer Science · #68 #Advanced Data Storage Technologies #D.3.4 #FOS: Computer and information sciences #Parallel Computing and Optimization Techniques #Programming Languages (cs.PL) #Software System Performance and Reliability
paper · pdf · doi:10.48550/arxiv.2503.16588
openalex publication_date 2025/03/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this work we unify two existing lines of work towards cache analysis for non-LRU policies. To this end, we extend the notion of competitiveness to block competitiveness and systematically analyze the competitiveness and block competitiveness of FIFO and MRU relative to LRU for arbitrary associativities. We show how competitiveness and block competitiveness can be exploited in state-of-the-art WCET analysis based on the results of existing persistence analyses for LRU. Unlike prior work, our approach is applicable to microarchitectures that exhibit timing anomalies. We experimentally evaluate the precision and cost of our approach on benchmarks from TACLeBench. The experiments demonstrate that quantitative cache analysis for FIFO and MRU comes close to the precision of LRU.