Direction prediction answers taken or not taken for conditional branches. Target prediction answers where fetch goes next when the branch is taken.
The two answers fail independently. A correct direction with a wrong target still redirects fetch late.
Structure | Predicts | Indexed by |
|---|---|---|
Bimodal table | Direction | Low PC bits |
Gshare table | Direction | PC mixed with global history |
BTB | Target address | Branch PC with tag check |
Return stack | Return target | Call and return pairing |
A bimodal table holds one 2-bit saturating counter per entry, indexed by low PC bits. Counters 0 and 1 predict not taken, counters 2 and 3 predict taken.
Gshare mixes global branch history with the PC before indexing. Correlated branches then use different entries, which cuts aliasing from unrelated PCs sharing one counter.
Aliasing never disappears entirely. Two active branches can still share an entry and untrain each other, which workload phase changes expose quickly.
Predictor | State per entry | Strength | Weakness |
|---|---|---|---|
Bimodal, 4K entries | 2-bit counter | Fast lookup, tiny state | Aliasing on correlated branches |
Gshare, 4K entries, 12-bit history | 2-bit counter | Learns correlated patterns | History must warm up after phase change |
TAGE sketch, tagged tables | Tagged counters plus base bimodal | Long histories without explosion | More complex update and allocation |
A BTB caches recent branch targets indexed by branch PC with a tag check. A hit redirects fetch to the stored target, while a miss falls back to sequential fetch until resolution.
The return stack pushes call targets and pops them at returns. Deep or unbalanced call depth overflows or underflows it, so returns mispredict until it refills.
Indirect branches change target per execution, so a plain BTB underperforms on them. Tagged indirect predictors and compiler layout help; security mitigations add lookup cost, and predictor depth lives in the cpu-design course.
Structure | Hit behavior | Miss behavior |
|---|---|---|
Direct-mapped BTB | Redirect fetch to stored target | Sequential fetch until resolution |
Return stack | Pop returns the call site target | Fall back to BTB or sequential on underflow |
Indirect predictor | Tagged history picks per-context target | Wrong target treated like a BTB miss |
The model below is a plain-SystemVerilog sketch of the mechanism. A bimodal table, a gshare table and a tagged BTB mock train on one 24-branch trace.
class bimodal_c;
int unsigned tab[];
function new(int unsigned n);
tab = new[n];
for (int i = 0; i < n; i++) tab[i] = 1;
endfunction
function bit predict(int unsigned pc);
return tab[pc % tab.size()] >= 2;
endfunction
function void train(int unsigned pc, bit taken);
int unsigned idx = pc % tab.size();
if (taken) begin
if (tab[idx] < 3) tab[idx] = tab[idx] + 1;
end else begin
if (tab[idx] > 0) tab[idx] = tab[idx] - 1;
end
endfunction
endclass
class gshare_c;
int unsigned tab[];
int unsigned hist;
int unsigned hbits;
function new(int unsigned n, int unsigned hb);
tab = new[n];
for (int i = 0; i < n; i++) tab[i] = 1;
hist = 0;
hbits = hb;
endfunction
function int unsigned index(int unsigned pc);
int unsigned mask = (1 << hbits) - 1;
return (pc ^ (hist & mask)) % tab.size();
endfunction
function bit predict(int unsigned pc);
return tab[index(pc)] >= 2;
endfunction
function void train(int unsigned pc, bit taken);
int unsigned idx = index(pc);
if (taken) begin
if (tab[idx] < 3) tab[idx] = tab[idx] + 1;
end else begin
if (tab[idx] > 0) tab[idx] = tab[idx] - 1;
end
hist = ((hist << 1) | (taken ? 1 : 0)) & 15;
endfunction
endclass
class btb_c;
int unsigned valid[];
int unsigned tag[];
int unsigned tgt[];
function new(int unsigned n);
valid = new[n];
tag = new[n];
tgt = new[n];
for (int i = 0; i < n; i++) valid[i] = 0;
endfunction
function bit hit(int unsigned pc);
int unsigned idx = pc % valid.size();
return (valid[idx] != 0) && (tag[idx] == pc);
endfunction
function void install(int unsigned pc, int unsigned t);
int unsigned idx = pc % valid.size();
valid[idx] = 1;
tag[idx] = pc;
tgt[idx] = t;
endfunction
endclass
Nine trains upward saturate the counter at 3, and one not-taken train only steps it to 2. The exit is mispredicted, then the counter relearns.
The index matches but the tag does not, so the first touch of each PC installs its own tag. Every later repeat hits.