3 ms·

It's a sub-optimal strategy. A modern TAGE branch predictor is correct well over 99% of the time. So those extra instructions for the other side of the branch

by phire 2y ago

It's a sub-optimal strategy. A modern TAGE branch predictor is correct well over 99% of the time. So those extra instructions for the other side of the branch are almost always discarded. Worse, the frontend is fetching dozens of branches ahead of where the backend can actually confirm which direction to take. What are you going to do at the next branch, start decoding four possible branches? then 8, 16, 32 possible branches? Remember, most of the time you are going to throw it away. If you actually have the hardware to fetch from multiple instruction streams in parallel (which Intel's Gracemont/Goldmont/Skymont and now AMDs Zen 5 do), the better strategy is to assume your branch predictor is actually correct 100% of the time. Follow one side of the branch, then the one after it. Intel's Skymont actually decodes the next 3 branch targets in parallel because it has three decoders, each 3-wide. Intel actually introduce fake branches to break up large blocks of code, so that all three decoders are always active decoding different part of the upcoming instruction stream. The three uop streams are later merged, allowing Skymont to maintain an effect decode bandwidth of 9 instructions per cycle. If you executed both sides of the branch, you are only slightly reducing the branch misspredit delay in the rare case the branch prediction was wrong. Instead, by executing one side the next two or three predictions, Intel and AMD can make multiple decoders do work in parallel. Intel are doing 9-wide with three simpler 3-wide decoders, and AMD can do 8-wide with two simpler 4-wide decoders.

tigrou 2y ago
Are you saying that branches can be used as a way of dividing code into several parts, so that several instruction decoders can be fed at the same time? Is it because the instruction decoder is actually one of the bottlenecks, not being able to deliver instructions fast enough to the hungry frontend? If branches can be used in this way, unconditional jumps (e.g. gotos) and function calls can probably be used for similar purposes.
- phire 2y ago
  Yep. It uses the branch predictor to slice up the instruction stream and feed it to multiple instruction decoders. Because the variable length nature of x86 instructions makes it hard to implement extremely wide instruction decoders. To reach a throughput of 4 instructions per cycle of the typical 4-wide x86 decoder you actually need 16 length decoders running in parallel, one for every byte position. The next pipeline stage then picks the 4 outputs that don't overlap before feeding it into proper decoders. Intel have actually implemented a 6-wide decoder for Golden Cove, but they must really be pushing the limits of propagation delays. So it's attractive to just use two or three smaller decoders in parallel. > If branches can be used in this way, unconditional jumps (e.g. gotos) and function calls can probably be used for similar purposes. It's a common misconception that the branch predictor only predicts conditional branches. They need to predict anything that causes control flow to diverge. So unconditional branches, calls, returns, and maybe even syscalls, all count as "branches" and get handled by the branch predictor. (On most RISC instruction sets, these instruction are often labeled branch. Call is just "Branch And Link" which saves the return address in a register. To return, you just use the "Branch to Register" instruction) This is necessary because the frontend is pipelined. It takes a minimum of four cycles to fetch the instruction data from instruction cache and decode it before the frontend can even know there is a call, return or unconditional branch instruction. If we are decoding four instruction per cycle, we are already 16 instructions past the branch before we even know it's there, and it's common to have a branch every 3-4 instructions. Basically, the frontend is blind and can't see any branches. Predicting the direction of conditional branches is almost a secondary task for modern branch predictors. It's much more important to predict where the branches are and their destination, so that instruction fetch stage can request the correct data from the instruction cache and keep the pipeline fed.
  - tigrou 2y ago
    Thanks for your reply. I learned a lot. For people wondering why you need a lot of decoders with x86, this answer explain it well (see "Decode problem" part) : https://qr.ae/p2IEt9 https://qr.ae/p2IEt9

by phire 2y ago

tigrou 2y ago

Are you saying that branches can be used as a way of dividing code into several parts, so that several instruction decoders can be fed at the same time? Is it because the instruction decoder is actually one of the bottlenecks, not being able to deliver instructions fast enough to the hungry frontend? If branches can be used in this way, unconditional jumps (e.g. gotos) and function calls can probably be used for similar purposes.

phire 2y ago
Yep. It uses the branch predictor to slice up the instruction stream and feed it to multiple instruction decoders. Because the variable length nature of x86 instructions makes it hard to implement extremely wide instruction decoders. To reach a throughput of 4 instructions per cycle of the typical 4-wide x86 decoder you actually need 16 length decoders running in parallel, one for every byte position. The next pipeline stage then picks the 4 outputs that don't overlap before feeding it into proper decoders. Intel have actually implemented a 6-wide decoder for Golden Cove, but they must really be pushing the limits of propagation delays. So it's attractive to just use two or three smaller decoders in parallel. > If branches can be used in this way, unconditional jumps (e.g. gotos) and function calls can probably be used for similar purposes. It's a common misconception that the branch predictor only predicts conditional branches. They need to predict anything that causes control flow to diverge. So unconditional branches, calls, returns, and maybe even syscalls, all count as "branches" and get handled by the branch predictor. (On most RISC instruction sets, these instruction are often labeled branch. Call is just "Branch And Link" which saves the return address in a register. To return, you just use the "Branch to Register" instruction) This is necessary because the frontend is pipelined. It takes a minimum of four cycles to fetch the instruction data from instruction cache and decode it before the frontend can even know there is a call, return or unconditional branch instruction. If we are decoding four instruction per cycle, we are already 16 instructions past the branch before we even know it's there, and it's common to have a branch every 3-4 instructions. Basically, the frontend is blind and can't see any branches. Predicting the direction of conditional branches is almost a secondary task for modern branch predictors. It's much more important to predict where the branches are and their destination, so that instruction fetch stage can request the correct data from the instruction cache and keep the pipeline fed.
- tigrou 2y ago
  Thanks for your reply. I learned a lot. For people wondering why you need a lot of decoders with x86, this answer explain it well (see "Decode problem" part) : https://qr.ae/p2IEt9 https://qr.ae/p2IEt9