Type: Process Essays
Sample donated: Gilbert Pope
Last updated: September 16, 2019
Locality of reference, or the principle of locality, is “the basisfor the performance advantage of a two-level memory” (Stallings, 2013), which standsfor that predictable behaviour of the processor, whereby the same memorylocation set, or relative storage locations, are frequently or repeatedlyaccessed over a brief time period. The first basic reference locality type iscalled Temporal, wherein specific, recently used data, and resources, ifapplicable, are reused within relatively small timeframes, such as in the caseof iteration loops. The second basic reference locality type is called Spatial,which involves the use and execution of data located in clusters, and incertain cases, such as its Sequential locality subset, arranged and accessed ina linear, sequential fashion, such as when processing data tables.
The rationalebehind reference locality is that memory references have a tendency to formclusters, and although the clusters in use by the system change over long timeperiods, over relatively shorter time spans, instead, the processor mainly handlesunchanged, memory cluster references. One of the reasons why locality ofreference is logical is because program execution is largely sequential, exceptingcall and branch instructions, and therefore, often, the processor fetches instructions,the one immediately following the other. Another reasoning is that whilelengthy, continuous, procedure call and, subsequent, return sequences mightoccasionally occur, what mostly happens is that temporal references toinstructions are localised to a small number of procedures, due to programsbeing limited to narrow windows of procedure-invocation depth. Also, it iscommon for iterative constructs to have few instructions which are repeatedfrequently, implying that computation, during iterations, is limited to smalland neighbouring program portions. Lastly, it is usual in programs that incomputations that process data structures, such as arrays or record sequences,that the consecutive data structure references be data items that are closelypositioned.Latency andthroughput are ultimately impacted by cache efficiency, despite RAM (RandomAccess Memory) giving programmers the ability to read and write at any locationat will. A cache, being a faster, albeit smaller memory area than RAM, exploitsthe Temporal locality of reference by keeping recently referenced data valuesand their contiguous elements in tight clusters in the machine registers, to augmentperformance, while data with poor reference locality is bypassed altogether toavoid cache thrashing or pollution (En.
wikipedia.org, 2018). Since computermemory is hierarchically divided to increase data access speed (L1 cache >L2 cache > L3 cache > main memory), where the lower memory levels areprogressively slower, but larger, programs using memory cached higher up thehierarchy will achieve greater performance than those substituting data cachedfor short-term use with new data elements. Hierarchical memory leverages bothTemporal as well as Spatial locality since it is an optimisation available atseveral memory hierarchy levels, a good example being Paging which greatlybenefits from this (En.wikipedia.
org, 2018). In modern machines the operatingsystem employs prediction algorithms to guess the data items least likely to beaccessed and migrate the same to lower points of the memory hierarchy tofurther optimise system performance. Spatial locality, instead, is, largely,exploited through the employment of large blocks of cache and via prefetching mechanismsthat import items, in anticipation of their use, into the cache control logic. Although,these cached data elements may not match spatially close items within the mainmemory, they are imported into the cache sequentially (one cache line at atime), thus allowing the cache to import not only the referenced elements butalso contiguous ones. Thus, locality of reference is extensively exploited bycache to improve performance.