Pythia: A Customizable Hardware Prefetching Framework Using Online Reinforcement Learning

1 INTRODUCTION

• Prefetchers identify recurring memory-access patterns by associating them with program context features, but different features fit different workloads.Bingo’s region-based features provide more coverage than SPP in some workloads, while SPP’s sequence-of-deltas feature better fits GemsFDTD’s regular within-page accesses.Source: §1 · pp. 1–2
• Prior prefetchers often rely on one program feature, so their performance varies with workload patterns; system-unaware overpredictions can be especially costly when bandwidth is scarce.Bingo improves performance by 6.4% over no prefetching in PARSEC-Canneal but loses 1.9% in Ligra-CC, where each overprediction wastes more precious bandwidth.Source: §1 · p. 2
• Prior prefetchers’ rigid design-time choices prevent online changes to the feature they exploit or the objective they target.The paper identifies adapting to varying workloads and system configurations as the motivation for such customization.Source: §1 · p. 2
• Pythia is designed to learn from multiple program features and system feedback, while configuration registers can change its features or prefetch objective without changing the underlying hardware.The authors describe a hardware implementation using no more complex structures than simple tables.Source: §1 · pp. 2–3
• Pythia formulates hardware prefetching as reinforcement learning: demand-request features form the state, and each prefetch action receives a reward for accuracy and timeliness under system feedback.This paper demonstrates system-level feedback using memory bandwidth usage.Source: §1 · p. 2

Results Summary

• Pythia outperforms MLOP and Bingo by 3.4% and 3.8% in single-core and 7.7% and 9.6% in twelve-core configurations.In a bandwidth-constrained server-like configuration, it outperforms MLOP and Bingo by 16.9% and 20.2%. Reward changes provide up to 7.8% (1.9% on average) more performance improvement across Ligra workloads; synthesis reports 1.03% area and 0.37% power overhead over a 4-core desktop-class processor.Source: §1 · p. 3

2.1 Reinforcement Learning

• At each timestep, an RL agent observes the environment’s state, takes an action, and receives a reward that encodes its objective.The environment transitions after the action; the agent seeks a policy that maximizes cumulative reward.Source: §2.1 · p. 3
• Q-values estimate cumulative reward for state-action pairs, and agents update them to improve their policy over time.An epsilon-greedy policy balances exploiting the highest-valued action with occasional random exploration.Source: §2.1 · pp. 3–4

2.2 Why is RL a Good Fit for Prefetching?

• Prefetching requires trading off coverage and accuracy according to system impact, making RL’s adaptive learning in a complex state space a fit.The paper names memory bandwidth usage as one system impact that can guide the trade-off.Source: §2.2 · p. 4
• RL agents can learn online from rewards without an expensive offline training phase, matching prefetching’s need to adapt to changing workloads and system conditions.Source: §2.2 · p. 4
• The paper contrasts RL with neural networks, LSTMs, and GNNs, whose model sizes and inference computation can make hardware implementation difficult.It says its RL-based model can make predictions quickly and be relatively easily adopted in a real processor.Source: §2.2 · p. 4

3 PYTHIA: KEY IDEA

• For each demand request, Pythia observes processor and memory-system state, chooses whether and where to prefetch, and receives a reward that accounts for accuracy, timeliness, and system feedback.This paper uses memory bandwidth usage as system-level feedback; the framework can incorporate other types.Source: §3 · p. 4

3.1 Formulation of the RL-based Prefetcher

• Pythia’s state is a fixed-dimension vector of configurable program features drawn from control-flow and data-flow information.Examples include load or branch PCs, cacheline addresses, page numbers, offsets, and access histories; the feature count is fixed at design time due to storage limits.Source: §3.1 · p. 4
• Pythia’s action selects a prefetch offset from candidate deltas; zero means no prefetch, and offsets are limited to the triggering request’s physical page.For 4KB pages and 64B cachelines, the stated range is [−63, 63].Source: §3.1 · pp. 4–5
• Pythia rewards timely and late hits, lost coverage, inaccurate prefetches, and no-prefetch decisions, with reward levels guiding accuracy, timeliness, page boundaries, and bandwidth-aware strategy.Reward values can be configured, including through the paper’s automated method.Source: §3.1 · p. 5

4.1 RL-based Prefetching Algorithm

• For each demand request, Pythia selects a high-Q prefetch action from the request’s feature state, records it in the Evaluation Queue, and later updates its Q-value using the assigned reward and SARSA.The queue retains action information because usefulness may not be known when the action is taken.Source: §4 · p. 5, §4.1 · pp. 5–6

4.2.1 Organization of QVStore.

• QVStore partitions values by feature into vaults, queries the feature-action values, and takes their maximum as the state-action value; adding vaults supports higher-dimensional state vectors.This avoids implementing a monolithic table whose size grows exponentially with feature width.Source: §4.2.1 · pp. 6–7
• Each vault uses multiple hashed planes to store partial feature-action values, which are summed for retrieval; tile coding shares values among similar features while reducing sharing across widely different ones.A shifted feature value is hashed to an index in each plane before the partial values are retrieved.Source: §4.2.1 · p. 7

4.2.2 Pipelined Organization of QVStore Search.

• The QVStore search is pipelined across five stages, with partial-value summation setting throughput; pipelining addresses the search’s impact on prediction latency.The stages compute plane indices, retrieve and sum partial values, combine feature values, and update the maximum across actions.Source: §4.2.2 · p. 7, Figure 6 · p. 7

4.2.3 Assigning Rewards and Updating Q-values

• Rewards distinguish accurate and timely or late prefetches, unused prefetches, and no-prefetch or out-of-page actions, with some reward levels conditioned on memory bandwidth usage.An address match during queue residency is classified as timely or late according to whether the prefetch has filled.Source: §4.2.3 · pp. 7–8

4.3.1 Feature Selection.

• Automated exploration selects PC+Delta and the last four deltas as the basic state vector; Pythia’s RL strategy increases coverage while maintaining high accuracy, unlike simply combining Bingo and SPP.The comparison passage reports that the hybrid combines their overpredictions, which can degrade performance in resource-constrained systems.Source: §4.3.1 · p. 8

4.3 Automated Design-Space Exploration

• The design-space process prunes actions with no significant measured impact and tunes reward levels and RL hyperparameters to choose the configuration with the highest average performance gain.Tuning tests 1,000 configurations on a 10-trace suite, then evaluates the top 25 across single-core traces.Source: §4.3.3 · p. 8, §4.3.2 · p. 8, §4.3 · p. 8

4.4 Storage Overhead

• Pythia requires 25.5KB of metadata storage and differs from CP through bandwidth-aware rewards, hardware-derived features, configurable objectives, and an RL design that weighs longer-term consequences.The reported storage comprises 24KB for QVStore and 1.5KB for the Evaluation Queue; hardware-derived features require no software changes.Source: §4.4 · p. 8, §4.5 · pp. 8–9

5 METHODOLOGY

• Evaluation combines ChampSim simulation on a Skylake-like processor supporting up to 12 cores with Chisel RTL synthesis and functional verification for area and power overhead measurement.Single-core runs warm up for 100M instructions and simulate 500M; multi-core runs use 50M for warmup and 150M for simulation.Source: §5 · p. 9, Table 5 · p. 9

5.1 Workloads

• The workload set contains 150 traces spanning 50 memory-intensive workloads from SPEC CPU2006/2017, PARSEC, Ligra, and Cloudsuite; traces below 3 baseline LLC MPKI are excluded.Multi-core mixes include both homogeneous and heterogeneous combinations of single-core traces.Source: §5.1 · p. 9, Table 6 · p. 9

5.2 Prefetchers

• Pythia is compared with SPP, SPP+PPF, SPP+DSPatch, Bingo, and MLOP, whose implementations are author-sourced and fine-tuned in the evaluation environment.Additional comparisons include commercial-style multi-level prefetchers and IPCP, with a PC-based stride prefetcher at L1 for multi-level tests.Source: §5.2 · p. 9, Table 7 · p. 10

6.1 Coverage and Overprediction in Single-core

• In single-core systems, Pythia provides 6.9%, 8.8%, and 14% higher coverage than MLOP, Bingo, and SPP, while generating 83.8%, 78.2%, and 3.6% fewer overpredictions.Coverage and overprediction are measured at the LLC–main memory boundary.Source: §6.1 · p. 10, Figure 7 · p. 10

6.2 Performance Overview

• Across single- to 12-core systems, Pythia consistently outperforms MLOP, Bingo, and SPP, with its performance advantage increasing as core count rises.In single-core systems it exceeds MLOP, Bingo, SPP, and SPP+PPF by 3.4%, 3.8%, 4.3%, and 1.02%; in 12-core systems the margins are 7.7%, 9.6%, 6.9%, and 5.2%.Source: §6.2.1 · p. 10, Figure 8 · p. 11
• Pythia outperforms competing prefetchers across DRAM bandwidth and LLC-size configurations, and bandwidth awareness preserves gains when bandwidth is low.At 150 MTPS it exceeds MLOP, Bingo, SPP, and SPP+PPF by 16.9%, 20.2%, 3.7%, and 9.5%; for 256KB LLC, the corresponding margins are 3.6%, 5.1%, 2.7%, and 1.2%. Stride+Pythia also beats Stride+Streamer and IPCP by 6.5% and 14.2% at 150 MTPS. Bandwidth-oblivious Pythia loses up to 4.6% on average at 150–600 MTPS, but performs similarly at 1200–9600 MTPS.Source: §6.2.2 · p. 10, §6.2.3 · p. 10, §6.2.4 · p. 10

6.3 Performance Analysis

• In workload-category comparisons, Pythia beats MLOP, Bingo, and SPP by 3.4%, 3.8%, and 4.3% in single-core and by 5.8%, 8.2%, and 6.5% in four-core systems.It also exceeds the five-prefetcher combination by 1.4% in single-core and 4.9% in four-core systems; adding prefetchers to stride+SPP in the four-core system lowers overall performance gain as overpredictions add up.Source: §6.3.1 · p. 10, §6.3.2 · p. 11, Figure 9 · p. 11

6.4 Performance on Unseen Traces

• On 500 untuned traces, Pythia outperforms MLOP, Bingo, and SPP by 8.3%, 3.5%, and 4.9% in single-core and by 9.7%, 5.4%, and 6.7% in four-core systems.Each trace has at least 3 LLC MPKI in the no-prefetching baseline.Source: §6.4 · p. 11, Figure 12 · p. 11

6.5 Understanding Pythia Using a Case Study

• In 459.GemsFDTD-1320B, offsets +23 and +11 account for nearly 72% of Pythia’s offset selections, with Q-values favoring those offsets for their corresponding PC+Delta features.The trace analysis links the +23 offset to the first load from PC 0x436a81 and the +11 offset to PC 0x4377c5.Source: §6.5 · p. 12, Figure 13 · p. 12

6.6 Performance Benefits via Customization

• Changing reward levels yields up to 7.8% (2.0% on average) higher Ligra performance than basic Pythia, while feature selection yields up to 5.1% (1.5% on average) improvement on SPEC CPU2006.The stricter Ligra configuration uses configuration registers without hardware changes; feature optimization selects the best one- or two-feature combination per workload from 32 supported features.Source: §6.6.1 · p. 12, §6.6.2 · p. 12, Figure 15 · p. 12

6.7 Overhead Analysis

• Pythia adds 1.03% area and 0.4% power overhead to a four-core desktop-class Skylake processor, and 1.33% area and 0.75% power overhead to a 28-core server-class Skylake processor.Pythia uses 0.33 mm^2 and 55.11 mW per core; QVStore accounts for 90.4% of its area and 95.6% of its power.Source: §6.7 · p. 13, Table 8 · p. 13

Traditional Prefetchers

• Precomputation-based prefetchers execute program code to generate future requests and can be accurate without recognizable access patterns, but usually have high design complexity.Pythia instead finds patterns in past memory requests.Source: §7 · p. 13
• Temporal prefetchers use previously observed address sequences but often require multi-megabyte metadata, whereas Pythia requires 25.5KB of storage.Spatial prefetchers learn cacheline deltas or spatial bit-patterns and generally use less storage than temporal prefetchers.Source: §7 · p. 13

Machine Learning (ML) in Computer Architecture

• Compared with prior ML-based prefetchers, Pythia learns from multiple program features and system feedback, supports online customization, and has low hardware overhead.Other ML applications in architecture also include adaptive algorithms and design-space exploration.Source: §7 · p. 13

8 CONCLUSION

• Pythia formulates customizable prefetching as reinforcement learning, learning from multiple program features and system-level feedback to predict memory accesses.The authors propose that autonomous, data-driven prefetchers could reduce architects’ burden in designing sophisticated mechanisms.Source: §8 · p. 13

A.1 Abstract

• The artifact supplies Pythia source code and instructions to reproduce key performance results using ChampSim.It identifies workload-category performance, coverage and overprediction, varying-bandwidth performance, and four-core performance as key results.Source: §A.1 · p. 16, §A.3.1 · p. 16

A.3 Description

• The artifact requires a general-purpose CPU and 52 GB of disk space; its documented software requirements include GCC 6.3.0 and Perl 5.24.1.The artifact checklist estimates 3–4 hours for experiments on a 480-core compute cluster.Source: §A.1 · p. 16, §A.2 · p. 16, §A.3.2 · p. 16

A.3.3 Software Dependencies

• The ChampSim implementation supports traces from prior cache-replacement, data-prefetching, and value-prediction championships, and includes new Ligra and PARSEC-2.1 traces.Source: §A.3.4 · p. 16

A.4 Installation

• Clone the Pythia repository, then clone and build the Bloomfilter library inside the Pythia directory.Source: §A.4 · p. 16
• Build ChampSim configurations for single-core and four-core runs using the supplied build script.Source: §A.4 · p. 16

A.5 Experiment Workflow

• The workflow recommends consulting the README to learn about the scripts used in the experiments.The section introduces steps for generating and executing the required experiments.Source: §A.5 · p. 16

A.5.1 Preparing Traces.

• Download the necessary traces with the provided `download_traces.pl` command.The instructions create a traces directory and run the script with `artifact_traces.csv` as its input.Source: §A.5.1 · p. 16
• If traces are stored elsewhere, update their full paths in `MICRO21_1C.tlist` and `MICRO21_4C.tlist`.For bulk experiment launches, the appendix recommends a compute cluster with Slurm support and specifies `–local 0`.Source: §A.5.1 · p. 16, §A.5.2 · p. 16

A.5.2 Launching Experiments.

• Launch single-core and four-core experiments using the provided job-file commands and their respective experiment lists.The instructions run the generated job file from the corresponding `experiments_1C` or `experiments_4C` directory.Source: §A.5.2 · pp. 16–17

A.5.3 Rolling-up Statistics.

• Run `automate_rollup.sh` to collect experiment statistics into three CSV files for evaluation.The section identifies these files as inputs for the appendix’s evaluation.Source: §A.5.3 · p. 17

A.6 Evaluation

• The evaluation measures performance, coverage, and overprediction for single-core baseline experiments, but only performance in bandwidth-scaling and four-core experiments.An Excel template with formulas, pivot tables, and charts can process the CSVs; another data processor such as pandas can also reproduce the results.Source: §A.6 · p. 17

• At 150-MTPS bandwidth, Pythia is expected to improve performance by 0.89% over no prefetching, while MLOP underperforms that baseline by 16%.Source: §A.7 · p. 17
• At 9600-MTPS bandwidth, Pythia is expected to improve performance by 22.7% over no prefetching, while MLOP achieves 19.5%.Source: §A.7 · p. 17
• 30% performance improvement over no prefetching is expected for Pythia in four-core experiments, versus 24% for MLOP.Source: §A.7 · p. 17

A.8 Experiment Customization •

• Change the configuration ini files to customize prefetchers, or edit experiment files to run new prefetcher combinations.Additional experiment files are available in the `experiments/extra` directory.Source: §A.8 · p. 17

A.9 Methodology

• The appendix labels a section on submission, reviewing, and badging methodology.Source: §A.9 · p. 17

B.1 Detailed Performance Analysis

• Across 150 single-core traces Pythia beats no prefetching except one, and across 272 four-core mixes it beats the baseline in all but one.It outperforms competing prefetchers especially on irregular workloads, while Bingo does better on regular streaming workloads such as libquantum.Source: Figure 17 · p. 17, §B.1 · pp. 17–18, Figure 18 · p. 18

B.2 Performance with Different Features

• Feature combinations shift Pythia’s performance improvement from 20.7% to 22.4%, coverage from 66.2% to 71.5%, and overprediction from 32.2% to 26.7%.The authors select the combination with the highest performance gain as the basic configuration.Source: Figure 19 · p. 18, §B.2 · p. 18

B.3 Performance Sensitivity to Hyperparameters

• Changing the exploration rate from 0.002 to 1.0 reduces performance improvement by 16.0%, while Pythia performs best at a learning rate of α=0.0065.Performance also declines when the learning rate is either increased or decreased from its optimal value.Source: Figure 20 · p. 18, §B.3 · p. 18

B.4 Comparison to the Context Prefetcher

• Pythia outperforms the hardware-context Context Prefetcher by 5.3% in single-core and 7.6% in four-core configurations.The authors attribute the advantage mainly to accounting for memory bandwidth in prefetch decisions and making far-sighted rather than myopic predictions.Source: Figure 21 · p. 18, §B.4 · p. 18

B.5 Comparison to the IBM POWER7 Adaptive Prefetcher

• Pythia outperforms the IBM POWER7 adaptive prefetcher by 4.5% in single-core, 6.5% in four-core, and 6.1% in eight-core systems.The authors connect its single-core advantage to handling address patterns beyond streaming and stride patterns.Source: §B.5 · pp. 18–19, Figure 22 · p. 19

B.6 Performance Sensitivity to Number of Warmup Instructions

• With 100M warmup instructions, Pythia beats MLOP, Bingo, and SPP by 3.4%, 3.8%, and 4.4%; with no warmup, the respective gains are 2.8%, 3.7%, and 4.2%.Pythia continues to outperform these prefetchers across the tested warmup configurations.Source: Figure 23 · p. 19, §B.6 · p. 19