Lightweight Reference Affinity Analysis
Xipeng Shen, Yaoqing Gao, Chen Ding, and Roch Archambault
ABSTRACT
Previous studies have shown that array regrouping and structure
splitting significantly improve data locality. The most effective
technique relies on profiling every access to every data element.
The high overhead impedes its adoption in a general compiler. In
this paper, we show that for array regrouping in scientific programs,
the overhead is not needed since the same benefit can be obtained by
pure program analysis.
We present an interprocedural analysis technique for array
regrouping. For each global array, the analysis summarizes the
access pattern by access-frequency vectors and then groups arrays with
similar vectors. The analysis is context sensitive, so it tracks
the exact array access. For each loop or function call, it uses
two methods to estimate the frequency of the execution. The first
is symbolic analysis in the compiler. The second is lightweight
profiling of the code. The same interprocedural analysis is used
to cumulate the overall execution frequency by considering the calling
context. We implemented a prototype of both the compiler and the
profiling analysis in the IBM® compiler, evaluated array regrouping
on the entire set of SPEC CPU2000 FORTRAN benchmarks, and compared
different analysis methods. The pure compiler-based array
regrouping improves the performance for the majority of programs,
leaving little room for improvement by code or data profiling.
Download the paper in
pdf
format.
Copyright notice