Dead-block prediction & dead-block correlating prefetchers
- 1 May 2001
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGARCH Computer Architecture News
- Vol. 29 (2), 144-154
- https://doi.org/10.1145/384285.379259
Abstract
Effective data prefetching requires accurate mechanisms to predict both “which” cache blocks to prefetch and “when” to prefetch them. This paper proposes the Dead-Block Predictors (DBPs), trace-based predictors that accurately identify “when” an Ll data cache block becomes evictable or “dead”. Predicting a dead block significantly enhances prefetching lookahead and opportunity, and enables placing data directly into Ll, obviating the need for auxiliary prefetch buffers. This paper also proposes Dead-Block Correlating Prefetchers (DBCPs), that use address correlation to predict “which” subsequent block to prefetch when a block becomes evictable. A DBCP enables effective data prefetching in a wide spectrum of pointer-intensive, integer, and floating-point applications. We use cycle-accurate simulation of an out-of-order superscalar processor and memory-intensive benchmarks to show that: (1) dead-block prediction enhances prefetching lookahead at least by an order of magnitude as compared to previous techniques, (2) a DBP can predict dead blocks on average with a coverage of 90% only mispredicting 4% of the time, (3) a DBCP offers an address prediction coverage of 86% only mispredicting 3% of the time, and (4) DBCPs improve performance by 62% on average and 282% at best in the benchmarks we studied.Keywords
This publication has 13 references indexed in Scilit:
- Selective, accurate, and timely self-invalidation using last-touch predictionPublished by Association for Computing Machinery (ACM) ,2000
- Prefetching using Markov predictorsIEEE Transactions on Computers, 1999
- Capturing dynamic memory reference behavior with adaptive cache topologyPublished by Association for Computing Machinery (ACM) ,1998
- Dependence based prefetching for linked data structuresPublished by Association for Computing Machinery (ACM) ,1998
- Compiler-based prefetching for recursive data structuresPublished by Association for Computing Machinery (ACM) ,1996
- Reducing memory latency via non-blocking and prefetching cachesPublished by Association for Computing Machinery (ACM) ,1992
- A model for estimating trace-sample miss ratiosPublished by Association for Computing Machinery (ACM) ,1991
- Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffersPublished by Association for Computing Machinery (ACM) ,1990
- Cache MemoriesACM Computing Surveys, 1982
- Dynamic Improvement of Locality in Virtual Memory SystemsIEEE Transactions on Software Engineering, 1976