4.1.9
Intuition The big pictureCache ek choti, fast memory hoti hai jo ek badi, slow main memory ke blocks ki copies rakhti hai.
Organization ek hi sawaal ka jawab deti hai: "Jab main memory block B
Direct-mapped → sirf ek slot (sasta, fast, lekin blocks ek slot ke liye lade).Fully associative → koi bhi slot (flexible, koi conflict nahi, lekin search karna mehenga).n-way set associative → ek chosen set ke andar n slots mein se koi ek (tunable middle ground).
Baaki sab (tag bits, hit logic, conflict misses) isi ek design choice se mechanically aata hai.
Main memory mein, maano, 2 32 2 15 har cache slot ko ek cycle mein check kare — jab tak hum limit na karein ki ek block kahan ja sakta hai.
Organization ek trade-off hai search cost aur flexibility ke beech :
Placement restrict karo → check karne ke liye kam slots → faster & cheaper, lekin zyada collisions.
Free placement do → koi collision nahi, lekin bahut saare slots search karne padte hain.
Hum split ko kabhi memorize nahi karte — hum use derive karte hain.
Definition Building blocks
Memory byte-addressable hai, address width = m
Cache data ko blocks (lines) mein store karta hai, har ek B
Cache mein S sets hain; har set mein E = S ⋅ E
Step 1 — Offset. B b = log 2 B bits (block offset) . Kyun? B log 2 B
Step 2 — Set index. Block ko ek set pe map kiya jaata hai
set = ( block number ) mod S , s = log 2 S bits (index) . Kyun mod S Hum address space ko S Low block-number bits use karna consecutive blocks ko alag-alag sets mein spread karta hai (spatial locality ke liye acha).
Step 3 — Tag. Baaki bache hue high bits identify karte hain ki kaun sa block, jo is set pe map hota hai, actually stored hai:
t = m − s − b bits (tag) .
Maano cache mein total N = S ⋅ E
Organization
E S Placement of block #k
Direct-mapped
E = 1 S = N exactly slot k mod N
n-way set assoc.
E = n S = N / n set k mod S n
Fully associative
E = N S = 1 koi bhi slot (no index bits!)
Intuition Ek picture, do extremes
E = 1 direct-mapped . Index mein sabse zyada bits, tag mein sabse kam. Fastest, sabse zyada conflicts.S = 1 fully associative . Koi index bits nahi (s = 0 har slot ko parallel mein compare karna hoga.Beech mein, E 1 N
Definition Hit/miss procedure
Address ko tag / index / offset mein split karo.
Index use karke ek set select karo (direct: ek single line; fully: wo ek hi set).Parallel mein , address tag ko us set ki har ek E AUR har line ka valid bit check karo.Hit ⇔ koi line hai jisme (valid = 1) AUR (stored tag = address tag). Byte extract karne ke liye offset use karo.Miss ⇔ koi match nahi → memory se block fetch karo, use place karo (agar zaroorat ho toh replacement policy ke hisaab se evict karke).
Kitne tag comparators chahiye = E E = N N
Worked example Example 1 — Field sizes for a direct-mapped cache32-bit address, 16 KiB cache, 64-byte blocks, direct-mapped .
Offset b = log 2 64 = 6 Kyun? 64 bytes per block.
Blocks N = 16 KiB /64 = 16384/64 = 256 S = N = 256
Index s = log 2 256 = 8 Kyun? har set mein ek slot, 256 sets.
Tag t = 32 − 8 − 6 = 18 Kyun? baaki bache bits block identify karte hain.
Split: 18 | 8 | 6 .
Worked example Example 2 — Same cache, 4-way set associative32-bit, 16 KiB, 64-byte blocks, 4-way (E = 4
Offset abhi bhi 6 Kyun? offset sirf B
N = 256 S = N / E = 256/4 = 64 Index s = log 2 64 = 6 Kyun? kam sets ⇒ kam index bits.
Tag t = 32 − 6 − 6 = 20 Kyun? index ne 2 bits lose kiye, toh tag ne gain kiye 2 bits.
Split: 20 | 6 | 6 . Note: zyada associativity ⇒ bade tags, zyada storage overhead .
Worked example Example 3 — Fully associative versionSame 16 KiB / 64-byte, fully associative .
S = 1 ⇒ s = 0 Kyun? har block kahi bhi ja sakta hai; set pre-select nahi kar sakte.Tag t = 32 − 0 − 6 = 26 26 | — | 6 . 256
Worked example Example 4 — Conflict demonstration (the punchline of organization)Direct-mapped, 4 lines, 1 byte blocks. Block numbers ka access pattern: 0 , 4 , 0 , 4 , … k → k mod 4 0 4 0 wo ek doosre ko har baar evict karte hain → 100% miss rate.
Same trace 2-way mein (2 sets, k mod 2 dono abhi bhi set 0 Associativity ne conflict misses khatam kar diye. Isliye ye exist karta hai.
Compulsory (cold): kisi block ka pehli baar reference. Organization se avoid nahi hota.Capacity : cache itni choti hai ki working set nahi aata. Fully associative mein bhi hota hai.Conflict : block evict ho jaata hai kyunki bahut saare blocks ek hi set pe map hote hain , chahe cache mein doosri jagah room ho. Sirf direct-mapped & low-associativity ko ye hota hai. Fully associative mein zero conflict misses.
Common mistake "Zyada associativity matlab hamesha zyada index bits."Kyun sahi lagta hai: associativity "zyada structure" jaisi lagti hai, toh aap expect karte ho zyada addressing bits.
Sach: Fixed total size ke liye, E S = N / E kam hota hai, toh index bits shrink hote hain aur tag bits grow karte hain. Index sets count karta hai, ways nahi.
Common mistake "Fully associative ko tags ki zaroorat nahi kyunki kuch bhi kahi bhi ja sakta hai."Kyun sahi lagta hai: "koi fixed location nahi" matlab "identify karne ko kuch nahi" jaisa lagta hai.
Sach: Bilkul ulta hai — koi index nahi hone se, tag ko poora block number rakhna hota hai , toh tags sabse bade hote hain. Phir bhi aapko identify karna hota hai ki har slot mein kaun sa block hai.
Common mistake "Bade blocks → hamesha kam misses."Kyun sahi lagta hai: bade blocks spatial locality exploit karte hain, neighbors ko bhi le aate hain.
Fix: Bade blocks ka matlab cache mein kam blocks bhi hote hain → zyada conflict/capacity misses aur agar locality poor hai toh zyada bandwidth waste. Ek optimum hota hai.
Common mistake "Direct-mapped toh bas 1-way hai... toh ise replacement policy bhi chahiye."Kyun sahi lagta hai: har doosri organization ko LRU etc. chahiye.
Fix: Direct-mapped mein ek block ka sirf ek hi legal slot hota hai — choose karne ko kuch nahi. Koi replacement policy ki zaroorat nahi. Policies tab hi matter karti hain jab E > 1
Recall Associativity badhane se tag size kyun badhti hai (fixed cache size mein)?Fixed N = S ⋅ E ⇒ ⇒ ⇒ t = m − s − b
Recall EkE E
Recall Fully-associative kaun sa miss type eliminate karta hai, aur kaun sa nahi kar sakta?Conflict misses eliminate karta hai; compulsory aur capacity abhi bhi hote hain.
Recall (Feynman, ek 12-saal ke bacche ko explain karo)Ek coat-check room imagine karo. Direct-mapped : tumhara coat number batata hai ki use exactly kis ek hook pe lagana hai — fast hai, lekin agar do coats ka number same ho, toh ek ko hataana padega. Fully associative : koi bhi hook chalega, toh coats kabhi nahi hataaye jaate, lekin worker ko har hook dekhna padta hai tumhari coat dhundhne ke liye — slow. n-way : room choti shelves mein divided hai; tumhara number ek shelf choose karta hai, aur uspe n n naam hai jo coat pe likha hota hai taaki tum jaano wo sach mein tumhari hai.
Mnemonic Field order yaad rakho"TIO" = T ag–I ndex–O ffset (high→low bits).
Aur associativity rule: "More ways, fewer sets, bigger tags." (M-F-B).
Cache organization kya decide karta hai? Kaun se slot(s) mein ek memory block cache mein reh sakta hai.
Address split, high se low bits? Tag | Index | Offset.
Block offset bits ka formula diya block size B? b = log 2 B
Index bits ka formula diya sets ki sankhya S? s = log 2 S
Tag bits ka formula? t = m − s − b
Direct-mapped (S,E) ke terms mein? E = 1 S = N
Fully associative (S,E) ke terms mein? S = 1 E = N s = 0
n-way set associative: set kaise choose hota hai? set = ( block number ) mod S n
E-way ke liye kitne tag comparators chahiye? Exactly E
Fixed cache size mein, associativity badhne pe tag bits ka kya hota hai? Tag bits increase hote hain (sets/index decrease hote hain).
Kaun si organization ko replacement policy ki zaroorat nahi aur kyun? Direct-mapped — ek block ka sirf ek hi legal slot hota hai, choose karne ko kuch nahi.
Cache misses ke 3 C's? Compulsory (cold), Capacity, Conflict.
Full associativity kaun sa miss type eliminate karta hai? Conflict misses.
Fully associative hardware mein kyun expensive hai? Har access pe N
32-bit, 16KiB, 64B-block, 4-way cache field split? Tag 20 | Index 6 | Offset 6.
Hit ke liye dono kya match karna chahiye? Valid bit = 1 AUR stored tag = address tag.
Cache organization choice
Search cost vs flexibility
