Array Regrouping and Structure Splitting Using Whole-Program
Reference Affinity
Yutao Zhong, Maksim Orlovich, Xipeng Shen, and Chen Ding
ABSTRACT
While the memory of most machines is
organized as a hierarchy, program data are laid out in a uniform
address space. This paper defines a model of reference affinity,
which measures how close a group of data are accessed together in a
reference trace. It proves that the model gives a hierarchical
partition of program data. At the top is the set of all data with the
weakest affinity. At the bottom is each data element with the strongest
affinity. Based on the theoretical model, the paper presents k-distance analysis, a practical
test for the hierarchical affinity of source-level data. When used for
array regrouping and structure splitting, k-distance analysis consistently
outperforms data organizations given by the programmer, compiler
analysis, frequency profiling, statistical clustering, and all other
methods we have tried.