4 ms·

Can someone explain me why, if a branch is mispredicted enough, a CPU can't execute both the true and the false side? Then throw away half the work when the di

Can someone explain me why, if a branch is mispredicted enough, a CPU can't execute both the true and the false side? Then throw away half the work when the direction of the branch is finally known. The cost would be more unretired instructions, but the cost of prediction failure would also be lower.

vlovich123 3y ago
It’s definitely a thought I’ve had from time to time as well. I’m not a chip designer but my hunch is that it’s because one of the branches is likely to result in even more branches, likely very soon after that initial branch on one of the paths taken (ie you won’t get far before hitting another branch). Example is a condition that causes you to leave the loop - on every iteration of the loop you’d be trying to speculatively execute what happens after the loop. That means you’ve got an exponentially increasing number of speculative execution happening and it’s almost all worthless (ie 1/n^2) while competing for resources with the one real path. This is ignoring the practical challenges of managing all that speculation and any fun additional speculative attacks that might arise again. The best case for something like this is where you have a bunch of unpredictable branches. In those cases, it’s better for the compiler to convert it to “branchless” code (eg using the x86 cmov instruction). There’s also major performance problems unrelated to branches which are data dependencies. I think those are even more impactful these days as they completely inhibit the length of a deep pipeline. Those can only really be solved by fixing code.
adrian_b 3y ago
Some CPUs have attempted to do this, but the cost is enormous. Conditional branches are very frequent, so a modern CPU that has much more than one hundred instructions in flight might have ten or twenty branches past which it executes instructions speculatively. So it will not have two sides executed in parallel, but each side will be split in two at the next branch, then again at the next branch. The number of branches that must be executed speculatively in parallel grows exponentially, together with the ratio between executed instructions that must be discarded and useful instructions whose results are retained after the conditions of the branches are resolved. So such a CPU would have a huge power consumption due to doing mostly useless work, which would reduce its performance much more than what is lost during branch mispredictions when only one side is executed. For unpredictable branches, all modern CPUs offer conditional move or conditional select instructions, where both sides of a conditional expression are executed and then the result for the true condition is selected.
TrainedMonkey 3y ago
You need to double the hardware... which fair enough modern CPUs are super scalar so they already do that. The issue is that there are a lot of branches in the code, the CPU would need to keep a lot of redundant hardware. All that extra hardware comes with increased power usage and consequently heat dissipation. On top of that modern branch predictors are pretty amazing, so you would need to get a lot of benefit to make this worth it... So the trade is, you can get slightly better latency due to misprediction masking by executing both branches at the cost of massively decreased throughput (b.c. you are using extra hardware to execute branches of the same thread vs different threads), increased power and heat dissipation, and increased cost due to additional hardware. Note that cost, power, and usage are generally the constraints you want to satisfy, so you will generally get a significantly slower CPU that probably has worse latency due to lower clocks, less cache, and whatever other tradeoffs you need to make to fit into the power/heat/cost budget.
Hikikomori 3y ago
Had the same thought, like hyperhreading but for branches. But then I read in the article that one of the games had a branch every 4-5 instructions.
NobodyNada 3y ago
Let’s look at the problem numerically! Under your proposed scheme, from the time between a branch being issued and resolved around half the subsequent instructions executed by your CPU will be retired and the other half will be discarded. So, all else being equal, performance is 50% compared to non-branching code. With branch prediction, after a single branch all the speculatively-executed instructions are either retired or discarded. If a branch predictor randomly guesses for each branch, it will achieve 50% accuracy...so, averaged across many branches, 50% of speculatively executed instructions are retired. So the worst possible branch predictor has equivalent performance to your proposed scheme, and it’s quite a bit simpler to implement (which translates to increased performance). If your branch predictor is any better than blind guessing, it will achieve better performance (by the benchmark of % of correctly-speculated instructions). Given that modern branch predictors achieve 95%+ accuracy on typical workloads, it’s clear why processor designers choose branch prediction rather than executing both pathways.
- hyperman1 3y ago
  I'm not sure this looks at the correct resources. If I read TFA, they have an IPC of 0.85 on the benchmark, but a theoretical IPC limit of 6. So 50% usage would be IPC=3, a lot better than the benchmark. So execution resources aren't the bottleneck. Also, this analysis skips the easily predictable jumps like loops. I remember 90% prediction being relatively easy to reach in most programs just because of loops. A better way would be to let the predictor not only respond with taken/not taken, but also with high/low confidence. If confidence us low, then a CPU could spend some unused part of IPC. All of this probably wont work in practice, of course.
  - adgjlsfhk1 3y ago
    The bigger thing you're missing is that theoretical IPC of 6 can only happen if you are using a bunch of different execution ports. Most branches will have similar instruction workloads afterwards so the different sides of the branch will be fighting each other.

vlovich123 3y ago

It’s definitely a thought I’ve had from time to time as well. I’m not a chip designer but my hunch is that it’s because one of the branches is likely to result in even more branches, likely very soon after that initial branch on one of the paths taken (ie you won’t get far before hitting another branch). Example is a condition that causes you to leave the loop - on every iteration of the loop you’d be trying to speculatively execute what happens after the loop. That means you’ve got an exponentially increasing number of speculative execution happening and it’s almost all worthless (ie 1/n^2) while competing for resources with the one real path. This is ignoring the practical challenges of managing all that speculation and any fun additional speculative attacks that might arise again. The best case for something like this is where you have a bunch of unpredictable branches. In those cases, it’s better for the compiler to convert it to “branchless” code (eg using the x86 cmov instruction). There’s also major performance problems unrelated to branches which are data dependencies. I think those are even more impactful these days as they completely inhibit the length of a deep pipeline. Those can only really be solved by fixing code.

adrian_b 3y ago

Some CPUs have attempted to do this, but the cost is enormous. Conditional branches are very frequent, so a modern CPU that has much more than one hundred instructions in flight might have ten or twenty branches past which it executes instructions speculatively. So it will not have two sides executed in parallel, but each side will be split in two at the next branch, then again at the next branch. The number of branches that must be executed speculatively in parallel grows exponentially, together with the ratio between executed instructions that must be discarded and useful instructions whose results are retained after the conditions of the branches are resolved. So such a CPU would have a huge power consumption due to doing mostly useless work, which would reduce its performance much more than what is lost during branch mispredictions when only one side is executed. For unpredictable branches, all modern CPUs offer conditional move or conditional select instructions, where both sides of a conditional expression are executed and then the result for the true condition is selected.

TrainedMonkey 3y ago

You need to double the hardware... which fair enough modern CPUs are super scalar so they already do that. The issue is that there are a lot of branches in the code, the CPU would need to keep a lot of redundant hardware. All that extra hardware comes with increased power usage and consequently heat dissipation. On top of that modern branch predictors are pretty amazing, so you would need to get a lot of benefit to make this worth it... So the trade is, you can get slightly better latency due to misprediction masking by executing both branches at the cost of massively decreased throughput (b.c. you are using extra hardware to execute branches of the same thread vs different threads), increased power and heat dissipation, and increased cost due to additional hardware. Note that cost, power, and usage are generally the constraints you want to satisfy, so you will generally get a significantly slower CPU that probably has worse latency due to lower clocks, less cache, and whatever other tradeoffs you need to make to fit into the power/heat/cost budget.

Hikikomori 3y ago

Had the same thought, like hyperhreading but for branches. But then I read in the article that one of the games had a branch every 4-5 instructions.

NobodyNada 3y ago

Let’s look at the problem numerically! Under your proposed scheme, from the time between a branch being issued and resolved around half the subsequent instructions executed by your CPU will be retired and the other half will be discarded. So, all else being equal, performance is 50% compared to non-branching code. With branch prediction, after a single branch all the speculatively-executed instructions are either retired or discarded. If a branch predictor randomly guesses for each branch, it will achieve 50% accuracy...so, averaged across many branches, 50% of speculatively executed instructions are retired. So the worst possible branch predictor has equivalent performance to your proposed scheme, and it’s quite a bit simpler to implement (which translates to increased performance). If your branch predictor is any better than blind guessing, it will achieve better performance (by the benchmark of % of correctly-speculated instructions). Given that modern branch predictors achieve 95%+ accuracy on typical workloads, it’s clear why processor designers choose branch prediction rather than executing both pathways.

hyperman1 3y ago
I'm not sure this looks at the correct resources. If I read TFA, they have an IPC of 0.85 on the benchmark, but a theoretical IPC limit of 6. So 50% usage would be IPC=3, a lot better than the benchmark. So execution resources aren't the bottleneck. Also, this analysis skips the easily predictable jumps like loops. I remember 90% prediction being relatively easy to reach in most programs just because of loops. A better way would be to let the predictor not only respond with taken/not taken, but also with high/low confidence. If confidence us low, then a CPU could spend some unused part of IPC. All of this probably wont work in practice, of course.
- adgjlsfhk1 3y ago
  The bigger thing you're missing is that theoretical IPC of 6 can only happen if you are using a bunch of different execution ports. Most branches will have similar instruction workloads afterwards so the different sides of the branch will be fighting each other.