Branches hurt because a pipelined processor has to fetch the next instruction before it knows what the next instruction is. It must guess, and every wrong guess throws away work that was already done. On a small core, a wrong guess costs a couple of cycles. On a large core, it can cost twenty cycles times several instructions per cycle, so the quality of that guess becomes one of the most important things in the whole design. This article explains exactly what the processor does not know when a branch arrives, how often that matters, how to work out the cost, and what a predictor has to do.
12 min read | Beginner to Intermediate
What You'll Learn
- Explain why fetching must continue before a branch is decided
- Calculate the cost of branches from their frequency, accuracy and penalty
- List the three questions a branch predictor must answer
- Describe speculation and how a wrong guess is undone
The Problem
A pipeline fetches a new instruction in every cycle. To do that, it needs the next address at the start of every cycle. For most instructions the next address is simply PC + 4. But a branch or a jump can send the program somewhere else, and in a five-stage pipeline the decision is not made until the third stage. For two cycles, the processor has to fetch something, without knowing what.
It could wait, but that would cost two cycles on every branch, taken or not. Instead it guesses, and continues working on the guess. If the guess was right, no time was lost. If it was wrong, the instructions fetched after the branch must be removed, which is the flush described in Load-Use Stalls and Control Hazards. The number of cycles lost is the branch penalty or misprediction penalty.
Working on a guess before knowing it is right is called speculation. It is one of the central ideas in modern processors. The processor does not just fetch on a guess. A large core decodes, renames and even executes instructions on the guess, and those are only made permanent once every branch before them has been confirmed.
How Often Does It Happen?
Branches are common. In one test of six small programs, between one in seven and more than one in three executed instructions was a conditional branch. Typical integer programs run a branch about every five or six instructions. Most of them are taken. Loops are the main reason, because a loop's branch goes back to the top on every pass except the last.
A large core may look ahead hundreds of instructions. If there is a branch every six instructions, a window of 300 instructions contains about 50 branches, all still unresolved. The chance that every guess is right is the accuracy raised to the power of 50. At 95 percent accuracy that is only about 8 percent, so most of the instructions at the end of the window would be wasted work. At 99.5 percent it is about 78 percent. That is why large cores need such high accuracy: small differences compound over many branches.
Working Out the Cost
The cost in CPI, cycles per instruction, follows from three numbers:
CPI lost to branches = branches per instruction x fraction predicted wrongly x penalty
Take one branch in five instructions. The picture shows the result for two pipelines, one with a 2-cycle penalty and one with a 15-cycle penalty:
For the small pipeline, a poor predictor barely matters: going from 80 to 99 percent gains less than a tenth of a cycle. For the deep pipeline, the same change takes the CPI from 1.60 to 1.03. And a large core should run several instructions per cycle, so losing the same number of cycles costs even more. If a core could finish 4 instructions per cycle, its ideal CPI is 0.25. Adding 0.3 cycles per instruction for branches would more than double its run time.
Quick Check
Q: A program has a branch every 6 instructions, predicted with 96 percent accuracy, on a core with a 12-cycle penalty. What does this add to the CPI?
Show Answer
1/6 x 0.04 x 12 = 0.08 cycles per instruction. On a core with an ideal CPI of 1, that is 8 percent; on a core with an ideal CPI of 0.25, it is 32 percent of the run time added.
The Three Questions
A branch predictor has to work in the fetch stage, when the instruction has not even been decoded. In the time it takes to read the instruction from memory, it must give an answer to three questions, knowing only the address:
- Is there a branch here at all? The processor has not decoded the instruction yet, so it must remember which addresses hold branches.
- If so, will it be taken? This is the direction, and it is the hard question for conditional branches.
- If taken, where does it go? The target address must be known right away, even though the instruction holds it in encoded form or a register holds it.
Different kinds of control transfer are hard for different reasons:
| Kind | Direction | Target |
|---|---|---|
| conditional branch (beq, bne ...) | hard: depends on data | easy: fixed offset from the PC |
| direct jump or call (jal) | always taken | easy: fixed offset from the PC |
| return (ret) | always taken | changes with the caller |
| indirect jump (jalr), such as a virtual call | always taken | hard: comes from a register |
Static Prediction, BTBs and Return Address Stacks deals with finding targets. Dynamic Predictors: Bimodal and gshare deals with direction.
Why Branches Are Predictable at All
It seems strange that a machine could guess the future, but programs are very regular. The branch at the bottom of a loop that runs a thousand times goes the same way 999 times. A check for an error is almost never true. An if inside a loop often follows a pattern. Some branches depend on an earlier one: if the program just tested that a pointer is valid, it will test the same thing again nearby. A processor that simply remembers what each branch did last time will be right most of the time.
Some branches really are unpredictable. The branch in the core of a sort or a compression program can depend directly on the data, and if the data is random, no predictor can beat 50 percent. In one test, a simple predictor was right about 99.8 percent of the time on an array loop, but only about 71 percent of the time on a program that multiplied by testing each bit of random numbers. Those few hard branches often account for most of the mispredictions in a program.
Where Does This Matter?
Programmers can sometimes see the effect directly. A loop over an array that adds up only the values above a threshold can run several times faster on sorted data than on the same data in random order, because on sorted data the if becomes perfectly predictable. Performance-critical code, such as sorting routines in standard libraries, is often written without branches on the data, using arithmetic or conditional moves instead, so that it pays no misprediction cost.
Undoing a Wrong Guess
Recovery has to leave no trace of the wrong path. In a five-stage pipeline this is easy, because the wrong instructions are still in the first two stages and have changed nothing. The hardware just turns them into bubbles and loads the correct address into the program counter.
On a large core, recovery is far more involved. Wrong-path instructions may have been decoded, given resources and even executed. The processor must find which instructions came after the branch, discard all of them, restore its record of which register holds what, and restart fetching. This must take as few cycles as possible, and the instructions on the correct path that were earlier than the branch must carry on. Out-of-Order Execution and Register Renaming explains the reorder buffer that makes this possible.
Stores are a special case. A store on the wrong path must never reach memory, because it could not be taken back. So stores wait in a buffer until they are certain, as Load/Store Queues and Memory Disambiguation describes.
Wrong-path work also costs energy. Every instruction fetched and thrown away burned power for nothing. On deep designs that can be a noticeable share of the total, so a better predictor saves power as well as time.
A Security Note
Speculation was long thought to be invisible, since a wrong-path instruction leaves no mark on registers or memory. In 2018, researchers showed this was not quite true. Wrong-path instructions can load data into the cache, and a careful program can detect that afterwards by timing its own memory accesses. Attacks based on this, known as Spectre, can read data the program should not see. Processors and operating systems now include defenses, and they are a good reminder that "invisible" hardware behavior only means invisible to correct programs.
Quick Check
Q: A wrong-path load in a five-stage pipeline is flushed before it reaches MEM. A wrong-path load in a large core does reach the cache before being canceled. Does that change the program's results?
Show Answer
No. The loaded value is thrown away, so registers and memory are as if it never ran. Only the cache contents and the timing differ, which is what makes the attacks described above possible.
What Designers Can Do
There are four ways to reduce the cost of branches, and real designs use all of them. Lower the penalty, by resolving branches earlier or restarting faster. Predict better, which is the rest of this chapter. Have fewer branches, for example through compilers that inline functions, unroll loops or use conditional moves. And reduce the effect of a miss, by fetching from both paths or by keeping decoded instructions ready. A small core stops after a very simple prediction, because the penalty is small. A large core spends a significant part of its area on prediction, because nothing else gives as much.
The choice is also a matter of timing. A predictor must give its answer within one cycle at the front of the pipeline, or fetch falls behind. So a very large predictor that takes two cycles to read can lose time on every taken branch, even while it improves accuracy. Many designs therefore use a small, fast predictor backed by a larger, slower one that can overrule it a cycle or two later.
Common Mistakes
Mistake #1: Quoting accuracy without the penalty
A predictor that is right 95 percent of the time may be excellent on a five-stage core and poor on a twenty-stage one. Always multiply through to lost cycles per instruction.
Mistake #2: Assuming most of the misses are spread evenly
A few hard branches often cause most of the mispredictions. Look at which branches miss, because code changes can sometimes remove those few.
Mistake #3: Forgetting jumps and returns
Unconditional transfers are always taken, but their target must still be known in the fetch stage. A design that only predicts conditional branches still loses cycles on every call and return.
Practice Exercise
Challenge: Is a Better Predictor Worth It?
A core has an ideal CPI of 0.5, a 14-cycle penalty, and one branch in six instructions. These numbers are assumptions for this exercise. (a) What is its CPI at 92 percent accuracy? (b) What is it at 97 percent? (c) What speedup does the better predictor give? (d) If the same predictor went on a five-stage core with an ideal CPI of 1 and a 2-cycle penalty, what speedup would it give?
Hint
Add the branch cost to the ideal CPI. The speedup is the old CPI divided by the new CPI.
Solution
(a) 0.5 + 1/6 x 0.08 x 14 = 0.5 + 0.187 = 0.687. (b) 0.5 + 1/6 x 0.03 x 14 = 0.5 + 0.07 = 0.57. (c) 0.687 / 0.57 = 1.21. (d) Old: 1 + 1/6 x 0.08 x 2 = 1.027. New: 1 + 1/6 x 0.03 x 2 = 1.01. The speedup is 1.017, under 2 percent. The same improvement is worth 21 percent on the large core and almost nothing on the small one.
Summary
- A pipeline must fetch before a branch is decided, so it guesses and works on the guess, which is called speculation.
- CPI lost = branches per instruction x wrong fraction x penalty.
- A predictor must say in the fetch stage whether there is a branch, which way it goes, and where to.
- Deep and wide cores need far higher accuracy, because they run many branches on the guess at once.
- A wrong guess must leave no visible trace in registers or memory.
