Question bank — Tomasulo's algorithm

False — yeh sirf false name dependencies (WAR/WAW) hata ta hai. Ek true read-after-write dependency real data flow hai, isliye consumer ko genuinely producer ke CDB broadcast ka wait karna padta hai.

False — woh kisi bhi order mein execute ho sakte hain. Ordering sirf register ke final tag par enforce hoti hai: jis writer ka naam register ke tag mein abhi hai, sirf uska broadcast accept hoga; doosra simply ignore ho jaata hai.

False — RS snapshot Issue par freeze ho jaata hai. Yeh specific tag ka wait karta hai jo usne copy kiya tha, isliye baad mein register ka tag overwrite karna (WAR situation) use disturb nahi kar sakta.

False — yeh sab ko broadcast karta hai. Har RS aur register simultaneously sunta hai, kyunki Issue time par hardware nahi jaanta ke kitni future instructions yeh value use karengi.

True — RS us cycle mein broadcast value latch karta hai aur apna Q field clear karta hai, isliye dono Q fields NULL hone par yeh immediately start ho sakta hai bina ek fresh clock edge ka "notice" lene ke liye wait kiye.

False — classic algorithm mein koi ROB nahi hota; yeh results directly registers mein commit karta hai. ROB ek baad ka addition hai jo precise exceptions aur speculation recovery bhi deta hai.

False — scoreboarding ek write ko tab tak stall karta hai jab tak earlier reads finish na ho jaayein (WAR stall); Tomasulo WAR ko renaming se completely eliminate karta hai, isliye writers kabhi earlier readers ka wait nahi karte.

False — full RS pool ek structural hazard hai; instruction Issue par stall karti hai aur in-order front end ko block karti hai jab tak koi slot free na ho.

True — NULL tag matlab "koi producer pending nahi," isliye RegFile[r].value live value hai. Non-NULL tag matlab register ek IOU hai jo us RS ka wait kar raha hai.

R1 broadcast sirf tab accept karta hai jab R1 ka tag abhi bhi Mult1 ke barabar ho. Agar kisi baad ki instruction ne R1 ko retag kar diya (say Add2 ko), toh R1 Mult1 ka result ignore karta hai — woh purani write rename ho chuki thi.

Yeh ready nahi hai. Execution ke liye dono Qj = NULL aur Qk = NULL chahiye; ek missing operand (Qk abhi bhi Add1 ka wait kar raha hai) ise block karta hai, kyunki B ke bina A + B compute nahi kar sakte.

Sirf tab jab source register ka tag NULL ho. Agar source abhi pending hai (tag set hai), toh hum value nahi balki tag copy karte hain — value abhi exist hi nahi karti, isliye hum IOU record karte hain.

Yeh unit latency mein kuch nahi badalta (ek DIV abhi bhi apne 40 cycles lega). Yeh throughput badhata hai independent instructions ko overlap karne aur early start karne deke, ILP extract karka.

Destination tag RS ka apna naam hai (jaise Add1), register naam nahi. Wahi RS naam precisely woh temporary rename hai jo poori machine mein register naam ki jagah leta hai.

Ek single CDB ek cycle mein ek broadcast channel hai — yeh ek structural bottleneck hai. Agar do units ek saath finish karein, ek ko wait karna padta hai, isliye real designs mein multiple CDBs ho sakte hain.

Kyunki producer abhi bhi mid-execution mein ho sakta hai. Tag ek forward-looking IOU hai jo consumer ko abhi issue hone deta hai aur baad mein CDB se value lene deta hai, pipeline ko flowing rakhta hai.

Issue time par yeh unknown hota hai ke kisi result ke future consumers kitne honge (zero bhi ho sakte hain, paanch bhi). Broadcast-and-latch scheme ek consumer list per producer maintain karne se simpler hai.

Do instructions same register ko target kar sakti hain; sirf latest writer ko win karna chahiye. Tag check register ko sirf us broadcast ko accept karne deta hai jiska RS naam woh abhi hold karta hai, stale write ko silently discard karta hai.

Agar SUB ke operands ready hain aur use apna RS milta hai, toh shared register par uski false (name) dependency rename ho jaati hai, isliye kuch bhi use earlier MUL ka wait karne par majboor nahi karta. Yeh out-of-order execution hai action mein.

Baad wala writer ek fresh RS tag paata hai, aur earlier reader ne ya toh value ya purana producing tag Issue par freeze kar liya tha. Reader register ke tag ke change hone se immune hai, isliye writer ko wait nahi karna padta.

Kyunki dependencies tag matching se resolve hoti hain, register names se nahi. RS naam ek pending value ko uniquely identify karta hai, jo chote architectural register set se kahin zyada distinct names deta hai — yahi hardware register renaming hai.

Dono Q fields NULL set ho jaate hain aur dono V fields Issue par load ho jaate hain, isliye instruction immediately execute-ready hai aur agle hi cycle mein start ho sakti hai — bilkul bhi CDB wait nahi.

Broadcast harmless hai — yeh kahin bhi latch nahi hota. Yeh tab hota hai jab koi write poori tarah rename ho gayi ho (dead result), isliye value correctly discard ho jaati hai.

Dono Qj aur Qk wahi same tag hold karte hain; jab CDB us par broadcast karta hai, dono fields match karte hain aur same cycle mein fill ho jaate hain, phir execution normally proceed karta hai.

Classic non-speculative algorithm mein yeh arise hi nahi ho sakta, kyunki tags sirf live producers par set hote hain aur broadcast par clear hote hain; deadlock-free progress is baat par rely karta hai ke har set tag eventually broadcast kare.

Haan — har write ko apne Issue par ek distinct RS tag milta hai, aur har reader ne apne Issue moment par valid tag freeze kar liya tha, isliye read/write ordering purely tag snapshots se preserve hoti hai.

Finished result wait karta hai (shared bus ke liye arbitration); uska RS busy rehta hai jab tak woh CDB nahi jeet leta, jo dependent instructions mein delay kar sakta hai — single-CDB design ki yeh ek real structural limit hai.