5.4.2 · D5 · HinglishMemory Hierarchy & Caches
Question bank — Cache organization (direct-mapped)
5.4.2 · D5· Hardware › Memory Hierarchy & Caches › Cache organization (direct-mapped)
Shuru karne se pehle, parent note ka address split yaad karo: ek address Tag (kaun sa memory block), Index (kaun si cache line), aur Block Offset (block ke andar kaun sa byte) mein divide hota hai. High bits → low bits = T → I → C.
True or false — justify karo
Direct-mapped ka matlab hai ki har memory block sirf ek cache line mein reh sakta hai.
True — index bits ek single line force karte hain; koi choice nahi hai, unlike set-associative jahan ek block apne set ki kisi bhi way mein ja sakta hai (dekho Set-Associative Caches).
Direct-mapped ka matlab hai ki ek cache line kabhi bhi sirf ek specific memory block hold kar sakti hai.
False — ek line kai saare blocks ki target hoti hai (saare blocks jo wo index share karte hain). Tag decide karta hai ki un competing blocks mein se abhi kaun sa resident hai.
Same index wale do addresses hamesha cache mein collide karte hain.
False — agar unka tag bhi same hai to wo same block hain aur dono hit karte hain; collision tabhi hota hai jab index match kare lekin tag differ kare.
Same tag wale do addresses hamesha same cache line mein map hote hain.
False — same tag lekin different index bits alag lines mein jaate hain; akela tag kuch locate nahi karta.
Index bits ki sankhya badhana hamesha conflict misses kam karta hai.
Practice mein False — index bits se pinned hain, isliye cache badhaaye ya blocks chhhote kiye bina inhe add nahi kar sakte (jo spatial locality hurt karta hai).
Ek cold (compulsory) miss cache ko bada karke avoid ki ja sakti hai.
False — kisi block ka pehla-ever reference size chahे kuch bhi ho, miss karega; sirf prefetching ya bade blocks (spatial locality) ise hide kar sakte hain.
Agar valid bit 0 hai, to tag comparison result koi mayne nahi rakhta.
True — ek invalid line mein garbage hota hai; hit condition hai , isliye miss force karta hai tag pe trust karne se pehle hi.
Block size double karne se, jab cache size fixed ho, cache lines ki sankhya kam hoti hai.
True — lines cache size block size, isliye bade blocks matlab kam lines, hence kam index bits aur zyada tag bits.
Do consecutive byte addresses hamesha same cache line mein land karte hain.
False — ye generally karte hain, lekin do blocks ki boundary par (offset se tak roll over hota hai) index increment hota hai, unhe alag lines mein bhejta hai.
Line mein stored tag redundant hai kyunki index line identify kar leta hai.
False — index line identify karta hai, lekin kai blocks wo index share karte hain; tag hi single cheez hai jo distinguish karti hai ki un blocks mein se kaun present hai.
Error dhundho
"Data dhundhne ke liye, pehle match ke liye saare tags search karo, phir us line par jaao."
Wrong order — index bits seedha line par jaate hain (koi search nahi), phir ek single tag compare confirm karta hai. Saare tags search karna associative-cache behaviour hai, direct-mapped nahi.
"Block offset batata hai ki tum kaun sa memory block access kar rahe ho."
Offset ek block ke andar byte select karta hai; block khud tag+index se identify hota hai (block address). Offset kabhi affect nahi karta ki kaun si line choose hogi.
"Conflict miss ka matlab hai cache ki space khatam ho gayi."
Nahi — conflict misses mostly-empty cache mein bhi hoti hain; problem ye hai ki do live blocks same line par map ho rahe hain, total capacity exhaust nahi hui hai.
"Address 0x0D aur 0x4D alag hain, isliye ye alag cache lines use karte hain."
Ye same index bits share karte hain (parent ki 16-byte cache mein dono index 3), isliye ye same line ke liye ladte hain; sirf unke tags differ karte hain, thrashing cause karte hue.
"Storage overhead sirf tag bits hai, isliye ye negligible hai."
Valid bit bhi count karna padega (aur Cache Write Policies ke koi bhi dirty/coherence bits); overhead hai (tag + valid + …) data bits par, jo blocks chhhote hone par badhta hai.
"Kyunki direct-mapped modulo use karta hai, block line par map hota hai."
Modulo wrap karta hai — block , isliye ye line 0 par map hota hai, block 0 se collide karta hua. Yahi wrap-around hai exactly kyun tags exist karte hain.
"Agar ek line ka tag match karta hai, to ye automatically hit hai."
Tabhi, jab valid bit bhi 1 ho — ek freshly powered-up cache mein invalid lines mein matching-looking garbage tags ho sakte hain, jo phir bhi miss hone chahiye.
Why questions
Index middle bits se kyun aata hai, high bits se nahi?
Middle (block-address low) bits consecutive blocks ke through stream karte waqt sabse zyada change hote hain, isliye ye nearby blocks ko alag lines mein spread karte hain, usable lines maximize karte aur conflicts reduce karte hain.
Offset lowest bits se kyun liya jaata hai?
Ek block ke andar consecutive bytes sirf apne lowest bits mein differ karte hain; low bits ko offset ke roop mein use karna bytes ko ek block ke andar cleanly index karta hai ke zariye.
Direct-mapped set-associative se per access faster kyun hai?
Ise ek jaani-hui line par exactly ek tag comparison chahiye (no multi-way search), isliye koi comparator array ya multiplexer nahi hai winner pick karne ke liye — trade-off dekho Set-Associative Caches mein.
Ek program perfectly-sized working set ke saath bhi thrash kyun kar sakta hai?
Agar do hot addresses ek index share karte hain, to direct-mapping unhe ek line mein force karta hai; ye har access par ek doosre ko evict karte hain, bhaahje total capacity kaafi ho.
Tag ko index bits bhi store karne ki zaroorat kyun nahi?
Tum index pehle se jaante ho (tumne ise line tak pohonchne ke liye use kiya), isliye ise dobara store karna redundant hoga; tag ko sirf block fully identify karne ke liye index ke upar ke bits chahiye.
Cache Replacement Policies jaise LRU pure direct-mapped cache ke liye irrelevant kyun hain?
Har block ka exactly ek legal line hai, isliye conflict par sirf ek possible victim hai — kya evict karna hai ye "choose" karne ke liye koi policy ki zaroorat nahi.
Edge cases
Power-on ke baad kisi bhi block ka pehla access kya hota hai?
Har line mein hai, isliye tag compare skip ho jaata hai aur ye tag value chahe kuch bhi ho, compulsory (cold) miss hai; block fetch hota hai aur 1 set ho jaata hai.
Agar block size poori cache size ke barabar ho (ek line, )?
Exactly ek line hai; har block usi par map hota hai, isliye cache ek single-block buffer tak degenerate ho jaati hai aur koi bhi do distinct blocks thrash karte hain — index ke paas 0 bits hain.
Agar block size 1 byte ho ()?
Koi offset field nahi hai; har byte apna block hai, isliye tum spatial-locality prefetching kho dete ho aur har byte per maximum tag overhead pay karte ho.
Agar poora address sirf index+offset ho aur zero tag bits hon?
Iska matlab hai cache poore address space jaisi badi hai, isliye koi bhi do blocks kabhi collide nahi karte — tag comparison trivially hamesha-true ho jaata hai aur usse omit kiya ja sakta hai.
Parent ki 16-byte/4-byte cache mein Address 0x2F phir 0x30 — same line?
Nahi — 0x2F, index 3 ke block ka offset 3 hai; 0x30 next block (index 0) mein roll karta hai, isliye index change ho jaata hai aur adjacent hone ke bawajood ye alag lines mein land karte hain.
Ek line flush/invalidate karna data touch kiye bina kya change karta hai?
Valid bit 0 clear ho jaata hai, isliye agla access miss hota hai aur refetch karta hai; stale data bytes physically present rehte hain lekin ignore kiye jaate hain kyunki hit ko gate karta hai.
Agar cache size aadhi kar do lekin block size same rakho, address split mein kya shift hota hai?
Index ek bit khota hai (aadhi lines), aur wo bit upar tag mein move ho jaati hai, isliye tags ek bit badhte hain aur zyada blocks ab har line share karte hain — impact dekho Cache Performance Metrics mein.
Recall One-line self-test
Agar koi kahe "same index, isliye miss," tumhara instant correction kya hai? Correction ::: "Same index sirf ek potential collision setup karta hai; ye miss tabhi hai jab tags differ karein (aur ye hit hai agar tags match karein aur line valid ho)."