Tournament and TAGE predictors: Question bank — Hinglish deep dive

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

Yeh bank un galat dharnaon ko dhundhta hai jo Tournament and TAGE predictors ke andar chupi rehti hain. Har item ek single-line reveal hai: prompt padho, apna jawab zor se bol ke commit karo, phir check karo. Answers mein sirf verdict nahi balki reasoning di gayi hai — woh reasoning hi yaad rakhne wali cheez hai.

Prerequisites jo aapko pehle se samajhni chahiye: 5.3.8-Two-level-adaptive-predictors, 5.3.9-Gshare-and-local-predictors. Ek branch ka fate 5.4.2-Speculative-execution ko feed karta hai, aur target address 5.3.11-Branch-target-bufers se aata hai.

Pehle, woh vocabulary jo in questions mein assume ki gayi hai

Traps se pehle, har word aur symbol ko clearly pin down karo — warna "gotcha" unfair lagega.

Definition Woh words jo is poore page par use hote hain

PC (Program Counter): us instruction ka address jo fetch ho rahi hai. "PC-indexed" ka matlab hai hum ek table ko (us address ke kuch bits) se lookup karte hain, isliye har branch instruction ka apna slot hota hai.
Component predictor: tournament ke andar ek base predictor. Is page par predictor 1 = local predictor aur predictor 2 = global predictor hai — poore page ke liye fixed, isliye "predictor 2 ki taraf move karo" ka matlab hamesha "global wale par zyada trust karo" hota hai.
Local predictor: sirf is branch ki apni recent taken/not-taken history se predict karta hai (PC se indexed).
Global predictor: Global History Register (GHR) se predict karta hai — last kuch branches ke outcomes regardless of PC — isliye yeh alag-alag branches ke beech correlation capture karta hai.
Selector: ek per-branch 2-bit saturating counter (values $0, 1, 2, 3$ ) jo choose karta hai ki kaunsa component jawab dega, branch kya karta hai yeh nahi.

Aage padhne se pehle ladder dekho — figure ordering ko aapke mind mein fix kar deta hai.

Selector ka decision ek simple threshold hai — figure counter ko ek dial ki tarah dikhata hai.

True or false — justify karo

Ek saturating counter ek chhota counter hota hai jo wrap around karne ki bajay apne minimum aur maximum par ruk jaata hai; verdict badalne se pehle isse repeated evidence chahiye hoti hai.

Tournament selector ek per-branch (ya per-hash) 2-bit saturating counter hai jo kehta hai ki kaunse component predictor par trust karna hai, branch kya karta hai yeh nahi.

TAGE mein provider woh single table hai jiska entry kisi given lookup par actually prediction deta hai — longest-history table jiska tag match kiya.

TF — Tournament selector predict karta hai ki branch taken hai ya not-taken.

False — selector kabhi branch outcome predict nahi karta; yeh sirf choose karta hai ki kaunsa component predictor (predictor 1 = local, predictor 2 = global) jawab dega. Chosen component taken/not-taken predict karta hai.

TF — Agar dono component predictors correct hain, to selector phir bhi us ek ki taraf move karta hai jo "jeet gaya".

False — update rule sirf tab selector ko move karta hai jab dono components ki correctness mein disagreement ho; agar dono sahi hain (ya dono galat) to yeh

s

par hold karta hai, kyunki ek ko doosre se prefer karne ka koi evidence nahi hai.

TF — Ek tournament predictor kabhi bhi apne single best component predictor ko beat nahi kar sakta.

False — kyunki alag-alag branches alag components ko prefer karti hain, har branch ko uske better component par route karna kisi bhi component ko akele measured karne se beat kar sakta hai; yahi meta-prediction ka poora point hai.

TF — TAGE ka base predictor T0 global history use karta hai jaise tagged tables karte hain.

False — T0 mein

L_{0} = 0

hai: yeh ek plain PC-indexed biased predictor hai jisme koi history nahi, yeh woh hamesha-available fallback hai jo tab use hota hai jab kisi tagged table ka tag match nahi karta.

TF — TAGE mein saari tagged tables jo match karti hain consult ki jaati hain aur unke votes average kiye jaate hain.

False — TAGE ek single provider choose karta hai: woh matching table jiska largest index

k

ho (longest history). Longer history zyada specific pattern ka matlab hai, isliye yeh outright jeet jaata hai — koi averaging nahi.

TF — TAGE ki history lengths linearly badhti hain (4, 8, 12, 16, …).

False — sequence

{L_{i}}

geometrically badhti hai (jaise

4, 8, 16, 32, 64

) isliye thodi si tables pattern lengths ki ek huge range cover karti hain, redundant nearby lengths par entries kharche bina.

TF — Ek longer-history TAGE table hamesha same branch ke liye shorter wali se zyada accurate hoti hai.

False — longer history zyada specific hoti hai, jo tabhi help karta hai jab branch actually utni history par depend karti ho; ek short-pattern branch ke liye, extra history bits noise hain aur shorter table better hai, isliye useful bit aur tag matching winner decide karte hain.

TF — Ek baar selector global predictor ki taraf saturate ho jaaye (

s = 3

), ek branch kabhi local par wapas switch nahi kar sakti.

False — saturation ka matlab sirf yeh hai ki

s

ko wapas neeche walk karne mein kaafi consecutive disagreements lagte hain dusri direction mein; behaviour change (jaise ek naya loop phase) exactly woh evidence deta hai aur counter

0

ki taraf wapas aata hai.

Error dhundho

Error — "Selector predictor 2 ki taraf update hota hai jab bhi predictor 2 correct hota hai."

Galat: yeh predictor 2 (global) ki taraf tabhi move karta hai jab predictor 2 correct ho aur predictor 1 (local) galat ho — yaani

s \to min (3, s + 1)

. Agar dono correct hain to trust shift karne ka koi reason nahi.

Error — "TAGE misprediction par, hum ek shorter-history table mein ek nayi entry allocate karte hain taaki jaldi react kar sakein."

Galat: allocation ek longer-history table

T_{m}

mein jaati hai jahan

m > k

ho, jahan

T_{k}

woh provider tha jisne misprediction ki. Uski history length is case ko distinguish karne ke liye insufficient thi, isliye hum zyada specific, longer pattern

L_{m} > L_{k}

try karte hain.

Error — "TAGE tags isliye exist karte hain taaki alag PCs wale lekin same history index wale do branches ek entry efficiently share kar sakein."

Galat: tags exactly us collision ko detect aur prevent karne ke liye exist karte hain. Ek mismatched tag ka matlab hai entry kisi alag context ki hai, isliye TAGE wahan table ko not-matching treat karta hai.

Error — "80% -accurate selector wala ek tournament predictor dono components mein se kisi bhi akele se bura perform karta hai."

Galat: ek imperfect selector bhi typically dono error rates ka ek weighted blend deta hai jo kisi bhi component se better hota hai, kyunki yeh zyatar branches ko unke stronger predictor ki taraf steer karta rehta hai.

Error — "TAGE entry ke har baar sahi predict karne par useful bit increment hota hai."

Galat: provider

T_{k}

ka useful bit sirf tab increment hota hai jab

T_{k}

correct ho aur next-shorter table $T_{k - 1}$ galat hoti — yaani jab is longer entry ne actually value add ki. Har correct prediction ko reward karna har entry ko useful dikhaega aur victim selection break kar dega.

Error — "Kyunki TAGE mein multiple tables hain, ise base predictor ki zarurat nahi."

Galat: T0 essential hai. Ek brand-new branch par kisi bhi tagged table mein koi allocated, tag-matching entry nahi hoti, isliye T0 ka biased guess hi ek maatra available prediction hai.

Error — "Global predictor is branch ke PC ki last N outcomes use karta hai."

Galat: yeh local predictor ko describe karta hai (per-PC history). Global predictor Global History Register use karta hai — last N branches ke outcomes regardless of PC — yehi use karne se yeh alag-alag branches ke beech correlation capture kar paata hai.

Why questions

Why — Selector ek single bit ki bajay saturating counter kyun use karta hai?

Ek single bit har disagreement par flip karta, oscillation cause karta; ek 2-bit saturating counter (

0

–

3

) threshold cross karne se pehle consistent evidence maangta hai, jo stability deta hai aur genuine phase changes ke saath adapt bhi karta hai.

Why — TAGE misprediction ke baad current provider

T_{k}

ko sirf retrain karne ki bajay longer table (

T_{m}

m > k

) mein allocate kyun karta hai?

Longest matching table se misprediction ka matlab hai history length

L_{k}

dono behaviours ko separate nahi kar sakti; same entry ko retrain karna use sirf thrash karega, isliye TAGE ek longer, zyada discriminating pattern

L_{m} > L_{k}

tak pahunchta hai.

Why — Geometric history lengths "any" needed length ko few tables ke saath cover karti hain kyun?

Kisi bhi required length

L

ke liye sequence

{L_{i}}

mein ek table hoti hai jahan

L_{i} \leq L < L_{i + 1}

ho; geometric spacing ka matlab hai har step roughly reach double karta hai, isliye mutthi bhar tables few bits se dozens tak bina important gaps ke span karti hain.

Why — Local predictor loop-counter branches ke liye acha kyun hai lekin global predictor correlated branches ke liye?

Ek loop ka taken/not-taken pattern sirf uski apni recent history par depend karta hai (local, PC-indexed), jabki ek branch jiska outcome kisi earlier branch ko track karta hai, Global History Register mein recorded doosri branches ke outcomes par depend karta hai.

Why — Ek tournament predictor "branch A ke liye local, branch B ke liye global" simultaneously route kar sakta hai kyun?

Selector per branch indexed hota hai (PC ke hash ke through), isliye har branch ka apna trust counter

s

hota hai aur woh independently apne best component ki taraf converge karta hai.

Why — TAGE ko per-entry tags chahiye lekin ek simple gshare predictor ko nahi?

Gshare aliasing ko noise ki tarah accept karta hai, lekin TAGE ko jaanna hi hoga ki longest-index matching table ki entry actually is branch-and-history context ki hai ya nahi; tag ownership confirm karta hai taaki kisi aur context ki stale entry ko provider ki tarah trust na kiya jaaye.

Edge cases

Edge — Ek branch TAGE mein pehli baar dekhi gayi hai. Kaunsa predictor jawab deta hai?

T0 (base predictor,

L_{0} = 0

) — kisi bhi tagged table mein abhi tak koi allocated, tag-matching entry nahi hai, isliye biased fallback use hoti hai aur (agar galat ho) ek longer table

T_{m}

mein allocation trigger hota hai.

Edge — Tournament branch par dono component predictors galat hain. Kya selector move karta hai?

Nahi — update rule

s

ko tab hold karta hai jab dono galat hon (jaise jab dono sahi hon), kyunki kisi bhi component ne is baar superiority demonstrate nahi ki.

Edge — Ek lookup mein har TAGE table ka tag match karta hai. Kaunsa prediction provide karta hai?

Woh jo matches mein largest index wala ho (longest history

L_{k}

); longer history sabse specific context hai aur chahe unke counter values kuch bhi hon, saare shorter matches ko outrank karta hai.

Edge — TAGE allocate karna chahta hai lekin saari longer tables ki candidate entries ka useful bit set hai.

Koi victim safely evict nahi kiya ja sakta, isliye allocation is baar typically fail hoti hai; useful bits ki periodic decrement eventually low-

u

victims free karti hai, aur tab tak existing provider predict karta rehta hai.

Edge — Selector counter exactly

1 \to 2

boundary par baitha hai aur favored component flip karta hai.

Woh boundary wohi hai jahan ek single disagreement choice tip karta hai; yeh intended hai — middle ke paas predictor genuinely undecided hai aur use readily switch karna chahiye, jabki extremes (

0

3

) ki taraf push ki gayi values switching resist karti hain.

Edge — Ek biased branch (almost hamesha not-taken, jaise error handling). Kaunsa mechanism ise cheaply handle karta hai?

T0 ka PC-indexed 2-bit counter akele strong bias capture karta hai; kisi tagged table ko kharchna nahi padta, isliye TAGE apne long-history resources un branches ke liye bachata hai jinhe actually unki zarurat hai.

Recall One-line self-test

Selector choose karta hai ==which component (low = local, high = global), provider hai longest-index tagged table $T_{k}$ whose tag matches, allocation jaati hai a longer table $T_{m}$ , $m > k$ mein, useful bit reward karta hai being correct when $T_{k - 1}$ would have been wrong==.