4 ms·

I am not a computer engineer and I always wondered: What if we had a modern, pipelined CPU architecture with no branch predictor, which instead unconditionally

I am not a computer engineer and I always wondered: What if we had a modern, pipelined CPU architecture with no branch predictor, which instead unconditionally executed the X instructions immediately following every branch before (possibly) proceeding with the branch's target instruction? Would compilers and programmers be able to find most of the efficiencies that we currently rely on the branch predictor to find? What would be the common cases where it would be hard to do that? How much circuitry would we save by leaving out the predictor? Enough to allow a measurable speedup in the CPU clock speed?

marcosdumay 7y ago
> How much circuitry would we save by leaving out the predictor? Enough to allow a measurable speedup in the CPU clock speed? Considering the complex predictors on current PCs, we would save quite a lot of circuitry. But that circuitry is there because it is the most effective place to increase the CPU speed, if you used it for something else, speed would go down, not up (but power consumption would improve). Also, actual clock speed isn't really relevant and has a complex relation to CPU speed. That circuitry isn't affecting clock speed, so it wouldn't change.
- morelisp 7y ago
  > speed would go down, not up (but power consumption would improve). Power consumption per second might go down, but overall may go up, depending on how many more seconds the computation takes.
  - lippel82 7y ago
    To be slightly pedantic here: Power is energy per second, so power consumption itself would go down. Total energy consumption, which is power*time could go up.
    - morelisp 7y ago
      The correction is welcome - I am just a little sad we trained a cohort of developers to care about power, but not well enough to understand that race-to-sleep is usually the best way to achieve that.
      - marcosdumay 7y ago
        Hum... Race to sleep is usually not the best way to save power. Undervoltage is. Race to sleep just gets the spotlight once you have an extremely optimized CPU that can not be undervolted anymore in a practical way. The rule of thumb you learned is useful for optimizing PC software, but has no place in CPU architecture discussions. Also, "usually" leaves a lot of important cases out.
- gpderetta 7y ago
  In fact, to increase clock speed you need more pipeline stages, which means higher mispredict penality which means you need a better branch predictor...
ThePadawan 7y ago
Not a computer engineer either, but I did do some GPGPU in college (~6 years ago). Notably, branching on a flag f on the GPU was so slow that most of the time it was faster to (manually) compute both branches b1 and b2 and then calculate the result as r = f * b1 + (1-f) * b2 (where f is either 0 or 1).
- hellofunk 7y ago
  This is pretty awesome.
  - sv_h1b 7y ago
    GPUs are designed to do massive parallel computations which all branch one way and don't have much (any?) branch prediction logic. You trade it off with increased code size which might spill the cache but for small tight loops not exceeding the cache line/ size it would still be a good win.
    - ScottFree 7y ago
      Would there be any benefit to adding branch prediction logic to a GPU?
      - rdc12 7y ago
        You would probably get some benefit on a per CUDA core basis, but the extra space required would mean less CUDA cores, overall it would probably be a net loss on problems well suited to GPU acceleration
- vardump 7y ago
  Just like you can do on x86/ARM SIMD. It often pays to compute both sides and mask out the undesired results.
gpderetta 7y ago
You just reinvented delay slots [1]. Two issues: - It is not easy for the compiler to always fill up a single delay slot. Filling dozen of them (as required for a deeply pipelined modern processor) would be significantly harder. - The number of delay slots would depend on the depth of the cpu pipeline. If you do not want to expose microarchitectural details in your ISA, you need either JIT or install time specialization. edit: or stick with a potentially suboptimal number. [1] https://en.wikipedia.org/wiki/Delay_slot https://en.wikipedia.org/wiki/Delay_slot
- planteen 7y ago
  Oh this takes me back to a horrible time in my life when I was tracking down a terrible intermittent crash on a LEON (SPARC) processor. I was down at the assembly level, stepping over instructions. It was a bit mind bending to always have an instruction execute AFTER the branch (you wouldn't know if the branch was taken or not until AFTER the delay slot instruction). Often the delay instruction was a NOP, showing the difficulty in filling the delay slots as you mentioned. If you were really lucky, your branch would also result in a register window overflow. By the time handling that was done, you lost your mental context of what was going on. shudder
  - gpderetta 7y ago
    Right, SPARC has both register windows and branch delay slots, truly a great collection of architectural dead ends :).
- sv_h1b 7y ago
  Plus, the delay slots are typically _fixed_ 1-5 cycles depending on CPU architectures. The problem is sometimes the real delay could easily be 200+ cycles (TLB/ cache reload, bus contention etc.) and _variable_. There's no way you could cover all variable latency scenarios with fixed delay slots, unless you have a highly specific scenario like a GPU where you control all the internals.
ericpauley 7y ago
Aside from other comments about weaknesses of delay slots, modern processors already do this automatically in the form of out of order execution. A branch can be moved up and assigned priority to an execution unit if it doesn't depend on some of the previous instructions. These instructions can be queued or assigned to other execution units.
- dooglius 7y ago
  It looks as though you're being downvoted but I'm not sure why. This matches my mental model of OoO execution, for instance if you have a loop like: sub eax, 1 (several non-flags-touching instructions) jmpne loop_start I would expect that a branch predictor wouldn't be needed as the jump only needs the flags register to figure out where the branch is going to go.
  - gpderetta 7y ago
    that's not how ooo cpu work in practice. Jumps are resolved at the fetch stage, always by consulting the predictor; at this stage there is no opportunity to actually execute the jmpne instruction and check if the sign flag is set or not. When the jumpne is executed later in the pipeline, its only effect it to either commit or rollback the speculation. This is not specific of OoO cpus. In order cpus work the same way, assuming they have a predictor of course. edit: to be more precise, jumps are not not resolved at the fetch stage, but in one of the early stages, in fact there is often a bubble for taken branches as the fetcher will fetch the next instruction in the stream by default.

marcosdumay 7y ago

> How much circuitry would we save by leaving out the predictor? Enough to allow a measurable speedup in the CPU clock speed? Considering the complex predictors on current PCs, we would save quite a lot of circuitry. But that circuitry is there because it is the most effective place to increase the CPU speed, if you used it for something else, speed would go down, not up (but power consumption would improve). Also, actual clock speed isn't really relevant and has a complex relation to CPU speed. That circuitry isn't affecting clock speed, so it wouldn't change.

morelisp 7y ago
> speed would go down, not up (but power consumption would improve). Power consumption per second might go down, but overall may go up, depending on how many more seconds the computation takes.
- lippel82 7y ago
  To be slightly pedantic here: Power is energy per second, so power consumption itself would go down. Total energy consumption, which is power*time could go up.
  - morelisp 7y ago
    The correction is welcome - I am just a little sad we trained a cohort of developers to care about power, but not well enough to understand that race-to-sleep is usually the best way to achieve that.
    - marcosdumay 7y ago
      Hum... Race to sleep is usually not the best way to save power. Undervoltage is. Race to sleep just gets the spotlight once you have an extremely optimized CPU that can not be undervolted anymore in a practical way. The rule of thumb you learned is useful for optimizing PC software, but has no place in CPU architecture discussions. Also, "usually" leaves a lot of important cases out.
gpderetta 7y ago
In fact, to increase clock speed you need more pipeline stages, which means higher mispredict penality which means you need a better branch predictor...

ThePadawan 7y ago

Not a computer engineer either, but I did do some GPGPU in college (~6 years ago). Notably, branching on a flag f on the GPU was so slow that most of the time it was faster to (manually) compute both branches b1 and b2 and then calculate the result as r = f * b1 + (1-f) * b2 (where f is either 0 or 1).

hellofunk 7y ago
This is pretty awesome.
- sv_h1b 7y ago
  GPUs are designed to do massive parallel computations which all branch one way and don't have much (any?) branch prediction logic. You trade it off with increased code size which might spill the cache but for small tight loops not exceeding the cache line/ size it would still be a good win.
  - ScottFree 7y ago
    Would there be any benefit to adding branch prediction logic to a GPU?
    - rdc12 7y ago
      You would probably get some benefit on a per CUDA core basis, but the extra space required would mean less CUDA cores, overall it would probably be a net loss on problems well suited to GPU acceleration
vardump 7y ago
Just like you can do on x86/ARM SIMD. It often pays to compute both sides and mask out the undesired results.

gpderetta 7y ago

You just reinvented delay slots [1]. Two issues: - It is not easy for the compiler to always fill up a single delay slot. Filling dozen of them (as required for a deeply pipelined modern processor) would be significantly harder. - The number of delay slots would depend on the depth of the cpu pipeline. If you do not want to expose microarchitectural details in your ISA, you need either JIT or install time specialization. edit: or stick with a potentially suboptimal number. [1] https://en.wikipedia.org/wiki/Delay_slot https://en.wikipedia.org/wiki/Delay_slot

planteen 7y ago
Oh this takes me back to a horrible time in my life when I was tracking down a terrible intermittent crash on a LEON (SPARC) processor. I was down at the assembly level, stepping over instructions. It was a bit mind bending to always have an instruction execute AFTER the branch (you wouldn't know if the branch was taken or not until AFTER the delay slot instruction). Often the delay instruction was a NOP, showing the difficulty in filling the delay slots as you mentioned. If you were really lucky, your branch would also result in a register window overflow. By the time handling that was done, you lost your mental context of what was going on. shudder
- gpderetta 7y ago
  Right, SPARC has both register windows and branch delay slots, truly a great collection of architectural dead ends :).
sv_h1b 7y ago
Plus, the delay slots are typically _fixed_ 1-5 cycles depending on CPU architectures. The problem is sometimes the real delay could easily be 200+ cycles (TLB/ cache reload, bus contention etc.) and _variable_. There's no way you could cover all variable latency scenarios with fixed delay slots, unless you have a highly specific scenario like a GPU where you control all the internals.

ericpauley 7y ago

Aside from other comments about weaknesses of delay slots, modern processors already do this automatically in the form of out of order execution. A branch can be moved up and assigned priority to an execution unit if it doesn't depend on some of the previous instructions. These instructions can be queued or assigned to other execution units.

dooglius 7y ago
It looks as though you're being downvoted but I'm not sure why. This matches my mental model of OoO execution, for instance if you have a loop like: sub eax, 1 (several non-flags-touching instructions) jmpne loop_start I would expect that a branch predictor wouldn't be needed as the jump only needs the flags register to figure out where the branch is going to go.
- gpderetta 7y ago
  that's not how ooo cpu work in practice. Jumps are resolved at the fetch stage, always by consulting the predictor; at this stage there is no opportunity to actually execute the jmpne instruction and check if the sign flag is set or not. When the jumpne is executed later in the pipeline, its only effect it to either commit or rollback the speculation. This is not specific of OoO cpus. In order cpus work the same way, assuming they have a predictor of course. edit: to be more precise, jumps are not not resolved at the fetch stage, but in one of the early stages, in fact there is often a bubble for taken branches as the fetcher will fetch the next instruction in the stream by default.