CRPC-TR95519-S
An Empirical Study of Cross-loop Reuse in the NAS Benchmarks
---

This paper describes an empirical study designed to quantify the level
of {\em cross-loop} reuse occurring in a set of scientific Fortran
programs, the NAS Benchmarks. Cross-loop reuse takes place when a set
of data items or cache lines are accessed in a given loop nest and
then accessed again within some subsequent portion of the program
(usually another outer loop nest). In contrast to {\em intra-loop}
reuse, which takes place during the execution of a single loop nest,
cross-loop reuse is not always detectable by traditional compile-time
reuse analysis techniques.  In this study, the benchmark programs are
instrumented and run through a cache simulator. The simulator gathers
statistics on cross-loop reuse using a novel classification scheme
that clearly identifies the different types of reuse. According to the
simulation data, the level of cross-loop reuse varies widely from
program to program, and depends greatly on the problem size and cache
size.  Some programs exhibit almost no cross-loop reuse, however other
programs have significant levels of cross-loop reuse even for fairly
small cache sizes.  The data from this study suggest that cross-loop
reuse information would be quite beneficial for compilers that
attempt certain optimizations.