When prefetching improves/degrades performance

Abstract

We formulate a new method for evaluating any prefetching algorithm (real or hypothetical). This method allows researchers to analyze the potential improvements prefetching can bring to an application independent of any known prefetching algorithm. We characterize prefetching with the metrics: timeliness, coverage, and accuracy. We demonstrate the usefulness of this method using a Markov prefetch algorithm. Under ideal conditions, prefetching can remove nearly all of the pipeline stalls associated with a cache miss. However, in today's processors, we show that nearly all of the performance benefits derived from prefetching are eroded and, in many cases, prefetching loses performance. We do quantitative analysis of these trade-offs, and show that there are linear relationships between overall performance and coverage, accuracy, and bandwidth. Copyright 2005 ACM.