Principle of locality (temporal - spatial): Visual walkthrough

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

Yeh page ek hi result zero se build karta hai: ek program jo memory reuse karta hai aur use order mein padhta hai, usse itne zyada cache hits kyun milte hain? Hum har symbol ko ek picture ke saath earn karenge, phir unhe ek single formula mein combine karenge. Agar aapne pehle kabhi cache nahi dekha, toh yahan se shuru karein — hum ise Step 1 mein define karte hain.

Parent: Principle of locality (temporal - spatial). Related: Cache organization fundamentals, Cache mapping strategies, Working set model, Loop blocking and tiling.

Step 1 — Cache actually hai kya (the drawer picture)

KYA HAI. Main memory bahut badi aur slow hai. Ek cache uski ek choti, fast copy hai, CPU ke paas rakhi hoti hai. Memory ko ek giant warehouse of numbered boxes socho, aur cache ko ek choti desk jo ek waqt mein sirf kuch hi boxes hold kar sakti hai.

KYUN. Neeche har symbol is desk ko refer karta hai. "Hits" aur "misses" ki baat karne se pehle hume fix karna hai ki desk mein kya hota hai. Hum har box ko ek block kehte hain (ek fixed chunk of bytes jo saath fetch hote hain), aur kehte hain ki desk $C$ blocks hold karti hai.

PICTURE. Daayein taraf ki red desk sirf $C = 4$ blocks hold karti hai. Baayein taraf ka black warehouse hazaaron blocks rakhta hai.

Cache capacity

C

= blocks ki woh number jo desk ek saath hold kar sakti hai.

Step 2 — Access stream (ek program ko ek list mein convert karna)

KYA HAI. Ek running program, memory ke point of view se, sirf ek list of addresses hai jo woh order mein maangta hai. $i$ -th address ko $A_{i}$ kehte hain.

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

$A_{i}$ :: $i$ -th step par request kiya gaya address — timeline par ek dot.
Subscript $i$ :: clock tick hai, address khud nahi. Do alag ticks ek hi address maang sakte hain.

KYUN. Hum "loops" ya "arrays" ke baare mein directly reason nahi kar sakte — woh bahut varied hain. Lekin har program is stream mein collapse ho jaata hai, toh agar hum streams ke baare mein kuch prove kar dein toh hum sab programs ke baare mein prove kar dete hain. Yahi woh trick hai jo poori theory ko possible banati hai.

PICTURE. Time left se right chalta hai; har mark ek access hai. Neeche red marks do accesses hain usi address par — woh repeat temporal locality ka seed hai.

Step 3 — Temporal locality: the reuse-distance ruler

KYA HAI. Ek address lo jo do baar appear hota hai, ticks $i$ aur $j$ par (jahan $i < j$ ). Count karo ki strictly unke beech mein kitne distinct addresses touch kiye gaye. Woh count hai reuse distance $d$ .

$d = {distinct addresses in A_{i + 1}, \dots, A_{j - 1}}$

Bars $∣ {\dots} ∣$ :: "is set mein kitne items hain" — ek plain count.
distinct :: hum har alag address ek baar count karte hain, chahe woh repeat hua ho. Yahi desk ko fill karta hai.
Chhota $d$ :: repeat jaldi wapas aaya → strong temporal locality.

Distinct kyun count karein, total nahi? Kyunki desk variety se evict hoti hai, volume se nahi. Agar apne do visits ke beech mein aapne same 3 addresses 100 baar touch kiye, toh sirf 3 desk-slots use hue. Jo cheez aapke block ko desk se kick karti hai woh 3 nayi cheezein hain, 300 repeats nahi.

PICTURE. Red span reuse distance hai — Step 2 ke do red marks ke beech ka ruler, jo distinct black marks count karta hai.

Step 4 — Hit/miss cut: $d$ ko $C$ se compare karna

KYA HAI. Yahan poore page ka hinge hai. Ek fully-associative LRU desk mein (hamara upar waala assumption), aapka block tab hi bachta hai jab aapki gairamoujoodgi mein $C$ se kam distinct doosre blocks aaye hon. Toh, ek re-access ke liye (pehla reference nahi):

re-access is a {hit miss if d < C if d \geq C

$d < C$ :: desk-slots se kam newcomers → aapka block kabhi push off nahi hua → hit.
$d \geq C$ :: kam se kam $C$ newcomers → unhone har slot fill kar diya aur aapko evict kar diya → miss.

Yeh exact comparison kyun? Kyunki $C$ slots ki ek desk maximum $C$ blocks hold kar sakti hai, aur LRU sirf oldest-used ko throw out karta hai. Agar $C$ ya zyada different blocks aapki gairamoujoodgi mein aaye, toh unmen se ek aapka slot le leta hai. " $C$ " literally woh cheezein hain jinke saath aap survive kar sakte ho.

PICTURE. Ek hi stream ke upar do reuse arcs: chhota red arc ( $d < C$ ) hit par land karta hai; lamba grey arc ( $d \geq C$ ) miss par land karta hai kyunki beech mein bahut saare distinct blocks ne desk fill kar di.

Step 5 — Cut ko hit rate mein convert karna

KYA HAI. Har access exactly teen mein se ek cheez hai: compulsory miss (first-ever reference, Step 3), capacity/temporal hit ( $d < C$ ), ya capacity miss ( $d \geq C$ ). Inhe group karo:

$total = d < C hits H + d \geq C M_{cap} + first refs M_{cold}$

$H$ :: re-accesses ki number jinhone hit kiya.
$M_{cap}$ :: re-accesses jo miss hue kyunki desk bahut chhoti thi.
$M_{cold}$ :: pehle references, jo zaroor miss honge chahe desk kitni bhi badi ho.

Isliye exact hit rate hai

$P (hit) = \frac{H}{H + M _{cap} + M _{cold}} .$

Pehle wale version mein " $\approx$ " kyun tha. Log aksar quote karte hain

$P (hit) \approx \frac{# { accesses with d < C }}{total accesses},$

jo cold misses ko total mein chup ke lump kar deta hai lekin numerator mein nahi, aur (real cache mein) conflict misses ko bhi ignore karta hai. Isliye yeh sirf ek approximation hai: yeh ek lower-bound sketch hai jo fully-associative LRU cache ke liye exact ban jaati hai jab aap compulsory misses subtract kar dein, kyunki phir reuse-only stream mein $M_{cold} = 0$ hota hai.

$# {\dots}$ :: "un accesses ki number jinke liye condition hold karti hai".
woh fraction :: $0$ aur $1$ ke beech ek probability; use $100$ se multiply karo toh percent ( $%$ ) mein padho.

Fraction kyun at all? Ek hardware designer ek access fix nahi kar sakta; woh typical one ke liye design karta hai. Fraction woh chance hai ki ek random access hit kare — woh number jo decide karta hai ki ek program fast feel karta hai ya slow.

PICTURE. Sab accesses ki ek tall bar teen bands mein split: red band ( $d < C$ hits), grey capacity-miss band, aur ek patli cold-miss band jo koi bhi cache remove nahi kar sakta.

Step 6 — Spatial locality: ek miss kai hits ke liye pay karta hai

KYA HAI. Abhi tak ek block ek address tha. Lekin ek real block $B$ bytes hold karta hai. Memory words ke fixed chunks mein addressed hoti hai; $W$ ko bytes per word hone do (e.g. $W = 4$ ek 32-bit integer ke liye). Isliye ek block hold karta hai

$k = \frac{B}{W} words,$

$B$ :: bytes per block — ek desk-slot ki chaurai.
$W$ :: bytes per word — ek element ka size jo program actually padhta hai.
$k = B / W$ :: ek block mein kitne words hain. $B = 64, W = 4$ ke liye: $k = 16$ .

Jab aap address $X$ par miss karte ho, desk saari block $X, X + W, \dots, X + (k - 1) W$ ussi trip mein free mein utha leti hai. Agar aapke agle accesses neighbours hain — ek word ka stride — woh already wahan hain.

$stride = ∣ A_{i + 1} - A_{i} ∣, stride = W \Rightarrow sequential$

stride :: consecutive addresses ke beech ka jump. Ek word = paas wale ghar jaana; bada = sheher ke paar teleport karna.

Yeh hits free mein kyun deta hai? Kyunki memory trip ka slow part trip khud hai, aap kya laate ho uska size nahi. $k$ neighbours laana almost utna hi cost karta hai jitna $1$ laana, toh memory system sab laata hai aur bet lagaata hai ki aap unhe chaahoge.

PICTURE. Ek red miss poori block fetch karta hai ( $k = 16$ words dikhaye); agle $k - 1 = 15$ sequential accesses usके andar hits ki tarah land karte hain.

Spatial hit rate. Agar aap fetched block ke sab $k$ words sequentially touch karo:

$P (hit)_{spatial} = \frac{k - 1}{k}$

$k - 1$ :: neighbours jo already desk par hain (hits).
$k$ :: run mein total accesses (ek miss $+$ $k - 1$ hits).

$\frac{k - 1}{k}$ se $1 - \frac{W}{B}$ tak — woh missing algebra. Fraction split karo:

$\frac{k - 1}{k} = \frac{k}{k} - \frac{1}{k} = 1 - \frac{1}{k} .$

Ab $k = B / W$ substitute karo, toh $\frac{1}{k} = \frac{1}{B / W} = \frac{W}{B}$ . Isliye

$P (hit)_{spatial} = 1 - \frac{1}{k} = 1 - \frac{W}{B} .$

Isliye single-word share $\frac{1}{k}$ equals $\frac{W}{B}$ : $k$ mein se ek word woh ek word ( $W$ bytes) hai jo poori block ( $B$ bytes) mein se ek hai. Worked numbers: $B = 64, W = 4 \Rightarrow k = 16$ , toh $1 - \frac{W}{B} = 1 - \frac{4}{64} = \frac{15}{16} = 0.9375 = 93.75%.$

Step 7 — Degenerate cases (har ek ke liye ek figure, reader ko koi unseen scenario nahi hit karna chahiye)

Teen corners jahan upar wale formulas bend karte hain. Har ek ko apni picture milti hai.

Ek-picture summary

Upar sab kuch ek single chain hai: ek program stream banta hai (Step 2); ek pehla reference hamesha cold miss hota hai (Step 3); reuse distance $d$ se measured repeats hit karte hain jab $d < C$ ho fully-associative LRU cache mein (Step 4); stride se measured neighbours free mein saath aa jaate hain jab stride ek word ho (Step 6); hits ko teeno miss types ke against count karne se $P (hit)$ milta hai (Step 5); aur corners (Step 7) dikhate hain kahan har mechanism khatam hoti hai.

Recall Feynman retelling — aise bolein jaise kisi dost ko explain kar rahe ho

Apni chair ke paas ek choti desk aur hall mein ek bada warehouse imagine karo. Warehouse se kaam karna slow hai, toh jo boxes use kar rahe ho unhe desk par rakhte ho. Ek program sirf "fetch box #…" requests ki list hai. Pehli baar jab bhi aap kisi box ko maangten ho, woh already desk par nahi ho sakta — yeh cold miss hai, inevitable. Temporal locality kehti hai: aap probably jaldi woh box phir maangoge — aur ek desk mein jahan koi bhi box kahi bhi baith sakta hai aur jo box sabse pehle use hua woh throw out hota hai, jab tak aapki gairamoujoodgi mein aapke desk ke size ( $C$ ) se kam different boxes aaye hon, aapka wahan hai: hit. (Agar desk har box ko ek fixed spot par force kare, toh do boxes us spot ke liye ladte hue ek doosre ko knock off kar sakte hain even jab count kehta hai nahi karna chahiye — yeh conflict miss hai.) Spatial locality kehti hai: boxes $k = B / W$ words ke bundles mein ship hote hain, toh ek grab karne se uske neighbours free mein mil jaate hain — aur kyunki programs order mein padhte hain, woh neighbours aage kya chaahiye wahi hain, jisse har miss par $\frac{k - 1}{k} = 1 - \frac{W}{B}$ hits milte hain. Dono ek hi tarah break karte hain: bahut choti desk, ya door boxes par teleport karna (bada stride). Yahi poori theory hai ki caches kyun kaam karte hain.

Which condition makes a temporal re-access a hit, and under what cache assumption?

d < C

, assuming a fully-associative cache with LRU replacement; direct-mapped/set-associative designs conflict misses add karte hain.

Why count distinct addresses for reuse distance?

Sirf distinct blocks desk slots consume karte hain aur eviction cause karte hain; repeats cache fill nahi karte.

How is the block word-count

k

related to

B

and

W

k = B / W

(bytes per block divided by bytes per word).

Why does

\frac{1}{k}

equal

\frac{W}{B}

in the spatial formula?

Kyunki

k = B / W

, toh

1/ k = W / B

— ek word of

W

bytes out of ek block of

B

bytes.

What is a compulsory (cold) miss aur bada cache use kyun remove nahi kar sakta?

Kisi block ka first-ever reference; woh pehle kabhi fetch nahi hua, toh koi bhi cache size use hold nahi kar sakti thi.

When does a large block hurt?

Yeh fixed cache size ke liye block count reduce karta hai, effective capacity shrink karta hai aur temporal locality weaken karta hai, aur conflict pressure badhata hai.