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

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

Isse pehle ki tum parent note follow karo, usmein use hone wali har squiggle ka kuch concrete matlab tumhare dimaag mein hona chahiye. Ye page har ek cheez ko zero se build karta hai, ek aisi order mein jahan har idea apne se pehle wale par tikta hai.

0. "Bit" kya hota hai? (har cheez ka atom)

Saath mein likhe bits ki ek row ek binary number hoti hai. Isko padhna bilkul decimal number padhne jaisa hai, bas har place apni right wali jagah se 10 times ki jagah 2 times worth hoti hai.

Figure — Cache organization (direct-mapped)

Figure dekho: sabse right wala bit "ones" place hai ( $2^{0}$ ), uske baad "twos" ( $2^{1}$ ), phir "fours" ( $2^{2}$ ), aur aage bhi aise hi. Value nikalne ke liye jahan bhi $1$ hai wahan ke place-values add karte hain.

Topic ko ye kyun chahiye: ek memory address bits ki ek row hi hai. Parent jo bhi "chopping" karta hai wo us row mein se certain bits grab karna hai — jab tak pata na ho ki ek bit ki kya worth hai, ye samajhna impossible hai.

1. Exponent notation $2^{n}$ (kyun powers of two sab pe raaj karti hain)

$n$ bits	patterns $2^{n}$
$1$	$2$
$2$	$4$
$3$	$8$
$10$	$1024$ (= 1 KB of things)

Topic ko ye kyun chahiye: cache size, block size, aur line count hamesha powers of two hote hain exactly isliye taaki address bits ka ek poora saaf group har ek ko name kar sake.

2. Logarithm $lo g_{2}$ ( $2^{n}$ ka exact undo)

$2^{n}$ jawab deta hai " $n$ bits kitne patterns dete hain?". Lekin parent hamesha ulta sawaal poochta hai: "Mujhe $2048$ lines name karni hain — uske liye kitne bits chahiye?"

Ye tool kyun, division kyun nahi? Division batata hai ki kitni baar kuch fit hota hai; $lo g_{2}$ batata hai ki kitne switches lagte hain — ye bilkul alag sawaal hai, aur ye wahi bit-counting sawaal hai jis par caches chalti hain.

$x$ ka power of two hona zaroori hai tabhi ye ek whole number par aata hai — aur exactly isliye cache sizes hamesha hoti hain.

3. Bytes aur "byte-addressable memory"

Topic ko ye kyun chahiye: parent ka "block offset" tabhi sense karta hai jab tum memory ko individually-numbered byte-mailboxes ki tarah dekho; offset ek group ke andar kaun sa mailbox chahiye wo batata hai. Poori picture ke liye Memory Addressing dekho.

4. Address ek $m$ bits ki row ke roop mein

Poore topic ka sabse important move: ek address $m$ bits ki ek row hai, aur hum us row ko teen labelled fields mein slice karenge. Us image ko pakad ke rakho.

5. Block — mailboxes ko group karna

Groups kyun? Kyunki programs almost always aas-paas ke bytes use karte hain jaldi baad mein (ye spatial locality hai). Ek poora neighbourhood ek saath fetch karna ek-ek mailbox fetch karne se sasta hai.

6. Modulo `mod` — wrap-around rule

Parent ke core formula mein $mod$ use hota hai. Ye "real math" ka ek hi piece hai aur iske liye ek picture deserve karta hai.

Ye tool kyun? Cache mein sirf $2^{c}$ lines hain lekin memory mein millions of blocks hain. Hume ek aisa rule chahiye jo koi bhi block number le aur hamesha $0 \dots 2^{c} - 1$ ke andar land kare, fairly cycling karte hue. Modulo exactly "wrap the counter" operation hai — koi aur simple operation har block ko ek definite, repeatable home slot nahi deta.

Ek khoobsurat shortcut: jab $n = 2^{c}$ ho, toh mod ka matlab bas "lowest $c$ bits rakhna" hai — kyunki wo low bits pehle se hi remainder hote hain. Isliye parent real division karne ki jagah bits grab kar sakta hai.

7. Floor $⌊ ⌋$ — leftovers phenkna

Parent block number ko $⌊ \frac{Address}{2 ^{b}} ⌋$ likhta hai. Address ko $2^{b}$ se divide karke floor karna matlab hai "last $b$ offset bits chop off karo" — ye discard karta hai ki tumhe kaun sa byte chahiye aur sirf kaun sa block chahiye wo rakhta hai. Bit-terms mein ye $b$ se right shift hai.

8. Slices ko saath jodna — Tag / Index / Offset

Ab har symbol earn ho chuka, parent ka decomposition clearly samajh aata hai. $m$ -bit address ko slice karo:

$Tag m - c - b bits Index c bits Offset b bits$

Offset (low $b$ ): block ke andar kaun sa byte — §5 se.
Index (middle $c$ ): kaun si cache line, wrap rule ke through — §6 se.
Tag (top $m - c - b$ ): jo bhi bacha, use prove karne ke liye ki line tumhara block hold karti hai koi colliding wala nahi.

Aage kahan jaate hain ye? Tags-per-line aur valid bits Cache Performance Metrics drive karte hain; ek block ko ek ki jagah several slots choose karne dena Set-Associative Caches hai; jab slots fill hoon toh kise kick out karein decide karna Cache Replacement Policies hai; writes memory ko kaise update karein decide karna Cache Write Policies hai.

Prerequisite map

Equipment checklist

Right side cover karo aur aage badhne se pehle har ek ka jawab do.

Binary number

101 0_{2}

ko decimal value mein padho

8 + 2 = 10

2^{n}

kya count karta hai, ek phrase mein

n

bits se banaye ja sakne wale distinct patterns ki sankhya

lo g_{2} 512

compute karo

9

, kyunki

2^{9} = 512

2^{c}

cache lines name karne ke liye kitne bits chahiye

exactly

c

bits

"Byte-addressable" ka matlab kya hai

har single byte ka apna numbered address hota hai

Agar block size

2^{b}

bytes hai, toh kitne offset bits hain

b

bits

13 mod 4

compute karo

1

(wraps: 0,1,2,3,0,1... 13 pe 1 aata hai)

Jab

n = 2^{c}

ho,

a mod n

compute karne ka fast tarika

a

ke lowest

c

bits rakh lo

⌊ Address / 2^{b} ⌋

kya deta hai

block number (offset bits chop ho jaate hain)

Kaun sa field cache line pick karta hai

Index (middle bits), kabhi Tag nahi

Tag kis kaam aata hai

ye prove karne ke liye ki ek line tumhara block hold karti hai un sab blocks mein se jo apna index share karte hain

Valid bit ka

0

hona kya force karta hai

ek miss — line khali hai

m = 8, c = 2, b = 2

ke liye, kitne Tag bits hain

8 - 2 - 2 = 4

bits