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

61–70 of 196 posts

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

#61

Post by kvemkon »

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.

Academic? Perhaps, applied:

"When Soviets Won the Cold War: Wading Through Pyotr Ufimstev's Work on Stealth" (26.03.2024)

https://news.ycombinator.com/item?id=39830671

> In the early 1970s, Lockheed Martin engineer Denys Overholser discovered the key to stealth technology hidden in a stack of translated Soviet technical papers. Disregarded by the Soviet academic elite, and unheard of in the United States, Pyotr Ufimstev had worked out calculations that would help win ...

Not sure of the details of this story, but in general having there enough people to grant them time just to search for something interesting seems not unrealistic.

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

#62

Post by paulmd »

Remnant44 wrote: post #60
paulmd wrote: post #55

Earlier quoted context omitted.

High SMT speedups aren’t a good thing, because those are pipeline bubbles - resources that can’t be saturated by the first thread. The ideal speedup from SMT is 0% because you’d be getting full output for a single thread. Like if you got a 50% speedup from SMT, in an ideal world that means a single thread could run 50% faster than it is, but it’s being stalled by pipeline bubbles.

For a fully compute-bound workload, you're certainly correct. That's rare though. All it takes is a couple stalls waiting on memory where a second thread is able to make progress to make that "ideal speedup" certainly be nonzero.

Regardless though why would it potentially being higher in newer architectures be viewed as a good thing?

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

#64

Post by eru »

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.

I wonder if current AI training's effort to hover up all the training data they can find will accidentally give us most of the benefits of that?

A human can only read so much, so has to discriminate. But our machines are omnivorous readers.

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

#65

Post by eru »

pornel wrote: post #18
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.

Image and video compression are like that. Ideas for mainframes in the '80s are realtime algorithms now.

I guess they are _soft_ realtime algorithms now?

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

#66

Post by kmeisthax »

mrlonglong wrote: post #39

Speculative predictors have been subjected to a number of attacks to weasel out private data. Given that so many of the common ISAs are vulnerable, are they taking steps to reduce the impact of such attacks?

The vulnerability is speculative execution, not branch prediction. The branch predictor is the thing you have to trick to force the processor to speculatively execute code in the victim program. Furthermore you also need a valid timing source to read out the results of the speculative execution.

As for how to stop that, short of boiling the ocean[0], you don't. Speculative execution is so valuable for performance that a computer without it is completely unusable. If you really want a processor without it, buy an old first-gen Pentium.

Actual practical mitigations for speculative execution vulnerabilities are varied, but at a minimum you have to ensure process separation between a victim process holding secrets and any potential attackers that may have the opportunity to influence victim process execution. Intel was caught with their hands in their pants speculating across rings, which is why you could read kernel or hypervisor memory from userspace, but on not-poorly-designed CPUs the main victim you have to worry about is HTML iframes. Different origins aren't allowed to make HTTP requests to one another[1], but they can transclude[2] one another without permission. That traditionally loaded information from the origin into the attacker's process, which could be exfiltrated with timing attacks.

The web's solution to this was actually not to process-separate iframes, at least not initially, but to take away shared-memory multithreading entirely. If you deny the attacker a timing reference then it doesn't matter what they can make the victim speculatively execute. But to do this you have to take away multithreading because otherwise a thread can just repeatedly write known data in a loop to create a clock.

[0] https://hackaday.com/2013/08/02/the-mill-cpu-architecture/

[1] At least not without the target origin allowing it via CORS

[2] e.g. hotlink images or embed iframes

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

#67

Post by eru »

orf wrote: post #31
emn13 wrote: post #28

Earlier quoted context omitted.

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.

Well, it depends on how expensive your comparison is compared to a cache miss.

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

#68

Post by tasty_freeze »

bhouston wrote: post #58
twoodfin wrote: post #49

Earlier quoted context omitted.

On the software side, garbage collection was well explored by academia for more than two decades before the JVM brought it to wide commercial adoption ca. 1995.

Lisp and Smalltalk and BASIC (to name a few) were popular languages before the JVM that used GC.

When I was in high school, I wrote a Z80 disassembler in BASIC and printed out the entire TRS-80 Model 3 ROM on a thick stack of fan folded greenline paper. I spent a lot of free time figuring out what was what and commenting the code by pen in the right margin.

The (string) garbage collector was amazingly frugal and correspondingly slow. Because the garbage collector typically ran only when memory was critically low it used almost no memory, just 4 bytes I think. (it was also possible to invoke it any time with the FRE(0) function call IIRC)

The routine would sweep all of the symbol table and expression stack looking for string pointers, and would remember the lowest (highest? I forget which) string base address which hadn't already been compacted. After each pass it would move that one string and fix the symbol table pointer (or expression stack str pointer) then do another pass. As a result, is was quadratic with the number of live strings -- so if you had a large number of small strings, it was possible for your program to lock solidly for 30 seconds or more.

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

#69

Post by sillywalk »

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.

It's from around 30 years ago, my guess is it's referring to this[0] paper from 1996. It's above my head, but it seems to help with branch prediction issues arising with both many instruction units and high-clock speed, which were sort of either or in the '90s, but I think most modern processors are both.

Multiple-block ahead branch predictors

Abstract:

A basic rule in computer architecture is that a processor cannot execute an application faster than it fetches its instructions. This paper presents a novel cost-effective mechanism called the two-block ahead branch predictor. Information from the current instruction block is not used for predicting the address of the next instruction block, but rather for predicting the block following the next instruction block. This approach overcomes the instruction fetch bottle-neck exhibited by wide-dispatch "brainiac" processors by enabling them to efficiently predict addresses of two instruction blocks in a single cycle. Furthermore, pipelining the branch prediction process can also be done by means of our predictor for "speed demon" processors to achieve higher clock rate or to improve the prediction accuracy by means of bigger prediction structures. Moreover, and unlike the previously-proposed multiple predictor schemes, multiple-block ahead branch predictors can use any of the branch prediction schemes to perform the very accurate predictions required to achieve high-performance on superscalar processors."

[0] https://dl.acm.org/doi/10.1145/237090.237169

EDIT: oops. Looks like eyegor posted the link earlier. Oh well, enjoy the abstract.

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

#70

Post by sjburt »

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.

In benchmarks, branch predictors guess correctly 90-95% of the time.
Post reply on HN