Reuse Distance Analysis


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 eÆcient and accurate methods are needed to nd the best cache con guration 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 rst performs fast analysis for full applications accessing large data sets, and the second ascribes the simulation result to source-level data structures at ne granularity. With this tool, we analyze data reuse behavior in a set of benchmark applications and present main ndings about their program locality.


6 Figures and Tables

Download Full PDF Version (Non-Commercial Use)