Processor speeds continue to outpace the memory subsystem making it
neccesary to proactively acquire and retain important data. Current
applications have an ever increasing number of dynamically allocated
data structures and these data structures occupy large footprints. A
large portion of dynamically allocated data is accessed through
pointers in the form of recursive data structures. Loads accessing
these data structures often become a data cache bottleneck because
they depend on a previous instance of themselves, scattering their
accesses. For this reason, optimization techniques specific to these
types of loads should be employed. One technique is to analyze the
data stream and use the resulting information to guide prefetching
and/or dynamic data layout.
This work characterizes the repeating data access patterns in both the
Olden and SPEC CPU2000I benchmark suites. The intent is to apply the
analysis result to guide later optimizations.
In this paper, we
discuss our findings, with some benchmarks show interesting
correlation in their data accesses. We have also obtained indication
that such correlation manifests itself more prominently when a
program's execution is divided into phases. A preliminary attempt was
also performed in which analysis results were used to guide data
prefetching.