Tournament and TAGE predictors: Visual walkthrough

5.3.10 · D2 · Hardware › Advanced Microarchitecture › Tournament and TAGE predictors

Yeh page ek single result ko pictures mein rebuild karti hai: TAGE kaise decide karta hai ki uski kitni saari tables mein se kaunsi wali branch predict karegi? Hum har symbol ko use karne se pehle earn karenge. End tak tum ek branch ko poori machine mein paper pe trace kar sakoge.

Agar koi word yahaan unexplained lagta hai, toh woh kisi earlier step mein build hota hai. Kuch bhi parent note se assume nahi kiya gaya — hum zero se neeche se shuru karte hain.

Step 1 — Branch kya hoti hai, aur "history" kya hoti hai?

KYA. Branch ek instruction hoti hai jaise if (x > 0) jump. Iska outcome do cheezein mein se ek hoti hai: T (taken, hum jump karte hain) ya NT (not taken, hum fall through karte hain). Branch instruction ke address ko hum iska PC kehte hain (Program Counter — literally code ki kaunsi line par hain hum).

KYUN. Yeh predict karne se pehle ki kya hum branch lenge, humein ek likha hua record chahiye ki recently kya hua. Woh record hai Global History Register (GHR): bits ki ek row, sabse naya daayein taraf, jahan har bit ek past branch outcome hai (1 = T, 0 = NT).

PICTURE. Figure dekho. GHR ek sliding row of bits hai. Jab bhi koi bhi branch resolve hoti hai, hum uska outcome daayein taraf se dhakelke andar daalte hain aur sabse purana bit baayein se gir jaata hai — ek queue ki tarah.

Step 2 — Sirf ek history length kyun nahi? (core tension)

KYA. Humein pick karna hoga ki predictor ko GHR ke kitne bits dene hain. Us number ko $L$ kehte hain (history length).

KYUN. Yeh woh tension hai jo poora design solve karta hai:

Ek loop counter branch (T,T,T,T,NT) ko sirf last few outcomes chahiye — chhota $L$ (maano $L = 4$ ).
Ek correlated branch (if a>0 bahut peeche decide karta hai if b>0 yahan) ko kaafi outcomes peeche chahiye — bada $L$ (maano $L = 32$ ).

Agar tum ek $L$ fix kar do, toh tum doosri tarah ki branch ke liye galat ho jaoge: bahut chhota $L$ underfit karta hai (pattern miss kar deta hai), bahut lamba $L$ dilute karta hai (har history combination cover karne ke liye impossibly many table entries chahiye).

PICTURE. Figure mein wohi branch ek chhote window se aur ek lambe window se feed hoti dikhti hai. Chhota window = kam possible patterns, jaldi seekhta hai, lekin door ke causes se anjaana. Lamba window = cause dekh leta hai, lekin yaad karne ke liye astronomically zyada patterns hain.

Hal: kai predictors rakho, har ek alag $L$ par, aur unhe compete karne do. Yahi geometric ladder hai jo hum aage banate hain. Single-length ancestor ke liye 5.3.8-Two-level-adaptive-predictors bhi dekho.

Step 3 — Tables ki geometric ladder

KYA. TAGE chhoti tables ka ek stack rakhta hai. Sabse neeche base predictor $T_{0}$ hai (koi bhi history nahi use karta — pure PC bias). Uske upar tagged tables $T_{1}, T_{2}, T_{3}, T_{4}$ baithte hain, har ek ko ek history length assign ki gayi jo geometrically badhti hai:

L_{1} = 4, L_{2} = 8, L_{3} = 16, L_{4} = 32

Term by term: $L_{i}$ woh GHR bits ki sankhya hai jo table $i$ dekhta hai. "Geometric" ka matlab hai ki har length apne neeche wale ka ek fixed multiple hai (yahaan $\times 2$ ), fixed addition nahi.

Geometric kyun aur $4, 8, 12, 16$ kyun nahi? Kyunki branch correlations wildly alag distances par rehti hain. Doubling ek bada span cover karta hai ( $4 \to 32$ ) sirf 4 tables ke saath. Agar hum $+ 4$ jodte har baar toh $L = 32$ tak pohonchne ke liye kaafi zyada tables chahiye honge, hardware waste hoga. Doubling broad coverage saste mein deta hai — yahi TAGE mein "Geometric" ka poora point hai.

PICTURE. Ek staircase: $T_{0}$ ground par (koi window nahi), phir har step upar ek window se jhankta hai jo do guna chaudi hai.

Ratio check: $L_{1} r^{3} = 4 \cdot 2^{3} = 32 = L_{4}$ . ✓

Step 4 — Ek table address kaise hoti hai: index aur tag

KYA. Har tagged table $T_{i}$ mein rows hain. Is branch ki row dhundhne ke liye hum ek index compute karte hain — table mein ek address — PC aur GHR ke pehle $L_{i}$ bits ko hashing karke (scramble karke):

index_{i} = hash (PC, GHR [0 : L_{i} - 1])

Kyunki kai alag (PC, history) combos usi row mein scramble ho sakte hain (ek collision), har row ek tag bhi store karti hai: (PC, history) ka ek doosra, independent hash jo hum compare karte hain yeh confirm karne ke liye "haan, yeh row sach mein meri hai."

Tag kyun rakhna? Iske bina, ek hi row mein jaane wali do unrelated branches ek doosre ki prediction silently corrupt kar deti. Tag ek fingerprint hai: agar stored tag ≠ woh fingerprint jo humne abhi compute kiya, toh yeh row hamaari nahi — is table ko matching nahi treat karo.

PICTURE. Ek row = teen fields: tag (fingerprint), ek prediction counter (kaunsi taraf guess karna hai), aur ek useful bit (Step 7 mein build hoga). Index row select karta hai; tag confirm karta hai.

Recall Base

$T_{0}$ mein tag kyun nahi hota? $T_{0}$ sirf PC se index hota hai aur hamesha jawaab deta hai (yeh safety net hai). Yeh kabhi "not match" nahi kar sakta, toh confirm karne ke liye kuch nahi — koi tag nahi chahiye. ::: Kyunki $T_{0}$ ek plain PC-indexed 2-bit counter hai jo HAMESHA ek fallback prediction deta hai, toh yeh decline nahi kar sakta — ek tag (jo ek table ko "not me" kehne deta hai) ka koi matlab nahi hota.

Step 5 — Prediction: sabse lambi matching table jeet jaati hai

KYA. Ab central result. Branch par hum:

Saare indices $index_{0}, \dots, index_{4}$ ek saath (parallel mein) compute karte hain.
Har row padho aur uska stored tag naye compute kiye fingerprint se compare karo.
Un saari tables mein se jinka tag match hota hai, sabse bada $i$ wali table chunte hain (lambi history). Use provider kehte hain.
Provider ke counter ka sign output karo: T agar $ctr \geq 0$ , warna NT.
Agar koi bhi tagged table match nahi karta, toh provider $T_{0}$ hai.

Sabse lamba kyun? Jo lambi history ab bhi is situation ko pehchaan rahi hai, usne apna guess strictly zyada context par condition kiya hai — woh sabse specific witness hai. Ek chhoti table coincidence se match kar sakti hai; ek lambi matching table ne yeh precise sequence dekha hai aur survive kiya hai. Specificity generality ko beat karti hai jab woh apply hoti hai, aur tag guarantee karta hai ki woh apply ho rahi hai.

PICTURE. Chaar tables green (match) ya grey (miss) light up hoti hain. Yahaan $T_{1}$ aur $T_{3}$ match karte hain; $T_{2}, T_{4}$ miss. Arrow $T_{3}$ ko provider crown karta hai kyunki $3 > 1$ .

Step 6 — Edge aur degenerate cases (saare ke saare)

KYA. Chaar situations kabhi surprise nahi karni chahiye. Har ek figure panel mein drawn hai.

(a) Koi table match nahi karti — bilkul naya branch, khaali tables. Provider $= T_{0}$ . Hum phir bhi ek guess emit karte hain (uska PC bias). Kabhi crash nahi.

(b) Sirf $T_{0}$ ne kabhi yeh branch dekhi hai — same as (a): base use karo. Yahi cold start hai jis se har branch shuru karti hai.

(c) Do tables match karti hain, lambi wali galat hai — hum phir bhi lambi wali par trust karte hain (Step 5 rule), lekin Step 7 ka allocation ise fix karne ke liye ek aur lambi table ugayega. Galat hona wahi hai jis se TAGE seekhta hai ki usse kaunsi length chahiye.

(d) Counter exactly boundary par — $ctr = 0$ T predict karta hai (rule hai $\geq 0$ ). Ek counter jo $+ 3$ ya $- 4$ par saturate ho jaata hai woh overflow nahi kar sakta; woh bas pinned rehta hai — isi liye ise saturating counter kehte hain, aur yeh kisi ek fluke ko ek confident branch flip karne se rokta hai.

PICTURE. Chaar mini-panels, har ek case ke liye ek, provider chosen dikhata hai (ya saturated counter jo hilne se mana kar raha hai).

Step 7 — Update: provider ko reward karo, failure par allocate karo, aur useful bit

KYA. Jab sach wala outcome aata hai, TAGE teen kaam karta hai.

Provider counter update karo. Use sach ki taraf le jaao: agar actual = T, toh $ctr \leftarrow min (+ 3, ctr + 1)$ ; agar actual = NT, $ctr \leftarrow max (- 4, ctr - 1)$ . $min / max$ saturation hai — counter kabhi $[- 4, + 3]$ se bahar nahi jaata.
Galat prediction par, allocate karo ek fresh entry kisi lambi table $T_{m}$ mein jahan $m > k$ (provider $T_{k}$ tha). Ek lambi history ko ek mauka do — current length clearly kaafi nahi thi (yahi exactly edge case (c) hai).
Useful bit $u$ . Provider entry par $u = 1$ set karo jab usne sahi predict kiya aur next-shorter matching table galat hoti — proof ki is entry ne apna kaam kiya. Periodically saare $u$ 0 ki taraf reset ho jaate hain; entries jo $u = 0$ par atki hain wahi hain jo hum overwrite karte hain jab jagah chahiye. Yeh victim selection hai: un entries ko bhulo jo kabhi kaam nahi aayein.

Allocate longer kyun, kabhi shorter kyun nahi? Agar ek lambi matching table pehle se galat thi, toh ek chhoti (kam context) ke paas better karne ka koi chance nahi — doosri taraf jaana bekar hai. Growth hi ek aisi direction hai jo information add karti hai.

PICTURE. Baayein: provider counter sach ke outcome ki taraf nudge hota hai (saturating). Daayein: ek misprediction ladder par ek rung upar ek naya tagged entry spawn karta hai.

Ek picture summary

Ek prediction ki poori zindagi: indices compute karo → tags check karo → longest match provide karta hai → uske counter se predict karo → resolution par, update karo / lambi allocate karo / useful bits manage karo. Staircase, fingerprint match, crowned provider, aur feedback arrows sab ek frame mein.

Recall Feynman retelling — plain words mein wapas batao

Socho ek branch witnesses ki ek row ke paas jaati hai. Har witness ne past ki alag kitni raashi dekhi hai: ek ne last 4 events dekhe, doosre ne last 8, phir 16, phir 32. Har witness ke paas ek fingerprint card bhi hai taaki woh honestly keh sake "main actually is exact scene ko pehchaanta hoon" ya chup reh sake. TAGE sirf un witnesses ki sunta hai jo scene ko pehchaan rahe hain, aur un mein se woh maan leta hai jisne sabse zyada history dekhi hai — kyunki us witness ka guess sabse zyada context par built hai. Agar koi scene ko nahi pehchaan raha, toh ek hamesha-maujood ground-floor witness (base predictor) ek rough PC-based hunch deta hai taaki humein hamesha jawaab mile. Jab sach aata hai, hum chosen witness ka confidence sach ki taraf nudge karte hain (lekin kabhi uski limits ke bahar nahi — yahi saturating counter hai). Agar hamare sabse experienced witness ne bhi galti ki, toh hum ek naya witness recruit karte hain aur bhi lambi memory ke saath, kyunki clearly humein aur peeche dekhna tha. Aur jo witnesses kabhi kuch kaam nahi aaye unhe chup-chaap retire kar dete hain seats free karne ke liye. Woh loop — pehchano, sabse lambe par trust karo, sahi karo, failure par lambe badhao — poora engine hai, aur yeh real programs par 95% se zyada accuracy tak pahonch jaata hai. Agla padata: 5.3.11-Branch-target-bufers batata hai kahaan ek taken branch jump karti hai, aur 5.4.2-Speculative-execution dikhata hai ki yeh saari guessing humein kya faayda deti hai.

Related builds: 5.3.9-Gshare-and-local-predictors, 7.2.5-Cache-coherence-and-branch-predictors.