Tournament and TAGE predictors — Hinglish notes

5.3.10 · Hardware › Advanced Microarchitecture

Overview

Modern wide-issue processors sirf kuch hi instructions retire karte hain per cycle (typically 4–8 per cycle), lekin saikdon instructions in-flight rehte hain kai pipeline stages mein. Branch instructions create karte hain fundamental uncertainty is baare mein ki aage kya fetch karna hai—aur ek galat guess sab in-flight work ko flush kar sakta hai. Tournament aur TAGE (Tagged Geometric History Length) predictors represent karte hain evolution simple adaptive schemes se hybrid meta-predictors ki taraf jo multiple prediction strategies ko combine karte hain. Classic tournament (hybrid) predictors ~90–93% accuracy tak pahunchte hain; high-end TAGE variants real workloads par 95% se bhi aage push karte hain.

Socho jaise multiple weather forecasters hain—ek rain predict karne mein expert hai, doosra temperature mein. Tum unki accuracy track karte ho aur jo current question ke liye recently sahi raha ho, uski suno.

Tournament Predictors: The Meta-Prediction Architecture

Tournament Predictor Kya Hai?

Ek tournament predictor (jise hybrid ya meta-predictor bhi kehte hain) do ya zyada component predictors ko combine karta hai ek selector (ya choice predictor) ke through, jo track karta hai ki kaunsa component recently sabse accurate raha hai.

Selector: Ek 2-bit saturating counter per branch (ya per set indexed schemes) jo vote karta hai:

00, 01 → Predictor 1 use karo
10, 11 → Predictor 2 use karo
Update hota hai based on kaunsa predictor correct tha

Tournament Selection Kaise Kaam Karta Hai

Har branch ke liye PC = 0x4000 par:

Dono predictors predictions karte hain:
- Local predictor → T
- Global predictor → NT
Selector apna counter padhta hai (maan lo, selector[hash(PC)] = 01 → local use karo)
Fetch proceed karta hai local ki prediction (T) ke saath
Resolution par:
- Actual outcome: T
- Local correct tha → selector ko local ki taraf increment karo (01 → 01 stay karta hai)
- Global wrong tha → selector global ki taraf nahi jaata

Selector adapt karta hai: agar global behtar karne lagta hai, repeated correctness counter ko 10, 11 ki taraf shift karti hai.

Saturating counters kyun? Oscillation prevent karta hai—switch karne ke liye consistent evidence chahiye, lekin behavior change hone par adapt karta hai (e.g., naya loop enter karne par).

Branch A: Local predictor loop ka T, T, .., NT pattern seekhta hai (iteration count par strong).

Branch B: Global predictor correlation dekhta hai—agar bahut saare A's T the (high arr[i]), toh B likely T hai (high sum).

Shuruaat mein, selector A ke liye local ko prefer kar sakta hai. Lekin B mein koi local pattern nahi dikhta—global B ke liye jeetta hai, selector shift hota hai. Processor end up karta hai local A ke liye, global B ke liye use karte hue, dono worlds ka best achieve karte hue.

Derivation: Selector Kaam Kyun Karta Hai

Prediction error ke first principles se shuru karo:

Error Rate = P (misprediction)

Accuracy $a_{1}$ wale single predictor ke liye:

Error_{1} = 1 - a_{1}

Accuracies $a_{1}, a_{2}$ wale do predictors ke liye:

Error_{oracle} = min (1 - a_{1}, 1 - a_{2})

Ek oracle selector (hamesha best pick karta hai) yahi achieve karta hai. Apni accuracy $a_{s}$ wala realistic selector ise approximate karta hai:

Error_{tournament} \approx (1 - a_{s}) \cdot max (1 - a_{1}, 1 - a_{2}) + a_{s} \cdot min (1 - a_{1}, 1 - a_{2})

Yeh behtar kyun hai: Even agar $a_{s} = 0.8$ ho (selector 80% accurate hai choose karne mein), tumhe dono predictors se weighted benefit milta hai, jo typically akele kisi ek se behtar hota hai.

Real workloads ke liye:

Local: ~85% accurate
Global: ~87% accurate
Tournament: ~90–93% accurate (meta-learning exploit karta hai ki alag branches ko alag strategies chahiye)

TAGE: Tagged Geometric History Length

TAGE Kaunsi Problem Solve Karta Hai?

Tournament predictors apni fixed history lengths se limited hain. Kuch branches ko 10 bits of history chahiye (nested loops), doosron ko 50+ (complex correlated control flow). Sirf ek length use karna ya resources waste karta hai ya underfit karta hai.

TAGE (Briz et al., 2006) multiple tables use karta hai geometrically increasing history lengths ke saath aur tagged entries ke saath taaki sahi history length ko har branch se match kiya ja sake.

TAGE Architecture

Tagged Tables (T1, T2, .., Tn): Typically 4-6 tables, har ek indexed by:

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

jahan $L_{i}$ table $i$ ke liye history length hai (e.g., $L_{1} = 4, L_{2} = 8, L_{3} = 16, L_{4} = 32$ —geometric series).

Har entry contain karti hai:

Tag: Partial PC + history hash (collision detection ke liye)
Prediction counter: 3-bit signed counter (−4 se +3 tak, T predict karo agar ≥ 0)
Useful bit: Track karta hai ki is entry ne correct predictions di hain ya nahi

TAGE Prediction Kaise Karta Hai

Saare indices compute karo $T_{0}, T_{1}, \dots, T_{n}$ ke liye PC aur varying history lengths use karke.
Tags check karo har indexed entry par. Sabse lamba matching table dhundho (sabse bada $i$ jahan tag match kare).
Us table ki prediction use karo:
- Agar $T_{3}$ match karta hai: $T_{3}$ ka counter use karo
- Agar sirf $T_{1}$ match karta hai: $T_{1}$ ka counter use karo
- Agar koi nahi match karta: $T_{0}$ use karo (base predictor)
Resolution par:
- Provider component ko update karo (jo prediction karta tha)
- Agar prediction wrong thi, longer-history table mein ek naya entry allocate karo (use ek chance do)
- Useful bits update karo track karne ke liye ki kaunse tables contribute kar rahe hain

Allocate in T_{m} where m > k (longer history)

Longer allocate kyun? Current history length kaafi nahi thi. Ek aur specific pattern try karo.

Useful bit: Tab increment hota hai jab yeh entry correctly predict kare aur next-shorter table ne incorrectly predict kiya hota. Periodically decrement hota hai. Low-useful entries replace ki ja sakti hain (victim selection).

Execution ke shuruaat mein:

$T_{0}$ (base): Weakly T predict karta hai (doosre code se biased)
Misprediction → $T_{1}$ mein allocate karo (4-bit history)

Kuch iterations ke baad:

$T_{1}$ inner loop pattern seekhta hai (T, T, T, T, NT)
Correct predictions → useful bit increment hota hai

Jab outer loop change hota hai:

Outer loop iteration pattern ko affect karta hai (naya i → alag data values)
$T_{1}$ mispredicting shuru karta hai → $T_{2}$ mein allocate karo (8-bit history)
$T_{2}$ two-level pattern seekhta hai (inner × outer)

Result: TAGE automatically discover karta hai ki is branch ko 8 bits of history chahiye, 4 nahi, progressively longer scales try karke.

Derivation: Geometric History Lengths Kyun?

Resource trade-off consider karo:

Total entries: $N$ (fixed hardware budget)
Agar uniform lengths use karo (sab 16-bit), tumhare paas $N$ entries hain ek scale par.
Agar geometric use karo ( $L_{1} = 2, L_{2} = 4, L_{3} = 8, L_{4} = 16, L_{5} = 32$ ), $N$ entries ko 5 tables mein distribute karo.

Coverage: Geometric ensure karta hai ki tum kisi bhi history length $L$ ko match kar sako table pick karke jahan $L_{i} \leq L < L_{i + 1}$ ho. Relative precision loss bounded hai:

\frac{L - L _{i}}{L} \leq \frac{L _{i + 1} - L _{i}}{L _{i + 1}} = 1 - \frac{1}{r}

jahan $r$ geometric ratio hai (typically $r = 2$ ). $r = 2$ ke saath, maximum relative error 50% hai, lekin practice mein, zyaatar branches ke characteristic scales hote hain (loops often powers of 2 mein hote hain length mein).

Linear kyun nahi (4, 8, 12, 16)? Mid-range lengths par entries waste hoti hain. Branches ya toh bahut short ya bahut long history chahte hain—geometric spacing extremes par resources concentrate karta hai.

Tournament vs. TAGE: Kab Kya Use Karein

Definition Comparison

Aspect	Tournament	TAGE
Predictors	2 fixed (local + global)	Multiple geometric tables
History	Fixed lengths (e.g., 10 bits)	Adaptive (4, 8, 16, 32, ..)
Selection	Per-branch selector counter	Longest matching tag
Accuracy	~90-93% (SPEC2000)	~95-96% (modern workloads)
Complexity	Moderate (3 tables total)	Higher (5-7 tables, tagging)
Best for	Bimodal workloads	Diverse history needs

Modern CPUs: Zyaatar TAGE ya TAGE variants use karte hain (Intel Skylake onward, AMD Zen, ARM Neoverse). Tournament predictors 2000s mein dominant the (Alpha 21264, Pentium 4) lekin ab replace ho gaye hain.

Kyun sahi lagta hai: "Tournament" naam suggest karta hai ek real-time competition jahan best jeetta hai.

Fix: Selector past accuracy use karta hai future accuracy predict karne ke liye. Yeh khud ek meta-predictor hai, apne 2-bit state machine ke saath. Phase changes ke dauran (e.g., naya function enter karte waqt), selector kuch branches ke liye galat predictor favor kar sakta hai jab tak adapt nahi karta.

Impact: Tournament accuracy ≠ max(local, global) accuracy. Yeh typically akele dono se behtar hota hai, lekin perfect nahi. Selector adaptation ke dauran mispredictions hoti rehti hain.

Kyun sahi lagta hai: Zyada information → behtar prediction, toh $T_{n}$ (sabse lamba) dominate karna chahiye.

Fix: Longer history ≠ behtar prediction agar branch mein utna correlation nahi hai. Koi random branch jisme koi pattern nahi, use base predictor (simple bias) se fayda hota hai, na ki 64 bits ke uncorrelated history se. TAGE tag matching use karta hai ensure karne ke liye ki history relevant hai—agar tag match nahi karta, toh woh entry is branch ke pattern ke baare mein nahi hai.

Impact: Longest history force karne se aliasing hoti hai (unrelated branches high-history tables mein collide karte hain, predictions pollute karte hain). TAGE ki allocation policy ensure karti hai ki tum long history tabhi use karo jab zaroorat ho.

Recall 12-Saal-Ke-Bachche Ko Samjhao

Socho tum guess karne ki koshish kar rahe ho ki tumhara dost school ke baad soccer khelna chahega ya nahi. Kabhi kabhi tum bol sakte ho "Kya unhone kal khela?" (short history). Lekin kabhi kabhi tumhe jaanna hoga "Kya woh puri week thake the? Kya unka bada test tha?" (long history).

Ek tournament predictor aise hai jaise do dost hain jo guessing mein acche hain: ek kal dekhta hai, ek poori week dekhta hai. Tum score rakhte ho: jo recently zyada sahi raha ho, uski suno.

TAGE aur bhi smart hai: yeh paanch guessers rakhta hai, har ek alag time scales dekhta hai—1 din, 3 din, ek hafte, ek mahine, ek season. Jab tum poochte ho "Kya woh aaj khelenge?", TAGE sab paanch check karta hai aur sabse specific wala use karta hai jisne yeh exact situation pehle dekhi ho (jaise, "Pichli baar jab woh poori week thake the AUR unka test tha, toh unhone nahi khela").

Toh TAGE simple patterns (sirf kal dekho) aur complex patterns (poore season ka data chahiye) dono handle kar sakta hai, bina galat time scale par space waste kiye.

Connections

5.3.8-Two-level-adaptive-predictors — TAGE two-level ko extend karta hai multiple history lengths use karke
5.3.9-Gshare-and-local-predictors — Tournament gshare (global) ko local ke saath combine karta hai
5.3.11-Branch-target-bufers — Predicted direction useless hai bina predicted target ke
5.4.2-Speculative-execution — Galat predictions saara speculative work waste kar dete hain
7.2.5-Cache-coherence-and-branch-predictors — Multi-core systems branch history share karte hain

Tournament ke liye: "Do predictors duel karte hain, selector judge hai—judge past wins use karta hai future winner choose karne ke liye."

#flashcards/hardware

Tournament predictor ki key innovation kya hai? :: Yeh multiple component predictors (typically local + global) ko ek selector ke through combine karta hai jo track karta hai kaunsa recently zyada accurate raha hai, jisse processor har branch type ke liye best strategy use kar sake.

Tournament predictor mein selector actually kya store karta hai?

Ek 2-bit saturating counter per branch (ya per set) jo predictor 1 (00, 01) ya predictor 2 (10, 11) ke liye vote karta hai, update hota hai based on kaunsa predictor correct tha.

Ek single fixed-history-length predictor >95% accuracy kyun nahi achieve kar sakta?

Alag branches ko alag history lengths chahiye: loops ko short history chahiye (4-10 bits), correlated branches ko medium (16-32 bits), deep call chains ko long (64+ bits). Fixed length ya resources waste karta hai ya underfit karta hai.

TAGE ka full form kya hai aur uska core idea kya hai?

Tagged Geometric History Length. Multiple tables geometrically increasing history lengths (4, 8, 16, 32 bits) ke saath aur tagged entries ke saath use karta hai; har branch ke liye sabse lamba matching history se predict karta hai.

TAGE decide kaise karta hai ki prediction ke liye kaunsi table use karni hai?

Saari tables mein indices compute karta hai PC + varying history lengths use karke, tag matches check karta hai, sabse zyada indexed (longest-history) table with a matching tag use karta hai, koi match nahi toh base predictor par fall back karta hai.

TAGE mein jab prediction galat hoti hai toh kya hota hai?

Provider table update hoti hai, aur ek longer-history table mein naya entry allocate hota hai (zyada GHR bits wali) taaki ek aur specific pattern capture ho jo current table ne miss kiya.

TAGE history lengths ke liye geometric (2×) spacing kyun use karta hai instead of linear spacing?

Branches typically history chahte hain scale-invariant lengths par (loops powers of 2 hoti hain). Geometric spacing resources concentrate karta hai short aur long extremes par jahan zyaatar branches cluster hote hain, intermediate lengths par waste avoid karta hai.

TAGE entry mein "useful bit" kya hai?

Ek bit jo track karta hai ki is entry ne correct predictions di hain jo next-shorter table se alag thi. Low-useful entries replace ki ja sakti hain taaki unhelpful patterns par space waste na ho.

Tournament predictor mein selector counter kab nahi change hota?

Jab dono predictors agree karte hain (dono correct ya dono wrong)—ek ko doosre par prefer karne ka koi evidence nahi.

Modern workloads par TAGE tournament predictors se zyada accurate kyun hai?

Modern code mein diverse history needs hain (simple loops se complex state machines tak). TAGE ki multiple history lengths har branch ke characteristic scale ke saath adapt karti hain, jabki tournament sirf do fixed lengths tak limited hai.

Tournament vs TAGE predictors ke liye typical accuracy range kya hai?

Tournament: ~90-93%, TAGE: ~95-96% SPEC benchmarks par. Mispredictions mein reduction significantly performance boost karta hai branch-heavy code par (kyunki mispredictions pipeline ko stall karti hain).

Modern wide-issue CPUs actually kitni instructions retire karti hain per cycle?

Sirf thodi si (typically 4-8 per cycle), jabki saikdon pipeline stages mein ek saath in-flight ho sakti hain. Isliye branch mispredictions costly hain—woh saara in-flight work flush kar deti hain.