Cache line size and tags: Visual walkthrough — Hinglish deep dive

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

Shuru karne se pehle, ek word jo hum baar baar use karenge:

Step 1 — Ek memory address bas ek ghar ka number hai

KYA HAI. Main memory byte-boxes ki ek enormous row hai jisme numbers likhe hain: box $0$ , box $1$ , box $2$ , … last box tak. Ek memory address simply woh number hai jo ek box par likha hota hai.

KYUN. Isse pehle ki hum ek address split karein, hume agree karna hoga ki yeh hai kya. Yeh koi mysterious code nahi hai — yeh ek badi lambi street par ek plain ghar ka number hai. Agar CPU $0$ se lekar $2^{N} - 1$ tak addresses produce kar sakta hai, to hum isse ek $N$ -bit address space kehte hain, kyunki sabse bade ghar ka number likhne mein exactly $N$ bits lagte hain.

PICTURE. Neeche byte-boxes ki street dekho. Amber box woh byte hai jisko CPU ne maanga; uska number, neeche binary mein likha hua, address hai.

Step 2 — Cache ek puri line laata hai, to low bits ek byte ko line ke andar name karti hain

KYA HAI. Cache kabhi ek byte fetch nahi karta; woh $L$ neighbouring bytes ka ek fixed clump fetch karta hai jise cache line kehte hain. $L$ ko power of two choose karo — maano $L = 64$ bytes. Ek poori line cache mein aane ke baad bhi hume yeh batana hota hai ki 64 mein se kaun sa byte CPU chahta tha. Yeh kaam address ke lowest bits karte hain: yeh hain offset.

YEH BITS KYUN, AUR ITNI KYUN? Ek line ke andar ke bytes $0, 1, \dots, L - 1$ numbered hain. $L$ possibilities count karne ke liye exactly utne bits chahiye jo " $2^{?} = L$ " satisfy kare. Woh sawaal — kaunsi power mujhe $L$ degi? — ka jawab $lo g_{2}$ se milta hai. Isliye $lo g_{2}$ aata hai: yeh " $n$ bits $2^{n}$ cheezein count karta hai" ka inverse hai.

b = " L ki power of 2 kya hai?" lo g_{2} bytes per line L

$L = 64$ ke liye: $b = lo g_{2} 64 = 6$ , kyunki $2^{6} = 64$ . To har address ke bottom 6 bits offset hain.

PICTURE. Ek cache line jo apne $64$ byte-slots mein unroll hui hai, slot numbers $6$ -bit binary mein likhe hain. Address ke bottom bits wahi slot numbers hain.

Step 3 — Offset hatao, aur baaki ek line number hai

KYA HAI. Koi bhi address lo aur mentally bottom $b$ bits hata do. Jo bachta hai woh ek line number hai: yeh bataata hai ki memory ke saare clumps mein se yeh byte kaunse $L$ -byte clump mein hai.

KYUN. Same line ke do addresses mein offset bits ke alawa sab kuch same hota hai. To inhe $b$ bits drop karna same hai jaise address ko $L$ se integer-divide karna. Result line identify karta hai, byte ko nahi — aur yahi woh number hai jiske baare mein cache reason karega.

PICTURE. Puri address bar jisme ek scissors low $b$ bits kaat rahi hai; amber remainder "line number" label hai.

Step 4 — Cache mein sirf kuch slots hain, to line numbers ko wrap around karna padta hai

KYA HAI. Cache chhota hota hai: ek direct-mapped cache mein kuch slots hote hain, use $S$ slots kaho (yeh bhi power of two). Memory mein lines ke mukable cache ke slots bahut kam hote hain. To bahut sari alag lines ek hi slot share karne par majboor hoti hain. Kaunsi slot mein ek line jaayegi iska rule yeh hai: line number lo aur sirf uske low bits rakho — wahi index hai.

KYUN. "Line number ke low bits rakho" same hai jaise "line number mod $S$ " (remainder after dividing by $S$ ). Mod isliye choose kiya jaata hai kyunki yeh line numbers ki unlimited range ko $0 \dots S - 1$ slots ke fixed set par map karta hai, sasta mein, bina kisi arithmetic ke — bas bits read karo. $S$ slots count karne ke liye hum phir poochte hain "power of two kaunsi $S$ hai?", to:

i = lo g_{2} S, S = \frac{C}{L \cdot A}

Yahan $C$ = total cache size bytes mein, $L$ = line size, $A$ = associativity (kitni lines ek slot share karti hain; $A = 1$ direct-mapped ke liye, set-associative ke liye zyada). $C$ ko $L$ se divide karne par cache mein jitni lines hain unki count milti hai; phir $A$ se divide karne par unhe slots (sets) mein group kiya jaata hai.

PICTURE. Baayein memory lines ka ek lamba column, ek arrow "mod $S$ " unhe daayein $S$ cache slots ke chhote column par fold kar raha hai — kai memory lines ek hi slot par land kar rahi hain.

Step 5 — Alag lines ek hi slot par aayi, to unhe alag karne ke liye ek tag chahiye

KYA HAI. Kyunki bahut si lines ek slot par fold hoti hain (Step 4), slot jaanna kaafi nahi hai — CPU ko confirm karna hota hai ki wahan rakhhi line wahi hai jo usne chaahi thi. Tag woh sab kuch hai jo bacha hai: address ke high bits, index aur offset ke upar. Cache yeh tag data ke saath store karta hai, aur har access par compare karta hai.

KYUN. Index bataata hai kahan dekhna hai; lekin "kahan" ambiguous hai (Step 4 ka folding). Tag woh leftover bits hain jo line number ko unique banate hain. Kyunki address = tag-bits + index-bits + offset-bits aur inhe $N$ tak add hona chahiye:

t = total bits N - index i - offset b

PICTURE. Puri $N$ -bit address bar teen zones mein coloured — amber Tag (high), cyan Index (middle), white Offset (low) — ek bracket ke saath jo $t + i + b = N$ dikhata hai.

Step 6 — Ek lookup dekho: hit vs miss

KYA HAI. Teen fields ko kaam par lagao. (1) Index use karke ek slot par jump karo. (2) Wahan store hua tag padho aur address ke tag se compare karo. (3) Valid bit bhi check karo — ek single bit jiska matlab hai "is slot mein real data hai, power-on ka garbage nahi". Agar tag match kare aur valid $= 1$ → hit; byte return karne ke liye offset use karo. Warna → miss; memory se line fetch karne jao.

KYUN. Yahi poora payoff hai. Index lookup ko $O (1)$ banata hai (ek jump, koi searching nahi). Tag ise sahi banata hai (us galat line ko reject karta hai jo same slot par fold hui thi). Valid ise safe banata hai (ek cold, empty cache kabhi falsely hit report nahi karta). Inme se koi ek na ho to machine toot jaati hai.

PICTURE. Do panels: upar = HIT (stored tag $=$ address tag, valid $1$ , green check, byte returned). Neeche = MISS (tags differ, red cross, arrow back to memory).

Step 7 — Edge cases: degenerate corners jo tumhe survive karne chahiye

KYA / KYUN / PICTURE. Jo formula tum corners par nahi tod sako woh formula tumhe samajh aata hai. Chaar corners:

Line size $= 1$ byte ( $L = 1$ ). To $b = lo g_{2} 1 = 0$ : koi offset bits nahi. Har byte apni khud ki line hai. Legal hai, bas wasteful — sari spatial locality chali jaati hai.
Poori memory cache mein fit ho jaaye ( $C =$ memory size, $A = 1$ ). To $i$ badhta hai jab tak $t = 0$ nahi ho jaata: koi tag bits nahi. Har line ka permanent ghar hai, koi folding nahi, to disambiguate karne ke liye koi tag nahi chahiye.
Fully associative ( $A =$ number of lines, to $S = 1$ ). To $i = lo g_{2} 1 = 0$ : koi index bits nahi. Ek giant slot; line kahin bhi reh sakti hai, to tag ko saare line-number bits carry karne honge.
Byte-offset zero / line-aligned address. Bottom $b$ bits sab $0$ hain: CPU ne line ka pehla byte manga tha. Kuch special nahi toot ta — offset bas $0$ read karta hai.

Har corner mein, $t, i, b$ mein se ek $0$ tak shrink ho jaata hai lekin identity $t + i + b = N$ tab bhi hold karti hai. Koi bhi case isse escape nahi kar sakta.

Step 8 — Ek poora numeric run, Worked Example 2 se match karta hua

KYA HAI. $C = 32 KiB = 32768$ B, $L = 64$ , $A = 1$ , $N = 32$ lo. To $b = 6$ , lines $= 32768/64 = 512$ , to $i = lo g_{2} 512 = 9$ , aur $t = 32 - 9 - 6 = 17$ . Ab address 0x0012A40 $= 76352$ decode karo.

KYUN. Numbers pictures ko concrete banate hain aur split machine-check karne dete hain. $32$ -bit pattern ko top se slice karo: Tag $=$ high $17$ bits $= 2$ , Index $=$ agle $9$ bits $= 169$ , Offset $=$ low $6$ bits $= 0$ .

PICTURE. $76352$ ki $32$ -bit binary jisme $17∣9∣6$ cut lines drawn hain, har slice ki decimal value neeche label ki gayi hai.

Ek-picture summary

Upar ki sab kuch ek single diagram mein compress: ek address upar se enter karta hai; low $b$ bits Offset ban ke split hoti hain, agle $i$ bits fold ho ke (mod $S$ ) slot via Index pick karte hain, top $t$ bits Tag ban jaate hain jo slot mein stored cheez se compare hoti hain — neeche hit ya miss.

Recall Feynman retelling — plain words mein vapas bolo

Memory ek mile-lambi street hai numbered byte-boxes ki; address ek box ka number hai. Cache greedy hota hai: ek box ki jagah woh $L$ boxes ka poora neighbourhood grab karta hai — ek line — kyunki generally tumhe jald hi next box chahiye hota hai. To address ke bottom $b = lo g_{2} L$ bits bas yeh kehte hain ki neighbourhood mein kaun sa box tumhara matlab tha: yeh offset hai. Unhe chop karo aur jo number bachta hai woh poore neighbourhood ka naam hai — line number. Lekin cache mein sirf $S$ parking slots hain, neighbourhoods se bahut kam, to yeh line numbers ko slots par fold karta hai unke low $i = lo g_{2} S$ bits rakh ke: yeh index hai — yahi parking rule hai. Bahut se neighbourhoods ek hi slot mein park karte hain, to jab tum aate ho to tumhe ek label check karna hota hai ki slot mein jo car hai woh tumhari hai: leftover high $t = N - i - b$ bits woh label hain, yeh tag hai, aur ek tiny valid flag hai jo kehta hai ki slot empty nahi hai. Lookup teen moves hai: index tumhe slot tak drive karta hai, tag confirm karta hai ki line sahi hai, offset tumhara byte grab karta hai. Aur chahe cache kaisi bhi size karo — tiny lines, huge associativity, memory jo completely fit ho — teen widths hamesha $N$ tak add back ho jaate hain.

Connections

Cache line size and tags (index 5.4.4) — parent result jisko yeh page zero se derive karta hai.
5.4.04 Cache line size and tags (Hinglish) — same content Hinglish mein.
5.4.01-Cache-fundamentals — caching exist kyun karta hai.
5.4.02-Direct-mapped-caches — woh $A = 1$ machine jisko hum walk through kiya.
5.4.03-Set-associative-caches — $A > 1$ hone par index ek set index ban jaata hai.
5.4.05-Cache-miss-types — Step 6 ka miss branch kahan jaata hai.
5.4.08-Write-policies — jahan dirty bit valid bit ke saath join karta hai.
6.2.01-Virtual-memory-pages — pages ke liye same tag/index/offset trick.
3.1.04-Spatial-locality — woh reason ki Step 2 poori line fetch karta hai.