Foundations — Tournament and TAGE predictors

Before you can read the parent note Tournament and TAGE predictors, you need every word and symbol it throws at you. This page builds each one from nothing — plain words first, then the picture, then why the topic can't live without it. Read top to bottom; each idea leans on the one above it.

1. A branch, and "taken vs not-taken"

The picture: a fork in a road. The car (the processor's flow of execution) reaches the fork and must go left or right.

• Taken (T) = the jump happens (take the branching road).
• Not-taken (NT) = fall through to the next instruction (go straight).

Outcome-notation, written as a stream: T, T, T, T, NT means a branch was taken four times then not-taken once — exactly what a loop that runs 4 times looks like.

2. PC — the address that names a branch

The picture: every fork on the road has a signpost with a unique number nailed to it. Two different ifs in your program sit at two different PCs.

Why the topic needs it: predictors keep a notebook of past behaviour per fork. To find the right page of the notebook, you look up the fork by its signpost — its PC. When the parent writes hash(PC), it means "turn this address into a small table-row number so we can find its notebook page fast."

3. GHR — the global history register

The picture: a conveyor belt holding, say, the last 8 results. New result enters the left, oldest drops off the right.

Two flavours the parent uses:

• Local history — a separate belt kept for one single branch (only that fork's own past T/NT).
• Global history (GHR) — one shared belt recording every branch's outcome mixed together.

4. The saturating counter — a guess with confidence

Predictors do not just store "T or NT." They store how sure they are, using a saturating counter.

A 2-bit counter has four states:

The picture: a slider with 4 notches. Each T nudges it right, each NT nudges it left, but it cannot slide past either end.

The parent uses two counter shapes — memorise both:

• 2-bit unsigned (0..3): used for the selector and the base predictor. min(3, x+1) and max(0, x-1) in the parent's formula are just "count up but don't pass 3, count down but don't pass 0."
• 3-bit signed (−4..+3): TAGE's prediction counter. Rule: predict T if the value $\ge 0$, NT if negative. Same idea, different numbering.

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

Why the topic needs it: the whole reason for tournament/TAGE is to make $1-a$ smaller. The parent compares numbers like "local 85%, global 87%, tournament 90–93%" — those are all values of $a$.

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

TAGE stores its notebooks as tables. You must know three things an entry holds.

The picture: a filing cabinet. The index is the drawer number; the tag is the name label you check to make sure you grabbed your folder and not a stranger's; the counter is the folder's contents; the useful bit is a sticky note saying "keep me."

Symbols to lock in: $T_0$ is the base (no-history) table; $T_1,T_2,\dots ,T_n$ are the tagged tables with lengths $L_1<L_2<\cdots <L_n$. The parent's "longest matching table" simply means: of all the drawers whose tag matched, use the one with the biggest $L_i$ — the most specific memory.

Prerequisite map

Where these connect in the vault

• The history-belt idea grows straight out of 5.3.8-Two-level-adaptive-predictors.
• Local vs global belts and hashing PC with history are the heart of 5.3.9-Gshare-and-local-predictors.
• The reason a wrong guess is expensive lives in 5.4.2-Speculative-execution and is paid for again with 5.3.11-Branch-target-bufers.
• Sharing history across cores raises subtle issues in 7.2.5-Cache-coherence-and-branch-predictors.

Equipment checklist

Answer each before reading the parent — if any stumps you, re-read its section.