Global Branch Predictor

computer-architecture

Definition

Global Branch Predictor

A global branch predictor is a dynamic branch prediction scheme that predicts a branch using the outcomes of all recent branches, not just the current one.

It maintains a global history register — a shift register of the last $m$ branch outcomes — and uses this history to index a pattern history table of 2-bit saturating counters. Because the history captures correlations between different branches, a global predictor can exploit patterns like if branch A is taken, branch B is likely not taken.

Examples

1-Bit Branch Prediction

Consider a 1-bit global predictor for the following code:

li s0, 1024
xloop: 
	li s1, 4
yloop: 
	mv a0, s0
	mv a1, s1
	jal ra, do_something
	addi s1, s1, -1
	bnez s1, yloop        # L09
	addi s0, s0, -1
	bnez s0, xloop        # L11

For the inner loop (L09), we have a branch pattern:

$$\mathrm{T}-\mathrm{T}-\mathrm{T}-\mathrm{NT}$$

and a nested loop pattern:

$$(\mathrm{T}-\mathrm{T}-\mathrm{T}-\mathrm{NT})\mathrm{T}(\mathrm{T}-\mathrm{T}-\mathrm{T}-\mathrm{NT})\mathrm{T}\dots$$

We know that L09 loops for four iterations. The low bit of the PC for L09 and L11 happens to be the same, so both branches alias to the same BHT entry. With a 1-bit predictor, a single shared counter governs all predictions. At start, the shared entry is PNT (predict not taken).

Branch	Start	L09	L09	L09	L09	L11
BTB entry L09	Y
BTB entry L11	Y
Shared BHT	PNT
Prediction	NT
Direction	-
Correct?	-

First L09. BHT $=$ PNT $\to$ predict NT. The branch is taken ($s1=3\ne 0$) — misprediction. The shared counter flips to PT.

Branch	Start	L09	L09	L09	L09	L11
BTB entry L09	Y	Y
BTB entry L11	Y	Y
Shared BHT	PNT	PNT
Prediction	NT	NT
Direction	-	T
Correct?	-	N

Second L09. BHT $=$ PT $\to$ predict T. The branch is taken again ($s1=2\ne 0$) — correct. The counter stays PT.

Branch	Start	L09	L09	L09	L09	L11
BTB entry L09	Y	Y	Y
BTB entry L11	Y	Y	Y
Shared BHT	PNT	PNT	PT
Prediction	NT	NT	T
Direction	-	T	T
Correct?	-	N	Y

Third L09. BHT $=$ PT $\to$ predict T. The branch is taken ($s1=1\ne 0$) — correct. The counter stays PT.

Branch	Start	L09	L09	L09	L09	L11
BTB entry L09	Y	Y	Y	Y
BTB entry L11	Y	Y	Y	Y
Shared BHT	PNT	PNT	PT	PT
Prediction	NT	NT	T	T
Direction	-	T	T	T
Correct?	-	N	Y	Y

Fourth L09. BHT $=$ PT $\to$ predict T. But the branch is not taken ($s1=0$) — misprediction. The counter flips back to PNT.

Branch	Start	L09	L09	L09	L09	L11
BTB entry L09	Y	Y	Y	Y	Y
BTB entry L11	Y	Y	Y	Y	Y
Shared BHT	PNT	PNT	PT	PT	PT
Prediction	NT	NT	T	T	T
Direction	-	T	T	T	NT
Correct?	-	N	Y	Y	N

L11 (outer loop). BHT $=$ PNT $\to$ predict NT. The branch is taken ($s0=1023\ne 0$) — misprediction. The shared counter flips to PT.

Branch	Start	L09	L09	L09	L09	L11
BTB entry L09	Y	Y	Y	Y	Y	Y
BTB entry L11	Y	Y	Y	Y	Y	Y
Shared BHT	PNT	PNT	PT	PT	PNT	PNT
Prediction	NT	NT	T	T	T	NT
Direction	-	T	T	T	NT	T
Correct?	-	N	Y	Y	N	N

Misprediction rate $5$ branches ($4$ inner $+$ $1$ outer). In the first iteration we mispredict $2$ of them (the first L09 and the L11). After L11, the shared counter is back at PT, so subsequent outer iterations start with a correct prediction for the first L09, giving $\sim 40\%$ misprediction rate overall.

Per outer loop iteration we execute

2-Bit Branch Prediction

Now replace the 1-bit counter with a 2-bit saturating counter. States: PWNT (weakly NT), PWT (weakly T), PST (strongly T). Same aliasing setup — L09 and L11 share one entry. Start: BHT $=$ PWNT.

Branch	Start	L09	L09	L09	L09	L11
BTB entry L09	Y
BTB entry L11	Y
Shared BHT	PWNT
Prediction	NT
Direction	-
Correct?	-

First L09. BHT $=$ PWNT (weakly NT) $\to$ predict NT. Taken ($s1=3\ne 0$) — misprediction. Counter increments to PWT (weakly T).

Branch	Start	L09	L09	L09	L09	L11
BTB entry L09	Y	Y
BTB entry L11	Y	Y
Shared BHT	PWNT	PWNT
Prediction	NT	NT
Direction	-	T
Correct?	-	N

Second L09. BHT $=$ PWT (weakly T) $\to$ predict T. Taken ($s1=2\ne 0$) — correct. Counter increments to PST (strongly T).

Branch	Start	L09	L09	L09	L09	L11
BTB entry L09	Y	Y	Y
BTB entry L11	Y	Y	Y
Shared BHT	PWNT	PWNT	PWT
Prediction	NT	NT	T
Direction	-	T	T
Correct?	-	N	Y

Third L09. BHT $=$ PST (strongly T) $\to$ predict T. Taken ($s1=1\ne 0$) — correct.

Branch	Start	L09	L09	L09	L09	L11
BTB entry L09	Y	Y	Y	Y
BTB entry L11	Y	Y	Y	Y
Shared BHT	PWNT	PWNT	PWT	PST
Prediction	NT	NT	T	T
Direction	-	T	T	T
Correct?	-	N	Y	Y

Fourth L09. BHT $=$ PST (strongly T) $\to$ predict T. Not taken ($s1=0$) — misprediction. Counter decrements to PWT (weakly T).

Branch	Start	L09	L09	L09	L09	L11
BTB entry L09	Y	Y	Y	Y	Y
BTB entry L11	Y	Y	Y	Y	Y
Shared BHT	PWNT	PWNT	PWT	PST	PST
Prediction	NT	NT	T	T	T
Direction	-	T	T	T	NT
Correct?	-	N	Y	Y	N

L11 (outer loop). BHT $=$ PWT (weakly T) $\to$ predict T. Taken ($s0=1023\ne 0$) — correct. Counter increments to PST (strongly T).

Branch	Start	L09	L09	L09	L09	L11
BTB entry L09	Y	Y	Y	Y	Y	Y
BTB entry L11	Y	Y	Y	Y	Y	Y
Shared BHT	PWNT	PWNT	PWT	PST	PST	PWT
Prediction	NT	NT	T	T	T	T
Direction	-	T	T	T	NT	T
Correct?	-	N	Y	Y	N	Y

Hysteresis at work $2/5$). After the first iteration the counter sits at PST (strongly T). In subsequent outer loops, only the inner loop exit is mispredicted (Y Y Y N Y — $1/5$). The 2-bit predictor converges to a better steady state than the 1-bit case because hysteresis prevents a single NT from flipping the prediction all the way back to NT — it only drops from PST to PWT, still in taken territory.

The first iteration mispredicts only the first and fourth L09 (N Y Y N Y —