PARDA: A Fast Parallel Reuse Distance Analysis Algorithm
Citations Over TimeTop 10% of 2012 papers
Abstract
Reuse distance is a well established approach to characterizing data cache locality based on the stack histogram model. This analysis so far has been restricted to offline use due to the high cost, often several orders of magnitude larger than the execution time of the analyzed code. This paper presents the first parallel algorithm to compute accurate reuse distances by analysis of memory address traces. The algorithm uses a tunable parameter that enables faster analysis when the maximum needed reuse distance is limited by a cache size upper bound. Experimental evaluation using the SPEC CPU 2006 benchmark suite shows that, using 64 processors and a cache bound of 8 MB, it is possible to perform reuse distance analysis with full accuracy within a factor of 13 to 50 times the original execution times of the benchmarks.
Related Papers
- → Temporal locality and its impact on Web proxy cache performance(2000)83 cited
- Temporal Locality in Web Request Streams - Sources, Characteristics, and Caching Implications(1999)
- Comparing Strength of Locality of Reference: Popularity, Temporal Correlations, and Some Folk Theorems for the Miss Rates and Outputs of Caches(2005)
- → BEAST: A Buffer Replacement Algorithm Using Spatial and Temporal Locality(2006)1 cited