Abstract

Cache is widely used in today's computing systems and plays a pivotal role in system cost, performance and energy consumption. Most programs benefit from cache because they have locality. Until now, program locality has been measured by precise but expensive cache simulation, which has to be repeated for every cache size and program input. In this paper, we measure program locality by the distance between data reuses. Reuse distance is an inherent program property. With a single measurement, one can quantitatively analyze the locality of individual program data as well as an entire application. We make three contributions in this work. First, we give an approximation method for measuring reuse distance. The new method reduces the space overhead by orders of magnitude compared to existing techniques. Second, we use compiler instrumentation so that the results of the analysis apply to the program source, rather than the compiled binary. Finally, we measure an extensive set of scientific applications and discuss their program locality.

Copyright notice