1 of 37

SPPAM:

Signature

Pattern

Prediction and

Access-

Map Prefetcher

Maccoy Merrell, Lei Wang, Stavros Kalafatis, Paul V. Gratz

TEXAS A&M UNIVERSITY

2 of 37

Outline

Introduction
Background and Motivation

Design
Evaluation

Conclusion

AMPM
SPP

Single Core
Multi Core

TEXAS A&M UNIVERSITY

3 of 37

Introduction

[1] Lei Wang, Chia-Hang Lee, Maccoy Merrell, Gino Chacon, Daniel A. Jiménez, and Paul V. Gratz. 2025. R-Max: A Method for

Approximating the Benefit of Ideal Prefetching and Replacement Policy. IEEE Computer Architecture Letters 24, 2(2025),

293–296. doi:10.1109/LCA.2025.3611316

TEXAS A&M UNIVERSITY

4 of 37

Introduction

[2] Yasuo Ishii, Mary Inaba, and Kei Hiraki. 2011. Access map pattern matching for high performance data cache prefetch. Journal of Instruction-

Level Parallelism 13,2011 (2011), 1–24.

[3] Magnus Bruce. 2023. Arm Neoverse V2 platform: Leadership Performance and Power Efficiency for Next Generation Cloud Computing, ML and

HPC Workloads.IEEE.

[4] Stephan G Meier, Gerard R Williams, Hari S Kannan, and Pavlos Konas. 2015.Access map-pattern match based prefetch unit for a processor.

[5] Jinchun Kim, Seth H. Pugsley, Paul V. Gratz, A. L. Narasimha Reddy, Chris Wilk-erson, and Zeshan Chishti. 2016. Path confidence based

lookahead prefetching. InThe 49th Annual IEEE/ACM International Symposium on Microarchitecture (Taipei,Taiwan) (MICRO-49). IEEE Press,

Taipei, Taiwan, Article 60, 12 pages.

TEXAS A&M UNIVERSITY

5 of 37

Introduction

AMPM relies on hard-coded pattern detection which fails to adapt to complex workloads but provides consistent behavior

SPP/PPF is susceptible to pattern noise caused by the OoO core but can prefetch complex access patterns

SPPAM seeks to solve both problems,�overcoming the limitations of these previous designs

TEXAS A&M UNIVERSITY

6 of 37

Background - AMPM

For regions (typically pages) demand block accesses are recorded in bitmaps

When this access map shows a recognized pattern, prefetches are generated

AMPM’s strategy is self-filtering, as previously accessed demand blocks or prefetched blocks cannot be reprefetched

TEXAS A&M UNIVERSITY

7 of 37

Background - AMPM

Region 0xaa

Region

0xbb

Region

0xcc

Region: 0xaa

Offset: 0x3

Set bitmap

TEXAS A&M UNIVERSITY

8 of 37

Background - AMPM

Region 0xaa

Region

0xbb

Region

0xcc

Region: 0xbb

Offset: 0x3

Pattern match!

Prefetch 0xbb004

Set bitmap

TEXAS A&M UNIVERSITY

Each time AMPM is setting a bit here in the access map, it is also checking for a pattern to emerge.�The variant that ships with ChampSim actually has only one pattern that it recognizes – 111. In this case when AMPM recognizes the pattern, it can choose which blocks it wants to prefetch.

You can think of this as taking in a history of 111 and then predicted the next N blocks, whether that would be a 2-bit prediction of 10 or a three bit prediction of 101, etc…��AMPM is going to only prefetch those lines not previously prefetched, so these predicted patterns will be marked and not re-fetched within the prefetch map for the region.�This independent tracking of the two prevents a runaway effect, where AMPM’s prefetches trigger patterns which trigger prefetches which trigger patterns and so on.

9 of 37

Background - SPP

SPP is a similar prefetcher to AMPM

Instead of an access map, we have a delta history (signature) for each region
This delta signature is a more descriptive, signed sequence of deltas

SPP adaptively identifies patterns, and forms an internal graph for determining prefetch paths

PPM / Markov chains

A recent-access filter functions similarly to AMPM’s prefetch map

TEXAS A&M UNIVERSITY

SPP – The signature path prefetcher – Is another prefetcher – far more recent and it came out of our research group a while back.�When all the technical talk is put aside, SPP is actually very similar to AMPM and could be thought of as another flavor of the same technique.��Instead of access maps, SPP stores only a short delta history (signature) for each region. The delta signature is short, but descriptive as it tells the last 3 signed jumps (deltas) the region took within it’s boundaries.�This is far more space-efficient than an access map, assuming that we are dealing with a relatively short signature.

The main difference besides the difference in region history tracking is the patterns themselves.�AMPM uses a pre-encoded catalogue of patterns, while SPP learns patterns from repeated signatures.

SPP will tally the occurrences of signatures, say a signature of [1,1,1] which leads to a signature of [1,1,2]. This indicates that a delta of 2 should be predicted for the signature [1,1,1].�The pattern table will encode this information, and allow SPP to make the best prediction choice for the workload.

Filtering through SPP is done block-wise instead of by access map, and this filter prevents recently prefetched blocks from being reprefetched.

10 of 37

Background - SPP

Region 0xaa

Region

0xbb

Region

0xcc

Last Offset

Signature

Last Offset

Signature

Last Offset

Signature

3

2

1

3

-2

1

-1

Region: 0xbb

Offset: 0x3

3

-2

1

3

To Pattern Table

Signature is updated

TEXAS A&M UNIVERSITY

11 of 37

Background - SPP

Signature

[3, -2, 1]

Delta

Signature

[1, 1, 1]

Signature

[-2, 1, 1]

Conf

1

2

3

75

43

29

Delta

Conf

1

-1

2

99

7

0

Delta

Conf

1

-2

2

80

20

5

-2

1

3

Signature

Delta

76

Confidence is increased

TEXAS A&M UNIVERSITY

12 of 37

Background - SPP

Signature

[3, -2, 1]

Delta

Signature

[1, 1, 1]

Signature

[-2, 1, 1]

Conf

1

2

3

76

43

29

Delta

Conf

1

-1

2

99

7

0

Delta

Conf

1

-2

2

80

20

5

-2

1

3

Signature

Prefetch +1

The new signature is used to predict the next delta

TEXAS A&M UNIVERSITY

13 of 37

Background - SPP

Signature

[3, -2, 1]

Delta

Signature

[1, 1, 1]

Signature

[-2, 1, 1]

Conf

1

2

3

76

43

29

Delta

Conf

2

-1

2

99

7

0

Delta

Conf

1

-2

2

80

20

5

-2

1

3

Lookahead Signature

Prefetch +2

1

Prefetch +1

The delta of a previous prediction can be used to generate additional deltas

TEXAS A&M UNIVERSITY

14 of 37

Motivation - Weaknesses

AMPM cannot prefetch complex access patterns

SPP must learn patterns, and is sensitive to access reordering. A +1 stride may be represented as:

SPP has a short history and is systemically biased towards the most-common delta +1.
SPP’s pattern table is deceptively small

SPP may be able to learn after multiple repetitions

[1, 1, 1]
[2, -1, 2]
[1,2,-1]
…

Each signature predicts a delta
That delta is appended to the signature
SPP can only link a small number of nodes within its graph

TEXAS A&M UNIVERSITY

There are some key weaknesses that both prefetchers have. AMPM, of course, is going to be unable to learn access patterns unique to a workload. It is limited to what it has (at least in the base form of AMPM) so will not be able to prefetch complex access patterns.

SPP can learn these patterns, but is quite vulnerable to request re-ordering. As an example, a +1 stride where we go from block a to b to c and so on may be issued out of order from the core or reordered due to activity in the upper-level caches.

This means a, b, and c may arrive in-order, but they could also arrive b, a, c or c, a, b. These orderings have different deltas, so SPP is unnecessarily splitting hairs, which can increase learning time and cause interference for authentic patterns that display this behavior.

There is a final issue, which is that +1 strides are incredibly common across most workloads. Aliasing within the pattern table and just general likelihood are going to interfere with the pattern table and cause +1 strides to be the most-common.�+1 strides lead to [1,1,1] signatures, and now we have all signatures which undergo lookahead converging to [1,1,1] which of course predicts 1 as the delta. This all-roads-lead-to-Rome behavior is undesirable.

Finally, SPP is essentially building a graph through it’s pattern table, but this graph is limited in the edges it can produce. A single signature predicts one delta, of lets say -4 to 3. This means there are only 7 edges each node can have in SPP’s system, and those are likely to conflict with others.

15 of 37

Motivation - SPPAM

[6] S. Somogyi, T. F. Wenisch, A. Ailamaki, B. Falsafi, and A. Moshovos, ‘Spatial Memory Streaming’,

in 33rd International Symposium on Computer Architecture (ISCA’06), 2006, pp. 252–263.

TEXAS A&M UNIVERSITY

16 of 37

Design – Region Table

Region 0xaa

Region

0xbb

Region

0xcc

Region: 0xaa

Offset: 0x2

[1,0,1]

To Pattern Table

TEXAS A&M UNIVERSITY

17 of 37

Design – Pattern Table

Pattern 000

Pattern 001

[1,0,1]

Pattern …

Pattern 101

Pattern …

Prediction

Conf

000

100

010

86

43

5

Prediction

Conf

100

111

001

56

35

20

Prediction

Conf

…

Prediction

Conf

010

110

111

72

15

3

Prediction

Conf

…

Region: 0xaa

Offset: 0x2

Prefetch 0xaa at 0x4

010 can be used to perform lookahead

TEXAS A&M UNIVERSITY

18 of 37

Design - Learning

SPPAM can utilize the access map as it’s history, so it can wait until all references are complete until committing it to memory

Heuristics are used to reinforce the learning of timely information, since old regions tend to converge to all 1s

Time since last access
Accumulated access counts

TEXAS A&M UNIVERSITY

Unlike SPP, we are managing multi-target predictions for a given pattern. This means that learning is not as simple.

We must wait until enough history is accumulated before learning, or we may accidentally exclude or include certain accesses.

SPPAM utilizes two heuristics to determine if a region is ready to learn from – “scrape”

Time since last access – so a counter that decreases each cycle and indicates whether this region has “died” and is ready to be learned from

Accumulated access counts – another down counter which manages how many recent accesses the region has had since it’s last scrape, and whether it can learn.��The latter of these is far more reasonable and less power-hungry to implement, though we got the best performance from utilizing both together.

The goal of this once again is timeliness, we want to learn to prefetch things that will be used soon after, to reduce strain on the cache and bandwidth.

19 of 37

Design - Learning

Region 0xaa

Access Count:

Access Timer:

7

982

0

!

[101], [010]

[010], [101]

[101], [010]

[010], [101]

[101], [010]

[010], [101]

[101], [010]

To Pattern Table

TEXAS A&M UNIVERSITY

20 of 37

Design - Learning

Pattern 000

Pattern …

Pattern 010

Pattern …

Pattern 101

Prediction

Conf

000

100

010

86

43

5

Prediction

Conf

…

Prediction

Conf

101

111

100

98

50

10

Prediction

Conf

…

Prediction

Conf

011

000

001

49

20

5

[101], [010]

[010], [101]

[101], [010]

[010], [101]

[101], [010]

[010], [101]

[101], [010]

Prediction

Conf

011

000

010

49

20

4

010

4

TEXAS A&M UNIVERSITY

21 of 37

Design - Learning

Pattern 000

Pattern …

Pattern 010

Pattern …

Pattern 101

Prediction

Conf

000

100

010

86

43

5

Prediction

Conf

…

Prediction

Conf

101

111

100

98

50

10

Prediction

Conf

…

Prediction

Conf

011

000

010

49

20

4

[101], [010]

[010], [101]

[101], [010]

[010], [101]

[101], [010]

[010], [101]

[101], [010]

Prediction

Conf

101

111

100

51

25

5

51

25

5

TEXAS A&M UNIVERSITY

22 of 37

Design - Lookahead

Over time, SPPAM will compile a pattern table that encodes these patterns

This table is from SPEC2017’s 605.mcf workload

TEXAS A&M UNIVERSITY

23 of 37

Design - Lookahead

010011

011011

TEXAS A&M UNIVERSITY

24 of 37

Design - Lookahead

010011

011011

111101

TEXAS A&M UNIVERSITY

25 of 37

Design - Lookahead

011011

111101

101111

010011

TEXAS A&M UNIVERSITY

26 of 37

Design - Lookahead

110110

4 table references

18 prefetch targets

011011

111101

010011

101111

TEXAS A&M UNIVERSITY

27 of 37

Design - Filtering

SPPAM incorporates usefulness feedback by sampling usefulness for each pattern

Each pattern’s usefulness determines whether it will be probabilistically dropped and whether it may attempt lookahead prefetching

The pattern that triggered each prefetch can be inferred from the region’s access map
If region entries don’t last long enough, SPPAM falls back to utilizing global usefulness

TEXAS A&M UNIVERSITY

28 of 37

Design - Overview

Page associations from Berti
LLC occupancy from Bingo
Berti trains SPPAM well

[8] Mohammad Bakhshalipour, Mehran Shakerinava, Pejman Lotfi-Kamran, and Hamid Sarbazi-Azad. 2019. Bingo Spatial Data Prefetcher. In 2019

IEEE Interna-tional Symposium on High Performance Computer Architecture (HPCA). 399–411.doi:10.1109/HPCA.2019.00053

[9] Agustín Navarro-Torres, Biswabandan Panda, Jesús Alastruey-Benedé, PabloIbáñez, Víctor Viñals-Yúfera, and Alberto Ros. 2022. Berti: an

Accurate Local-Delta Data Prefetcher. In 2022 55th IEEE/ACM Int. Symp. on Microarchitecture.IEEE Press, Chicago, IL, USA, 975–991.

doi:10.1109/MICRO56248.2022.00072

TEXAS A&M UNIVERSITY

For our final prefetcher configuration, Berti was used in the L1D, SPPAM in the L2C, and Bingo in the LLC.��There was some metadata-based sharing between Berti and Bingo to SPPAM, so SPPAM had a rough idea of the sequence of physical pages as well as the occupancy of blocks in the LLC.��Bingo is a prefetcher I haven’t mentioned as of yet, but it is quite useful in the sense of looking at many different properties of accesses when making prefetch decisions.�Berti has a tendency to throttle itself on some workloads where prefetching offers massive benefits (607.cactuBSSN) and SPPAM is limited to spatial correlations.�So, if demand streams are reaching the LLC then Bingo is going to learn what Berti and SPPAM cannot and provide a last-line-of-defense against unnecessary throttling behaviors.

29 of 37

Evaluation – Single Core�Speedup over Berti + Pythia – Geomean: 6.2, 5.9%

TEXAS A&M UNIVERSITY

We have plotted the performance of regular AMPM in blue, SPPAM in orange, and SPPAM with the inclusion of Bingo in the LLC in green.

We found the greatest improvements over the baseline occurred due to throttling rather than accuracy or coverage. BC, MCF, and XALANCBMK are all workloads where SPPAM decided to not prefetch.�

I want to draw your attention to these circles here. These are cases where traditional AMPM beats SPPAM, and by a significant margin.�What this suggest to use is that for some workloads SPPAM is either failing to learn these simple patterns or is behaving too aggressively.

These are also workloads where Berti + Pythia was slower than what we would expect, suggesting these may be linked. Perhaps AMPM’s conservative nature (at least in ChampSim’s implementation) is the reason here

30 of 37

Evaluation – Multi Core�Speedup over Berti + Pythia – Geomean: -2.12%

TEXAS A&M UNIVERSITY

31 of 37

Conclusion

SPPAM is still an unoptimized design in many ways

The general design trajectory of SPPAM seems to be leading somewhere interesting

AMPM, SPP, and SPPAM all have interesting parallels �with branch prediction (PPM)
Can we leverage what has been learned in that field for future�prefetcher designs?
DRAM-aware?

[10] M. Sutherland, A. Kannan, and N. Enright Jerger, ‘Not Quite My Tempo: Matching Prefetches to

Memory Access Times’, 06 2015.

TEXAS A&M UNIVERSITY

32 of 37

Q/A

TEXAS A&M UNIVERSITY

33 of 37

Background - Comparison

Both SPP and AMPM try to recognize history within regions

SPP builds its pattern table, while AMPM utilizes a pre-built catalogue

Each can issue multiple prefetches

SPP keeps a detailed short-term history
AMPM keeps a vague long-term history

SPP can perform lookahead
AMPM’s pattern catalogue can provide multiple targets

[2,-1,3]

1001001001

TEXAS A&M UNIVERSITY

34 of 37

Design - Filtering

[7] Viji Srinivasan, E.S. Davidson, and G.S. Tyson. 2004. A prefetch taxonomy. IEEETrans. Comput. 53, 2 (2004), 126–140.

doi:10.1109/TC.2004.1261824

[1] Lei Wang, Chia-Hang Lee, Maccoy Merrell, Gino Chacon, Daniel A. Jiménez, andPaul V. Gratz. 2025. R-Max: A Method for

Approximating the Benefit of Ideal Prefetching and Replacement Policy. IEEE Computer Architecture Letters 24, 2(2025),

293–296. doi:10.1109/LCA.2025.3611316

TEXAS A&M UNIVERSITY

35 of 37

Design

SPPAM learns the access behaviors and forms graphs to prefetch into regions
These are based on the encoded Markov chain

TEXAS A&M UNIVERSITY

If we go ahead and plot all the paths encoded in the pattern table for this workload, we get a graph like this with three distinct groups.�This is a broad trend we see across nearly all the workloads, where we have two end points at 111111 and 000000, and then some number of other groups that tend to follow a similar converging behavior.��This bottom-left graph is the one we were just traversing, but you can see that many patterns lead to 000000 which is effectively the terminating set. If any of these patterns appear, it assumes the traversal is dead and it’s effectively killed.�On the other hand, we have this upper graph that forms a loop from 110111, 111011, 011111, 101101, 111110 and back to 110111.�If you do that full-traversal, you will realize that loop is playing that same pattern we just predicted, but from different entry points. Unlike our traversal entry point though, that pattern never ends while our entry point tells SPPAM that we will eventually converge to a 111111 loop instead.

36 of 37

Design – Learning

Why no offline learning?

A naïve approach leads�to this resulting graph

TEXAS A&M UNIVERSITY

37 of 37

Design – Learning

Why predict more than 1 bit?�SPP and branch prediction get by �with a single target prediction!

Costly to reference the table per-spatial prediction
A multi-bit prediction of all 0’s gives us a useful terminator symbol
Usefulness/Uselessness data is easier to correlate with multi-bit predictions

TEXAS A&M UNIVERSITY