News for hackers. Stuff that matters.
Re:How and why CPUs do “branch prediction” (2017) by londons_explore on Monday July 01, 2019 @03:27PM (#20328855)
I feel like fixed precision neural nets are probably the future of branch prediction. Both 'hardcoding' a neural net on a large amount of software and then designing the weights into the CPU in a ROM, but also dynamic approaches to deciding which prediction strategy to use for a specific branch based on state recorded by another neural net.

Approaches like this have been used as a fun exercise, but now I think we're reaching the point where single thread performance is so important, and mispredicts are getting more expensive, so it's worth taking quite a big power and area hit to get a few more percentage points of performance...

Re:How and why CPUs do “branch prediction” (2017) by jcranmer on Tuesday July 02, 2019 @01:10AM (#20332310)
> but now I think we're reaching the point where single thread performance is so important

Ever since Denard scaling stopped, the biggest boosts to performance have been in increasing the parallelization opportunity, both at the SIMD level and at the multi-core level. Admittedly, working in HPC gives me a biased view, but everyone I see has resigned themselves to processors ceasing to give meaningful boosts to single-threaded performance.

Moreover, the ceiling you could get in boosting single-threaded performance with a perfect branch predictor (for conditional branches) over current state-of-the-art is around 4%. There's just not a lot of upside to be had, and even just using the extra space for another core looks preferable at that low ceilings. Extra area for the branch predictor is likely to go to better indirect branch prediction (including virtual function calls), which are increasingly important in modern workloads, and where there is a much larger headroom for performance improvement.

I'll also add that the effectiveness of neural nets in modern machine learning contexts has come from making them big and deep, and deep means adding latency to the branch predictor, which is not what you want (especially because you want to know ASAP if you need to prefetch a different I-cache line).

Re:How and why CPUs do “branch prediction” (2017) by redcalx on Tuesday July 02, 2019 @01:49AM (#20332473)
Also, branch prediction circuitry has costs, such as higher energy per instruction on average; management of the design complexity, the risks associated with that (e.g Spectre, meltdown), increased die size and therefore faulty die rate and die cost, etc.
Re:How and why CPUs do “branch prediction” (2017) by gpderetta on Tuesday July 02, 2019 @08:36AM (#20334390)
Thing is not everything is amenable to simd or multithreaded optimization. As you said yourself, a lot of HPC code tend to parallelize more easily than average. For a lot of code out of order execution is the only way to extract some amount of parallelism, and one of the biggest limiting factors to increasing the reorder window is branch prediction rate. Even an improvement of 0.1% in the prediction rate can lead to non trivial improvements in performance.
Re:How and why CPUs do “branch prediction” (2017) by dragontamer on Tuesday July 02, 2019 @09:47AM (#20334895)
> For a lot of code out of order execution is the only way to extract some amount of parallelism

But that's the thing. A CPU is simply a parallel machine forced to accelerate "sequential" code.

A "truly sequential" code sequence, like linkedList->head->next->next->next cannot be parallelized on a modern CPU. The only stuff that can be parallelized are if-statements / loops (aka: branch prediction: try to do the future speculatively), and anything Tomasulo's algorithm happens to pick up.

Even then: the modern CPU will attempt to parallelize that linked-list access because of Cache prefetching. That's actually why Arrays work so well in today's architectures: because the L1, L2, L3, and DRAM components are working in parallel through Cache Prefetchers (and Arrays are so simple that speculation will certainly be correct).

In effect: people are writing parallel programs. They are just leaving it to the CPU to figure out the parallelism details.

X = Y + Z; A = B + C can be made parallel (independent variables).

X = Y + Z; X = D + E. Also parallel: Write-after-write hazard, so X=D+E can execute first, and just throw away X=Y+Z entirely. Etc. etc.

CPUs simply find these patterns in your code and execute them in parallel.

AMD Zen has 4-integer pipelines + 4-vector pipelines + 2 load/store units per core.

Intel has 8-pipelines of varying capabilities per core. 0, 1, 5 are vector units, but 0 is also the division pipeline. Its a bit more complicated, but its still 8x parallelism that is being fed by the front-end (and reordered into the correct order by the backend).

--------------

Basically: the parallelism does exist in the code that was written. The programmer just hasn't explicitly acknowledged it yet.

But with every "speculative" branch taken, the CPU does work, and then (maybe) throws it away. The GPU-basis of coding is to not do any speculative work at all. Instead, GPUs throw 10-threads per shader (kinda like a core) and SMT the heck out of them.

If thread#0 accesses memory, it will be stuck doing that for 300+ cycles. So thread#1 will take over the core. When thread#1 waits on memory, thread#2 takes over. Etc. etc. By the time thread#9 and #10 roll around, thread#1 probably has its memory ready.

Instead of speculatively executing thread#0, the GPU is provided with alternative work it can do. In any HPC context, there's probably "more work to do" somewhere, so the GPU can remain saturated with work to do. Its naturally a more power-efficient methodology: there's less wasted work.

It just requires the programmer to figure out a lot of tasks that the GPU can do to remain saturated. While a CPU will dedicate more and more resources, all the way towards speculative execution, to accelerate the same task. Even if its highly wasteful.

Re:How and why CPUs do “branch prediction” (2017) by oso2k on Tuesday July 02, 2019 @11:30AM (#20336075)
> Admittedly, working in HPC gives me a biased view, but everyone I see has resigned themselves to processors ceasing to give meaningful boosts to single-threaded performance.

There's also that realization that compiler & software development is still far, far behind the parallelization capabilities of the HW. See the failed DEC Alpha, Itanium. It's a bad design situation when compilers regularly generate code that blows caches, branch predictors, TLBs and instruction pipelines more than 50% of the time when the code has been run through aggressive non-PGO effort. Compilers need to get better at generating better code.

Re:How and why CPUs do “branch prediction” (2017) by Veedrac on Tuesday July 02, 2019 @06:50PM (#20340103)
> Moreover, the ceiling you could get in boosting single-threaded performance with a perfect branch predictor (for conditional branches) over current state-of-the-art is around 4%.

No, actually having perfect branch prediction is a major blocker on performance even now, since it limits the useful size of the out-of-order reorder buffer.

Re:How and why CPUs do “branch prediction” (2017) by Symmetry on Tuesday July 02, 2019 @10:41AM (#20335602)
There has been some work in making cores wider with larger re-order depth and more physical register files, etc. But all of that is deeply into diminishing returns territory.
Re:How and why CPUs do “branch prediction” (2017) by ben-schaaf on Tuesday July 02, 2019 @12:57AM (#20332246)
It seems like AMD has been doing something similar for a little while already: https://chasethedevil.github.io/post/the_neural_network_in_y...
Re:How and why CPUs do “branch prediction” (2017) by tntn on Tuesday July 02, 2019 @01:08AM (#20332297)
AMD switched to TAGE for Zen 2, so I don't know if neural networks are "the future of branch prediction" or just a neat diversion.
Re:How and why CPUs do “branch prediction” (2017) by fooker on Tuesday July 02, 2019 @05:22AM (#20333462)
Future? Most modern CPUs do this to some extent. Remember you can only have a very simple model here, because the inference time has to be extremely fast.