Quantifying locality
Knut Grimsrud · 1993
A direct measure of the locality characteristics of reference streams is presented that quantifies the concepts of locality. The new locality definition unifies the traditional concepts of temporal and spatial locality and represents the probability that the first occurrence of an access to a memory location a distance of s away from the current location occurs within the next $1\over 2$d to d references. The locality definition has useful properties that allow insight to be gained into the trace structures that correspond to various locality features. The locality of reference streams is shown to be a meaningful metric by which the interaction of reference streams and locality dependent subsystems can be quantified and visualized. Applications of this technique explored in this work include trace characterization, algorithm classification, cache parameter estimation, workload profiling, benchmark evaluation, and reference model evaluation. An examination of the locality characteristics at each level in the memory hierarchy reveals that the locality characteristics of reference streams account for the general architecture and design decisions common at each level. The locality characteristics of the UNIX SVR4 monolithic operating system and MACH 3.0 microkernel operating system are contrasted. Also, the differences in locality between references generated by the SPARC RISC processor and the i486 CISC processor are quantified.