Noesis
5.3.9 · D5 · HinglishAdvanced Microarchitecture

Question bank — Branch target buffer (BTB)

2,398 words11 min read↑ Read in English

5.3.9 · D5 · Hardware › Advanced Microarchitecture › Branch target buffer (BTB)

Shuru karne se pehle vocabulary reminders, taaki koi symbol samjhe bina na rahe. Yeh padhte waqt Figure 1 dekho — woh poora lookup draw karta hai:

  • PC = program counter = us instruction ka address jo hum abhi fetch karne wale hain.
  • PC+4 = agla sequential address (instructions yahan 4 bytes apart hain), yaani "seedha chalte raho."
  • Index = PC ke lower bits jo BTB ki kaun si row (slot) mein dekhna hai yeh decide karte hain — table mein ek fast, direct address (Figure 1 mein amber arrow dekho).
  • Tag = us row ke andar stored PC ke upper bits, jo current PC ke upper bits se compare kiye jaate hain yeh confirm karne ke liye ki "yeh row sach mein meri branch ki hai, kisi doosri ki nahi jo same row mein aayi."
  • Aliasing = do alag branch PCs jinke lower bits (index) identical hain, toh woh ek hi row ke liye ladte hain — ek doosre ko overwrite karta hai. Tag comparison yeh pakad leta hai aur wrong jump ki jagah miss report karta hai.
  • I-Cache = Instruction Cache, woh fast memory jisse fetch stage actual instruction bytes padhti hai. Ise BTB ke saath parallel mein padha jaata hai: jab I-Cache bytes fetch kar raha hota hai, BTB decide karta hai agla address kya fetch karna hai.
  • Hit / Miss = kya row ka tag match hua (hit) ya nahi (miss).
  • Flush = pipeline se galat-fetch hue instructions ko bahar fenkna, ek control hazard penalty.
  • Direction = yes/no jawab "kya yeh branch taken hai?" — branch predictor ki zimmedari.
  • Target = taken hone par jump karne ka address — BTB ki zimmedari.
Figure — Branch target buffer (BTB)

Figure 2 mein do units (BTB aur predictor) alag-alag boxes mein dikhaye gaye hain jo dono PC se fed hain, aur Figure 3 woh fetch-cycle timeline hai jisko neeche ke zyaadatar timing traps refer karte hain.

Figure — Branch target buffer (BTB)
Figure — Branch target buffer (BTB)

True or false — justify

"Direction vs target" ka split dimag mein rakho — zyaadatar traps usi seam pe hain.

BTB decide karta hai ki branch taken hai ya nahi.
False. BTB sirf target store karta hai (taken hone par kahan jump karna hai); taken/not-taken direction branch predictor se aata hai. Yeh do cooperating units hain (Figure 2), ek nahi.
BTB miss hamesha harmless hoti hai.
False. Yeh tabhi harmless hai jab instruction sach mein taken branch nahi thi. Miss par hum PC+4 assume karte hain; agar woh sach mein taken branch thi, toh decode baad mein correct karta hai aur hum flush penalty bharte hain.
BTB mein tag matching correctness ko affect karta hai, na sirf speed ko.
Correctness ke liye false, speed ke liye true. Tag check alias par galat branch ko reject karke correctness guarantee karta hai; iske bina hum ek stale target par jump kar dete. Yeh sirf performance cost karta hai (ek miss), correctness kabhi nahi.
Agar branch predictor "not taken" kehta hai, toh BTB target is cycle mein ignore ho jaata hai.
True. BTB hit hone par bhi, "not taken" prediction ka matlab hai hum PC+4 fetch karte hain; stored target unused baith raha hota hai jab tak future mein "taken" prediction na aaye.
BTB aur branch prediction sequentially hote hain, pehle prediction.
False. Yeh dono same fetch cycle mein parallel chalte hain (Figure 3) — wahi parallelism hai jo same-cycle redirection possible banata hai.
Ek correctly-predicted taken branch jisme BTB hit ho, uski zero penalty cycles hoti hain.
True (ideal case). Target fetch cycle mein available hota hai, toh agla fetch bina kisi bubble ke seedha target se aata hai.
BTB store karta hai ki instruction branch hai bhi ya nahi.
Effectively true, implicitly. BTB hit ka matlab hai "humne yahan pehle ek taken branch dekhi thi," toh BTB mein presence khud hi "yeh ek branch hai" ka signal hai — ek wajah hai ki ise decode se pehle lookup kiya ja sakta hai.
BTB size double karna hamesha performance improve karta hai.
False. Badi table mein zyada rows hoti hain, toh row select karne wala address decoder aur data carry karne wali wires physically lambi hoti hain, aur tag-compare ko slower array read ka wait karna padta hai — woh extra propagation delay lookup ko single-cycle window ke bahar push kar sakta hai jo fetch stage allow karti hai (Figure 3). Working set se aage, extra capacity hit-rate mein diminishing returns deti hai jabki latency ka cost phir bhi chukana padta hai.
BTB branches ko bilkul decode karne ki zaroorat khatam kar deta hai.
False. Decode phir bhi branch verify karta hai aur real target update ke liye aur BTB misses/mispredictions ke liye compute karta hai; BTB bas humein target ko pehle speculate karne deta hai speculation ke zariye.
Unconditional jump ko bhi branch predictor ki zaroorat hoti hai.
Direction ke liye zyaadatar false. Yeh hamesha taken hota hai, toh direction trivial hai — lekin phir bhi isse BTB (ya decode) ki zaroorat hai yeh jaanne ke liye ki kahan jaana hai, aur indirect jumps ko target prediction bhi chahiye.

Spot the error

Har statement mein ek flaw hai. Use naam do aur woh reasoning dikhao jo ise expose kare.

"BTB hit par hum tag comparison skip kar sakte hain kyunki indexing ne entry already dhoondh li."
Index sirf ek slot narrow down karta hai. Yeh galat kyun hai: index sirf PC ke lower bits hain, aur bahut saare alag PCs wahi same lower bits share karte hain (aliasing, Figure 1), toh ek row abhi kisi doosri branch ka target hold kar sakti hai — tag (upper bits) hi ek cheez hai jo prove karta hai ki yeh is branch ki hai. Skip karo aur tum stale target par jump kar doge.
"Kyunki BTB target cache karta hai, function returns isse perfectly handle hote hain."
Return har baar alag caller ke paas jaata hai. Yeh galat kyun hai: BTB ek branch ke liye ek fixed target store karta hai, lekin kai sites se call ki gayi subroutine kai addresses par return karti hai, toh last time ka cached target almost hamesha galat hoga. Ek stack-shaped structure, RAS, matching caller ko pop karta hai.
"BTB miss ka matlab hai instruction definitely branch nahi hai."
Yeh galat kyun hai: miss sirf kehta hai "abhi koi matching row stored nahi hai" — branch bilkul nayi ho sakti hai (kabhi insert nahi hui) ya aliasing se evict ho gayi ho. Speed ke liye hum assume karte hain not-a-branch, lekin decode baad mein reveal kar sakta hai ki woh branch thi aur flush force kar sakta hai.
"Aliasing galat jump produce karta hai, toh BTB unsafe hai."
Yeh galat kyun hai: aliasing sirf lower index bits collision change karta hai, lekin stored upper tag bits phir bhi alag hain, toh tag comparison fail hota hai → ek miss, galat jump nahi. Cost ek lost speed opportunity hai, kabhi correctness bug nahi.
"95% accurate BTB ke saath, branch penalties basically khatam ho jaate hain."
Yeh galat kyun hai: zero penalty ke liye teen cheezein ek saath sahi honi chahiye — BTB hit, koi aliasing eviction nahi, aur correct direction prediction. Yeh independent failure modes hain, toh inki combined miss probability kisi bhi single 5% figure se zyada hai; penalties bani rehti hain.
"Kyunki BTB next PC feed karta hai, ise I-Cache ke baad padha jaana chahiye."
Yeh galat kyun hai: BTB aur I-Cache dono same PC lete hain aur same cycle mein start karte hain (Figure 3). I-Cache instruction bytes fetch karta hai jabki BTB independently next PC compute karta hai — inhe serialize karna exactly wahi stall wapas la dega jo BTB hatane ke liye exist karta hai.
"BTB branch ke apne PC ko uski payload ke roop mein store karta hai."
Yeh galat kyun hai: PC key hai — iske lower bits index banate hain aur upper bits tag banate hain. Payload woh nayi information honi chahiye jo hum otherwise early nahi pa sakte, yaani target address. Jo PC hum pehle se hold karte hain usse store karna humein kuch nahi batata.

Why questions

Sirf fact nahi, reason do.

BTB ek target decode se pehle predict kyun kar sakta hai?
Kyunki yeh sirf fetch PC se index hota hai (Figure 1), aur ek prior hit already encode karta hai "yahan ek taken branch rehti thi jo wahaan jaati thi" — lookup ke liye koi opcode bits (jo decode chahiye) ki zaroorat nahi hoti.
BTB miss case ko "assume PC+4" optimize karna achha design kyun hai?
Common case non-branch instructions ka hai jo sequentially chalti hain, toh PC+4 default zyaadatar sahi hota hai; sirf rare real-branch misses penalty pay karti hain.
Bada BTB performance ko indefinitely scale kyun nahi karta?
Ek baar jab yeh program ke branch working set ko cover kar le, extra rows mostly idle baithti hain, jabki longer decoder/word-lines propagation delay add karte hain jo lookup ko single-cycle budget ke bahar push kar sakti hai (Figure 3).
Indirect branches ek plain BTB ke liye zyada mushkil kyun hain?
Unka target runtime par vary karta hai (jaise, ek pointer call), toh ek single cached target aksar stale hota hai — unhe ek fixed entry ki jagah specialized indirect-target predictors chahiye.
Direction prediction ko BTB se alag kyun rakha jaata hai?
Yeh dono alag sawaalon ka jawab dete hain (whether vs. where). Fuse karne par kya hota: ek merged table ko, har row mein, ek direction counter aur ek target address dono store karne padte, aur unhe alag events par update karna padta — direction bits har baar branch resolve hone par change hote hain jab taken/not-taken, jabki target tabhi change hota hai jab jump destination khud change ho (rare). Alag update rates aur widths wali do cheezein ek row mein bundle karna un entries par bits waste karta hai jinhe sirf ek field chahiye, aur write logic complicated ho jaata hai jo ab jaanta hai ki kaun sa field ek update touch karta hai. Unhe alag rakhna (Figure 2) har table ko apne events ke hisaab se size aur update karne deta hai, haalaanki kuch designs inhe jaan-boojhkar fuse bhi karte hain.
BTB delay slots ke historical goal ke saath naturally pair kyun karta hai?
Dono ek hi control-hazard bubble ko attack karte hain — delay slots ise ISA mein hide karte hain, BTB ise hardware mein remove karta hai, toh modern designs BTB prefer karte hain aur slot drop kar dete hain.
Same-cycle prediction headline feature kyun hai?
Iske bina, ek correct "taken" prediction bhi tab tak stall karti hai jab tak decode target compute na kare; BTB fetch cycle mein hi target supply karta hai (Figure 3), us 1–2 cycle wait ko zero kar deta hai.

Edge cases

Boundary aur degenerate scenarios — woh wale jo exams ko pasand hain.

Ek branch ki pehli ever execution (cold BTB).
Guaranteed miss → fetch PC+4 → decode corrects → flush + penalty, phir BTB entry likhi jaati hai taaki baad ke runs hit karein.
Do branches jinke PCs same BTB index mein collide karte hain.
Doosra pehle ko overwrite karta hai (Figure 1 mein same row); pehle ko dobara chalane par tag mismatch → miss → penalty. Correctness bani rehti hai, speed girta hai (classic aliasing).
BTB hit lekin predictor "not taken" kehta hai.
Hum correctly PC+4 fetch karte hain aur stored target ignore karte hain; agar branch sach mein taken thi, toh woh predictor misprediction hai, BTB fault nahi.
BTB hit + correct target + wrong direction prediction.
Hum galat path fetch kar sakte hain → flush. Sahi target hone se kuch nahi bachta kyunki direction galat tha — zero penalty ke liye dono sahi hone chahiye.
Ek non-branch instruction jo accidentally kisi branch ke BTB slot ko alias kare.
Hit par tag mismatch (alag PC) miss deta hai → PC+4, jo non-branch ke liye waise bhi sahi hai; koi nuksan nahi.
Ek branch jo almost kabhi taken nahi hoti.
Predictor baar baar "not taken" kehta rehta hai, toh BTB entry, present bhi ho toh, rarely consult hoti hai — target cache hone ka cost kuch nahi lekin fayda bhi kam hota hai.
Deep call stack wala return instruction.
Ek single BTB target almost hamesha galat hota hai kyunki return site change hoti rehti hai; RAS correct caller pop karta hai, toh returns BTB target prediction ko bypass karte hain.
Self-modifying ya freshly loaded code region.
Purani BTB entries stale targets point kar sakti hain; entries invalidate/re-learn karni hoti hain, warna speculation dead addresses follow karta hai (baad mein commit par squash hoti hain).
Recall Poore trap set ka one-line summary

BTB where ka jawab deta hai (target), predictor whether ka jawab deta hai (direction), tag correctness guarantee karta hai aliasing ke baad bhi, aur ek miss ka matlab sirf "straight-line PC+4 assume karo" hota hai.