Cache line size and tags: Exercises — Hinglish deep dive

5.4.4 · D4 · Hardware › Memory Hierarchy & Caches › Cache line size and tags

Yeh page parent topic ki practice ground hai. Neeche har problem fully solved hai ek collapsible callout ke andar — pehle khud try karo, phir reveal karo. Levels seedhe fields ko pehchaanna se lekar scratch se cache design karna tak jaate hain.

Shuru karne se pehle, ek figure saari vocabulary fix kar deta hai taaki koi symbol kabhi unexplained na rahe.

Level 1 — Recognition

Exercise 1.1

Ek cache 128-byte lines use karti hai. Har address ko kitne offset bits chahiye?

Recall Solution 1.1

Offset ko ek line ke andar har byte ko name karna hoga. $L = 128$ byte-positions hain. $b = lo g_{2} 128 = lo g_{2} 2^{7} = 7 bits .$ $lo g_{2}$ kyun? 128 distinct positions ke liye exactly utne bits chahiye jo $0$ se $127$ tak count kar sakein, aur $2^{7} = 128$ . Toh 7 bits.

Exercise 1.2

Ek direct-mapped cache mein $2048$ lines hain. Kitne index bits?

Recall Solution 1.2

Direct-mapped matlab $A = 1$ , toh sets ki sankhya = lines ki sankhya = $2048$ . Index $2048$ mein se ek slot pick karta hai. $i = lo g_{2} 2048 = lo g_{2} 2^{11} = 11 bits .$ 11 bits.

Exercise 1.3

Field widths $t = 20$ , $i = 6$ , $b = 6$ diye hain, toh total address width $N$ kya hai?

Recall Solution 1.3

Teeno fields hi poori address hain, edge to edge — koi bit leftover nahi, koi shared nahi. $N = t + i + b = 20 + 6 + 6 = 32 bits .$ 32-bit address space.

Level 2 — Application

Exercise 2.1

Ek 16 KiB direct-mapped cache 32-bit machine par 32-byte lines use karti hai. $b$ , $i$ , $t$ nikalo.

Recall Solution 2.1

Step 1 — offset. $L = 32 = 2^{5} \Rightarrow b = 5$ . (line mein har byte ko name karta hai) Step 2 — lines ki sankhya. $C = 16 KiB = 16384$ B. Lines $= \frac{C}{L} = \frac{16384}{32} = 512 = 2^{9}$ . Step 3 — index. $A = 1$ , toh $i = lo g_{2} 512 = 9$ . (har slot ko name karta hai) Step 4 — tag. $t = N - i - b = 32 - 9 - 5 = 18$ . Answer: [18-bit Tag | 9-bit Index | 5-bit Offset].

Exercise 2.2

2.1 wali hi cache. CPU address 0x0000_2C64 request karta hai. Ise Tag / Index / Offset mein split karo.

Recall Solution 2.2

Pehle, 0x2C64 = $2 \cdot 4096 + 12 \cdot 256 + 6 \cdot 16 + 4 = 8192 + 3072 + 96 + 4 = 11364$ (decimal).

32-bit binary mein: 0000 0000 0000 0000 0010 1100 0110 0100

Top se [18 tag | 9 index | 5 offset] split karo:

Offset = low 5 bits = 0 0100 = 4.
Index = agle 9 bits = 011 0011 shifted... seedha compute karte hain. Offset drop karo: $⌊ 11364/32 ⌋ = 355$ line number hai. Index $= 355 mod 512 = 355$ .
Tag = high bits $= ⌊ 355/512 ⌋ = 0$ .

Answer: Tag $= 0$ , Index $= 355$ , Offset $= 4$ . Check: $Tag \cdot 2^{14} + Index \cdot 2^{5} + Offset = 0 + 355 \cdot 32 + 4 = 11360 + 4 = 11364$ ✓ (note $i + b = 14$ , toh tag ko $2^{14}$ se multiply kiya gaya).

Exercise 2.3

2.1 wali cache ke liye, poori cache kitne tag storage bits use karti hai (tag + valid bit, no dirty bit)?

Recall Solution 2.3

Per line: tag $= 18$ bits, valid $= 1$ bit $\Rightarrow 19$ bits. $512$ lines hain. $512 \times 19 = 9728 bits = 1216 bytes \approx 1.19 KiB .$

Level 3 — Analysis

Exercise 3.1

Do engineers ek fixed 32 KiB, direct-mapped, 32-bit cache ke baare mein argue kar rahe hain. Engineer A line size ko 64 B se double karke 128 B kar deta hai. (a) index bits, (b) tag bits, (c) total tag-storage bytes ka kya hota hai? Har direction explain karo.

Recall Solution 3.1

Cache size $C = 32768$ B fixed rehti hai. $N = 32$ , $A = 1$ .

Case 64 B: $b = 6$ . Lines $= 32768/64 = 512 = 2^{9} \Rightarrow i = 9$ . $t = 32 - 9 - 6 = 17$ . Tag storage (tag + valid) $= 512 \times (17 + 1) = 512 \times 18 = 9216$ bits $= 1152$ B.

Case 128 B: $b = 7$ . Lines $= 32768/128 = 256 = 2^{8} \Rightarrow i = 8$ . $t = 32 - 8 - 7 = 17$ . Tag storage $= 256 \times (17 + 1) = 256 \times 18 = 4608$ bits $= 576$ B.

(a) Index: $9 \to 8$ — 1 se ghatta, kyunki line size double karne se lines ki sankhya half ho jaati hai. (b) Tag: $17 \to 17$ — yahan unchanged. Humne 1 offset bit khoya lekin 1 index bit bhi khoya; dono cancel ho gaye ( $t = N - i - b$ , aur $i + b$ 15 pe hi raha). (c) Tag storage: $1152 \to 576$ B — half ho gayi, kyunki half lines hain, har ek usi 18 metadata bits ke saath.

Exercise 3.2

Ek cache designer line size $L = 64$ B aur address width $N = 32$ rakhta hai, lekin cache ko 16 KiB se 64 KiB tak grow karta hai (dono direct-mapped). Dikhao ki tag bits shrink karte hain aur kitne.

Recall Solution 3.2

$b = lo g_{2} 64 = 6$ throughout.

16 KiB: lines $= 16384/64 = 256 = 2^{8} \Rightarrow i = 8$ . $t = 32 - 8 - 6 = 18$ . 64 KiB: lines $= 65536/64 = 1024 = 2^{10} \Rightarrow i = 10$ . $t = 32 - 10 - 6 = 16$ .

Cache ko $\times 4$ grow karne se $lo g_{2} 4 = 2$ index bits add hote hain, jo tag se 2 bits chura lete hain: $18 \to 16$ . Intuition: badi cache mein zyada slots hain, toh address ka zyada hissa yeh batane mein kharch hota hai ki kaunsa slot — blocks ko alag karne ke liye fewer bits bachte hain jo same slot mein land karte hain.

Level 4 — Synthesis

Exercise 4.1

Design task. Ek 64-bit machine ko 4-way set-associative cache chahiye, total size $C = 256$ KiB, line size $L = 64$ B. Sets, $b$ , $i$ , $t$ , aur total metadata (tag + valid + dirty) KiB mein compute karo.

Recall Solution 4.1

Step 1 — offset. $L = 64 = 2^{6} \Rightarrow b = 6$ . Step 2 — total lines. $C / L = 262144/64 = 4096$ lines. Step 3 — sets. Set-associative $A = 4$ lines per set pack karta hai: $sets = \frac{C}{L \cdot A} = \frac{262144}{64 \cdot 4} = \frac{4096}{4} = 1024 = 2^{10} .$ Toh $i = lo g_{2} 1024 = 10$ (index ab ek set ko name karta hai, single line ko nahi). Step 4 — tag. $t = N - i - b = 64 - 10 - 6 = 48$ bits. Step 5 — metadata. $4096$ lines mein se har ek tag (48) + valid (1) + dirty (1) $= 50$ bits carry karti hai. $4096 \times 50 = 204800 bits = 25600 B = 25 KiB .$ Answer: 1024 sets, $b = 6$ , $i = 10$ , $t = 48$ ; metadata $= 25$ KiB.

Exercise 4.2

4.1 jaisa hi lekin direct-mapped (A=1) bana do, baaki sab same. Kya badlega — $b$ , $i$ , ya $t$ — aur kyun tag badhta hai?

Recall Solution 4.2

$b = 6$ (line size unchanged). Ab sets $=$ lines $= C / L = 4096 = 2^{12} \Rightarrow i = 12$ . $t = 64 - 12 - 6 = 46$ bits.

4.1 se compare karein: index $10 \to 12$ (+2) badha aur tag $48 \to 46$ (−2) gira... ruko — tag chota hua, bada nahi. Same $C, L, N$ ke saath, direct-mapped ke zyada sets hain ( $4096$ vs $1024$ ), toh zyada index bits chahiye aur kam tag bits.

Lesson: associativity badhana (fewer sets) tag ko badhata hai; ghataana tag ko ghataata hai. Set-associative version (4.1, $t = 48$ ) ka tag bada hai.

Level 5 — Mastery

Exercise 5.1

Reverse-engineering. Bataya gaya hai ki ek address [Tag | Index | Offset] ke roop mein split hota hai jisme lookup circuit $i = 7$ index bits aur $b = 8$ offset bits use karta hai ek 32-bit machine par, aur cache 2-way set-associative hai. $L$ , sets ki sankhya, total cache size $C$ , aur $t$ recover karo.

Recall Solution 5.1

Line size: $b = 8 \Rightarrow L = 2^{8} = 256$ B. Sets: $i = 7 \Rightarrow$ sets $= 2^{7} = 128$ . Cache size: $C = sets \times A \times L = 128 \times 2 \times 256 = 65536$ B $= 64$ KiB. Tag: $t = N - i - b = 32 - 7 - 8 = 17$ bits. Sanity check via formula: $i = lo g_{2} (C / (L \cdot A)) = lo g_{2} (65536/ (256 \cdot 2)) = lo g_{2} (128) = 7$ ✓. Answer: $L = 256$ B, 128 sets, $C = 64$ KiB, $t = 17$ .

Exercise 5.2

Capstone trade-off. Do designs, dono 32-bit, 16 KiB, direct-mapped:

Design P: $L = 16$ B.
Design Q: $L = 128$ B. Dono ke liye metadata overhead fraction (tag + valid + dirty per line, data bytes ke upar) compute karo, aur batao kaunsa overhead mein jeetta hai aur har ek kya sacrifice karta hai.

Recall Solution 5.2

$C = 16384$ B, $N = 32$ , $A = 1$ .

Design P ( $L = 16$ ): $b = 4$ . Lines $= 16384/16 = 1024 = 2^{10} \Rightarrow i = 10$ . $t = 32 - 10 - 4 = 18$ . Metadata/line $= 18 + 2 = 20$ bits $= 2.5$ B. Data/line $= 16$ B. Overhead fraction $= 2.5/16 = 0.15625 = 15.625%$ .

Design Q ( $L = 128$ ): $b = 7$ . Lines $= 16384/128 = 128 = 2^{7} \Rightarrow i = 7$ . $t = 32 - 7 - 7 = 18$ . Metadata/line $= 18 + 2 = 20$ bits $= 2.5$ B. Data/line $= 128$ B. Overhead fraction $= 2.5/128 = 0.01953 = 1.953%$ .

Overhead mein winner: Design Q — badi lines fixed 20-bit tag block ko kahin zyada data pe amortise karti hain (2.0% vs 15.6%). Sacrifice: Q ke paas sirf 128 lines hain P ki 1024 ke mukable, toh Q zyada conflict misses aur zyada miss penalty (128 B transfers) suffer karta hai. P chip area metadata par waste karta hai lekin kaafi saare distinct slots rakhta hai. Yahi exactly woh spatial-locality trade-off hai jo real CPUs ko 64 B tak le jaata hai — beech ka raasta.

Recall Ek-line field recovery cheat card

Widths se: $L = 2^{b}$ ; sets $= 2^{i}$ ; $C = 2^{i} \cdot A \cdot 2^{b}$ ; $t = N - i - b$ . Ek address value split karne ke liye: offset $= addr mod 2^{b}$ ; line# $= ⌊ addr / 2^{b} ⌋$ ; index $= line# mod 2^{i}$ ; tag $= ⌊ line# / 2^{i} ⌋$ .

Connections

Cache line size and tags — parent theory jise yeh drills exercise karti hain.
5.4.02-Direct-mapped-caches — L1–L3 maan lete hain $A = 1$ .
5.4.03-Set-associative-caches — L4–L5 sets aur $\div A$ step introduce karte hain.
5.4.05-Cache-miss-types — L5 trade-off ke peeche conflict-miss cost.
5.4.08-Write-policies — jahan se metadata counts mein dirty bit aata hai.
3.1.04-Spatial-locality — kyun badi lines help karti hain.

#flashcards/hardware