Worked examples — Principle of locality (temporal - spatial)

5.4.1 · D3 · Hardware › Memory Hierarchy & Caches › Principle of locality (temporal - spatial)

Yeh page parent note on locality ka hands-on companion hai. Wahan humne dono localities define ki thi. Yahan hum unhe compute karte hain — ek worked example per "flavour of situation" jo ek program cache ke saath kar sakta hai — including kuch weird degenerate cases (zero reuse distance, infinite stride, random access) jo parent note mein sirf passing mein mention hue the.

Koi bhi number dekhne se pehle, aao hum un do rulers par agree kar lein jinse hum locality measure karte hain. Dono parent note mein introduce ki gayi thi, lekin chaliye inhe re-anchor karte hain taaki kuch assume na karna pade.

Hum ek aur derived quantity bhi poore note mein use karenge:

---

The scenario matrix

Is chapter mein locality ka har problem in cells mein se ek hoga. Har worked example neeche us cell ke saath tagged hai jo wo cover karta hai, isliye milke poori table cover ho jaati hai.

Cell	Access pattern	Stride	Reuse distance	What it stresses
A	Sequential sweep, stride 1	$=1$ word	$=\infty$ (kabhi reuse nahi)	Pure spatial
B	Same address repeated	$=0$	$=0$	Pure temporal
C	Loop over array plus ek accumulator	mixed	mixed	Dono saath mein
D	Row-major matrix ka column walk	$=N$ words (bahut bada)	large	Spatial broken
E	Reuse distance vs cache size boundary	$=1$	$d$ near $C$	Hit ↔ miss threshold
F	Bada block, lekin random / large stride	large	large	Block-size backfire
G	Degenerate: single access, empty loop	undefined	undefined	Edge / limiting case
H	Real-world word problem (image blur)	2-D	mixed	Applied synthesis
I	Exam twist: block size doubles	$=1$	fixed	Trade-off reasoning

---

Example 1 — Cell A: pure spatial locality

Forecast: Abhi guess karo — kya hit rate $50\%$ ke kareeb hai ya $90\%$ ke?

1. Block ko words mein convert karo. Block $B=64$ bytes, word $W=4$ bytes, isliye $b=64/4=16$ words per block. Yeh step kyun? Locality ek block ki granularity par rehti hai: ek miss poora block drag karta hai, isliye words mein count karna batata hai kitne free hits saath milte hain.
2. Total accesses count karo. $k=64$ words touch hue, har ek exactly ek baar (figure mein sweep dekho — har access par ek blue dot, right ki taraf badhta hua). Yeh step kyun? Humein hit rate ka denominator chahiye.
3. Sweep formula apply karo. $\text{misses}=\lceil 64/16\rceil =4$. Yeh step kyun? Har 16th access ek fresh block mein land karta hai (ek miss); baaki 15 pehle hi drag in ho chuke the.

4. Hit rate. $1-4/64=60/64=0.9375=93.75\%$.

Verify: $4$ blocks $\times 16$ words $=64$ words — exactly array ke barabar, na kam na zyada. Hit rate $15/16$ per block parent ke $1-W/B=1-4/64=15/16$ se match karta hai. ✓

---

Example 2 — Cell B: pure temporal locality

Forecast: Kya sum $1000$ misses cause karega, ya sirf $1$?

1. Reuse distance. Consecutive sum accesses ke beech, zero distinct other addresses aate hain. Isliye $d=0$. Yeh step kyun? $d=0$ strongest possible temporal locality hai — parent ka rule "$d<C\Rightarrow$ hit" kisi bhi cache ke liye satisfy hota hai jahan $C\ge 1$ ho.
2. Stride. $|A_{i+1}-A_i|=0$ (har baar same address). Yeh parent ka "stride $=0$ ⇒ pure temporal" cell hai. Yeh step kyun? Confirm karta hai ki koi spatial component nahi hai — yeh 100% temporal hai.
3. Miss count. Pehla access miss hoga (cold), baaki $999$ hit honge. Misses $=1$. Yeh step kyun? Ek block, ek baar load hone ke baad, kabhi evict nahi hota kyunki koi cheez uski slot ke liye compete nahi karti.

Verify: Hit rate $=999/1000=99.9\%$. Jaise accesses $\to \infty$, hit rate $\to 100\%$ — perfect temporal locality ka limiting behaviour. ✓

---

Example 3 — Cell C: dono localities ek saath

Forecast: $100$ misses se zyada ya kam?

1. Words per block. $b=64/4=16$ words. (Kyun: wahi granularity argument jaise Ex 1 mein.)
2. Spatial part — array. Stride $=4$ bytes $=1$ word ⇒ sequential. Misses $=\lceil 1000/16\rceil =63$. Yeh step kyun? $1000/16=62.5$, aur hum up round karte hain — woh aakhri half-block bhi ek poora miss maangta hai.
3. Temporal part — sum, i. Reuse distance $\approx 0$ (registers, koi eviction nahi) ⇒ $\approx 0$ misses. Yeh step kyun? Parent ka combo example: temporal hot scalars rakhta hai, spatial array stream karta hai.
4. Overall array hit rate. $1-63/1000=93.7\%$.

Verify: $\lceil 1000/16\rceil =63$; parent ke stated $93.7\%$ se exactly match karta hai. ✓

---

Example 4 — Cell D: spatial locality broken (column walk)

Forecast: Kya yahan hit rate $93\%$ ke kareeb hai (jaise Ex 3) ya $0\%$ ke kareeb?

1. Rows ke beech address gap. B[k][j] &B + (k·1000 + j)·4 bytes par rehta hai. k → k+1 step karne par $1000\times 4=4000$ bytes ka jump hota hai. Yeh step kyun? Stride yahan poora diagnostic hai — figure dekho: consecutive accesses (red arrows) poori rows ke across uchhalte hain.

2. Stride vs block. Stride $=4000$ bytes $\gg 64$-byte block. Har access ek alag block mein land karta hai. Yeh step kyun? Agar jump ek block se zyada ho, to jo neighbours hum fetch karte hain unhe reuse nahi kiya jaayega.
3. Fetched block ka utilisation. Drag in kiye gaye 16 ints mein se hum $1$ use karte hain: $1/16=6.25\%$. Yeh step kyun? "Wasted bandwidth" quantify karta hai — parent ka terrible-spatial-locality case.
4. Misses. Effectively har access par ek miss ⇒ $1000$ column reads ke liye $1000$ misses.

Verify: Utilisation $1/16=0.0625=6.25\%$, wasted $=93.75\%$ — Ex 1 ki hit rate ka mirror image. Fix ke liye Loop blocking and tiling dekho. ✓

---

Example 5 — Cell E: reuse-distance / cache-size threshold

Forecast: $d=7$ ya $d=8$ mein se kaun hit karega?

1. Rule yaad karo. Parent se: $d<C\Rightarrow$ hit, $d\ge C\Rightarrow$ miss (LRU cache). Yeh step kyun? Cell E ka poora point is inequality par exactly baiThna hai.
2. Case $d=7$. $7<8$ ⇒ hit. $7$ intervening blocks plus $X$ $=8$ blocks, sab fit ho jaate hain. Yeh step kyun? $X$ least-recently-used hai lekin abhi tak push out nahi hua.
3. Case $d=8$. $8\nless 8$ ⇒ miss. Aath other blocks aa gaye, saare 8 slots fill ho gaye aur $X$ evict ho gaya. Yeh step kyun? Razor edge dikhata hai: ek aur intervening block add karo aur hit miss mein flip ho jaata hai.

Verify: Boolean check: $(7<8)=\text{True}$ (hit), $(8<8)=\text{False}$ (miss). Threshold strict inequality hai. Working set model dekho. ✓

---

Example 6 — Cell F: bada block backfire karta hai

Forecast: Kaun sa block size poora working set hold karega?

1. Blocks jo fit honge — 16 B block. $32,768/16=2048$ slots. Working set $=500$ blocks $<2048$ ⇒ sab fit, near-zero capacity misses. Yeh step kyun? Temporal locality tab hi fayda deta hai jab reused blocks resident rahen.
2. Blocks jo fit honge — 256 B block. $32,768/256=128$ slots. Working set (500 items, har ek apne 256 B block mein kyunki access scattered hai) $>128$ ⇒ constant eviction. Yeh step kyun? Kam, mote blocks matlab kam distinct items resident — parent ki warning ko numeric banaya.
3. 256 B block ke saath wasted bytes. Har fetch 256 B drag karta hai lekin sirf 16 B chahiye: $16/256=6.25\%$ use hota hai. Yeh step kyun? Random access koi spatial payoff nahi deta lost temporal capacity ko offset karne ke liye.

Verify: $2048>500$ (16 B fit hota hai), $128<500$ (256 B thrash karta hai). Bada worse hai yahan. Cache organization fundamentals dekho. ✓

---

Example 7 — Cell G: degenerate / limiting inputs

Forecast: Kya $0$-iteration loop $0$ misses cause karega ya $1$?

1. (a) Empty loop. $k=0$ accesses ⇒ $\lceil 0/b\rceil =0$ misses. Hit rate undefined hai ($0/0$), $0\%$ nahi. Yeh step kyun? Total accesses zero — aapko kehna hoga "undefined", silently $0$ print nahi karna.
2. (b) Single access. $k=1$: $\lceil 1/16\rceil =1$ miss, hit rate $=1-1/1=0\%$. Reuse distance undefined (koi doosra access nahi). Yeh step kyun? Ek akela cold miss locality ka floor hai — abhi kuch exploit karne ko nahi.
3. (c) Exact multiple, $k=32,b=16$. $\lceil 32/16\rceil =2$ — koi rounding penalty nahi kyunki $32/16=2$ already integer hai. Yeh step kyun? Dikhata hai ki ceiling tab hi kaati hai jab remainder ho; yahan clean $2$ hai.

Verify: $\lceil 0/16\rceil =0$; $\lceil 1/16\rceil =1$; $\lceil 32/16\rceil =2$. Teeno edge values confirm hue. ✓

---

Example 8 — Cell H: real-world word problem (image blur)

Forecast: Centre row ki horizontal sweep ke liye locality acchi hai ya buri?

1. Row ke saath stride. j → j+1 move karne par $1$ byte step hota hai (chars contiguous hain). Stride $=1$ B $\ll 64$ B block. Yeh step kyun? Row ke andar horizontal moves row-major storage mein acchi direction hain.
2. Ek row ke liye misses. $k=1920$ bytes, $b=64$ bytes: $\lceil 1920/64\rceil =30$ misses. Yeh step kyun? $1920/64=30$ exactly — row sweep karne par 30 cold block loads lagte hain.
3. Neighbour rows. Upar aur neeche ki row $1920$ bytes door hai — alag block, lekin har ek khud sequential sweep hoti hai, isliye unhe bhi $30$ misses lagenge, phir reuse hoga. Yeh step kyun? Stencil ki teeno rows individually acchi tarah stream hoti hain; vertical gap ek baar pay hota hai, har pixel ke liye nahi.
4. Row hit rate. $1-30/1920=98.4\%$.

Verify: $\lceil 1920/64\rceil =30$; hit rate $1-30/1920=0.984375=98.4375\%$. Row-major + horizontal sweep = strong spatial locality. ✓

---

Example 9 — Cell I: exam twist (block double karo)

Forecast: Kya misses roughly half hokar ~$31$ ho jaate hain?

1. Nayi sweep misses. $b=32$: $\lceil 1000/32\rceil =32$ misses. Yeh step kyun? Bade $b$ ke saath sweep formula directly apply karo — spatial locality improve hoti hai.
2. Compare karo. $63\to 32$ misses, roughly half — is pure-sequential pattern ke liye acha hai. Yeh step kyun? Naive "bada block = kam misses" intuition confirm karta hai jab stride 1 ho.
3. Hidden cost. Fixed cache size ke liye, block double karne par blocks ki count half ho jaati hai (Ex 6 ka lesson) aur miss penalty double ho jaata hai (per transfer do gune bytes). Yeh step kyun? Exam trap: win aur dono costs report karo, warna aadhe marks hi milenge.

Verify: $\lceil 1000/32\rceil =32$ vs pehle $63$ — nearly half, exactly jaise claim kiya. ✓

---

Recall Quick self-test

Stride-0 access pattern mein kaun si locality hoti hai? ::: Pure temporal (same address repeatedly, reuse distance 0). LRU cache mein $C$ blocks ke saath reuse distance $d=C$ — hit ya miss? ::: Miss (rule hai $d<C$ strict). Bada cache block kyun hit rate lower kar sakta hai? ::: Kam blocks fit hote hain ⇒ worse temporal capacity, plus wasted bytes jab stride bada ho. $0$-iteration loop: kitne misses aur hit rate kya? ::: $0$ misses; hit rate undefined ($0/0$) hai, $0\%$ nahi.

Related deeper dives: Cache mapping strategies · Virtual memory · Working set model · Loop blocking and tiling.