Accurate approximation of locality from time distance histograms

Locality increasingly determines system performance. As a rigor-ous and precise locality model, reuse distance has been used in pro-gram optimizations, performance prediction, memory disambigua-tion and locality phase prediction. However, the high cost of mea-surement has been severely impeding its uses in scenarios requiring high efciency, e.g. product compilers, performance debugging, and run-time optimizations. This work proposes a statistical model to approximate reuse dis-tance histograms from easily-obtained time distance histograms. The model makes reuse distance measurement as light as measur-ing data access frequency. Compared to the state-of-the-art tech-nique, this model reduces measurement overhead by 17 times on ten SPEC CPU2000 ref executions and achieves over 99 % accuracy for cache reuse approximation. Furthermore, this paper presents a trace generator, which produces data access traces from a given reuse distance histogram. It is benecial for comprehensive evalua-tion of the approximation technique and can serve as a general tool for other locality studies. 1