Principle of locality (temporal - spatial)

5.4.1 · Hardware › Memory Hierarchy & Caches

Overview

Principle of locality ek fundamental observation hai ki programs kisi bhi given time pe apne address space ke relatively chhote hisse ko access karte hain. Yeh predictable access pattern hi poori wajah hai ki cache hierarchies kaam karti hain — locality ke bina, caching bilkul bekar hoti.

Agar programs memory ko randomly access karte, toh har access equally likely hoti. Lekin real programs mein structure hota hai, aur structure se predictability aati hai.

Do Tarah Ki Locality

Temporal Locality

Yeh kyun hota hai:

1. Loop counters: for(int i=0; i<n; i++) — variable i har iteration mein access hota hai
2. Function calls: Same function code kai baar execute hota hai
3. Frequently-used variables: Accumulators, status flags, pointers

Time scale: Human terms mein milliseconds se seconds, CPU terms mein thousands se millions of cycles.

$\text{Reuse Distance}=\text{count of unique addresses accessed between }{A}_i\text{ and }{A}_j$

jahan $A_i$ aur $A_j$ same address ke accesses hain.

Short reuse distance = strong temporal locality.

Derivation ki yeh caching ke liye kyun matter karta hai:

Maano ek cache $C$ blocks hold karta hai. Agar address $X$ ka reuse distance $d$ hai:

• Agar $d<C$: $X$ re-reference hote waqt cache mein hi hai → cache hit
• Agar $d\ge C$: $X$ evict ho gaya → cache miss

Temporal locality ke liye hit rate hai:

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

Isliye bade caches zyada temporal locality capture karte hain — wo longer reuse distances wale blocks hold kar sakte hain.

Spatial Locality

Yeh kyun hota hai:

1. Sequential instruction execution: Address 0x1000 par instruction ke baad 0x1004 aata hai
2. Array traversal: a[0], a[1], a[2], ... memory mein contiguous hote hain
3. Struct field access: Struct ke fields adjacent hote hain
4. Stack operations: Push/pop nearby stack addresses access karte hain

$\text{Stride}=|A_{i+1}-A_i|$

jahan $A_i$ $i$-va memory address hai jo access hua.

Stride = 1 word → perfect spatial locality (sequential access) Stride = 0 → pure temporal locality (same location) Large stride → poor spatial locality (idhar udhar jump karna)

Cache block benefit ki derivation:

Ek cache block $B$ bytes hold karta hai. Jab hum address $X$ fetch karte hain, toh hume $X,X+1,\dots ,X+(B-1)$ milta hai.

Agar program $X$ se start hoke $k$ consecutive addresses access karta hai (stride 1), toh hum ek miss dete hain lekin $k-1$ hits paate hain:

$\text{Hit rate from spatial locality}=\frac{k-1}{k}$

Jaise jaise $k\to B/W$ ($W$ word size hai), hit rate $\to 1-\frac{W}{B}$.

Example: 64-byte cache block, 16 consecutive words (4 bytes each) access karte hue:

• $k=16$ words, $B=64$ bytes = 16 words
• Hit rate = $\frac{15}{16}=93.75\%$

Isliye bade cache blocks spatial locality ko better exploit karte hain — lekin ek limit tak hi (agar stride bada hai, toh hum bekar data fetch karte hain).

Saath Kaam Karna: The Locality Combo

int sum = 0;                // sum in register
for (int i = 0; i < 1000; i++) {
    sum += array[i];
}

Temporal locality:

• Variable sum: 1000 baar access hota hai (padhna, uspe add karna, store karna)
• Variable i: 1000 baar access hota hai
• Loop instructions khud: 1000 baar execute hote hain

Spatial locality:

• array[0], array[1], array[2], ... memory mein contiguous hain
• array[0] fetch karne se array[1..15] cache block mein aa jaata hai (agar 64-byte blocks hain, 4-byte ints ke saath)
• Stride = 4 bytes (ek integer)

Har step kyun matter karta hai:

1. Pehli iteration: array[0] par cache miss, array[0..15] wala block load hota hai
2. Agle 15 iterations: array[1..15] par Cache hits — spatial locality kaam aati hai
3. 16vi iteration: array[16] par cache miss, array[16..31] load hota hai
4. Pattern repeat hota hai

Total misses = $\lceil 1000/16\rceil =63$ misses 1000 accesses ke liye → hit rate $=1-63/1000=$ 93.7% sirf spatial locality se.

Temporal locality add karo: sum, i, aur loop code cache mein (ya registers mein) rehta hai → un sab ka hit rate ~100% hota hai.

// Row-major storage: A[i][j] at memory address &A + (i*N + j)*sizeof(int)
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        for (int k = 0; k < N; k++) {
            C[i][j] += A[i][k] * B[k][j];
        }
    }
}

Access patterns:

• A[i][k]: Row $i$ ko sequentially access karta hai → good spatial locality (stride = 1 element)
• B[k][j]: Column $j$ access karta hai → stride = $N$ elements (rows ke across jump karta hai)
  • Agar $N=1000$, stride = 4000 bytes (4-byte ints maano)
  • Cache block 64 bytes ka hai → har block fetch mein sirf 1 element use hota hai
  • Terrible spatial locality: fetched data ka sirf 1/16 = 6.25% utilization

Yeh step itna bura kyun hai:

• Har B[k][j] access cache mein miss karta hai
• Hum 64 bytes fetch karte hain lekin sirf 4 bytes use karte hain
• Bandwidth waste hoti hai, performance gir jaati hai

Fix: Pehle $B$ ko transpose karo, ya blocking use karo (cache optimization mein cover hoga).

Locality Quantify Karna: The 90/10 Rule

Yeh physics ka law nahi hai — yeh real workloads mein ek statistical observation hai.

Kyun?

• Loops execution time dominate karte hain (inner loops millions of times execute hote hain)
• Hot functions baar baar call hote hain
• Cold code (error handlers, initialization) rarely run karta hai

Derivation:

Maano ek program $N$ instructions wala hai, jahan $f$ fraction "hot" hai (loops mein / frequently called).

Agar hot instructions average par $R$ baar execute hote hain, aur cold instructions ek baar:

$\text{Total execution time}=f\cdot N\cdot R\cdot T+(1-f)\cdot N\cdot T$

jahan $T$ time per instruction hai.

Hot code mein time ka fraction:

$\frac{f\cdot N\cdot R}{f\cdot N\cdot R+(1-f)\cdot N}=\frac{f\cdot R}{f\cdot R+(1-f)}$

90/10 rule ke liye: $f=0.1$, $R$ solve karo:

$0.9=\frac{0.1R}{0.1R+0.9}$ $0.09R+0.81=0.1R$ $R=81$

Toh agar 10% code average par ~81 baar execute hota hai, toh 90/10 rule milta hai.

Cache implication: Agar tum us 10% code aur uske data ko cache mein rakh sako, toh tumne 90% execution time optimize kar liya.

Common Mistakes & Misconceptions

Yeh galat kyun hai: Yeh toh temporal locality hai! Spatial ka matlab hai nearby addresses access karna (alag addresses, lekin address space mein close).

Steel-man: Confusion isliye hota hai kyunki dono cache performance improve karte hain, aur practice mein yeh aksar saath hote hain (jaise array pe loop karne mein dono hote hain). Lekin mechanisms alag hain:

• Temporal: Reuse ke liye same block ko cache mein rakho
• Spatial: Adjacent blocks prefetch karo kyunki wo jald chahiye honge

Fix: Etymology yaad rakho: "Temporal" = time (same address over time), "Spatial" = space (address space mein nearby).

Yeh galat kyun hai: Agar tumhara stride bada hai ya access pattern random hai, toh tum bekar data fetch karte ho. Bade blocks ka matlab yeh bhi hai:

• Fewer blocks cache mein fit hote hain (fixed cache size ke liye) → worse temporal locality
• Higher miss penalty (zyada bytes transfer karne padte hain)
• Conflict misses badhte hain (fewer blocks = zyada collisions)

Example:

• Cache size = 32 KB
• Block size = 16 bytes → 2048 blocks
• Block size = 256 bytes → 128 blocks

Agar tumhara working set 500 distinct blocks ka hai jo good temporal locality rakhte hain, toh 16-byte blocks jeetenge (sab 500 hold kar sakte hain), lekin 256-byte blocks sirf 128 hold kar sakte hain → bahut saari evictions.

Fix: Optimal block size stride distribution aur working set size par depend karta hai. Typical sweet spot: 32-128 bytes.

Locality Memory Hierarchy Ko Kyun Enable Karti Hai

Agar yeh bets pay off hoti hain, toh tumhe milta hai:

• Fast memory (cache) mein frequently used data hota hai
• Slow memory (DRAM) mein baaki sab hota hai
• Average access time cache speed ke paas pahunchta hai, DRAM speed ke nahi

Average access time ki derivation:

Maano $h$ = hit rate (accesses ka fraction jo cache mein hain), $T_c$ = cache access time, $T_m$ = DRAM access time.

$T_{\text{avg}}=h\cdot T_c+(1-h)\cdot (T_c+T_m)$

Dono terms kyun? Cache pehle check hota hai (hamesha $T_c$ pay karo), phir miss par $T_m$ bhi pay karna padta hai.

Simplify karo:

$T_{\text{avg}}=T_c+(1-h)\cdot T_m$

Example: $T_c=1$ ns, $T_m=100$ ns, $h=95\%$:

$T_{\text{avg}}=1+0.05\cdot 100=6\text{ ns}$

DRAM se ~17× faster (jisko $T_c+T_m=101$ ns per access chahiye) — yeh sab sirf isliye kyunki locality $h=0.95$ banati hai.

Agar locality nahi ($h=0$), $T_{\text{avg}}=101$ ns → cache bekar overhead hai.

Connections

• Cache organization fundamentals — caches locality ko blocks aur replacement policies ke zariye kaise exploit karti hain
• Cache mapping strategies — direct-mapped vs. set-associative, temporal vs. spatial conflicts ka trade-off
• Working set model — locality ko "recently used pages" ke roop mein formalize karna
• Loop blocking and tiling — locality improve karne ke liye compiler transformations
• Virtual memory — poore address space mein locality demand paging enable karti hai

Temporal locality: Tum baar baar same pencil use karte rehte ho. Har baar shelf tak jaane ki bajaye, tum use desk par hi chhod dete ho kyunki jaante ho 30 second baad phir chahiye hogi. Yahi temporal hai — "maine abhi yeh use kiya, shaayad jald phir use karunga."

Spatial locality: Jab tum shelf se math ki textbook uthate ho, saath mein math notebook bhi uthate ho kyunki wo usike paas hai, aur thodi der mein chahiye hogi. Yahi spatial hai — "agar mujhe yeh cheez chahiye, toh shaayad iske paas wali cheezein bhi chahiye hongi."

Cache bhi aise hi kaam karti hai. Computer haal hi mein use ki gayi cheezon ko paas rakhta hai (temporal) aur nearby cheezein saath mein uthata hai (spatial) kyunki programs aisa hi karte hain — wo random nahi hote, wo patterns follow karte hain jaise tum homework karte waqt karte ho.

Space → Spatial SPACE aur ADJACENCY ke baare mein hai (nearby addresses)

Simply: "Temporal = Time, Spatial = Space"

#flashcards/hardware

Concept Map