Finding the Reference Affinity Groups in Trace using Sampling Method

Making better use of the cache is of great importance for the modern computer programs and systems. One key step is to understand the data locality. In this article, we investigate one effective and important model of data locality---reference affinity. This model is superior than the previous methods in that it can express the whole-scale locality in a more accurate and more flexible way. Traces collected from different applications are a rich source for the analysis of reference affinity. In this article, we extend the strict reference affinity to weak reference affinity and their properties are proved. We propose a sampling method to find reference affinity groups and present experimental results based on synthetic data showing that the new method is more scalable and accurate than the state-of-the-art method proposed by Zhong et al. (2004)