10 ms·

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

321 points by matt_d 2y ago

emn13 2y ago
As a novice in this area, it's not clear to me after reading this what exactly the 2-ahead branch predictor is.
- deadmutex 2y ago
  You can check out the seminal paper linked in the article. Or start by summarizing the paper with Gemini, Claude, ChatGPT, etc. to get a high level overview (and then confirm the answer by reading the paper).
  - coherentpony 2y ago
    https://link.springer.com/article/10.1007/s10676-024-09775-5 https://link.springer.com/article/10.1007/s10676-024-09775-5
- cpldcpu 2y ago
  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.
  - emn13 2y ago
    Ah, that makes sense in the context of the article - thanks!
  - layer8 2y ago
    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.
    - ithkuil 2y ago
      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.
    - Filligree 2y ago
      Building on the sibling comment: if (a) { ... } if (b) { return x; } else { return y; } The two branches can be wholly independent, but predicting the second is still a two-ahed prediction.
    - toast0 2y ago
      > 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. I'm not involved in CPU design, I just read a lot, but... I think you need to do something special to have a second prediction, because you have to track three windows of out of order execution: Window 0: code you're definitely running but is still being completed. Window 1: code from the branch you think will be taken Window 2: code from the 2-ahead branch you think will be taken. If you figure out that the window 1 branch isn't taken, you have to drop the whole pipeline (pipeline bubble). But if you figure out that window 1 is taken, then window 1 becomes window 0 and window 2 bcomes window 1. With a 1 ahead predictor, the pipeline stalls if you get to a conditional branch while speculating in window 1, because the processor can't manage three instruction windows. IMHO, it sounds like if the core is doing SMT and both threads are active, each thread only gets 1-ahead prediction because the two windows are statically divided between the cpu threads. This may mean a) a significant boost for some loads when SMT is not in use and b) SMT can branch predict in both threads in the same cycle, I don't think that was possible on AMD before (no idea for other vendors)
  - flamedoge 2y ago
    I wonder what they need before this change. Branch predictor hardware may not have accounted for depth beyond single conditional branch? but pipeline was probably always filled, unpredicted.
- hmry 2y ago
  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...
- eyegor 2y ago
  I think it just predicts 2 branches per cycle instead of 1. So it can evaluate the result of n+2 ahead of time instead of only n+1 (typical branch prediction). How this works without wrecking the L1 cache, I'm not sure. It seems like the lookahead past n+1 would make cache evictions much more likely, so maybe I'm missing something here. > Zen 5 can look farther forward in the instruction stream beyond the 2nd taken branch and as a result Zen 5 can have 3 prediction windows where all 3 windows are useful in producing instructions for decoding. The original paper is open access but I haven't read far into it: https://dl.acm.org/doi/10.1145/237090.237169 https://dl.acm.org/doi/10.1145/237090.237169
  - phire 2y ago
    > It seems like the lookahead past n+1 would make cache evictions much more likely, so maybe I'm missing something here. The frontend is already predicting dozens of branches ahead of what the backend can actually confirm. Looking ahead by one extra branch ahead doesn't really hurt. Also, modern TAGE branch predictors are scary accurate, well above 99% on most code (including unpredictable indirect jumps). Besides, the majority of branch prediction targets are already in the L1 cache, it only predicts them because it saw them recently. The branch predictor in Apple's M1 actually takes advantage of the latter fact. It doesn't predict what address to fetch next, it predicts which cacheline in L1 holds the target. So you only actually get branch predictions for targets in L1.
    - mjevans 2y ago
      That seems like a good idea against speculation based attacks too; predict within what is at hand, do not cause side effects.
      - phire 2y ago
        I didn't even notice that advantage. I was just thinking about how it minimised each branch target entry to about 16 bits. I suspect Apple are also using it as a way predictor. If the BTB points directly to the correct cacheline and each cacheline points to the next way then the only time you need to do a search is on a branch misspredit.
- sillywalk 2y ago
  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 https://dl.acm.org/doi/10.1145/237090.237169 EDIT: oops. Looks like eyegor posted the link earlier. Oh well, enjoy the abstract.
- tigrou 2y ago
  A regular branch predictor try to guess which way a branch (eg: if-else) will go before it's executed. That way, CPU can fetch and decode instructions in advance. Each side of the branch leads to the start of a new block of instructions. The last instruction of such a block is usually another branch. In other words, a branch predictor guess the address of the next block. A 2-ahead branch predictor does the same thing, but for the two subsequent blocks. As stated in the paper: "information from the current instruction block is used for predicting the address of the block following the next instruction block". Unlike a regular branch predictor, it can do that without having to wait for instructions in the next block to be decoded. That way, you can feed multiple instruction decoders at once. This is particularly useful in modern CPUs where the instruction decoder has become a bottleneck. With only 1 decoder and 1 instruction decoded per cycle (at best) it cannot cope with a wide frontend that can execute many instructions (eg: 4-6) per cycle.
Szpadel 2y ago
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
- dymk 2y ago
  Transistor count; now you have to duplicate all the decode and speculative execution circuitry for both possible branches
  - immibis 2y ago
    No, the same circuits would execute them interleaved just like they execute multiple hardware threads now
    - nomel 2y ago
      With the SMT core count having to be one less.
      - immibis 2y ago
        No.
        nomel 2y ago
        Could you expand on that a bit? How could the "same circuit" be used for twice as many things, for free. If it's currently being used as an SMT core, how could it also support the second branch prediction, for both SMT cores? I say the SMT core would be reduced by one since, rather than being used as an SMT core, it would be used as the second branch prediction thing.
- wmf 2y ago
  It's a huge waste of energy and in some cases it would even be slower because you'd execute more instructions overall. If the branch mispredict rate is around 1% it's simply not worth paying a penalty 99% of the time to get a gain 1% of the time. Maybe it would be worth doing on low-confidence branches.
IvanAchlaqullah 2y ago
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 cheap few decades latter, and every realtime 3d renderer ended up using it. [1] https://en.wikipedia.org/wiki/Z-buffering https://en.wikipedia.org/wiki/Z-buffering
- bee_rider 2y ago
  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.
  - findthewords 2y ago
    Yes, "read 10 year old papers as a source of ideas ripe for commercialization" IS common advice in universities.
    - chrisbrandow 2y ago
      A post-doc in my chemistry lab had the saying, “two weeks in the lab will save you a day in the library”
      - scns 2y ago
        Weeks of work can save hours of planning.
    - deleted 2y ago
      [deleted]
  - pornel 2y ago
    Image and video compression are like that. Ideas for mainframes in the '80s are realtime algorithms now.
gary_0 2y ago
Here's a great explanation of branch prediction, starting from the earliest implementations: https://danluu.com/branch-prediction/ https://danluu.com/branch-prediction/
- skywal_l 2y ago
  Godbolt recently did an ELI5 on computerphile about everything CPU[0] and about branch prediction in particular[1]. [0]: https://www.youtube.com/watch?v=nhXevKMm3JI&list=PLzH6n4zXuckpwdGMHgRH5N9xNHzVGCxwf https://www.youtube.com/watch?v=nhXevKMm3JI&list=PLzH6n4zXuc... [1]: https://www.youtube.com/watch?v=nczJ58WvtYo&list=PLzH6n4zXuckpwdGMHgRH5N9xNHzVGCxwf&index=3 https://www.youtube.com/watch?v=nczJ58WvtYo&list=PLzH6n4zXuc...
- holoduke 2y ago
  Thats a good read
mrlonglong 2y ago
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?
- akira2501 2y ago
  Interactions between speculative execution and virtual memory translation and caches are exploitable. It's not an inherent vulnerability in prediction.
  - paulmd 2y ago
    Sure, as long as it’s not observable in any way, it’s not observable. But the problem is that speculation has been repeatedly been found to be observable in unexpected ways from both brands. Amd, for example, has observability issues in all zen1/2/3 processors that leaks enough data to break KASLR that remain unpatched in all chips except for Milan (specifically epyc only, not ryzen). They didn’t expect cache ways to be visible in that fashion, and it’s observable that the model is incorrectly implemented. the idea cannot fail, only be failed, because if it’s observable then obviously you just did it wrong.
    - akira2501 2y ago
      The point was, you can engineer around problems that aren't _inherent_ in the design, but arise as an interaction between systems. You just change the rules of interaction between systems to mitigate the vulnerabilities. So, to your original question, we're always going to have prediction, and we're going to have to solve any vulnerabilities that arise downstream. Which, thankfully, is always an available option.
- kmeisthax 2y ago
  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/ 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
phkahler 2y ago
>> 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?
- paulmd 2y ago
  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.
  - Remnant44 2y ago
    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.
    - paulmd 2y ago
      Regardless though why would it potentially being higher in newer architectures be viewed as a good thing?
      - Remnant44 2y ago
        Because most code is not running anywhere near saturation of the available resources, and the problem is only getting worse as cores get wider. I mean, look at the Zen5 block diagram - there are 6 ALUs and 4 AGUs on the integer side alone! That's almost two entire Zen1 cores worth of execution resources, which is pretty amazing. Very, very little real world code is going to be able to get anywhere near saturating that every cycle. SMT helps improve the utilization of the execution resources that have already been paid for in the core. I'll give another example from my own experience. I write a lot of code in the computer graphics domain. Some of the more numeric-oriented routines are able to saturate the execution resources, and get approximately 0% speedup from SMT. Importantly though, there are other routines that make heavy use of lookup tables. Even though the tables reside completely within L1 cache, there are some really long dependency chains where the 3/4 cycle wait for L1 chains and causes some really low utilization of ALUs. Or at least, that's my theory. :) Regardless in that code running SMT provides about a 30% speedup "for free" which is quite impressive. I was uncertain of if SMT had a future for a while, but I think for x86 in general it provides some pretty significant gains, for a design complexity that has already been 'paid' for.
ryukoposting 2y ago
4 years after graduating college, my decision to dive into computer architecture classes has borne no fruit except my ability to loosely understand what writeups like this are talking about. But, I guess that's the point, isn't it? This is fascinating stuff, whether or not I need to know it.
vegabook 2y ago
Now all it needs is more memory bandwidth, because those two memory channels on the consumer AM5 socket are pathetic given the compute this will deliver, and especially in comparison with even the most basic ASi. I moved to an M2 Max from a chunky Zen setup and it's a revelation how much the memory bandwidth improvement accelerates intensive data work. Also for heavy-ish multitasking the Zen setup's narrow memory pipe would often choke.
- AnthonyMouse 2y ago
  There are very few applications that are actually memory bandwidth bound but aren't more suited to a GPU than a CPU. The reason people have been looking at Apple Silicon for LLMs in particular is that even though they are more suited to GPUs, they also require a lot of VRAM and NVIDIA charges an extortionate amount of money for GPUs with a lot of VRAM. What AMD should really do if they want to steal NVIDIA's thunder is to sell consumer GPUs with 64-128GB of VRAM.
  - The_Colonel 2y ago
    > What AMD should really do if they want to steal NVIDIA's thunder is to sell consumer GPUs with 64-128GB of VRAM. For gaming, it's an overkill (esp. given the price), it would be useful only for LLM enthusiasts which isn't that big of a market.
    - AnthonyMouse 2y ago
      Then how come so many people are buying GPUs with that amount of VRAM for extraordinary amounts of money? Nobody said it was for gaming. Though of course consumers could use it for both.
      - kimixa 2y ago
        But AMD already offer GPUs with that amount of VRAM for extraordinary amounts of money, so there'll be no change? And from what I hear they're selling every one they're producing, even to the level where there's a ~6 month waiting list. So even if they reduced the price, the only difference would be that the list would get longer and AMD got less money. No more devices would actually make into people's hands, being production limited.
im3w1l 2y ago
I still ahve no idea what a 2-ahead branch predictor is.
- adrian_b 2y ago
  You can better start by reading the old research papers linked in the article. In general, the older research papers suppose that the reader knows much less about such subjects, because they were still much more niche knowledge at that time.
  - im3w1l 2y ago
    Okay, so a "block" is a sequence of instructions that can be executed from top to bottom, i.e. only the last instruction may be a jump. A 2-ahead branch predictor is a branch predictor that predicts not which block to run next after the current one, but rather, which block should be run after that one.
brcmthrowaway 2y ago
Did the paper author get a cut from AMD?
- adrian_b 2y ago
  They have no reason to give him any cut. On the contrary, he points that one of their most important innovations is not that innovative, because it was analyzed in detail almost 30 years ago. Before AMD, Intel had started to use such multiple decoders in their Atom cores, now rebranded as E-cores (efficient cores). The multiple decoders have been first used in Tremont (2020), then in Gracemont (2021) and Crestmont (2023), and now in Skymont (2024). It is hard to predict which of the decoders of Skymont (triple 3-instruction decoder) or of Zen 5 (double 4-instruction decoder) is better. AMD has made the choice of the double decoder because their core uses SMT, and a double decoder is easy to be partitioned into two decoders when both simultaneous threads are active.
ksec 2y ago
It will be interesting to see the SMT performance, I am expecting this would provide benefits and be further refined in future generation. With Zen5c we get 192 Core or 384vCPU. We should be getting 256 Core with Zen 6c next year. Which means on a Dual Socket 1U Server, that is a potential of 512 Core with 1024 vCPU. Whatever Web App Scaling issues we had in 2014 could now fit into a single server, assuming we somehow manage to cool the thing. Even at 1 RPS per vCPU that is 1000 RPS, excluding cache hit. Even on HN front-page dont hit the server at 1000 Page View per second.
- teaearlgraycold 2y ago
  Web app scaling issues are usually around database latency.
  - CodesInChaos 2y ago
    In my experience, scaling is limited by database throughput, not latency.
    - codesnik 2y ago
      well, db latency in some naive unoptimized app with multiple sequential queries directly affects _app_'s throughput
    - teaearlgraycold 2y ago
      Depends. Most apps that are slow have shitty app code with N+1 queries. If you can get past that stage and write good enough app code then eventually you’ll hit database throughout issues.
  - jeltz 2y ago
    But database performance is also a lot about CPU and RAM speed plus concurrent use of those resources.
  - jiggawatts 2y ago
    Only because the database is on the far end of a network hop, and then all too often its storage is remote from its compute as well. This is the most common scenario in enterprise or cloud deployments, where for good measure a couple of firewalls, load balancers, routers, and reverse proxies are added at every stage.
pyrolistical 2y ago
We would need more branch hints? https://github.com/ziglang/zig/issues/5177 https://github.com/ziglang/zig/issues/5177 Cold, warm, warmer, omit hot as it is the default? Sometimes you would set all branches to be cold except one
sholladay 2y ago
Despite being aware of AMD’s Zen chips, for a moment I thought this was about a ZEN player. Good times! https://en.wikipedia.org/wiki/Creative_Zen https://en.wikipedia.org/wiki/Creative_Zen
hnpl 2y ago
I'd love to see the performance data before judging whether it is a good idea. There's no information on the branch prediction penalty of this approach as well. Anyway, I think the intuition of this approach is to aggressively fetch/decode instructions that might not already in L1 instruction cache / micro-op cache. This is important for x86 (and probably RISC-V) because both have varied instruction length, and just by looking at an instruction cache block, the core wouldn't know how to decode the instruction in the cache block. Both ISAs (x86, RISC-V) require knowing the PC of at least one instruction to start decoding an instruction cache block. So, knowing where the application can jump to 2 blocks ahead helps the core fetching/decoding further ahead compared to the current approach. This approach is comparable to instruction prefetching, though, instruction prefetching does not give the core information about the starting point. (High performance ARM cores probably won't suffer from the "finding the starting point" problem because every instruction has the length of 32-bit, so the decoding procedure can be done in parallel without knowing a starting point). This approach likely benefits front-end heavy applications (applications with hot code blocks scatter everywhere in the binary, e.g., cloud workloads). I wonder if there's any performance benefit/hit for other types of applications.
yogrish 2y ago
When I began my career as a DSP optimization engineer, I worked on ZSP processors. I had a particular passion for branch predictions. By analyzing data, we would code and recode branch instructions to minimize mispredictions. I loved that super- scalar architecture of ZSP and its Branch prediction feature was amazing, apart from its multi Instruciton execution in a cycle.

321 points by matt_d 2y ago

emn13 2y ago

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

deadmutex 2y ago
You can check out the seminal paper linked in the article. Or start by summarizing the paper with Gemini, Claude, ChatGPT, etc. to get a high level overview (and then confirm the answer by reading the paper).
- coherentpony 2y ago
  https://link.springer.com/article/10.1007/s10676-024-09775-5 https://link.springer.com/article/10.1007/s10676-024-09775-5
cpldcpu 2y ago
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.
- emn13 2y ago
  Ah, that makes sense in the context of the article - thanks!
- layer8 2y ago
  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.
  - ithkuil 2y ago
    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.
  - Filligree 2y ago
    Building on the sibling comment: if (a) { ... } if (b) { return x; } else { return y; } The two branches can be wholly independent, but predicting the second is still a two-ahed prediction.
  - toast0 2y ago
    > 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. I'm not involved in CPU design, I just read a lot, but... I think you need to do something special to have a second prediction, because you have to track three windows of out of order execution: Window 0: code you're definitely running but is still being completed. Window 1: code from the branch you think will be taken Window 2: code from the 2-ahead branch you think will be taken. If you figure out that the window 1 branch isn't taken, you have to drop the whole pipeline (pipeline bubble). But if you figure out that window 1 is taken, then window 1 becomes window 0 and window 2 bcomes window 1. With a 1 ahead predictor, the pipeline stalls if you get to a conditional branch while speculating in window 1, because the processor can't manage three instruction windows. IMHO, it sounds like if the core is doing SMT and both threads are active, each thread only gets 1-ahead prediction because the two windows are statically divided between the cpu threads. This may mean a) a significant boost for some loads when SMT is not in use and b) SMT can branch predict in both threads in the same cycle, I don't think that was possible on AMD before (no idea for other vendors)
- flamedoge 2y ago
  I wonder what they need before this change. Branch predictor hardware may not have accounted for depth beyond single conditional branch? but pipeline was probably always filled, unpredicted.
hmry 2y ago
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...
eyegor 2y ago
I think it just predicts 2 branches per cycle instead of 1. So it can evaluate the result of n+2 ahead of time instead of only n+1 (typical branch prediction). How this works without wrecking the L1 cache, I'm not sure. It seems like the lookahead past n+1 would make cache evictions much more likely, so maybe I'm missing something here. > Zen 5 can look farther forward in the instruction stream beyond the 2nd taken branch and as a result Zen 5 can have 3 prediction windows where all 3 windows are useful in producing instructions for decoding. The original paper is open access but I haven't read far into it: https://dl.acm.org/doi/10.1145/237090.237169 https://dl.acm.org/doi/10.1145/237090.237169
- phire 2y ago
  > It seems like the lookahead past n+1 would make cache evictions much more likely, so maybe I'm missing something here. The frontend is already predicting dozens of branches ahead of what the backend can actually confirm. Looking ahead by one extra branch ahead doesn't really hurt. Also, modern TAGE branch predictors are scary accurate, well above 99% on most code (including unpredictable indirect jumps). Besides, the majority of branch prediction targets are already in the L1 cache, it only predicts them because it saw them recently. The branch predictor in Apple's M1 actually takes advantage of the latter fact. It doesn't predict what address to fetch next, it predicts which cacheline in L1 holds the target. So you only actually get branch predictions for targets in L1.
  - mjevans 2y ago
    That seems like a good idea against speculation based attacks too; predict within what is at hand, do not cause side effects.
    - phire 2y ago
      I didn't even notice that advantage. I was just thinking about how it minimised each branch target entry to about 16 bits. I suspect Apple are also using it as a way predictor. If the BTB points directly to the correct cacheline and each cacheline points to the next way then the only time you need to do a search is on a branch misspredit.
sillywalk 2y ago
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 https://dl.acm.org/doi/10.1145/237090.237169 EDIT: oops. Looks like eyegor posted the link earlier. Oh well, enjoy the abstract.
tigrou 2y ago
A regular branch predictor try to guess which way a branch (eg: if-else) will go before it's executed. That way, CPU can fetch and decode instructions in advance. Each side of the branch leads to the start of a new block of instructions. The last instruction of such a block is usually another branch. In other words, a branch predictor guess the address of the next block. A 2-ahead branch predictor does the same thing, but for the two subsequent blocks. As stated in the paper: "information from the current instruction block is used for predicting the address of the block following the next instruction block". Unlike a regular branch predictor, it can do that without having to wait for instructions in the next block to be decoded. That way, you can feed multiple instruction decoders at once. This is particularly useful in modern CPUs where the instruction decoder has become a bottleneck. With only 1 decoder and 1 instruction decoded per cycle (at best) it cannot cope with a wide frontend that can execute many instructions (eg: 4-6) per cycle.

Szpadel 2y ago

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

dymk 2y ago
Transistor count; now you have to duplicate all the decode and speculative execution circuitry for both possible branches
- immibis 2y ago
  No, the same circuits would execute them interleaved just like they execute multiple hardware threads now
  - nomel 2y ago
    With the SMT core count having to be one less.
    - immibis 2y ago
      No.
      - nomel 2y ago
        Could you expand on that a bit? How could the "same circuit" be used for twice as many things, for free. If it's currently being used as an SMT core, how could it also support the second branch prediction, for both SMT cores? I say the SMT core would be reduced by one since, rather than being used as an SMT core, it would be used as the second branch prediction thing.
wmf 2y ago
It's a huge waste of energy and in some cases it would even be slower because you'd execute more instructions overall. If the branch mispredict rate is around 1% it's simply not worth paying a penalty 99% of the time to get a gain 1% of the time. Maybe it would be worth doing on low-confidence branches.

IvanAchlaqullah 2y ago

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 cheap few decades latter, and every realtime 3d renderer ended up using it. [1] https://en.wikipedia.org/wiki/Z-buffering https://en.wikipedia.org/wiki/Z-buffering

bee_rider 2y ago
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.
- findthewords 2y ago
  Yes, "read 10 year old papers as a source of ideas ripe for commercialization" IS common advice in universities.
  - chrisbrandow 2y ago
    A post-doc in my chemistry lab had the saying, “two weeks in the lab will save you a day in the library”
    - scns 2y ago
      Weeks of work can save hours of planning.
  - deleted 2y ago
    [deleted]
- pornel 2y ago
  Image and video compression are like that. Ideas for mainframes in the '80s are realtime algorithms now.

gary_0 2y ago

Here's a great explanation of branch prediction, starting from the earliest implementations: https://danluu.com/branch-prediction/ https://danluu.com/branch-prediction/

skywal_l 2y ago
Godbolt recently did an ELI5 on computerphile about everything CPU[0] and about branch prediction in particular[1]. [0]: https://www.youtube.com/watch?v=nhXevKMm3JI&list=PLzH6n4zXuckpwdGMHgRH5N9xNHzVGCxwf https://www.youtube.com/watch?v=nhXevKMm3JI&list=PLzH6n4zXuc... [1]: https://www.youtube.com/watch?v=nczJ58WvtYo&list=PLzH6n4zXuckpwdGMHgRH5N9xNHzVGCxwf&index=3 https://www.youtube.com/watch?v=nczJ58WvtYo&list=PLzH6n4zXuc...
holoduke 2y ago
Thats a good read

mrlonglong 2y ago

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?

akira2501 2y ago
Interactions between speculative execution and virtual memory translation and caches are exploitable. It's not an inherent vulnerability in prediction.
- paulmd 2y ago
  Sure, as long as it’s not observable in any way, it’s not observable. But the problem is that speculation has been repeatedly been found to be observable in unexpected ways from both brands. Amd, for example, has observability issues in all zen1/2/3 processors that leaks enough data to break KASLR that remain unpatched in all chips except for Milan (specifically epyc only, not ryzen). They didn’t expect cache ways to be visible in that fashion, and it’s observable that the model is incorrectly implemented. the idea cannot fail, only be failed, because if it’s observable then obviously you just did it wrong.
  - akira2501 2y ago
    The point was, you can engineer around problems that aren't _inherent_ in the design, but arise as an interaction between systems. You just change the rules of interaction between systems to mitigate the vulnerabilities. So, to your original question, we're always going to have prediction, and we're going to have to solve any vulnerabilities that arise downstream. Which, thankfully, is always an available option.
kmeisthax 2y ago
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/ 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

phkahler 2y ago

>> 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?

paulmd 2y ago
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.
- Remnant44 2y ago
  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.
  - paulmd 2y ago
    Regardless though why would it potentially being higher in newer architectures be viewed as a good thing?
    - Remnant44 2y ago
      Because most code is not running anywhere near saturation of the available resources, and the problem is only getting worse as cores get wider. I mean, look at the Zen5 block diagram - there are 6 ALUs and 4 AGUs on the integer side alone! That's almost two entire Zen1 cores worth of execution resources, which is pretty amazing. Very, very little real world code is going to be able to get anywhere near saturating that every cycle. SMT helps improve the utilization of the execution resources that have already been paid for in the core. I'll give another example from my own experience. I write a lot of code in the computer graphics domain. Some of the more numeric-oriented routines are able to saturate the execution resources, and get approximately 0% speedup from SMT. Importantly though, there are other routines that make heavy use of lookup tables. Even though the tables reside completely within L1 cache, there are some really long dependency chains where the 3/4 cycle wait for L1 chains and causes some really low utilization of ALUs. Or at least, that's my theory. :) Regardless in that code running SMT provides about a 30% speedup "for free" which is quite impressive. I was uncertain of if SMT had a future for a while, but I think for x86 in general it provides some pretty significant gains, for a design complexity that has already been 'paid' for.

ryukoposting 2y ago

4 years after graduating college, my decision to dive into computer architecture classes has borne no fruit except my ability to loosely understand what writeups like this are talking about. But, I guess that's the point, isn't it? This is fascinating stuff, whether or not I need to know it.

vegabook 2y ago

Now all it needs is more memory bandwidth, because those two memory channels on the consumer AM5 socket are pathetic given the compute this will deliver, and especially in comparison with even the most basic ASi. I moved to an M2 Max from a chunky Zen setup and it's a revelation how much the memory bandwidth improvement accelerates intensive data work. Also for heavy-ish multitasking the Zen setup's narrow memory pipe would often choke.

AnthonyMouse 2y ago
There are very few applications that are actually memory bandwidth bound but aren't more suited to a GPU than a CPU. The reason people have been looking at Apple Silicon for LLMs in particular is that even though they are more suited to GPUs, they also require a lot of VRAM and NVIDIA charges an extortionate amount of money for GPUs with a lot of VRAM. What AMD should really do if they want to steal NVIDIA's thunder is to sell consumer GPUs with 64-128GB of VRAM.
- The_Colonel 2y ago
  > What AMD should really do if they want to steal NVIDIA's thunder is to sell consumer GPUs with 64-128GB of VRAM. For gaming, it's an overkill (esp. given the price), it would be useful only for LLM enthusiasts which isn't that big of a market.
  - AnthonyMouse 2y ago
    Then how come so many people are buying GPUs with that amount of VRAM for extraordinary amounts of money? Nobody said it was for gaming. Though of course consumers could use it for both.
    - kimixa 2y ago
      But AMD already offer GPUs with that amount of VRAM for extraordinary amounts of money, so there'll be no change? And from what I hear they're selling every one they're producing, even to the level where there's a ~6 month waiting list. So even if they reduced the price, the only difference would be that the list would get longer and AMD got less money. No more devices would actually make into people's hands, being production limited.

im3w1l 2y ago

I still ahve no idea what a 2-ahead branch predictor is.

adrian_b 2y ago
You can better start by reading the old research papers linked in the article. In general, the older research papers suppose that the reader knows much less about such subjects, because they were still much more niche knowledge at that time.
- im3w1l 2y ago
  Okay, so a "block" is a sequence of instructions that can be executed from top to bottom, i.e. only the last instruction may be a jump. A 2-ahead branch predictor is a branch predictor that predicts not which block to run next after the current one, but rather, which block should be run after that one.

brcmthrowaway 2y ago

Did the paper author get a cut from AMD?

adrian_b 2y ago
They have no reason to give him any cut. On the contrary, he points that one of their most important innovations is not that innovative, because it was analyzed in detail almost 30 years ago. Before AMD, Intel had started to use such multiple decoders in their Atom cores, now rebranded as E-cores (efficient cores). The multiple decoders have been first used in Tremont (2020), then in Gracemont (2021) and Crestmont (2023), and now in Skymont (2024). It is hard to predict which of the decoders of Skymont (triple 3-instruction decoder) or of Zen 5 (double 4-instruction decoder) is better. AMD has made the choice of the double decoder because their core uses SMT, and a double decoder is easy to be partitioned into two decoders when both simultaneous threads are active.

ksec 2y ago

It will be interesting to see the SMT performance, I am expecting this would provide benefits and be further refined in future generation. With Zen5c we get 192 Core or 384vCPU. We should be getting 256 Core with Zen 6c next year. Which means on a Dual Socket 1U Server, that is a potential of 512 Core with 1024 vCPU. Whatever Web App Scaling issues we had in 2014 could now fit into a single server, assuming we somehow manage to cool the thing. Even at 1 RPS per vCPU that is 1000 RPS, excluding cache hit. Even on HN front-page dont hit the server at 1000 Page View per second.

teaearlgraycold 2y ago
Web app scaling issues are usually around database latency.
- CodesInChaos 2y ago
  In my experience, scaling is limited by database throughput, not latency.
  - codesnik 2y ago
    well, db latency in some naive unoptimized app with multiple sequential queries directly affects _app_'s throughput
  - teaearlgraycold 2y ago
    Depends. Most apps that are slow have shitty app code with N+1 queries. If you can get past that stage and write good enough app code then eventually you’ll hit database throughout issues.
- jeltz 2y ago
  But database performance is also a lot about CPU and RAM speed plus concurrent use of those resources.
- jiggawatts 2y ago
  Only because the database is on the far end of a network hop, and then all too often its storage is remote from its compute as well. This is the most common scenario in enterprise or cloud deployments, where for good measure a couple of firewalls, load balancers, routers, and reverse proxies are added at every stage.

pyrolistical 2y ago

We would need more branch hints? https://github.com/ziglang/zig/issues/5177 https://github.com/ziglang/zig/issues/5177 Cold, warm, warmer, omit hot as it is the default? Sometimes you would set all branches to be cold except one

sholladay 2y ago

Despite being aware of AMD’s Zen chips, for a moment I thought this was about a ZEN player. Good times! https://en.wikipedia.org/wiki/Creative_Zen https://en.wikipedia.org/wiki/Creative_Zen

hnpl 2y ago

I'd love to see the performance data before judging whether it is a good idea. There's no information on the branch prediction penalty of this approach as well. Anyway, I think the intuition of this approach is to aggressively fetch/decode instructions that might not already in L1 instruction cache / micro-op cache. This is important for x86 (and probably RISC-V) because both have varied instruction length, and just by looking at an instruction cache block, the core wouldn't know how to decode the instruction in the cache block. Both ISAs (x86, RISC-V) require knowing the PC of at least one instruction to start decoding an instruction cache block. So, knowing where the application can jump to 2 blocks ahead helps the core fetching/decoding further ahead compared to the current approach. This approach is comparable to instruction prefetching, though, instruction prefetching does not give the core information about the starting point. (High performance ARM cores probably won't suffer from the "finding the starting point" problem because every instruction has the length of 32-bit, so the decoding procedure can be done in parallel without knowing a starting point). This approach likely benefits front-end heavy applications (applications with hot code blocks scatter everywhere in the binary, e.g., cloud workloads). I wonder if there's any performance benefit/hit for other types of applications.

yogrish 2y ago

When I began my career as a DSP optimization engineer, I worked on ZSP processors. I had a particular passion for branch predictions. By analyzing data, we would code and recode branch instructions to minimize mispredictions. I loved that super- scalar architecture of ZSP and its Branch prediction feature was amazing, apart from its multi Instruciton execution in a cycle.