Foundations — Tournament and TAGE predictors

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

Parent note Tournament and TAGE predictors padhne se pehle, tumhe usmein aane wala har word aur symbol pata hona chahiye. Yeh page har ek ko scratch se build karta hai — pehle plain words mein, phir picture, phir yeh topic isके bina kyon nahi chal sakta. Upar se neeche padho; har idea uske upar wale pe lean karta hai.

1. Ek branch, aur "taken vs not-taken"

Picture: ek raaste mein fork. Car (processor ka execution flow) fork tak pahunchti hai aur use left ya right jaana hai.

• Taken (T) = jump hota hai (branching road lo).
• Not-taken (NT) = agli instruction pe fall through karo (seedha jao).

Outcome-notation, ek stream ki tarah likhi: T, T, T, T, NT matlab ek branch chaar baar taken hua phir ek baar not-taken — exactly waisa jaisa ek loop jo 4 baar run karta hai lagta hai.

2. PC — woh address jo ek branch ko naam deta hai

Picture: raaste mein har fork ke paas ek signpost hai jisme ek unique number thoka hua hai. Tumhare program ke do alag ifs do alag PCs pe baithe hain.

Topic ko isski kyun zaroorat hai: predictors har fork ke past behaviour ka ek notebook rakhte hain. Notebook ka sahi page dhundne ke liye, tum fork ko uske signpost se — uske PC se — lookup karte ho. Jab parent hash(PC) likhta hai, iska matlab hai "is address ko ek chhoti table-row number mein badlo taaki hum iska notebook page jaldi dhundh sakein."

3. GHR — global history register

Picture: ek conveyor belt jo, maan lo, pichhle 8 results hold karti hai. Naya result left se enter karta hai, sabse purana right se gir jaata hai.

Do flavours jo parent use karta hai:

• Local history — ek alag belt jo sirf ek single branch ke liye rakhi jaati hai (sirf us fork ka apna past T/NT).
• Global history (GHR) — ek shared belt jo har branch ka outcome milaakar record karti hai.

4. Saturating counter — ek guess with confidence

Predictors sirf "T ya NT" store nahi karte. Woh store karte hain kitna sure hain, ek saturating counter use karke.

Ek 2-bit counter ke chaar states hain:

Picture: 4 notches wala ek slider. Har T use right nudge karta hai, har NT use left, lekin yeh kisi bhi end se aage nahi jaata.

Parent do counter shapes use karta hai — dono yaad karo:

• 2-bit unsigned (0..3): selector aur base predictor ke liye use hota hai. Parent ke formula mein min(3, x+1) aur max(0, x-1) bas "count up but don't pass 3, count down but don't pass 0" hain.
• 3-bit signed (−4..+3): TAGE ka prediction counter. Rule: T predict karo agar value $\ge 0$ ho, NT agar negative. Same idea, alag numbering.

5. Accuracy, error rate, aur symbols $a$, $P(\cdot )$

Topic ko isski kyun zaroorat hai: tournament/TAGE ka poora reason $1-a$ ko chhota karna hai. Parent "local 85%, global 87%, tournament 90–93%" jaisi numbers compare karta hai — yeh sab $a$ ki values hain.

6. Tables, tags, aur "useful" bit (TAGE vocabulary)

TAGE apne notebooks ko tables ke roop mein store karta hai. Tumhe teen cheezein pata honi chahiye jo ek entry hold karti hai.

Picture: ek filing cabinet. Index drawer number hai; tag woh naam label hai jo tum check karte ho yeh ensure karne ke liye ki tumne apna folder pakda hai na kisi aur ka; counter folder ka content hai; useful bit ek sticky note hai jo kehti hai "mujhe rakho."

Lock karne wale symbols: $T_0$ base (no-history) table hai; $T_1,T_2,\dots ,T_n$ tagged tables hain lengths $L_1<L_2<\cdots <L_n$ ke saath. Parent ka "longest matching table" simply matlab hai: un sab drawers mein se jinke tag match kiya, woh use karo jiska $L_i$ sabse bada ho — sabse specific memory.

Prerequisite map

Vault mein yeh kahan connect karte hain

• History-belt idea seedha 5.3.8-Two-level-adaptive-predictors se grow karta hai.
• Local vs global belts aur PC ko history ke saath hash karna 5.3.9-Gshare-and-local-predictors ka dil hai.
• Kyon ek galat guess expensive hai yeh 5.4.2-Speculative-execution mein rehta hai aur 5.3.11-Branch-target-bufers ke saath phir se pay kiya jaata hai.
• Cores mein history share karna 7.2.5-Cache-coherence-and-branch-predictors mein subtle issues raise karta hai.

Equipment checklist

Parent padhne se pehle har ek ka answer do — agar koi stumps kare, toh uska section dobara padho.