We use reuse distance (originally called LRU stack distance) as a metric of program locality. Unique properties of reuse distance make it possible to compare data access pattern in different program executions. By selective run-time monitoring and efficient reuse distance measurement, we can analyze memory reference pattern of part or whole programs in different granularity. Preliminary results show that reuse distance analysis can predict whole-program locality through profiling. This analysis can then be used to estimate cache miss rate for all data inputs of a program.
We propose to further develop reuse distance analysis in depth and width. We will divide program data into subgroups based on group locality. Clustering will be applied based on the access pattern of individual elements. By measuring reuse distance distribution for different cache line sizes, we will estimate spatial locality. Based on program locality, we plan to study new techniques in memory benchmark design and cache-sensitive job scheduling. We will show that reuse distance analysis can improve the effectiveness in program understanding, optimization and scheduling.