Reuse Distance Analysis

Chen Ding, Yutao Zhong
Computer Science Department
University of Rochester
Rochester, New York
{cding,ytzhong}@cs.rochester.edu

February 2001

Technical Report UR-CS-TR-741


 

Abstract

Cache is one of the most widely used components in today's computing
systems.  Its performance is heavily depended on the locality in
programs.  Till now, the analysis of program locality relies on
expensive cache simulation.  As machine cache becomes increasingly
complex and adaptive, more efficient and accurate methods are needed
to find the best cache configuration for each program or even each
part of the program.

In this report, we measure program locality directly by the distance
between the reuses of its data.  Data reuse is an inherent program
property and does not depend on any cache parameters.  Therefore, it
allows quantitative measurement of program locality that is not tied
to any particular machine. To measure reuse distance, we describe a
new method consisting of two components. The first performs fast
analysis for full applications accessing large data sets, and the
second ascribes the simulation result to source-level data structures
at fine granularity.  With this tool, we analyze data reuse behavior
in a set of benchmark applications and present main findings about
their program locality.


Download the paper in pdf or postscript format.

Copyright notice