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 {\em $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.
Download the paper in pdf format.
Copyright notice