Fact-checked by Grok 2 weeks ago

Locality of reference

Locality of reference, also known as the principle of locality, is the observed tendency of computer programs to cluster their memory references to small subsets of their address space over extended intervals of time.^[1] This behavior manifests in two primary forms: temporal locality, where recently accessed data is likely to be referenced again soon, and spatial locality, where data located near a recently accessed address is likely to be accessed next.^[1] These patterns arise from common programming structures, such as loops for temporal clustering and contiguous data arrays or modules for spatial clustering.^[1] The concept emerged in the late 1950s during the development of early virtual memory systems, such as the Atlas computer at the University of Manchester, to address inefficiencies in paging and reduce thrashing in multiprogrammed environments.^[1] It was formally articulated by Peter J. Denning in his 1968 paper introducing the working set model, which defines the working set of a process as the set of pages referenced within a recent time window, providing a predictive framework for memory allocation based on locality.^[2] Denning's model demonstrated that programs exhibit stable localities, allowing systems to allocate just enough memory to avoid excessive page faults while maintaining performance.^[3] Locality of reference underpins the design of modern memory hierarchies, including caches, virtual memory, and prefetching mechanisms, enabling dramatic improvements in system throughput by minimizing data movement between slow and fast storage layers.^[1] In contemporary architectures, it influences processor optimizations, database query processing, and even web caching algorithms, where exploiting locality can reduce latency by orders of magnitude.^[1] Violations of locality, such as in pointer-chasing workloads, highlight its critical role, often necessitating algorithmic redesigns to enhance spatial and temporal reuse.^[4]

Core Concepts

Definition

Locality of reference is a fundamental principle in computer science describing the tendency of computer programs to access a relatively small portion of their total address space or to repeatedly reference the same data items over relatively short periods of time.^[5] This behavior arises because programs, influenced by their structure and the algorithms they implement, cluster memory references into localized subsets rather than distributing them uniformly or randomly across the entire memory.^[5] The concept was developed by Peter J. Denning during his doctoral research at MIT and formally introduced in his 1968 paper on the working set model, emerging from efforts to model program behavior in virtual memory systems and to resolve performance issues such as thrashing in multiprogrammed environments.^[5]^[2] In the von Neumann architecture, where instructions and data share a unified linear address space accessed sequentially by the processor, memory access patterns reflect the linear flow of program execution and the modular organization of code and data structures.^[5] These patterns deviate from purely random access, exhibiting predictability that stems from algorithmic locality, such as loops reusing variables or sequential scans of arrays, thereby enabling system designers to optimize for clustered rather than scattered references.^[5] The principle primarily manifests as spatial locality (accesses to nearby addresses) and temporal locality (reuse of recently accessed data), though these are explored in greater detail elsewhere.^[5]

Types of Locality

Spatial locality refers to the tendency of a program to access data or instructions located in close physical proximity to recently accessed items in memory. This pattern arises because many algorithms process data in a linear or clustered manner, allowing multiple related elements to be loaded into a cache line or page simultaneously. A classic example occurs in sequential traversals of arrays or linked structures within loops, where consecutive elements are stored adjacently, enabling efficient prefetching and reducing the number of distinct memory fetches.^[2]^[6] Temporal locality, in contrast, captures the propensity for the same memory location—whether data or instructions—to be referenced again shortly after its initial access. This reuse stems from repetitive control flows in programs, such as iterations in loops or frequent evaluations of conditional statements, where variables or code blocks are accessed multiple times in quick succession. For instance, loop counters and accumulated results in iterative computations exhibit strong temporal locality, as they are read and updated repeatedly during execution.^[2]^[7] In practice, spatial and temporal localities frequently interplay within program execution, as seen in nested loops that both reuse variables (temporal) and scan adjacent array elements (spatial), amplifying overall predictability in reference streams. Despite this synergy, the two can be decoupled for analysis; a program might demonstrate robust temporal locality in branch-heavy code but limited spatial locality if data accesses skip intervening locations. This separation aids in targeted optimizations, such as adjusting data layouts for spatial gains without altering reuse patterns.^[7]^[6] These locality types differ markedly from non-local patterns like strided access, which involves regular intervals between references (e.g., sampling every fifth array element), offering partial spatial benefits only if strides align with cache boundaries but generally weaker than contiguous access. Random access patterns, characterized by unpredictable and dispersed references, exhibit negligible locality in both dimensions, leading to frequent cache misses without the clustering that defines spatial or temporal behaviors.^[6]

Theoretical and Empirical Basis

Empirical Evidence

Early empirical studies of program behavior provided foundational evidence for locality of reference through analysis of memory address traces. In 1968, Peter J. Denning examined traces from various computational workloads and found that memory references were highly concentrated within small sets of recently accessed pages, with the working set size stabilizing to capture the majority of accesses during execution phases. This observation demonstrated that programs tend to reuse a limited subset of memory locations over extended periods, validating the existence of both temporal and spatial locality patterns.^[8] Subsequent work by Denning and Stuart C. Schwartz in 1972 reinforced these findings by deriving properties of the working set model from trace data, showing consistent clustering of references, with the probability of reuse dropping sharply outside the working set.^[9] Validations using standardized workloads, such as the SPEC CPU2017 benchmark suite, confirm the prevalence of locality. Trace-driven simulations reveal average L1 data cache miss rates around 3.4% for typical configurations, corresponding to hit rates exceeding 95% and highlighting strong temporal reuse in loop-dominated code sections. Spatial locality is evident in reduced miss rates with larger cache lines, as sequential accesses within data structures account for a significant portion of references.^[10] In operating systems, locality manifests in low page fault frequencies during normal operation, implying near-complete reuse of resident pages and minimal disk I/O due to temporal patterns in application behavior. The extent of locality observed in these studies is influenced by program characteristics, including repetitive code structures that foster temporal reuse and compact data arrangements that promote spatial proximity of accessed elements.

Mathematical Modeling

The reuse distance metric provides a formal measure of temporal locality in memory access patterns. For a sequence of memory references r_1, r_2, \dots, r_n, the reuse distance d for a reference r_i to item x is defined as the number of distinct items accessed between the previous reference to x at position j < i and r_i, i.e., d = |\{ r_k \mid j < k < i, r_k \neq x \} |. This distance indicates the likelihood of a cache hit: if d is smaller than the cache size, the item remains in cache under optimal replacement policies like LRU. Lower average reuse distances across a trace signify stronger temporal locality, enabling predictions of cache performance independent of specific hardware parameters. This metric originates from early evaluations of storage hierarchies, where it was used to simulate stack-based replacement algorithms.^[11] The working set model offers another foundational approach to modeling locality, particularly for paging systems. Introduced by Denning, it defines the working set W(t, \theta) at time t with window size \theta as the set of unique pages p referenced in the recent past:

W(t, \theta) = \{ p \mid \exists i : t - \theta < a_i < t \land \text{page}(a_i) = p \},

where a_i denotes the timestamp of the i-th memory access. The size |W(t, \theta)| represents the active memory footprint, and maintaining \theta such that |W(t, \theta)| fits in physical memory prevents thrashing by ensuring locality is preserved. This model assumes references within the window capture the program's current locality phase, guiding resource allocation in multiprogrammed environments.^[2] Spatial locality metrics focus on the tendency to access nearby data items, often quantified through miss ratio curves or access stride patterns. Miss ratio curves depict the cache miss rate as a function of block size or cache capacity, showing how larger blocks exploit spatial reuse to reduce misses exponentially in many workloads. For stride-based accesses, such as in linear array traversals, the probability of hitting within a spatial distance k can be modeled exponentially as P(k) = 1 - e^{-\lambda k}, where \lambda > 0 reflects the decay rate of access likelihood with distance; this captures decaying spatial correlation in reference streams. Such models help predict the benefits of prefetching or larger cache lines by fitting empirical traces to parameter \lambda.^[12] Despite their utility, these mathematical models rely on key assumptions that limit their applicability. A primary limitation is the assumption of stationarity in access patterns, where locality metrics like reuse distances or working set sizes are presumed invariant over time or inputs; in practice, dynamic workloads with phase changes or varying data sets violate this, leading to inaccurate predictions without adaptive adjustments.^[13]

Performance Implications

Relevance to Efficiency

Locality of reference significantly enhances computational efficiency by reducing the average memory access time, as programs tend to repeatedly reference a limited subset of data and instructions, allowing these to be kept in faster storage levels while minimizing fetches from slower ones. This principle underpins memory hierarchies, where exploiting temporal and spatial locality avoids the high latency of distant storage, such as main memory or disk, which can be orders of magnitude slower than on-chip caches—disk seeks, for instance, are approximately 10 million times slower than CPU cycles (e.g., 10 ms vs. 1 ns).^[14]^[15] By limiting page faults and cache misses, locality ensures that systems operate closer to their peak performance, directly tying into Amdahl's law, which emphasizes balancing components to maximize overall throughput; without locality-aware management, thrashing can degrade efficiency to near zero, but proper exploitation maintains high utilization across the hierarchy.^[14] Quantitative impacts of locality are evident in cache hit rate improvements, which can yield substantial speedups in execution time. For example, optimizing algorithms to better exploit locality in memory hierarchies, such as through separate caches for arrays and scalars, has demonstrated cache miss rate reductions of up to 43%, leading to performance improvements by increasing reuse and reducing misses.^[16] In blocked matrix multiplication, exploiting locality via cache blocking reduces miss rates from around 2 per iteration to as low as 0.1, resulting in 3x to 4x overall speedups on typical processors of the era. These gains highlight how even modest hit rate enhancements (e.g., from 90% to 95%) compound across billions of accesses to deliver transformative efficiency.^[17] Beyond raw performance, locality contributes to broader efficiency through energy savings and improved scalability in large systems. On-chip accesses consume far less power than off-chip ones—typically 10-100 times lower due to reduced data movement across buses—making locality crucial for power-constrained environments like mobile devices and data centers. In scalable architectures, such as clustered databases or edge computing, locality enables efficient resource partitioning, allowing systems to handle growing workloads without proportional increases in energy or latency, as locality sets remain manageable even as total data scales.^[14] However, enhancing locality introduces trade-offs, particularly the overhead of techniques like prefetching or data reorganization. Prefetching data based on predicted locality can anticipate needs but incurs costs when predictions fail at phase boundaries, leading to unnecessary cache pollution or bandwidth waste; similarly, algorithm restructuring for better locality may add computational overhead that offsets gains in small datasets. These costs must be weighed against benefits, often requiring runtime monitoring to adapt dynamically.^[14]

Impact on System Design

The principle of locality of reference serves as a foundational guideline for designing memory hierarchies in computing systems, enabling efficient data access by aligning hardware structures with observed access patterns. Multi-level caches exemplify this by being dimensioned according to the characteristic windows of temporal and spatial locality; L1 caches, typically small (e.g., 32-64 KB), prioritize rapid exploitation of short-term temporal locality for frequently reused data, while progressively larger L2 (256 KB-1 MB) and L3 (several MB) caches extend to spatial locality across broader address ranges and longer reuse intervals. This tiered sizing reduces average memory latency by capturing locality at scales that match program behavior, as established in early analyses of reference patterns.^[2] Virtual memory systems integrate locality principles through page replacement algorithms that approximate temporal locality to manage limited physical memory. The least recently used (LRU) policy, for example, evicts pages based on the recency of access, assuming that recently referenced pages are likely to be reused soon, which aligns with empirical observations of program phasing and minimizes thrashing in multiprogrammed environments.^[18] Compilers and operating systems further embed locality-aware mechanisms into system design: compilers apply transformations like loop tiling to reorder code iterations, thereby enhancing data reuse and fitting access patterns to cache sizes during code generation.^[19] Meanwhile, OS schedulers preserve locality by prioritizing thread assignments to processors that retain shared data in local caches, particularly in cache-coherent non-uniform memory access (CC-NUMA) architectures, to avoid costly data migrations. System performance benchmarking leverages locality through metrics such as cache miss rates, which quantify how effectively the design exploits reference patterns—lower miss rates indicate better alignment between hardware capacities and locality windows, providing a direct measure of overall efficiency.^[20]

Applications in Computing

Memory Hierarchies

Memory hierarchies in computing systems are structured as a pyramid of storage levels, each with increasing capacity and access latency but decreasing cost per bit, designed to exploit the locality of reference principle. At the apex are CPU registers, which offer sub-nanosecond access times and hold a few dozen entries for immediate operand storage, capitalizing on temporal locality by retaining recently computed values. Below them lie on-chip caches: the L1 cache (typically 32-64 KB per core) provides latencies around 1-4 cycles and targets both spatial and temporal locality for instructions and data; the L2 cache (256 KB to 1 MB per core) extends this with 10-20 cycle latencies; and the shared L3 cache (several MB to tens of MB) serves multiple cores at 20-50 cycles, further buffering main memory. DRAM main memory follows with hundreds of cycles latency and gigabyte-scale capacity, while secondary storage like SSDs or disks at the base offers milliseconds access for archival data. This tiered design ensures that programs, which exhibit locality by reusing nearby or recent data, experience average access times closer to the fastest levels rather than the slowest, as misses in higher levels fetch blocks into all intervening caches to prime future accesses.^[21]^[22] Cache management policies within these hierarchies directly leverage locality to maximize hit rates, which measure the fraction of accesses served from the cache without resorting to slower levels. For temporal locality, the Least Recently Used (LRU) policy approximates optimality by evicting the block unused for the longest time, assuming recent accesses predict future ones; this performs well in workloads with looping structures but incurs overhead from tracking recency. Spatial locality is exploited via prefetching mechanisms, where hardware anticipates and loads adjacent blocks upon a miss, such as stride prefetchers detecting regular access patterns in arrays. Cache associativity influences hit rates by allowing multiple blocks per set: direct-mapped caches (associativity of 1) are fast but prone to conflict misses that disrupt locality, while higher associativity (e.g., 8- or 16-way set-associative) reduces such conflicts by 20-50% in typical benchmarks, though at the cost of slightly longer hit times due to parallel tag comparisons. These policies collectively tune the hierarchy to the observed 90%+ hit rates in L1 for locality-rich programs.^[23]^[24] Belady's anomaly illustrates a counterintuitive failure in replacement policies under locality assumptions, where increasing cache size does not always reduce misses and can even increase them for certain access patterns. Named after László Bélády, the anomaly arises in non-optimal policies like FIFO (First-In-First-Out), which evict the oldest block regardless of future use; for a reference string like 1-2-3-4-1-2-5-1-2-3-4-5, a 3-frame FIFO incurs 9 faults, but a 4-frame version incurs 10, violating the expectation that larger caches better capture temporal locality. Even the optimal Bélády algorithm—evicting the block referenced farthest in the future—relies on perfect locality knowledge, which real systems approximate imperfectly, leading to scenarios where scaling up exposes pathological patterns not aligned with typical reuse. This highlights the need for locality-aware policies beyond naive sizing in hierarchy design.^[25]^[26] In modern multi-core CPUs, cache inclusion policies extend hierarchies to handle shared access while preserving locality benefits. Inclusive caches, common in Intel processors, mandate that the L3 contains all L1 and L2 contents, simplifying coherence by allowing snoop broadcasts to check a single point but potentially duplicating data and underutilizing L3 space for temporal locality in private cores. Non-inclusive (or exclusive) designs, as in some AMD architectures, permit L3 to hold data absent from private caches, maximizing effective capacity and hit rates by up to 10-15% in multi-threaded workloads with strong locality, though they complicate coherence protocols with additional invalidations. These extensions balance locality exploitation against inter-core sharing, influencing overall system performance as hierarchies scale to dozens of cores.^[27]^[28]

Algorithm Optimization

Algorithm optimization techniques leverage locality of reference to minimize memory access latencies by restructuring code and data access patterns. These methods target both spatial and temporal locality, ensuring that data likely to be reused is kept in faster memory levels such as caches or registers. By analyzing access patterns and applying transformations, algorithms can achieve significant performance gains without altering their functional correctness. Seminal works in this area emphasize the importance of modeling data reuse to guide optimizations, enabling developers and compilers to tune code for modern hardware hierarchies.^[29] Loop transformations, such as tiling or blocking, enhance spatial locality by partitioning loops into smaller blocks that fit within cache lines, reducing cache misses during nested iterations. For instance, in matrix multiplication, dividing the computation into blocks sized to the cache capacity localizes data accesses, allowing repeated use of the same data within the cache before eviction. This approach, introduced in early blocked algorithm optimizations, can improve cache performance by factors of 2 to 10 depending on the problem size and cache configuration. Tiling also preserves temporal locality by reordering iterations to reuse data soon after loading.^[17]^[30] Data structure selections play a crucial role in exploiting locality, with contiguous structures like arrays preferred over scattered ones like linked lists to capitalize on spatial locality. Arrays enable prefetching of adjacent elements into the cache during sequential access, whereas linked lists often scatter nodes across memory, leading to frequent cache misses and degraded performance in traversal-heavy operations. Cache-oblivious algorithms and data structures further generalize this by designing layouts that perform well across unknown cache hierarchies without explicit tuning, such as recursive matrix layouts that maintain locality at multiple levels. These choices can yield up to 5-10 times faster execution for memory-bound computations compared to non-optimized alternatives.^[31]^[32] Compiler optimizations, including register allocation and instruction scheduling, target temporal locality by keeping frequently accessed data in registers and reordering instructions to maximize reuse proximity. Register allocation assigns variables with high reuse frequency to the limited number of processor registers, minimizing spills to slower memory and exploiting short-term temporal locality; graph coloring techniques ensure conflict-free assignments, reducing execution time by up to 50% in register-poor architectures. Instruction scheduling rearranges code to overlap latencies and group accesses with similar reuse patterns, further enhancing temporal reuse without hardware knowledge. These passes, often performed late in compilation, integrate locality models to prioritize allocations based on live ranges and access distances.^[29] Analysis tools like reuse distance profiling aid in tuning algorithms by quantifying the distance between successive accesses to the same data, providing metrics to evaluate and improve locality. Reuse distance measures the number of unique references between reuses, allowing prediction of cache miss rates under various configurations; for example, distances shorter than cache associativity indicate good temporal locality. Tools employing this metric, such as dynamic analyzers, sample execution traces to recommend transformations like loop reordering, achieving 20-40% reductions in misses for loop-dominated applications. By focusing on whole-program behavior, these tools enable iterative optimization without exhaustive simulations.^[33]^[13]

Specialized Examples

One prominent example of exploiting locality in computing is matrix multiplication, where the standard O(n³) algorithm suffers from poor spatial locality due to strided memory accesses that evict useful data from the cache before reuse.^[17] By dividing the matrices into blocks sized to fit within the cache, the blocked algorithm reuses submatrices multiple times while they remain resident, thereby improving both spatial and temporal locality.^[17] This approach achieves the asymptotically optimal number of cache misses of O(n³ / √M), where M is the cache size in elements, by better exploiting spatial and temporal locality to minimize capacity and conflict misses beyond those in the naive algorithm, which suffers from strided accesses leading to poorer reuse.^[34] In database query processing, B+-tree indexing leverages spatial locality by organizing keys in sorted, contiguous leaf nodes, enabling range queries to perform sequential disk or memory block accesses rather than scattered random reads.^[35] This structure minimizes cache misses during scans, as adjacent keys are likely to be fetched together into the cache, supporting efficient prefetching and reducing I/O latency in systems like relational databases.^[35] For graph traversals, breadth-first search (BFS) exploits temporal locality by processing vertices level by level, reusing adjacency lists of neighboring vertices that remain in cache during the frontier expansion phase.^[36] In compressed sparse row representations, this can amortize cache misses across multiple traversals, improving reuse for connected components.^[37] Performance comparisons highlight the impact of these optimizations; for instance, the general matrix multiply (GEMM) routine in BLAS libraries, which employs blocked algorithms, achieves cache reuse efficiencies approaching 90% on modern processors for moderately sized matrices, leading to near-peak floating-point performance.^[38] In contrast, unoptimized implementations may incur 10-50 times more cache misses, slowing execution by factors of 5-20 depending on matrix dimensions and hardware.^[17] A notable failure case arises in branchy code, where frequent conditional branches disrupt access pattern predictability, leading to branch mispredictions that stall the pipeline and invalidate prefetcher assumptions about future memory references.^[39] This scatters memory accesses, reducing effective temporal locality as recently cached data is evicted before reuse, with misprediction rates exceeding 20% in irregular workloads potentially doubling effective cache miss penalties.^[40]

Advanced and Emerging Uses

Parallel and Distributed Systems

In shared-memory parallel systems, Non-Uniform Memory Access (NUMA) architectures introduce varying access latencies, where local memory fetches are significantly faster than remote ones, impacting spatial locality by increasing the cost of accessing data across nodes. For instance, in NUMA machines like the IBM ACE, local memory access times are about 0.65 μs for fetches compared to 1.5 μs for global memory, leading to performance degradation if data placement does not align with processor affinity, as unrelated objects on the same page can force frequent remote accesses. Operating system techniques, such as page migration and replication in cache-coherent NUMA (CC-NUMA) systems, mitigate this by moving or duplicating pages to processors with high access rates, reducing remote cache misses by up to 52% in engineering workloads and improving execution time by 29%. Cache coherence protocols, such as the MESI (Modified, Exclusive, Shared, Invalid) protocol, preserve temporal locality by managing cache line states to allow repeated local accesses without unnecessary invalidations, enabling private caching for high-locality data blocks in multi-core environments. Locality-aware extensions to MESI further adapt coherence based on runtime profiling, classifying cache lines with a Private Caching Threshold (e.g., 4 accesses) to exploit spatio-temporal reuse, yielding up to 15% faster completion times on 64-core systems. In distributed systems, data locality optimizes computation placement to minimize network overhead, as exemplified by MapReduce frameworks like Hadoop, where tasks are scheduled on nodes holding input data replicas to avoid transferring large datasets. The MapReduce model, built on distributed file systems like GFS, stores files in 64 MB blocks with three replicas and prioritizes local reads during the map phase, ensuring most input data is processed without network involvement in large-scale operations. This approach reduces bandwidth usage by aligning computation with data storage, directly leveraging locality of reference to scale processing across clusters while handling failures through redundant replicas. From a network perspective, joint scheduling algorithms in Hadoop-like systems prefetch data and balance task assignment with routing, stabilizing throughput at higher arrival rates (e.g., 48 tasks per time slot in 200-node clusters) compared to traditional fair schedulers. A key challenge in parallel systems is false sharing, where multiple threads access distinct variables mapped to the same cache line, violating spatial locality through unnecessary coherence traffic and invalidations. This "ping-ponging" effect can degrade performance by up to 160 times in microbenchmarks and 10 times in applications like those in the Phoenix suite, as updates to one variable evict the line from other caches despite no logical dependency. Optimizations address this via affinity scheduling, which binds threads or loop iterations to specific processors to maintain data proximity, such as in locality-based dynamic scheduling (LDS) for NUMA systems that partitions loops into small subtasks and prioritizes local execution, outperforming static methods in varied workloads on machines like Hector. Data partitioning further enhances locality by dividing datasets into balanced chunks aligned with node topology, as in spatial-aware strategies like Spatial-Aware Bucket Balanced Split (SABBS), which groups related data while limiting load per node, achieving up to 1.64 times performance gains in distributed multimedia retrieval over 60 nodes with billions of descriptors.

Modern Hardware Adaptations

In modern graphics processing units (GPUs) and other accelerators, the Single Instruction, Multiple Threads (SIMT) execution model inherently promotes thread-level locality by executing groups of threads in lockstep, allowing shared data accesses to benefit from coalesced memory operations that reduce bandwidth pressure and improve spatial reuse.^[41] Within this model, CUDA's shared memory serves as a programmer-controlled on-chip resource that captures temporal locality by enabling threads within a block to reuse data loaded from global memory, minimizing repeated off-chip accesses and enhancing overall throughput for data-parallel workloads.^[42] Emerging interconnect standards like Compute Express Link (CXL) extend locality of reference across disaggregated devices by providing cache-coherent memory semantics over PCIe, allowing remote memory to be treated as part of a unified address space and enabling efficient data sharing without explicit copying, which mitigates the latency penalties of traditional NUMA hierarchies.^[43] Complementing this, processing-in-memory (PIM) architectures reduce latency gaps in the memory hierarchy by embedding compute units directly within or near DRAM, thereby localizing data movement and exploiting both spatial and temporal locality for bandwidth-bound applications, as demonstrated in low-overhead PIM instruction sets that adaptively monitor access patterns to avoid unnecessary data transfers.^[44] In AI workloads, particularly transformer models, attention mechanisms can leverage spatial locality in token embeddings through IO-aware algorithms like FlashAttention, which employ blockwise tiling to compute attention scores while keeping intermediate results in fast GPU SRAM, avoiding full materialization of large attention matrices in slower HBM and achieving up to 3x speedups on sequence lengths common in language models. Looking to future trends, quantum computing algorithms for tasks like quantum chemistry exploit inherent locality in molecular Hamiltonians by mapping sparse, local interactions to qubit operators with reduced circuit depth, as in locality-optimized variants of the Bravyi-Kitaev transformation, potentially lowering the qubit and gate requirements for practical simulations.^[45] Similarly, neuromorphic systems, inspired by neural architectures, enforce locality constraints in synaptic connections and learning rules, enabling on-chip, distributed processing that mirrors the brain's sparse, local activations and supports energy-efficient computation without relying on von Neumann bottlenecks.^[46]

References

[1]
The Locality Principle - the denning institute
Locality of reference is one of the cornerstones of com- puter science. It was born from efforts to make virtual memory systems work well. Vir-.Missing: original | Show results with:original
[2]
The working set model for program behavior - ACM Digital Library
The working set model for program behavior. Author: Peter J. Denning. Peter J ... Published: 01 May 1968 Publication History. 762citation6,999Downloads.Cited By · Information & Contributors · Author Tags
[3]
The Working Set Model for Program Behavior - cs.wisc.edu
The Working Set Model for Program Behavior. P. J. Denning @ MIT. Communications of the ACM, May 1968, pages 323-333. Goal. Develop a unified approach to tackle ...
[4]
[PDF] Locality of Reference - CS@Cornell
If a process access a memory location, then it is likely that the same memory location is going to be accessed again in the near future (temporal locality).
[5]
The locality principle
Locality of reference is one of the cornerstones of com- puter science. It was born from efforts to make virtual memory systems work well. Vir-.
[6]
[PDF] Quantifying Locality In The Memory Access Patterns of HPC ...
This paper proposes a method to quantify spatial and temporal locality in memory access patterns of HPC applications using architecture-independent metrics.
[7]
None
### Summary of Temporal and Spatial Locality from the PDF
[8]
The working set model for program behavior
The working set model is a new model where the working set of pages, the most recently used pages, provides vital knowledge for dynamic memory management.
[9]
Properties of the working-set model
A program's working set W(t, T) at time t is the set of distinct pages among the T most recently referenced pages. Relations between the average.
[10]
Cache performance of SPEC CPU2000 - Computer Sciences Dept.
On this webpage, we present functional cache miss ratios and related statistics for the SPEC CPU2000 suite.
[11]
Evaluation techniques for storage hierarchies - IEEE Xplore
IBM Systems Journal >Volume: 9 Issue: 2. Evaluation techniques for storage hierarchies. Publisher: IBM. Cite This. PDF. R.L. Mattson ; J. Gecsei ; D. R. Slutz
[12]
The Stack Growth Function: Cache Line Reference Models
SGFs measured for some 40 real programs show that a simple exponential model fits the SGFs reasonably well over a range of execution intervals. Parameters of ...
[13]
[PDF] Program locality analysis using reuse distance - Research
Mattson et al. [1970] gave the first algorithm, which used a stack. Bennett and Kruskal [1975] observed that a stack was too slow to measure ...
[14]
[PDF] Locality Principle. - the denning institute
Jun 22, 2008 · Locality is a universal behavior of all computational processes: They tend to refer repeatedly to subsets of their resources over extended ...Missing: paper | Show results with:paper
[15]
A Study of Separate Array and Scalar Caches. - ResearchGate
... locality of reference. [4], which is a property exhibited by most programs. A ... We achieve almost a 10X speedup in execution time compared to non-optimized C ...
[16]
[PDF] The Cache Performance and Optimization of Blocked Algorithms
By reusing data in the faster level of the hierarchy, it cuts down the average access latency. It also reduces the number of references made to slower levels ...
[17]
The Locality Principle - Communications of the ACM
Jul 1, 2005 · Locality of reference is one of the cornerstones of computer science. It was born from efforts to make virtual memory systems work well.Missing: original paper
[18]
[PDF] A Data Locality Optimizing Algorithm - SUIF Compiler
In general, tiling transforms an n-deep loop nest into a 2n-deep loop nest where the inner n loops execute a compiler-determined number of iterations. Figure 4 ...
[19]
[PDF] Measuring Cache and TLB Performance and Their Effect on ...
Our measurement technique involves the timing of operations executed repeatedly within small loops; in such cases, few cache and TLB misses are encountered.<|control11|><|separator|>
[20]
[PDF] The Memory Hierarchy
Sep 23, 2025 · ⬛ References array elements in succession (spatial locality). ⬛ References sum and i each iteration (temporal locality; put in registers).
[21]
[PDF] Memory Management - cs.Princeton
• Registers as cache of L1/L2 cache and main memory. • Main memory as a cache for the disk. • Disk as a cache of files from remote storage. • Locality of ...
[22]
[PDF] 03-04-memory-hierarchy.pdf - Overview of 15-740
Temporal Locality: If a location is referenced it is likely to be referenced again in the near future. Spatial Locality: If a location is referenced it is ...
[23]
[PDF] Chapter 2: Memory Hierarchy Design – Part 2
Cache size is the total capacity of the cache. Bigger caches exploit temporal locality better than smaller caches. But are not always better.
[24]
[PDF] Beyond Physical Memory: Policies - cs.wisc.edu
The optimal replacement policy leads to the fewest number of misses overall. Belady showed that a sim- ple (but, unfortunately, difficult to implement!)
[25]
[PDF] Cache Replacement Policy - Washington
Belady's Anomaly. FIFO (3 ,slots). Reference A. B C D. A B E. A B C. D E. A. D. E. +. 2 ... • MIN is optimal. - replace the page or cache entry that will be used.
[26]
[PDF] Achieving Non-Inclusive Cache Performance with Inclusive Caches
We propose Temporal Locality Aware (TLA) cache management policies to allow an inclusive LLC to be aware of the temporal locality of lines in the core caches.
[27]
[PDF] Non-Inclusion Property in Multi-level Caches Revisited
The inclusion property, which dictates that the contents of a lower level cache be a subset of those of a higher level cache, is highly desired in a ...
[28]
[PDF] Compiler Optimizations for Improving Data Locality
the best loop permutation. Wolf and Lam use unimodular transformations and tiling with estimates of temporal and spatial reuse to improve data local- ity ...
[29]
[PDF] Improving Data Locality with Loop Transformations
In this article, we present compiler optimizations to improve data locality based on a simple yet accurate cost model. The model computes both temporal and ...
[30]
Improving the cache locality of memory allocation - ACM Digital Library
Our measurements show that poor locality in sequential-fit allocation algorithms reduces program performance, both by increasing paging and cache miss rates.
[31]
[PDF] Cache-Oblivious Algorithms and Data Structures - Erik Demaine
ousness, introduced by Frigo, Leiserson, Prokop, and Ramachandran in. 1999. Cache-oblivious algorithms perform well on a multilevel memory hierarchy without ...
[32]
[PDF] Predicting Whole-Program Locality through Reuse Distance Analysis
First, reuse distance is at most a linear function of program data size. The search space is therefore much smaller for pattern recognition and prediction.
[33]
[PDF] Cache-Oblivious Algorithms
Many of the results in this thesis are based on a joint paper [21] coauthored by. Matteo Frigo, Charles E. Leiserson, and Sridhar Ramachandran. 12. Page 9 ...
[34]
[PDF] Fractal Prefetching B -Trees: Optimizing Both Cache and Disk ...
This paper, however, is the first to propose a B+-Tree index structure that effec- tively optimizes both CPU cache and disk performance on modern processors, ...
[35]
[PDF] The More the Merrier: Efficient Multi-Source Graph Traversal
Multi-Source BFS (MS-BFS) runs multiple concurrent BFSs on a single CPU core, sharing computation, reducing memory accesses, and avoiding synchronization costs.
[36]
CGAcc: A Compressed Sparse Row Representation-Based BFS ...
Nov 7, 2018 · Graph traversal suffers from memory stalls and cache misses due to limited spatial locality. Spatial locality for traversal only exists in ...<|separator|>
[37]
[PDF] High-Performance Implementation of the Level-3 BLAS
Right: The curves labeled “Pack A” and “Pack B” indicate the percent of total time spent in each of these operations.
[38]
[PDF] The Effects of Predicated Execution on Branch Prediction
Predication removes branch instructions, affecting branch prediction accuracy, branch penalty, and basic block size. Branch prediction eliminates branch delay.
[39]
[PDF] Branch prediction, instruction-window size, and cache size
Using an RUU eliminates artifacts arising from interactions between active-list size and issue- queue size and reduces the already large number of variables we ...
[40]
Locality-Driven Dynamic GPU Cache Bypassing - ACM Digital Library
This paper presents novel cache optimizations for massively parallel, throughput-oriented architectures like GPUs. L1 data caches (L1 D-caches) are critical ...
[41]
A locality-aware memory hierarchy for energy-efficient GPU ...
We investigate the locality of reference at different cache levels in the memory hierarchy. At the L1 cache level, we look into the locality behavior at the ...
[42]
An Introduction to the Compute Express Link (CXL) Interconnect
Jul 8, 2024 · CXL enables coherency and memory semantics and builds on top of PCIe' s physical subsystem. Non-coherent accesses work well for streaming I/O ...
[43]
a low-overhead, locality-aware processing-in-memory architecture
In addition, we introduce a simple hardware structure that monitors the locality of data accessed by a PIM-enabled instruction at runtime to adaptively execute ...
[44]
Exploiting Locality in Quantum Computation for Quantum Chemistry
We show that the utilization of spatial locality combined with the Bravyi–Kitaev transformation offers an improvement in the scaling of known quantum algorithms ...
[45]
[PDF] Loihi: A Neuromorphic Manycore Processor with On-Chip Learning
Once a learning rule satisfies the locality constraint, the inherent parallelism offered by SNNs will allow the adaptive network to be scaled up to large ...