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

Zen 5's 2-ahead branch predictor: how a 30 year old idea allows for new tricks

chipsandcheese.com

Post reply on HN
Print view View original

21–30 of 196 posts

Re: Zen 5's 2-ahead branch predictor: how a 30 year old idea allows for new tricks

#21

Post by branko_d »

swatcoder wrote: post #13
Szpadel wrote: post #3

that's probably bad idea but I would like to learn why: why when we have a conditional branch we cannot just fetch and prepare instructions for both possible branches and then discard the incorrect one? is this that much harder or there are other reasons that makes this not worth it

Because it's rare for a branch result to be random. The compiler/runtime/cpu/etc can often guess which result is more likely, and correctly not do the extra work in the first place, and so that's usually the better strategy than spending silicon and heat on the wrong answer just in case. I think a lot of people don't have an intuition about how accurate branch prediction can be, but if you look at your own code, you'…

> it's rare for a branch result to be random

How rare, though?

QuickSort has fundamentally unpredictable branches, and it’s a pretty widely used algorithm. Binary search, B-trees also come to mind.

Re: Zen 5's 2-ahead branch predictor: how a 30 year old idea allows for new tricks

#22

Post by MBCook »

Szpadel wrote: post #3

that's probably bad idea but I would like to learn why: why when we have a conditional branch we cannot just fetch and prepare instructions for both possible branches and then discard the incorrect one? is this that much harder or there are other reasons that makes this not worth it

We reached 90% accuracy decades ago. Depending on workload modern chips can do way better.

So basically it’s just nowhere near worth it. Much better to use those chip resources for another thread or core.

Re: Zen 5's 2-ahead branch predictor: how a 30 year old idea allows for new tricks

#24

Post by kllrnohj »

branko_d wrote: post #21
swatcoder wrote: post #13

Earlier quoted context omitted.

Because it's rare for a branch result to be random. The compiler/runtime/cpu/etc can often guess which result is more likely, and correctly not do the extra work in the first place, and so that's usually the better strategy than spending silicon and heat on the wrong answer just in case. I think a lot of people don't have an intuition about how accurate branch prediction can be, but if you look at your own code, you'…

> it's rare for a branch result to be random How rare, though? QuickSort has fundamentally unpredictable branches, and it’s a pretty widely used algorithm. Binary search, B-trees also come to mind.

Binary searching is quite slow and should be used sparingly but not because of branch misprediction necessarily but because of memory stalls - you're almost always guaranteed to have a cache miss during the search. Similarly for B-trees it's going to be memory stalls that you're probably more focused on addressing, not branch mispredicts.

Re: Zen 5's 2-ahead branch predictor: how a 30 year old idea allows for new tricks

#25

Post by emn13 »

cpldcpu wrote: post #11
emn13 wrote: post #2

As a novice in this area, it's not clear to me after reading this what exactly the 2-ahead branch predictor is.

My understanding is that they do not predict the target of the next branch but of the one after the next (2-ahead). This is probably much harder than next-branch prediction but does allows to initiate code fetch much earlier to feed even deeper pipelines.

Ah, that makes sense in the context of the article - thanks!

Re: Zen 5's 2-ahead branch predictor: how a 30 year old idea allows for new tricks

#26

Post by nomel »

immibis wrote: post #14
dymk wrote: post #4

Earlier quoted context omitted.

Transistor count; now you have to duplicate all the decode and speculative execution circuitry for both possible branches

No, the same circuits would execute them interleaved just like they execute multiple hardware threads now

With the SMT core count having to be one less.

Re: Zen 5's 2-ahead branch predictor: how a 30 year old idea allows for new tricks

#27

Post by [deleted] »

bee_rider wrote: post #8
IvanAchlaqullah wrote: post #5

It's always interesting to see decades old papers, sometimes published with little to no fanfares, suddenly becomes "state of the art" because hardware have become powerful enough. For example Z-buffers[1]. It's used by 3d video games. When it's first published on paper, it's not even the main topic of the paper, just some side notes because it requires expensive amount of memory to run. Turn out megabytes is quite c…

I sometimes wonder if there’s an academic career hidden in there for an engineer: go to the library and read what the CS folks were publishing on physical papers, maybe there are some ideas that can actually be implemented now that weren’t practical back then.

[deleted]

Re: Zen 5's 2-ahead branch predictor: how a 30 year old idea allows for new tricks

#28

Post by emn13 »

kllrnohj wrote: post #24
branko_d wrote: post #21

Earlier quoted context omitted.

> it's rare for a branch result to be random How rare, though? QuickSort has fundamentally unpredictable branches, and it’s a pretty widely used algorithm. Binary search, B-trees also come to mind.

Binary searching is quite slow and should be used sparingly but not because of branch misprediction necessarily but because of memory stalls - you're almost always guaranteed to have a cache miss during the search. Similarly for B-trees it's going to be memory stalls that you're probably more focused on addressing, not branch mispredicts.

This probably depends on the size of the area to be searched, and just how hot that region is. After all, if it's fairly small, there won't be any cache misses, and the data structure does use less memory than a typical hash table, which is itself an advantage.

Re: Zen 5's 2-ahead branch predictor: how a 30 year old idea allows for new tricks

#29

Post by isotypic »

0x000xca0xfe wrote: post #16
Szpadel wrote: post #3

that's probably bad idea but I would like to learn why: why when we have a conditional branch we cannot just fetch and prepare instructions for both possible branches and then discard the incorrect one? is this that much harder or there are other reasons that makes this not worth it

- Side effects; how do you handle two different writes to memory? - Double the execution units; very expensive for wide vector units - Massive waste of energy as half the resources will always be wasted no matter what - Bad scaling, i.e. four branches ahead would require 16x the resources

Handling two different writes to memory is not really a concern - existing speculative/out of order processors already solve this issue by completing (perform architectural side effects) instructions in-order. So even if two writes are made, one in each branch, by the time the write is meant to be completed, the prior branch is resolved and we know which write is actually meant to be made and the bad one can be discarded.

Doubling the execution units also isn't strictly needed - you can use the existing out-of-order core to send two sets of instructions through the same functional units. There will be more contention for the resources, possibly causing stalls, but you don't need to fully double everything.

Things similar to this idea are already done in processors - simultaneous multithreading, early branch resolution, conditional instructions, are all ideas that have similar implementation difficulties. So the reason this specific idea is not done is more in line with your last two points rather than the first two.

Re: Zen 5's 2-ahead branch predictor: how a 30 year old idea allows for new tricks

#30

Post by layer8 »

cpldcpu wrote: post #11
emn13 wrote: post #2

As a novice in this area, it's not clear to me after reading this what exactly the 2-ahead branch predictor is.

My understanding is that they do not predict the target of the next branch but of the one after the next (2-ahead). This is probably much harder than next-branch prediction but does allows to initiate code fetch much earlier to feed even deeper pipelines.

Surely you must also predict the next branch to predict the one after. Otherwise you wouldn’t know which is the one after.

Given that, I still don’t understand how predicting the next two branches is different from predicting the next branch and then the next after that, i.e. two times the same thing.

Post reply on HN