Which direction predictor should a small in-order core carry, once its answer has to arrive in time?
I compared six predictors at equal table budget. I measured them on five programs I set aside before any measurement, and on a stress program with a thousand branch sites. The most accurate predictor is not the fastest. The answer depends on one number: how many cycles the predictor takes to answer.
The caveat from the earlier articles still holds: every cycle count in this post comes from a model I wrote, not from silicon. The model follows its rules exactly, and several independent checks show that. Whether those rules describe a real core is a separate question. Every measured number below comes from a result file that a script produced.
Setup
The core is the one from the branch article, with the same five stages and caches. A conditional branch is verified in EX, reading its operands with the forwarding rules, as every other instruction does. Four rules matter here:
- A correctly predicted taken branch redirects fetch in ID, which costs 1 cycle.
- A wrong direction is found in EX, which costs 2 cycles.
- JAL keeps the static rule. Returns are resolved in EX in every variant, so the study compares conditional branches only.
- A predictor may answer late. If its answer takes
Lcycles after the branch reaches ID, a predicted-taken branch redirects fetchLcycles later, so it costs1 + Lcycles.
The budget counts table bits: 1, 4 and 16 KiB are 8192, 32768 and 131072 bits. Global history registers are not counted, which is the usual convention for this kind of comparison. The predictors are:
- Static: backward branches taken, forward not taken. No table.
- Bimodal: 2-bit saturating counters, indexed by the word address, starting weakly not taken.
- Gshare: the same counters, indexed by the word address xor a global history as long as the index.
- Tournament: a bimodal table, a gshare table and a chooser that picks whichever has been right more often where they disagree.
- Perceptron: one row per word address, a bias and 16 weights of 8 bits, trained when it is wrong or when its output is below 44.
- Overriding: a fast bimodal table with an eighth of the budget, and a slow perceptron with the rest. The fast table redirects fetch at once. Where the slow perceptron disagrees, the correction arrives when its answer does, and the slow answer is final.
None of these parameters is tuned. Each follows from the budget, and I fixed the perceptron's history length of 16 before measuring.
What the model does not model
- Trace-driven predictors. A predictor sees the outcomes of the correct path only. Wrong-path fetches do not pollute its tables, and updates have no latency.
- A fixed penalty. A wrong direction costs 2 cycles, which is what a five-stage pipeline gives. A deeper pipeline would charge more, and that would change the balance below.
- A fixed latency. The slow predictor's latency is a parameter I set, and I sweep it from 0 to 3 cycles. I did not design the circuit behind it.
- Indirect branches and returns. Both are resolved in EX here, so they cost the same in every variant.
The corpus
Each program is a small C program compiled for rv32im, with no library. Its exit value is checked against a native run of the same C. The five training programs (isort, lexer, hashprobe, sieve, collatz) helped me check the design, and the five held-out programs (qsort, bsearch, tree, strsearch, rle) are the basis of the results. The stress program has 998 distinct branch addresses, each with its own bias. It is reported apart from the means.
| Program | Split | Instructions | Conditional branches | Branches per 100 instructions | Branch sites |
|---|---|---|---|---|---|
| isort | train | 148,444 | 47,971 | 32.3 | 5 |
| lexer | train | 102,322 | 26,518 | 25.9 | 10 |
| hashprobe | train | 69,112 | 13,609 | 19.7 | 9 |
| sieve | train | 119,949 | 36,100 | 30.1 | 4 |
| collatz | train | 3,849,535 | 1,341,100 | 34.8 | 6 |
| qsort | test | 66,578 | 12,345 | 18.5 | 6 |
| bsearch | test | 438,722 | 127,112 | 29.0 | 6 |
| tree | test | 363,613 | 98,158 | 27.0 | 11 |
| strsearch | test | 69,509 | 13,652 | 19.6 | 5 |
| rle | test | 90,205 | 22,852 | 25.3 | 9 |
| footprint | stress | 3,262,797 | 398,800 | 12.2 | 998 |
The held-out programs have 5 to 11 branch sites each. That is the reason the table size hardly matters on them, and the stress program exists to show what happens when it does.
Checks
Before I trust any number, I check four things.
- An independent reference. I wrote the six predictors again in Python, from the rules, and ran them on the same branch traces: 198 pairs (six predictors, three budgets, eleven traces), with no mismatch. The collatz trace is cut to its first 200,000 branches for this check, to keep the Python run short.
- Known answers. On synthetic traces whose behaviour is known, all 12 checks pass. One of them is instructive. A branch that alternates taken and not taken defeats a 2-bit counter that starts weakly not taken: the counter moves between two states that both predict wrongly, so it misses all 10,000 branches. Gshare learns the alternation and misses 8.
- The model against the simulator. In all 30 model runs, the number of mispredictions the timing model counts equals the number the accuracy simulator counts for the same predictor.
- Two timing models. The scoreboard and the stage-thread model give the same cycle counts in all 30 runs. The branch article's variants are unchanged: the cycle counts of fib and bubble under H0 to H5 are the same as published, in both models.
Accuracy
On the held-out programs, the mean mispredictions per 1000 instructions at 4 KiB are 32.2 for the perceptron, 34.2 for the tournament, 35.5 for the bimodal table and 35.9 for gshare. The static rule gives 133.6. The perceptron is 9 % below the bimodal table. It is the best predictor on four of the five programs: qsort, tree, strsearch and rle. On bsearch the bimodal table is marginally better, at 50.1 against 50.6. The training programs give the same ranking, with the perceptron first at 36.3, so the choice was not tuned on the held-out set.
| Predictor | Table | Held-out mean, MPKI | Train mean, MPKI | Stress program, MPKI |
|---|---|---|---|---|
| static | - | 133.63 | 99.42 | 58.36 |
| bimodal | 1 KiB | 35.50 | 38.11 | 37.10 |
| bimodal | 4 KiB | 35.50 | 38.11 | 35.20 |
| bimodal | 16 KiB | 35.50 | 38.11 | 35.20 |
| gshare | 1 KiB | 36.01 | 39.69 | 60.31 |
| gshare | 4 KiB | 35.89 | 39.56 | 59.28 |
| gshare | 16 KiB | 35.82 | 40.56 | 56.08 |
| tournament | 1 KiB | 34.55 | 37.82 | 41.87 |
| tournament | 4 KiB | 34.24 | 37.39 | 37.33 |
| tournament | 16 KiB | 34.18 | 37.33 | 36.58 |
| perceptron | 1 KiB | 32.21 | 36.28 | 42.09 |
| perceptron | 4 KiB | 32.21 | 36.28 | 36.97 |
| perceptron | 16 KiB | 32.21 | 36.28 | 33.47 |
| overriding | 1 KiB | 32.21 | 36.28 | 42.40 |
| overriding | 4 KiB | 32.21 | 36.28 | 37.29 |
| overriding | 16 KiB | 32.21 | 36.28 | 33.90 |
The budget changes nothing on the held-out programs, because they have so few branch sites that their table entries do not collide. On the stress program it matters. The perceptron goes from 42.1 to 37.0 to 33.5 mispredictions per 1000 instructions as the budget grows from 1 to 16 KiB. At 1 KiB it has only 60 rows for a thousand sites, so unrelated branches share a row. The bimodal table, with 4096 counters, hardly moves, from 37.1 to 35.2. Gshare does worse than the static rule on the stress program at 1 and 4 KiB. Its global history is shared by nearly a thousand unrelated branches, so the history tells it little.
On the held-out programs the overriding predictor's final decisions are the perceptron's, so its mispredictions are the same: its slow table is large enough there. Its fast table disagrees with the slow one on 1.3 % of the branches in rle, 4.7 % in strsearch, 11 % in qsort and bsearch, and 15 % in tree.
Cycles
The mispredictions above are not the cost that matters here. A correctly predicted taken branch costs 1 + L cycles, and a wrong direction costs 2. For a single predictor, the cycle count is close to 2 × mispredictions + (1 + L) × correct taken predictions. A slow answer taxes every taken prediction, while accuracy saves only 2 cycles per error.
| Program | Static (H2) | Bimodal (H6) | Gshare (H7) | Tournament (H8) | Perceptron, 2 cycles (H9) | Overriding, 2 cycles (H10) |
|---|---|---|---|---|---|---|
| qsort | 105,549 (+14.4 %) | 92,287 | 92,213 (-0.1 %) | 92,016 (-0.3 %) | 95,908 (+3.9 %) | 93,725 (+1.6 %) |
| bsearch | 952,814 (+15.8 %) | 823,010 | 825,762 (+0.3 %) | 822,960 (-0.0 %) | 879,000 (+6.8 %) | 840,101 (+2.1 %) |
| tree | 1,241,364 (+10.1 %) | 1,127,780 | 1,124,552 (-0.3 %) | 1,125,232 (-0.2 %) | 1,141,425 (+1.2 %) | 1,145,898 (+1.6 %) |
| strsearch | 89,444 (+0.8 %) | 88,708 | 89,086 (+0.4 %) | 88,776 (+0.1 %) | 103,383 (+16.5 %) | 89,047 (+0.4 %) |
| rle | 133,499 (+17.4 %) | 113,673 | 113,865 (+0.2 %) | 113,772 (+0.1 %) | 129,499 (+13.9 %) | 113,868 (+0.2 %) |
The perceptron saves mispredictions and loses cycles. On qsort it avoids 206 errors, which is worth about 410 cycles, but its taken predictions wait two cycles each, and the total is 3,621 cycles more than the bimodal table, or 3.9 %. Gshare and the tournament predictor stay within half a percent of the bimodal table on every program, so their accuracy is not worth the extra table.
Latency is the variable that decides the comparison. I swept the slow answer from 0 to 3 cycles over the five held-out programs:
| Answer latency (cycles) | Perceptron alone (H9) | Overriding (H10) |
|---|---|---|
| 0 | 2,238,531 (-0.31 %) | 2,247,811 (+0.10 %) |
| 1 | 2,293,873 (+2.16 %) | 2,265,225 (+0.88 %) |
| 2 | 2,349,215 (+4.62 %) | 2,282,639 (+1.66 %) |
| 3 | 2,404,557 (+7.09 %) | 2,300,053 (+2.43 %) |
The bimodal table answers at once, and it totals 2,245,458 cycles. The perceptron wins only with no latency at all, and by 0.3 %. Each cycle of latency costs it about 2.5 %. Overriding loses less, because the fast table redirects most branches in time. It still never beats the bimodal table in this range.
The idea I tested: overriding
Overriding is a way to keep a slow predictor's accuracy without paying its latency on every branch. The fast table answers at once, and the slow one corrects it only where they disagree. Its cost is therefore the disagreement rate. On this corpus, that rate is 1 to 15 % of the branches, and the accuracy it keeps over the bimodal table is about 3 mispredictions per 1000 instructions. That gain does not cover the corrections, and the design loses here. The result is specific to these programs and this latency model. A workload where the slow predictor is much more accurate than the fast one would look different.
Limitations
- Few programs. Five held-out programs, of 66,000 to 440,000 instructions each, is a small sample. The stress program is synthetic by design, with its bias chosen per site.
- My parameters. The 2-cycle mispredict penalty, the 1, 4 and 16 KiB budgets, the history length of 16 and the latency values are my choices. A deeper pipeline would raise the penalty, and that would favour accuracy.
- A model of latency. A predictor's answer is a fixed delay, not the result of a circuit. Real predictors pipeline their lookups, which changes the numbers.
- Trace-driven accuracy. The mispredictions are those of the correct path. Wrong-path fetches do not disturb the tables here.
How far can this be trusted?
The implementation follows its rules, and the checks show it: an independent reference agrees on all 198 pairs, the model agrees with the simulator on every run, and both timing models agree. None of that says the rules describe a real core. The robust result is the shape of the trade-off: on these programs, the time a predictor takes to answer is worth more than its accuracy. The size of the effect depends on the pipeline, and the model does not measure that.
Reproduction
Everything runs from the cpu-systemc folder. The simulator and the accuracy tool come first, then the corpus, then the studies:
make # build build/cpusim and build/bpsim
python3 scripts/gen_footprint.py
python3 scripts/corpus.py # the eleven programs: ISS value against the native run, branch traces
python3 scripts/bp_reference.py # the independent reference and the known answers
python3 scripts/bp_study.py # accuracy of every program, and cycles of the held-out programs
python3 scripts/bp_latency.py # the latency sweep
python3 scripts/predictor_numbers.py # the tables and figures of this articleEach script writes its results to results/, as JSON. The branch traces go to tmp/bp and are not kept in the repository.