2018/02/05 by Liang Yuan, Yuan, Liang, Chen Ding +5
Computer Science · #Advanced Data Storage Technologies #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel Computing and Optimization Techniques #Performance (cs.PF)
paper · pdf · doi:10.48550/arxiv.1802.01254
openalex publication_date 2018/02/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Locality is a fundamental principle used extensively in program and system optimization. It can be measured in many ways. This paper formalizes the metrics of locality into a measurement theory. The new theory includes the precise definition of locality metrics based on access frequency, reuse time, reuse distance, working set, footprint, and the cache miss ratio. It gives the formal relation between these definitions and the proofs of equivalence or non-equivalence. It provides the theoretical justification for four successful locality models in operating systems, programming languages, and computer architectures which were developed empirically.