Extended Histories: Improving Regularity and Performance in Correlation Prefetchers

R. Manikantan, Kaushik Rajan, and R. Govindarajan


Data Prefetchers identify and make use of any regularity

present in the history/training stream to predict future references

and prefetch them into the cache. The training information

used is typically the primary misses seen at a particular

cache level, which is a filtered version of the accesses seen

by the cache. In this work we demonstrate that extending the

training information to include secondary misses and hits

along with primary misses helps improve the performance of

prefetchers. In addition to empirical evaluation, we use the

information theoretic metric entropy, to quantify the regularity

present in extended histories. Entropy measurements indicate

that extended histories have improved regularity than

the default primarymiss only training stream and help corroborate

our empirical findings.

In case of extended histories, further benefits are achieved

by triggering prefetches during secondary misses also. In this

paper we explore the design space of extended prefetch histories

and alternative prefetch trigger points for delta correlation

prefetchers. We observe that different prefetch schemes

benefit to a different extent by extended history and alternative

trigger points. Also the best performing design point

can vary on a per-benchmark basis. To meet these requirements,

we propose a simple adaptive scheme that identifies

the best performing design point for a benchmark-prefetcher

combination at runtime.

In SPEC2000 benchmarks, using all the L2 accesses as

history for prefetcher helps improve the performance in terms

of both IPC and misses reduced over methods which use only

primary misses as history. The adaptive scheme improves

the performance of CZone prefetcher over Baseline by 4.6%

on an average. These performance gains are accompanied

by a moderate reduction in the memory traffic requirements.


Publication typeInproceedings
Published inProceedings of High Performance Embedded Architectures and Compilers, HIPEAC'2011
> Publications > Extended Histories: Improving Regularity and Performance in Correlation Prefetchers