Markov Prefetcher (Joseph and Grunwald)
State Transition Table with History of 1
State Transition Table with History of 3
Notes:
Contrary to the other prefetchers we looked at, the Markov prefetcher does not tie itself to particular data structure accesses. Instead it remembers past sequences of misses to predict future sequences.
Possible such sequences are shown up here. Arrows indicate what has been observed in the past. Once this information is collected, a prefetch can be issued when a miss from this sequence is detected. If, for example, we observe again a miss on 3b, then the Markov prefetcher could prefetch 4b, 4c, and 4d.
This information is maintained in the state transition table that associated several predictors with a miss address. An LRU scheme is used to update the predictors.
If the memory latency is large, then a larger prefetch distance is desirable. This is shown for a distance of three in the state transition table on the right. A miss on 2b, for example, would generate prefetches for 5b, 5c, and 5d.
The Markov prefetcher can be effective for prefetching strided references, linked memory references, and other references. However, because multiple predictors are used to achieve a good coverage, the Markov prefetcher does not achieve very good accuracy. It also has a large table requirement and has the disadvantage of only prefetching during the second traversal of the data structure. This is because the state transition table must first be built. While the other prefetchers must built their tables, too, they only do so for the first execution of an instruction, not for each address that is generated.