Predicting Whole-Program Locality through Reuse Distance Analysis
Chen Ding and Yutao Zhong
Profiling can accurately analyze program behavior for select data
inputs. We show that profiling can also predict program locality for
inputs other than profiled ones. Here locality is defined by the
distance of data reuse. Studying whole-program data reuse may reveal
global patterns not apparent in short-distance reuses or local control
flow. However, the analysis must meet two requirements to be useful.
The first is efficiency. It needs to analyze all accesses to all data
elements in full-size benchmarks and to measure distance of any length
and in any required precision. The second is predication. Based on a
few training runs, it needs to classify patterns as regular and
irregular and, for regular ones, it should predict their (changing)
behavior for other inputs. In this paper, we show that these goals
are attainable through three techniques: approximate analysis of reuse
distance (originally called LRU stack distance), pattern recognition,
and distance-based sampling. When tested on 15 integer and
floating-point programs from SPEC and other benchmark suites, our
techniques predict with on average 94% accuracy for data inputs up to
hundreds times larger than the training inputs. Based on these
results, the paper discusses possible uses of this analysis.
Download the paper in pdf format.