array regrouping and structure splitting using whole-program reference affinity
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.
arrays array regrouping group structure structure splitting reference affinity memorialized organization hierarchies hierarchic data addressing space paper model measurement traces partition analysis practical test programmer compilation profiles statistics cluster method distance program locality volume distance reuse signature program transformation