Foundations — Set-associative and fully associative caches

5.4.3 · D1 · Hardware › Memory Hierarchy & Caches › Set-associative and fully associative caches

Parent note set-associative and fully associative caches padhne se pehle, tumhe har woh symbol khud se banana aana chahiye jo woh tumhare saamne phenk deta hai. Yeh page har ek cheez ko bilkul scratch se build karta hai — pehle plain words, phir ek picture, phir kyun is topic ko yeh cheez chahiye. Upar se neeche padho; har block sirf wahi cheez use karta hai jo usse upar define ho chuki hai.

0. Sab kuch ke peeche ki picture: memory ek giant ruler ki tarah

Is chapter ki har cheez ek idea par tiki hai: memory numbered boxes ki ek lambi line hai, har box mein ek byte (8 bits) hai. Ek box ka number uska address hai.

• Book = main memory (huge, slow), lakhon numbered boxes.
• Notebook = cache (tiny, fast), sirf muthi bhar boxes.
• Poora game: book ka ek chunk notebook mein copy karo taaki CPU use jaldi padh sake.

Yeh picture apne dimag mein rakho. Neeche har symbol iska koi na koi hissa label karta hai.

1. Bit, byte, aur "yeh kitni cheezein count kar sakta hai?"

Hum kyun care karte hain? Kyunki addresses bits mein likhe jaate hain, aur bits ki tadaad humein batati hai ki kitne boxes ko naam de sakte hain.

$n\text{ bits}⟶2^n\text{ distinct patterns}$

• $6$ bits $\to 2^6=64$ patterns.
• $8$ bits $\to 2^8=256$ patterns.
• $32$ bits $\to 2^{32}\approx 4.3$ billion — isliye "32-bit address" lagbhag 4 GB boxes naam de sakta hai.

2. Exponent $2^n$ aur uska undo: ${\log }_2$

Humne abhi $2^n$ use kiya ("do ko $n$ baar khud se multiply karo"). Topic ko baar baar ulta sawaal chahiye hota hai:

"Mere paas $S$ cheezein naam deni hain. Mujhe kitne bits chahiye?"

Woh sawaal ==${\log }_2$== (log base 2) se answer hota hai.

Yahi tool kyun, na ki ordinary division ya ordinary logarithm? Kyunki hardware addresses bits se bane hain, aur har bit ek doubling hai. Doublings count karna exactly wahi kaam hai jo ${\log }_2$ karta hai — koi aur function "how many bit-switches?" ka jawab nahi deta.

3. Hexadecimal — bits ka ek shorthand

Bits ki lambi strings bahut painful hoti hain. Hexadecimal ("hex") 4 bits ko ek symbol mein pack karta hai, $0$–$9$ aur phir $10$–$15$ ke liye $a$–$f$ use karke. Hex numbers 0x prefix ke saath likhe jaate hain.

Topic ko iska kyun zaroorat hai: 0x001A4C0 jaisi addresses bits-strings hi hain disguise mein. Address ko pieces mein split karne ke liye hex $\to$ bits convert karo, kaato, aur padho.

4. Address, aur usse teen pieces mein kaatna

CPU ek byte ko uske address se maangta hai: ek fixed-width bit number (yahan $A=32$ bits wide, $A$ = "address width"). Cache saari bits ko equally treat nahi karta — yeh address ko slice karke teen named fields mein baant deta hai.

Picture mein slice ko least-significant (rightmost) se pehle padho, kyunki low bits ruler par chalte waqt sabse tezi se change hote hain:

Teen pieces kyun, na ki ek? Kyunki ek cache slot ko teen alag sawaalon ka jawab dena hota hai: block ke andar kahan? (offset), kaun si shelf dhundhuun? (index), kya yeh sach mein wahi block hai jo mujhe chahiye tha? (tag). Har sawaal ko apne bits milte hain.

$\underset{\text{total bits}}{\underbrace{A}}=\underset{\text{tag}}{\underbrace{t}}+\underset{\text{index}}{\underbrace{i}}+\underset{\text{offset}}{\underbrace{b}}$

5. Block aur block size $B$

Why copy a whole bundle instead of one byte? Spatial locality — programs lagbhag hamesha jald hi neighbouring boxes use karte hain, toh bundle le lena future trips bachata hai.

• $B$ = block size bytes mein (jaise $B=64$).
• Offset bits $b={\log }_2(B)$. $B=64$ ke saath, $b={\log }_2(64)=6$: exactly itne ki andar ke $64$ bytes mein se kisi ko bhi naam de sako.

6. Line, cache size $C$, aur total lines $L$

• $C$ = total cache size bytes mein.
• Lines ki total tadaad: $L=\frac{C}{B}$

Kyun? Har line exactly $B$ bytes store karti hai, aur $C$ bytes ki jagah hai, toh $C/B$ lines fit hoti hain. Picture mein, chhoti notebook ko $L$ equal shelves mein kaato.

7. Sets $S$, ways $N$, aur associativity

Ab parent note ka star. Hum $L$ lines ko sets mein group karte hain.

Yeh formula kyun? Tumhare paas $L$ shelves hain; tum unhe $N$-$N$ karke bundle karte ho; bundles ki tadaad $L/N$ hai. $L=C/B$ substitute karo toh $C/(B\cdot N)$ milta hai.

Teen cases seedha picture se padho:

• Index bits $i={\log }_2(S)$ — $S$ sets mein se ek pick karne ke liye enough bits.
• Jab $S=1$ (fully associative), $i={\log }_2(1)=0$: koi index field hi nahi. Isliye parent ke fully-associative address mein sirf tag + offset hota hai.

Direct-mapped extreme ko Direct-mapped caches mein aur develop kiya gaya hai; miss-type payoff ka subject Conflict misses vs capacity misses mein hai.

8. Comparator aur "parallel"

Kyun matter karta hai: ek $N$-way set ko $N$ comparators chahiye; $L$ lines ke fully-associative cache ko $L$ comparators chahiye. Hardware ka yeh badhta hua dher associativity ki keemat hai, aur yahi parent note ke tradeoff table ko drive karta hai.

9. Tag bits, assembled

Sections 4–7 ko milao toh parent ki master equation milti hai:

Prerequisite map

Related topics jo inhi foundations par build karte hain: Cache replacement policies, Cache performance metrics, Write policies, Cache coherence, Translation Lookaside Buffer (TLB). Hinglish prefer karte ho? Dekho 5.4.03 Set-associative and fully associative caches (Hinglish).

Equipment checklist

Right side cover karo; kya tum reveal karne se pehle har sawaal answer kar sakte ho?