Improving Cache Management Policies Using Dynamic Reuse Distances
Authors:
- 1 December 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10724451,p. 389-400
Abstract
Cache management policies such as replacement, bypass, or shared cache partitioning have been relying on data reuse behavior to predict the future. This paper proposes a new way to use dynamic reuse distances to further improve such policies. A new replacement policy is proposed which prevents replacing a cache line until a certain number of accesses to its cache set, called a Protecting Distance (PD). The policy protects a cache line long enough for it to be reused, but not beyond that to avoid cache pollution. This can be combined with a bypass mechanism that also relies on dynamic reuse analysis to bypass lines with less expected reuse. A miss fetch is bypassed if there are no unprotected lines. A hit rate model based on dynamic reuse history is proposed and the PD that maximizes the hit rate is dynamically computed. The PD is recomputed periodically to track a program's memory access behavior and phases. Next, a new multi-core cache partitioning policy is proposed using the concept of protection. It manages lifetimes of lines from different cores (threads) in such a way that the overall hit rate is maximized. The average per-thread lifetime is reduced by decreasing the thread's PD. The single-core PD-based replacement policy with bypass achieves an average speedup of 4.2% over the DIP policy, while the average speedups over DIP are 1.5% for dynamic RRIP (DRRIP) and 1.6% for sampling dead-block prediction (SDP). The 16-core PD-based partitioning policy improves the average weighted IPC by 5.2%, throughput by 6.4% and fairness by 9.9% over thread-aware DRRIP (TA-DRRIP). The required hardware is evaluated and the overhead is shown to be manageable.Keywords
This publication has 28 references indexed in Scilit:
- CRUISE2012
- SHiP2011
- PACMan2011
- Sampling Dead Block Prediction for Last-Level Caches2010
- PIPP2009
- Counter-Based Cache Replacement and Bypassing AlgorithmsIEEE Transactions on Computers, 2008
- Cache replacement based on reuse-distance prediction2007
- LIRS2002
- Run-time cache bypassingIEEE Transactions on Computers, 1999
- Minimization of demand paging for the LRU stack model of program behaviorInformation Processing Letters, 1983