5 ms·

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 b

• 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.
  • deleted 2y ago
    [deleted]
  • kolbe 2y ago
    The vast vast vast majority of instruction pipelines are sparse. You can pack in non-dependent instructions essentially for free.
• sapiogram 2y ago
  Disclaimer: I don't work in this field, just an enthusiast. As far as I can tell, branch predictors have always been too good for it to be worth it. Moderns CPUs have instruction reorder buffers that are hundreds of instructions deep, so even if only 8 of those instructions are conditional jumps, there's 256 different paths your program could take. If your branch predictor predicts all 8 correctly >50% of the time (It does), doing 256x the work to cover your ass is not worth it.
• swatcoder 2y ago
  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'll quickly realize "well, yeah, control flow is almost always going to go this way and we just have this branch so we can handle the exceptional case" -- compilers can often deduce this pretty well themselves now, and cpus/jits/runtimes can develop some pretty impressive heuristics as well, and when all those fail you can often add explicit hints in your code that tell your compiler/etc what you expect if they can't guess.
  • branko_d 2y ago
    > 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.
    • kllrnohj 2y ago
      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.
      • emn13 2y ago
        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.
        • orf 2y ago
          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.
• 0x000xca0xfe 2y ago
  - Side effects; how do you handle two different writes to memory? - Double the execution units; very expensive for wide vector units - Massive waste of energy as half the resources will always be wasted no matter what - Bad scaling, i.e. four branches ahead would require 16x the resources
  • isotypic 2y ago
    Handling two different writes to memory is not really a concern - existing speculative/out of order processors already solve this issue by completing (perform architectural side effects) instructions in-order. So even if two writes are made, one in each branch, by the time the write is meant to be completed, the prior branch is resolved and we know which write is actually meant to be made and the bad one can be discarded. Doubling the execution units also isn't strictly needed - you can use the existing out-of-order core to send two sets of instructions through the same functional units. There will be more contention for the resources, possibly causing stalls, but you don't need to fully double everything. Things similar to this idea are already done in processors - simultaneous multithreading, early branch resolution, conditional instructions, are all ideas that have similar implementation difficulties. So the reason this specific idea is not done is more in line with your last two points rather than the first two.
• eigenform 2y ago
  Most branches are biased one way or the other. "Fetching down both paths" means not exploiting any information you might have gathered about a branch being biased - I think that would be equivalent to randomly predicting the branch (except for it would cost more than a random predictor because you're actually fetching both ways instead of just one).
• bsder 2y ago
  > why when we have a conditional branch we cannot just fetch and prepare instructions for both possible branches and then discard the incorrect one? We actually do that. It's called a GPU. And it sucks for general code.
• MBCook 2y ago
  We reached 90% accuracy decades ago. Depending on workload modern chips can do way better. So basically it’s just nowhere near worth it. Much better to use those chip resources for another thread or core.
• ithkuil 2y ago
  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_vulnerability) https://en.m.wikipedia.org/wiki/Spectre_(security_vulnerabil...
• deleted 2y ago
  [deleted]
• 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.
• gpderetta 2y ago
  Divergence. On an OoO pipeline fetch might be ahead of retire by hundreds of instructions. That's dozen of branches, and if each causes execution to speculatively fork, it wouldn't scale. You could potentially do it only for predicted "unpredictable" branches. Now the tradeoff is wasted power and execution units for dead work and so far the tradeoff was just not worth it. Some form of this has been experimented with. In the late '90 SPRC experimented with scouting threads and as mentioned else thread the Efficient Intel cores can fetch (but not execute) across branches.