Perceptron learning for reuse prediction

Citations Over TimeTop 10% of 2016 papers

Abstract

The disparity between last-level cache and memory latencies motivates the search for efficient cache management policies. Recent work in predicting reuse of cache blocks enables optimizations that significantly improve cache performance and efficiency. However, the accuracy of the prediction mechanisms limits the scope of optimization. This paper proposes perceptron learning for reuse prediction. The proposed predictor greatly improves accuracy over previous work. For multi-programmed workloads, the average false positive rate of the proposed predictor is 3.2%, while sampling dead block prediction (SDBP) and signature-based hit prediction (SHiP) yield false positive rates above 7%. The improvement in accuracy translates directly into performance. For single-thread workloads and a 4MB last-level cache, reuse prediction with perceptron learning enables a replacement and bypass optimization to achieve a geometric mean speedup of 6.1%, compared with 3.8% for SHiP and 3.5% for SDBP on the SPEC CPU 2006 benchmarks. On a memory-intensive subset of SPEC, perceptron learning yields 18.3% speedup, versus 10.5% for SHiP and 7.7% for SDBP. For multi-programmed workloads and a 16MB cache, the proposed technique doubles the efficiency of the cache over LRU and yields a geometric mean normalized weighted speedup of 7.4%, compared with 4.4% for SHiP and 4.2% for SDBP.

Related Papers

• → Transient and Steady-state Regime of a Family of List-based Cache Replacement Algorithms(2015)72 cited
• → CIPARSim: cache intersection property assisted rapid single-pass FIFO cache simulation technique(2011)10 cited
• → Measuring the potential benefits of a dynamically adaptive cache line size(2006)
• Hybrid Scheme of Data Cache Design for Reducing Energy Consumption in High Performance Embedded Processor(2006)
• A Comparison of Cache Replacement Algorithms for Video Services(2020)