Insertion policy selection using Decision Tree Analysis
- 1 October 2010
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2010 IEEE International Conference on Computer Design
Abstract
The last-level cache (LLC) mitigates the impact of long memory access latencies in today's microarchitectures. The insertion policy in the LLC has a significant impact on cache efficiency. A fixed insertion policy can allow useless blocks to remain in the cache longer than necessary, resulting in inefficiency. We introduce insertion policy selection using Decision Tree Analysis (DTA). The technique requires minimal hardware modification over the least-recently-used (LRU) replacement policy. This policy uses the fact that the LLC filters temporal locality. Many of the lines brought to the cache are never accessed again. Even if they are reaccessed they do not experience bursts, but rather they are reused when they are near to the LRU position in the LRU stack. We use decision tree analysis of multi-set-dueling to choose the optimal insertion position in the LRU stack. Inserting in this position, zero reuse lines minimize their dead time while the non-zero reuse lines remain in the cache long enough to be reused and avoid a miss. For a 1MB 16 way set-associative last level cache in a single core processor, our policy uses only 2,069 additional bits over the LRU replacement policy. On average it reduces misses by 5.16% and achieves 7.19% IPC improvement over LRU.Keywords
This publication has 9 references indexed in Scilit:
- Extending the effectiveness of 3D-stacked DRAM caches with an adaptive multi-queue policyPublished by Association for Computing Machinery (ACM) ,2009
- Pseudo-LIFOPublished by Association for Computing Machinery (ACM) ,2009
- PIPPACM SIGARCH Computer Architecture News, 2009
- Cache bursts: A new approach for eliminating dead blocks and increasing cache efficiencyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- Adaptive insertion policies for managing shared cachesPublished by Association for Computing Machinery (ACM) ,2008
- Cache replacement based on reuse-distance predictionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- Adaptive insertion policies for high performance cachingPublished by Association for Computing Machinery (ACM) ,2007
- Counter-based cache replacement algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Dead-block prediction & dead-block correlating prefetchersPublished by Association for Computing Machinery (ACM) ,2001