A Measurement Theory of Locality (MTL)
Loading...
Authors
Yuan, Liang
Ding, Chen
Denning, Peter
Zhang, Yunquan
Subjects
Advisors
Date of Issue
2018-04-14
Date
Publisher
Language
Abstract
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.
Type
Article
Description
Preprint
Series/Report No
Department
Computer Science (CS)
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
26 p.
Citation
Yuan, Liang, et al. "A Measurement Theory of Locality (MTL)." , 2018 1-26.
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.