Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A history of branch prediction

danluu.com

Post reply on HN
Print view View original

31–40 of 68 posts

Re: A history of branch prediction

#31

Post by dfox »

Simon_says wrote: post #30
mjevans wrote: post #10

Earlier quoted context omitted.

You could do it, but 'work' produces heat. From that point of view a branch predictor /saves/ you from spending the heat of the cases you /don't/ need to have processed. The performance per watt of such a design would probably leave it on the back of a napkin as an educated guess of how costly that would be.

Pie-in-the-sky idea here, but only irreversible computations produce heat. Maybe in the distant future we can make chips that do many parallel computations of all branches reversibly, and only make the results irreversible once the correct branch is known?

In theory, irreversible computations have to produce heat, while reversible do not. In practice this is mostly irrelevant, because the heat involved is so minuscule that there will always be other significantly larger sources of inefficiency involved. Also it is somewhat questionable whether one could actually construct physical realization of useful logic primitive that is truly reversible.

Re: A history of branch prediction

#32

Post by glenneroo »

filereaper wrote: post #3

Ryzen has rolled out a Neural-Net based branch predictor, would be curious to see its accuracy compared to the listed approaches.

It's even mentioned in the article:

> Some modern CPUs have completely different branch predictors; AMD Zen (2017) and AMD Bulldozer (2011) chips appear to use perceptron based branch predictors. Perceptrons are single-layer neural nets[0].

[0]: https://www.cs.utexas.edu/~lin/papers/hpca01.pdf

Re: A history of branch prediction

#33

Post by mrob »

legulere wrote: post #18

I really have problems reading this website. You don't have to make a website bloated to make it readable: http://bettermotherfuckingwebsite.com

For a long time I used to just disable CSS in Firefox (View, Page Style, No Style), which gives a readable page most of the time. I knew about Reader View, but because it only allowed low contrast gray text, and because I already had a workable solution, I dismissed it at worthless.

I recently noticed that I was using No Style so frequently that it would be worth checking for a better solution. I found it's possible to fix the low contrast text in Reader View with custom userContent.css:

    @namespace url(http://www.w3.org/1999/xhtml);
    @-moz-document url-prefix("about:reader") {
    body {
      background-color: #FFFFFF !important;
      color: #000000 !important;
      }
    }
No Style is still occasionally useful to get something readable where Reader View fails, but now I use Reader View most of the time instead.

Re: A history of branch prediction

#34

Post by terryf »

userbinator wrote: post #5

The use of previous branch history and branch address as a "context" for prediction reminds me of the very similar technique used for prediction in arithmetic compression as used in e.g. JBIG2, JPEG2000, etc. --- the goal being that, if an event X happens several times in context C, then whenever context C occurs, the probability of X is more likely. Also, since modern CPUs internally have many functional units to wh…

They do. Video here from 7 years ago that talks about it: https://www.infoq.com/presentations/click-crash-course-moder...

Basically, they do speculative execution with register renaming to get quick turn-around if the memory is available in cache.

It really is quite crazy how much faster the cpu is than memory and what tricks it pulls to get around that problem.

Re: A history of branch prediction

#35

Post by eberkund »

ramshorns wrote: post #4

Very informative. I missed the part about 1500000 BC though – a time when our ancestors lived in the branches of trees? Another beginner-friendly explanation of the effects of branch prediction is this Stack Overflow post which compares a processor to a train: https://stackoverflow.com/questions/11227809/why-is-it-faste...

Maybe it is just an arbitrarily long time in the past, since there were no computers then there is no history related to branch prediction so it's a joke that makes it sound like a longer spanning history than it actually is.

Re: A history of branch prediction

#36

Post by ufo »

One surprising thing that I discovered recently is that after Haswell, Intel processors got much much better at predicting "interpreter loops", which are basically a while true loop with a very large seemingly unpredictable switch statement. It lead to a dramatic improvement in micro benchmarks and made some traditional optimizations involving computed goto and " indirect threading" obsolete.

Does anyone know how it achieved this?

Re: A history of branch prediction

#37

Post by fulafel »

ufo wrote: post #36

One surprising thing that I discovered recently is that after Haswell, Intel processors got much much better at predicting "interpreter loops", which are basically a while true loop with a very large seemingly unpredictable switch statement. It lead to a dramatic improvement in micro benchmarks and made some traditional optimizations involving computed goto and " indirect threading" obsolete. Does anyone know how it…

It doesn't look like a series of comparisons from the CPU point of view. Normally switch statements are compiled like a series of "if" statements, but the interpreter loop style switch gets compiled into a table of jump targets that is indexed by bytecode. Same kind of indirect branch prediction features that were previously designed to help C++ "virtual" functions help here - a branch target buffer, etc.

The VM interpreter loop is mostly a main bottleneck in languages that have rather low-level VM instructions and data types. In high level VMs the dispatch on operand type is the main bottleneck. This too benefits from indirect branch prediction.

Re: A history of branch prediction

#38

Post by oshepherd »

Sniffnoy wrote: post #12

> PA 8000 (1996): actually implemented as a 3-bit shift register with majority vote This actually seems interestingly different from the two-bit saturating counter. Like, it's not just a different way of implementing it; you can't realize the saturating counter as a "quotient" of the shift/vote scheme.

It's the same just with redundant representations (the 2-bit repr is the count of ones in the 3-bit repr)

  '00' -> '000'
  '01' -> '001', '010', '100'
  '10' -> '011', '101', '110'
  '11' -> '111'
this kind of transformation is truly bread & butter in hardware; we regularly numbers between binary counts, mask/number-of-set-bits and one-hot representations for optimisation purposes.

Re: A history of branch prediction

#39

Post by marcosdumay »

cwzwarich wrote: post #7
userbinator wrote: post #5

The use of previous branch history and branch address as a "context" for prediction reminds me of the very similar technique used for prediction in arithmetic compression as used in e.g. JBIG2, JPEG2000, etc. --- the goal being that, if an event X happens several times in context C, then whenever context C occurs, the probability of X is more likely. Also, since modern CPUs internally have many functional units to wh…

This wouldn't really buy you much, because after N branches you'd be pursuing 2^N possible execution paths, each of which requires its own resources throughout the CPU, to fetch, decode, rename, schedule, execute, and retire the instructions. Going any deeper than a few branches would be impractical, and you'd be spending most of your resources on computation that doesn't affect the final result. It also doesn't work…

So, if you have low confidence in a short time in too many branches you would lose some performance. But that would happen anyway, you can't optimize low confidence stuff.

The GP's question is still a good one. Is doing both branches in parallel better than going superscalar into the slightly more favored one? Is the low confidence situation common enough that it's worth adding the extra circuitry into the CPU.

Post reply on HN