Local Branch Predictor

computer-architecture

Definition

Local Branch Predictor

A local branch predictor is a dynamic branch prediction scheme that predicts a branch using only the history of that specific branch, indexed by its PC.

In its simplest form, a table of 2-bit saturating counters is indexed by the low bits of the PC. A two-level adaptive variant adds a local history table: the PC selects a per-branch shift register of recent outcomes, which then indexes a pattern history table of counters.

Unlike a global branch predictor, a local predictor cannot exploit correlations between different branches. It can, however, capture per-branch patterns — such as a single branch that alternates taken / not taken — which a global predictor may miss if that pattern is drowned out by other branches in the global history.

Examples

1-Bit Branch Prediction

Consider the same nested loop as in the global predictor example, but now with a 1-bit local predictor: each branch has its own BHT entry, indexed by its PC.

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

The inner loop (L09) has pattern $\mathrm{T}\text{-}\mathrm{T}\text{-}\mathrm{T}\text{-}\mathrm{NT}$. At start, both BHT entries are PNT.

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

First L09. BHT${}_{L09}=$ PNT $\to$ predict NT. Taken ($s1=3\ne 0$) — misprediction. BHT${}_{L09}\leftarrow$ PT.

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

Second L09. BHT${}_{L09}=$ PT $\to$ predict T. Taken ($s1=2\ne 0$) — correct.

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

Third L09. BHT${}_{L09}=$ PT $\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
BHT L09	PNT	PNT	PT	PT
BHT L11	PNT	PNT	PNT	PNT
Prediction	NT	NT	T	T
Direction	-	T	T	T
Correct?	-	N	Y	Y

Fourth L09. BHT${}_{L09}=$ PT $\to$ predict T. Not taken ($s1=0$) — misprediction. BHT${}_{L09}\leftarrow$ PNT.

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

L11 (outer loop). BHT${}_{L11}=$ PNT $\to$ predict NT. Taken ($s0=1023\ne 0$) — misprediction. BHT${}_{L11}\leftarrow$ 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
BHT L09	PNT	PNT	PT	PT	PT	PNT
BHT L11	PNT	PNT	PNT	PNT	PNT	PNT
Prediction	NT	NT	T	T	T	NT
Direction	-	T	T	T	NT	T
Correct?	-	N	Y	Y	N	N

Comparison with global predictor $2/5$ mispredictions as the global case. But the local predictor has separate counters: L11's counter stays PNT throughout the inner loop and only trains after L11 executes. In subsequent outer loops, L11 predicts correctly, dropping the misprediction rate below the global case. The local predictor isolates each branch's history — L09's exit behaviour never corrupts L11's counter.

The first outer loop gives the same