Program locality analysis using reuse distance
Top Cited Papers
Open Access
- 26 August 2009
- journal article
- review article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 31 (6), 1-39
- https://doi.org/10.1145/1552309.1552310
Abstract
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 article 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 article presents two techniques that predict how the locality of a program changes with its input. The first is approximate reuse-distance measurement, which is asymptotically faster than exact methods while providing a guaranteed precision. The second is statistical prediction of locality in all executions of a program based on the analysis of a few executions. The prediction process has three steps: dividing data accesses into groups, finding the access patterns in each group, and building parameterized models. The resulting prediction may be used on-line with the help of distance-based sampling. When evaluated on fifteen benchmark applications, the new techniques predicted program locality with good accuracy, even for test executions that are orders of magnitude larger than the training executions. The two techniques are among the first to enable quantitative analysis of whole-program locality in general sequential code. These findings form the basis for a unified understanding of program locality and its many facets. Concluding sections of the article present a taxonomy of related literature along five dimensions of locality and discuss the role of reuse distance in performance modeling, program optimization, cache and virtual memory management, and network traffic analysis.Keywords
Funding Information
- U.S. Department of Energy (DE-FG02-02ER25525)
- National Science Foundation (CCR-0238176CNS-0720796CNS-0509270)
- Division of Computer and Network Systems (CCR-0238176CNS-0720796CNS-0509270)
This publication has 82 references indexed in Scilit:
- FormaACM Transactions on Programming Languages and Systems, 2007
- Efficient and accurate analytical modeling of whole-program data cache behaviorInternational Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2004
- Cache miss equationsACM Transactions on Programming Languages and Systems, 1999
- Improving the ratio of memory operations to floating-point operations in loopsACM Transactions on Programming Languages and Systems, 1994
- Efficient trace-driven simulation methods for cache performance analysisACM Transactions on Computer Systems, 1991
- An implementation of interprocedural bounded regular section analysisIEEE Transactions on Parallel and Distributed Systems, 1991
- An efficient data dependence analysis for parallelizing compilersIEEE Transactions on Parallel and Distributed Systems, 1990
- Efficient (stack) algorithms for analysis of write-back and sector memoriesACM Transactions on Computer Systems, 1989
- The Measurement of Locality and the Behaviour of ProgramsThe Computer Journal, 1984
- An empirical study of FORTRAN programsSoftware: Practice and Experience, 1971