Effective Context-Sensitive Memory Dependence Prediction
Authors:
- 2 March 2024
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 515-527
Abstract
Memory dependence prediction is a fundamental technique to increase instruction- and memory-level parallelism in out-of-order processors, which are crucial for high performance. However, over the years, the performance gap of state-of-the-art memory dependence predictors with respect to an ideal predictor has grown due to the increase of the pipeline width, reaching up to 6% for modern architectures. State-of-the-art predictors brace context sensitivity, however, not-well-adjusted history lengths lead to loss of accuracy and high storage requirements. This work proposes PHAST, a novel context-sensitive memory dependence predictor that identifies for each load the minimum history length necessary to provide precise predictions. Our key observation is that for each load, it suffices to identify the youngest conflicting store and the path between them. This observation is proven empirically using an unlimited budget version of PHAST, which performs close to an ideal predictor with a 0.47% gap. Through cycle-accurate simulation of the SPEC CPU 2017 suite, we show that a 14.5KB implementation of PHAST falls 1.50% behind an ideal predictor. Compared to the top-performing state-of-the-art predictors, PHAST achieves average speedups of 5.05% (up to 39.7%), 1.29% (up to 22.0%), and 3.04% (up to 38.2%) with respect to an 18.5KB StoreSets, a 19KB NoSQ, and a 38.6 MDP-TAGE, respectively. This stems from a considerable misprediction reduction, ranging between 62.5% and 70.0%, on average.Keywords
Funding Information
- European Research Council (ERC) (819134)
This publication has 29 references indexed in Scilit:
- Next Generation “Zen 3” Core2021
- CACTI-P: Architecture-level modeling for SRAM-based structures with advanced leakage reduction techniques2011
- Store Vectors for Scalable Memory Dependence Prediction and Scheduling2006
- Software-Hardware Cooperative Memory Disambiguation2006
- Store Vulnerability Window (SVW): Re-Execution Filtering for Enhanced Load Optimization2005
- An oldest-first selection logic implementation for non-compacting issue queues [microprocessor power reduction]2003
- Speculation techniques for improving load related instruction scheduling2003
- Memory dependence prediction using store sets2002
- Dynamic branch prediction with perceptrons2002
- Analysis of branch prediction strategies and branch target buffer designPerformance Evaluation, 1983