Tournament and TAGE predictors: Exercises — Hinglish deep dive

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

Ye problems ek hybrid predictor ke parts ko pehchanne se lekar design karne tak jaate hain. Har ek ko paper pe karo solution dekhne se pehle. Jo kuch bhi chahiye vo parent note mein build kiya gaya tha; jahan bhi koi term pehli baar yahan aata hai, hum use re-anchor karte hain taaki tum kisi symbol se anjaan na raho.

Do objects poori jagah baar baar aate hain, toh chalte hain inhe ek baar pin down karte hain. Figure s01 dono ko side by side draw karta hai: selector left pe (kaun sa predictor trust karna hai) aur TAGE counter right pe (taken ya nahi, aur kitna sure). Jab bhi koi counter value aaye, is figure ko refer karo.

Definition Do counters jinhe tum baar baar touch karoge

Selector (choice) counter — ek 2-bit saturating counter (figure s01 ka left half). "2-bit" matlab yeh $0, 1, 2, 3$ hold karta hai. "Saturating" matlab yeh ends par ruk jaata hai: $3 + 1$ stays $3$ , $0 - 1$ stays $0$ (ek normal counter $3 \to 0$ wrap kar leta). Yeh ek sawaal ka jawab deta hai: abhi mere do component predictors mein se main kaun sa trust karta hoon? Is poore page mein predictor 1 = local predictor (per-branch history) aur predictor 2 = global predictor (shared global history) — yeh pairing kabhi nahi badalti. Parent ke rule ke hisaab se, ${00, 01}$ (yani values $0, 1$ , blue cells) → predictor 1 (local), ${10, 11}$ (values $2, 3$ , yellow cells) → predictor 2 (global).

TAGE prediction counter — ek 3-bit signed counter jo $- 4, - 3, \dots, + 3$ range mein chalta hai (figure s01 ka right half). "Signed" matlab yeh $\pm$ sign carry karta hai. Yeh batata hai taken ya not-taken, aur kitna sure?: predict Taken agar value $\geq 0$ ho (green cells), Not-Taken agar $< 0$ ho (red cells). Iska magnitude confidence hai.

Level 1 — Recognition

Problem 1.1 (L1)

Ek tournament predictor ke selector mein value $2$ (binary $10$ ) hai. Yeh kaun sa component predictor choose karta hai, aur kyun?

Recall Solution 1.1

Parent ki mapping (aur figure s01 ke colours): values ${0, 1}$ → predictor 1 (local), values ${2, 3}$ → predictor 2 (global). $2 \in {2, 3}$ , toh selector predictor 2 (the global predictor) pick karta hai. Kyun: 2-bit counter ka top bit hi decision hai. $2 = 1 0_{2}$ , top bit $= 1$ → predictor 2. Bottom bit sirf "kitni strongly" batata hai.

Problem 1.2 (L1)

TAGE mein, ek prediction counter $- 1$ read karta hai. Taken ya Not-Taken?

Recall Solution 1.2

Rule: Taken predict karo agar counter $\geq 0$ ho. Yahan $- 1 < 0$ , toh predict karo Not-Taken. Value $- 1$ yeh bhi batata hai ki confidence low hai (yeh $0$ = weakly Taken se ek step door hai).

Problem 1.3 (L1)

TAGE mein ek base table $T_{0}$ aur tagged tables $T_{1}, T_{2}, T_{3}$ hain jinki history lengths $L_{1} = 4, L_{2} = 8, L_{3} = 16$ bits hain. Ek lookup par, tags $T_{1}$ aur $T_{3}$ mein match karte hain lekin $T_{2}$ mein nahi. Kaun sa table prediction provide karta hai?

Recall Solution 1.3

TAGE hamesha longest matching history use karta hai (sabse specific). Matches hain $T_{1}$ ( $L = 4$ ) aur $T_{3}$ ( $L = 16$ ). Sabse lamba hai == $T_{3}$ ==. $T_{2}$ par gap theek hai — TAGE ko matches ki contiguous chain ki zaroorat nahi, sirf ek longest hit chahiye.

Level 2 — Application

Is poore level mein yaad rakho ki base table $T_{0}$ ki history length $L_{0} = 0$ hai — yeh sirf PC se index hota hai, koi branch history use nahi karta, aur hamesha ek fallback ke roop mein exist karta hai. Tagged tables $T_{1}, T_{2}, T_{3}$ mein $L_{1} = 4, L_{2} = 8, L_{3} = 16$ bits hain, Problem 1.3 ki tarah.

Problem 2.1 (L2)

Ek selector abhi $1$ hold karta hai. Is branch par: predictor 1 (local) correct hai, predictor 2 (global) wrong hai. Parent ka update rule apply karo. Naya selector value kya hai, aur kya chosen predictor badalta hai?

Recall Solution 2.1

Update rule (parent): $selector_{new} = ⎩ ⎨ ⎧ max (0, sel - 1) min (3, sel + 1) sel pred 1 correct AND pred 2 wrong pred 2 correct AND pred 1 wrong otherwise$ Yahan pred 1 sahi, pred 2 galat → pehla case: $max (0, 1 - 1) = 0$ . Choice pehle: $1 \in {0, 1}$ → predictor 1. Choice baad mein: $0 \in {0, 1}$ → predictor 1. Koi change nahi — lekin hum predictor-1 region mein aur gehre chale gaye (zyada confident).

Problem 2.2 (L2)

Selector wahi $1$ par hai, lekin is baar dono predictors correct hain. Naya value?

Recall Solution 2.2

Dono correct → teesra case: selector unchanged = $1$ . Yeh design kyun aisa karta hai: agar dono agree karte hain aur sahi hain, toh ek ko doosre se prefer karne ka koi evidence nahi, isliye hum move nahi karte. Selector sirf disagreements se seekhta hai.

Problem 2.3 (L2)

Ek branch ek repeating stream run karta hai jahan predictor 1 sahi hai aur predictor 2 galat har branch par. Selector $2$ se start karta hai. 3 branches tak trace karo.

Recall Solution 2.3

Har step case 1 hai: $max (0, sel - 1)$ .

Branch 1: $2 \to 1$
Branch 2: $1 \to 0$
Branch 3: $0 \to 0$ (saturates)

Final = == $0$ ==. Chosen predictor sirf ek branch ke baad predictor 2 (at $2$ ) se predictor 1 (at $1$ ) mein flip ho jaata hai, phir predictor 1 mein maximum confidence ki taraf badhta rehta hai.

Problem 2.4 (L2)

TAGE mein base $T_{0} (L_{0} = 0)$ aur tagged tables $T_{1} (4), T_{2} (8), T_{3} (16)$ ke saath, table $T_{2}$ (the provider) mispredict karta hai. TAGE kahan naya entry allocate karne ki koshish karta hai, aur shorter table mein kyun nahi?

Recall Solution 2.4

Rule: provider $T_{k}$ dwara misprediction par, kisi $T_{m}$ mein allocate karo jahan $m > k$ ho. Provider $T_{2}$ hai, toh sirf ek longer table available hai == $T_{3}$ == ( $L = 16$ ). Shorter mein kyun nahi? $T_{2}$ ke 8 bits of history is case ko distinguish karne ke liye insufficient the — shorter history strictly kam specific hai, toh voh bhi fail ho jaata. Ek longer history un patterns ko alag kar sakta hai jo $T_{2}$ ne conflate kiye. Agar $T_{3}$ mein ek free (low-useful) entry hai, TAGE wahaan allocate karta hai; agar $T_{3}$ useful entries se full hai, is baar koi allocation nahi hoti (TAGE ek proven entry ko evict karne ki bajay wait karta hai).

Level 3 — Analysis

Problem 3.1 (L3)

Do component predictors ki accuracies $a_{1} = 0.85$ (local) aur $a_{2} = 0.87$ (global) hain. Selector sahi predictor probability $a_{s} = 0.80$ se choose karta hai. Pehle tournament error model scratch se derive karo, phir numbers plug in karo. Kya tournament dono akele predictors se better hai?

Recall Solution 3.1

Model derive karna. Kisi bhi branch par selector do mein se ek kaam karta hai: ya toh yeh us branch ke liye sahi predictor point karta hai, ya galat wala. $a_{s}$ = probability ki yeh better one pick kare.

Probability $a_{s}$ ke saath selector sahi choice nail karta hai, toh hamara error chhoti error rate ke barabar hoti hai, $min (1 - a_{1}, 1 - a_{2})$ .
Probability $1 - a_{s}$ ke saath selector galat choose karta hai aur hum badi error ke saath stuck ho jaate hain, $max (1 - a_{1}, 1 - a_{2})$ .

In dono outcomes ka probability-weighted average exactly yeh deta hai: $Err_{tour} \approx (1 - a_{s}) \cdot max (1 - a_{1}, 1 - a_{2}) + a_{s} \cdot min (1 - a_{1}, 1 - a_{2}) .$ Toh do terms arbitrary nahi hain: $min$ achhi tarah se choose karne ka reward hai, $max$ buri tarah se choose karne ki penalty hai, dono weighted by kitni baar aisa hota hai. (Ek oracle with $a_{s} = 1$ ise pure $min$ tak collapse karta hai — sabse best possible.)

Numbers plug in karna. Errors: $1 - a_{1} = 0.15$ , $1 - a_{2} = 0.13$ . Toh $max = 0.15$ , $min = 0.13$ . $Err_{tour} \approx 0.20 \cdot 0.15 + 0.80 \cdot 0.13 = 0.030 + 0.104 = 0.134$ Best single predictor error $= 0.13$ (global). Tournament error $= 0.134$ yahan global-alone error se worse hai! Kyun: selector sirf 80% achha hai aur dono predictors skill mein close hain (0.85 vs 0.87). Ek weak selector chhote gap ko waste karta hai. Tournaments tab jeette hain jab alag branches alag predictors ko favor karte hain (toh effective per-branch $min$ kisi bhi global average se kaafi lower hota hai) — upar ka single-number model us structural benefit ko understate karta hai. Problem 3.2 dekho.

Problem 3.2 (L3)

Ab realistic case model karo. Maano aadhe branches "local-friendly" hain (local 95%, global 70%) aur aadhe "global-friendly" hain (local 70%, global 95%). Ek perfect (oracle) selector per branch best pick karta hai. Oracle tournament kitni accuracy reach karta hai, aur yeh sab branches par sirf local ya sirf global use karne se compare kaise karta hai?

Recall Solution 3.2

Local-only accuracy $= \frac{1}{2} (0.95) + \frac{1}{2} (0.70) = 0.825$ . Global-only accuracy $= \frac{1}{2} (0.70) + \frac{1}{2} (0.95) = 0.825$ . Oracle tournament: har half par yeh better predictor leta hai $= 0.95$ , toh $= \frac{1}{2} (0.95) + \frac{1}{2} (0.95) = 0.95$ . Insight: koi bhi single predictor $82.5%$ nahi beat karta, phir bhi oracle $95%$ hit karta hai — $+ 12.5$ point ki jump. Yahi wajah hai ki tournaments exist karte hain: yeh exploit karte hain ki branches alag needs wali populations mein split hoti hain, jo kisi single average-accuracy number mein chhupi rehti hain.

Problem 3.3 (L3)

TAGE tables geometric history lengths $L_{i} = L_{1} \cdot r^{i - 1}$ use karti hain. $L_{1} = 2$ aur $L_{5} = 32$ ke saath 5 tables diye gaye hain, common ratio $r$ find karo aur paancho lengths list karo.

Recall Solution 3.3

Geometric: $L_{5} = L_{1} r^{4}$ , toh $32 = 2 r^{4} \Rightarrow r^{4} = 16 \Rightarrow r = 2$ . Lengths: $L_{1} = 2, L_{2} = 4, L_{3} = 8, L_{4} = 16, L_{5} = 32$ — bilkul wahi ladder jo figure s02 mein draw hai. Geometric kyun, linear nahi (2,4,6,8,10)? History-need roughly logarithmic hoti hai — thodi si branches ko bahut lambi history chahiye. Doubling sirf 5 tables se $2 \to 32$ ka bada range cover karta hai; ek linear ladder ko 32 tak pahanuchne ke liye steps of 2 mein 16 tables chahiye, jinhe koi use nahi karta aur hardware waste hota hai.

Figure s02 resource argument ko visual banata hai: har bar ek table hai, uski length uski history depth hai, aur rungs ke beech "×2" hi wajah hai ki paanch chhote bars $2$ se $32$ tak span karte hain.

Level 4 — Synthesis

Problem 4.1 (L4)

Ek TAGE useful bit tab increment hota hai jab entry correctly predict karti hai aur next-shorter matching table galat predict karta. Maano entry $E$ $T_{3}$ mein Taken predict karti hai (correct), aur $T_{2}$ mein jo entry bhi match karti uska Not-Taken predict karna (incorrect) hota. $E$ ke useful bit ke saath kya hota hai, aur strategically iska kya matlab hai?

Recall Solution 4.1

Dono conditions hold karti hain: $E$ correct aur shorter table galat → useful bit incremented hota hai. Matlab: $E$ apni value prove kar rahi hai. Yeh exist hi isliye karti hai kyunki longer history ne kuch aisa capture kiya jo shorter wale ne galat kar diya. Ek high useful bit $E$ ko eviction se bachata hai; agar yeh $0$ hota, toh nayi allocation ke liye space chahiye hone par $E$ ek candidate victim hoti. Yahi TAGE ka tarika hai har long-history entry se poochne ka: "kya tum actually kuch aisa information add kar rahe ho jo sasta table miss karta hai?"

Problem 4.2 (L4)

Design trace. Ek doubly-nested loop ke andar ek branch ko achhi tarah predict karne ke liye 8 bits of history chahiye, lekin TAGE ke paas abhi sirf $T_{1}$ ( $L = 4$ ) mein ek entry hai. Events ka sequence walk karo (mispredict → allocate → learn) jo TAGE ko correct table tak le jaata hai. Tables $T_{1} (4), T_{2} (8), T_{3} (16)$ maano.

Recall Solution 4.2

Abhi: $T_{1}$ longest match hai, toh yahi provide karta hai. Sirf 4 bits ke saath yeh do alag outer-loop contexts ko conflate karta hai → mispredict karta hai.
Allocate: provider $T_{1}$ hai, toh TAGE longer table mein allocate karta hai, $m > 1$ → try karo $T_{2}$ ( $L = 8$ ). Naya entry fresh 3-bit counter ke saath aata hai, useful bit $0$ .
Learn: agle visits par, $T_{2}$ ka 8-bit index ab do contexts ko separate karta hai. Iska counter sahi direction ki taraf train hota hai; har correct-while- $T_{1}$ -wrong iska useful bit set karta hai.
Steady state: $T_{2}$ longest match aur provider ban jaata hai; $T_{1}$ ki stale entry age out ho jaati hai. TAGE ne discover kar liya ki branch ko 8 bits chahiye — kisine bataya nahi; mispredict-then-lengthen loop ne yeh find kiya.

Problem 4.3 (L4)

Dono ideas combine karo. Ek tournament predictor jiske do components khud ek short-history aur ek long-history predictor hain, selector partially TAGE ke longest-match logic ko duplicate karta hai. TAGE ka is 2-component tournament ke upar ek concrete advantage do.

Recall Solution 4.3

Ek 2-component tournament exactly do history lengths offer karta hai aur unke beech ek coin-flip selector. TAGE kaafi lengths offer karta hai (4–6 tables) aur, sabse important baat, length deterministically tag match se choose karta hai na ki ek trained selector se jo galat ho sakta hai. Advantages: (1) finer granularity — ek branch jise 8 bits chahiye use coarse 4-or-32 choice mein force nahi karna padta; (2) no selector misprediction penalty — longest tag match unambiguous hai, jabki ek selector counter ek phase change ke baad kai branches tak galat direction point kar sakta hai; (3) per-entry usefulness tracking TAGE ko dead history cheaply reclaim karne deta hai. Yahi wajah hai ki high-end TAGE tournament accuracy se zyada hota hai ( $> 95%$ vs $\sim 90 - 93%$ ).

Level 5 — Mastery

Problem 5.1 (L5)

Full pipeline reasoning. Ek processor fetch karta hai jab branch unresolved hoti hai (yeh speculative execution hai). Yeh 4 GHz par run karta hai, 4 instructions/cycle retire karta hai, aur 192 instructions in flight rakhta hai. Misprediction saara in-flight work discard karta hai aur refill karta hai. Do predictors offer kiye gaye hain: Tournament at $92%$ accuracy, TAGE at $96%$ . Agar branches $20%$ instructions hain, dono ke liye misprediction rate per instruction calculate karo, aur unke beech wasted-work ka ratio.

Recall Solution 5.1

Instructions ka fraction jo branches hain $= 0.20$ . Mispredict rate per branch: Tournament $= 1 - 0.92 = 0.08$ ; TAGE $= 1 - 0.96 = 0.04$ . Misprediction rate per instruction $= 0.20 \times (branch miss rate)$ :

Tournament: $0.20 \times 0.08 = 0.016$ (100 instructions mein 1.6 mispredicts).
TAGE: $0.20 \times 0.04 = 0.008$ (100 mein 0.8).

Har mispredict 192 in-flight instructions tak flush karta hai, toh wasted work mispredict count ke proportional hai. Ratio hai $0.016/0.008 = 2$ : tournament predictor do guna zyada flushes trigger karta hai, toh yeh TAGE ke comparison mein roughly do guna zyada speculative work per instruction throw away karta hai. Concretely, 1000 instructions mein tournament lagbhag $16 \times 192 \approx 3072$ instruction-slots of work waste karta hai versus TAGE ke liye $8 \times 192 \approx 1536$ . Yahi wajah hai ki TAGE ke extra transistors worth it hain — flush rate roughly half karna branchy code par useful throughput roughly double kar deta hai. (Refilled front-end branch target buffer se feed leta hai, jo kahan fetch karna hai yeh batata hai jab whether predict ho jaaye.)

Problem 5.2 (L5)

Corner cases. Har degenerate input ke liye, batao predictor kya karta hai aur kyun yeh safe hai: (a) TAGE lookup jahan koi bhi tagged table match nahi karta. (b) Selector exactly boundary par — value $1$ , aur predictor 1 galat rehta hai jabki predictor 2 sahi, teen branches in a row. (c) Ek TAGE prediction counter apne extreme $+ 3$ par jo phir mispredict karta hai.

Recall Solution 5.2

(a) Koi tag match nahi: base predictor $T_{0}$ par fall back karo (PC-indexed 2-bit counter, history length $L_{0} = 0$ ). $T_{0}$ hamesha exist karta hai aur hamesha answer deta hai — TAGE kabhi undefined nahi hota. Yeh "cold branch" / capacity-miss safety net hai. (b) Boundary crossing: value $1$ predictor 1 choose karta hai. Har branch case 2 hai ( $min (3, sel + 1)$ ): $1 \to 2 \to 3 \to 3$ (saturates). Choice flip ho jaati hai predictor 2 pe jaise hi hum $2$ hit karte hain (pehle branch ke baad), phir harden ho jaati hai. $3$ par saturation runaway rokta hai. (c) Extreme counter mispredict karta hai: $+ 3$ matlab "strongly Taken" lekin actual tha Not-Taken. Signed & saturating hone ki wajah se, yeh truth ki taraf step karta hai: $+ 3 \to + 2$ (abhi bhi Taken predict karta hai — ek wrong outcome ek strongly-trained entry ko flip nahi karna chahiye). Prediction flip karne ke liye kaafi Not-Takens lagte hain ( $+ 3 \to + 2 \to + 1 \to 0 \to - 1$ ). Yeh hysteresis deliberate hai: yeh one-off noise ignore karta hai, sirf sustained new behaviour ke under flip karta hai.

Recall Self-test checklist

Kya tum ab memory se yeh sab kar sakte ho? ::: (1) 2-bit selector ko choice+strength mein split karna; (2) 3-case selector update apply karna; (3) TAGE ka longest-matching provider pick karna aur $T_{0}$ fallback jaanna; (4) allocate-longer-on-miss aur useful bit explain karna; (5) geometric history lengths calculate karna; (6) accuracy ko per-instruction mispredict rate aur wasted work mein convert karna.

Related builds: 5.3.9-Gshare-and-local-predictors (tournament ke andar ke components), 5.3.8-Two-level-adaptive-predictors (jahan se global history registers aate hain), 7.2.5-Cache-coherence-and-branch-predictors (multicore interactions).