Step 1 — Offset. To pick a byte inside a block of B bytes we need
b=log2B bits (block offset).Why?B distinct bytes require log2B bits to index them.
Step 2 — Set index. The block is mapped to a set by
set=(block number)modS,s=log2S bits (index).Why mod S? We chop the address space into S groups; identical low bits → same set. Using the low block-number bits spreads consecutive blocks across different sets (good for spatial locality).
Step 3 — Tag. The remaining high bits identify which of the many blocks that map to this set is actually stored:
t=m−s−b bits (tag).
Recall Why does increasing associativity increase tag size (fixed cache size)?
Fixed N=S⋅E. More ways ⇒ fewer sets ⇒ fewer index bits ⇒ since t=m−s−b, tag grows.
Recall How many tag comparators does an
E-way cache need?
Exactly E — one per line in a set, all compared in parallel.
Recall Which miss type does fully-associative eliminate, and which it cannot?
Eliminates conflict misses; compulsory and capacity still occur.
Recall (Feynman, explain to a 12-year-old)
Imagine a coat-check room. Direct-mapped: your coat number tells you the one exact hook it must hang on — fast, but if two coats share a number, one gets bumped. Fully associative: any hook is fine, so coats never get bumped, but the worker must look at every hook to find yours — slow. n-way: the room is split into small shelves; your number picks a shelf, and there are n hooks on it — a couple of friends can share a shelf without bumping, and the worker only checks n hooks. The tag is the name written on the coat so you know it's really yours.
Cache organization ka matlab sirf ek sawaal hai: jab main memory ka koi block cache me laana hai, toh wo cache ke kaun se slot me ja sakta hai. Direct-mapped me block ka sirf ek hi fixed ghar hota hai (block number mod total slots) — bahut fast aur sasta, par agar do alag blocks ka same slot ban jaye toh wo ek-doosre ko baar-baar nikaalte rehte hain, isko conflict miss bolte hain. Fully associative me block kahin bhi ja sakta hai — koi conflict nahi, par har slot ko check karna padta hai, isliye hardware mehnga (har line pe ek comparator). n-way beech ka raasta hai: pehle index se ek set choose karo, fir us set ke andar n slots me se kisi ek me daal do.
Address ko hum teen hisson me todte hain: Tag | Index | Offset. Offset block ke andar ka byte choose karta hai (b = log2 BlockSize). Index set choose karta hai (s = log2 NumberOfSets). Tag baaki bache bits, jo batata hai us slot me actually kaunsa block pada hai. Yaad rakho: cache size fix ho aur associativity badhao, toh sets kam ho jate hain, index bits kam, aur tag bits badh jaate hain — yeh exam me sabse common trick hai.
Hit kab hota hai? Jab us set ki kisi line ka valid bit = 1 ho aur uska stored tag address ke tag se match kare. Direct-mapped me replacement policy ki zaroorat hi nahi, kyunki sirf ek hi jagah hai — choice hi nahi. Yeh saari cheezein bas ek hi design decision (S aur E choose karna) se nikalti hain, isliMumbaiE ratne ki zaroorat nahi, derive kar lo.
