Noesis
5.3.12 · D5 · HinglishAdvanced Microarchitecture

Question bank — Return address stack

1,769 words8 min read↑ Read in English

5.3.12 · D5 · Hardware › Advanced Microarchitecture › Return address stack

Yeh page ek question bank hai. Har line ek Question ::: Answer reveal hai. Right side cover karo, apna jawab zor se reason ke saath bolo, phir check karo. Agar tumhara reason galat hai — chahe yes/no sahi ho — toh abhi samjha nahi hai.

Shuru karne se pehle, teen simple reminders taaki koi bhi symbol use karne se pehle anchor ho jaye:

Recall Teen moving parts (inhe bolo pehle kuch bhi answer karne se pehle)
  • RAS = ek chhoti si hardware stack of return addresses. Socho plates ki stack: sirf upar wali plate ko touch kar sakte ho.
  • TOS = "Top-Of-Stack" pointer — yeh upar wali plate ko point karta hai (woh jo tum next grab karte).
  • count = kitni plates abhi stack par hain (0 = empty, = full, jahan slots ki number hai). Ek CALL ek plate push karta hai (woh address jahan wapas aana hai). Ek RETURN top plate grab karke remove karta hai taaki pata chale kahan jump karna hai. Yeh parent note ek saansi mein.

True ya false — justify karo

Har jawab mein reason dena zaroori hai, sirf "true/false" nahi chalega.

Ek RAS return instruction ke target ka prediction karta hai, na ki yeh ki return liya jayega ya nahi.
True — ek return (almost) hamesha liya jaata hai, isliye mushkil sawaal hai "jump kahan karna hai?"; RAS iska jawab deta hai, jabki direction prediction conditional branches ke liye taken/not-taken handle karta hai.
Ek BTB akela returns ko RAS jitna achha predict kar sakta hai.
False — ek return instruction (same PC) time ke saath kai alag callers ko return karta hai; BTB ek target per PC store karta hai, isliye woh har baar mispredict karta rehta hai jab caller badalta hai, jabki RAS LIFO nesting track karta hai.
RAS software call stack ke return addresses ko exactly aur hamesha ke liye mirror karta hai.
False — yeh sirf most recent return addresses mirror karta hai; jab real call depth se exceed kar jaaye, toh purane RAS entries evict ho jaate hain chahe software stack unhe abhi bhi hold kar raha ho.
Zyada entries wala RAS hamesha har program par strictly better accuracy deta hai.
Strict sense mein False — jis deepest call chain se program kabhi nahi guzarta, us se zyada entries bakar baith jaati hain; zyada depth sirf un programs ko help karti hai jinki nesting chhote RAS ko overflow kar deti.
CALL par push aur RET par pop kaafi hai; ek plain mod N pointer ko koi extra guard nahi chahiye.
False — ek bare mod N pointer pop-when-empty par silently underflow karta hai aur stale garbage ko "prediction" ke roop mein de deta hai; tumhe ek occupancy count (ya valid bits) chahiye taaki "no prediction" keh sako.
RAS sirf recursive programs ke liye useful hai.
False — ordinary non-recursive call chains (main → init → parse → open → check) already kai return addresses stack karte hain; recursion sirf overflow karna aasaan bana deta hai, lekin RAS flat call trees par bhi apni value prove karta hai.
Agar RAS empty hai aur ek RET fetch hota hai, toh sabse safe behaviour hai phir bhi pop karna aur jo bhi slot mein hai use karna.
False — empty RAS pop karna stale data deta hai aur near-certain misprediction; correct behaviour hai "no prediction" signal karna aur BTB par fall back karna ya stall karna.
RAS overflow karne se turant currently-returning function corrupt ho jaata hai.
False — overflow oldest entry (outermost caller) ko evict karta hai; inner returns abhi bhi correctly predict karte hain, aur misprediction baad mein surface hota hai jab tum evicted outer frame par return karne ki koshish karte ho.

Error pakdo

Har item mein ek hidden flaw ke saath ek claim hai. Flaw batao.

"CALL par hum CALL instruction ka address khud push karte hain."
Galat — hum push karte hain, yaani next instruction ka address; CALL par wapas jaane se woh call hamesha re-execute hoti rahegi.
"Ek return stack ke bottom ko pop karta hai kyunki woh original caller hai."
Galat — ek return top (most recent) entry pop karta hai; LIFO ka matlab hai innermost, latest call pehle match hoti hai, jo exactly waise hai jaise nested calls unwind hoti hain.
"Occupancy counter pop par upar jaata hai aur push par neeche."
Ulta hai — push ek plate add karta hai (count up, par cap), pop ek remove karta hai (count down, 0 par floor).
"Hume C switch jump table ke liye RAS use karni chahiye kyunki yeh ek indirect branch hai."
Galat — ek switch target data (x) par depend karta hai, call/return nesting par nahi, isliye yeh LIFO break karta hai; woh Indirect Branch Prediction ka kaam hai, RAS ka nahi.
"Pipeline flush par hum sirf RAS ko empty kar dete hain aur continue karte hain."
Galat — clear karne se correct outer-frame addresses kho jaate hain; tumhe RAS (TOS aur count dono) ko snapshot par restore karna padega jo mispredicted call se pehle liya gaya tha, speculative recovery ka hissa.
"Ek function pointer ke through indirect jmp ko RAS par push karna chahiye."
Galat — sirf architectural CALL/RET pairs RAS ke saath interact karte hain; ek akela indirect jump ka koi matching return nahi hai, isliye iske push karne se stack real call nesting se desynchronise ho jaata hai.
"Jab RAS full ho, toh agli push simply ignore kar di jaati hai purane data ko protect karne ke liye."
Galat — push ignore nahi hoti; TOS phir bhi advance karta hai aur oldest slot overwrite karta hai (intended eviction). Ignore karne se inner returns mispredict hoti, na ki sirf outermost.

Why wale sawaal

Yahan answers reasoning hain, koi fact nahi.

Returns ke liye stack (LIFO) kyun sahi structure hai, queue (FIFO) kyun nahi?
Kyunki program semantics force karta hai ki returns calls ke reverse order mein ho — last called function pehle return karta hai — isliye most-recently-pushed address pehle pop hona chahiye, jo exactly LIFO hai.
Returns ko special treatment kyun chahiye, jabki woh bas indirect jumps hain?
Kyunki same return PC program ki life mein kai targets map karta hai (har caller ke liye ek); ordinary indirect predictors PC par key karte hain aur conflicting targets dekhte hain, jabki RAS nesting order par key karta hai aur exactly ek sahi jawab dekhta hai.
Occupancy counter par saturate kyun karta hai climb karna continue karne ki jagah?
Kyunki sirf physical slots hain; count ko se aage jaane dena falsely zyada pops allow karta jitne live entries hain, isliye yeh par cap ho jaata hai (wrap already oldest slot evict kar chuka hai).
Do RAS kyun rakhte hain — ek committed aur ek speculative?
Kyunki fetch speculatively aage bhaagta hai aur un calls ke liye push/pop kar sakta hai jo architecturally kabhi execute nahi hue; committed copy true architectural state preserve karti hai taaki flush hone par speculative copy bina corruption ke restore ho sake.
32-entry RAS itna tiny hone ke bawajood near-perfect accuracy kyun deta hai?
Kyunki real programs rarely ~16 se zyada live frames ek saath nest karte hain, isliye 32 slots almost kabhi overflow nahi hote — misprediction cost sirf rare deep chains ya unbalanced recursion mein pay hoti hai.
Overflow "graceful" kyun hai lekin underflow "dangerous" kyun?
Overflow oldest slot overwrite karta hai — ek known, bounded loss jo sirf door ke outer returns ko hurt karta hai; underflow ek aisi slot read karta hai jo kabhi likhi nahi gayi — ek unknown garbage target — isliye guard ise no-prediction treat karta hai.
Deep recursion RAS ko utni hi lambi flat call chain se zyada stress kyun karta hai?
Dono depth consume karte hain, lekin recursion bina kisi intervening return ke hundreds of frames nest kar sakta hai, quickly exceed karke base frames evict kar deta hai jinke returns phir sab mispredict ho jaate hain.

Edge cases

Boundary conditions jo yeh topic quietly invite karta hai.

Call depth exactly ke barabar hai (RAS full, abhi overflow nahi).
Saari entries live hain, count ; har return abhi bhi perfectly predict karta hai. Agli push woh hogi jo oldest evict karegi — exactly full hona theek hai.
Ek RET tab aata hai jab count .
Underflow: koi valid entry exist nahi karti, isliye RAS "no prediction" report karta hai; control BTB par fall back karta hai ya pipeline tab tak stall hoti hai jab tak real target compute na ho jaye.
Tail call / setjmp-longjmp style control flow jo bina matching CALL ke return karta hai.
RAS desynchronise ho jaata hai kyunki ek pop ka koi corresponding push nahi tha; uske baad ke predictions drift karte hain jab tak stack accidentally realign na ho — aisi patterns ek known RAS-accuracy killer hain.
Ek call aur uska return poori tarah mispredicted (galat) speculative path par rehte hain.
Speculative RAS ne ek push phir ek pop kiya jo architecturally kabhi hua hi nahi; flush par speculative RAS pre-call snapshot par roll back ho jaata hai, dono undo ho jaate hain, isliye committed state clean rehta hai.
Overflow, phir utni hi matching returns: kya RAS "recover" karta hai?
Partially — evicted outermost entry hamesha ke liye chali gayi, isliye uska return mispredict karta hai, lekin har inner return jo abhi bhi live slot mein hai correctly predict karta hai; stack un depths ke liye self-heal karta hai jo kabhi overflow nahi hue.
Do consecutive CALLs bina kisi instruction ke beech (chained trampolines).
Har CALL abhi bhi apna push karta hai; RAS sirf do back-to-back pushes dekhta hai, count do se badhta hai, aur LIFO order preserve hota hai — kuch bhi special break nahi hota.