Principle of locality (temporal - spatial): Foundations

This page assumes you have seen almost nothing. Before you can read the parent note on locality, we must earn every word it uses: address, memory location, access, reference, cache, block, hit/miss, reuse distance, stride, and the bits of arithmetic notation ( $A_{i}$ , $∣ \cdot ∣$ , $⌈ \cdot ⌉$ , $\sum$ , $P (\cdot)$ ) it leans on. We build them in the exact order they depend on each other.

1. Memory as a long street of numbered boxes

Everything starts here. Forget circuits — picture a very long street of identical boxes in a row. Each box holds a small number. Each box has a permanent house-number painted on it.

Figure — Principle of locality (temporal - spatial)

A subtle but vital point drawn in the figure: consecutive addresses sit physically side by side. Address $0 x 1004$ is the box immediately to the right of $0 x 1000$ . "Close in number" means "close in space." Hold onto that — it is the whole engine of spatial locality.

Recall

A memory location vs. an address ::: The location is the box (the physical slot); the address is the number painted on it.

2. Accessing and referencing a box

The parent talks about a program doing a sequence of accesses. Picture a stream of tickets, one per access, each stamped with the address touched:

$A_{1}, A_{2}, A_{3}, \dots$

3. Two questions we ask about the list — and the symbols that answer them

The parent note squeezes each flavour of locality into a tiny formula. Each formula is one question about the list $A_{1}, A_{2}, \dots$ . Let us earn the arithmetic first.

3a. Distance-between-two-numbers: absolute value $∣ \cdot ∣$

Why does the topic need this? To measure how far apart two consecutive addresses are:

$Stride = ∣ A_{i + 1} - A_{i} ∣$

Here $A_{i + 1} - A_{i}$ is "next box number minus this box number." If the program stepped forwards the difference is positive; if it jumped backwards it is negative. We only care how big the jump was, not its direction — so we wrap it in $∣ \cdot ∣$ .

Recall

Why absolute value in the stride formula ::: A backward step ( $A_{i + 1} < A_{i}$ ) gives a negative difference, but we only care about the distance jumped, so we strip the sign.

3b. Counting distinct visitors: reuse distance

The topic writes this counting job with a name; the machinery of "count the unique items between two markers" is what the formula in the parent means. No new symbol — just the word "count."

4. The word-vs-byte trap, and why blocks exist

5. The last few notation gadgets the parent uses

6. How it all feeds the topic

Once these foundations are in place you are ready for Cache organization fundamentals and Cache mapping strategies (how the shelf is arranged), the Working set model (formalising "the small portion in use"), and Loop blocking and tiling (fixing the bad-stride matrix case). Later, Virtual memory reuses locality at a coarser page grain.

Equipment checklist

Self-test: can you answer each before moving on?

What is a memory location versus its address?

The location is the physical box; the address is the number labelling it.

What does

A_{i}

mean, and what does it not mean?

The address touched by the

i

-th access; it is NOT

A

times

i

Why does the stride formula use absolute value

∣ A_{i + 1} - A_{i} ∣

We want the size of the jump, not its direction, so we discard the sign.

Define reuse distance in one sentence.

The count of distinct addresses accessed between two touches of the same address.

Why is array stride 4 bytes when we step one element at a time?

One int word is 4 bytes, so the next element sits 4 addresses along.

What does a cache block do that makes spatial locality useful?

It scoops a contiguous run of neighbouring boxes in one fetch, so nearby later accesses are free hits.

What is the difference between a hit and a miss?

A hit finds the box already on the fast shelf; a miss must fetch its whole block from slow memory.

Why does

⌈ 1000/16 ⌉ = 63

and not

62

The 8 leftover accesses still need one more fetch; you round up because you can't have a partial miss.

What does

P (hit) = 0.9

tell you?

9 out of every 10 accesses are served from the cache.