Source-linked AI summary
Proba: A High-Performance, Low-Traffic Probabilistic Spatial Memory Streaming Prefetcher
Yinting Huang, Jacky Wong, Sam Ainsworth
TL;DR
Memory latency and bandwidth have lagged processor advances, while existing SMS designs offer limited adaptability in prefetch aggressiveness. Proba uses probabilistic pattern updates and accuracy feedback to adapt prefetching. It outperforms other SMS-based prefetchers with lower DRAM traffic, including in bandwidth-constrained settings.
Problem
Existing SMS-based prefetchers have limited adaptability to dynamic access patterns and coarse control over prefetch aggressiveness.
Source: §1 · p. 2Method
Proba combines probabilistic pattern updates with accuracy feedback, marginal-accuracy decisions, and pattern accumulation across multiple trigger features.
Source: §1 · p. 2Results
Proba outperforms other SMS-based prefetchers across bandwidth conditions; on SPECspeed 2017 it achieves 6.6% geomean speedup with 8.5% additional DRAM traffic, versus PMP's 5.6% speedup with 28.1% additional DRAM traffic.
Source: §1 · p. 2, §5.1 · p. 8Takeaways & Limitations
Proba's frugal bandwidth use makes it well suited to energy-bound systems, from mobile phones to data centers.
Source: §1 · p. 2
Abstract
from arXiv · showhide
Spatial Memory Streaming (SMS) prefetchers exploit recurring spatial access patterns across memory regions to predict future accesses. Despite their effectiveness, existing SMS-based designs suffer from coarse control over aggressiveness and limited adaptability to dynamic program behavior and historical patterns. In this work, we present Proba, a feedback-directed SMS-based prefetcher that integrates probabilistic pattern updates, marginal accuracy decision-making, and pattern accumulation over several trigger features to achieve fine-grained accuracy-coverage trade-offs. When accuracy deteriorates, Proba moderates its aggressiveness to prioritize accurate prefetches; conversely, when accuracy rises, it expands its coverage. Proba achieves higher speedups than any other SMS-based prefetcher while being vastly more efficient in DRAM traffic. This culminates in a large performance gap between Proba and other techniques in multicore and DRAM-constrained scenarios without harming single-threaded throughput.
1 Introduction
Memory latency and bandwidth have lagged processor advances, leaving applications vulnerable to stalls. Proba adapts SMS prefetching with probabilistic updates and accuracy feedback, and outperforms other SMS-based prefetchers across bandwidth conditions.
1 Introduction
- The widening gap between processor performance and memory access latency causes frequent stalls and underutilized computational resources.Processor performance has advanced while memory latency and bandwidth have improved more slowly.Source: §1 · p. 1
- SMS exploits recurring spatial access patterns by replaying a stored prediction when a trigger feature recurs in another memory region.Trigger features include metadata such as the program counter or the first access offset.Source: §1 · p. 1, Figure 2 · p. 2
- Existing SMS-based designs trade accuracy for coverage: DSPatch switches between two fixed update behaviors, while PMP uses storage-intensive counters that constrain trigger-feature granularity.Both designs require more storage per entry and coarser pattern updates.Source: §1 · pp. 1–2
- Proba combines probabilistic updates, accuracy feedback, multi-feature pattern accumulation, marginal accuracy decisions, and a Jail Table to adapt prefetch aggressiveness without additional pattern storage.The Jail Table separates pattern discovery from region tracking for cache-generation tracking.Source: §1 · p. 2
- Proba consistently outperforms state-of-the-art SMS-based prefetchers under ample and constrained DRAM bandwidth, with its advantage more pronounced in multicore settings.It limits inaccurate prefetches while favoring coverage when additional prefetching is beneficial.Source: Figure 1 · p. 1, §1 · p. 2
2 Background and Motivation
SMS records a region's access pattern and replays it when a trigger recurs, but replacing history with each new observation limits adaptability. DSPatch and PMP preserve more history through different pattern-merging schemes, with trade-offs in storage and prediction granularity.
2.1 Spatial Memory Streaming (SMS)
- SMS records accesses from a region's start until eviction, stores the pattern under its trigger feature, and replays it in a new region; replacing history with each observation can cause oscillation and poor adaptivity.The first access starts a generation, and eviction ends tracking.Source: §2.1 · p. 2
2.2 Dual Spatial Pattern Prefetcher (DSPatch)
- DSPatch maintains accuracy-biased and coverage-biased patterns, selects between them using pattern metrics and bandwidth utilization, and combines observations with bitwise AND and OR updates.Repeated OR updates can drive patterns toward all ones; a saturating counter eventually stops accumulation and triggers reset and retraining, losing historical information.Source: §2.2 · pp. 2–3
2.3 Pattern Merging Prefetcher (PMP)
- PMP accumulates patterns in offset-indexed OPT and PC-indexed PPT tables, but counter-vector storage reduces history capacity and fixed voting thresholds limit adaptation to workload-specific aggressiveness.PPT stores a coarser compressed pattern; PMP's coarse trigger features can miss regularities captured by finer-grained features.Source: §2.3 · p. 3
3 Our Solution: Proba
Proba combines probabilistic pattern updates and accuracy feedback with multiple trigger-feature tables, while sampling and a Jail Table improve region tracking. Its Jail Table raises the share of AGT entries reaching EoG to 70.2% with a 64-entry AGT.
3.2 Probabilistic Update
- Proba stores one history pattern per entry and probabilistically incorporates new observations, avoiding additional storage while gradually refining predictions.Insertion probability p governs adding newly observed bits; deletion probability q governs removing bits absent from an observation, while matching bits are retained.Source: §3 · p. 3, §3.2 · pp. 4–5
3.3 Accuracy-Coverage Seeking Decision-making
- Proba compares pattern accuracy with an 80% default threshold, shifting toward coverage when accuracy exceeds it and toward accuracy otherwise.The update uses the PHT-entry-local accuracy metric; its probability states are stored in a 3-bit field.Source: §3.3 · p. 5
3.4 Pattern History Tables and Marginal Accuracy
- Three PHTs index PC-Only, PC+Offset, and Offset+Offset triggers, and Proba issues the union of their predictions.For less accurate trigger features, aggressiveness is adjusted according to the accuracy of their additional predictions beyond those of more accurate features, using an 80% default target.Source: §3.4 · pp. 5–6
3.5 Jail Table and Region Sampling
- Proba separates region-interval tracking from access-pattern recording, using a Jail Table for active regions and a sampling-based AGT for representative patterns.When an AGT set reaches 50% occupancy, new regions are sampled at 5%; regions marked in the Jail Table are not reallocated until EoG.Source: §3.5 · pp. 6–7
- 70.2% of Proba’s AGT entries reach EoG with a 64-entry AGT and Jail Table, versus 2.7% with a 64-entry AGT without one.The comparison also reports 6.1% with a 128-entry AGT and 53.5% with a 512-entry AGT.Source: §3.5 · p. 6
- The Jail Table uses two hash-indexed bitmaps to track whether a region is active, and its deletion can cause false negatives that split regions or false positives that reduce coverage.A marked region generates no prefetches and receives no AGT entry; the table is cleared when EoG is observed.Source: Figure 10 · p. 6, §3.5 · p. 7
3.6 Hardware Overhead
- Proba requires 10.04 KiB of storage and supports PC-Only, PC+Offset, and Offset+Offset trigger features.Its FT and AGT each have 64 entries; each of its three PHTs has 256 entries.Source: §3.6 · p. 7
4 Experimental Setup
The evaluation uses ChampSim traces and compares SMS-based prefetchers under common cache placement, region size, storage, and L1-prefetcher settings. It spans four benchmark suites and single-core and multicore DRAM configurations.
Workloads and simulator
- The evaluation uses ChampSim and simpoint traces from SPECspeed 2017, SPEC CPU2006, Ligra, and CloudSuite.It includes 95, 93, 76, and 120 traces from those suites, respectively, with a 200-million-instruction warmup and simulation window per trace.Source: §4 · p. 8
Experimental configuration
- All prefetchers are evaluated at L2 on 4 KiB regions with comparable storage budgets, and all configurations include a degree-3 IP-stride prefetcher at L1.The implementations are taken from the original authors.Source: §4 · p. 8
DRAM configurations
- Single-core tests use one 2400 MTPS DRAM channel; 2-core and 4-core tests use two 4800 MTPS channels, with two ranks per channel for the 4-core configuration.The multicore configuration is inspired by Gaze.Source: §4 · p. 8
5 Evaluation
Across single-core suites, Proba pairs higher speedups with lower DRAM traffic than competing SMS-based designs; its advantage grows under multicore contention. Ablations and sensitivity tests show how its components and parameters affect this performance–traffic balance.
5.1 Single Core Analysis on SPECspeed 2017
- 6.6% geomean speedup with 8.5% additional DRAM traffic made Proba faster and more traffic-efficient than the compared SMS-based prefetchers on SPECspeed 2017.PMP achieved 5.6% speedup with 28.1% additional traffic; Proba also remained effective across abrupt phase changes in two traces.Source: §5.1 · pp. 8–9
5.2 Alternative Benchmark Suites
- On alternative suites, Proba outperformed Gaze by 1.7% on SPEC CPU2006 with roughly one third of its additional DRAM traffic, and achieved a 5.1% speedup above baseline on CloudSuite.Across CloudSuite workloads, Proba was more accurate and achieved higher coverage than other SMS-based prefetchers; its overall accuracy was highest on the alternative suites, though LLC coverage was sometimes lower.Source: §5.2 · p. 9, Figure 13 · p. 9, Figure 14 · p. 9
5.3 Multicore Performance Analysis
- 7.9% geomean speedup on 4-core CloudSuite was almost double the nearest contender, while Proba achieved 5.7% versus PMP’s -0.3% on 4-core homogeneous SPEC mixes.On 2-core homogeneous mixes, Proba achieved 7.0% versus PMP’s 1.1%; added DRAM traffic from most prefetchers became increasingly detrimental as cores scaled.Source: Figure 15 · p. 9, §5.3 · p. 10, Figure 16 · p. 10
5.4 Ablation Study
- The ablation study identifies dynamic probabilistic updates as crucial to reducing DRAM traffic while maintaining competitive speedup.L2-miss and prefetch-tag-hit training supports accuracy targeting; multi-feature PHTs improve coverage, and marginal-accuracy filtering balances speedup and traffic.Source: §5.4 · p. 10, Figure 17 · p. 10
5.5 Integration with Multi-Prefetcher Setups
- In multi-prefetcher stacks, Proba gave the best performance–traffic trade-off, including 3.8% speedup with 8.7% additional traffic in the Berti-at-L1 configuration.With stride at L1 and Pythia alongside SMS at L2, Proba improved performance by 1.7% over the non-SMS stack with 5.0% traffic overhead.Source: §5.5 · pp. 10–11, Figure 18 · p. 10
5.6 Parameter Sensitivity
- Across SPECspeed 2017, increasing each Jail Table bitmap from 4096 to 16384 bits changed geomean speedup only from 6.6% to 6.7%, while reducing it to 1024 bits hurt selected workloads.Sampling-rate and accuracy-threshold changes also exposed traffic–performance trade-offs, while 1–4 transition-state bits all yielded 6.6% geomean speedup; reasonable PHT-size changes had little speedup effect.Source: §5.6 · p. 11
6 Related Work
Related work spans SMS variants, accuracy–coverage control, and other prefetcher families. Proba builds on SMS-based approaches while addressing pattern updating and aggression control.
Spatial Memory Streaming Prefetchers
- SMS variants differ in trigger features, histories, and update policies, while DSPatch selects accuracy- or coverage-biased patterns using bandwidth utilization.Bingo combines PC+Offset and PC+Address features; Gaze uses Offset+Offset; PMP uses PC-Only and Offset-Only tables.Source: §6 · p. 11
Aggression Control
- Feedback-directed prefetchers estimate accuracy, timeliness, or cache pollution to adjust aggression, while PPF filters inaccurate prefetches and DSPatch guides decisions with table-based accuracy estimates..Source: §6 · p. 11
Other classes of prefetchers
- Other approaches include stride, offset-based, signature-path, neural, temporal, and runahead prefetchers, which exploit different access patterns or histories.The passage characterizes stride prefetchers as low-complexity but limited in coverage.Source: §6 · p. 11
7 Conclusion
Proba combines probabilistic pattern updates, marginal-accuracy aggression control, and multiple trigger features for SMS-based prefetching. Across the evaluation, it achieves higher speedups with substantially lower DRAM traffic than state-of-the-art SMS-based prefetchers.
7 Conclusion
- Proba combines probabilistic pattern updates, marginal-accuracy-based aggression control, and multi-feature PHTs to achieve higher speedups with substantially lower DRAM traffic than state-of-the-art SMS-based prefetchers.Its updates preserve long-term access behavior while avoiding pattern corruption, duplicated storage, and coarse-grained update policies.Source: §7 · p. 11
8 Artifact Appendix
The artifact provides source code and a simulation framework for evaluating Proba and related prefetchers. Its documented reproduction workflow centers on SPECspeed 2017, with additional benchmark traces available for extending the experiments.
8.1 Abstract
- The artifact includes Proba and comparison-prefetcher source code, a modified ChampSim framework, system configuration, and scripts to download SPECspeed 2017 traces and run simulations.It reproduces the paper’s SPECspeed 2017 performance, DRAM traffic, coverage, and accuracy results.Source: §8.1 · p. 12
8.2 Artifact check-list (meta-information)
- The checklist specifies ChampSim, SPECspeed 2017, speedup, normalized DRAM traffic, LLC coverage, and overall prefetch accuracy, with approximately 40 GB disk space and six hours for baseline-and-Proba runs.Reproducing baseline and all evaluated prefetchers is estimated at approximately 21 hours on a 40-core Intel Xeon Platinum 8168.Source: §8.2 · p. 12
8.3 Description
- The code is publicly available on GitHub and Zenodo, and the artifact can be modified to reproduce results on SPEC CPU2006, Ligra, and CloudSuite traces.The documented dependencies include Python 3.9 or later, GCC/G++ 11, GNU Make, and Git; newer compiler versions are not currently supported.Source: §8.3.1 · p. 12, §8.3.3 · p. 12, §8.3.2 · p. 12
8.4 Installation
The installation workflow clones and initializes the Proba artifact, then downloads the required SPECspeed 2017 traces.
8.4 Installation
- Clone the repository and initialize the artifact with the setup script.The instructions use `git clone` followed by `./scripts/setup.sh`.Source: §8.4 · p. 12
- Run the repository setup script after cloning the artifact.Source: §8.4 · p. 12
- Download the required SPECspeed 2017 traces with the provided Python script.Source: §8.4 · p. 12
8.5 Experiment workflow
The workflow runs baseline and Proba simulations, with options to run all evaluated prefetchers; the baseline includes an L1D stride prefetcher and no L2C prefetcher.
8.5 Experiment workflow
- The baseline uses a degree-3 stride prefetcher at L1D and no prefetcher at L2C.Accordingly, “no” means no L2C prefetching, not no prefetching anywhere in the hierarchy.Source: §8.5 · p. 12
- Run the baseline and Proba configurations with the experiment script, or optionally run all evaluated prefetchers.The optional list is no, sms, bingo, dspatch, pmp, gaze, and proba.Source: §8.5.1 · p. 12, §8.5.2 · pp. 12–13
- At 40-way parallelism, each configuration takes about 3 hours, while the complete experiment takes about 21 hours.Fewer available cores require a smaller parallel-job count and increase total execution time.Source: §8.5.1 · p. 12, §8.5.2 · p. 13
- Each simulation produces a text simulator log and a JSON file of statistics.Files are saved under results/spec2017/<prefetcher>/<benchmark>/<trace> with .txt and .json extensions.Source: §8.5.1 · p. 12
8.6 Evaluation and expected results
The result-reporting script provides aggregate prefetcher metrics, including speedup, DRAM traffic, LLC coverage, and accuracy across cache levels. The reproduced Proba aggregate reports a speedup of 1.0659 and DRAM traffic of 1.0845.
8.6 Evaluation and expected results
- Aggregate reporting includes IPC speedup over baseline, normalized DRAM traffic, LLC prefetch coverage, and overall prefetch accuracy.Source: §8.6 · p. 13
- Accuracy is measured across L2C and LLC to support fair comparison with multilevel prefetchers.Source: §8.6 · p. 13
- After simulations finish, run the reporting script for Proba or, optionally, for the evaluated prefetchers.The optional command lists sms, bingo, dspatch, and pmp.Source: §8.6.1 · p. 13
- Proba reports 1.0659 Speedup and 1.0845 DRAM in the aggregate results.The same output lists 0.5088 LLC cov. and 0.8068 Accuracy.Source: §8.6.1 · p. 13
8.7 Experiment customization
The artifact supports changing Proba parameters, simulated processor and cache parameters, and experiment scripts for additional evaluations.
8.7 Experiment customization
- Proba parameters can be changed in prefetcher/proba/proba.h, while processor and cache parameters can be changed in params/baseline.json.Source: §8.7 · p. 13
- The experiment scripts can be modified to evaluate additional workloads, configurations, and prefetchers.Source: §8.7 · p. 13
8.8 Methodology
- The document includes a submission, reviewing, and badging methodology section.Source: §8.8 · p. 13