Efficient Locality Approximation Using Time

Locality, characterized by data reuses, determines caching performance. Reuse distance (i.e. LRU stack distance) precisely characterizes program locality and has been used in memory-related research since 1970s. However, the high cost of measuring it still urges a breakthrough before its practical uses in performance debugging, locality analysis and optimizations of long-running applications.

In this work, we improve the efficiency by exploring the connection between time and locality. We propose a statistical model converting cheap time distance to costly reuse distance. Compared to the state-of-the-art technique, this approach reduces measuring time by 17 times, and approximates cache line reuses with over 99% accuracy. Experiments demonstrate the effective uses of the approximated reuse distance in cache miss rate prediction. This work, for the first time, reveals the strong correlations between time and locality. It makes precise locality as easy to obtain as data access frequency, removes the obstacles to reuse distance's practical uses, and opens new opportunities for program optimizations.


Greg Steffan
Last modified: Tue Aug 26 09:57:05 EDT 2008