THE FOLD / CHEAT / THE SHORTCUT / THE BRANCH TARGET BUFFER
THE BRANCH TARGET BUFFER
99.8% accurate and wrong every single time
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Two different questions get asked at the same instruction. Will it branch? and where to? The first has two answers and is easy. The second has as many answers as there are addresses, and is not.
LIT verified live. on 1,000 executions of one indirect call that cycles through four targets, the direction predictor is right 998 of 1,000 — the branch is always taken and it learns that in two tries. Over the very same 1,000 executions, a one-entry BTB keyed on the program counter predicts the target correctly 0 times. Same instruction, same run: 99.8% and 0%. Give the BTB the previous target as its index and it reaches 995; make the targets random instead of cyclic and it falls to 254.
LIT verified live. on 1,000 executions of one indirect call that cycles through four targets, the direction predictor is right 998 of 1,000 — the branch is always taken and it learns that in two tries. Over the very same 1,000 executions, a one-entry BTB keyed on the program counter predicts the target correctly 0 times. Same instruction, same run: 99.8% and 0%. Give the BTB the previous target as its index and it reaches 995; make the targets random instead of cyclic and it falls to 254.
2 HOW IT WAS WEAVED · AI + HUMAN
Branch target buffers and the direction/target split are textbook microarchitecture; indirect-branch predictors keyed on target history are the standard fix.
AVAN (AI) built the case where the two numbers separate as far as they can go, and instrumented both predictors on one instruction stream so the comparison is not between benchmarks. The result that matters is not that the BTB fails, it is that a headline of ‘99.8% branch prediction accuracy’ is true while the branch is mispredicted every single time.
AVAN (AI) built the case where the two numbers separate as far as they can go, and instrumented both predictors on one instruction stream so the comparison is not between benchmarks. The result that matters is not that the BTB fails, it is that a headline of ‘99.8% branch prediction accuracy’ is true while the branch is mispredicted every single time.
3 ONE DIMENSION
One branch. Two predictions. Only one of them is right.
4 TWO DIMENSIONS · INTERACTIVE
Step the call and watch the two predictors disagree.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that indirect calls need a smarter predictor. The inverse is that accuracy is a property of the question, not of the instruction, and averaging hides exactly the cases you care about. The 99.8% and the 0% are measured on the same branch in the same run; nothing about the aggregate is false, and nothing about it is useful. Read backwards, every reported accuracy is a weighted average over a distribution of questions someone else chose — and the hard questions are always the rare ones, so they always weigh least.
LIT on 1,000 executions of one indirect call cycling through four targets the direction predictor is right 998 of 1,000 while a one-entry BTB keyed on the program counter predicts the target correctly 0 times - same instruction, same run, 99.8% and 0% - and keying the BTB on the previous target reaches 995, which falls to 254 when the targets are random instead of cyclic
FIG Branch target buffers and the direction/target split are textbook microarchitecture; indirect predictors keyed on target history are the standard fix. AVAN built the case where the two numbers separate as far as they can and instrumented both on ONE instruction stream, so the comparison is not between benchmarks. The result that matters is not that the BTB fails - it is that a headline of '99.8% branch prediction accuracy' is true while the branch is mispredicted every single time.
FIG Branch target buffers and the direction/target split are textbook microarchitecture; indirect predictors keyed on target history are the standard fix. AVAN built the case where the two numbers separate as far as they can and instrumented both on ONE instruction stream, so the comparison is not between benchmarks. The result that matters is not that the BTB fails - it is that a headline of '99.8% branch prediction accuracy' is true while the branch is mispredicted every single time.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE SHORTCUT · David Lee Wise (ROOT0), with AVAN