Question bank — Cache coherence at scale (directory-based)

Directory ::: Ek hardware table jo, har memory block ke liye, yaad rakhti hai ki kisne cached copy rakhi hai aur woh kis state mein hai — yeh sirf metadata store karti hai, data khud kabhi nahi. Home node (HD) ::: Woh fixed node jo ek memory address ki directory entry ka "owner" hota hai; us address ke liye har request pehle yahan aani chahiye. Sharer ::: Ek cache jo abhi ek block ki read-only copy hold kar raha hai (state Shared). Owner ::: Woh single cache jo ek block ki ek-maatra up-to-date (dirty) copy hold karta hai (state Modified); memory stale hai. Invalidate ::: Ek message jo ek cache ko bolta hai ki woh apni copy phenk de taaki ek writer exclusive access pa sake.

Directory block ke data ki ek copy store karta hai taaki woh reads ko quickly answer kar sake. ::: False. Directory sirf metadata (state + sharer list) rakhti hai. Ek Modified block par fresh data owner ki cache mein hoti hai, isliye directory ko request forward karni padti hai — uske paas khud dene ke liye data hi nahi hota. State Modified mein ek block ko hamesha exactly ek cache hold karta hai. ::: True. Modified ka matlab hai exactly ek owner ke paas exclusive dirty copy hai; agar doosri cache ke paas bhi hoti, to woh alag values rakh sakti thi aur coherence toot jaati. Jab memory Shared state mein hoti hai, to main memory mein jo copy hai woh stale hoti hai. ::: False. Shared copies read-only hoti hain aur memory ke identical hoti hain, isliye memory valid hai. Memory sirf Modified ke under stale hoti hai, jahan owner bina write-back kiye likh sakta hai. Snooping se Directory par jaane se per-request latency kam hoti hai. ::: False. Yeh bandwidth kam karta hai, latency nahi. Ek directory request ko home node tak pahunchna padta hai aur possibly ek owner ko forward kiya jaata hai — extra hops jo har request ko ek single broadcast se slower banate hain. Full-map directory ka size cores ki sankhya par depend karta hai lekin memory ki maatra par nahi. ::: False. Size $M\times (2+N)$ bits hai — yeh dono block count $M$ aur core count $N$ ke saath scale karta hai. Memory double karne se directory double ho jaati hai. Full-map Modified entry mein, aapko phir bhi ek alag owner-ID field ki zaroorat hai. ::: False. Sharer vector mein woh ek set bit hi owner hai. Ek dedicated ${\log }_{2}N$ owner field sirf woh information duplicate karta jo pehle se present hai. Shared block ko write home directory request receive hote hi complete ho sakta hai. ::: False. Home ko pehle har sharer ko invalidate karna hoga aur saare Invalidate-Acks collect karne honge; sirf tab woh write grant kar sakta hai, warna ek purana reader stale value rakh sakta tha.

"Modified block par read miss hone par, home directory memory se data padhta hai aur reply karta hai." ::: Galat — Modified ke under memory stale hoti hai. Home ke paas valid data nahi hota; woh request owner ko forward karta hai, jo data supply karta hai aur write-back karta hai. "Saare sharers ko invalidate karne ke liye, directory har core ko broadcast karke Invalidate bhejti hai." ::: Galat — directory ka poora point hi broadcast avoid karna hai. Yeh sirf unhi cores ko Invalidate bhejti hai jo sharer list mein named hain (typically 1–3), sabhi N ko nahi. "Kyunki sharers read-only hain, writer ko unke acknowledgements ka wait nahi karna padta." ::: Galat — read-only copies mein abhi bhi purana value hota hai. Agar writer unke invalidations complete hone se pehle aage badhta hai, to woh readers stale data serve kar sakte the, jo coherence violate karta. "Distributed directory multi-hop routing hata deta hai kyunki har node sab kuch locally handle karta hai." ::: Galat — distribution routing complexity badhaata hai: ek request ko interconnect traverse karke sahi home slice tak pahunchna pad sakta hai. Yeh single-bottleneck hotspot hataata hai, hops nahi. "Sparse/limited-pointer directories strictly better hain kyunki woh kam memory use karte hain." ::: Galat — woh storage ke badle correctness pressure trade karte hain. Jab $k$ se zyada sharers hote hain, extras evict ho jaate hain ya scheme false (over-broad) invalidations par fall back karti hai, jo performance hurt karta hai. "NUMA example mein, ek address ke low 8 bits home socket choose karte hain." ::: Galat — 256B interleaving ke saath low 8 bits block offset hain (woh ek socket par rehte hain). Socket offset ke upar wale bits se choose hota hai (bits 8–9). "Snooping directory ki tarah per-block sharing state track karta hai." ::: Galat — snooping koi central sharer table nahi rakhta; har cache bus ko dekhti hai aur react karti hai. Woh statelessness hi reason hai ki yeh simple hai lekin kyun use broadcast karna padta hai.

Modified owner read miss par requester ko data aur home ko write-back kyun bhejta hai? ::: Requester ko abhi fresh value chahiye, aur home ko stale memory update karni hai aur state ko Shared par downgrade karna hai — warna memory block ke shared hone ke baad galat rahti. Broadcast traffic ko $O(N^2)$ kyun describe kiya jaata hai jabki directory traffic $O(N)$ hai? ::: $N$ mein se har core miss issue kar sakta hai, aur ek broadcast $N-1$ caches tak pahunchta hai — $N\times (N-1)$. Ek directory har request ko ek home plus uske sharers ko bhejti hai, isliye hum kehte hain per-request cost $O(\text{sharers})$ hai, $O(N)$ nahi. Kya "a handful of sharers" disguise mein sirf $N$ nahi hai — kya saare $N$ cores ek block share nahi kar sakte, directory traffic ko bhi $O(N)$ nahi bana sakte? ::: Worst case mein (saare $N$ ek block padhte hain) ek write saare $N$ ko invalidate karti hai, to ek request $O(N)$ hai — lekin woh ek single write hai, $N\times (N-1)$ traffic nahi. Common case mein sharing degree chhoti rehti hai (1–3) kyunki truly widely-shared read-only data rare hai, isliye directory traffic actual sharers se bounded hai, total core count se nahi jaise broadcast hamesha hota hai. Directory acks ko count kyon karta hai — sirf invalidations bhej ke aage kyon nahi badh jaata? ::: Fire-and-forget guarantee nahi kar sakta ki purane readers ne sach mein apni copies chhod di hain. Har ack ka wait karna hi "koi stale reader write ke baad survive nahi karta" ko provable banata hai. Modern multi-chip systems (EPYC, Graviton) ko snooping ki jagah directories kyun chahiye? ::: Alag chips ko span karne ke liye koi shared bus nahi hai jis par snoop kiya ja sake. Point-to-point directory messages hi physically distinct dies par coherence banaye rakhne ka ek-maatra tarika hai. Memory ko block offset ke upar interleave kyun karte hain, bilkul lowest bits par nahi? ::: Offset ke upar interleaving consecutive blocks ko sockets par spread karta hai (directory load balance karta hai) jabki har block ke bytes ek socket par rakhta hai (spatial locality preserve karta hai). Directory sharers ko exactly track kyon karta hai, sirf count nahi? ::: Write par use specifically unhi caches ko invalidate karna hai jinke paas copies hain. Ek mere count se pata chalta hai kitni hain lekin kaunsi ko message karna hai nahi — jo ek broadcast force karta aur design ko defeat karta.