Abstract Cache replacement policies significantly impact CPU performance, particularly under diverse memory access patterns. While Least Recently Used (LRU) excels with strong temporal locality, it suffers catastrophic performance degradation under streaming workloads and working sets that marginally exceed cache capacity. We present Adaptive-LRU, a lightweight, dynamically adaptive insertion policy that employs set dueling to toggle between standard LRU insertion and a thrash-resistant bimodal insertion scheme. Our comprehensive evaluation using a detailed trace-driven simulator with proper statistical methodology demonstrates that Adaptive-LRU achieves +32.6% higher hit rate than LRU/FIFO on streaming workloads and 63.2% on near-capacity loops. Compared to state-of-the-art DRRIP, Adaptive-LRU delivers 7.6 times better performance on streaming and 5.2 times better on near-capacity workloads while maintaining identical performance on cache-friendly patterns. The policy requires minimal hardware overhead 6.0-12 bytes total per cache partition, zero per-line metadata and preserves the hit critical path of standard LRU implementations.
Om Maheshwari (Thu,) studied this question.