Locality Approximation Using Time
Xipeng Shen, Jonathan Shaw, Brain Meeker, and Chen Ding
ABSTRACT
Reuse distance (i.e. LRU stack distance) precisely characterizes
program locality and has been a basic tool for memory system research
since the 1970s. However, the high cost of measuring has restricted
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 that
converts cheaply obtained time distance to the more costly reuse
distance. Compared to the state-of-the-art technique, this approach
reduces measuring time by a factor of 17, and approximates cache line
reuses with over 99\% accuracy and the cache miss rate with less than
0.4\% average error for 12 SPEC 2000 integer and floating-point
benchmarks. By exploiting the strong correlations between time and
locality, this work makes precise locality as easy to obtain as data
access frequency, and opens new opportunities for program
optimizations.
Download the paper in
pdf format.