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

Post by CoastalCoder » Fri, Jul 26, 2024, 11:47 PM UTC

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…

Post by Terr_ » Fri, Jul 26, 2024, 11:52 PM UTC

CoastalCoder wrote: post #41

Terr_ wrote: post #33

Earlier quoted context omitted.

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…

Mind editing that to give a spoiler alert?

Post by eyegor » Fri, Jul 26, 2024, 11:54 PM UTC

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.

Post by Filligree » Sat, Jul 27, 2024, 12:06 AM UTC

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.

  if (a) { ... }

  if (b) { return x; } else { return y; }

Post by twoodfin » Sat, Jul 27, 2024, 12:18 AM UTC

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…