Locality of Reference [7M]

Principle: Program memory access is not random but clustered. Observed empirically (Denning, 1968). Foundation for cache, virtual memory and hierarchy design. $90\%$ execution time in $10\%$ code.

1. Types:

• Temporal Locality: If location $X$ is referenced at time $t$, it will likely be referenced again soon (near future).
  Reason: Loops, reuse of variables, stack, counters.
  Example:

  for(i=0;i<1000;i++) sum += a[i]; // `sum` reused every iteration
  

  sum accessed every iteration -> temporal.

• Spatial Locality: If location $X$ is referenced, nearby locations $X+\Delta$ will likely be referenced soon.
  Reason: Sequential instruction execution, array traversal, contiguous structures.
  Example: a[0], a[1], a[2]... contiguous words -> fetching a[i] brings cache block of 64B (8 words) -> next 7 accesses are hits. Instructions are sequential as well.

• Sequential Locality: Special case of spatial - next instruction is $PC+1$ unless branch.

2. Implications / Applications:

• Cache Memory: Block size $>1$ word exploits spatial locality. Upper level stores working set exploiting temporal. LRU replacement exploits temporal. Without locality, hit ratio $\to 0$ and cache useless.
• Virtual Memory / Paging: Keep working set in RAM; pages brought on locality basis. Thrashing occurs when locality violated / working set exceeds frames.
• Prefetching: Hardware prefetcher fetches $next\ line$ based on spatial.
• Branch prediction & instruction cache: Sequential locality predicts next fetch.
• Quantified: Hit ratio $h \approx 0.9-0.98$ for L1 when locality high. Effective access time: $T_{eff}= h\cdot T_{cache} + (1-h)\cdot T_{memory}$ -> makes $T_{eff}\approx T_{cache}$.

3. Working Set Theory:

Denning: $W(t,\tau)$ = set of pages referenced in last $\tau$ references. Locality implies $|W|$ small (e.g. 2-4 pages) vs total size. OS tries to keep $W$ resident. If $\sum W_i >$ physical memory -> thrashing.

4. Example Calculation:

Loop touches 1K word array stride 1 with 64B block (16 words):
Without spatial exploitation: 1000 misses. With block: $\approx 1000/16 =63$ misses -> 93% hit rate due to spatial.

5. Violations:
Linked list with nodes scattered, random pointer chasing, large stride $> block size$ defeats spatial locality; large data set with no reuse defeats temporal -> cache pollution.

Conclusion: Locality of reference bridges speed gap between CPU and memory; hierarchy design (register-cache-main-disk) succeeds only because of it.