Cache organization (direct-mapped): Exercises — Hinglish deep dive

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

Intuition Is page ko kaise use karein

Ye problems "bits padho" se shuru hokar "cache design karo aur defend karo" tak jaati hain. Har ek ko L1 → L5 grade kiya gaya hai. Har problem ko collapsible solution kholne se pehle khud try karo. Parent note hai Cache organization (direct-mapped) — agar koi symbol yahan unexplained lage, woh note ne use pehle build kiya hai.

Poore note mein, parent se yahi teen address fields reuse hoti hain: $Tag m - c - b bits Index c bits Offset b bits$ jahan $m$ = address width, $2^{c}$ = cache lines ki sankhya, $2^{b}$ = block size bytes mein.

Ek notation note: jahan bhi koi final numerical answer aata hai, use ==double equals== mein wrap kiya gaya hai. Is vault mein yeh ek cloze mark karta hai — woh term ya number jo tumhe khud yaad rakhna chahiye; review karte waqt yahi woh blank hai jo tumhe fill karna hai. Iska koi mathematical matlab nahi; yeh bas ek "yeh yaad rakho" highlight hai.

Shuru karne se pehle, Figure 1 (s01) dekho. Yeh woh map hai jo har problem use karta hai: yeh ek single address ko ek horizontal bar ke roop mein dikhata hai jo teen coloured boxes mein split hai — left par ek lavender Tag box (most-significant bits), beech mein ek mint Index box ( $c$ bits), aur right par ek butter-yellow Offset box (least-significant $b$ bits). Har box se ek arrow girta hai us kaam par jo woh karta hai: Tag → "batata hai KI KAUN SA memory block hai," Index → "KAUN SI cache line chunata hai (koi search nahi!)," Offset → "block mein KAUN SA byte chunata hai." Neeche hit rule likha hai (tag compare karo AUR valid = 1) aur yaad dilata hai ki offset kabhi miss ka kaaran nahi banta.

Figure — Cache organization (direct-mapped)

Level 1 — Recognition

"Kya tum fields ko seedha address se padh sakte ho?"

Exercise 1.1

Ek cache mein $b = 4$ (16-byte blocks) aur $c = 6$ (64 lines) hain, $m = 16$ -bit addresses ke saath. (a) Kitne tag bits hain? (b) Address 0xB3A7 ke liye (tag, index, offset) binary aur decimal mein do.

Recall Solution 1.1

(a) Tag bits $= m - c - b = 16 - 6 - 4 === 6 ==$ bits.

(b) 0xB3A7 ko binary mein likho (16 bits): $1011 0011 1010 0111$ Right se split karo (bilkul Figure 1 ka box order) — offset sabse neeche hai, phir index, phir tag:

Offset = lowest $b = 4$ bits = 0111 = $7$ .
Index = agle $c = 6$ bits. Low 4 offset hain, toh index bits $[9 : 4]$ hai. Unhe group karo: bits ...11 1010 0... → index bits hain 111010 = $58$ .
Tag = top $6$ bits = bits $[15 : 10]$ = 101100 = $44$ .

Check: $44 \cdot 2^{10} + 58 \cdot 2^{4} + 7 = 45056 + 928 + 7 = 45991 = 0xB3A7$ . ✅

Exercise 1.2

Wahi cache jaise 1.1 mein hai. 0xB3A7 ka block address kya hai (woh address jisme offset bits strip ho gayi hain)?

Recall Solution 1.2

Block address $= ⌊ \frac{Address}{2 ^{b}} ⌋ = ⌊ \frac{45991}{16} ⌋ === 2874 ==$ . Sanity check: binary mein block address bas "tag ∥ index" hai = 101100 111010 = $2874$ . ✅

Level 2 — Application

"Ek address diya hai, hit/miss ka decision karo."

Exercise 2.1

Ek cache mein 16 bytes data hai, 4-byte blocks hain, aur 8-bit addresses hain. Pehle khud field widths nikalo, phir: line 3 mein abhi valid data stored hai aur stored tag = 0010 (=2) hai, aur tum 0x2E access karte ho. (a) $b$ , $c$ , aur tag width nikalo. (b) 0x2E ke liye (tag, index, offset) compute karo. (c) Hit hai ya miss? Kyun?

Recall Solution 2.1

(a) Fields nikalna (self-contained):

Block size $= 4 = 2^{2}$ bytes → $b = 2$ (offset bits).
Lines ki sankhya $= \frac{cache size}{block size} = \frac{16}{4} = 4 = 2^{2}$ → $c = 2$ (index bits). Toh exactly 4 lines hain, 0–3 numbered.
Tag width $= m - c - b = 8 - 2 - 2 = 4$ bits.

(b) 0x2E = 0010 1110 (8 bits).

Offset = low 2 bits = 10 = $2$ .
Index = agle 2 bits = 11 = $3$ .
Tag = top 4 bits = 0010 = $2$ .

(c) Line 3 par jao (index turant bata deta hai, koi search nahi). Valid = 1 ✅ aur stored tag 0010 address tag 0010 se match karta hai ✅. Hit condition ke hisaab se $Hit = (Valid = 1) \land (Tag_{cache} = Tag_{addr}),$ yeh ek HIT hai. Line 3 ke block ka byte $2$ return karo.

Exercise 2.2

Wahi 16-byte / 4-byte-block / 8-bit cache ( $b = 2$ , $c = 2$ , 4 lines). Is stream ko cold (sab-invalid) cache par trace karo aur har access ko H (hit) ya M (miss) label karo: $0x00, 0x01, 0x04, 0x00$

Recall Solution 2.2

Har ek ko decode karo (offset = low 2 bits, index = agle 2 bits, tag = top 4):

Addr	binary	index	offset	block addr $= ⌊ a /4 ⌋$
0x00	0000 0000	0	0	0
0x01	0000 0001	0	1	0
0x04	0000 0100	1	0	1
0x00	0000 0000	0	0	0

0x00: line 0 invalid hai → M (cold). Block 0 load karo, tag 0.
0x01: line 0 ab valid hai, tag 0 match karta hai → H (same block, alag byte).
0x04: line 1 invalid hai → M (cold). Alag index hai!
0x00: line 0 abhi bhi block 0 hold kar rahi hai, tag match → H.

Result: M H M H → 2 hits, 2 misses. Hit rate $= 2/4 === 0.5 ==$ .

Level 3 — Analysis

"Collisions aur thrashing explain aur quantify karo."

Exercise 3.1

16-byte cache, 4-byte blocks, 8-bit addresses (toh $b = 2$ , $c = 2$ , 4 lines). $[0, 255]$ mein teeno woh aur addresses list karo jo (a) 0x0D ke same line par map hote hain aur (b) alag block se belong karte hain (conflict cause karenge). Sabse chhote aise addresses do.

Recall Solution 3.1

0x0D = 0000 1101: index = 11 = 3, tag = 0000.

"Block address $mod 4$ " se index kyun milta hai? Definitions se shuru karo. Offset strip karo: block address hai $B = ⌊ a / 2^{b} ⌋$ . Iska binary form bilkul woh address hai jisme low $b$ bits hata diye gaye hain — yaani, "tag ∥ index" ke bits jodon mein. Index $B$ ke lowest $c$ bits mein hota hai. Kisi bhi integer ko modulo $2^{c}$ lena sirf uske lowest $c$ bits rakhta hai aur baaki discard karta hai (yahi binary mein $mod 2^{c}$ ki definition hai). $B$ ke woh lowest $c$ bits hi index field hain. Isliye $Index = B mod 2^{c} = ⌊ \frac{a}{2 ^{b}} ⌋ mod 2^{c},$ aur yahan $c = 2$ ke saath, woh hai $B mod 4$ . Yahi kaaran hai ki blocks $3, 7, 11, 15, \dots$ (sab $\equiv 3 (mod 4)$ ) line 3 par land karte hain.

Block 3 se conflict karne wale distinct blocks (block address of 0x0D is $⌊ 13/4 ⌋ = 3$ ):

block 7 → base address $7 \cdot 4 = 28 = 0x1C$ , tag = 0001
block 11 → $11 \cdot 4 = 44 = 0x2C$ , tag = 0010
block 15 → $15 \cdot 4 = 60 = 0x3C$ , tag = 0011

Toh 0x1C, 0x2C, 0x3C teeno 0x0D ke saath line 3 ke liye ladte hain. Har ek ka tag alag hai, isliye koi bhi interleaving thrash karega.

Exercise 3.2

Usi cold cache par, yeh loop 3 iterations chalta hai: $(0x0D, 0x4D) \times 3$ 0x4D = 0100 1101 → index 3, tag 0100. Total misses count karo aur miss rate do. Har miss classify karo (cold vs conflict).

Recall Solution 3.2

Dono line 3 par map karte hain, tags 0000 vs 0100 alag hain → woh collide karte hain.

#	access	line 3 before	result	line 3 after
1	0x0D	invalid	M (cold)	tag 0000
2	0x4D	tag 0000	M (conflict)	tag 0100
3	0x0D	tag 0100	M (conflict)	tag 0000
4	0x4D	tag 0000	M (conflict)	tag 0100
5	0x0D	tag 0100	M (conflict)	tag 0000
6	0x4D	tag 0000	M (conflict)	tag 0100

Total accesses = 6, misses = 6. Miss rate = $6/6 === 1.0 ==$ (100% — pure thrashing): 1 cold + 5 conflict.

Figure 2 (s02) is ping-pong ko draw karta hai: left par 4 cache lines ka stack hai jisme sirf line 3 coral colour ki hai (lines 0–2 khali hain); right par dono blocks 0x0D (tag 0000) aur 0x4D (tag 0100) hain. Curved arrows dikhate hain ki har block line 3 mein load hota hai aur doosre ko turant evict karta hai, aur result panel mein likha hai "M M M M M M, miss rate = 100%," aur neeche ("set-associativity") ka ilaaj box mein hai.

Level 4 — Synthesis

"Fields design karo; har bit account karo."

Exercise 4.1

Ek direct-mapped cache design karo: 32-bit addresses, 32 KB data, 64-byte blocks. $b$ , $c$ , tag bits, aur total SRAM bits compute karo, jisme har line mein 1 valid bit bhi shaamil ho.

Recall Solution 4.1

Block size $= 64 = 2^{6}$ → $b === 6 ==$ .
Lines ki sankhya $= \frac{32 KB}{64 B} = \frac{32768}{64} = 512 = 2^{9}$ → $c === 9 ==$ .
Tag $= m - c - b = 32 - 9 - 6 === 17 ==$ bits.

Har line ke bits = data $64 \times 8 +$ tag $17 +$ valid $1 = 512 + 17 + 1 = 530$ bits. Total = $512 lines \times 530 === 271360 ==$ bits $= 33920$ bytes $\approx 33.1$ KB. 32 KB data par overhead: $\frac{17 + 1}{512} \approx== 3.52% ==$ .

Exercise 4.2

4.1 ke cache ke liye ( $m = 32$ , $b = 6$ , $c = 9$ , tag $= 17$ ), kya address 0xDEADBEEF hit hai agar us line par jahan yeh map karta hai valid data stored hai aur stored tag 0x1BD45 hai? Index aur tag explicitly decode karo aur decide karo.

Recall Solution 4.2

0xDEADBEEF $= 3735928559$ . Standard formulas se fields nikalo.

Offset $= a mod 2^{b} = a mod 64$ . …EF ke low 6 bits = 101111 = $47$ .

Index $= ⌊ \frac{a}{2 ^{b}} ⌋ mod 2^{c} = ⌊ \frac{a}{64} ⌋ mod 512$ . $⌊ 3735928559/64 ⌋ = 58373883$ , aur $58373883 mod 512 = 315$ . Toh 0xDEADBEEF line 315 par map karta hai (binary 100111011). Kyunki problem kehti hai ki resident line wahi hai jo is index par hai, dono address aur stored line index 315 share karte hain — index yahan outcome decide nahi karta; tag karta hai.

Tag $= ⌊ \frac{a}{2 ^{b + c}} ⌋ = ⌊ \frac{a}{2 ^{15}} ⌋ = ⌊ \frac{3735928559}{32768} ⌋ = 113989 = 0x1BD45$ .

Stored tag hai 0x1BD45 = $113989$ — address tag ke barabar hai, aur line valid hai. Hit condition ke hisaab se yeh ek HIT hai. (Agar stored tag koi aur value hota, toh yeh conflict miss hota, chahe index match karta ho.)

Level 5 — Mastery

"Trade-offs ke baare mein reason karo, behaviour prove karo, designs chunao."

Exercise 5.1

Do direct-mapped caches ki same total data size 8 KB hai.

Cache A: 32-byte blocks. Cache B: 64-byte blocks. Har ek ke liye $(b, c)$ compute karo. Ek workload memory mein stride karta hai, har 48 bytes mein 1 byte padhta hai (toh consecutive reads 48 B apart hain). Is stride ke liye kaun sa cache har fetched block mein zyada spatial locality capture karta hai, aur kyun?

Recall Solution 5.1

A: block $32 = 2^{5}$ → $b = 5$ ; lines $= 8192/32 = 256 = 2^{8}$ → $c = 8$ .
B: block $64 = 2^{6}$ → $b = 6$ ; lines $= 8192/64 = 128 = 2^{7}$ → $c = 7$ .

Stride = 48 B. A mein (32-B blocks), 48 B apart do accesses kabhi same block mein nahi padte (48 > 32), isliye har access ek fresh block hai — spatial locality ka reuse 0 extra bytes milta hai. B mein (64-B blocks), byte $x$ par access aur $x + 48$ par agla access ek block share kar sakta hai (48 < 64) jab bhi $x mod 64 \leq 15$ ho. Toh Cache B is stride par zyada spatial locality capture karta hai. Trade-off: B mein kam lines hain (128 vs 256), isliye kahin aur conflict-miss ka risk badh jaata hai. Bade blocks spatial locality mein madad karte hain lekin line count ki keemat par — koi free lunch nahi.

Exercise 5.2

Prove karo: kisi bhi direct-mapped cache mein, do addresses $x$ aur $y$ kabhi bhi ek saath resident aur hit nahi ho sakte agar woh same index share karte hain lekin alag tags hain. Phir woh ek architectural change batao jo is limitation ko tod deta hai.

Recall Solution 5.2

Ek line ek single slot hai: woh exactly ek (valid, tag, block) triple store karta hai. Maano $x$ aur $y$ index $i$ share karte hain lekin tags $t_{x} \neq = t_{y}$ hain. Dono line $i$ par map karte hain. Line ka tag field $t_{x}$ ya $t_{y}$ ke barabar ho sakta hai, dono simultaneously nahi (yeh ek register hai). Toh kisi bhi instant par $x, y$ mein se sirf ek $Tag_{cache} = Tag_{addr}$ satisfy kar sakta hai. Isliye dono hit nahi ho sakte; ek load karna doosre ko evict karta hai. ∎

Ilaaj: ek set ko ek se zyada lines hold karne do — yaani set-associativity ( $n$ ways ka set $n$ colliding blocks ko ek saath rehne deta hai). $n \geq 2$ ke saath, $x$ aur $y$ dono resident ho sakte hain.

Exercise 5.3

Parent ka thrashing loop (0x0D, 0x4D)×N direct-mapped cache par 100% miss rate deta tha. Agar hum same total size ki 2-way set-associative cache mein upgrade karein aur LRU replacement use karein, toh bade $N$ ke liye steady-state miss rate kya hogi? (Bas reason karo.)

Recall Solution 5.3

Dono blocks same set par map karte hain, lekin 2-way set mein do ways hain — dono blocks fit ho jaate hain, ek per way. Pehle do accesses cold misses hain; uske baad har block resident rehta hai (kuch aur use evict nahi karta), toh har baad ka access hit hota hai. Miss rate $= \frac{2}{2 N} = \frac{1}{N} \to== 0 ==$ jab $N \to \infty$ . Thrashing khatam. Yahi kaaran hai ki associativity standard ilaaj hai — details hain Cache Replacement Policies mein aur write side ke liye Cache Write Policies mein.

Recall Ek-line self-test dump

Kisi bhi address ka tag/index/offset padho ::: offset (low $b$ ) nikalo, phir index (agle $c$ ), baaki tag hai. Index bits ki sankhya ::: $c = lo g_{2} (cache size / block size)$ . Block-address mod $2^{c}$ index ke barabar kyun hota hai ::: modulo $2^{c}$ lowest $c$ bits rakhta hai, jo bilkul block address ka index field hain. Do addresses, same index, alag tag ::: conflict — direct-mapped cache mein ek saath nahi reh sakte. 100% miss par pure thrashing ka ilaaj ::: set-associativity (ek set mein kai ways hote hain). Kya offset kabhi miss cause karta hai ::: nahi — yeh sirf already-chosen line mein ek byte select karta hai.