NNP: A Neural Network Approach to Cache Prefetching Based on Pythia

What is Pythia?

Pythia is a hardware-realizable, light-weight data prefetcher that uses reinforcement learning to generate accurate, timely, and system-aware prefetch requests.

Pythia formulates hardware prefetching as a reinforcement learning task. For every demand request, Pythia observes multiple different types of program context information to take a prefetch decision. For every prefetch decision, Pythia receives a numerical reward that evaluates prefetch quality under the current memory bandwidth utilization. Pythia uses this reward to reinforce the correlation between program context information and prefetch decision to generate highly accurate, timely, and system-aware prefetch requests in the future.

Pythia is presetend at MICRO 2021.

Rahul Bera, Konstantinos Kanellopoulos, Anant V. Nori, Taha Shahroodi, Sreenivas Subramoney, Onur Mutlu, "Pythia: A Customizable Hardware Prefetching Framework Using Online Reinforcement Learning", In Proceedings of the 54th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), 2021

This work is based on the original Pythia project, available at: https://github.com/CMU-SAFARI/Pythia.git

What is NNP?

NNP stands for Neural Network-based Pythia. It utilizes a lightweight shallow neural network to approximate the Q-function, eliminating the need for a table to store the Q-values. Traditional tabular methods(SARSA algorithm) used in Pythia struggle when the state-action space becomes large or continuous. Moreover, the size of the Q-table increases exponentially with the number of states and actions, resulting in high storage overhead. By replacing the Q-table with a shallow neural network, this work achieves a 90% reduction in storage overhead.

About The Framework

Pythia is implemented in ChampSim simulator. The original project have significantly modified the prefetcher integration pipeline in ChampSim to add support to a wide range of prior prefetching proposals mentioned below:

• Stride [Fu+, MICRO'92]
• Streamer [Chen and Baer, IEEE TC'95]
• SMS [Somogyi+, ISCA'06]
• AMPM [Ishii+, ICS'09]
• Sandbox [Pugsley+, HPCA'14]
• BOP [Michaud, HPCA'16]
• SPP [Kim+, MICRO'16]
• Bingo [Bakshalipour+, HPCA'19]
• SPP+PPF [Bhatia+, ISCA'19]
• DSPatch [Bera+, MICRO'19]
• MLOP [Shakerinava+, DPC-3'19]
• IPCP [Pakalapati+, ISCA'20]

Most of the prefetchers (e.g., SPP [1], Bingo [2], IPCP [3]) reuse codes from 2nd and 3rd data prefetching championships (DPC). Others (e.g., AMPM [4], SMS [5]) are implemented from scratch and shows similar relative performance reported by previous works.

Prerequisites

The infrastructure has been tested with the following system configuration: * G++ v6.3.0 20170516 * CMake v3.20.2 * md5sum v8.26 * Perl v5.24.1 * LibTorch(PyTorch C++ API) v2.7.0.dev20250131+cpu

Installation

1. Install necessary prequisites bash sudo apt install perl
2. Clone the GitHub repo

bash git clone https://github.com/wzcwd/Neural-Network-Pythia.git 2. Clone the bloomfilter library inside Pythia home directory

bash cd Pythia git clone https://github.com/mavam/libbf.git libbf 3. Build bloomfilter library. This should create the static libbf.a library inside build directory

```bash
cd libbf
mkdir build && cd build
cmake ../
make clean && make
```

1. Download LibTorch inside Pythia home directory, it should give you libtorch-shared-with-deps-latest.zip

bash cd Pythia wget https://download.pytorch.org/libtorch/nightly/cpu/libtorch-shared-with-deps-latest.zip 5. Uzip libtorch-shared-with-deps-latest.zip, it should give you a libtorch directory inside Pythia home directory

bash unzip libtorch-shared-with-deps-latest.zip 6. Build Pythia for single/multi core using build script. This should create the executable inside bin directory.

bash cd $PYTHIA_HOME # ./build_champsim.sh <l1_pref> <l2_pref> <llc_pref> <ncores> ./build_champsim.sh multi multi no 1 Please use build_champsim_highcore.sh to build ChampSim for more than four cores.

1. Set appropriate environment variables as follows:

   bash source setvars.sh export LD_LIBRARY_PATH=$PYTHIA_HOME/libtorch/lib:$LD_LIBRARY_PATH

Preparing Traces

[Update: Dec 18, 2024] The trace will be downloaded in two phases: (1) all traces, except Ligra and PARSEC workloads, will be downloaded using the automated script, and (2) the Ligra and PARSEC traces needs to be downloaded manually from Zenodo repository mentioned below.

1. Use the download_traces.pl perl script to download all traces, except Ligra and PARSEC.

   bash mkdir $PYTHIA_HOME/traces/ cd $PYTHIA_HOME/scripts/ perl download_traces.pl --csv artifact_traces.csv --dir ../traces/

   Note: The script should download 138 traces. Please check the final log for any incomplete downloads.

2. Once the trace download completes, please verify the checksum as follows. Please make sure all traces pass the checksum test.

   bash cd $PYTHIA_HOME/traces md5sum -c ../scripts/artifact_traces.md5

3. Download the Ligra and PARSEC traces from these repositories:

   • Ligra: https://doi.org/10.5281/zenodo.14267977
   • PARSEC 2.1: https://doi.org/10.5281/zenodo.14268118

4. If the traces are downloaded in some other path, please change the full path in experiments/MICRO21_1C.tlist and experiments/MICRO21_4C.tlist accordingly.

More Traces

• Our simulation infrastructure is completely compatible with all prior ChampSim traces used in CRC-2 and DPC-3. One can also convert the CVP-2 traces (courtesy of Qualcomm Datacenter Technologies) to ChampSim format using the following converter. The traces can be found in the follwing websites:
  • CRC-2 traces: http://bit.ly/2t2nkUj
  • DPC-3 traces: http://hpca23.cse.tamu.edu/champsim-traces/speccpu/
  • CVP-2 traces: https://www.microarch.org/cvp1/cvp2/rules.html

Experimental Workflow

Our experimental workflow consists of two stages: (1) launching experiments, and (2) rolling up statistics from experiment outputs.

Launching Experiments

1. To create necessary experiment commands in bulk, we will use scripts/create_jobfile.pl
2. create_jobfile.pl requires three necessary arguments:
   • exe: the full path of the executable to run
   • tlist: contains trace definitions
   • exp: contains knobs of the experiements to run

3. Create experiments as follows. Please make sure the paths used in tlist and exp files are appropriate.

   bash cd $PYTHIA_HOME/experiments/ perl ../scripts/create_jobfile.pl --exe $PYTHIA_HOME/bin/perceptron-multi-multi-no-ship-1core --tlist nnp_1C.tlist --exp nnp_1C.exp --local 1 > jobfile.sh

4. Go to a run directory (or create one) inside experiements to launch runs in the following way: bash cd nnp_experiments_1C source ../jobfile.sh

5. If you have slurm support to launch multiple jobs in a compute cluster, please provide --local 0 to create_jobfile.pl

Rolling-up Statistics

1. To rollup stats in bulk, we will use scripts/rollup.pl
2. rollup.pl requires three necessary arguments:
   • tlist
   • exp
   • mfile: specifies stat names and reduction method to rollup

3. Rollup statistics as follows. Please make sure the paths used in tlist and exp files are appropriate.

   bash cd nnp_experiments_1C perl ../../scripts/rollup.pl --tlist ../nnp_1C.tlist --exp ../nnp_1C.exp --mfile ../rollup_1C_base_config.mfile > rollup.csv

4. Export the rollup.csv file in you favourite data processor (Python Pandas, Excel, Numbers, etc.) to gain insights.

Code Walkthrough

Pythia was code-named Scooby (the mistery-solving dog) during the developement. So any mention of Scooby anywhere in the code inadvertently means Pythia.

• The top-level files for Pythia are prefetchers/scooby.cc and inc/scooby.h. These two files declare and define the high-level functions for Pythia (e.g., invoke_prefetcher, register_fill, etc.).
• The released version of Pythia has two types of RL engine defined: basic and featurewise. They differ only in terms of the QVStore organization (please refer to our paper to know more about QVStore). The QVStore for basic version is simply defined as a two-dimensional table, whereas the featurewise version defines it as a hierarchichal organization of multiple small tables. The implementation of respective engines can be found in src/ and inc/ directories.
• This project creates a novel RL engine in src/ directory: learningengineneural_network.cc, For each demand request, this learning engineuses extracted features and state to select the action with the highest Q-value output by the neural network for prefetching. The basic configuration has a single hidden layer network with 8 neurons, 2 features, 16 actions.
• inc/feature_knowledge.h and src/feature_knowldege.cc define how to compute each program feature from the raw attributes of a deamand request. If you want to define your own feature, extend the enum FeatureType in inc/feature_knowledge.h and define its corresponding process function.
• inc/util.h and src/util.cc contain all hashing functions used in our evaluation. Play around with them, as a better hash function can also provide performance benefits.

Citation

If you use this framework, please cite the original paper: @inproceedings{bera2021, author = {Bera, Rahul and Kanellopoulos, Konstantinos and Nori, Anant V. and Shahroodi, Taha and Subramoney, Sreenivas and Mutlu, Onur}, title = {{Pythia: A Customizable Hardware Prefetching Framework Using Online Reinforcement Learning}}, booktitle = {Proceedings of the 54th Annual IEEE/ACM International Symposium on Microarchitecture}, year = {2021} }