Set-associative and fully associative caches

5.4.3 · Hardware › Memory Hierarchy & Caches

Overview

Humne dekha ki direct-mapped caches mein conflict misses aate hain jab multiple addresses ek hi cache line pe map ho jaate hain. Set-associative caches iss problem ko solve karte hain — har memory block ko multiple possible locations mein jaane ki permission deke — jabki fully associative caches is cheez ko extreme pe le jaate hain jahan block kahin bhi ja sakta hai. Yahi fundamental tradeoff hai: flexibility vs. hardware complexity.

Hume Associativity Ki Zaroorat Kyun Hai?

Set-associative caches tumhe spots ka ek chhota sa choice dete hain. Fully associative caches tumhe kahin bhi park karne dete hain. Zyada choice = kam conflicts, lekin apni car dhundhna zyada time leta hai (zyada comparison hardware chahiye).

Set-Associative Caches

N = 1: direct-mapped
N = 2, 4, 8: common set-associative configurations
N = total cache lines: fully associative

Address Decomposition

Set-associative cache ke liye, address in parts mein split hota hai:

$Address = ⟨ Tag ∣ Set Index ∣ Block Offset ⟩$

$Number of sets S = \frac{C}{B \times N}$

$Set index bits = lo g_{2} (S)$

Yeh formula kyun?

Total cache lines = $C / B$
Har set mein $N$ lines hoti hain
Toh number of sets = $(C / B) / N = C / (B \times N)$

Set index bits select karte hain ki kaunsi set search karni hai. Tag bits alag-alag blocks ko identify karti hain jo ek hi set pe map hote hain. Block offset block ke andar byte select karta hai (direct-mapped jaisa hi).

Step 1: Number of sets calculate karo $S = \frac{64 KB}{64 B \times 4} = \frac{65536}{256} = 256 sets$

65536 kyun? $64 KB = 64 \times 1024 = 65536$ bytes.

Step 2: Bit fields calculate karo

Block offset: $lo g_{2} (64) = 6$ bits
Set index: $lo g_{2} (256) = 8$ bits
Tag: $32 - 8 - 6 = 18$ bits

Index ke liye 8 bits kyun? Hume 256 sets ko distinguish karna hai, aur $2^{8} = 256$ .

Step 3: Example address lookup Address: 0x001A4C0 (ek 32-bit address, 7 hex digits = 28 bits ke roop mein dikhaya gaya hai; top 4 hex digits 0 hain).

Poora 32-bit binary:

0000 0000 0001 1010 0100 1100 0000

(Yaani $0 x 001 A 4 C 0 = 0000000000000001101001001100000 0_{2}$ .)

Tag(18) | Index(8) | Offset(6) mein partition karo, MSB se LSB tak:

Tag    (18 bits): 00 0000 0000 0001 1010   = 0x01A
Index  (8 bits):  0100 1100                 = 0x4C = 76
Offset (6 bits):  00 0000                    = 0

Check: $18 + 8 + 6 = 32$ bits ✓, aur 8-bit index $0100110 0_{2} = 64 + 8 + 4 = 76$ .

Block set 76 pe map hoti hai. Cache controller set 76 ke saare 4 tag fields ko parallel mein check karta hai match dhundne ke liye.

Set-Associative Lookup Kaise Kaam Karta Hai

Set index extract karo address se → set select karo
Tag compare karo set ke saare N tags ke against simultaneously (parallel comparators)
Agar koi bhi tag match kare aur valid bit = 1 → HIT, us line ka data use karo
Agar koi match nahi → MISS, memory se fetch karo, us set ki kisi bhi line mein place karo (replacement policy decide karta hai kaunsi line mein)

Fully Associative Caches

Address Decomposition

$Address = ⟨ Tag ∣ Block Offset ⟩$

Koi index field nahi! Tag itna bada hona chahiye ki block ko uniquely identify kar sake.

$Number of lines = \frac{C}{B}$

$Tag bits = A - lo g_{2} (B)$

$Offset bits = lo g_{2} (B)$

Index kyun nahi? Kyunki block kahin bhi ja sakta hai, hum cache ko sets mein partition nahi karte. Hum sab kuch search karte hain.

Lines: $16384/64 = 256$ lines

Bit fields:

Offset: $lo g_{2} (64) = 6$ bits
Tag: $32 - 6 = 26$ bits
Index: 0 bits

Har access pe, hardware 26-bit tag ko saare 256 tags ke against parallel mein compare karta hai. Iske liye 256 comparators chahiye — expensive hai lekin conflict misses bilkul khatam ho jaate hain.

Comparison: Direct-Mapped vs. Set-Associative vs. Fully Associative

Property	Direct-Mapped	N-Way Set-Assoc	Fully Associative
Ways per set	1	N	C/B (saari lines)
Number of sets	C/B	C/(B×N)	1
Comparators	1	N	C/B
Hit time	Sabse fast	Medium	Sabse slow
Miss rate	Sabse zyada (conflicts)	Medium	Sabse kam
Hardware cost	Sabse sasta	Medium	Sabse expensive
Use case	L1 caches (speed critical)	L2, L3 caches	TLBs, chhote caches

Zyaatar real caches 2-way, 4-way, ya 8-way set-associative use karte hain — yeh ek sweet spot hai.

Replacement Policies

Jab set-associative ya fully associative cache mein miss hota hai, hume decide karna hota hai ki kaunsi line evict karni hai. Direct-mapped caches mein koi choice nahi hoti (sirf ek hi possible location hoti hai), lekin associative caches ko ek replacement policy chahiye.

LRU practice mein sabse better perform karta hai lekin access order track karna padta hai (jaise counter bits ya "age matrix" se). 2-way ke liye, LRU ko 1 bit per set chahiye. 4-way ke liye, aur complex logic chahiye.

Ek miss aata hai. Hum Way 1 ko evict karte hain (least recently used). Way 1 ko naye data se fill karne ke baad, yeh most recently used ban jaata hai: [Way 1, Way 2, Way 0, Way 3]

Order track kyun karte hain? LRU temporal locality ka faayda uthata hai: agar ek block haal mein use hua hai, toh wo jald hi phir use hone ki sambhavna hai. "Coldest" block ko evict karna future misses ko minimize karta hai.

Derivation: Cache Configuration Math

Chalo cache parameters ke beech relationship derive karte hain.

Diya gaya hai:

Total cache size: $C$ bytes
Block size: $B$ bytes
Associativity: $N$ ways

Total cache lines: $L = \frac{C}{B}$

Kyun? Har line ek block of $B$ bytes store karti hai. Agar hamare paas $C$ total bytes hain, toh hum $C / B$ blocks fit kar sakte hain.

Number of sets: $S = \frac{L}{N} = \frac{C}{B \cdot N}$

Kyun? Hamare paas $L$ total lines hain, jo evenly $N$ -way sets mein distribute hoti hain. Har set ko $N$ lines milti hain, toh hume $L / N$ sets chahiye.

Set index bits: $i = lo g_{2} (S) = lo g_{2} (\frac{C}{B \cdot N})$

Kyun? Hume itne bits chahiye jo $S$ sets mein se ek ko uniquely identify kar sakein. $lo g_{2} (S)$ bits $2^{l o g_{2} (S)} = S$ values represent kar sakti hain.

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

jahan $A$ address width hai, $b = lo g_{2} (B)$ block offset bits hain.

Kyun? Address tag, index, aur offset mein partition hota hai. Jo index aur offset ke liye use nahi hota, woh tag ban jaata hai.

Common Mistakes

Kyun aisa lagta hai: "4-way" sunke "4 times" jaisa lagta hai.

Fix: Associativity describe karta hai ki block kitni jagahon pe ja sakta hai, na ki total capacity. Ek 64 KB direct-mapped cache aur ek 64 KB 4-way set-associative cache ka total storage same hota hai. 4-way version mein sirf kam sets hote hain (har ek mein 4 lines), jabki direct-mapped mein zyada sets hote hain (har ek mein 1 line).

Kyun aisa lagta hai: "Koi bhi block kahin bhi ja sakta hai" unlimited lagta hai.

Fix: Fully associative mein bhi $C / B$ total lines hi hoti hain. Iska bas matlab hai koi index bits nahi — block un mein se kisi bhi line mein ja sakta hai. Jab full hoti hai, tab bhi eviction hoti hai.

Kyun aisa lagta hai: Software wali sequential soch ki wajah se.

Fix: Hardware parallel comparators use karta hai. Saare N tag comparisons simultaneously hote hain. Hit time thoda badh sakta hai multiplexer delay ki wajah se, lekin yeh N mein linear nahi hota.

Worked Problem: 2-Way Set-Associative Cache Design Karna

Problem: Ek 2-way set-associative cache design karo jisme 32 KB capacity ho, 128-byte blocks hon, aur system 32-bit addresses use karta ho. Calculate karo:

Number of sets
Bit field sizes
Total tag storage bits

Solution:

Step 1: Number of sets $S = \frac{C}{B \cdot N} = \frac{32768}{128 \cdot 2} = \frac{32768}{256} = 128 sets$

2 se divide kyun? Hamare paas 2 ways hain, toh lines 2 groups mein split ho jaati hain per set.

Step 2: Bit fields

Block offset: $lo g_{2} (128) = 7$ bits
Set index: $lo g_{2} (128) = 7$ bits
Tag: $32 - 7 - 7 = 18$ bits

Step 3: Total tag storage

Har line ko chahiye: 18-bit tag + 1 valid bit + 1 dirty bit (agar write-back hai) = 20 bits overhead
Total lines: $32768/128 = 256$ lines
Total overhead: $256 \times 20 = 5120$ bits = 640 bytes

Additional: Har set mein 2 lines hain, toh hume 1 LRU bit per set chahiye (track karne ke liye ki kaunsa way least recent hai). Total: 128 sets × 1 bit = 128 bits = 16 bytes.

Active Recall

Recall Ek 12-saal ke bacche ko samjhao

Imagine karo tumhare paas ek chhoti notebook hai jisme tum homework problems ke answers likh lete ho, taaki har baar bade textbook mein dhundna na pade.

Direct-mapped notebook mein, har problem ko ek specific page number pe jaana hi padega (jaise problem 10 hamesha page 10 pe). Agar alag-alag chapters ke do problem 10 hain, toh woh ek hi page ke liye ladte hain — ek likhte ho toh doosra mita dete ho. Bahut irritating!

Set-associative notebook mein, tum apni notebook ko sections mein divide karte ho. Problem 10 abhi bhi ek specific section pe map hoti hai, lekin us section ke andar 2 ya 4 khaali slots hote hain. Toh do alag problem 10 dono fit ho jaate hain bina ek doosre ko mitaye. Bahut better!

Fully associative notebook mein, problem 10 kisi bhi page pe ja sakti hai jo tumhe chahiye. Koi ladai nahi! Lekin ab dhundna ki tumne problem 10 kahan likhi thi zyada time leta hai — tumhe har page scan karna padta hai. Yahi tradeoff hai: zyada flexibility lekin search karna slower.

Mnemonic

Connections

Direct-mapped caches — N=1 ka special case
Cache replacement policies — LRU, FIFO, Random eviction victim choose karne ke liye
Cache coherence — aur complexity jab multiple cores ke paas associative caches hon
Translation Lookaside Buffer (TLB) — aksar fully associative, chhota, fast
Conflict misses vs capacity misses — associativity conflict misses reduce karta hai
Cache performance metrics — associativity badhne se hit time badhta hai, miss rate ghatta hai
Write policies — write-back aur write-through saare associativity types mein same tarah kaam karte hain

#flashcards/hardware

"4-way set-associative" ka kya matlab hai? :: Ek cache jahan har set mein 4 lines (ways) hoti hain, aur ek memory block ek specific set pe map hoti hai lekin us set ke andar kisi bhi 4 lines mein ja sakti hai.

C bytes, B-byte blocks, N-way associativity wale cache mein kitne sets hote hain?

S = C / (B × N)

Fully associative cache mein kitne set index bits hote hain?

Zero. Address sirf Tag | Offset hota hai kyunki koi bhi block kahin bhi ja sakta hai.

Zyada associativity ka main advantage kya hai?

Lower conflict miss rate, kyunki zyada blocks ek saath coexist kar sakte hain jo ek hi index pe map hote hain.

Zyada associativity ka main disadvantage kya hai?

Slower hit time aur zyada hardware cost (zyada comparators, multiplexers, power).

Set-associative caches mein parallel comparators kyun use karte hain?

Saare N ways ko ek hi cycle mein simultaneously check karne ke liye, sequential search delay se bachne ke liye.

Kaunsi replacement policy track karti hai ki kaunsi line sabse kam recently access ki gayi?

LRU (Least Recently Used).

2-way set-associative cache mein LRU ke liye per set kitne bits chahiye?

1 bit per set (2 ways mein se kaunsa least recent hai, yeh track karne ke liye).

Agar 64 KB cache mein 64-byte blocks hain aur yeh 8-way set-associative hai, toh kitne sets hain?

65536 / (64 × 8) = 65536 / 512 = 128 sets.

Fully associative ka miss rate sabse low kyun hota hai?

Koi conflict misses nahi — koi bhi block kahin bhi ja sakta hai, toh sirf capacity aur compulsory misses hote hain.

Set-associative cache mein teen address fields kaunse hote hain?

Tag, Set Index, Block Offset.

TLBs aksar fully associative kyun hote hain?

Woh chhote hote hain (kam entries), toh parallel comparison affordable hai, aur fully associative critical address translations ke liye miss rate minimize karta hai.