Cache organization (direct-mapped): Visual walkthrough

5.4.2 · D2 · Hardware › Memory Hierarchy & Caches › Cache organization (direct-mapped)

Shuru karne se pehle, ek word jo hum baar baar use karenge:

Step 1 — Address ko bits ki ek row ke roop mein rakhna

KYA. Koi bhi address lo aur use $m$ bits ki horizontal strip ke roop mein likho, most-significant bit ("sabse badi" bit, sabse zyada worth wali) left par, least-significant right par.

KYUN. Cache jo bhi karta hai woh hai "yeh bit group pakdo, baaki ignore karo." Strip ki picture se hum literally point kar sakte hain ki kaun se bits kaun sa kaam karte hain. Hum binary choose karte hain (decimal nahi) kyunki number ko bit-groups mein kaatna exactly wahi hai jaise ruler ko powers of two mein kaatna — aur caches powers of two se bane hote hain.

PICTURE. Neeche ki strip dekho. Abhi yeh $m$ bits ka ek undivided ribbon hai. Is page par hamara poora kaam hai isme do vertical cut lines kheenchna.

Step 2 — Pehla cut: Block Offset

KYA. Sabse right ke $b$ bits kaat do. Is piece ko block offset kaho. Agar ek block $2^{b}$ bytes rakhta hai, toh yeh $b$ bits ek block ke andar har byte ka naam lene ke liye exactly kaafi hain.

KYUN. Memory byte-addressable hoti hai, lekin ek akela byte wire par le jaana trip ko waste karta hai. Isliye cache hamesha $2^{b}$ bytes ka poora block fetch karta hai. Jab block aa jaata hai, tab bhi humein ek byte point karna hota hai uske andar — yahi offset ka kaam hai. Aur $b$ bits $0$ se $2^{b} - 1$ tak count karte hain, jo exactly block ke "byte 0 … byte last" hai. Perfect fit, koi waste nahi.

PICTURE. Figure mein sabse right wala hissa (yellow) peel off hota dikhai deta hai. Dekho ki offset ki value $0, 1, 2, \dots, 2^{b} - 1$ cycle hoti hai aur phir 0 par reset hoti hai jab hum next block mein jaate hain — jaise odometer ka last digit.

Step 3 — Jo bacha woh hai Block Address

KYA. Offset cut ke left mein sab kuch — upar ke $m - b$ bits — block address hai. Yeh woh address hai jisme "kaun sa byte" wala part hata diya gaya ho.

KYUN. Ek hi block ke do bytes ke sab high bits same hote hain; woh sirf offset mein differ karte hain. Toh agar hum offset erase kar dein, ek block ke saare $2^{b}$ bytes ek number mein collapse ho jaate hain. Woh single number wahi hai jiske baare mein cache sochta hai jab woh decide karta hai ki block kahan store karna hai. Yeh Step 4 se pehle banana tha kyunki placement rule poore blocks par kaam karta hai, kabhi single bytes par nahi.

PICTURE. Figure odometer analogy dikhata hai: last $b$ digits kaatna wahi hai jaise $2^{b}$ se integer-divide karna. Bytes 0–3 sab block 0 par map hoti hain; bytes 4–7 sab block 1 par.

Step 4 — Doosra cut: Index (parking spot)

KYA. Block address mein se, agle $c$ bits kaat do (block address ke low $c$ bits). Ise index kaho. $2^{c}$ lines wale cache mein, yeh $c$ bits exactly ek line ka naam lete hain.

KYUN — aur kyun yeh tool. Cache mein sirf $2^{c}$ lines hain lekin memory mein kahin zyada blocks hain. Humein ek aisi rule chahiye jo har block ko ek definite line par bheje, bina search ke. Rule hai $mod 2^{c}$ : block $0 \to$ line $0$ , block $1 \to$ line $1$ , …, block $2^{c} - 1 \to$ last line, phir block $2^{c}$ wapas line $0$ par. Hum modulo choose karte hain (say, "free line dhundo" nahi) exactly isliye kyunki modulo ek direct, instantaneous answer deta hai — isliye naam hai direct-mapped. Aur $mod 2^{c}$ hardware mein free hai: yeh bas "low $c$ bits rakho" hai, koi divider nahi chahiye.

PICTURE. Figure block numbers ko $2^{c}$ lines ki ring ke around wrap karta hai jaise clock face par numbers hain. Blocks $0, 2^{c}, 2 \cdot 2^{c}, \dots$ sab line 0 par land karte hain — woh stack up hote hain ek hi spot par. Yeh stacking yaad rakho; Step 5 isi ko suljhaane ke liye hai.

Step 5 — Jo bacha woh hai Tag (naam ka badge)

KYA. Sabse upar ke $m - c - b$ bits, dono cuts ke baad jo bacha, woh tag hai.

KYUN. Step 4 ne bataya tha: bahut saare alag blocks ek hi line par land karte hain. Line 0 abhi block 0 hold kar sakti hai, ya block $2^{c}$ , ya block $2 \cdot 2^{c}$ — woh sirf index se alag nahi ho sakte. Tag leftover high bits hain, aur woh high bits exactly wahi hain jo un colliding blocks ko alag banate hain. Toh tag ek naam ka badge hai: ek baar index hamein ek line par le jaata hai, stored tag ko hamare address ke tag se compare karna bata deta hai "kya yahan jo block rakha hai woh sach mein mera hai?"

PICTURE. Strip ab poori tarah teen coloured pieces mein cut ho gayi hai: red Tag | blue Index | yellow Offset. Neeche do addresses same index ke saath lekin alag tags ke saath ek hi line par ladte dikhai dete hain.

Step 6 — Pieces ko kaam mein lagana: hit/miss decision

KYA. Index se ek line choose karo; us line ka valid bit check karo (kya yahan kuch real store hai?); agar valid hai, stored tag ko apne tag se compare karo.

KYUN. Yahi do tarike hain jisme answer "no" ho sakta hai. Ya toh line kabhi fill nahi hui (valid bit = 0 → ek cold miss), ya woh kisi aur ka block hold kar rahi hai (tag mismatch → ek conflict miss). Sirf tab jab line valid hai aur tags match karte hain woh data hamara hai — ek hit. Ek line lookup, ek tag comparison. Koi loops nahi. Woh single comparison hi direct-mapped ki set-associative caches ke upar poori speed advantage hai.

PICTURE. Ek flow: address → split → line par seedha jaao → do checks → HIT (green) ya MISS (red).

Step 7 — Edge aur degenerate cases (reader ko kabhi stranded mat chodo)

KYA & KYUN. Chalte hain machine ko uski extremes par test karte hain taaki koi bhi scenario tumhe surprise na kare.

Zero bits ka Offset ( $b = 0$ , block size $= 1$ byte). Tab koi yellow slice nahi; har block ek single byte hai. Offset "wrap" kabhi nahi hota kyunki block mein sirf ek byte hai. Legal hai, lekin tum bandwidth ka faida kho dete ho neighbours fetch karne ka — spatial locality ke liye bura (dekho Cache Performance Metrics).
Zero bits ka Index ( $c = 0$ , exactly ek line). Koi blue slice nahi; har block ek hi single line par map hota hai. Tag poora block address ban jaata hai. Yeh ultimate collision machine hai — do alternating addresses hamesha ke liye thrash karte hain.
Zero bits ka Tag ( $m - c - b = 0$ ). Koi red slice nahi; index+offset milke har address ko uniquely name kar dete hain, toh koi bhi do blocks kabhi collide nahi karte. Matlab cache utna bada hai jitni memory — bekar hai, lekin ek valid limit hai.
Power-on par Valid bit = 0. Cache run karne se pehle, har line invalid hoti hai, isliye kisi bhi block ka pehla touch hamesha cold miss hoga. Isliye hum valid bit tag se pehle compare karte hain — ek unfilled line mein leftover garbage bits ho sakte hain jo accidentally "match" kar sakti hain.

PICTURE. Teen mini-strips $b = 0$ , $c = 0$ , aur all-collide case ek saath dikhate hain.

Ek-picture summary

Neeche poora walkthrough compress kiya gaya hai: ek 8-bit address ( $m = 8$ , $b = 2$ , $c = 2$ ) enter hota hai, Tag | Index | Offset mein cut hota hai, index ek line par jump karta hai, valid bit aur tag decide karte hain hit vs miss, aur offset final byte nikalta hai. Arrows ek baar trace karo aur tum poora scheme re-derive kar loge.

Recall Feynman retelling — plain words mein bolo

Ek memory address bas ek number hai jo ek giant ruler par ek byte ka naam rakhta hai. Main use binary mein bits ke ribbon ke roop mein likhta hoon. Main do cuts karta hoon. Sabse right wala cut kuch bits peel off karta hai — offset — jo bas kehta hai "bytes ke carton ke andar kaun sa byte," kyunki main hamesha bytes carton mein (block mein) fetch karta hoon. Agla cut index peel karta hai — yeh ek parking-spot number hai jo mujhe blocks ko parking spots ki ring ke around count karke aur wrap karke milta hai; yeh mujhe exactly ek line batata hai, koi searching nahi. Jo bits upar baache woh tag hain — ek naam ka badge, kyunki bahut saare alag blocks ek hi parking spot share karne par majboor hain, aur badge hi eklauta cheez hai jo unhe alag karta hai. Yeh answer dene ke liye ki "kya tumhara data mere paas hai?": main index se seedha us ek line par jaata hoon, uska valid bit check karta hoon (kya yahan kuch real hai?), aur agar hai toh uska stored badge mere badge se compare karta hoon. Dono theek → hit, aur offset mera byte pakad leta hai. Badge galat → conflict miss. Kabhi fill nahi hua → cold miss. Ek walk, ek comparison, done.

Recall Quick self-test

Kaun sa address piece hit ya miss hone par kabhi effect nahi karta? ::: Block offset — yeh sirf ek pehle se locate ho chuke block ke andar ek byte select karta hai. Index ke liye modulo natural tool kyun hai? ::: Kyunki "block number mod number-of-lines" blocks ko lines ke around bhejta hai aur wrap karta hai — ek direct, search-free placement — aur hardware mein $2^{c}$ se mod bas "low $c$ bits rakho" hai. $m = 8$ , $b = 2$ , $c = 2$ ke saath, kitne tag bits? ::: $8 - 2 - 2 = 4$ tag bits. Do addresses ek index share karte hain lekin tag mein differ karte hain — agar tum unhe alternate karo toh kya hoga? ::: Woh thrash karte hain: har access doosre ko evict karta hai, isliye har access ek conflict miss hai.

Dekho bhi: Cache Write Policies · Cache Replacement Policies · Cache Performance Metrics · Set-Associative Caches