1 of 46

Performance-Driven Composite Prefetching with Bandits

Charles Block, Pedro Palacios Almendros, Abraham Farrell, Gerasimos Gerogiannis, Josep Torrellas

University of Illinois Urbana-Champaign

coblock2@illinois.edu

​

February 1, 2026

1

2 of 46

Prefetching Feedback Mechanisms

  • Many prefetchers collect feedback to tune their actions
    • Pythia and Berti both use accuracy/timeliness information

​

  • Complex relationship between heuristics and performance
    • Tradeoff between accuracy and coverage changes between workloads

​

  • Individual prefetchers struggle to use performance as feedback
    • Performance is a very coarse-grained metric
    • Prefetchers must make fine-grained decisions (stride offsets, etc.)

​

2

3 of 46

Ensembles of Prefetchers

  • Extract the benefits of many types of prefetchers

​

  • Offers coarse-grained decisions
    • Which prefetchers should be active in a workload?
    • Which prefetchers should be prioritized?

​

  • Performance-driven control becomes feasible

​

3

"Arm Neoverse V2 platform", Hot Chips 2023

4 of 46

Multi-Armed Bandits

4

5 of 46

Multi-Armed Bandits

5

Which machine pays out most?

6 of 46

Multi-Armed Bandits

6

Images by bizmac - IMG_7080, CC BY 2.0, https://commons.wikimedia.org/w/index.php?curid=54615179; and by Naomi Andrzejeski - https://commons.wikimedia.org/wiki/File:Proof_Coin_-_1_Penny,_Australia,_1949.jpg

7 of 46

Multi-Armed Bandits

7

Images by bizmac - IMG_7080, CC BY 2.0, https://commons.wikimedia.org/w/index.php?curid=54615179; and by Naomi Andrzejeski - https://commons.wikimedia.org/wiki/File:Proof_Coin_-_1_Penny,_Australia,_1949.jpg

1

0

3

0

2

8 of 46

Multi-Armed Bandits

8

Images by bizmac - IMG_7080, CC BY 2.0, https://commons.wikimedia.org/w/index.php?curid=54615179; and by Naomi Andrzejeski - https://commons.wikimedia.org/wiki/File:Proof_Coin_-_1_Penny,_Australia,_1949.jpg

1

0

3

0

2

9 of 46

Multi-Armed Bandits

9

Images by bizmac - IMG_7080, CC BY 2.0, https://commons.wikimedia.org/w/index.php?curid=54615179; and by Naomi Andrzejeski - https://commons.wikimedia.org/wiki/File:Proof_Coin_-_1_Penny,_Australia,_1949.jpg

1

0

3

0

2

10 of 46

Multi-Armed Bandits

10

Images by bizmac - IMG_7080, CC BY 2.0, https://commons.wikimedia.org/w/index.php?curid=54615179; and by Naomi Andrzejeski - https://commons.wikimedia.org/wiki/File:Proof_Coin_-_1_Penny,_Australia,_1949.jpg

1

0

1.5

0

2

11 of 46

Multi-Armed Bandits

11

Images by bizmac - IMG_7080, CC BY 2.0, https://commons.wikimedia.org/w/index.php?curid=54615179; and by Naomi Andrzejeski - https://commons.wikimedia.org/wiki/File:Proof_Coin_-_1_Penny,_Australia,_1949.jpg

1

0

1.5

0

2

12 of 46

Multi-Armed Bandits

12

Images by bizmac - IMG_7080, CC BY 2.0, https://commons.wikimedia.org/w/index.php?curid=54615179; and by Naomi Andrzejeski - https://commons.wikimedia.org/wiki/File:Proof_Coin_-_1_Penny,_Australia,_1949.jpg

1

0

1.5

0

2

13 of 46

Multi-Armed Bandits

13

Images by bizmac - IMG_7080, CC BY 2.0, https://commons.wikimedia.org/w/index.php?curid=54615179; and by Naomi Andrzejeski - https://commons.wikimedia.org/wiki/File:Proof_Coin_-_1_Penny,_Australia,_1949.jpg

1

0

1.5

0

2.5

14 of 46

Micro-Armed Bandit for Prefetching

14

Images by bizmac - IMG_7080, CC BY 2.0, https://commons.wikimedia.org/w/index.php?curid=54615179; and by Naomi Andrzejeski - https://commons.wikimedia.org/wiki/File:Proof_Coin_-_1_Penny,_Australia,_1949.jpg

1

0

1.5

0

2.5

Stream

Stride

SMS

Stream

Stride

SMS

Stream

Stride

SMS

Stream

Stride

SMS

Stream

Stride

SMS

15 of 46

Micro-Armed Bandit for Prefetching

15

1

0

1.5

0

2.5

Stream

Stride

SMS

Stream

Stride

SMS

Stream

Stride

SMS

Stream

Stride

SMS

Stream

Stride

SMS

IPC=2.55

16 of 46

Micro-Armed Bandit for Prefetching

16

Gerogiannis & Torrellas, "Micro-Armed Bandit: Lightweight & Reusable Reinforcement Learning for Microarchitecture Decision-Making," Micro 2023

17 of 46

Micro-Armed Bandit for Prefetching

17

Gerogiannis & Torrellas, "Micro-Armed Bandit: Lightweight & Reusable Reinforcement Learning for Microarchitecture Decision-Making," Micro 2023

18 of 46

Micro-Armed Bandit for Prefetching

18

Gerogiannis & Torrellas, "Micro-Armed Bandit: Lightweight & Reusable Reinforcement Learning for Microarchitecture Decision-Making," Micro 2023

19 of 46

Micro-Armed Bandit for Prefetching

19

Gerogiannis & Torrellas, "Micro-Armed Bandit: Lightweight & Reusable Reinforcement Learning for Microarchitecture Decision-Making," Micro 2023

20 of 46

Micro-Armed Bandit for Prefetching

20

Gerogiannis & Torrellas, "Micro-Armed Bandit: Lightweight & Reusable Reinforcement Learning for Microarchitecture Decision-Making," Micro 2023

21 of 46

The Multi-Core Problem

21

22 of 46

The Multi-Core Problem

22

CPU

L2

RL

CPU

L2

RL

CPU

L2

RL

CPU

L2

RL

LLC

Memory

Block et al., "Micro-MAMA: Multi-Agent Reinforcement Learning for Multicore Prefetching," Micro 2025

23 of 46

The Multi-Core Problem

23

CPU

L2

RL

CPU

L2

RL

CPU

L2

RL

CPU

L2

RL

LLC

Memory

Block et al., "Micro-MAMA: Multi-Agent Reinforcement Learning for Multicore Prefetching," Micro 2025

24 of 46

Aggressiveness Grows with Cores

24

Most become less aggressive when resources are scarce

Bandit becomes more aggressive when resources are scarce

Block et al., "Micro-MAMA: Multi-Agent Reinforcement Learning for Multicore Prefetching," Micro 2025

25 of 46

Micro-MAMA

  • We address this with Micro-MAMA
    • A central agent supervises the system
    • Pushes prefetcher agents towards better system-wide equilibria

25

Block et al., "Micro-MAMA: Multi-Agent Reinforcement Learning for Multicore Prefetching," Micro 2025

26 of 46

The Micro-MAMA Architecture

26

Config + Perf

Config + Perf

Config + Perf

Config + Perf

Measure Perf

27 of 46

The Micro-MAMA Architecture

27

Measure Perf

Compute System-Level Perf & Update Reward Tables

28 of 46

The Micro-MAMA Architecture

28

Measure Perf

Compute System-Level Perf & Update Reward Tables

Choose New Config

29 of 46

Micro-MAMA

  • Records joint-actions in a Joint-Action Value Cache

29

Block et al., "Micro-MAMA: Multi-Agent Reinforcement Learning for Multicore Prefetching," Micro 2025

Which action?

How many times?

How performant?

30 of 46

Micro-MAMA

  • Records joint-actions in a Joint-Action Value Cache
  • A Bandit-like Arbiter chooses between
    • Letting local prefetcher ensembles act independently
    • Enforcing a previously-observed joint action on all local prefetchers

30

Block et al., "Micro-MAMA: Multi-Agent Reinforcement Learning for Multicore Prefetching," Micro 2025

31 of 46

A New Reward Function

  • Ideally, the reward should be the desired performance metric
    • In DPC4: harmonic mean of core speedups over 1C Berti+Pythia

​

  • However, it is difficult to estimate this at runtime
    • How much slower does multicore make this workload?
    • How fast would this run if Pythia was used?

​

  • We use a simpler reward for Micro-MAMA: Geomean IPC
    • We also make this a small part of each local agent's reward

31

32 of 46

The Full Prefetcher Selection

32

L1

L2

LLC

Berti

Next-Line

Stream

Stride

SMS

BOP

"as-is"

33 of 46

The Full Prefetcher Selection

33

34 of 46

Our Arms

34

35 of 46

Our Arms

35

ON/OFF

36 of 46

Our Arms

36

Control prefetcher aggressiveness by varying degree

37 of 46

Performance

  • AI/ML benefits from very aggressive streaming
  • Sub-optimal arm selection for Google

37

38 of 46

Performance

  • Underperform the baseline in multicore
    • Likely due to limited selection of low-aggressiveness arms

38

39 of 46

Multi-Core Benefit of Micro-MAMA

  • Micro-MAMA improves on Bandit in all MC categories
    • Without coordination, local agents�over-compete for resources

​

  • Global coordination allows better�resources sharing and prioritizes�workloads with higher sensitivity

​

39

40 of 46

Design Space Exploration

  • No success at automating arm selection with
    • Bayesian optimization (and several similar methods)
    • Evolutionary algorithms
  • Nothing outperformed random search

40

41 of 46

Design Space Exploration

  • No success at automating arm selection with
    • Bayesian optimization (and several similar methods)
    • Evolutionary algorithms
  • Nothing outperformed random search
  • In the end, humans chose which arms to provide to Bandit

41

42 of 46

Design Space Exploration

  • We still believe that automated methods of selecting arms are necessary for achieving Bandit/Micro-MAMA's full potential

​

  • Traditional autotuning algorithms are not well-suited to the highly-categorical nature of this problem

​

  • Long simulation times (esp. multicore) make iterative processes very time-consuming

​

42

43 of 46

Conclusion

  • We present a performance-driven L2 prefetching solution using multi-armed bandit models for ensemble control

​

  • System-level control like Micro-MAMA is crucial for these systems to perform well in multicore

​

  • Design space exploration for these systems remains challenging and an interesting future research direction

43

44 of 46

Performance-Driven Composite Prefetching with Bandits

Charles Block, Pedro Palacios Almendros, Abraham Farrell, Gerasimos Gerogiannis, Josep Torrellas

University of Illinois Urbana-Champaign

coblock2@illinois.edu

​

February 1, 2026

44

45 of 46

45

46 of 46