Principle of locality (temporal - spatial): Exercises

This page is a self-test ladder. Each rung is harder than the last: L1 you just recognise the idea, by L5 you design around it. Read the problem, try it yourself, then open the collapsible solution.

Everything here builds on the parent locality note. If a term feels shaky, the Cache organization fundamentals and Cache mapping strategies notes hold the prerequisites; Working set model and Loop blocking and tiling extend the last few exercises.

Before we start, some words we will lean on constantly:

Figure — Principle of locality (temporal - spatial)

Figure s01 — your mental model for the whole page: memory is a long tape of bytes (top row, addresses increasing rightward); one block is the orange fixed-width window of $B_{c}$ contiguous bytes that gets fetched together on a miss; the teal shelf at the bottom is the cache, holding only $C$ such windows at a time. Keep this picture in mind — every exercise is really "which window is on the shelf right now?"

Level 1 — Recognition

Goal: can you name which locality is at play?

Exercise 1.1

For each access pattern, say temporal, spatial, or both:

(a) for(i=0;i<n;i++) s += a[i]; — the variable s
(b) the same loop — the array elements a[i]
(c) while(1){ handle(); } — the instructions of handle
(d) reading p->next->next->next down a linked list scattered across memory

Recall Solution 1.1

(a) s sits at one address, touched every iteration → temporal. (b) a[0], a[1], … are different but adjacent addresses → spatial. (There's mild temporal reuse too, but the dominant effect is spatial.) (c) The instruction addresses of handle repeat each loop → temporal. (Within one call they also run in sequence → spatial. So really both, but the loop makes temporal dominate.) (d) Each next is a new, far-away address with no neighbour reuse and no repeat → neither. This is the classic locality-killer: pointer chasing.

Exercise 1.2

A cache holds $C = 8$ blocks. Address $X$ is accessed, then 5 distinct other blocks are accessed, then $X$ is accessed again. Hit or miss on the second $X$ ?

Recall Solution 1.2

The reuse distance (defined above) is $d = 5$ (distinct blocks touched between the two references to $X$ ). Rule for our fully-associative LRU model: hit iff $d < C$ . Here $5 < 8$ , so $X$ is still on the shelf → hit. (In a set-associative cache this could still miss if those 5 blocks all collide with $X$ 's set — a conflict miss — but with full associativity we are safe.)

Level 2 — Application

Goal: plug numbers into the reuse-distance and stride machinery.

Exercise 2.1

A 64-byte block. int is 4 bytes. You loop for(i=0;i<64;i++) sum += a[i]; with stride 1. How many misses, how many hits, and what hit rate (spatial only)?

Recall Solution 2.1

Using the word size $w = 4$ bytes defined above, one block holds $B_{c} / w = 64/4 = 16$ ints. Accessing 64 ints in order:

Access to a[0] misses, pulls in a[0..15] → next 15 are hits.
Pattern repeats every 16 ints. $misses = \frac{64}{16} = 4, hits = 64 - 4 = 60.$ $hit rate = \frac{60}{64} = 0.9375 = 93.75%.$ This matches the parent's steady-state formula, which we can now state cleanly with the symbols defined here: for stride-1 access the miss rate is $w / B_{c}$ (one miss per block of $B_{c} / w$ elements), so the hit rate is $1 - \frac{w}{B _{c}} = 1 - \frac{4}{64} = \frac{15}{16} .$

Exercise 2.2

Same block, same array, but now for(i=0;i<64;i+=8) — stride 8 ints = 32 bytes. How many misses out of the 8 accessed elements?

Recall Solution 2.2

You access a[0], a[8], a[16], …, a[56] — that's 8 elements. Stride in bytes $= 8 \times 4 = 32$ . Block is 64 bytes, so two of your accessed elements can fit in one block:

Block containing a[0..15] holds a[0] and a[8] → 1 miss + 1 hit.
Block containing a[16..31] holds a[16] and a[24] → 1 miss + 1 hit.
… four blocks total. $misses = 4, hits = 4, hit rate = 4/8 = 50%.$ Doubling stride roughly halved our spatial benefit.

Exercise 2.3

Stride grows to 16 ints = 64 bytes, exactly one block. Accessing 8 elements. Misses?

Recall Solution 2.3

Now each accessed element lands in a fresh block (stride = block size). No two share a block. $misses = 8, hit rate = 0%.$ Spatial locality is completely dead once the stride reaches the block size — every fetch drags in 60 useless bytes.

Figure s02 — the pedagogical point of Exercises 2.1–2.3 in one image: a single 64-byte block splits into 16 int-slots. The teal slots are the ones stride-1 access actually touches (many hits per block); the plum slots show stride-8 touching only 2 of the 16, so the other 14 bytes are fetched-but-wasted. The figure makes the L2 trap visible — hits come from slots you touch, not from slots that exist.

Level 3 — Analysis

Goal: reason about a whole algorithm's locality, including the bad cases.

Exercise 3.1 — Row vs column traversal

Row-major matrix, $N = 1024$ , int = 4 bytes, block = 64 bytes (16 ints).

(a) Summing row by row: for i { for j { s += M[i][j]; } }. Miss rate?
(b) Summing column by column: for j { for i { s += M[i][j]; } }. Miss rate?

Recall Solution 3.1

Row-major means M[i][j] sits at address $base + (i \cdot N + j) \cdot 4$ . Along a row ( $j$ varies) addresses are contiguous; down a column ( $i$ varies) they jump by $N \cdot 4 = 4096$ bytes.

(a) Row by row — stride 1. 16 ints per block → 1 miss per 16 accesses. $miss rate = \frac{1}{16} = 6.25%.$

(b) Column by column — stride 4096 bytes. Compare stride to block size directly: stride $= 4096 B$ , block $= 64 B$ , and $4096/64 = 64$ . Because the stride is 64 whole blocks long, consecutive accesses never share a block — each M[i][j] for successive $i$ lands in a different, freshly-fetched block, so every access is a compulsory miss. Could an earlier column's block still be resident when we come back? No: between two accesses to the same block (one full column apart), we touch $N = 1024$ other blocks, so the reuse distance is $d = 1024$ . Any cache with fewer than $1024$ blocks (which, at 64 B each, means smaller than 64 KB) has $d \geq C$ → evicted before reuse. For the realistic caches assumed on this page, therefore: $miss rate = 100%.$

Same arithmetic, same data — a 16× difference in miss rate purely from traversal order.

Figure s03 — Exercise 3.1 drawn on a small row-major grid. The teal arrow sweeps a row: consecutive addresses, so 16 elements ride in on one block (6.25% miss). The plum arrow walks a column: each step jumps $N$ elements to a brand-new block (100% miss). The two arrows carry identical arithmetic — the figure shows that only the traversal order differs, which is the whole lesson of L3.

Exercise 3.2 — Reuse distance decides it

A cache holds $C = 100$ blocks. Two loops each re-access the same address after touching, respectively, $d_{1} = 60$ and $d_{2} = 140$ distinct blocks in between. Which loop's reuse is a hit?

Recall Solution 3.2

Hit iff $d < C$ (fully-associative LRU).

Loop 1: $d_{1} = 60 < 100$ → hit (the block survived).
Loop 2: $d_{2} = 140 \geq 100$ → miss (evicted before reuse). The temporal locality of loop 1 is captured by this cache; loop 2's is not. Enlarging the cache to $C \geq 141$ blocks would rescue loop 2 — this is exactly why bigger caches capture longer reuse distances.

Level 4 — Synthesis

Goal: combine locality with a cost model and make a design decision.

Exercise 4.1 — Is a bigger block worth it?

Fixed cache size 32 KB, fully-associative LRU.

Option A: block = 32 B → $32768/32 = 1024$ blocks.
Option B: block = 256 B → $32768/256 = 128$ blocks.

A workload streams sequentially through a 4 KB region once (pure spatial, stride 1), then randomly re-accesses 500 distinct 32-byte units with strong temporal reuse. For the temporal phase, count how many 32-byte units each configuration can actually hold, then decide which block size wins.

Recall Solution 4.1

Spatial part (streaming 4 KB once):

A: $4096/32 = 128$ misses.
B: $4096/256 = 16$ misses. Bigger block wins the streaming phase (fewer misses, better spatial locality).

Temporal part — do the capacity arithmetic, don't assert it. The cache is 32 KB = 32768 bytes either way. Convert its total capacity into 32-byte units: $units held = \frac{32768 B}{32 B/unit} = 1024 units, for BOTH options.$ Total bytes is fixed, so both configurations physically store 1024 of our 32-byte working-set units. Since the working set is only 500 units, both A and B can retain all 500 — neither thrashes on the temporal phase. (Option B holds $128$ lines $\times 256/32 = 8$ units each $= 1024$ units; Option A holds $1024$ lines $\times 1$ unit $= 1024$ units. Same total.)

So the temporal phase is a tie on this idealised fully-associative cache. The decision therefore turns on the spatial phase, where Option B had far fewer misses ( $16$ vs $128$ ).

Verdict: on this idealised model, Option B (256-byte blocks) wins — it matches A's temporal capacity yet crushes the streaming misses.

The real-world caveat (why "bigger is always better" is still false). This tie only holds because we assumed full associativity and a working set of exactly 500 units that each map to whatever free slot. Two things break Option B in practice:

If the 500 units are scattered (not 8-consecutive), a 256-byte line drags in up to 7 useless units per fetch — you may need far more than 500 lines' worth of bytes to cover 500 scattered units, and then B does run short of lines.
Real caches are set-associative; larger lines mean fewer sets, so more conflict misses. The clean tie above is the best case for big blocks; the parent Cache mapping strategies and the L4 trap below show where it collapses.

Exercise 4.2 — Derive the crossover for scattered working-set units

Now suppose the 500 working-set units are scattered — no two share a block. Then each unit needs its own line, and a config with line size $B_{ℓ}$ (the same quantity as the block size $B_{c}$ — we just rename it $B_{ℓ}$ because here it is the variable we are choosing) holds only $32768/ B_{ℓ}$ lines. What is the largest line size that still holds all 500 scattered units?

Recall Solution 4.2

Need (number of lines) $\geq$ (number of scattered units): $\frac{32768}{B _{ℓ}} \geq 500 \Rightarrow B_{ℓ} \leq \frac{32768}{500} = 65.5 bytes \Rightarrow B_{ℓ} = 64 B (largest power of two that fits) .$ So when units are scattered, a 64-byte line is the sweet spot: as spatially generous as possible while still giving 500 distinct lines. Push to 256-byte lines and you drop to $128$ lines $< 500$ → now Option B does thrash. This is precisely the "bigger blocks trade temporal capacity for spatial reach" trade-off — but only once locality within a line is poor.

Level 5 — Mastery

Goal: reason at the level of designing an access pattern from scratch.

(From here on, plain $B$ denotes the matrix $B$ in a multiply. The cache block size stays $B_{c}$ , exactly as defined at the top — no collision.)

Exercise 5.1 — Blocking the matrix multiply

The naive i,j,k multiply reads $B [k] [j]$ down a column (stride $N$ , miss every access). We tile the loops so each inner region works on a $b \times b$ sub-block that fits in cache. If cache holds $C$ ints and we must simultaneously hold sub-blocks of $A$ , $B$ , and $C$ (three $b \times b$ tiles), what is the largest tile size $b$ ? Evaluate for $C = 8192$ ints.

Recall Solution 5.1

Three tiles of $b^{2}$ ints each must coexist: $3 b^{2} \leq C \Rightarrow b \leq C /3 .$ For $C = 8192$ : $b \leq 8192/3 = 2730.67 \approx 52.3$ , so pick $b = 52$ (or a friendly power-of-two-ish $b = 32$ in practice for alignment).

Why it works: once a $b \times b$ tile of matrix $B$ is loaded, every element is reused $b$ times before eviction — we converted the terrible stride- $N$ column reads into temporal locality on a small resident tile. This is the payoff of Loop blocking and tiling.

Exercise 5.2 — Reuse count after blocking

In the tiled multiply above, how many times is each loaded element of a $B$ -tile reused before it leaves cache, and what does that do to matrix $B$ 's effective miss rate compared to the naive $100%$ ?

Recall Solution 5.2

Each element of a $b \times b$ $B$ -tile participates in updating a whole column-strip of the $b \times b$ $C$ -tile → it is used $b$ times per tile pass. So one miss now serves $b$ useful accesses: $miss rate for matrix B \approx \frac{1}{b} .$ For $b = 52$ : miss rate $\approx 1/52 \approx 1.92%$ , versus $100%$ naive — a ~52× reduction in misses on $B$ . That is locality engineered by hand.

Exercise 5.3 — Working set and virtual memory

A program's working set (distinct pages touched in a time window) is 200 pages. Physical memory gives it 150 page frames. Predict the behaviour and connect it to locality.

Recall Solution 5.3

Working set $= 200 >$ frames $= 150$ . The program cannot keep its actively-used pages resident → each window it evicts pages it will need again → thrashing (constant page faults, disk-latency stalls). This is the reuse-distance argument at the page granularity: when the Working set model size exceeds capacity, temporal locality can no longer be captured, exactly as $d \geq C$ caused cache misses. See Virtual memory for the paging mechanism. The fix: give it $\geq 200$ frames, or restructure the code (tiling!) to shrink the working set below 150.

Recall Quick self-check (cloze)

Reuse distance $d$ hits (fully-assoc LRU) when ::: $d < C$ (cache holds $C$ blocks). Spatial locality dies when stride reaches ::: the block size $B_{c}$ . Largest tile with 3 resident $b \times b$ tiles ::: $b \leq C /3$ . Blocking cuts matrix $B$ 's miss rate from 100% to ::: about $1/ b$ . Real caches add which extra miss type beyond the LRU model? ::: conflict misses (from set-associativity).