4 ms·

Branch prediction: Why CPUs can't wait?

50 points by signa11 1y ago

whitten 1y ago
I know branch prediction is essential if you have instruction pipelining in actual CPU hardware. It is an interesting thought experiment re instruction pipelining in a virtual machine or interpreter design. What would you change in a design to allow it ? Would an asynchronous architecture be necessary ? How would you merge control flow together efficiently to take advantage of it ?
- addaon 1y ago
  > I know branch prediction is essential if you have instruction pipelining in actual CPU hardware. With sufficiently slow memory, relative to the pipeline speed. A microcontroller executing out of TCM doesn’t gain anything from prediction, since instruction fetches can keep up with the pipeline.
  - immibis 1y ago
    The head of the pipeline is at least several clock cycles ahead of the tail, by definition. At the time the branch instruction reaches the part of the CPU where it decides whether to branch or not, the next several instructions have already been fetched, decoded and partially executed, and that's thrown away on a mispredicted branch. There may not be a large delay when executing from TCM with a short pipeline, but it's still there. It can be so small that it doesn't justify the expense of a branch predictor. Many microcontrollers are optimized for power consumption, which means simplicity. I expect microcontroller-class chips to largely run in-order with short pipelines and low-ish clock speeds, although there are exceptions. Older generations of microcontrollers (PIC/AVR) weren't even pipelined at all.
    - addaon 1y ago
      > but it's still there Unless you evaluate branches in the second stage of the pipeline and forward them. Or add a delay slot and forward them from the third stage. In the typical case you’re of course correct, but there are many approaches out there.
- cogman10 1y ago
  With the way architectures have gone, I think you'd end up recreating VLIW. The thing holding back VLIW was compilers were too dumb and computers too slow to really take advantage of it. You ended up with a lot of "NOP"s as a result in the output. VLIW is essentially how modern GPUs operate. The main benefit of VLIW is that it simplifies the processor design by moving the complicated tasks/circuitry into the compiler. Theoretically, the compiler has more information about the intent of the program which allows it to better optimize things. It would also be somewhat of a security boon. VLIW moves the branch prediction (and rewinding) into the processor. With exploits like spectre, pulling that out would make it easier to integrate compiler hints on security sensitive code "hey, don't spec ex here".
  - _chris_ 1y ago
    > The thing holding back VLIW was compilers were too dumb That’s not really the problem. The real issue is that VLIW requires branches to be strongly biased, statically, so a compiler can exploit them. But in fact branches are very dynamic but trivially predicted by branch predictors, so branch predictors win. Not to mention that even vliw cores use branch predictors, because the branch resolution latency is too long to wait for the branch outcome to be known.
- o11c 1y ago
  You have to ensure that virtual instructions map to distinct hardware instructions. Computed-goto-after-each-instruction is well known, and copying fragments of machine code is obvious. Less known is "make an entire copy of your interpreter for each state" - though I'm only aware of this as a depessimization for stack machines. https://dl.acm.org/doi/pdf/10.1145/223428.207165 https://dl.acm.org/doi/pdf/10.1145/223428.207165 But the main problem, which none of these solve, is that most VM languages are designed to be impossible (or very difficult) to optimize, due to aggressive use of dynamic typing. Nothing will save you from dynamic types.
zenolijo 1y ago
I do wonder how branch prediction actually works in the CPU, predicting which branch to take also seems like it should be expensive, but I guess something clever is going on. I've also found G_LIKELY and G_UNLIKELY in glib to be useful when writing some types of performance-critical code. Would be a fun experiment to compare the assembly when using it and not using it.
- hansvm 1y ago
  Semantically it's just a table from instruction location to branch probability. Some nuances exist in: - Table overflow mitigation: multi-leveled tables, not wasting space on 100% predicted branches, etc - Table eviction: Rolling counts are actually impossible without space consumption; do you have space wasted, periodic flushing, exponential moving averages, etc - Table initialization: When do you start caring about a branch (and wasting table space), how conservative are the initial parameters, etc - Table overflow: What do you do when a branch doesn't fit in the table but should As a rule of thumb, no extra information/context is used for branch prediction. If a program over the course of a few thousand instructions hits a branch X% of the time, then X will be the branch prediction. If you have context you want to use to influence the prediction, you need to manifest that context as additional lines of assembly the predictor can use in its lookup table. As another rule of thumb, if the hot path has more than a few thousand branches (on modern architectures, often just a few thousand <100% branches (you want the assembly to generate the jump-if-not-equal in the right direction for that architecture though, else you'll get a 100% misprediction rate instead)) then you'll hit slow paths -- multi-leveled search, mispredicted branches, etc. It's reasonably interesting, and given that it's hardware it's definitely clever, but it's not _that_ clever from a software perspective. Is there anything in particular you're curious about?
  - NobodyNada 1y ago
    > If a program over the course of a few thousand instructions hits a branch X% of the time, then X will be the branch prediction. This is not completely true - modern branch predictors can recognize patterns such as "this branch is taken every other time", or "every 5th time", etc. They also can, in some cases, recognize correlations between nearby branches. However, they won't use factors like register or memory contents to predict branches, because that would require waiting for that data to be available to make the prediction -- which of course defeats the point of branch prediction.
Izmaki 1y ago
My favourite explanation of how Branch Prediction works: https://stackoverflow.com/a/11227902/1150676 https://stackoverflow.com/a/11227902/1150676
zzo38computer 1y ago
MMIX instruction set specifies the branch prediction explicitly. If you also have a "branch always" and "branch never" and the compiler can generate a code to modify that instruction during the initialization of the program, then for some programs where some of the branches are known during initialization, it might modify the code when it is initialized before it is executed.
- immibis 1y ago
  Pretty much every CPU has a "branch always" (it's called "branch" or "jump") and a "branch never" (it's called "nop"). The language support for this is the tricky part.
  - zzo38computer 1y ago
    For "branch always", yes, but for "branch never", it is not necessarily the same as the "nop" in many instruction sets, because it would still have an operand of the same size and format of a branch instruction, although the operand is ignored. (For instruction sets with fixed size instructions, the "nop" will potentially work if it has an operand which is not used for any other purpose; the SWYM instruction on MMIX is also no operation but the operand may be used for communication with debuggers or for other stuff.)
    - dan_hawkins 1y ago
      You can just use "branch always" but to the next instruction (:
  - eigenform 1y ago
    Think you're referring to the idea that "my compiler can know that some branch is always/never taken" and turn it into an unconditional control-flow instruction (either "always jump here", or "always continue sequentially" and don't emit anything!). But the parent comment is talking about "hinting" for branches where the compiler cannot compute this ahead of time, and the CPU is responsible for resolving it during runtime. This is usually exposed by the ISA, ie. a bit in the branch instruction encoding that tells the machine "when you encounter this instruction for the first time, the default prediction should be 'taken'." In practice, branches are usually predicted "not-taken" by default: - It's advantageous to assume that control-flow is sequential because [pre-]fetching sequentially is the easy case - It's wasteful to track the target addresses of branches in your predictor if they aren't taken at least once!
bob1029 1y ago
Branch prediction is getting pretty crazy with the latest hardware generation. https://hackaday.com/2024/07/28/amd-returns-to-1996-with-zen-5s-two-block-ahead-branch-predictor/ https://hackaday.com/2024/07/28/amd-returns-to-1996-with-zen...

50 points by signa11 1y ago

I know branch prediction is essential if you have instruction pipelining in actual CPU hardware. It is an interesting thought experiment re instruction pipelining in a virtual machine or interpreter design. What would you change in a design to allow it ? Would an asynchronous architecture be necessary ? How would you merge control flow together efficiently to take advantage of it ?

addaon 1y ago
> I know branch prediction is essential if you have instruction pipelining in actual CPU hardware. With sufficiently slow memory, relative to the pipeline speed. A microcontroller executing out of TCM doesn’t gain anything from prediction, since instruction fetches can keep up with the pipeline.
- immibis 1y ago
  The head of the pipeline is at least several clock cycles ahead of the tail, by definition. At the time the branch instruction reaches the part of the CPU where it decides whether to branch or not, the next several instructions have already been fetched, decoded and partially executed, and that's thrown away on a mispredicted branch. There may not be a large delay when executing from TCM with a short pipeline, but it's still there. It can be so small that it doesn't justify the expense of a branch predictor. Many microcontrollers are optimized for power consumption, which means simplicity. I expect microcontroller-class chips to largely run in-order with short pipelines and low-ish clock speeds, although there are exceptions. Older generations of microcontrollers (PIC/AVR) weren't even pipelined at all.
  - addaon 1y ago
    > but it's still there Unless you evaluate branches in the second stage of the pipeline and forward them. Or add a delay slot and forward them from the third stage. In the typical case you’re of course correct, but there are many approaches out there.
cogman10 1y ago
With the way architectures have gone, I think you'd end up recreating VLIW. The thing holding back VLIW was compilers were too dumb and computers too slow to really take advantage of it. You ended up with a lot of "NOP"s as a result in the output. VLIW is essentially how modern GPUs operate. The main benefit of VLIW is that it simplifies the processor design by moving the complicated tasks/circuitry into the compiler. Theoretically, the compiler has more information about the intent of the program which allows it to better optimize things. It would also be somewhat of a security boon. VLIW moves the branch prediction (and rewinding) into the processor. With exploits like spectre, pulling that out would make it easier to integrate compiler hints on security sensitive code "hey, don't spec ex here".
- _chris_ 1y ago
  > The thing holding back VLIW was compilers were too dumb That’s not really the problem. The real issue is that VLIW requires branches to be strongly biased, statically, so a compiler can exploit them. But in fact branches are very dynamic but trivially predicted by branch predictors, so branch predictors win. Not to mention that even vliw cores use branch predictors, because the branch resolution latency is too long to wait for the branch outcome to be known.
o11c 1y ago
You have to ensure that virtual instructions map to distinct hardware instructions. Computed-goto-after-each-instruction is well known, and copying fragments of machine code is obvious. Less known is "make an entire copy of your interpreter for each state" - though I'm only aware of this as a depessimization for stack machines. https://dl.acm.org/doi/pdf/10.1145/223428.207165 https://dl.acm.org/doi/pdf/10.1145/223428.207165 But the main problem, which none of these solve, is that most VM languages are designed to be impossible (or very difficult) to optimize, due to aggressive use of dynamic typing. Nothing will save you from dynamic types.

zenolijo 1y ago

I do wonder how branch prediction actually works in the CPU, predicting which branch to take also seems like it should be expensive, but I guess something clever is going on. I've also found G_LIKELY and G_UNLIKELY in glib to be useful when writing some types of performance-critical code. Would be a fun experiment to compare the assembly when using it and not using it.

hansvm 1y ago
Semantically it's just a table from instruction location to branch probability. Some nuances exist in: - Table overflow mitigation: multi-leveled tables, not wasting space on 100% predicted branches, etc - Table eviction: Rolling counts are actually impossible without space consumption; do you have space wasted, periodic flushing, exponential moving averages, etc - Table initialization: When do you start caring about a branch (and wasting table space), how conservative are the initial parameters, etc - Table overflow: What do you do when a branch doesn't fit in the table but should As a rule of thumb, no extra information/context is used for branch prediction. If a program over the course of a few thousand instructions hits a branch X% of the time, then X will be the branch prediction. If you have context you want to use to influence the prediction, you need to manifest that context as additional lines of assembly the predictor can use in its lookup table. As another rule of thumb, if the hot path has more than a few thousand branches (on modern architectures, often just a few thousand <100% branches (you want the assembly to generate the jump-if-not-equal in the right direction for that architecture though, else you'll get a 100% misprediction rate instead)) then you'll hit slow paths -- multi-leveled search, mispredicted branches, etc. It's reasonably interesting, and given that it's hardware it's definitely clever, but it's not _that_ clever from a software perspective. Is there anything in particular you're curious about?
- NobodyNada 1y ago
  > If a program over the course of a few thousand instructions hits a branch X% of the time, then X will be the branch prediction. This is not completely true - modern branch predictors can recognize patterns such as "this branch is taken every other time", or "every 5th time", etc. They also can, in some cases, recognize correlations between nearby branches. However, they won't use factors like register or memory contents to predict branches, because that would require waiting for that data to be available to make the prediction -- which of course defeats the point of branch prediction.

Izmaki 1y ago

My favourite explanation of how Branch Prediction works: https://stackoverflow.com/a/11227902/1150676 https://stackoverflow.com/a/11227902/1150676

zzo38computer 1y ago

MMIX instruction set specifies the branch prediction explicitly. If you also have a "branch always" and "branch never" and the compiler can generate a code to modify that instruction during the initialization of the program, then for some programs where some of the branches are known during initialization, it might modify the code when it is initialized before it is executed.

immibis 1y ago
Pretty much every CPU has a "branch always" (it's called "branch" or "jump") and a "branch never" (it's called "nop"). The language support for this is the tricky part.
- zzo38computer 1y ago
  For "branch always", yes, but for "branch never", it is not necessarily the same as the "nop" in many instruction sets, because it would still have an operand of the same size and format of a branch instruction, although the operand is ignored. (For instruction sets with fixed size instructions, the "nop" will potentially work if it has an operand which is not used for any other purpose; the SWYM instruction on MMIX is also no operation but the operand may be used for communication with debuggers or for other stuff.)
  - dan_hawkins 1y ago
    You can just use "branch always" but to the next instruction (:
- eigenform 1y ago
  Think you're referring to the idea that "my compiler can know that some branch is always/never taken" and turn it into an unconditional control-flow instruction (either "always jump here", or "always continue sequentially" and don't emit anything!). But the parent comment is talking about "hinting" for branches where the compiler cannot compute this ahead of time, and the CPU is responsible for resolving it during runtime. This is usually exposed by the ISA, ie. a bit in the branch instruction encoding that tells the machine "when you encounter this instruction for the first time, the default prediction should be 'taken'." In practice, branches are usually predicted "not-taken" by default: - It's advantageous to assume that control-flow is sequential because [pre-]fetching sequentially is the easy case - It's wasteful to track the target addresses of branches in your predictor if they aren't taken at least once!

bob1029 1y ago

Branch prediction is getting pretty crazy with the latest hardware generation. https://hackaday.com/2024/07/28/amd-returns-to-1996-with-zen-5s-two-block-ahead-branch-predictor/ https://hackaday.com/2024/07/28/amd-returns-to-1996-with-zen...