HOT: a Higher Order Theory of Locality

The locality of a program may be quantified by the data footprint over a time period or by the miss ratio in a particular cache. The relation between data usage and miss frequency has not been precisely established. Neither is it known whether one metric contains more information than the other. This paper presents a theory with two constituents. The first is a set of complete derivations between five commonly used locality metrics including the footprint and miss ratio curve. The second is a condition for the footprint-to-miss-ratio conversion to be correct. The derivations use statistics on variable-length windows and different-size caches. The calculation is similar to differentiation and integration used to convert between high- degree polynomials. As an application, the paper gives a new sampling technique, which predicts the miss ratio for all cache sizes in near real time without special hardware support and without the exclusive use of the machine cache. The paper evaluates the technique for sequential and parallel programs as well as for a parallel mix of sequential programs