Tournament and TAGE predictors: Worked examples — Hinglish deep dive

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

Yeh Tournament and TAGE predictors (index 5.3.10) ka hands-on companion hai. Wahan humne machinery banai thi: local aur global component predictors, 2-bit selector, aur tagged tables ki TAGE ladder. Yahan hum us machinery ko drive karte hain — har us situation mein jo aa sakti hai — har counter value, har tie, har empty table, har degenerate input.

Shuru karne se pehle, teen plain-words definitions jo hum poore page use karte hain:

Recall 2-bit saturating counter ka kya matlab hai?

2-bit counter chaar states mein se ek hold karta hai: 00, 01, 10, 11 (numbers 0–3). "Saturating" matlab woh ends par ruk jaata hai — 11 mein 1 add karne par 11 hi rehta hai, 00 se 1 subtract karne par 00 hi rehta hai. Low half (00,01) = ek choice, high half (10,11) = doosri choice. Woh akela bit jo beech cross karte waqt flip hota hai woh decision bit hai.

Recall Tournament predictor mein selector kya decide kar raha hai?

Selector decide karta hai is baar kis component predictor par trust karna hai — T vs NT nahi, balki local-vs-global. 00,01 → predictor 1, 10,11 → predictor 2.

Scenario matrix

Neeche har worked example ko us cell se tag kiya gaya hai jo woh cover karta hai. Matrix mein har distinct behaviour list hai jo yeh topic tumhare saath kar sakta hai.

#	Cell	Kya isko alag banata hai	Example
A	Selector: agree	dono components sahi ya dono galat → koi move nahi	Ex 1
B	Selector: disagree, P1 wins (no cross)	neeche move karo, same half mein raho	Ex 2
C	Selector: saturation edge (both ends)	already `00` ya `11` par, aage move nahi ho sakta	Ex 3
D	Selector: mid-crossing flip	woh move jo actually chosen predictor badal deta hai	Ex 4
E	TAGE: no tag match (cold)	saare tagged tables miss → base T0 provide karta hai	Ex 5
F	TAGE: longest-match wins	kai tags match karte hain, deepest table chunte hain	Ex 6
G	TAGE: misprediction → allocate	provider galat → longer table mein naya entry	Ex 7
H	TAGE: useful-bit gate	jab ek sahi prediction useful set karta / nahi karta	Ex 8
I	Real-world word problem	nested loop, count the history bits needed	Ex 9
J	Exam twist: accuracy algebra	tournament error formula mein numbers plug karo	Ex 10

Do special "degenerate" inputs folded in hain: cold table (empty entry, cell E) aur saturated counter (cell C) — woh do jagah jahan naive update rule "move" karna chahti hai lekin nahi kar sakti.

Tournament worked examples

Woh ek rule jo hum baar baar apply karte hain

Yahan P1 = local predictor, P2 = global predictor. Figure s01 woh picture hai jis par hum har tournament example mein wapas aate hain.

Figure s01 — selector as a 4-point number line. Left par do teal dots (00, 01) matlab "P1 (local) par trust karo"; right par do orange dots (10, 11) matlab "P2 (global) par trust karo". Value 1.5 par dashed plum line mid-crossing hai: woh single akela jagah jahan ek step which predictor chosen hai badal deta hai. Orange arrow (increment) right push karta hai jab P2 uniquely jeetta hai; teal arrow (decrement) left push karta hai jab P1 uniquely jeetta hai; "clamp" end-stops dikhate hain jahan saturation counter ko freeze kar deti hai.

Jab bhi koi example pooche "kya provider badla?", is line par start aur end dots dhundho aur check karo kya woh same colour hain (koi change nahi) ya different colours hain (plum line cross hui).

Forecast: Ek case mein dono sahi, doosre mein dono galat — kya inमें se koi counter move karta hai?

Kaunsa predictor chosen hai? 10 Figure s01 mein ek orange dot hai → dono runs mein P2 (global) use karo. Yeh step kyun? Selector provider ko current value se choose karta hai outcome jaanne se pehle.
Sub-case (a) — dono correct. Local T ✓, Global T ✓ → rule ka teesra case → koi move nahi, sel = 10. Kyun? Koi unique winner nahi ⇒ koi evidence nahi ⇒ freeze.
Sub-case (b) — dono galat. Local T ✗, Global T ✗ → yeh bhi teesra case → koi move nahi, sel = 10. Yeh alag kyun dikhayein? "Both wrong" Cell A ka woh half hai jise bhoolna aasaan hai. Agar dono components saath mein fail karte hain, to na dono mein se kisi ko doosre ke relative blame milna chahiye, isliye selector phir bhi freeze rehna chahiye — move karna ek ko arbitrarily punish karega.

Verify: Dono sub-cases mein value 2 (10) par rehti hai — start aur end same orange dot hain, isliye provider global rehta hai. ✓

Forecast: Hum teal half mein deep start karte hain. P1 jeetta hai. Kya yahan se ek leftward step kabhi teal half chhod sakta hai?

Score karo. Local = NT ✓, Global = T ✗ → P1 uniquely correct. Kyun? Rule ka pehla case exactly hai "P1 correct AND P2 wrong."
Neeche move karo. $sel_{new} = max (0, 0 - 1) = max (0, - 1) = 0 =$ 00. Kyun? Hum winner ko reward karte hain low (teal) half ki taraf drift karke jahan P1 rehta hai — lekin 00 already leftmost teal dot hai, isliye clamp ise hold karta hai. (Yeh reminder bhi hai ki Cell B aur Cell C touch kar sakte hain, lekin yahan point yeh hai ki hum firmly teal half mein rehte hain.)
Kya provider badla? Start = 00 (teal), end = 00 (teal) — Figure s01 mein same colour, plum line kabhi approach nahi ki. Provider P1 (local) rehta hai. Yeh framing kyun? Cell B define hota hai "P1 ko reward karo bina chosen predictor badle." P1 ke apne half mein deep start karna guarantee karta hai ki step confidence ko deepen karta hai flip karne ki jagah — Cell D ka clean opposite.

Verify: $max (0, - 1) = 0$ ; start aur end same teal dot hain, isliye provider unchanged hai aur koi mid-cross nahi hua. ✓

Forecast: Dono selectors ek wall ke against pinned hain aur "winner" unhe aur andar push kar raha hai. Kya inमें se koi move kar sakta hai?

Sub-case (a) — bottom wall. P1 uniquely correct → rule kehta hai decrement: $sel_{new} = max (0, 0 - 1) = 0 =$ 00. max kyun? Counter saturating hai; 0 se neeche koi state nahi, isliye Figure s01 mein left "clamp" end-stop ise hold karta hai.
Sub-case (b) — top wall. P2 uniquely correct → rule kehta hai increment: $sel_{new} = min (3, 3 + 1) = min (3, 4) = 3 =$ 11. min kyun? Symmetric saturation — right clamp end-stop left wale ka mirror hai. 3 se upar koi state nahi.
Dono interpret karo. Har wall par, "winning predictor mein trust already maximum hai"; uske liye zyada evidence bas ise pinned rakhta hai. Yeh kyun matter karta hai? Saturation dono ends par woh hysteresis hai jo oscillation se bachati hai — far edge se ek opposing win instantly provider flip nahi kar sakti.

Verify: (a) $max (0, - 1) = 0$ ; (b) $min (3, 4) = 3$ . Dono walls handle ho gayi, kisi bhi end par wraparound nahi. ✓

Forecast: 01 Figure s01 mein rightmost teal dot hai, plum line se ek step door. Global jeetta hai. Kya step ise cross karta hai?

Score. Global = T ✓, Local = NT ✗ → P2 uniquely correct → increment. Kyun? Rule ka doosra case.
Increment. $sel_{new} = min (3, 1 + 1) = 2 =$ 10. min kyun? Symmetric top saturation; yahan hum uske paas kahin nahi hain.
Figure s01 padhte hain. Start 01 (teal) → end 10 (orange): 1.5 par dashed plum line cross hui. High bit 0→1 flip hua — provider badal gaya local → global. Yeh highlight kyun karein? Sirf ek step each direction mein plum line cross karta hai; baaki steps sirf ek colour ke andar confidence deepen karte hain. Yeh crossing woh exact moment hai jab behaviour visibly change hota hai — Ex 2 se contrast karo, jo ek colour mein raha.

Verify: $min (3, 2) = 2$ ; start dot teal, end dot orange ⇒ colours differ ⇒ provider flip hua. ✓

TAGE worked examples

TAGE ek provider choose karta hai growing history length wali tables mein tag matching karke. Figure s02 ladder draw karta hai: T0 (koi history nahi) bottom par, phir T1, T2, T3 history lengths $4, 8, 16$ bits ke saath. Jis longest table ka tag match karta hai woh jeetta hai.

Figure s02 — TAGE ladder as stacked table rows. Har row ek table, uski history length, aur ek example branch ke liye uska lookup result dikhati hai. Hum tag hit dhundhte hue top-down scan karte hain (left par ink arrow). Yahan T3 (history 16) apna tag miss karta hai, T2 (history 8) aur T1 (history 4) dono hit karte hain; kyunki T2 deeper hit hai woh provider ban jaata hai (orange highlight). T0 bottom par koi tag carry nahi karta aur guaranteed fallback hai jab har tagged row miss kare.

Prediction counters yahan 3-bit signed hain, range $- 4$ se $+ 3$ tak; T predict karo agar counter $\geq 0$ ho, warna NT.

Recall "Longest match wins" kyun?

Longer history situation ka ek zyada specific fingerprint hai. Agar usne yeh exact pattern seekha hai, toh woh shorter, zyada general table se zyada reliable hai. Bottom (T0) always-available fallback hai.

Forecast: Kuch bhi tagged match nahi karta — kya answer dene ke liye kuch bacha hai?

Tables top-down scan karo (Figure s02 arrow). T3 tag ✗, T2 ✗, T1 ✗. Top-down kyun? Hum longest tag hit chahte hain; deep start karo aur neeche aao.
Base par aao. Koi tagged match nahi → provider = T0. T0 kyun hamesha kaam karta hai? T0 sirf PC se indexed hai aur iska koi tag nahi, isliye woh kabhi "miss" nahi kar sakta — yeh cold/degenerate inputs ke liye guaranteed fallback hai.
T0 ka counter padho. $+ 1 \geq 0$ → predict T. $\geq 0$ threshold kyun? Signed counter: non-negative = taken ki taraf leaning.

Verify: Provider = T0, prediction = T kyunki $1 \geq 0$ true hai. ✓

Forecast: T1 aur T2 dono match karte hain lekin sign mein disagree karte hain. Kiski vote count hogi?

Matches list karo (Figure s02). Matching tables: T1 (len 4) aur T2 (len 8). Kyun list karein? Rule history lengths compare karta hai, counter strengths nahi.
Longest chunte hain. $8 > 4$ → provider = T2 (orange-highlighted row). Zyada confident T1 kyun nahi? Specificity confidence se better hai — T2 ne zyada context dekha aur phir bhi is branch ka fingerprint match kiya.
T2 ka counter padho. $+ 2 \geq 0$ → predict T (chahe T1 $- 2$ se NT chahta tha). T1 ko ignore kyun karein? T1 alternate hai; ise sirf useful-bit logic (Ex 8) ke liye consult kiya jaata hai, final call ke liye nahi.

Verify: Provider = T2, prediction = T kyunki $2 \geq 0$ . T1 ka $- 2$ overrule hua. ✓

Forecast: 4-bit history kaafi nahi thi. Kaunse longer table ko new entry milti hai — aur agar koi free nahi hota?

Provider counter update karo. T prediction par galat (actual NT) → decrement: $+ 1 \to 0$ . Abhi bhi $\geq 0$ kyun? $0 \geq 0$ abhi bhi T predict karta hai — ek strike 3-bit counter flip karne ke liye kaafi nahi; counters ka yahi point hai.
Longer tables tak restrict karo. Provider = T1 (index $k = 1$ ). Sirf $T_{m}$ jahan $m > k$ candidates hain: yahan {T2, T3}. Sirf longer kyun? Current length fail hui, isliye zyada specific (longer) history woh hypothesis hai jise test karna worth hai. Kabhi shorter allocate mat karo — woh context throw away karna hai.
Victim ko lowest useful bit se chunte hain. Candidates mein, hum sirf usi entry ko overwrite kar sakte hain jiska useful bit = 0 ho (useless slot). T2 mein useful = 1 → protected; T3 mein useful = 0 → overwrite karna free. Isliye T3 mein allocate karo. Useful-bit gate kyun? Ek proven-useful entry ko overwrite karna knowledge destroy kar dega; useful bit exactly "mujhe evict mat karo" flag hai. Jab kai candidates free hon, real TAGE shortest free table prefer karta hai (failed length ke closest) taaki woh ek rung ek time climb kare; yahan T3 akela free hai, isliye woh outright jeetta hai.
Agar KOI candidate free nahi ho (sab useful = 1)? Tab TAGE is baar kuch allocate nahi karta aur instead candidate entries ke useful bits decrement karta hai (ek ageing step). Eviction force kyun nahi? Ek useful entry ko force out karna likely ek future misprediction cause karega jo hum jo fix kar rahe hain usse bura hoga. Ageing ek slot ko next miss par free hone deta hai, isliye allocation sirf postpone hota hai, destructive kabhi nahi.
New entry seed karo. T3 ka tag write karo, uska counter weakly actual outcome NT se match karte hue set karo → counter $= - 1$ , useful bit $= 0$ . Weak kyun, strong nahi? Ek brand-new entry untrusted hai; use future visits par confidence earn karni padegi.

Verify: Provider counter $1 \to 0$ (abhi bhi $\geq 0$ , prediction direction unchanged — ek miss flip nahi karta). Candidate set = {T2,T3}; sirf T3 mein useful = 0 hai, isliye target = T3, seeded NT counter $- 1 < 0$ ke saath. ✓

Forecast: Sahi hona acha hai — lekin sahi hona jab tum redundant bhi the kya reward earn karta hai?

Fix karo alternate kaun hai. Matches = {T1, T3}; provider = longest = T3; alternate = next-shorter match = T1. T2 ne apna tag miss kiya, isliye woh is comparison mein kabhi enter nahi karta. Yeh kyun matter karta hai? "Alternate" matlab next-shorter table jo actually matched, na sirf ek rung neeche ki table. Ek missed table yahan invisible hai.
Sub-case (a): alternate galat. T3 sahi, T1 galat → T3 necessary tha. Increment kyun? Useful bit measure karta hai "kya is entry ne woh value provide ki jo shorter match nahi kar sakta tha?" Yahan clearly kiya → useful $+ 1$ .
Sub-case (b): alternate bhi sahi. T3 sahi, T1 sahi → T3 redundant tha. Increment kyun NAHI? T1 (cheaper, shorter) ne already ise cover kiya. T3 ko yahan reward karna ek aise table ko protect karega jo apni jagah earn nahi kar raha → useful unchanged.
Consequence. Redundant deep entries low useful ki taraf drift karte hain aur future allocations ke liye victims ban jaate hain (Ex 7 step 3). Yeh healthy kyun hai? Yeh hardware ko un patterns se recycle karta hai jo shorter table free mein handle kar leti hai.

Verify: alternate = T1 (akela shorter matching table). useful increment karo $⟺$ (provider correct) AND (alternate wrong). (a) → haan; (b) → nahi. ✓

Real-world & exam-style

Worked example Ex 9 — Cell I: word problem, kitne history bits chahiye?

for (int i = 0; i < 3; i++)      // outer, 3 iterations
  for (int j = 0; j < 4; j++)    // inner, 4 iterations
    if (cond) { ... }            // Branch X, fully periodic

Inner loop ka apna back-edge (woh "looping karte rahein?" branch) same decision ek fixed period par repeat karta hai. TAGE table ko inner loop ke back-edge ka ek full period capture karne ke liye minimum global-history length $L$ (branches mein) kya hai, aur parent ki ladder ( $L_{1} = 4, L_{2} = 8, L_{3} = 16$ ) mein kaunsi shortest table kaafi hai?

Forecast: Inner loop ka apna branch kitni baar fire hota hai per period repeat se pehle?

Inner branch ka period count karo. Inner $j = 0, 1, 2, 3$ run karta hai phir exit karta hai. Inner loop-back branch outcome sequence per outer iteration hai $T, T, T, N T$ — period 4. Period 4 kyun? Pattern repeat hone se pehle chaar inner conditional-branch resolutions.
History bits = period. Period-4 pattern recognize karne ke liye tumhe last 4 outcomes yaad rakhne chahiye → $L \geq 4$ bits. Exactly period kyun? Period se shorter history register cycle mein do aisi positions distinguish nahi kar sakta jo ek common suffix share karte hain; $L = 4$ har phase ke liye ek unique fingerprint deta hai.
Table se match karo. Parent ki ladder mein $L_{1} = 4$ , table T1 shortest table hai jo kaafi hai; yahi wajah hai ki parent ke nested-loop example mein TAGE T1 mein allocate kiya. T0 kyun nahi? T0 mein koi history (length 0) nahi aur woh sirf average bias seekhega, har period mein loop-exit mispredict karega.

Verify: Period = 4, minimum $L = 4$ , chosen table = T1 ( $L_{1} = 4$ ). ✓

Forecast: Selector sirf 80% acha hai — kya combo phir bhi 87% global ko beat kar sakta hai?

Model likho (parent se). $Err_{tour} = (1 - a_{s}) \cdot max (1 - a_{1}, 1 - a_{2}) + a_{s} \cdot min (1 - a_{1}, 1 - a_{2})$ Yeh shape kyun? Probability $a_{s}$ ke saath selector ne better predictor choose kiya (smaller error milta hai); probability $1 - a_{s}$ ke saath usne worse waala choose kiya (larger error).
Per-predictor errors fill karo. $1 - a_{1} = 0.15$ , $1 - a_{2} = 0.13$ . Toh $min = 0.13$ , $max = 0.15$ . Kyun dono compute karein? Formula dono extremes ko weight karta hai.
$a_{s} = 0.80$ ke saath evaluate karo. $Err_{tour} = 0.20 \times 0.15 + 0.80 \times 0.13 = 0.030 + 0.104 = 0.134$ Tournament accuracy $\approx 1 - 0.134 = 0.866 = 86.6%$ . Interpret kyun karein? Yeh particular selector standalone global (87%) se thoda worse hai — yeh model ka honest edge case dikhata hai: ek weak selector ek strong component ko dilute kar sakta hai.
$a_{s} = 0.95$ ke saath redo karo. $Err_{tour} = 0.05 \times 0.15 + 0.95 \times 0.13 = 0.0075 + 0.1235 = 0.131$ Tournament accuracy $\approx 1 - 0.131 = 0.869 = 86.9%$ — ab essentially best component se match kar raha hai. Contrast kyun? Exam trap yeh assume karna hai ki "hybrid hamesha $>$ best component." Yeh coarse single- $a_{s}$ model dikhata hai ki woh sirf tab jeetta hai jab selector accurate enough ho; real hybrids dono ko isliye beat karte hain kyunki woh per-branch seekhte hain kispar trust karna (per-branch selector, ek global $a_{s}$ nahi).
Final answer. $a_{s} = 0.80$ ke saath: error $= 0.134$ (86.6%, global ke 87% se thoda neeche). $a_{s} = 0.95$ ke saath: error $= 0.131$ (86.9%). Conclusion: tournament tabhi payoff karta hai jab selector ki apni accuracy high ho.

Verify: $0.2 (0.15) + 0.8 (0.13) = 0.134$ ; aur $0.05 (0.15) + 0.95 (0.13) = 0.131$ ; best single predictor error $= min (0.15, 0.13) = 0.13$ , isliye weak selector ise beat nahi kar sakta. ✓

Wrap-up

Recall Selector

01 par, P2 ek disagreement jeetta hai — new value aur kya provider badlega? $min (3, 1 + 1) = 2$ = 10; woh plum mid-line cross karta hai, isliye provider local → global flip ho jaata hai (Cell D).

Recall Selector

00 par, dono predictors galat — new value? Dono galat ek tie hai ⇒ teesra case ⇒ 00 par freeze (Cell A, both-wrong half).

Recall TAGE: T1 aur T3 tags dono match karte hain, disagree karte hain — kaun provide karta hai?

Longer history table T3 provide karta hai; T1 alternate ban jaata hai jo sirf useful-bit test ke liye use hota hai.

Recall TAGE misprediction, lekin har longer table ki entry mein useful = 1 hai — kya hota hai?

Is cycle mein koi allocation nahi; TAGE un useful bits ko decrement karta hai (ageing) taaki baad ki miss par ek slot free ho jaye. Allocation postpone hota hai, destructive kabhi nahi.

Related: 5.3.8-Two-level-adaptive-predictors · 5.3.9-Gshare-and-local-predictors · 5.3.11-Branch-target-bufers · 5.4.2-Speculative-execution · 7.2.5-Cache-coherence-and-branch-predictors · Hinglish version