Principle of locality (temporal - spatial): Exercises

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

Yeh page ek self-test ladder hai. Har rung pichle se mushkil hai: L1 mein aap sirf idea ko pehchante ho, L5 tak aap us idea ke around design karte ho. Problem padhho, khud try karo, phir collapsible solution kholna.

Yahan sab kuch the parent locality note par build karta hai. Agar koi term shaky lage, to Cache organization fundamentals aur Cache mapping strategies notes mein prerequisites hain; Working set model aur Loop blocking and tiling last few exercises ko extend karte hain.

Shuru karne se pehle, kuch words jo hum baar baar use karenge:

Definition Cache block (line) aur word size

Cache ek byte fetch nahi karta — woh ek poora block of $B_{c}$ contiguous bytes ek saath fetch karta hai. Toh address $X$ par ek miss $X, X + 1, \dots, X + B_{c} - 1$ sab ko drag in kar leta hai. Yahi woh machinery hai jo spatial locality ko hits mein badalta hai. Hum block size ko $B_{c}$ likhte hain (subscript $c$ = "cache") taaki yeh Level 5 mein aane wali matrix $B$ se kabhi clash na kare. Block aur line dono ka matlab ek hi physical cheez hai; jab hum baad mein ek design problem mein iska size vary karte hain toh ise line size $B_{ℓ}$ kehte hain — same quantity as $B_{c}$ , bas rename kiya kyunki yeh woh variable ban jaata hai jise hum choose kar rahe hain. Hum word size $w$ bhi fix karte hain = ek element mein bytes ki sankhya jo hum access karte hain (ek int ke liye, $w = 4$ bytes). Toh ek block mein $B_{c} / w$ elements aate hain.

Definition Woh cache model jo hum is page par assume karte hain

Jab tak koi problem kuch aur na kahe, yahan har cache fully-associative with LRU (least-recently-used) replacement hai. Matlab: koi bhi block kisi bhi slot mein baith sakta hai, aur jab cache full ho jaaye toh least recently used block evict ho jaata hai. Yahi wajah hai ki yeh clean rule sach hai: "hit iff reuse distance $d <$ number of slots $C$ " — agar beech mein $C$ se kam aur blocks touch hue, to aapka wala kabhi shelf se nahi gira. Real caches usually set-associative hote hain (ek block sirf ek set of slots mein ja sakta hai), jisse conflict misses add hoti hain — do hot addresses jo same set mein map hote hain ek doosre ko evict kar dete hain chahe cache bilkul full na ho. Hum flag karte hain jahan yeh matter karta hai; parent Cache mapping strategies note ise fully develop karta hai.

Figure — Principle of locality (temporal - spatial)

Figure s01 — poore page ke liye aapka mental model: memory bytes ki ek lambi tape hai (top row, addresses rightward badhte hain); ek block woh orange fixed-width window hai $B_{c}$ contiguous bytes ka jo miss par ek saath fetch hota hai; neeche teal shelf cache hai, ek waqt mein sirf $C$ aisi windows rakhti hai. Yeh picture dhyan mein rakho — har exercise aslan "abhi shelf par kaunsa window hai?" hi hai.

Level 1 — Recognition

Goal: kya aap bata sakte ho kaunsi locality kaam kar rahi hai?

Exercise 1.1

Har access pattern ke liye, batao temporal, spatial, ya both:

(a) for(i=0;i<n;i++) s += a[i]; — variable s
(b) wahi loop — array elements a[i]
(c) while(1){ handle(); } — handle ke instructions
(d) memory mein scatter hue linked list mein p->next->next->next padhna

Recall Solution 1.1

(a) s ek address par baitha hai, har iteration mein touch hota hai → temporal. (b) a[0], a[1], … alag magar adjacent addresses hain → spatial. (Thoda temporal reuse bhi hai, lekin dominant effect spatial hai.) (c) handle ke instruction addresses har loop mein repeat hote hain → temporal. (Ek call ke andar woh sequence mein bhi chalte hain → spatial. Toh sach mein both, lekin loop temporal ko dominant banata hai.) (d) Har next ek naya, door-door address hai jisme na neighbour reuse hai na repeat → neither. Yeh classic locality-killer hai: pointer chasing.

Exercise 1.2

Ek cache mein $C = 8$ blocks aate hain. Address $X$ access hota hai, phir 5 distinct aur blocks access hote hain, phir $X$ dobara access hota hai. Doosre $X$ par hit ya miss?

Recall Solution 1.2

Reuse distance (upar define kiya) $d = 5$ hai ( $X$ ke do references ke beech touch hue distinct blocks). Hamare fully-associative LRU model ka rule: hit iff $d < C$ . Yahan $5 < 8$ , toh $X$ abhi bhi shelf par hai → hit. (Set-associative cache mein yeh phir bhi miss ho sakta tha agar woh 5 blocks $X$ ke set se collide karte — conflict miss — lekin full associativity se hum safe hain.)

Level 2 — Application

Goal: reuse-distance aur stride machinery mein numbers plug karo.

Exercise 2.1

64-byte block. int 4 bytes ka hai. Aap loop karte ho for(i=0;i<64;i++) sum += a[i]; stride 1 se. Kitne misses, kitne hits, aur hit rate kya hai (sirf spatial)?

Recall Solution 2.1

Upar define kiya word size $w = 4$ bytes use karte hue, ek block mein $B_{c} / w = 64/4 = 16$ ints aate hain. 64 ints order mein access karna:

a[0] access miss karta hai, a[0..15] pull in karta hai → agle 15 hits hain.
Pattern har 16 ints mein repeat hota hai. $misses = \frac{64}{16} = 4, hits = 64 - 4 = 60.$ $hit rate = \frac{60}{64} = 0.9375 = 93.75%.$ Yeh parent ke steady-state formula se match karta hai, jise hum ab yahan define kiye symbols se clearly likh sakte hain: stride-1 access ke liye miss rate $w / B_{c}$ hai (har $B_{c} / w$ elements ke block mein ek miss), toh hit rate hai $1 - \frac{w}{B _{c}} = 1 - \frac{4}{64} = \frac{15}{16} .$

Exercise 2.2

Same block, same array, lekin ab for(i=0;i<64;i+=8) — stride 8 ints = 32 bytes. 8 accessed elements mein se kitne misses?

Recall Solution 2.2

Aap a[0], a[8], a[16], …, a[56] access karte ho — yeh 8 elements hain. Bytes mein stride $= 8 \times 4 = 32$ . Block 64 bytes ka hai, toh do accessed elements ek block mein fit ho sakte hain:

Block containing a[0..15] mein a[0] aur a[8] hain → 1 miss + 1 hit.
Block containing a[16..31] mein a[16] aur a[24] hain → 1 miss + 1 hit.
… kul char blocks. $misses = 4, hits = 4, hit rate = 4/8 = 50%.$ Stride double karne se hamara spatial benefit roughly half ho gaya.

Exercise 2.3

Stride badh ke 16 ints = 64 bytes ho jaata hai, bilkul ek block ke barabar. 8 elements access ho rahe hain. Misses?

Recall Solution 2.3

Ab har accessed element ek fresh block mein padta hai (stride = block size). Koi bhi do ek block share nahi karte. $misses = 8, hit rate = 0%.$ Spatial locality bilkul khatam ho jaati hai jab stride block size tak pahunch jaata hai — har fetch 60 bekar bytes drag in karta hai.

Figure s02 — Exercises 2.1–2.3 ka pedagogical point ek image mein: ek 64-byte block 16 int-slots mein split hota hai. Teal slots woh hain jo stride-1 access actually touch karta hai (har block mein kaafi hits); plum slots dikhate hain stride-8 sirf 16 mein se 2 touch karta hai, toh baaki 14 bytes fetch-but-wasted hain. Figure L2 trap ko visible karta hai — hits un slots se aati hain jo aap touch karte ho, na un slots se jo exist karte hain.

Level 3 — Analysis

Goal: poore algorithm ki locality ke baare mein reason karo, including bad cases.

Exercise 3.1 — Row vs column traversal

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

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

Recall Solution 3.1

Row-major ka matlab M[i][j] address $base + (i \cdot N + j) \cdot 4$ par hai. Ek row ke along ( $j$ vary karta hai) addresses contiguous hain; ek column ke neeche ( $i$ vary karta hai) woh $N \cdot 4 = 4096$ bytes jump karte hain.

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

(b) Column by column — stride 4096 bytes. Stride ko directly block size se compare karo: stride $= 4096 B$ , block $= 64 B$ , aur $4096/64 = 64$ . Kyunki stride 64 poore blocks lambi hai, consecutive accesses kabhi ek block share nahi karte — successive $i$ ke liye har M[i][j] ek alag, freshly-fetched block mein padta hai, toh har access ek compulsory miss hai. Kya kisi earlier column ka block dobara aane par resident reh sakta hai? Nahi: same block ke do accesses ke beech (ek poora column apart), hum $N = 1024$ aur blocks touch karte hain, toh reuse distance $d = 1024$ hai. Koi bhi cache jo $1024$ blocks se chhota ho (jo, 64 B each par, 64 KB se chhota matlab hai) ka $d \geq C$ → evicted before reuse. Is page par assume kiye realistic caches ke liye, isliye: $miss rate = 100%.$

Same arithmetic, same data — miss rate mein 16× difference sirf traversal order ki wajah se.

Figure s03 — Exercise 3.1 ek chhoti row-major grid par draw kiya. Teal arrow ek row sweep karta hai: consecutive addresses, toh 16 elements ek block par ride in karte hain (6.25% miss). Plum arrow ek column walk karta hai: har step $N$ elements jump karke ek brand-new block par jaata hai (100% miss). Dono arrows mein identical arithmetic hai — figure dikhata hai ki sirf traversal order alag hai, jo L3 ka poora lesson hai.

Exercise 3.2 — Reuse distance decide karta hai

Ek cache mein $C = 100$ blocks aate hain. Do loops mein se har ek same address ko re-access karta hai, respectively $d_{1} = 60$ aur $d_{2} = 140$ distinct blocks touch karne ke baad. Kis loop ka reuse hit hai?

Recall Solution 3.2

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

Loop 1: $d_{1} = 60 < 100$ → hit (block bach gaya).
Loop 2: $d_{2} = 140 \geq 100$ → miss (reuse se pehle evict ho gaya). Loop 1 ki temporal locality is cache se captured hai; loop 2 ki nahi. Cache ko $C \geq 141$ blocks tak bada karne se loop 2 bach jaata — yahi wajah hai ki bade caches longer reuse distances capture karte hain.

Level 4 — Synthesis

Goal: locality ko cost model ke saath combine karo aur design decision lo.

Exercise 4.1 — Kya ek bada block worth it hai?

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.

Ek workload sequentially ek 4 KB region se ek baar stream karta hai (pure spatial, stride 1), phir strong temporal reuse ke saath 500 distinct 32-byte units ko randomly re-access karta hai. Temporal phase ke liye, count karo har configuration kitni 32-byte units actually hold kar sakti hai, phir decide karo kaunsa block size jeetta hai.

Recall Solution 4.1

Spatial part (streaming 4 KB once):

A: $4096/32 = 128$ misses.
B: $4096/256 = 16$ misses. Bada block streaming phase jeetta hai (kam misses, better spatial locality).

Temporal part — capacity arithmetic karo, assert mat karo. Cache 32 KB = 32768 bytes hai dono taraf. Iske total capacity ko 32-byte units mein convert karo: $units held = \frac{32768 B}{32 B/unit} = 1024 units, DONO options ke liye.$ Total bytes fixed hai, toh dono configurations physically hamare 32-byte working-set units mein se 1024 store karte hain. Kyunki working set sirf 500 units hai, A aur B dono saare 500 retain kar sakte hain — koi bhi temporal phase par thrash nahi karta. (Option B $128$ lines $\times 256/32 = 8$ units each $= 1024$ units rakhta hai; Option A $1024$ lines $\times 1$ unit $= 1024$ units rakhta hai. Same total.)

Toh temporal phase is idealised fully-associative cache par tie hai. Decision isliye spatial phase par turn karta hai, jahan Option B ke far kam misses the ( $16$ vs $128$ ).

Verdict: is idealised model par, Option B (256-byte blocks) jeetta hai — yeh A ki temporal capacity se match karta hai phir bhi streaming misses crush karta hai.

Real-world caveat (kyun "bigger is always better" phir bhi galat hai). Yeh tie sirf isliye hold karta hai kyunki humne full associativity assume ki aur exactly 500 units ka working set jis ka har ek kisi bhi free slot mein map hota. Do cheezein Option B ko real world mein tod deti hain:

Agar 500 units scattered hain (8-consecutive nahi), toh ek 256-byte line har fetch mein 7 tak bekar units drag in karta hai — 500 scattered units cover karne ke liye aapko 500 lines se kahin zyada bytes chahiye ho sakte hain, aur tab B sach mein lines se short ho jaata hai.
Real caches set-associative hote hain; bade lines ka matlab kam sets, toh zyada conflict misses. Upar ka clean tie big blocks ke liye best case hai; parent Cache mapping strategies aur neeche L4 trap dikhate hain kahan yeh collapse hota hai.

Exercise 4.2 — Scattered working-set units ke liye crossover derive karo

Ab maano 500 working-set units scattered hain — koi bhi do ek block share nahi karte. Tab har unit ko apni khud ki line chahiye, aur line size $B_{ℓ}$ (same quantity as block size $B_{c}$ — hum bas ise $B_{ℓ}$ rename karte hain kyunki yahan yeh woh variable hai jise hum choose kar rahe hain) waali config mein sirf $32768/ B_{ℓ}$ lines hoti hain. Sabse badi line size kya hai jo abhi bhi saari 500 scattered units hold kar sake?

Recall Solution 4.2

Chahiye (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) .$ Toh jab units scattered hoin, 64-byte line sweet spot hai: jitna ho sake spatially generous, phir bhi 500 distinct lines deta hai. 256-byte lines tak push karo aur aap $128$ lines $< 500$ tak gir jaate ho → ab Option B sach mein thrash karta hai. Yahi "bigger blocks temporal capacity ko spatial reach ke liye trade karte hain" trade-off hai — lekin sirf jab ek line ke andar locality poor ho.

Level 5 — Mastery

Goal: scratch se access pattern design karne ke level par reason karo.

(Yahan se aage, plain $B$ matrix $B$ ko denote karta hai multiply mein. Cache block size $B_{c}$ hi rehti hai, bilkul jaisi upar define ki — koi collision nahi.)

Exercise 5.1 — Matrix multiply ko blocking karna

Naive i,j,k multiply $B [k] [j]$ ko column se neeche read karta hai (stride $N$ , har access miss). Hum loops tile karte hain taaki har inner region ek $b \times b$ sub-block par kaam kare jo cache mein fit ho. Agar cache $C$ ints hold karta hai aur humein $A$ , $B$ , aur $C$ ke sub-blocks (teen $b \times b$ tiles) ek saath hold karne hain, toh sabse bada tile size $b$ kya hai? $C = 8192$ ints ke liye evaluate karo.

Recall Solution 5.1

Teen tiles of $b^{2}$ ints each ek saath hone chahiye: $3 b^{2} \leq C \Rightarrow b \leq C /3 .$ $C = 8192$ ke liye: $b \leq 8192/3 = 2730.67 \approx 52.3$ , toh $b = 52$ lo (ya practically alignment ke liye friendly power-of-two-ish $b = 32$ ).

Kyun kaam karta hai: ek baar matrix $B$ ka ek $b \times b$ tile load ho jaata hai, har element $b$ baar reuse hota hai eviction se pehle — humne terrible stride- $N$ column reads ko ek chhote resident tile par temporal locality mein convert kar diya. Yahi Loop blocking and tiling ka payoff hai.

Exercise 5.2 — Blocking ke baad reuse count

Upar ke tiled multiply mein, ek $B$ -tile ka har loaded element cache se jaane se pehle kitni baar reuse hota hai, aur yeh matrix $B$ ki effective miss rate par kya karta hai naive $100%$ ke comparison mein?

Recall Solution 5.2

Ek $b \times b$ $B$ -tile ka har element $b \times b$ $C$ -tile ke poore column-strip ko update karne mein participate karta hai → yeh har tile pass mein $b$ baar use hota hai. Toh ek miss ab $b$ useful accesses serve karta hai: $matrix B ke liye miss rate \approx \frac{1}{b} .$ $b = 52$ ke liye: miss rate $\approx 1/52 \approx 1.92%$ , versus $100%$ naive — $B$ par misses mein ~52× reduction. Yahi haath se engineer ki gayi locality hai.

Exercise 5.3 — Working set aur virtual memory

Ek program ka working set (ek time window mein touch hue distinct pages) 200 pages hai. Physical memory usse 150 page frames deti hai. Behaviour predict karo aur locality se connect karo.

Recall Solution 5.3

Working set $= 200 >$ frames $= 150$ . Program apne actively-used pages resident nahi rakh sakta → har window mein woh un pages ko evict karta hai jo dobara chahiye honge → thrashing (constant page faults, disk-latency stalls). Yeh page granularity par reuse-distance argument hai: jab Working set model size capacity se zyada ho jaaye, temporal locality capture nahi ho sakti, bilkul jaisi $d \geq C$ ne cache misses cause kiye. Paging mechanism ke liye Virtual memory dekho. Fix: usse $\geq 200$ frames do, ya code restructure karo (tiling!) taaki working set 150 se neeche aa jaaye.

Recall Quick self-check (cloze)

Reuse distance $d$ hits (fully-assoc LRU) jab ::: $d < C$ (cache $C$ blocks hold karta hai). Spatial locality khatam hoti hai jab stride pahunch jaata hai ::: block size $B_{c}$ tak. 3 resident $b \times b$ tiles ke saath sabse bada tile ::: $b \leq C /3$ . Blocking matrix $B$ ki miss rate 100% se cut karke karta hai ::: approximately $1/ b$ . Real caches LRU model se pare kaunsa extra miss type add karte hain? ::: conflict misses (set-associativity ki wajah se).