Cache organization (direct-mapped): Worked examples

5.4.2 · D3 · Hardware › Memory Hierarchy & Caches › Cache organization (direct-mapped)

Tumne parking-garage wali picture pehle hi dekhi hai Cache organization (direct-mapped) mein: har memory address ke liye ek hi cache line hoti hai jahan woh reh sakta hai. Yeh page woh boring-but-essential kaam karta hai: hum woh ek rule lete hain aur use har tarah ke input se uthate hain jab tak exam mein kuch bhi surprise na kare.

Shuru karne se pehle, teen words jo hum baar baar use karenge, har ek address se hi nikla hua.

Address ko slice hote dekho:

Figure — Cache organization (direct-mapped)

Agar koi word yahan shaky lag raha hai, toh parent note har field ko scratch se derive karta hai; aur Memory Addressing explain karta hai ki addresses ko bytes mein kyun count kiya jaata hai.

Scenario matrix

Direct-mapped cache chhota hota hai, isliye qualitatively alag cheezein jo ho sakti hain ki list finite hai. Yeh rahi — neeche har worked example us cell(s) ke saath tagged hai jise woh cover karta hai.

Cell	Kya ise alag banata hai	Covered by
A. Cold access	Pehli baar touch, valid bit = 0	Ex 1
B. Hit	Line valid hai, tag match karta hai	Ex 1, Ex 2
C. Same block, different offset	Do addresses, same index+tag, alag byte	Ex 2
D. Conflict miss / thrash	Same index, alag tag, alternating	Ex 3
E. Degenerate: block size = 1	$b = 0$ , offset field bilkul nahi	Ex 4
F. Degenerate: one line	$c = 0$ , sab kuch line 0 pe map hota hai	Ex 4
G. Boundary: block-crossing access	Ek read jo do blocks mein span kare	Ex 5
H. Wrap-around of index	Block $2^{c}$ wapas line 0 pe aa jaata hai	Ex 6
I. Parameter derivation	Given sizes → $b, c, tag$ nikalo	Ex 7
J. Real-world word problem	Array pe loop, misses count karo	Ex 8
K. Exam twist	Ek parameter badlo, effect predict karo	Ex 9

Examples 1–3 aur 5–6 ke liye hum same tiny cache rakhte hain taaki numbers familiar rahein.

Worked examples

Example 1 — Cold access, phir ek hit (cells A, B)

Worked example Address

0x2D access karo, do baar Setup: reference cache, sare valid bits 0 se start hain (cache empty hai).

Forecast: abhi guess karo — kya pehla access hit hai ya miss? Kya doosra? Kyun?

Address ko binary mein likho. $0x2D = 0010110 1_{2}$ . Yeh step kyun? Har field seedha bits se padhi jaati hai; hum decimal ko slice nahi kar sakte.
TTTT | II | OO slice karo: tag $= 001 0_{2} = 2$ , index $= 1 1_{2} = 3$ , offset $= 0 1_{2} = 1$ . Yeh step kyun? Index akela hume woh ek line batata hai — koi searching nahi.
Line 3 pe jao, uska valid bit padho. Woh 0 hai (empty cache). Yeh step kyun? Garbage pe tag comparison ka koi matlab nahi; valid bit gate hai.
Valid = 0 ⇒ MISS (ek cold/compulsory miss). 4-byte block fetch karo, data store karo, tag $= 0010$ set karo, valid $= 1$ karo. Yeh step kyun? Yahan kabhi kuch load nahi hua, isliye koi eviction nahi chahiye — yeh explain karne ke liye sabse sasta miss hai.
0x2D ka doosra access: same index 3, valid ab $= 1$ hai, stored tag $0010$ = address tag $0010$ . HIT. Block ka byte 1 return karo (offset $= 1$ ). Yeh step kyun? Dikhata hai ki hit condition $Valid = 1 \land Tag_{cache} = Tag_{addr}$ actually fire kar rahi hai.

Verify karo: index (block address) mod 4 ke barabar hona chahiye. Block address $= ⌊ 0 x 2 D /4 ⌋ = ⌊ 45/4 ⌋ = 11$ ; $11 mod 4 = 3$ . ✓ Offset $= 45 mod 4 = 1$ . ✓

Example 2 — Same block, different offset (cells B, C)

Worked example

0x2D, 0x2E, 0x2F row mein access karo (Ex 1 ke block load karne ke baad) Forecast: in teen mein se kitne misses hain?

Binary: 0x2D $= 00101101$ , 0x2E $= 00101110$ , 0x2F $= 00101111$ . Kyun? Hume dekhna hai ki kaunse fields alag hain.
Fields compare karo: tag $= 0010$ teeno ke liye, index $= 11$ teeno ke liye. Sirf offset badlta hai ( $01, 10, 11$ ). Kyun? Cache hit/miss sirf tag+index pe depend karta hai. Offset kabhi decision affect nahi karta.
Teeno HIT hain — same valid line, same tag — bytes 1, 2, 3 return karta hai ek cached block ke. Kyun? Yeh spatial locality ka fayda hai: ek fetch, teen saste reads. Cache Performance Metrics dekho ki yeh hit rate kaise badhata hai.

Verify karo: block addresses $⌊ 45/4 ⌋ = ⌊ 46/4 ⌋ = ⌊ 47/4 ⌋ = 11$ , sab identical ⇒ same block ⇒ Ex 1 ke baad sab hits. ✓

Example 3 — Conflict miss aur thrashing (cell D)

Worked example

0x0D aur 0x4D ko hamesha ke liye alternate karo Forecast: woh alag addresses hain — lekin kya woh alag lines pe land karte hain? Alternating stream ki hit rate kya hai?

Binary: 0x0D $= 00001101$ , 0x4D $= 01001101$ . Kyun? Tag aur index padhne ke liye.
Fields: dono ka index $= 1 1_{2} = 3$ hai. Tags alag hain: $0000$ vs $0100$ . Kyun? Same index = same line (dono ko spot 3 share karna padega). Alag tag = alag block. Yahi conflict ka exact recipe hai.
Stream trace karo line 3 pe:
- 0x0D: empty → MISS, tag $0000$ store karo.
- 0x4D: line mein tag $0000$ hai, $0100$ chahiye → mismatch → MISS, evict karo, $0100$ store karo.
- 0x0D: line mein $0100$ hai, $0000$ chahiye → MISS, phir evict karo… Kyun? Har access us block ko evict karta hai jo agla access chahega — yahi thrashing ki definition hai.
Har access miss hai jabki cache mein 3 aur empty lines hain. Kyun? Direct-mapping un lines ko use karne se mana karta hai; yahi woh weakness hai jo Set-Associative Caches fix karta hai har index ko ek se zyada ghar dekar.

Verify karo: dono ka index $= (⌊ 13/4 ⌋ mod 4)$ aur $(⌊ 77/4 ⌋ mod 4)$ . $⌊ 13/4 ⌋ = 3, 3 mod 4 = 3$ ; $⌊ 77/4 ⌋ = 19, 19 mod 4 = 3$ . Same index. Tags $⌊ 13/16 ⌋ = 0 \neq = ⌊ 77/16 ⌋ = 4$ . Conflict confirmed. ✓

Example 4 — Do degenerate caches (cells E, F)

Worked example Kya hota hai jab ek field

gayab ho jaata hai? Forecast: kya $b = 0$ ho sakta hai? Kya $c = 0$ ? Address split tab kaisa dikhega?

Case E — block size = 1 byte ( $b = 0$ ).

Offset field $0$ bits wide hai → koi offset nahi. Har address apna block hai. Kyun? $2^{0} = 1$ byte per block; sirf ek byte hai, andar index karne ke liye kuch nahi.
Hamare $m = 8$ , $c = 2$ ke saath: split ban jaata hai TTTTTT | II (tag $= 6$ bits, index $= 2$ ). Kyun? Bits conserved rehte hain: $8 = 6 + 2 + 0$ .
Consequence: zero spatial locality — ek byte fetch karna neighbors ko pre-load nahi karta. Word problems jo array pe loop karte hain (Ex 8) yahan kaafi worse ho jaate hain.

Case F — ek cache line ( $c = 0$ ).

Index field $0$ bits wide hai → har block line 0 pe map karta hai. Kyun? $2^{0} = 1$ line; kisi bhi cheez ka modulo-1 0 hota hai.
Split ( $b = 2$ rakhte hue): TTTTTT | OO.
Consequence: alag tags wale koi bhi do blocks collide karte hain — yeh Ex 3 ki thrashing maximum tak badh gayi. Ek line wala "cache" basically ek single-block buffer hai.

Verify karo: bit budgets. Case E: $6 + 2 + 0 = 8 = m$ . ✓ Case F: $6 + 0 + 2 = 8 = m$ . ✓ Case F ke liye, har address ka index $= blockaddr mod 1 = 0$ . ✓

Example 5 — Block-crossing access (cell G)

Worked example

0x1F se shuru hoke ek 4-byte word padho Setup: reference cache (4-byte blocks). Ek 4-byte read bytes 0x1F, 0x20, 0x21, 0x22 chahta hai.

Forecast: yeh 4 bytes — kya sab ek hi cache block mein rehte hain?

Har byte kaun se block mein hai? Block address = byte address $\div 4$ (floor). 0x1F $= 31 \to ⌊ 31/4 ⌋ = 7$ ; 0x20 $= 32 \to 8$ ; 0x21,0x22 $\to 8$ . Kyun? Ek block boundary har 4 bytes pe hoti hai; hume dhundhna hai ki hamari read kahan straddle karti hai.
Do alag blocks (7 aur 8) ⇒ do cache lookups. Byte 31 block 7 se aata hai; bytes 32–34 block 8 se. Kyun? Offset field 4 pe wrap karta hai; address 0x20 ka offset $00$ hai, matlab "ek nayi block ka shuru."
Har block ka index: $7 mod 4 = 3$ , $8 mod 4 = 0$ . Alag lines — yeh particular crossing self-conflict bhi nahi karta. Kyun? Dikhata hai ki crossing ek two-access event hai, hardware do block fetches ki tarah handle karta hai.

Verify karo: offsets $31 mod 4 = 3$ (apne block ka aakhri byte) aur $32 mod 4 = 0$ (agale ka pehla). ✓ Indices $7 mod 4 = 3$ , $8 mod 4 = 0$ . ✓

Example 6 — Index wrap-around (cell H)

Example 7 — Parameter derivation (cell I)

Example 8 — Real-world word problem (cell J)

Worked example 64-int array ka sum karo (har int = 4 bytes) reference cache mein

Setup: 64 ints ka array, address 0x00 se contiguously laid out. Reference cache: 4-byte blocks, 4 lines. Ek int exactly ek block mein fit hota hai. Hum har element ek baar order mein padhte hain.

Forecast: 64 reads ke saath, kitne misses hain? Compute karne se pehle ek number guess karo.

Block mein kitne bytes, kitne ints? Block $= 4$ bytes $= 1$ int. Toh har int apna block hai — yahan koi spatial locality benefit nahi. Kyun? Block size element size ke barabar hai, streaming ke liye worst case.
Miss pattern: har naye block ka pehla touch compulsory MISS hai. Kyunki har int ek naya block hai aur hum kabhi wapas nahi aate, sare 64 accesses compulsory misses hain. Kyun? Sequential, single-pass, koi reuse nahi ⇒ conflicts aur capacity irrelevant hain; sirf cold misses hote hain.
Miss rate $= 64/64 = 100%$ . Hit rate $= 0%$ . Kyun? Highlight karta hai ki streaming performance mein line count nahi, block size drive karta hai.
Fix: 16-byte blocks use karo (4 ints each). Tab sirf har 4th access miss karta hai ⇒ 16 misses ⇒ hit rate $= 48/64 = 75%$ . Kyun? Bade blocks ek fetch ko 4 uses pe amortise karte hain — spatial locality, quantified.

Verify karo: 4-byte block: misses $= 64$ , hit rate $0$ . 16-byte block: misses $= 64/4 = 16$ , hits $= 48$ , hit rate $48/64 = 0.75$ . ✓

Example 9 — Exam twist: ek knob badlo (cell K)

Worked example "Block size double karo lekin total cache size fixed rakho. Index bits aur tag ka kya hoga?"

Setup: Ex 7 se shuru karo (32-bit addr, 64 KB, 32-byte blocks → $b = 5, c = 11, tag = 16$ ). Ab block size $\to 64$ bytes, cache size 64 KB rehti hai.

Forecast: kya tag badhega, ghategaa, ya same rahega?

Naye offset bits: $64 = 2^{6}$ ⇒ $b = 6$ (tha 5). 1 offset bit gain hua. Kyun? Bada block = andar zyada bytes address karne padte hain.
Nayi line count: $64 KB /64 B = 1024 = 2^{10}$ ⇒ $c = 10$ (tha 11). 1 index bit gaya. Kyun? Same total size, mote blocks ⇒ kam blocks ⇒ kam lines.
Naya tag: $32 - 10 - 6 = 16$ . Unchanged! Kyun? Offset ne ek bit chura li aur index ne ek wapas de di; tag leftover hai aur net zero hai. Yahi woh trap hai jo exam test kar raha hai — students expect karte hain ki tag move karega.
Performance side-effect: kam lines ⇒ zyada potential conflict misses, lekin bade blocks ⇒ better spatial locality. Yeh ek trade-off hai, strict win nahi — Cache Performance Metrics se connect karta hai.

Verify karo: purana $5 + 11 + 16 = 32$ ; naya $6 + 10 + 16 = 32$ ; tag identical 16 pe. ✓

Recall Pure matrix pe quick self-test

Kaun sa field hit vs miss decide karta hai? ::: Tag aur Index dono milke (valid bit ke saath); offset kabhi nahi karta. Cache mein empty lines hote hue bhi har baar miss kyun ho sakta hai? ::: Direct-mapping colliding blocks ko ek hi line pe force karta hai (conflict/thrash), free lines ignore karke — cell D. Agar block size $= 1$ byte ho, kaun sa field gayab hota hai? ::: Offset ( $b = 0$ ) — cell E. Block size double karo, cache size fixed rakho: tag ka kya hota hai? ::: Woh same rehta hai; offset $+ 1$ , index $- 1$ cancel ho jaate hain — cell K. 0x1F pe ek 4-byte word read ke liye kitne block fetches chahiye? ::: Do — yeh ek block boundary straddle karta hai (cell G).

Related deeper dives: Cache Replacement Policies (kya evict karein jab lines share hoon — direct-mapped ke liye trivial, sirf ek candidate!), Cache Write Policies (ek write hit/miss pe kya hota hai), aur Set-Associative Caches (Example 3 ki thrashing ka ilaaj).