8 ms·

Execution units are often pipelined

165 points by ingve 2y ago

Vogtinator 2y ago
For x86 cores this is visible in Agner Fog's instruction performance tables: https://agner.org/optimize/#manuals https://agner.org/optimize/#manuals The latency shows after how many cycles the result of an instruction can be consumed by another, while the throughput shows how many such instructions can be pipelined per cycle, i.e. in parallel.
- wtallis 2y ago
  I believe the throughput shown in those tables is the total throughput for the whole CPU core, so it isn't immediately obvious which instructions have high throughput due to pipelining within an execution unit and which have high throughput due just to the core having several execution units capable of handling that instruction.
  - BeeOnRope 2y ago
    That's true, but another part of the tables show how many "ports" the operation can be executed on, which is enough information to concluded an operation is pipelined. For example, for many years Intel chips had a multiplier unit on a single port, with a latency of 3 cycles, but an inverse throughput of 1 cycle, so effectively pipelined across 3 stages. In any case, I think uops.info [1] has replaced Agner for up-to-date and detailed information on instruction execution. --- [1] https://uops.info/table.html https://uops.info/table.html
    - Earw0rm 2y ago
      Shame it doesn't seem to have been updated with Arrow Lake, Zen 5 and so on yet.
      - BeeOnRope 2y ago
        Yes. In the past new HW has been made available to the uops.info authors in order to run their benchmark suite and publish new numbers: I'm not sure if that just hasn't happened for the new stuff, or if they are not interested in updating it.
- ajross 2y ago
  FWIW, there are two ideas of parallelism being conflated here. One is the parallel execution of the different sequential steps of an instruction (e.g. fetch, decode, operate, retire). That's "pipelining", and it's a different idea than decoding multiple instructions in a cycle and sending them to one of many execution units (which is usually just called "dispatch", though "out of order execution" tends to connote the same idea in practice). The Fog tables try hard show the former, not the latter. You measure dispatch parallelism with benchmarks, not microscopes. Also IIRC there are still some non-pipelined units in Intel chips, like the division engine, which show latency numbers ~= to their execution time.
  - BeeOnRope 2y ago
    I don't think anyone is talking about "fetch, decode, operate, retire" pipelining (though that is certainly called pipelinig): only pipelining within the execution of a instruction that takes multiple cycles just to execute (i.e., latency from input-ready to output-ready). Pipelining in stages like fetch and decode are mostly hidden in these small benchmarks, but are visible when there are branch misprediction, other types of flushes, I$ misses and so on.
    - ajross 2y ago
      > I don't think anyone is talking about "fetch, decode, operate, retire" pipelining (though that is certainly called pipelinig): only pipelining within the execution of a instruction that takes multiple cycles just to execute (i.e., latency from input-ready to output-ready). I'm curious what you think the distinction is? Those statements are equivalent. The circuit implementing "an instruction" can't work in a single cycle, so you break it up and overlap sequentially issued instructions. Exactly what they do will be different for different hardware, sure, clearly we've moved beyond the classic four stage Patterson pipeline. But that doesn't make it a different kind of pipelining!
      - formerly_proven 2y ago
        Independently scheduled and queued execution phases are qualitatively different from a fixed pipeline.
delusional 2y ago
Is this still the case if I have different ALU operations. Say I have a single ALU on a single x86 core. Would the ALU be able to interleave say ADD and MULs? or would I incur the latency measure for each operation switch? I know that some ALU's have multiple ADD complexes, and I assume that would influence the answer, hence why I specified x86.
- deleted 2y ago
  [deleted]
- barbegal 2y ago
  You need to be far more specific than x86, x86 is just the instruction set, the actual architecture can vary massively with the same instruction set. In general though there is no penalty for interleaved operations.
- bjourne 2y ago
  A modern ALU has multiple pipelined data paths for its operations. So maybe three adders with a one-cycle latency, two multipliers with a three-cycle latency, and one divider with a 16-cycle latency. Sustained throughput depends on the operation. Maybe one per cycle for add and multiply, but only one every eight cycle for divide.
- BeeOnRope 2y ago
  Yes, it applies to different operations. E.g. you could interleave two or three different operations with 3 cycle latency and 1 cycle inv throughput on the same port and get 1 cycle inv throughput in aggregate for all of them. There is no restriction that they must be same operation. In some cases mixing operations with _different_ latencies on the same execution port will leave you with less throughput than you expect due to "writeback conflicts", i.e., two instructions finishing on the same cycle (e.g., a 2 cycle operation starting on cycle 0 and a 1 cycle operation on cycle 1, will both finish on cycle 2 and in some CPUs this will delay the results of one of the operations by 1 cycle due to a conflict).
- Tuna-Fish 2y ago
  You can interleave most operations how you like, without any extra latency, each op starting as soon as all the results are ready, regardless of where they were computed. There are some exceptions where "domain crossing", or using a very different operation costs an extra clock cycle. Notably, in vector registers using FP or integer operations on the result of the different type of op, as modern CPUs don't actually hold FP values in their IEEE754 transfer format inside registers, but instead registers have hidden extra bits and store all values in normal form, allowing fast operations on denormals. The downside of this is that if you alternate between FP and INT operations, the CPU has to insert extra conversion ops between them. Typical cost is 1-3 cycles per domain crossing.
barbegal 2y ago
These days CPUs are so complex and have so many interdependencies that the best way to simulate them is simply to run them! In most real code the high throughput of these sorts of operations means that something else is the limiting factor. And if multiplier throughput is limiting performance then you should be using SIMD or a GPU.
- sroussey 2y ago
  > These days CPUs are so complex and have so many interdependencies that the best way to simulate them is simply to run them! True. You can imagine how difficult it is for the hardware engineer designing and testing these things before production!
- alain94040 2y ago
  Very true. To paraphrase a saying, CPU amateurs argue about micro-benchmarks on HN, the pros simulate real code.
  - pizlonator 2y ago
    Or even just A:B test real code.
  - devit 2y ago
    The amateurs usually run benchmarks (because they can't reason about it as they lack the relevant knowledge) and believe they got a useful result on some aspect when in the fact the benchmark usually depends on other arbitrary random factors (e.g. maybe they think they are measuring FMA throughput, but are in fact measuring whether the compiler autovectorizes or whether it fuses multiply and adds automatically). A pro would generally only run benchmarks if it's the only way to find out (or if it's easy), but isn't going to trust it unless there's a good explanation for the effects, or unless they actually just want to compare two very specific configurations rather than coming up with a general finding.
    - LegionMammal978 2y ago
      Then again, 'reasoning about it' can easily go awry if your knowledge doesn't get updated alongside the CPU architectures. I've seen people confidently say all sorts of stuff about optimization that hasn't been relevant since the early 2000s. Or in the other direction, some people treat modern compilers/CPUs like they can perform magic, so that it makes no difference what you shovel into them (e.g., "this OOP language has a compiler that always knows when to store values on the stack"). Benchmarks can help dispel some of the most egregious myths, even if they are easy to misuse.
codedokode 2y ago
What I am interested to know is who invented pipelining? I tried googling but without much success. Does anybody know?
- paulsutter 2y ago
  Probably the first person to ask, 'how can I speed up this processor, maybe there's a way to do more than one processing step at a time for each instruction'
  - zelos 2y ago
    Presumably by analogy to production lines in factories?
    - sroussey 2y ago
      Actually, it’s just obvious when you design the most basic ALU and the circuits for doing the carry.
      - codedokode 2y ago
        Pipelining requires inserting extra (costly) flip-flops and intuitively one might think that this would decrease the performance. It is not that easy.
    - NotCamelCase 2y ago
      Is it really that much different than e.g. a cook preparing carrots while onions are being cooked? Nobody needed to invent this as far as my knowledge of history goes; so, maybe there really is nothing new under the sun :) Joking aside, of course, the ingenuity lies in finding a fitting solution to problem at hand, as well as knowing how to apply it.
  - adrian_b 2y ago
    Actually there are 2 ways to do more than one processing step at a time: parallel execution and pipelined (a.k.a. overlapped) execution. Both ways had been used for many centuries for the manufacturing of complex things, as ways to organize the work of multiple workers.
saagarjha 2y ago
Unrelated but for benchmarks like these you can just ask the kernel for how many clock cycles you’ve used using proc_pid_rusage rather than hardcoding it.
taneq 2y ago
Is anything important not pipelined?
- monocasa 2y ago
  Operations that are important, but take a single cycle.
- BeeOnRope 2y ago
  Division, gather are muti-cycle instructions which have typically had little or no pipelining on x86.
- syncsynchalt 2y ago
  Memory barriers come to mind.
  - deleted 2y ago
    [deleted]
ryukoposting 2y ago
If the two ALUs could feed results into each other, that would make things really interesting, especially when you consider the way it would affect reordering. Imagine if the OP's benchmark had two of those multiplication chains on independent registers: mul x1, x0, x0 // a mul x2, x1, x1 // b mul x3, x2, x2 // c mul x4, x3, x3 // d mul x6, x5, x5 // e mul x7, x6, x6 // f mul x8, x7, x7 // g mul x9, x8, x8 // h If you had two independent ALUs, my intuition is that you'd want to dispatch the instructions as AEBFCGDH, interleaving the two chains. But, if the two ALUs could feed each other, perhaps you'd actually want to leave it in ABCDEFGH order? Hmm.
- monocasa 2y ago
  They are able to do this via what's called a bypass network.
- wtallis 2y ago
  > If you had two independent ALUs, my intuition is that you'd want to dispatch the instructions as AEBFCGDH, interleaving the two chains. But, if the two ALUs could feed each other, perhaps you'd actually want to leave it in ABCDEFGH order? Hmm. Once the frontend has determined what the dependencies are between instructions, you no longer have a linear sequence of instructions being dispatched to execution units but a DAG, and with multiple instructions starting on the same clock cycle the execution order would be more like (AE)(BF)(CG)(DH) without any ordering between instructions in the same parenthesized group. The reorder buffer in the CPU will be large enough to handle the compiler emitting either ABCDEFGH or AEBFCGDH, but the interleaved ordering is less likely to run into limitations of the instruction decoder (if this chunk of code isn't already in a decoded µop cache).
- ack_complete 2y ago
  Closest I can think of would be the original Pentium 4, which had double-speed integer ALUs where simple operations like addition would produce the low 16 bits in the first half cycle and the high 16 bits in the second half cycle. A dependent op could immediately start using the low result before the high result was done to give effective 0.5c latency and throughput and 4 adds/cycle. Intel dropped this in the 64-bit capable revision of the P4, though.
ElizabethVio52 2y ago
[dead]
filiphorvat 2y ago
Unrelated, do FPUs on modern CPUs use FMAs to both multiply and add or do they use mul/add-only units?
- bonzini 2y ago
  Probably to do multiplies, as the extra add is basically free. Adds are cheaper.
  - thesz 2y ago
    Adds are cheaper only for fixed-point computations. Floating point addition needs to denormalize one of its' arguments, perform an (integer) addition and then normalize the result. Usually FP adds take a cycle or two longer than FP multiplication.
    - dahart 2y ago
      Depends on what you mean by ‘cheaper’. Multiplies are still more gates. The adds are slower due to longer dependency chains, not because they cost more gates.
- gpderetta 2y ago
  I don't think there is a generally optimal design. There are cons and pros to using the same homogeneous FMAs units for adds, multiplies and fmas, even at the cost of making adds slower (simpler design, and having all instructions of the same latency greatly simplifies scheduling). IIRC intel cycled through 4 cycles fma, add and mul, then to 4 cycles add and mul and 5 cycles fmas, then with a dedicated 3 cycles add. The optimal design depends a lot on the rest of the microarchitecture, the loads the core is being optimized for, the target frequency, the memory latency, etc.
rasz 2y ago
Pipelining is the direct reason behind 1996 Quake running 30 fps on Intel Pentium 133 but requiring 233MHz from Cyrix and 166MHz from AMD K6 to reach same result. 20 fps needed 75MHz Intel Pentium, 133MHz Cyrix and 100MHz AMD K5.
- gary_0 2y ago
  Specifically, Carmack exploited the fact that on the Pentium, integer instructions could run in parallel with floating-point division[0]. This goes to show that an optimization that usually gets you ~10% might get you 200% depending on what software you're running. And that no implementation detail is safe from an ambitious software engineer. [0] https://news.ycombinator.com/item?id=38249029 https://news.ycombinator.com/item?id=38249029
  - gpderetta 2y ago
    So that was not actually pipelining, but superscalar execution. Incidentally division wasn't pipelined at all.
    - ack_complete 2y ago
      Pipelining did also play a role. The Quake inner rasterization loop has a decent amount of non-division math in it as well that leverages the Pentium's ability to execute FP add/multiplies at 1/cycle. The K6 and 6x86 FPUs were considerably slower -- 2 and 4 cyclesnon-pipelined (http://www.azillionmonkeys.com/qed/cpuwar.html http://www.azillionmonkeys.com/qed/cpuwar.html). Additionally, the FXCH instructions required to optimally schedule FPU instructions on the Pentium hurt 486/K6/6x86 performance even more since they cost additional cycles. Hard for the 6x86 to keep up when it takes 7 cycles to execute an FADD+FXCH pair vs. 1 for the Pentium.
  - rasz 2y ago
    No, thats not it as explained in my reply to that TerrifiedMouse comment in 2023 :) On x86 Integer instructions _never_ waited for floating point opcode to retire. You can check it yourself by reading FPU status register busy flag - if FPU was blocking you could never catch it in BUSY state and FWAIT would be useless :-) Abrash exploited the fact Pentium was the first time x87 FPU instructions could run pipelined overlapping one another. All other x86 vendors FPUs waited for previous FPU instruction to retire. https://www.agner.org/optimize/microarchitecture.pdf https://www.agner.org/optimize/microarchitecture.pdf page 47 While floating point instructions in general cannot be paired, many can be pipelined, i.e. one instruction can begin before the previous instruction has finished. Example: fadd st1,st0 ; Clock cycle 1-3 fadd st2,st0 ; Clock cycle 2-4 fadd st3,st0 ; Clock cycle 3-5 fadd st4,st0 ; Clock cycle 4-6 Obviously, two instructions cannot overlap if the second instruction needs the result of the first one. Since almost all floating point instructions involve the top of stack register, ST0, there are seemingly not very many possibilities for making an instruction independent of the result of previous instructions. The solution to this problem is register renaming. The FXCH instruction does not in reality swap the contents of two registers; it only swaps their names. Paradoxically often mentioned Texture Divide every 16 pixels overlaps just fine on all CPUs and doesnt explain performance discrepancies. Intel FDIV latency is 19 cycles compared to Cyrix 24, mere 20% yet you need almost double the MHz on Cyrix to match FPS numbers. Answer lies in rest of Quake heavily pipelined FPU code.
dhash 2y ago
My favorite illustrations for the concepts discussed here (in an accessible form, not the processor optimization manuals) has long been [0]. For me, this really makes working with a modern microprocessor a science, as anyone who has written benchmarks knows -- it's difficult to reason about the complex behaviour and performance cliffs without testing. Another excellent example of the weirdness has to be JVM anatomy quarks [1] [0] https://www.lighterra.com/papers/modernmicroprocessors/ https://www.lighterra.com/papers/modernmicroprocessors/ [1] https://shipilev.net/jvm/anatomy-quarks/ https://shipilev.net/jvm/anatomy-quarks/
- gpderetta 2y ago
  The first link is very nice, worth of a submission of its own.
  - aargh_aargh 2y ago
    https://hn.algolia.com/?query=Modern%20Microprocessors%20%E2%80%93%20A%2090-Minute%20Guide&type=story&dateRange=all&sort=byDate&storyText=false&prefix&page=0 https://hn.algolia.com/?query=Modern%20Microprocessors%20%E2...
  - titanomachy 2y ago
    It was very good, I learned a lot. Actually more high-quality info than I can absorb in one sitting, but I bookmarked it to come back to. I'd love to see an updated version. The article talks about how out-of-order execution has a high power overhead and produces relatively small performance gains, but the M-series chips from Apple have deep OOO and low power consumption; I'm curious to learn what they did differently.
    - atq2119 2y ago
      > I'm curious to learn what they did differently. Being 20 years later than the original version of that article. Silicon process improvements since then have been wild.
mshockwave 2y ago
divisions, regardless of integer or floating point, are usually NOT pipelined though
- gpderetta 2y ago
  I haven't seen any cpu with a fully pipelined division, but division units are at least partially pipelined in recent-ish cpus. They usually can start a new division well before the previous one has stopped executing. ALUs in Recent Apple cpus can actually start a new division every other cycle (in addition to having an abnormally low latency), which is very impressive.
  - mshockwave 2y ago
    > ALUs in Recent Apple cpus can actually start a new division every other cycle (in addition to having an abnormally low latency) That's indeed impressive. I'll argue that we're definitely capable of making fully pipelined divisions, it's just that it's usually not worth the PPA.
mshockwave 2y ago
shameless self plug of modern uArchs and how LLVM models it: https://myhsu.xyz/llvm-sched-model-1 https://myhsu.xyz/llvm-sched-model-1
olliej 2y ago
I think my favorite introduction to just how insane the pipelines, predictors, and other insanity in "modern" (more than a decade ago now) was trying to improve `Math.sqrt()` performance in JSC. This was during the first generation of JIT JS engines (e.g. no one was inlining functions yet), and I was replacing the host implementation of Math.sqrt with a pure assembly version - essentially calling a host function was significantly more expensive another JS function - e.g. JIT JS function -> JIT JS function was significantly faster than JIT JS function -> host code (e.g. C/C++). As part of doing that I was going step by step through each instruction making sure it was the minimum overhead as each step, think something like (very approximate - again more than a decade ago): v0: 1. if (input not a number) fallback to C++; else 2. return tagged 0; // Just making sure the numeric check was optimal v1: 1. As above 2. If integer convert to float 3. return tagged 0 v2: 1-2. as above 3. If negative return tagged nan 4. Return tagged 0 v3: 1-3. as above 4. use the sqrt instruction 5. return tagged 0 v4. 1-4. as above 5. move <4> back to an integer register 6. return tagged 0 v5. 1-5. as above 6. tag the result of sqrt 7. return tagged 0 v6. 1-6. as above 7. Actually return/store the result of <6> Alas I cannot recall whether at this point return values were going into the heap allocated VM call stack, or whether the return was via rax, but that's not the bit that was eye opening to me. I had a benchmark that was something like for (var i = 0; i < large number; i++) Math.sqrt(i) Noting that while I was working on this there was no meaningful control flow analysis, inlining, etc so this was an "effective" benchmark for perf work at the time - it would not be so today. The performance remained "really good" (read fake) until the `v6` version that actually store/returned the result of the work. It was incredibly eye opening to see just how much code could be "executed" before the CPU actually ended up doing any work, and significantly impacted my approach to dealing with codegen in future. My perspective at the time was "I know there's a significant marshaling cost to calling host code, and I know the hardware sqrt is _very_ fast", so it seemed that it was possible that a 5-10x perf improvement seemed "plausible" to me at the time (because marshaling was legitimately very expensive) - and I can't recall where in the 5-10x range the perf improvement was - but then once the final store/return was done it dropped in perf to only 2x faster. Which was still a big win, but also seeing just how much work the CPU could just avoid doing while trying to build out the code was a significant learning experience.
bru3s 2y ago
[flagged]

165 points by ingve 2y ago

For x86 cores this is visible in Agner Fog's instruction performance tables: https://agner.org/optimize/#manuals https://agner.org/optimize/#manuals The latency shows after how many cycles the result of an instruction can be consumed by another, while the throughput shows how many such instructions can be pipelined per cycle, i.e. in parallel.

wtallis 2y ago
I believe the throughput shown in those tables is the total throughput for the whole CPU core, so it isn't immediately obvious which instructions have high throughput due to pipelining within an execution unit and which have high throughput due just to the core having several execution units capable of handling that instruction.
- BeeOnRope 2y ago
  That's true, but another part of the tables show how many "ports" the operation can be executed on, which is enough information to concluded an operation is pipelined. For example, for many years Intel chips had a multiplier unit on a single port, with a latency of 3 cycles, but an inverse throughput of 1 cycle, so effectively pipelined across 3 stages. In any case, I think uops.info [1] has replaced Agner for up-to-date and detailed information on instruction execution. --- [1] https://uops.info/table.html https://uops.info/table.html
  - Earw0rm 2y ago
    Shame it doesn't seem to have been updated with Arrow Lake, Zen 5 and so on yet.
    - BeeOnRope 2y ago
      Yes. In the past new HW has been made available to the uops.info authors in order to run their benchmark suite and publish new numbers: I'm not sure if that just hasn't happened for the new stuff, or if they are not interested in updating it.
ajross 2y ago
FWIW, there are two ideas of parallelism being conflated here. One is the parallel execution of the different sequential steps of an instruction (e.g. fetch, decode, operate, retire). That's "pipelining", and it's a different idea than decoding multiple instructions in a cycle and sending them to one of many execution units (which is usually just called "dispatch", though "out of order execution" tends to connote the same idea in practice). The Fog tables try hard show the former, not the latter. You measure dispatch parallelism with benchmarks, not microscopes. Also IIRC there are still some non-pipelined units in Intel chips, like the division engine, which show latency numbers ~= to their execution time.
- BeeOnRope 2y ago
  I don't think anyone is talking about "fetch, decode, operate, retire" pipelining (though that is certainly called pipelinig): only pipelining within the execution of a instruction that takes multiple cycles just to execute (i.e., latency from input-ready to output-ready). Pipelining in stages like fetch and decode are mostly hidden in these small benchmarks, but are visible when there are branch misprediction, other types of flushes, I$ misses and so on.
  - ajross 2y ago
    > I don't think anyone is talking about "fetch, decode, operate, retire" pipelining (though that is certainly called pipelinig): only pipelining within the execution of a instruction that takes multiple cycles just to execute (i.e., latency from input-ready to output-ready). I'm curious what you think the distinction is? Those statements are equivalent. The circuit implementing "an instruction" can't work in a single cycle, so you break it up and overlap sequentially issued instructions. Exactly what they do will be different for different hardware, sure, clearly we've moved beyond the classic four stage Patterson pipeline. But that doesn't make it a different kind of pipelining!
    - formerly_proven 2y ago
      Independently scheduled and queued execution phases are qualitatively different from a fixed pipeline.

delusional 2y ago

Is this still the case if I have different ALU operations. Say I have a single ALU on a single x86 core. Would the ALU be able to interleave say ADD and MULs? or would I incur the latency measure for each operation switch? I know that some ALU's have multiple ADD complexes, and I assume that would influence the answer, hence why I specified x86.

deleted 2y ago
[deleted]
barbegal 2y ago
You need to be far more specific than x86, x86 is just the instruction set, the actual architecture can vary massively with the same instruction set. In general though there is no penalty for interleaved operations.
bjourne 2y ago
A modern ALU has multiple pipelined data paths for its operations. So maybe three adders with a one-cycle latency, two multipliers with a three-cycle latency, and one divider with a 16-cycle latency. Sustained throughput depends on the operation. Maybe one per cycle for add and multiply, but only one every eight cycle for divide.
BeeOnRope 2y ago
Yes, it applies to different operations. E.g. you could interleave two or three different operations with 3 cycle latency and 1 cycle inv throughput on the same port and get 1 cycle inv throughput in aggregate for all of them. There is no restriction that they must be same operation. In some cases mixing operations with _different_ latencies on the same execution port will leave you with less throughput than you expect due to "writeback conflicts", i.e., two instructions finishing on the same cycle (e.g., a 2 cycle operation starting on cycle 0 and a 1 cycle operation on cycle 1, will both finish on cycle 2 and in some CPUs this will delay the results of one of the operations by 1 cycle due to a conflict).
Tuna-Fish 2y ago
You can interleave most operations how you like, without any extra latency, each op starting as soon as all the results are ready, regardless of where they were computed. There are some exceptions where "domain crossing", or using a very different operation costs an extra clock cycle. Notably, in vector registers using FP or integer operations on the result of the different type of op, as modern CPUs don't actually hold FP values in their IEEE754 transfer format inside registers, but instead registers have hidden extra bits and store all values in normal form, allowing fast operations on denormals. The downside of this is that if you alternate between FP and INT operations, the CPU has to insert extra conversion ops between them. Typical cost is 1-3 cycles per domain crossing.

barbegal 2y ago

These days CPUs are so complex and have so many interdependencies that the best way to simulate them is simply to run them! In most real code the high throughput of these sorts of operations means that something else is the limiting factor. And if multiplier throughput is limiting performance then you should be using SIMD or a GPU.

sroussey 2y ago
> These days CPUs are so complex and have so many interdependencies that the best way to simulate them is simply to run them! True. You can imagine how difficult it is for the hardware engineer designing and testing these things before production!
alain94040 2y ago
Very true. To paraphrase a saying, CPU amateurs argue about micro-benchmarks on HN, the pros simulate real code.
- pizlonator 2y ago
  Or even just A:B test real code.
- devit 2y ago
  The amateurs usually run benchmarks (because they can't reason about it as they lack the relevant knowledge) and believe they got a useful result on some aspect when in the fact the benchmark usually depends on other arbitrary random factors (e.g. maybe they think they are measuring FMA throughput, but are in fact measuring whether the compiler autovectorizes or whether it fuses multiply and adds automatically). A pro would generally only run benchmarks if it's the only way to find out (or if it's easy), but isn't going to trust it unless there's a good explanation for the effects, or unless they actually just want to compare two very specific configurations rather than coming up with a general finding.
  - LegionMammal978 2y ago
    Then again, 'reasoning about it' can easily go awry if your knowledge doesn't get updated alongside the CPU architectures. I've seen people confidently say all sorts of stuff about optimization that hasn't been relevant since the early 2000s. Or in the other direction, some people treat modern compilers/CPUs like they can perform magic, so that it makes no difference what you shovel into them (e.g., "this OOP language has a compiler that always knows when to store values on the stack"). Benchmarks can help dispel some of the most egregious myths, even if they are easy to misuse.

codedokode 2y ago

What I am interested to know is who invented pipelining? I tried googling but without much success. Does anybody know?

paulsutter 2y ago
Probably the first person to ask, 'how can I speed up this processor, maybe there's a way to do more than one processing step at a time for each instruction'
- zelos 2y ago
  Presumably by analogy to production lines in factories?
  - sroussey 2y ago
    Actually, it’s just obvious when you design the most basic ALU and the circuits for doing the carry.
    - codedokode 2y ago
      Pipelining requires inserting extra (costly) flip-flops and intuitively one might think that this would decrease the performance. It is not that easy.
  - NotCamelCase 2y ago
    Is it really that much different than e.g. a cook preparing carrots while onions are being cooked? Nobody needed to invent this as far as my knowledge of history goes; so, maybe there really is nothing new under the sun :) Joking aside, of course, the ingenuity lies in finding a fitting solution to problem at hand, as well as knowing how to apply it.
- adrian_b 2y ago
  Actually there are 2 ways to do more than one processing step at a time: parallel execution and pipelined (a.k.a. overlapped) execution. Both ways had been used for many centuries for the manufacturing of complex things, as ways to organize the work of multiple workers.

saagarjha 2y ago

Unrelated but for benchmarks like these you can just ask the kernel for how many clock cycles you’ve used using proc_pid_rusage rather than hardcoding it.

taneq 2y ago

Is anything important not pipelined?

monocasa 2y ago
Operations that are important, but take a single cycle.
BeeOnRope 2y ago
Division, gather are muti-cycle instructions which have typically had little or no pipelining on x86.
syncsynchalt 2y ago
Memory barriers come to mind.
- deleted 2y ago
  [deleted]

ryukoposting 2y ago

If the two ALUs could feed results into each other, that would make things really interesting, especially when you consider the way it would affect reordering. Imagine if the OP's benchmark had two of those multiplication chains on independent registers: mul x1, x0, x0 // a mul x2, x1, x1 // b mul x3, x2, x2 // c mul x4, x3, x3 // d mul x6, x5, x5 // e mul x7, x6, x6 // f mul x8, x7, x7 // g mul x9, x8, x8 // h If you had two independent ALUs, my intuition is that you'd want to dispatch the instructions as AEBFCGDH, interleaving the two chains. But, if the two ALUs could feed each other, perhaps you'd actually want to leave it in ABCDEFGH order? Hmm.

monocasa 2y ago
They are able to do this via what's called a bypass network.
wtallis 2y ago
> If you had two independent ALUs, my intuition is that you'd want to dispatch the instructions as AEBFCGDH, interleaving the two chains. But, if the two ALUs could feed each other, perhaps you'd actually want to leave it in ABCDEFGH order? Hmm. Once the frontend has determined what the dependencies are between instructions, you no longer have a linear sequence of instructions being dispatched to execution units but a DAG, and with multiple instructions starting on the same clock cycle the execution order would be more like (AE)(BF)(CG)(DH) without any ordering between instructions in the same parenthesized group. The reorder buffer in the CPU will be large enough to handle the compiler emitting either ABCDEFGH or AEBFCGDH, but the interleaved ordering is less likely to run into limitations of the instruction decoder (if this chunk of code isn't already in a decoded µop cache).
ack_complete 2y ago
Closest I can think of would be the original Pentium 4, which had double-speed integer ALUs where simple operations like addition would produce the low 16 bits in the first half cycle and the high 16 bits in the second half cycle. A dependent op could immediately start using the low result before the high result was done to give effective 0.5c latency and throughput and 4 adds/cycle. Intel dropped this in the 64-bit capable revision of the P4, though.

ElizabethVio52 2y ago

[dead]

filiphorvat 2y ago

Unrelated, do FPUs on modern CPUs use FMAs to both multiply and add or do they use mul/add-only units?

bonzini 2y ago
Probably to do multiplies, as the extra add is basically free. Adds are cheaper.
- thesz 2y ago
  Adds are cheaper only for fixed-point computations. Floating point addition needs to denormalize one of its' arguments, perform an (integer) addition and then normalize the result. Usually FP adds take a cycle or two longer than FP multiplication.
  - dahart 2y ago
    Depends on what you mean by ‘cheaper’. Multiplies are still more gates. The adds are slower due to longer dependency chains, not because they cost more gates.
gpderetta 2y ago
I don't think there is a generally optimal design. There are cons and pros to using the same homogeneous FMAs units for adds, multiplies and fmas, even at the cost of making adds slower (simpler design, and having all instructions of the same latency greatly simplifies scheduling). IIRC intel cycled through 4 cycles fma, add and mul, then to 4 cycles add and mul and 5 cycles fmas, then with a dedicated 3 cycles add. The optimal design depends a lot on the rest of the microarchitecture, the loads the core is being optimized for, the target frequency, the memory latency, etc.

rasz 2y ago

Pipelining is the direct reason behind 1996 Quake running 30 fps on Intel Pentium 133 but requiring 233MHz from Cyrix and 166MHz from AMD K6 to reach same result. 20 fps needed 75MHz Intel Pentium, 133MHz Cyrix and 100MHz AMD K5.

gary_0 2y ago
Specifically, Carmack exploited the fact that on the Pentium, integer instructions could run in parallel with floating-point division[0]. This goes to show that an optimization that usually gets you ~10% might get you 200% depending on what software you're running. And that no implementation detail is safe from an ambitious software engineer. [0] https://news.ycombinator.com/item?id=38249029 https://news.ycombinator.com/item?id=38249029
- gpderetta 2y ago
  So that was not actually pipelining, but superscalar execution. Incidentally division wasn't pipelined at all.
  - ack_complete 2y ago
    Pipelining did also play a role. The Quake inner rasterization loop has a decent amount of non-division math in it as well that leverages the Pentium's ability to execute FP add/multiplies at 1/cycle. The K6 and 6x86 FPUs were considerably slower -- 2 and 4 cyclesnon-pipelined (http://www.azillionmonkeys.com/qed/cpuwar.html http://www.azillionmonkeys.com/qed/cpuwar.html). Additionally, the FXCH instructions required to optimally schedule FPU instructions on the Pentium hurt 486/K6/6x86 performance even more since they cost additional cycles. Hard for the 6x86 to keep up when it takes 7 cycles to execute an FADD+FXCH pair vs. 1 for the Pentium.
- rasz 2y ago
  No, thats not it as explained in my reply to that TerrifiedMouse comment in 2023 :) On x86 Integer instructions _never_ waited for floating point opcode to retire. You can check it yourself by reading FPU status register busy flag - if FPU was blocking you could never catch it in BUSY state and FWAIT would be useless :-) Abrash exploited the fact Pentium was the first time x87 FPU instructions could run pipelined overlapping one another. All other x86 vendors FPUs waited for previous FPU instruction to retire. https://www.agner.org/optimize/microarchitecture.pdf https://www.agner.org/optimize/microarchitecture.pdf page 47 While floating point instructions in general cannot be paired, many can be pipelined, i.e. one instruction can begin before the previous instruction has finished. Example: fadd st1,st0 ; Clock cycle 1-3 fadd st2,st0 ; Clock cycle 2-4 fadd st3,st0 ; Clock cycle 3-5 fadd st4,st0 ; Clock cycle 4-6 Obviously, two instructions cannot overlap if the second instruction needs the result of the first one. Since almost all floating point instructions involve the top of stack register, ST0, there are seemingly not very many possibilities for making an instruction independent of the result of previous instructions. The solution to this problem is register renaming. The FXCH instruction does not in reality swap the contents of two registers; it only swaps their names. Paradoxically often mentioned Texture Divide every 16 pixels overlaps just fine on all CPUs and doesnt explain performance discrepancies. Intel FDIV latency is 19 cycles compared to Cyrix 24, mere 20% yet you need almost double the MHz on Cyrix to match FPS numbers. Answer lies in rest of Quake heavily pipelined FPU code.

dhash 2y ago

My favorite illustrations for the concepts discussed here (in an accessible form, not the processor optimization manuals) has long been [0]. For me, this really makes working with a modern microprocessor a science, as anyone who has written benchmarks knows -- it's difficult to reason about the complex behaviour and performance cliffs without testing. Another excellent example of the weirdness has to be JVM anatomy quarks [1] [0] https://www.lighterra.com/papers/modernmicroprocessors/ https://www.lighterra.com/papers/modernmicroprocessors/ [1] https://shipilev.net/jvm/anatomy-quarks/ https://shipilev.net/jvm/anatomy-quarks/

gpderetta 2y ago
The first link is very nice, worth of a submission of its own.
- aargh_aargh 2y ago
  https://hn.algolia.com/?query=Modern%20Microprocessors%20%E2%80%93%20A%2090-Minute%20Guide&type=story&dateRange=all&sort=byDate&storyText=false&prefix&page=0 https://hn.algolia.com/?query=Modern%20Microprocessors%20%E2...
- titanomachy 2y ago
  It was very good, I learned a lot. Actually more high-quality info than I can absorb in one sitting, but I bookmarked it to come back to. I'd love to see an updated version. The article talks about how out-of-order execution has a high power overhead and produces relatively small performance gains, but the M-series chips from Apple have deep OOO and low power consumption; I'm curious to learn what they did differently.
  - atq2119 2y ago
    > I'm curious to learn what they did differently. Being 20 years later than the original version of that article. Silicon process improvements since then have been wild.

mshockwave 2y ago

divisions, regardless of integer or floating point, are usually NOT pipelined though

gpderetta 2y ago
I haven't seen any cpu with a fully pipelined division, but division units are at least partially pipelined in recent-ish cpus. They usually can start a new division well before the previous one has stopped executing. ALUs in Recent Apple cpus can actually start a new division every other cycle (in addition to having an abnormally low latency), which is very impressive.
- mshockwave 2y ago
  > ALUs in Recent Apple cpus can actually start a new division every other cycle (in addition to having an abnormally low latency) That's indeed impressive. I'll argue that we're definitely capable of making fully pipelined divisions, it's just that it's usually not worth the PPA.

mshockwave 2y ago

shameless self plug of modern uArchs and how LLVM models it: https://myhsu.xyz/llvm-sched-model-1 https://myhsu.xyz/llvm-sched-model-1

olliej 2y ago

I think my favorite introduction to just how insane the pipelines, predictors, and other insanity in "modern" (more than a decade ago now) was trying to improve `Math.sqrt()` performance in JSC. This was during the first generation of JIT JS engines (e.g. no one was inlining functions yet), and I was replacing the host implementation of Math.sqrt with a pure assembly version - essentially calling a host function was significantly more expensive another JS function - e.g. JIT JS function -> JIT JS function was significantly faster than JIT JS function -> host code (e.g. C/C++). As part of doing that I was going step by step through each instruction making sure it was the minimum overhead as each step, think something like (very approximate - again more than a decade ago): v0: 1. if (input not a number) fallback to C++; else 2. return tagged 0; // Just making sure the numeric check was optimal v1: 1. As above 2. If integer convert to float 3. return tagged 0 v2: 1-2. as above 3. If negative return tagged nan 4. Return tagged 0 v3: 1-3. as above 4. use the sqrt instruction 5. return tagged 0 v4. 1-4. as above 5. move <4> back to an integer register 6. return tagged 0 v5. 1-5. as above 6. tag the result of sqrt 7. return tagged 0 v6. 1-6. as above 7. Actually return/store the result of <6> Alas I cannot recall whether at this point return values were going into the heap allocated VM call stack, or whether the return was via rax, but that's not the bit that was eye opening to me. I had a benchmark that was something like for (var i = 0; i < large number; i++) Math.sqrt(i) Noting that while I was working on this there was no meaningful control flow analysis, inlining, etc so this was an "effective" benchmark for perf work at the time - it would not be so today. The performance remained "really good" (read fake) until the `v6` version that actually store/returned the result of the work. It was incredibly eye opening to see just how much code could be "executed" before the CPU actually ended up doing any work, and significantly impacted my approach to dealing with codegen in future. My perspective at the time was "I know there's a significant marshaling cost to calling host code, and I know the hardware sqrt is _very_ fast", so it seemed that it was possible that a 5-10x perf improvement seemed "plausible" to me at the time (because marshaling was legitimately very expensive) - and I can't recall where in the 5-10x range the perf improvement was - but then once the final store/return was done it dropped in perf to only 2x faster. Which was still a big win, but also seeing just how much work the CPU could just avoid doing while trying to build out the code was a significant learning experience.

bru3s 2y ago

[flagged]