5 ms·

Every time I see people trying to eliminate branches, I wonder, do we realize that having long pipelines where a branch misprediction stalls the pipeline is not

Every time I see people trying to eliminate branches, I wonder, do we realize that having long pipelines where a branch misprediction stalls the pipeline is not actually a necessary part of architecture? The pipeline is long because we do lots of analysis and translation on the fly, just in time, which could easily be done in most cases ahead of time, as it's not a very stateful algorithm. This is how Transmeta Crusoe CPUs worked. Imagine NOT caring that you have a branch. After all, if you think about it, all operations are branches. Down to bitwise operations and summing two numbers. It's branching in the ALU, carry bits and what not. You can't compute absolutely anything without looking at the state of one or more bits, and making a decision that changes the outcome. But the reason those branches don't hurt performance is that they're not branches on the main pipeline. These local branches have a very short (or non-existent) "pipeline". And the main pipeline is therefore not affected, despite the actual state of the system is.

robertlagrant 3y ago
> After all, if you think about it, all operations are branches Isn't this definition the crux of it? If you redefine everything as a Branch™, even things that are not branches, then you can definitely precompute some Branch™es. But the sort of non-Branch™ branch elimination is talking about actually branching computation routes in code due to an if/else statement or similar, is it not? That would still be useful to do in your world of Branch™es, just only the Branch™es that try and compute the results of more than one future at the same time (i.e. branches).
- deleted 3y ago
  [deleted]
dragontamer 3y ago
> The pipeline is long because we do lots of analysis and translation on the fly, just in time, which could easily be done in most cases ahead of time, as it's not a very stateful algorithm. You're going down the wrong path, again, as Intel did with Itanium. We have pipelines because CPUs are performing Tomasulo's algorithm at runtime, because there are 10 pipelines in practice (for Intel systems), and all can be run in parallel. Multiply can be issued on pipeline0, pipeline1, or pipeline5. If there are 3 multiply instructions, all three pipelines (p0, p1, and p5) all get issued a multiply on _THIS_ clock tick. ---------- The analysis must be dynamic because instructions such as "mov" can take a variable amount of time: loading data from L1 cache is 4-clock ticks, L2 cache is 40 clock ticks, L3 cache is ~150 clock ticks, and RAM is 400+ clock ticks. That means a "lazy" strategy, where you analyze the state of the pipeline "as late as possible" before making a decision wins out. If you do pre-analysis (ie: what Intel's compiler was supposed to do with Itanium), you pretty much lose out on all variable-time instructions (ex: cache vs RAM). If you know for certain that you have no memory-operations, then you probably should use a GPU instead of a CPU. --------- theLoop: mov ebx, eax[ecx] ; y = array[x] add ebx, edx ; y += z add ecx, 4 cmp ecx, jnz theLoop How long should you schedule the "add" instruction in the above assembly code? If you got a dynamic system just analyzing your pipelines and "lazily" issuing the instructions, you "perform it when its ready" (ie: after the mov instruction is complete, as you need ebx / variable-y to have been finished reading from RAM before progressing). "add ecx, 4" can actually be done right now in parallel. You split ecx into two registers (ecx-old and ecx-new). You issue "mov ebx, eax[ecx-old]", and then you can execute future instructions with ecx-new. If the next loop is branch predicted (as would be the case in binary search, since you almost always loop), the pipeline/branch prediction stuff works together and you can execute mov ebx, eax[ecx0], mov ebx, eax[ecx1], mov ebx, eax[ecx2], mov ebx, eax[ecx3]... all in parallel (!!!!), as ecx3 gets branch predicted and multiple loops start running in parallel.. Its not hard, its not very difficult analysis, its low power. Everyone does this parallel computation now. If you go static / compiled ahead-of-time, you can't do this kind of thing anymore. So you lose out in speed compared to regular CPUs that have OoO analysis going on. ---------- Furthermore, most code with branches can seemingly be replaced with branchless code (ex: cmov instructions, min instruction, max instruction, etc. etc.) So instead of magic compilers trying to solve an unsolvable problem (how do you schedule memory load/stores to keep the processor busy even though you don't know how long any memory operation takes...)... you write a magic compiler that solves a very easy to solve problem. (IE: convert the branchy-if statement into a branchless max or branchless cmov instruction instead). -------- EDIT: I added "theLoop:" to the assembly above, because I realized that "branches" can be beneficial in the face of OoO / Tomasulo's algorithm. "Executing future loops" before the 1st loop is done is very beneficial.
- awesomeMilou 3y ago
  I have little experience in hardware related performance optimizations, so excuse me if some of the things you wrote went over my head. But this sentence: > Everyone does this parallel computation now. If you go static / compiled ahead-of-time, you can't do this kind of thing anymore. So you lose out in speed compared to regular CPUs that have OoO analysis going on. Are you implying that in JIT compiled languages I can care less about making my code branchless, since both CPU and JIT compiler will optimize to a branchless version on the fly whereever possible, whereas in AoT compiled languages such as C++ I loose this edge? Are JIT compiled languages just better when it comes to utilizing the branch predictor?
  - dragontamer 3y ago
    JIT is completely separate issue entirely. I'm not talking about C++ vs Java here. I'm talking about the designs of different assembly languages. I'm talking about Intel Itanium (ia64) vs AMD x86-64. Or VLIW (compiler-driven parallelism) vs Out-of-Order pipelined processors. Intel Itanium had "premade bundles". Without getting into too far into the weeds, *the compiler* was responsible for discovering parallelism. The compiler then bundled instructions together So think of this code: theLoop: mov ebx, eax[ecx] ; y = array[x] add ebx, edx ; y += z add ecx, 4 cmp ecx, jnz theLoop The Itanium Assembly language would allow the compiler to emit: mov ebx, eax[ecx] ; add ebx, edx : add ecx, 4; // This line executed in parallel cmp ecx; jnz theLoop The compiler discovers that "add ebx, edx : add ecx, 4" are both independent, and therefore "bundles" them together. Intel Itanium then ran faster and without as much need of a decoder to discover this information ahead of time. But look at how few optimizations are available to Itanium or its compiler!! The amount of parallelism in practice (for classic x86 code) was much bigger, especially when you consider Tomasulo's Algorithm.
  - mhh__ 3y ago
    JITs can do a lot of things but in practice its a better mental model to just assume that the equivalent AOT code is faster and the JIT is merely recouping performance lost to the inefficiencies of interpretation or weird semantics (javascript being the implication)
Const-me 3y ago
> as it's not a very stateful algorithm It might be stateless, but it depends on many things unknown at compile time. One of them is the input data being processed. Binary search is exactly that, compiler don’t know at which position the result will be found. Another one is micro-architecture, most notably cache hierarchy, and composition of EUs inside codes. If you switch to ISA with instructions resembling the micro-ops of the current CPUs, you’ll have to re-compile for every micro-architecture. However, this one is technically solvable with JIT compiler in OSes, like current GPUs where programs ship in byte code formats (DXBC, SPIR-V, NVPTX) then user-mode half of GPU driver recompiles into actual hardware instructions. Another huge one, other CPU threads are running unknow code. Even if you drop hyper-threading making cores independent, there’re still resources shared across the complete chip: L3 cache, off-chip memory, I/O bandwidth, and electricity i.e. thermals.
- scottlamb 3y ago
  > > > as it's not a very stateful algorithm > It might be stateless, but it depends on many things unknown at compile time. > One of them is the input data being processed. Binary search is exactly that, compiler don’t know at which position the result will be found. Are you and 3cats-in-a-coat are talking about the same "it"? I think they're talking about the work that requires such a long pipeline [1], as they've stated that doing more ahead of time would reduce the length of the pipeline and thus importance of accurate branch prediction. You are talking about...the branch predictor? the application's algorithm being executed (binary search in this case)? [1] my CPU microarchitectural knowledge isn't that good; I have only the vaguest idea of what that is. Register renaming / data dependency analysis / instruction scheduling, maybe? translation to micro-ops? other things? don't know!
ChuckMcM 3y ago
Is that you Dave? :-) There was paper[1] comparing superscalar CISC approaches to uniscalar RISC in terms of work done over time versus instructions per clock. I recall telling srk at the time that it was a good treatise on how choosing the metric (IPC vs throughput) can influence ones thinking about what is "good" and what is "bad." The IPC crowd reasons that if they can get a higher IPC value, then the process guys can crank the clock and everybody wins. The thoughput crowd takes the more pragmatic approach that Moore's law is dead and making silicon clock faster melts it so being clever in the ISA wins the day. Both camps have had successes and setbacks over the last 20 years. I am really enjoying the RISC-V stuff which is getting back into this level of question with regard to CPU architectures. Also a good place to look if you want to catch up on what "modern" superscalar ideas are being added with support of instruction set flexibility. My guess is that wins the game in the long run. [1] This was in the early oughts so could have been HotChips, Microprocessor Forum, or HPC workshops.
taeric 3y ago
You could rephrase that the pipeline is long because there is a lot of independent work that you can do in a processor. Consider, for every independent operation that can be done, you can potentially do that much at the same time. And I don't just mean decode, fetch, and execute. If your computer has independent ALU and Shifting units, you can potentially be shifting something as you are also adding. Have a dedicated Adder and a Multiplication unit? No reason you can't try and do both as the same time. This directly leads to wanting multiple instructions in flight at the same time, which means you have to be able to fetch and decode instructions faster than you are processing them. Also naturally leads to situations where you want to reorder so that the N Add instructions don't keep you from seeing an independent Shift that you could do in the same time. You can think that things are more complicated than they need to be. And, you may not even be wrong. But a ton of engineering is going into making what we have. If you think you can make something a ton faster by not doing it this way, probably a good thing to dig into how accurate that claim is.
deleted 3y ago
[deleted]
mhh__ 3y ago
People have spent probably a billion dollars trying to get this to work. It's a noble goal but when will it actually stick?
jasonwatkinspdx 3y ago
I'm sorry but this is completely mistaken. Transmeta's translation did not somehow eliminate branch costs. In fact I distinctly remember a comp.arch thread and post from Linus himself while he worked at Transmeta that paraphrased was "the cpu's job is to generate cache misses as fast as possible." Compulsory misses are a thing. No form of JIT is capable of eliminating them. Capacity misses are inevitable in the real world, even with the monster caches we have now. Itanium thought it could eliminate branch costs with static analysis. How did that work out? I really wish programmers would actually read a book about computer architecture before they so confidently conclude that it's simple to build things better than state of the art processors. You are underestimating the scale of smart that has gone into current processors by at least 7 orders of magnitude in my opinion.
- rtomanek 3y ago
  Can you give some book recommendations, please?
  - jasonwatkinspdx 3y ago
    Hennessy and Patterson's Computer Architecture: A Quantitative Approach is the definitive textbook. They also have a 2nd textbook Computer Organization and Design. The former is more focused on people who might go after a Computer Engineering degree while the latter is more an exploration of microprocessor architecture relevant to a wide audience of programmers. Previous editions are available free online and just as good for learning the big picture imo. Actually the older editions might be better for learning microarchitecture specifically because the more recent editions have cut some material on that in order to cover mobile and cloud computing.

robertlagrant 3y ago

> After all, if you think about it, all operations are branches Isn't this definition the crux of it? If you redefine everything as a Branch™, even things that are not branches, then you can definitely precompute some Branch™es. But the sort of non-Branch™ branch elimination is talking about actually branching computation routes in code due to an if/else statement or similar, is it not? That would still be useful to do in your world of Branch™es, just only the Branch™es that try and compute the results of more than one future at the same time (i.e. branches).

deleted 3y ago
[deleted]

dragontamer 3y ago

> The pipeline is long because we do lots of analysis and translation on the fly, just in time, which could easily be done in most cases ahead of time, as it's not a very stateful algorithm. You're going down the wrong path, again, as Intel did with Itanium. We have pipelines because CPUs are performing Tomasulo's algorithm at runtime, because there are 10 pipelines in practice (for Intel systems), and all can be run in parallel. Multiply can be issued on pipeline0, pipeline1, or pipeline5. If there are 3 multiply instructions, all three pipelines (p0, p1, and p5) all get issued a multiply on _THIS_ clock tick. ---------- The analysis must be dynamic because instructions such as "mov" can take a variable amount of time: loading data from L1 cache is 4-clock ticks, L2 cache is 40 clock ticks, L3 cache is ~150 clock ticks, and RAM is 400+ clock ticks. That means a "lazy" strategy, where you analyze the state of the pipeline "as late as possible" before making a decision wins out. If you do pre-analysis (ie: what Intel's compiler was supposed to do with Itanium), you pretty much lose out on all variable-time instructions (ex: cache vs RAM). If you know for certain that you have no memory-operations, then you probably should use a GPU instead of a CPU. --------- theLoop: mov ebx, eax[ecx] ; y = array[x] add ebx, edx ; y += z add ecx, 4 cmp ecx, jnz theLoop How long should you schedule the "add" instruction in the above assembly code? If you got a dynamic system just analyzing your pipelines and "lazily" issuing the instructions, you "perform it when its ready" (ie: after the mov instruction is complete, as you need ebx / variable-y to have been finished reading from RAM before progressing). "add ecx, 4" can actually be done right now in parallel. You split ecx into two registers (ecx-old and ecx-new). You issue "mov ebx, eax[ecx-old]", and then you can execute future instructions with ecx-new. If the next loop is branch predicted (as would be the case in binary search, since you almost always loop), the pipeline/branch prediction stuff works together and you can execute mov ebx, eax[ecx0], mov ebx, eax[ecx1], mov ebx, eax[ecx2], mov ebx, eax[ecx3]... all in parallel (!!!!), as ecx3 gets branch predicted and multiple loops start running in parallel.. Its not hard, its not very difficult analysis, its low power. Everyone does this parallel computation now. If you go static / compiled ahead-of-time, you can't do this kind of thing anymore. So you lose out in speed compared to regular CPUs that have OoO analysis going on. ---------- Furthermore, most code with branches can seemingly be replaced with branchless code (ex: cmov instructions, min instruction, max instruction, etc. etc.) So instead of magic compilers trying to solve an unsolvable problem (how do you schedule memory load/stores to keep the processor busy even though you don't know how long any memory operation takes...)... you write a magic compiler that solves a very easy to solve problem. (IE: convert the branchy-if statement into a branchless max or branchless cmov instruction instead). -------- EDIT: I added "theLoop:" to the assembly above, because I realized that "branches" can be beneficial in the face of OoO / Tomasulo's algorithm. "Executing future loops" before the 1st loop is done is very beneficial.

awesomeMilou 3y ago
I have little experience in hardware related performance optimizations, so excuse me if some of the things you wrote went over my head. But this sentence: > Everyone does this parallel computation now. If you go static / compiled ahead-of-time, you can't do this kind of thing anymore. So you lose out in speed compared to regular CPUs that have OoO analysis going on. Are you implying that in JIT compiled languages I can care less about making my code branchless, since both CPU and JIT compiler will optimize to a branchless version on the fly whereever possible, whereas in AoT compiled languages such as C++ I loose this edge? Are JIT compiled languages just better when it comes to utilizing the branch predictor?
- dragontamer 3y ago
  JIT is completely separate issue entirely. I'm not talking about C++ vs Java here. I'm talking about the designs of different assembly languages. I'm talking about Intel Itanium (ia64) vs AMD x86-64. Or VLIW (compiler-driven parallelism) vs Out-of-Order pipelined processors. Intel Itanium had "premade bundles". Without getting into too far into the weeds, *the compiler* was responsible for discovering parallelism. The compiler then bundled instructions together So think of this code: theLoop: mov ebx, eax[ecx] ; y = array[x] add ebx, edx ; y += z add ecx, 4 cmp ecx, jnz theLoop The Itanium Assembly language would allow the compiler to emit: mov ebx, eax[ecx] ; add ebx, edx : add ecx, 4; // This line executed in parallel cmp ecx; jnz theLoop The compiler discovers that "add ebx, edx : add ecx, 4" are both independent, and therefore "bundles" them together. Intel Itanium then ran faster and without as much need of a decoder to discover this information ahead of time. But look at how few optimizations are available to Itanium or its compiler!! The amount of parallelism in practice (for classic x86 code) was much bigger, especially when you consider Tomasulo's Algorithm.
- mhh__ 3y ago
  JITs can do a lot of things but in practice its a better mental model to just assume that the equivalent AOT code is faster and the JIT is merely recouping performance lost to the inefficiencies of interpretation or weird semantics (javascript being the implication)

Const-me 3y ago

> as it's not a very stateful algorithm It might be stateless, but it depends on many things unknown at compile time. One of them is the input data being processed. Binary search is exactly that, compiler don’t know at which position the result will be found. Another one is micro-architecture, most notably cache hierarchy, and composition of EUs inside codes. If you switch to ISA with instructions resembling the micro-ops of the current CPUs, you’ll have to re-compile for every micro-architecture. However, this one is technically solvable with JIT compiler in OSes, like current GPUs where programs ship in byte code formats (DXBC, SPIR-V, NVPTX) then user-mode half of GPU driver recompiles into actual hardware instructions. Another huge one, other CPU threads are running unknow code. Even if you drop hyper-threading making cores independent, there’re still resources shared across the complete chip: L3 cache, off-chip memory, I/O bandwidth, and electricity i.e. thermals.

scottlamb 3y ago
> > > as it's not a very stateful algorithm > It might be stateless, but it depends on many things unknown at compile time. > One of them is the input data being processed. Binary search is exactly that, compiler don’t know at which position the result will be found. Are you and 3cats-in-a-coat are talking about the same "it"? I think they're talking about the work that requires such a long pipeline [1], as they've stated that doing more ahead of time would reduce the length of the pipeline and thus importance of accurate branch prediction. You are talking about...the branch predictor? the application's algorithm being executed (binary search in this case)? [1] my CPU microarchitectural knowledge isn't that good; I have only the vaguest idea of what that is. Register renaming / data dependency analysis / instruction scheduling, maybe? translation to micro-ops? other things? don't know!

ChuckMcM 3y ago

Is that you Dave? :-) There was paper[1] comparing superscalar CISC approaches to uniscalar RISC in terms of work done over time versus instructions per clock. I recall telling srk at the time that it was a good treatise on how choosing the metric (IPC vs throughput) can influence ones thinking about what is "good" and what is "bad." The IPC crowd reasons that if they can get a higher IPC value, then the process guys can crank the clock and everybody wins. The thoughput crowd takes the more pragmatic approach that Moore's law is dead and making silicon clock faster melts it so being clever in the ISA wins the day. Both camps have had successes and setbacks over the last 20 years. I am really enjoying the RISC-V stuff which is getting back into this level of question with regard to CPU architectures. Also a good place to look if you want to catch up on what "modern" superscalar ideas are being added with support of instruction set flexibility. My guess is that wins the game in the long run. [1] This was in the early oughts so could have been HotChips, Microprocessor Forum, or HPC workshops.

taeric 3y ago

You could rephrase that the pipeline is long because there is a lot of independent work that you can do in a processor. Consider, for every independent operation that can be done, you can potentially do that much at the same time. And I don't just mean decode, fetch, and execute. If your computer has independent ALU and Shifting units, you can potentially be shifting something as you are also adding. Have a dedicated Adder and a Multiplication unit? No reason you can't try and do both as the same time. This directly leads to wanting multiple instructions in flight at the same time, which means you have to be able to fetch and decode instructions faster than you are processing them. Also naturally leads to situations where you want to reorder so that the N Add instructions don't keep you from seeing an independent Shift that you could do in the same time. You can think that things are more complicated than they need to be. And, you may not even be wrong. But a ton of engineering is going into making what we have. If you think you can make something a ton faster by not doing it this way, probably a good thing to dig into how accurate that claim is.

deleted 3y ago

[deleted]

mhh__ 3y ago

People have spent probably a billion dollars trying to get this to work. It's a noble goal but when will it actually stick?

jasonwatkinspdx 3y ago

I'm sorry but this is completely mistaken. Transmeta's translation did not somehow eliminate branch costs. In fact I distinctly remember a comp.arch thread and post from Linus himself while he worked at Transmeta that paraphrased was "the cpu's job is to generate cache misses as fast as possible." Compulsory misses are a thing. No form of JIT is capable of eliminating them. Capacity misses are inevitable in the real world, even with the monster caches we have now. Itanium thought it could eliminate branch costs with static analysis. How did that work out? I really wish programmers would actually read a book about computer architecture before they so confidently conclude that it's simple to build things better than state of the art processors. You are underestimating the scale of smart that has gone into current processors by at least 7 orders of magnitude in my opinion.

rtomanek 3y ago
Can you give some book recommendations, please?
- jasonwatkinspdx 3y ago
  Hennessy and Patterson's Computer Architecture: A Quantitative Approach is the definitive textbook. They also have a 2nd textbook Computer Organization and Design. The former is more focused on people who might go after a Computer Engineering degree while the latter is more an exploration of microprocessor architecture relevant to a wide audience of programmers. Previous editions are available free online and just as good for learning the big picture imo. Actually the older editions might be better for learning microarchitecture specifically because the more recent editions have cut some material on that in order to cover mobile and cloud computing.