4 ms·

> One way you might design a CPU is to have the CPU do all of the work for one instruction, then move on to the next instruction, do all of the work for the nex

> One way you might design a CPU is to have the CPU do all of the work for one instruction, then move on to the next instruction, do all of the work for the next instruction, and so on. If a modern CPU did no branch prediction, how much slower would it be? Just curious to know a ballpark figure, like 5x slower or 100x slower?

shiftingleft 4y ago
Not much if you adjust the ISA for it! https://arxiv.org/abs/2007.15919 https://arxiv.org/abs/2007.15919 This paper adds (more or less) a really big branch delay slot to fill the cpu with work while it's waiting for the branch to resolve. Impossibility of Spectre-like attacks is a neat side-effect.
- coder543 4y ago
  I've only glanced over that paper, but they're using a processor with a 5-stage pipeline, which is really short by modern standards (Zen 1 uses a 19-stage pipeline, and I couldn't quickly find the number for subsequent versions of Zen). Using a very short pipeline significantly reduces the advantage of control flow speculation (CFS)... but they still showed CFS offering up to a ~50% advantage over their best alternative, if I'm reading that right. I wish they had included the geometric mean of their benchmarks, but I didn't see it anywhere, and I'm not going to run the numbers right now. Even if the speedup CFS offered on a 5-stage pipeline is "only" 25%, that is still huge... and on a larger pipeline, that delta would grow. "Not much" is drastically different from my interpretation of those results. I do think security is extremely important, but I'm not convinced that things are currently so terrible that this is the only way forward, as the authors seemed to imply. OTOH, I would enjoy seeing a return of an Itanium-style ISA that moves a lot of speculation from the hardware to the compiler. I think compilers are in a much better place now than they were when Itanium hit the scene, which did not help Itanium's problems.
  - cpgxiii 4y ago
    In many ways we've seen that return to dumber hardware + smarter compilers in the GPGPU realm, although even there the hardware continues to get more capable over time. Those applications tend to work, though, on the basis that either the compiler is generating fat binaries to support multiple architecture versions (e.g. Cuda), or some sort of IR, or compilation happens at runtime (e.g. OpenCL). It doesn't really work if you want to generate single binaries that will work performantly on a wide range of hardware versions - particularly important for users answering "how will application X work on future hardware Y", which really gets in the way of general-purpose use. That's really the great advantage of putting more smarts in the hardware - you can evolve the processor design (often to improve performance) while executing the same binaries.
  - shiftingleft 4y ago
    Thanks for the insights! In my defense, 1.5X is "not much" when compared with 5 to 100X :-)
alain94040 4y ago
Some back of the envelope math: - there is a branch instruction every 10 instructions or so - if you can't predict, assume you guess wrong half of the time So every 20 instructions or so, you take the wrong branch. Sounds like it could be a significant overhead, from 10% - 50% depending on what the code inside the loop is doing. For instance, if your code is doing only arithmetic operations, no load/store, such as computing factorial or other silly integer math, 20 instructions would probably take 20 cycles or less to execute, but the branch failure would cause a similar delay. So that's 50% overhead. In the other case, assume the 20 instructions are fairly slow (lots of memory accesses), then your branch penalty won't feel so bad.
coder543 4y ago
One of the other comments around here[0] points to one truly classic StackOverflow question[1] where the answer is "branch prediction". In that example, the CPU is 6x slower at processing the data when the branch predictor is failing repeatedly. It is surely still succeeding some of the time, since that question wasn't specifically built to foil the branch predictor, so that isn't even the upper bound for performance loss. If you designed a CPU to lack a branch predictor, you would certainly make different choices that would reduce the penalty of that, but there would still be a significant penalty. Modern CPUs are all pipelined[2] because it allows a sequence of instructions to be executed (to some degree) in parallel. With out-of-order CPUs, the amount of parallelism that is possible for a sequence of instructions increases even more. Without a branch predictor, you would have to stall the entire pipeline as soon as you see a branch instruction, until that instruction is finished. Obviously if you don't have a branch predictor, you're going to choose to have a shorter pipeline, but the penalty of each branch instruction will still be significant. There's a lot of nuance to any proper answer to this question, and it's been years since I learned about this or thought deeply about this, so I'm probably not the right person to provide a deeper answer at this point. The performance impact would be significant. [0]: https://news.ycombinator.com/item?id=34202230 https://news.ycombinator.com/item?id=34202230 [1]: https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array https://stackoverflow.com/questions/11227809/why-is-processi... [2]: https://en.wikipedia.org/wiki/Instruction_pipelining https://en.wikipedia.org/wiki/Instruction_pipelining
- mysterydip 4y ago
  If the branch predictor fails, does it have to take time undoing the steps it's already done? Or are pipelines long enough that the fail would be detected before registers/pointers are updated?
  - coder543 4y ago
    The results for partially-executed instructions aren't "committed" yet, so the pipeline is flushed (thrown away), and execution starts again with an empty pipeline at the corrected address. IIRC, each stage of a pipeline has its own registers. The registers your code knows about would not have been updated until the end of the pipeline, but that branch instruction is ahead of the speculative execution, so none of the speculative results would be stored before the mistake is identified. So, there's no work required to "undo" those mistakes, but starting from an empty pipeline still means you're a dozen (or two) clock cycles from getting back to where you would have been with a successful branch prediction, which is why it is important for the CPU to predict correctly as often as it can.
AgentOrange1234 4y ago
There’s no easy answer. Branch prediction is a key enabler for other kinds of speculation. Modern CPUs can have dozens of ops in a partially executed state. This lets them, e.g., simultaneously fetch many lines of memory that are going to be needed soon, under the assumption that a branch will/won’t be taken. If you can’t predict branches, you won’t be able to keep nearly so many ops in flight, and the whole apparatus for speculative execution starts to make a lot less sense. Everything is workload dependent, but I suspect you’re more in the 100x than 5x range after the knock-on effects.
tcmart14 4y ago
Wouldn't any kind of measurement have to rely on a heuristic? We would need a baseline as to how often a branch prediction is accurate. If the branch prediction is always wrong, we can assume the speed would be the same. If the branch prediction is always correct, then it should be a pretty big speed up. I would be interested to see a paper on about this topic, so if anyone has one, please share!
- eru 4y ago
  > If the branch prediction is always wrong, we can assume the speed would be the same. Not sure, because in that case the wrongly-predicting CPU is doing lots of wasted work, which contributes to eg waste heat. A non-predicting CPU could do more real work, than a wrong-predicting one?
cellularmitosis 4y ago
Hopefully others can correct me here, but my intuition is that the lower bound of performance would be determined by the pipeline length. I.e. if your instruction pipeline was 8 stages, worst-case scenario is flushing the pipeline on every instruction, which would cause it to run at 1/8th speed. (At one point I believe the Pentium 4 had a twenty-stage pipeline, yikes!). In practice, branches aren't every instruction, so the impact will be less.
- coder543 4y ago
  > At one point I believe the Pentium 4 had a twenty-stage pipeline, yikes! Modern pipeline lengths aren't documented publicly as often as they could be, but Zen 1 was a 19 stage pipeline, and it performed great for the time. But, I think Pentium 4's full pipeline was 31 stages. Regardless, I think CPU designers these days have better tools and techniques for dealing with long pipelines.

shiftingleft 4y ago

Not much if you adjust the ISA for it! https://arxiv.org/abs/2007.15919 https://arxiv.org/abs/2007.15919 This paper adds (more or less) a really big branch delay slot to fill the cpu with work while it's waiting for the branch to resolve. Impossibility of Spectre-like attacks is a neat side-effect.

coder543 4y ago
I've only glanced over that paper, but they're using a processor with a 5-stage pipeline, which is really short by modern standards (Zen 1 uses a 19-stage pipeline, and I couldn't quickly find the number for subsequent versions of Zen). Using a very short pipeline significantly reduces the advantage of control flow speculation (CFS)... but they still showed CFS offering up to a ~50% advantage over their best alternative, if I'm reading that right. I wish they had included the geometric mean of their benchmarks, but I didn't see it anywhere, and I'm not going to run the numbers right now. Even if the speedup CFS offered on a 5-stage pipeline is "only" 25%, that is still huge... and on a larger pipeline, that delta would grow. "Not much" is drastically different from my interpretation of those results. I do think security is extremely important, but I'm not convinced that things are currently so terrible that this is the only way forward, as the authors seemed to imply. OTOH, I would enjoy seeing a return of an Itanium-style ISA that moves a lot of speculation from the hardware to the compiler. I think compilers are in a much better place now than they were when Itanium hit the scene, which did not help Itanium's problems.
- cpgxiii 4y ago
  In many ways we've seen that return to dumber hardware + smarter compilers in the GPGPU realm, although even there the hardware continues to get more capable over time. Those applications tend to work, though, on the basis that either the compiler is generating fat binaries to support multiple architecture versions (e.g. Cuda), or some sort of IR, or compilation happens at runtime (e.g. OpenCL). It doesn't really work if you want to generate single binaries that will work performantly on a wide range of hardware versions - particularly important for users answering "how will application X work on future hardware Y", which really gets in the way of general-purpose use. That's really the great advantage of putting more smarts in the hardware - you can evolve the processor design (often to improve performance) while executing the same binaries.
- shiftingleft 4y ago
  Thanks for the insights! In my defense, 1.5X is "not much" when compared with 5 to 100X :-)

alain94040 4y ago

Some back of the envelope math: - there is a branch instruction every 10 instructions or so - if you can't predict, assume you guess wrong half of the time So every 20 instructions or so, you take the wrong branch. Sounds like it could be a significant overhead, from 10% - 50% depending on what the code inside the loop is doing. For instance, if your code is doing only arithmetic operations, no load/store, such as computing factorial or other silly integer math, 20 instructions would probably take 20 cycles or less to execute, but the branch failure would cause a similar delay. So that's 50% overhead. In the other case, assume the 20 instructions are fairly slow (lots of memory accesses), then your branch penalty won't feel so bad.

coder543 4y ago

One of the other comments around here[0] points to one truly classic StackOverflow question[1] where the answer is "branch prediction". In that example, the CPU is 6x slower at processing the data when the branch predictor is failing repeatedly. It is surely still succeeding some of the time, since that question wasn't specifically built to foil the branch predictor, so that isn't even the upper bound for performance loss. If you designed a CPU to lack a branch predictor, you would certainly make different choices that would reduce the penalty of that, but there would still be a significant penalty. Modern CPUs are all pipelined[2] because it allows a sequence of instructions to be executed (to some degree) in parallel. With out-of-order CPUs, the amount of parallelism that is possible for a sequence of instructions increases even more. Without a branch predictor, you would have to stall the entire pipeline as soon as you see a branch instruction, until that instruction is finished. Obviously if you don't have a branch predictor, you're going to choose to have a shorter pipeline, but the penalty of each branch instruction will still be significant. There's a lot of nuance to any proper answer to this question, and it's been years since I learned about this or thought deeply about this, so I'm probably not the right person to provide a deeper answer at this point. The performance impact would be significant. [0]: https://news.ycombinator.com/item?id=34202230 https://news.ycombinator.com/item?id=34202230 [1]: https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array https://stackoverflow.com/questions/11227809/why-is-processi... [2]: https://en.wikipedia.org/wiki/Instruction_pipelining https://en.wikipedia.org/wiki/Instruction_pipelining

mysterydip 4y ago
If the branch predictor fails, does it have to take time undoing the steps it's already done? Or are pipelines long enough that the fail would be detected before registers/pointers are updated?
- coder543 4y ago
  The results for partially-executed instructions aren't "committed" yet, so the pipeline is flushed (thrown away), and execution starts again with an empty pipeline at the corrected address. IIRC, each stage of a pipeline has its own registers. The registers your code knows about would not have been updated until the end of the pipeline, but that branch instruction is ahead of the speculative execution, so none of the speculative results would be stored before the mistake is identified. So, there's no work required to "undo" those mistakes, but starting from an empty pipeline still means you're a dozen (or two) clock cycles from getting back to where you would have been with a successful branch prediction, which is why it is important for the CPU to predict correctly as often as it can.

AgentOrange1234 4y ago

There’s no easy answer. Branch prediction is a key enabler for other kinds of speculation. Modern CPUs can have dozens of ops in a partially executed state. This lets them, e.g., simultaneously fetch many lines of memory that are going to be needed soon, under the assumption that a branch will/won’t be taken. If you can’t predict branches, you won’t be able to keep nearly so many ops in flight, and the whole apparatus for speculative execution starts to make a lot less sense. Everything is workload dependent, but I suspect you’re more in the 100x than 5x range after the knock-on effects.

tcmart14 4y ago

Wouldn't any kind of measurement have to rely on a heuristic? We would need a baseline as to how often a branch prediction is accurate. If the branch prediction is always wrong, we can assume the speed would be the same. If the branch prediction is always correct, then it should be a pretty big speed up. I would be interested to see a paper on about this topic, so if anyone has one, please share!

eru 4y ago
> If the branch prediction is always wrong, we can assume the speed would be the same. Not sure, because in that case the wrongly-predicting CPU is doing lots of wasted work, which contributes to eg waste heat. A non-predicting CPU could do more real work, than a wrong-predicting one?

cellularmitosis 4y ago

Hopefully others can correct me here, but my intuition is that the lower bound of performance would be determined by the pipeline length. I.e. if your instruction pipeline was 8 stages, worst-case scenario is flushing the pipeline on every instruction, which would cause it to run at 1/8th speed. (At one point I believe the Pentium 4 had a twenty-stage pipeline, yikes!). In practice, branches aren't every instruction, so the impact will be less.

coder543 4y ago
> At one point I believe the Pentium 4 had a twenty-stage pipeline, yikes! Modern pipeline lengths aren't documented publicly as often as they could be, but Zen 1 was a 19 stage pipeline, and it performed great for the time. But, I think Pentium 4's full pipeline was 31 stages. Regardless, I think CPU designers these days have better tools and techniques for dealing with long pipelines.