Program Locality Analysis Using Reuse Distance

Date Added: Aug 2009
Format: PDF

On modern computer systems, the memory performance of an application depends on its locality. For a single execution, locality-correlated measures like average miss rate or working-set size have long been analyzed using reuse distance - the number of distinct locations accessed between consecutive accesses to a given location. This paper addresses the analysis problem at the program level, where the size of data and the locality of execution may change significantly depending on the input. The paper presents two techniques that predict how the locality of a program changes with its input.