Prefetching using Markov predictors

Prefetching is one approach to reducing the latency of memory op-erations in modem computer systems. In this paper, we describe the Markov prefetcher. This prefetcher acts as an interface between the on-chip and off-chip cache, and can be added to existing com-puter designs. The Markov prefetcher is distinguished by prefetch-ing multiple reference predictions from the memory subsystem, and then prioritizing the delivery of those references to the processor. This design results in a prefetching system that provides good coverage, is accurate and produces timely results that can be ef-fectively used by the processor. In our cycle-level simulations, the Markov Prefetcher reduces the overall execution stalls due to in-struction and data memory operations by an average of 54 % for various commercial benchmarks while only using two thrds the memory of a demand-fetch cache organization.