Principle of locality (temporal - spatial): Question bank

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

Yeh principle of locality ke liye ek thinking gym hai. Neeche har item mein ek common trap ya boundary case chupaaya gaya hai. Prompt padho, answer reveal karne se pehle out loud bolo, aur check karo ki tumhari reasoning — sirf verdict nahi — sahi hai ya nahi. Yahan sirf "true" ya "false" ka koi value nahi; why hi poori baat hai.

True or false — justify

Re-reading a variable inside a loop is temporal locality

True — wohi address thodi si time gap ke baad phir touch hota hai, jo exactly "recently used → soon reused" pattern hai.

Walking array[0], array[1], array[2] is temporal locality

False — yeh alag, nearby addresses hain, isliye yeh spatial locality hai; temporal ke liye wohi address dobara visit karna padta.

A program with zero locality could still benefit from a big cache

False — agar accesses truly uniform-random hain ek space par jo cache se kaafi bada hai, toh har access roughly equally likely hai evict hone ki, isliye cache bekar hai; locality hi cache ko faaydemand banati hai.

Spatial and temporal locality are mutually exclusive

False — zyaadatar real loops (jaise array sum) mein dono hoti hain: array elements spatial locality dete hain jabki loop counter, accumulator, aur instructions temporal locality dete hain.

Stride-1 access has strong spatial locality

True — agla har address ek word door hai, isliye woh usi cache block mein land karta hai jo already fetch ho chuka hai, ek miss ko kaafi hits mein badal deta hai.

Stride-0 access is spatial locality

False — stride 0 matlab tum usi address ko baar baar hit kar rahe ho, jo pure temporal locality hai; spatial ke liye nearby-but-different addresses par move karna zaroori hai.

Larger cache blocks always raise the hit rate

False — bade blocks tabhi help karte hain jab stride chota ho; bade ya random strides ke saath tum mostly useless bytes fetch karte ho, aur fixed cache size ke liye kam blocks hold hote hain, jo temporal locality ko hurt karta hai.

The 90/10 rule is a law of physics

False — yeh real workloads mein ek empirical statistical observation hai, jo isliye arise hota hai kyunki inner loops cold code se enormously zyaada execute hote hain, kisi fundamental principle se nahi.

Sequential instruction fetch is a source of spatial locality

True — address 0x1000 ke baad wala instruction usually 0x1004 hota hai, isliye ek block of instructions fetch karna kai upcoming fetches ko ek hi memory access se serve karta hai.

A cache miss on array[0] means array[1] will also miss

False — array[0] par miss poora block load karta hai jisme kai agle elements hain, isliye array[1..15] (64-byte blocks, 4-byte ints ke liye) phir hits hote hain spatial locality ki wajah se.

Spot the error

"Temporal locality means data stored close together in memory."

Error definitions ko swap kar raha hai: memory mein closeness spatial hai; temporal matlab time mein closeness hai (wohi address jald reuse hona).

"To exploit temporal locality, prefetch the next few blocks."

Adjacent blocks prefetch karna spatial locality exploit karta hai; temporal locality ko exploit kiya jaata hai reused block ko itna der resident rakh ke ki uska agla reference aa sake.

"Column access of a row-major matrix has good spatial locality because we still touch the array."

Array touch karna kaafi nahi — column access ka stride = N elements hota hai, isliye har fetched block sirf ek useful element deta hai aur baaki waste hota hai, yaani buri spatial locality hai.

"If reuse distance is 5 and the cache holds 5 blocks, the re-reference is guaranteed a hit."

Reuse distance

d = 5

aur capacity

C = 5

ke saath, hit ki condition hai

d < C

; yahan

d = C

hai, isliye block abhi-abhi evict hua ho sakta hai — yeh (potentially) miss hai, guaranteed hit nahi.

"Bigger blocks are strictly better because miss penalty doesn't change."

Bade blocks miss penalty badhate hain — har miss par zyaada bytes transfer karne padte hain — aur block count kam karte hain, isliye yeh doubly wrong hai.

"Since the 90/10 rule says 10% of code runs 90% of the time, that 10% runs 9× more often per instruction."

Multiplier 9 nahi hai; model solve karne par hot code average mein lagbhag 81 times execute karta hai, kyunki tumhe time split ke saath 10%/90% code-size split bhi account karna hota hai.

"Spatial locality helps only for data, not for instructions."

Instructions mein bhi strong spatial locality hoti hai — sequential execution consecutive addresses se guzarta hai, isliye instruction caches block fetch heavily exploit karti hain.

Why questions

Why does looping over an array give a ~93.7% hit rate even before any temporal reuse

Har 64-byte block mein 16 four-byte ints hote hain; ek miss block load karta hai aur agle 15 accesses hit hote hain, jo purely spatial locality se

15/16 = 93.75%

deta hai.

Why does transposing matrix

B

fix the matrix-multiply slowdown

Transpose karna B[k][j] ki strided column walk ko stride-1 row walk mein badal deta hai, isliye har fetched block poora use hota hai ek element ki jagah.

Why do larger caches capture more temporal locality

Bada cache zyaada blocks

C

hold karta hai, isliye longer reuse distances

d

wale addresses bhi

d < C

satisfy karte hain aur re-reference par resident rehte hain evict hone ki jagah.

Why can a large stride make big cache blocks actively harmful

Bade stride ke saath tum har fetched block ka sirf ek word use karte ho, isliye bada block har useful byte ke liye zyaada bandwidth waste karta hai aur doosre useful blocks ko junk ke liye evict karta hai.

Why is the loop counter i an example of temporal locality rather than spatial

i ek fixed address par rehta hai jo har iteration mein read aur write hota hai — wohi location samay ke saath reuse hoti hai — jo temporal ki definition hai, spatial ki nahi.

Why does the 90/10 rule matter for cache design

Agar sirf 10% code (aur uska data) 90% execution time capture karta hai, toh us hot fraction ko resident rakhna almost saare program ke running cost ko optimize karta hai.

Why do spatial and temporal locality "often occur together but by different mechanisms"

Yeh arrays par loops mein saath aate hain, phir bhi spatial adjacent blocks fetch karke serve hoti hai aur temporal usi block ko retain karke — ek ko improve karna automatically doosre ko improve nahi karta.

Edge cases

What is the locality of accessing a single hardware register in a tight loop

Pure temporal locality (stride 0) aur koi spatial locality nahi — wohi location baar baar hit hoti hai, lekin koi neighbouring address touch nahi hota.

What happens to the spatial hit rate as consecutive-access count

k

grows toward one block's worth of words

Spatial hit rate

(k - 1) / k

approach karta hai

1 - W / B

(word size over block size); yeh kabhi 100% nahi pahuncha kyunki har block ka pehla access hamesha compulsory miss hota hai.

If reuse distance equals cache capacity (

d = C

) exactly, hit or miss

Boundary case — hit ke liye strict condition hai

d < C

, isliye

d = C

par block typically evict ho chuka hota hai aur re-reference miss karta hai.

What is the locality of truly uniform-random memory access over a huge space

Effectively koi nahi — koi address doosre se zyaada likely nahi aur working set cache se zyaada hai, isliye caching negligible benefit deti hai aur hierarchy near main-memory speed par perform karti hai.

Does a block size equal to the whole cache make sense

Nahi — woh exactly ek block chhod deta hai, temporal locality destroy karta hai (koi bhi doosra working-set block pehle ko evict kar deta hai) aur miss penalty maximize karta hai; yeh sirf ek perfectly sequential stream ke liye "kaam" karta hai.

What locality does the return-address stack exhibit during many nested calls

Dono — pushes aur pops nearby stack addresses touch karte hain (spatial) aur wohi stack slots revisit hote hain jab frames unwind karte hain (temporal).

Recall Quick self-test

Spatial vs temporal in one line each ::: Spatial = nearby-but-different addresses jald; temporal = same address jald. Hit condition in terms of reuse distance and capacity ::: Hit jab reuse distance $d <$ cache capacity $C$ ; miss jab $d \geq C$ .