Locality of reference: Difference between revisions

Revision as of 01:13, 6 May 2021

Latest revision as of 02:47, 21 July 2025

(18 intermediate revisions by 18 users not shown)

Line 1:

{{Short description|tendencyTendency of a processor to access nearby memory locations in space or time}}

{{more citations needed|date=July 2008}}

In [[computer science]], '''locality of reference''', also known as the '''principle of locality''',<ref>Not to be confused with the [[principle of locality]] o=s*v=411##sts in physics.</ref> is the tendency of a processor to access the same set of memory locations repetitively over a short period of time.<ref>{{Cite book|title=Computer organization and architecture : designing for performance|last=William.|first=Stallings|date=2010|publisher=Prentice Hall|isbn=9780136073734|edition= 8th|___location=Upper Saddle River, NJ|oclc=268788976}}</ref> There are two basic types of reference locality {{sndNdash}} temporal and spatial locality. Temporal locality refers to the reuse of specific data and/or resources within a relatively small time duration. Spatial locality (also termed ''data locality'')<ref name="NistBig1">"NIST Big Data Interoperability Framework: Volume 1", [https://doi.org/10.6028/NIST.SP.1500-1r2 urn:doi:10.6028/NIST.SP.1500-1r2</ref>) refers to the use of data elements within relatively close storage locations. Sequential locality, a special case of spatial locality, occurs when data elements are arranged and accessed linearly, such as traversing the elements in a one-dimensional [[Array data structure|array]].

Locality is a type of [[predictability|predictable]] behavior that occurs in computer systems. Systems thatwhich exhibit strong ''locality of reference'' are greatgood candidates for performance optimization through the use of techniques such as the [[CPU cache|caching]], [[prefetch instruction|prefetching]] for memory and advanced [[branch predictor]]s at the [[Pipeline (computing)|pipelining]] stage of a processor core.

== Types of locality ==

Line 43:

Typical memory hierarchy (access times and cache sizes are approximations of typical values used {{As of|2013|lc=on}} for the purpose of discussion; actual values and actual numbers of levels in the hierarchy vary):

* [[CPU register]]s (8–256 registers) &ndash; immediate access, with the speed of the innermost core of the processor

* L1 [[CPU cache]]s (32&nbsp;KiBKB to 512&nbsp;[[KiBkilobyte|KB]]) &ndash; fast access, with the speed of the innermost memory bus owned exclusively by each core

* L2 CPU caches (128&nbsp;KiBKB to 24&nbsp;[[MiBmegabyte|MB]]) &ndash; slightly slower access, with the speed of the [[memory bus]] shared between twins of cores

* L3 CPU caches (2&nbsp;MiBMB up to 32a max of 64&nbsp;[[MiBmegabyte|MB]]) &ndash; even slower access, with the speed of the memory bus shared between even more cores of the same processor

* Main [[physical memory]] ([[random-access memory|RAM]]) (256&nbsp;MiBMB to 64&nbsp;[[GiBgigabyte|GB]]) &ndash; slow access, the speed of which is limited by the spatial distances and general hardware interfaces between the processor and the memory modules on the [[motherboard]]

* Disk ([[virtual memory]], [[file system]]) (1&nbsp;GiBGB to 256&nbsp;[[TiBterabyte|TB]]) &ndash; very slow, due to the narrower (in bit width), physically much longer data channel between the main board of the computer and the disk devices, and due to the extraneous software protocol needed on the top of the slow hardware interface

* Remote memory (other computers or the cloud) (practically unlimited) &ndash; speed varies from very slow to extremely slow

Line 96:

On a year 2014 processor, the second case is approximately five times faster than the first case, when written in [[C (programming language)|C]] and compiled with <code>gcc -O3</code>. (A careful examination of the disassembled code shows that in the first case, [[GNU Compiler Collection|GCC]] uses [[SIMD]] instructions and in the second case it does not, but the cache penalty is much worse than the SIMD gain.){{Citation needed|date=September 2014}}

Temporal locality can also be improved in the above example by using a technique called [[Loop blocking|blocking]]. The larger matrix can be divided into evenly sized sub-matrices, so that the smaller blocks can be referenced (multiplied) several times while in memory. Note that this example works for square matrices of dimensions SIZE x SIZE, but it can easily be extended for arbitrary matrices by substituting SIZE_I, SIZE_J and SIZE_K where appropriate.

<syntaxhighlight lang="pascal" line="1">

Line 124:

* [[Scratchpad memory]]

* [[Working set]]

* [[Heuristic]]

* [[Locality-sensitive hashing]]

== References ==

Line 130 ⟶ 132:

== Bibliography ==

* [[Peter J. Denning]], [http://denninginstitute.com/pjd/PUBS/CACMcols/cacmJul05.pdf "The Locality Principle"], ''Communications of the ACM'', Volume 48, Issue 7, (2005), Pages 19–24

* Peter J. Denning, Stuart C. Schwartz, [http://denninginstitute.com/pjd/PUBS/WSProp_1972.pdf "Properties of the Working-Set Model"], ''Communications of the ACM'', Volume 15, Issue 3 (March 1972), Pages 191-198191–198

{{DEFAULTSORT:Locality Of Reference}}