5.4.4
Jab CPU ek single byte maangta hai, cache poora cache line (block) memory se le aata hai—typically 64 bytes. Kyun? Kyunki programs mein spatial locality hoti hai: agar tumhe byte X chahiye, toh probably X+1, X+2... bhi chahiye honge. Tag cache ka tarika hai yeh yaad rakhne ka ki yeh line memory ke kis chunk se aayi hai, taaki woh nanoseconds mein "cache hit ya miss?" ka jawab de sake.
Problem : Main memory CPU se ~100× slower hoti hai. Ek ek byte fetch karna wide data bus (64–128 bits) ko waste karta hai aur locality exploit nahi karta.
Solution : Fixed-size ==cache lines == (ya blocks) transfer karo. Modern x86 64-byte lines use karta hai; ARM often 32 ya 64 bytes use karta hai. Ek slow memory access pay karo, lekin phir 64 bytes cache speed pe serve karo.
Har memory address teen fields mein split hota hai (ek direct-mapped cache ke liye; set-associative "line index" ki jagah "set index" use karta hai):
Address = Tag t bits ∣ Index i bits ∣ Offset b bits
Definition Address Field Definitions
Offset (b andar konsa byte. Agar line size = 2 b b b = 6 Index (i 2 i i Tag (t kaun sa memory block is cache line mein stored hai. Tag = address_bits − i − b
Yeh decomposition kyun?
Offset se hum line fetch karne ke baad requested byte extract kar sakte hain.Index hardware ko batata hai ki kahan dekhna hai (jaise ek hash table bucket).Tag confirm karta hai ki jo humne find kiya woh sahi data hai (collision detection).
Diya hua :
Address space: N
Cache size: C
Line size: L
Associativity: A A = 1
Step 1 : Cache lines ki sankhya = L C
Step 2 : Sets ki sankhya = L ⋅ A C A = 1
Step 3 :
b = log 2 L (offset bits) i = \log_2\left(\frac{C}{L \cdot A}\right) \quad \text{(index/set bits)}
t = N − i − b (tag bits)
Worked example Worked Example 1: 32 KiB Direct-Mapped Cache, 64-byte LinesDiya hua : C = 32 KiB = 32 , 768 B L = 64 A = 1 N = 32 Offset : b = log 2 64 = 6 Kyun? 64 bytes = 2 6
Index : # lines = 32 , 768/64 = 512 = 2 9 i = 9 Kyun? 512 lines matlab ek line select karne ke liye 9 bits chahiye (jaise ek 512-entry array).
Tag : t = 32 − 9 − 6 = 17 Kyun? Baaki bits distinguish karte hain ki 2 17 kaun sa is cache line mein hai.
Summary : Ek 32-bit address ban jata hai [17-bit Tag | 9-bit Index | 6-bit Offset].
Worked example Worked Example 2: Address 0x0012A40Pehle, 0x0012A40 = decimal 76,352. Full 32-bit binary mein:
0000 0000 0000 0001 0010 1010 0100 0000
Ab [17-bit Tag | 9-bit Index | 6-bit Offset] mein split karo upar se:
Tag (top 17 bits): 0 0000 0000 0000 001 = binary 10 = 0x2 (decimal 2).Index (next 9 bits): 0 1010 1001 = binary 010101001 = 0xA9 (decimal 169).Offset (last 6 bits): 00 0000 = 0 → line ka byte 0.
Check : Tag·2 15 2 6 2 ⋅ 32768 + 169 ⋅ 64 + 0 = 65536 + 10816 = 76 , 352
Cache lookup :
Line 169 read karo (index).
Stored tag ko 0x2 se compare karo. Match ho → hit . Na ho → miss .
Hit ho toh offset 0 pe byte return karo.
Har cache line ko chahiye:
Data : L Tag : t Valid bit : 1 bit (kya yeh line initialized hai?).Dirty bit (write-back): 1 bit (kya data modify hua hai?).
Total overhead per line : t + 2
Worked example Worked Example 3: Tag OverheadUpar wale 32 KiB cache ke liye: 512 lines, har ek mein 17-bit tag + 2 status bits = 19 bits per line = 2.375 bytes per line .
Total tag storage : 512 × 2.375 B = 1 , 216
Overhead fraction : 1 , 216/32 , 768 ≈ 3.7%
Yeh kyun matter karta hai : Line size double karna (64→128 bytes) lines ki sankhya aadhi kar deta hai, toh tag overhead ~1.9% tak drop ho jaata hai, lekin same cache size ke liye tumhe fewer lines milti hain.
Common mistake Mistake 1: "Offset select karta hai ki kaun si cache line check karni hai"Kyun sahi lagta hai : Offset address ka part hai, toh shayad line locate karne mein help karta hai?
Fix : Index line select karta hai. Offset us line ke andar ek byte select karta hai. Ise array ki tarah socho: cache[index][offset].
Mnemonic : Index = "kahan dekhna hai", Offset = "dhundh lene ke baad kya grab karna hai".
Common mistake Mistake 2: "Tag bits hamesha har cache ke liye same hote hain"Kyun sahi lagta hai : Tags address ki fixed property lagte hain.
Fix : Tag bits cache size, line size, aur associativity pe depend karte hain. Ek 16 KiB cache mein same line size wale 4 KiB cache se zyada index bits hote hain (kam tag bits).
Steel-man : Tum sahi ho ki tag ka concept universal hai, lekin width design-specific hoti hai.
Common mistake Mistake 3: "Badi cache lines hamesha performance improve karti hain"Kyun sahi lagta hai : Har fetch mein zyada data = behtar spatial locality!
Fix : Ek limit ke baad, tum aisa data fetch kar rahe ho jo kabhi use nahi hoga (wasted bandwidth), aur miss penalty badh jaati hai. Saath hi, kum total lines → zyada conflict misses. Real-world mein: 64-byte ek balance hai; 256-byte lines zyaatar workloads ko harm karengi.
Recall Kisi 12-saal ke bachche ko explain karoSocho tumhara desk (cache) 10 folders (cache lines) rakh sakta hai, aur har folder mein 8 pages (bytes) hain. Tumhare paas ek bada filing cabinet (main memory) hai jisme hazaaron folders hain.
Jab tum folder 237 ka page 5 maangoge, cache sirf page 5 nahi laata—woh poora folder 237 (saare 8 pages) le aata hai. Kyun? Kyunki shayad tumhe aage page 6 aur 7 bhi chahiye honge. Yahi spatial locality hai.
Offset batata hai folder mein kaun sa page chahiye (page 5). Index batata hai desk pe kaun sa slot check karna hai (slot 7). Tag folder pe ek label hai jo kehta hai "yeh cabinet ka folder 237 hai" taaki tum jaano sahi folder mila.
Agar koi folder 450 maange aur woh bhi desk slot 7 pe map hota hai, toh folder 237 ko nikaalna padega (ek conflict ). Bade folders (badi line size) matlab desk pe kam folders samayenge, toh zyada conflicts. Chhote folders matlab tum baar baar cabinet ke chakkar kaatoge. 64 pages per folder zyaatar homework ke liye sweet spot hai.
T ag = T ell me which block, I ndex = I n which slot, O ffset = O n which byte"
High bits se low bits tak: T-I-O (jaise "I/O" ka reverse, lekin memory addressing ke liye).
5.4.01-Cache-fundamentals – caching kyun zaroori hai (locality principles)5.4.02-Direct-mapped-caches – in address fields use karne wali sabse simple cache organization5.4.03-Set-associative-caches – index ban jaata hai "set index", multiple tags per set5.4.05-Cache-miss-types – line size compulsory vs. conflict misses ko kaise affect karta hai5.4.08-Write-policies – write-back caches mein dirty bit ka usage6.2.01-Virtual-memory-pages – page tables mein bhi similar tag-index decomposition hoti hai3.1.04-Spatial-locality – wajah ki cache lines multi-byte hoti hain
#flashcards/hardware
Cache system mein memory address ke teen fields kaun se hote hain? Tag (kaun sa block), Index (kaun si line/set), Offset (line mein kaun sa byte)
Agar cache mein 1024 lines hain aur 32-byte line size hai, toh kitne offset bits? b = log 2 32 = 5
Agar cache mein 1024 lines hain aur 32-byte line size hai, toh kitne index bits? i = log 2 1024 = 10
32-bit address space mein 10 index bits aur 5 offset bits hone par kitne tag bits honge? t = 32 − 10 − 5 = 17
Badi cache lines tag overhead kyun reduce karti hain? Same cache size ke liye kum total lines → store karne ke liye kam tags (har line ke saath zyada data per tag)
Bahut badi cache lines (e.g., 256 bytes) ka kya nuksan hai? Kum total lines → zyada conflict misses; lamba miss penalty; unused data fetch karna bandwidth waste karta hai
"Offset" field kya select karta hai? Cache line ke andar byte (ya word) (line index aur tag se locate hone ke baad)
"Index" field kya select karta hai? Check karne ke liye cache line (ya set, set-associative caches mein)
"Tag" field kya karta hai? Identify karta hai ki is cache line mein kaun sa memory block stored hai (hit/miss detection enable karta hai)
Ek byte ki jagah poora cache line kyun transfer karte hain? Spatial locality exploit karta hai: adjacent bytes jald hi chahiye honge; slow memory access ko multiple bytes pe amortize karta hai
Modern x86 CPUs mein typical cache line size kya hai? 64 bytes
64-byte lines wali 64 KiB direct-mapped cache mein kitni cache lines hongi? 65 , 536/64 = 1024
1024 cache lines ke liye kitne index bits? log 2 1024 = 10
Number of sets C over L times A