Dynamic markov model based prefetching
Doug Joseph, Dirk C. Grunwald · 1997
Markov model based prefetching is a technique to dynamically construct an approximate markov model from the time series of cache miss references, with the goal of predicting future miss references. The main contribution of this thesis is that markov model based prefetching is shown to be a practical and effective technique for data and instruction prefetching on industry standard benchmarks. This thesis examines the issues that are critical to the performance and practicality of markov prefetching. First, metrics are devised to examine the properties of actual markov models constructed from the miss reference time series of L1 I and D cache models on the workloads. Their potential as a basis for predicting future miss references is demonstrated and compared to traditional stream oriented techniques. To validate the effectiveness of markov prefetching, cycle level simulations of prefetchers with a simplified processor model and detailed memory hierarchy models are evaluated. Results indicate that markov based prefetching can reduce memory stalls to a much greater degree than stream oriented techniques on our workloads. In addition, instruction prefetching is shown to be a greater factor in reducing stalls than data prefetching (sometimes by large degrees), especially in the commercial workloads. Simulations indicate an average 54% reduction in memory stalls across all benchmarks using markov prefetching, which was a 40% improvement over that achieved using stream oriented prefetchers alone.