Comparative Evaluation of Locality Metrics : Assessing Accuracy in Representing Memory Access Patterns’ Temporal and Spatial Locality

Sammanfattning

Memory is a critical and high-demand resource in modern computing systems, the design and management of which are crucial to performance. The growing gap between processor and memory access speeds (and bandwidth) makes optimising data access a challenging yet increasingly important task. In this context, locality of reference—the tendency of a program to access a subset of memory addresses repeatedly and within a short period—has become a foundational concept in the areas of Computer Science and Computer Architecture. It is used widely both within hardware and software design and optimisation, from operating systems and caches, to web browsers and humancomputer interaction. However, there is no clear consensus on how to quantify locality—that is, how to assign a value to it and on what grounds. Despite the existence of numerous proposed metrics to quantify temporal and spatial locality in the literature, there is no universal agreement on their use or precision. This bachelor’s thesis addresses that gap by providing a comparative study of three locality metrics. Said metrics are evaluated against a series of synthetic traces, designed to exhibit controlled locality properties. The study then assesses how well each score aligns with the intuitive notions of temporal and spatial locality. The results reveal that the considered metrics can produce different scores for the same memory access patterns, reflecting their divergent definitions of locality. Stride-based metrics effectively capture not only spatial locality but also distance, while block-based metrics are more sensitive to the clustering of addresses in particular block-sized regions. These findings demonstrate that a metric’s utility is context-dependent, and a universal framework is yet to be achieved.