Accurate Approximation of Locality from Time Distance Histograms
Xipeng Shen, Jonathan A. Shaw, Brian Meeker · 2006
Locality increasingly determines system performance. As a rigorous and precise locality model, reuse distance has been used in program optimizations, performance prediction, memory disambiguation and locality phase prediction. However, the high cost of measurement has been severely impeding its uses in scenarios requiring high efficiency, e.g. product compilers, performance debugging, and run-time optimizations. This work proposes a statistical model to approximate reuse distance histograms from easily-obtained time distance histograms. The model makes reuse distance measurement as light as measuring data access frequency. Compared to the state-of-the-art technique, 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 beneficial for comprehensive evaluation of the approximation technique and can serve as a general tool for other locality studies.