Set-associative and fully associative caches: Visual walkthrough

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

Yeh page set-associative cache ka poora idea bilkul zero se build karta hai. Hum sirf "memory ek lambi numbered boxes ki list hai" se shuru karenge aur end mein us exact formula tak pahunchenge jo parent note mein likha hai:

$S = \frac{C}{B \times N}$

Har symbol earn kiya jayega — pehle ek picture ki tarah draw hoga — tab formula mein aayega. Agar aapne pehle kabhi cache nahi dekha, line ek se shuru karo aur chalte raho.

Pehle yeh dekhna helpful rahega: Direct-mapped caches. Hum usi ke upar build karte hain.

Step 1 — Memory numbered boxes ki ek strip hai

KYA HAI. Main memory ek lambi row hai byte-sized boxes ki. Har box ka ek address hota hai — sirf uska position number, 0 se ginke.

KYU HAI. Yeh poochhe jaane se pehle ki "address 76 cache mein kahan jayega?", hume yeh agree karna hoga ki address hai kya. Yeh koi mystery nahi hai: yeh ek bahut lambi row mein box ka seat number hai.

PICTURE. Figure mein sabse upar ki strip main memory hai. Box 0 baayi taraf hai; numbers daayein taraf badhte hain. Ek highlighted box woh byte hai jo hum chahte hain.

Is page ke sabhi examples mein hum $A = 32$ bits use karte hain, to $2^{32}$ possible addresses hain — lagbhag 4 billion boxes.

Step 2 — Hum kabhi ek byte nahi move karte, hum poora block move karte hain

KYA HAI. Memory ek byte at a time copy nahi hoti. Yeh fixed-size chunks mein copy hoti hai jise blocks kehte hain. Ek block $B$ consecutive bytes hota hai jo hamesha saath chalte hain.

KYU HAI. Do kaaranon se. Hardware data ko bursts mein move karta hai, isliye 64 bytes grab karna lagbhag utna hi cost karta hai jitna 1 grab karna. Aur programs ka tendency hota hai ki woh neighbouring bytes ko ek doosre ke baad jaldi use karein (spatial locality), isliye neighbours ko abhi grab karna worth hai.

PICTURE. Step 1 ki strip ab $B$ boxes ke groups mein fence ki gayi hai. Har fence-group ek block hai. Jis byte ka hum chahte hain uska address naturally split hota hai "kaunsa block?" aur "us block ke andar kaunsa byte?" mein.

$lo g_{2}$ kyun aur kuch aur kyun nahi? Kyunki har bit yeh double kar deta hai ki aap kitni cheezein name kar sakte ho: $1$ bit $2$ cheezein name karta hai, $2$ bits $4$ name karte hain, ... $b$ bits $2^{b}$ name karte hain. Exactly $B$ boxes name karne ke liye aap us doubling ko invert karte ho — aur "ise $b$ baar double karo" ka inverse $lo g_{2}$ hai.

Step 3 — Cache lines ki ek choti shelf hai

KYA HAI. Cache ek choti shelf hai. Shelf par har slot exactly ek block hold karta hai aur ise line kehte hain. Agar cache total $C$ bytes hold karta hai aur har block $B$ bytes ka hai, to lines ki sankhya hai:

$L = \frac{C}{B}$

KYU HAI. Ek line purposely block-shaped hoti hai — yeh wahi exact container hai jisme ek block drop hota hai. Total bytes count karo, bytes-per-block se divide karo, aur aapko pata chalega kitne blocks fit hote hain. Pizza share karne se zyada subtle kuch nahi.

PICTURE. Upar lambi memory strip; neeche choti cache shelf. Shelf mein memory blocks se kaafi kam slots hain — yahi poora reason hai ki hume ek rule chahiye ki kaunsa block kahan jaata hai.

$C$ = total cache size in bytes.
$B$ = block size in bytes (wahi $B$ jaise Step 2 mein).
$L$ = lines ki sankhya = shelf par block-shaped slots ki sankhya.

Example: $64 KB$ cache with $64$ -byte blocks mein $L = 65536/64 = 1024$ lines hain.

Step 4 — Direct-mapped: ek forced home (aur yeh kyun hurt karta hai)

KYA HAI. Sabse simple rule: block number $mod L$ us ek aur sirf ek line ko deta hai jo block use kar sakta hai. Yeh ek direct-mapped cache hai.

PEHLE DARD KYUN DIKHAYEIN. Hume fix karne se pehle problem ko feel karna hoga. Jab do hot blocks dono ek hi line pe map hote hain, woh forever "evict tag" khelne lagte hain — har ek doosre ko bahar nikalta hai — chahe shelf ka baaki hissa khaali pada rahe. Yeh repeated eviction ek conflict miss hai (dekhein Conflict misses vs capacity misses).

PICTURE. Do coral arrows do alag memory blocks se dono ek hi single line par land karte hain. Uske beside mint lines khaali hain — wasted. Woh waste hi dushman hai.

Step 5 — Har block ko homes ka ek chota set do

KYA HAI. Ek forced home ke bajay, lines ko $N$ lines ke sets mein group karo. Ek block phir bhi ek specific set pe map hota hai, lekin us set ke andar yeh $N$ lines mein se kisi bhi mein reh sakta hai. $N$ associativity hai (number of "ways").

KYU HAI. Choice hi cure hai. $N$ slots choose karne ke option se, do colliding blocks dono resident reh sakte hain — woh tabhi ladte hain jab koi teesra block usi set chahta ho. Humne ek rigid single home ko ek chote apartment block ke saath trade kiya.

PICTURE. Step 3 ki shelf ab sets mein bracket ki gayi hai. Har set $N$ lines ka ek chota group hai. Do pehle-colliding coral blocks ab usi set ki do alag lines mein khushi se baithe hain.

Step 6 — Sets count karo: central formula

KYA HAI. Hamare paas total $L$ lines hain, aur hum unhe $N$ karke ek set mein bundle karte hain. To sets ki sankhya $L$ divided by $N$ hai. Step 3 ka $L = C / B$ substitute karo:

$S = \frac{L}{N} = \frac{C}{B \times N}$

YEH the result kyun hai. Set-associative cache address karne ke baare mein sab kuch $S$ se nikalta hai. Yeh parent note ka headline formula hai — aur ab isme har letter woh picture hai jo aap pehle se dekh chuke ho:

$C$ = total cache bytes (puri shelf, Step 3).
$B$ = block bytes (ek fence-group, Step 2).
$N$ = ways per set (apartment ka size, Step 5).
$S$ = number of sets (kitne apartment blocks hain).

PICTURE. Division literally dikhaya gaya: $L$ lines height $N$ ke stacks mein flow karti hain; stacks count karo — woh count $S$ hai.

Sanity checks (dono extremes Step 4 aur 8 se agree karni chahiye):

$N = 1 \Rightarrow S = L$ → utne sets jinme lines hain → ek line per set → direct-mapped. ✓
$N = L \Rightarrow S = 1$ → ek single set jo sab kuch hold karta hai → fully associative. ✓

Step 7 — Address ko Tag / Index / Offset mein kato

KYA HAI. Address ab teen fields mein slice hoti hai, lowest bits se highest tak:

$⟨ t bits Tag ∣ i bits Set Index ∣ b bits Offset ⟩$

with

$b = lo g_{2} (B), i = lo g_{2} (S), t = A - i - b$

HAR FIELD KYU EXIST KARTI HAI — inhe right-to-left padho, jis order mein yeh sawaalon ka jawaab deti hain:

Offset ( $b$ bits, Step 2 se): block ke andar kaunsa byte?
Index ( $i$ bits): kaunsa set search karun? Hume $S$ sets mein se ek ko name karna hai, aur $lo g_{2} (S)$ bits exactly $S$ cheezein name karti hain — wahi doubling logic jaise Step 2 mein.
Tag ( $t$ bits): un sabhi blocks mein se jo yeh set share karte hain, kaun sa main hun? Offset aur index ke baad jo bhi bits bachi hain — woh hai $A - i - b$ .

PICTURE. Ek single 32-bit address bar, teen pastel bands mein coloured, har band apne kaam aur bit count ke saath labelled.

Step 8 — Extreme case: fully associative (koi index nahi)

KYA HAI. $N$ ko $L$ tak poori tarah push karo. Tab $S = L / N = 1$ : ek single set jo har line hold karta hai. Sirf ek set hone se choose karne ko kuch nahi — isliye index field gayab ho jaata hai:

$⟨ A - b bits Tag ∣ b bits Offset ⟩$

INDEX KYUN GAYAB HOTA HAI. Index bits sirf ek set pick karne ke liye exist karte hain. $S = 1$ ke saath pick karne ko kuch nahi hota — $i = lo g_{2} (1) = 0$ bits. Woh bits tag mein absorb ho jaati hain, jo ab poori memory mein block identify karna hai, isliye yeh $t = A - b$ tak grow kar jaata hai.

PICTURE. Step 7 ka teen-band address bar collapse hota hai: index band zero width tak shrink ho jaata hai aur tag band usse fill karne ke liye swell ho jaata hai. Ek block-arrow har line ki taraf point karta hai — yeh kahin bhi reh sakta hai.

Step 9 — Block dhundhna: parallel comparison aur do edge results

KYA HAI. Choose kiye gaye set ke andar, hardware saare $N$ tags ko side by side rakhta hai aur unhe address ke tag se usi clock cycle mein compare karta hai, $N$ alag comparators use karke. Ek line tabhi match count hoti hai jab uska stored tag address tag se equal ho aur uska valid bit 1 ho.

PARALLEL KYUN, EK-EK KARKE KYUN NAHI. $N$ tags ko sequence mein check karna hit time ko $N$ se multiply kar dega — jo speed ko khatam kar dega jiske liye humne cache banaya. Isliye hum hardware mein pay karte hain (N comparators) taaki time flat rahe. Woh trade — zyada silicon usi speed ke liye — associativity ki asli cost hai.

Do outcomes (dono cases covered):

HIT: exactly ek tag valid = 1 ke saath match karta hai → us line ke bytes offset par grab karo. Fast.
MISS: koi tag match nahi karta (ya matching line invalid hai) → block memory se fetch karo. Agar set full hai, ek replacement policy (LRU, FIFO, random) decide karta hai kaunsi line evict karni hai.

Degenerate detail: ek cold cache par har valid bit 0 hota hai, isliye har access MISS hoti hai chahe associativity kuch bhi ho — ek compulsory miss, jise koi bhi ways prevent nahi kar sakti.

PICTURE. Set 76 apne 4 tags ke saath jo 4 comparators ko feed karte hain ek OR gate mein: koi bhi TRUE → HIT light up; sab FALSE → MISS light up.

Ek-picture summary

Upar sab kuch, ek canvas par: upar address bar → offset byte pick karta hai, index set pick karta hai, tag $N$ comparators ke saath race karta hai → HIT ya MISS → aur master formula $S = C / (B N)$ sab kuch ek saath bind karta hai, direct-mapped ( $N = 1$ ) aur fully associative ( $N = L$ ) dial ke do ends ke roop mein.

Recall Feynman retelling — apne simple words mein wapas bolo

Memory numbered boxes ki ek lambi row hai. Hum ise fixed chunks mein copy karte hain jise blocks kehte hain, $B$ bytes har ek — isliye kisi bhi address ke bottom $lo g_{2} B$ bits sirf yeh batate hain chunk ke andar kaunsa byte. Cache ek choti shelf hai block-shaped slots ki jise lines kehte hain; $C / B$ hain unki. Ek rigid "har block ke liye ek hi ghar" rule (direct-mapped) do hot blocks ko ek slot ke upar ladhata hai jabki shelf khaali baithi rehti hai — ek conflict miss. Isliye hum lines ko $N$ ke sets mein bundle karte hain, aur ek block apne set ki kisi bhi line mein baith sakta hai. $L$ lines ko $N$ -at-a-time bundle karo aur aapko $S = C / (B N)$ sets milte hain — woh ek formula jo sab kuch chalata hai. Address tab teen taraf split hota hai: offset (kaunsa byte), index (kaunsa $S$ sets mein se, $lo g_{2} S$ bits chahiye), tag (jo bacha woh, set share karne wale blocks ko alag karne ke liye). Data dhundhne ke liye hum indexed set par jump karte hain aur saare $N$ tags ko $N$ comparators se ek clock tick mein race karte hain; ek valid bit ke saath match HIT hai, warna MISS aur hum kisi ko replacement policy se evict karte hain. $N$ ko 1 tak giraao aur yeh phir direct-mapped hai; usse $L$ tak uthao aur ek giant set hai bina index ke — fully associative, koi conflicts nahi, lekin har line ke liye ek comparator.

Recall

N-way cache of size C with block size B mein sets ki sankhya ::: $S = C / (B \times N)$ Fully associative cache mein index field kyun gayab ho jaata hai ::: Kyunki $S = 1$ hai, aur $lo g_{2} (1) = 0$ index bits ki zaroorat hai — choose karne ko kuch nahi. HIT ke liye do conditions ::: Stored tag address tag se match kare AUR us line ka valid bit 1 ho. Associativity badhana kya cost karta hai, aur yeh kya nahi kharidta ::: Zyada comparators (area/power) cost hote hain; storage capacity add nahi hoti. Ek cache jo almost khaali hai phir bhi thrash karti hai — kyun ::: Conflict misses choice (mapping) ki kami se aate hain, space ki kami se nahi.

See also: Cache replacement policies · Conflict misses vs capacity misses · Write policies · Cache coherence · Cache performance metrics · 5.4.03 Set-associative and fully associative caches (Hinglish)