TL;DR
This paper introduces a novel approach to store-load forwarding in computer processors that replaces slow, fully-associative searches with faster, speculative indexed lookups. By using prediction to identify the most likely source of data for a load, this method significantly improves the scalability of store queues, a critical component for high-performance processors, while achieving performance close to ideal designs.
What Problem Does This Paper Address?
Modern high-performance processors are designed to execute many instructions simultaneously (wide-issue) and keep a large number of instructions "in-flight" to hide latency. A key mechanism for efficient execution is store-load forwarding, where a load instruction can immediately retrieve data from a preceding, not-yet-committed store instruction. This is typically handled by a "store queue" (SQ).
The challenge is that as processors become wider and have larger instruction windows, the store queue needs to become much larger and support higher bandwidth. Traditional store queues use a "fully-associative" search, meaning every entry in the queue is checked in parallel for a matching address. This associative search becomes a significant bottleneck: it's slow, consumes a lot of power, and takes up a lot of chip area as the queue grows. This latency can even exceed that of the main data cache, complicating processor design and hurting performance. The paper aims to solve this scalability problem by eliminating the need for associative search in the store queue.
Methods
The core innovation is replacing the fully-associative search with a speculative indexed access. Instead of searching the entire store queue, the processor uses prediction to guess which single entry in the SQ is most likely to contain the data the load needs.
Here's how it works:
- Forwarding Index Predictor: This predictor, inspired by techniques like "Store Sets," takes the program counter (PC) of a load instruction and predicts the index (position) of the SQ entry from which it's most likely to forward.
- Indexed SQ Access: When a load executes, it accesses the SQ only at the predicted index. If the address in that predicted entry matches the load's address, the load gets the data. Otherwise, it falls back to fetching data from the main data cache.
- Mis-prediction Handling: Since this is speculative, mis-predictions (where the predicted entry doesn't match or the data isn't there) are detected through a mechanism called "filtered load re-execution" before instructions commit. A mis-prediction triggers a pipeline flush, similar to branch mis-predictions.
- Delay Index Predictor: To handle "difficult" loads where reliably predicting a single forwarding entry is hard, a second predictor is introduced. This predictor, inspired by the "Exclusive Collision Predictor," delays the execution of such loads until all but the youngest "candidate" stores (potential sources of data) have committed. This prevents flushes by ensuring the data is available either in the cache or from a committed store.
- Unified Load Scheduling: The proposed predictors also integrate with traditional load scheduling, simplifying the overall design.
Datasets
The paper evaluates its proposed indexed SQ design using:
- SPEC2000 benchmarks: A standard suite for evaluating processor performance.
- MediaBench benchmarks: Another suite focusing on multimedia applications.
The authors run these benchmarks on their simulator and report performance relative to different SQ configurations. No new benchmarks were introduced.
Key Insights and Ideas
- Eliminating Associativity is Key: The fundamental insight is that the associative search is the primary scalability bottleneck for store queues. By replacing it with a predicted indexed access, the paper unlocks significant performance and scalability gains.
- Prediction is Sufficient (Mostly): The core idea that a single predicted SQ entry is often enough for forwarding is powerful. This dramatically reduces the complexity and latency of the SQ access path.
- The "Difficult Load" Problem: The paper acknowledges that prediction isn't perfect. The introduction of a second predictor to delay problematic loads is crucial. This "delay" mechanism is a clever way to avoid flushes without sacrificing the single-indexed-access-per-load invariant.
- Unifying Load Scheduling and Forwarding: The predictors naturally integrate with load scheduling, simplifying the overall memory subsystem design. This is a significant architectural benefit beyond just raw performance.
- Trade-offs in Prediction: The paper highlights that aggressive forwarding (no delay) can lead to flushes for certain load patterns, while aggressive delay can hurt performance for well-behaved loads. Finding the right balance is key.
Key Results
- Performance: On an 8-way issue processor with a 512-entry reorder buffer, the proposed indexed SQ performs within 3.3% of an ideal associative SQ (with data cache latency).
- Comparison to Realistic SQ: It matches or exceeds the performance of a realistic associative SQ (which has slower latency than the data cache) on 31 out of 47 programs.
- Mis-forwarding Rate: The raw forwarding predictor has a mis-forwarding rate of 0.18% (less than 2 in 1000 loads).
- Delay Predictor Impact: Adding the delay predictor reduces the mis-forwarding rate to 0.03% at the cost of delaying 2.3% of loads by an average of 53 cycles.
- Energy Savings: Indexed SQs show approximately 30% lower per-access energy compared to associative SQs, though the overall processor energy impact is modest as the SQ is a small fraction of total energy.
Limitations and Future Work
- Not-Most-Recent Forwarding: The paper acknowledges a limitation where the predictor struggles with "not-most-recent" forwarding patterns (e.g., a load depending on a store from several iterations ago, where the SAT only tracks the most recent store). The delay predictor helps mitigate this, but associative search still has an advantage here.
- Predictor Tuning: The performance sensitivity analysis shows that predictor capacities and training ratios (especially for the delay predictor) need careful tuning for optimal performance.
- Future Work: The authors suggest exploring alternative predictor organizations and approaches, potentially incorporating "path-based information" to improve both forwarding and delay prediction accuracy and robustness. They also note that their indexed SQ, combined with filtered load re-execution for load queue search, creates a system with no associative search whatsoever, which is a significant step towards more scalable memory systems.
Summary updated