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

31–40 of 196 posts

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

#31

Post by orf »

emn13 wrote: post #28
kllrnohj wrote: post #24

Earlier quoted context omitted.

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.

If the size of the data is small, a linear search through a contiguous array is going to be far faster than anything more complex.

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

#32

Post by [deleted] »

findthewords wrote: post #10
bee_rider wrote: post #8

Earlier quoted context omitted.

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.

Yes, "read 10 year old papers as a source of ideas ripe for commercialization" IS common advice in universities.

[deleted]

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

#33

Post by Terr_ »

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.

In a series of books by David Brin [0] there is a galaxy-wide institution known as the library, and civilizations regularly mine its millions of years of data for suddenly-relevant-again techniques and technologies.

I remember one bit where a species had launched some tricky fleet-destroying weapon to surprise their enemies with esoteric physics, only to have it reversed against them, possibly because the Librarian that once helped their research-agent wasn't entirely unbiased.

[0] https://en.m.wikipedia.org/wiki/Uplift_Universe

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

#34

Post by ithkuil »

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

That's called speculative execution and IIRC all modern CPUs are doing it.

It requires more silicon to hold more microarchitectural state and more execution units to fully exploit the technique, but superscalar CPUs already have those since they are essential to exploit instruction level parallelism in non-branchy code. The rest is "just" a lot of headaches to handle complicated stuff such as aliasing, interrupts, ... But hardware engineers are such wizards they can do these things too.

Turns out however that speculative execution opens up a possibility of abusing a cache timing side channel to extract information from data touched by branches of code that has been only speculatively executed but whose architectural side effects were not committed (i.e. not "really" executed).

Which includes code that had been explicitly not executed because of a conditional check (e.g. permissions, ...)

A familiar instance of such an attack is Spectre [1]

1: https://en.m.wikipedia.org/wiki/Spectre_(security_vulnerabil...

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

#35

Post by barrkel »

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.

B-trees are cache friendly, spending more time doing linear scans at each level to keep the tree shallow, and thus indirection less frequent. They're designed for high latency indirection - loading pages from spinning rust.

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

#36

Post by ithkuil »

layer8 wrote: post #30
cpldcpu wrote: post #11

Earlier quoted context omitted.

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.

Interestingly you can build a branch predictor that predicts the second branch without predicting the first.

A branch predictor result is just a tuple of ("branch instruction address", "branch target address") that hints the processor that when the CPU will encounter a given branch instructions in the future (at "branch instruction address") it will likely branch to the branch target and so it would make sense to start fetching that address and filling the instruction pipeline with whatever steps are safe to perform before the jump will be actually performed.

Now, commonly this branch happens to be at the end of the current basic block and I assume some branch predictors may also leverage this fact in order to encode only offsets from the current instruction pointer.

But there is no reason why the branch location might be after some other branches may be taken. As long as the cpu eventually gets to that branch location the prediction will be useful. If the IP never reaches that location it's like the branch was never actually taken.

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

#37

Post by AceJohnny2 »

Terr_ wrote: post #33
bee_rider wrote: post #8

Earlier quoted context omitted.

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.

In a series of books by David Brin [0] there is a galaxy-wide institution known as the library, and civilizations regularly mine its millions of years of data for suddenly-relevant-again techniques and technologies. I remember one bit where a species had launched some tricky fleet-destroying weapon to surprise their enemies with esoteric physics, only to have it reversed against them, possibly because the Librarian t…

Also in Vinge's Deepness in the Sky, there aren't really "programmers" as we know them anymore, but "programmer-archeologists" that just search the archives for code components to reuse.

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

#38

Post by phkahler »

>> Now when Zen 5 has two threads active, the decode clusters and the accompanying fetch pipes are statically partitioned.

This sounds like a big boost for hyper threading performance. My Zen1 gets about 25 percent faster due to HT. Has anyone tested the newer ones in this regard?

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

#40

Post by hmry »

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.

You're not alone. Non-novice, same here. Article spends a lot of time explaining the absolute basics of branch prediction but then when it gets to 2-ahead it just skips over explaining it...
Post reply on HN