HOTL: a higher order theory of locality

The locality metrics are many, for example, miss ratio to test perfor-mance, data footprint to manage cache sharing, and reuse distance to analyze and optimize a program. It is unclear how different met-rics are related, whether one subsumes another, and what combina-tion may represent locality completely. This paper first derives a set of formulas to convert between five locality metrics and gives the condition for correctness. The transformation is analogous to differentiation and integration. As a result, these metrics can be assigned an order and organized into a hierarchy. Using the new theory, the paper then develops two techniques: one measures the locality in real time without special hardware sup-port, and the other predicts multicore cache interference without parallel testing. The paper evaluates them using sequential and par-allel programs as well as for a parallel mix of sequential programs