9 ms·

Playing with the CPU pipeline

129 points by jck 13y ago

kevinchen 13y ago
Site went down; cached here. http://webcache.googleusercontent.com/search?q=cache:http://lolengine.net/blog/2011/9/17/playing-with-the-cpu-pipeline&safe=off&strip=1 http://webcache.googleusercontent.com/search?q=cache:http://...
zhemao 13y ago
I'm really skeptical whether the author's "optimizations" are actually doing what the author thinks they do. Read-after-write hazards do not always result in a stall. Modern CPU pipelines have backward propagation that can resolve RAW hazards without stalling the pipeline. More likely it's the fact that x86 processors are superscalar and have multiple ALUs and FPUs. Therefore, they can dispatch multiple floating point instructions at once, as long as there is no data dependence.
- djcapelis 13y ago
  Yes, the author ironically doesn't actually understand what's happening in the pipeline for the processor they're writing about. It is a superscalar processor using reservation stations and tomasulo's algorithm, a RAW hazard doesn't stall the pipeline. But instructions which would be affected by RAW hazards will slow down execution if those instructions are on the critical path. So paying close attention to instruction-level dependencies will produce better results in both since you can increase the ILP possible in the instruction sequence. This helps a lot especially on code which might run on in-order pipelines (a lot of mobile and embedded chips still use in-order pipelines) too.
  - pslam 13y ago
    That's just nit-picking the nomenclature. The author is simplifying things greatly but he's essentially correct - the naive version with less operations ends up slower because there is a long chain of dependencies. With out-of-order execution this isn't really a stall, because non-dependent instructions can still execute/retire with renamed registers alongside it, but it still effectively delays progress of the dependent chain the same way an in-order pipeline would operate. You might say: its progress is stalled.
    - alain94040 13y ago
      No. A read-after-write hazard has not stalled a cpu in the last 10 years. So the article will mislead all the beginner architects out there. A clear explanation of dependencies would be much more appropriate.
      - brigade 13y ago
        Intel released Atom not 6 years ago, and is still selling Bonnell-derived CPUs to this day... Cortex-A7 and A53 are in-order as well, and are/will be quite common among low-end Chinese smartphones and tablets.
      - weland 13y ago
        There are CPUs that have been stalled by RAWs and appeared in the last 10 years, and they are here to stay. That being said, I think the downvotes are unfair on your post. The author of the post is writing about CPUs that are indeed unlikely to be ever stalled by RAWs.
      - Tuna-Fish 13y ago
        Sadly, this is only true on proper desktop cpus. For an example of a CPU that does horribly on RAW hazards, look no further than the Xenon CPU in the XBox360.
  - knappador 13y ago
    If you need a result to perform the next operation, you have something greater than a RAW hazard. RAW is not necessarily guaranteed to stall whereas a dependency in the result, regardless of the register it's supposed to land in, can't be optimized away without creating opportunities for register renaming and instruction re-ordering to work. It's probably going a little far to say that the author doesn't understand the pipeline. I thought they were over-simplifying the pipeline stages, but the potential for register renaming an instruction reordering don't fundamentally change on AMD vs Intel's x86 CPU's while they do change depending on how you write your C. The results speak for themselves.
    - djcapelis 13y ago
      > but the potential for register renaming an instruction reordering don't fundamentally change on AMD vs Intel's x86 CPU's People are writing code to run on a lot more than x86_64 these days. The author's way of optimizing is actually more correct for an in-order pipeline than an out-of-order one and that is probably the correct approach for multi-architecture code. But the author's approach is not particularly well informed by knowledge of what's actually happening in the pipeline of a modern x86 processor. Nor does, in this case, it particularly matter. Which is why the author's assertion that knowing about the pipeline will help with code optimization is somewhat ironic, since they are modeling their optimization using a completely different pipeline than the processor actually implements. And more interestingly, that's probably the correct way to do it for code that you expect to run on more than one processor generation, or certainly for code that runs on more than one processor architecture.
      - pslam 13y ago
        He points out this is a simplification several times: "For the sake of simplicity, imagine the CPU’s pipeline depth is 3. At a given time, it can fetch, execute and finish one instruction" and later: "I don’t know whether this scheduling is optimal for the (incorrect) assumption of a 3-stage pipeline, but it does look pretty good. Also, loading a0, a1 etc. from memory hasn't been covered for the sake of simplicity." This wouldn't be anywhere near as readable an article if it covered the gory details of multiple decode, dispatch and register renaming. The same analysis still applies reasonably well to an out-of-order pipeline.
- brigade 13y ago
  Even without superscalar execution it'd still help, since no sane architecture has floating-point arithmetic with an effective latency of 1 cycle. Current Intel cores have a latency of 3 cycles for FP add, and 4 cycles for FP multiply. OoOE is another matter though...
knappador 13y ago
Related work demonstrating that ultra-tight mapping loops benefit from multiple inputs per loop iteration: https://github.com/knappador/pipe-packing-demo https://github.com/knappador/pipe-packing-demo
- nkurz 13y ago
  Nice article, I submitted it here: https://news.ycombinator.com/item?id=7176576 https://news.ycombinator.com/item?id=7176576 I also added a comment on this thread that might interest you: https://news.ycombinator.com/item?id=7176553 https://news.ycombinator.com/item?id=7176553
userbinator 13y ago
The CPU he was using is spec'd for a base frequency of 2.7GHz but for microbenchmarks like these, will more likely be at the full turbo frequency of 3.4GHz, That's a 0.294ns instruction cycle, and the fastest result of his optimisation is 15.617ns/call, which is almost exactly 53 cycles/call. That's right in the middle of the timings for the FSINCOS instruction, which on this CPU model (http://www.agner.org/optimize/instruction_tables.pdf http://www.agner.org/optimize/instruction_tables.pdf ) runs in 20-110 cycles -- calculating both sin and cos, to 80 bits of precision. From my experience these FPU instructions will take more cycles for edge cases since they'll do more iterations to guarantee a specific precision, but for the majority of the input range will be closer to the lower end. So I don't think the author really optimised anything here.
- knappador 13y ago
  The author optimized a Taylor series expansion that is way more generic than just a sin/cos function, and they explained why, at the atomic level of data dependency in the pipeline, their optimization worked.
  - userbinator 13y ago
    He did, and then benchmarked it against sin(), so it looked like that was the goal rather than a general polynomial evaluation function, and I'm saying there are faster (and shorter) ways to do that quickly.
epx 13y ago
Old ball game, the fad is to calculate sin(x) using 10,000 machines!
solarexplorer 13y ago
It would be interesting to see what Intel's compiler would do to his mini benchmarks.
Lockal 13y ago
He forgot about 3 things: 1) FMA. The most important optimization that GCC can do automatically on Haswell with ffast-math. With FMA and AVX one can calculate 4 (!) doubles simultaneously only for 10 instructions! 2) Register spill. His final version uses 5 xmm registers, while sin3 uses only 3. Sine function is just a primitive, used in more complex calculations. If the final result can't fit in 16 XMMs, each load/store will bite him. More spill -- more blood. 3) Unordered memory access. His final version accesses polynomial coeffs in random order. In some cases compiler may reorder static vars, but not in his benchmark. In synthetic tests all 8 coefficients stay in L1 cache, but in real HPC applications such situation is extremely rare.
- pascal_cuoq 13y ago
  FMA? Have you seen the date of the post? He would have been writing for PowerPC and IA-64 users, all six of them, if he had based his post on FMA.
  - Lockal 13y ago
    If somebody writes a + x(b + x(c + ...)) one should expect this code to be future-proof and work with any compiler. But if code is mixed with inline assembly, the result will be doubtful, at least. No need to be a prophet. First CPU with AVX appeared 3 years ago. Haswell was announced 6 months ago. There are no AVX-512 solutions for home users yet, but one can write AVX512-opimized code without any special knowledge.
anon4 13y ago
This basically shows that if you don't need to shave off that last nanosecond, sin1 is the fastest variant for a modern optimising compiler.
nkurz 13y ago
Some people have asked about how these optimizations fare with different compilers. Do the "optimizations" hurt as one changes compilers? Do they help? Do any of them manage to vectorize? Here's some data: http://lolengine.net/attachment/blog/2011/9/17/playing-with-the-cpu-pipeline/poly.cpp http://lolengine.net/attachment/blog/2011/9/17/playing-with-... Intel(R) Xeon(R) CPU E5-1620 0 @ 3.60GHz stepping 07 uname -a: Linux 3.5.0-41-generic #64-Ubuntu SMP clang++ -v: clang version 3.2 icpc -v: icpc version 14.0.1 g++ -v: gcc version 4.7.2: Compiled with "-std=c++11" plus the options mentioned in the names. At a glance, all versions produced the same results to reasonable precision (no gross errors). "-ffast-math" only worked with g++, and did not offer substantial improvement, so I've omitted it from the tests. g++_O3 icpc_O3 clang++_O3 sin: 18.193 ns 7.0174 ns 14.6862 ns sin1: 22.5272 ns 8.0225 ns 9.6777 ns sin2: 14.9128 ns 4.7247 ns 7.1016 ns sin3: 18.943 ns 5.1121 ns 6.169 ns sin4: 13.9225 ns 4.8979 ns 5.6666 ns sin5: 14.2042 ns 5.0435 ns 6.3257 ns sin6: 12.2543 ns 4.2955 ns 5.2681 ns sin7: 11.6969 ns 5.0538 ns 5.5793 ns So yes, these optimizations can still have a positive effect, but generally less than that of using a better compiler. In this case, that means if you care about performance use Intel, or if not possible, use CLang. But what about vectorization? Perhaps the compiler can do a better job if you let it make full use of modern SIMD: g++_O3_mavx icpc_O3_mavx clang++_O3_mavx sin: 18.1148 ns 3.7879 ns 14.1987 ns sin1: 22.3675 ns 6.4376 ns 9.2589 ns sin2: 14.5665 ns 3.2823 ns 6.2089 ns sin3: 18.3841 ns 3.6652 ns 5.2409 ns sin4: 13.0917 ns 3.0374 ns 4.9839 ns sin5: 13.1144 ns 3.598 ns 5.177 ns sin6: 11.7605 ns 2.8766 ns 4.2239 ns sin7: 11.4222 ns 3.3261 ns 4.612 ns Yes, it looks like Intel gains quite a bit from vectorizing the result with 256-bit AVX (4-wide for doubles). If you care about autovectorization, use Intel. This performance here generally matched my expectations. I have no affiliation with Intel other than having a free academic license, but find that in general their compiler offers better performance than GCC or CLang. In this case, Intel's best (sin6 with AVX) is 4x faster than GCC's best. I'd usually expect something more like a 20%-40% improvement, but vectorization is one of Intel's strong suits. For those who wish to explore the reasons for the difference in performance, here are the results of 'objdump -C -d' for the functions in question: g++_O3: http://pastebin.com/VstqvcHJ http://pastebin.com/VstqvcHJ icpc_O3: http://pastebin.com/3LjtXAhS http://pastebin.com/3LjtXAhS clang++_O3: http://pastebin.com/aSyCyULh http://pastebin.com/aSyCyULh g++_O3_mavx: http://pastebin.com/81vYueEp http://pastebin.com/81vYueEp icpc_O3_mavx: http://pastebin.com/XRdCuusV http://pastebin.com/XRdCuusV clang++_O3_mavx: http://pastebin.com/KJqUpUBE http://pastebin.com/KJqUpUBE Personally, I'd be very interested to see what an experienced x64 SIMD programmer could do to improve these further. My usual estimate is a further 2x, but I don't know how well that applies to this case. I'd also welcome analysis of the code produced by the compilers.

129 points by jck 13y ago

Site went down; cached here. http://webcache.googleusercontent.com/search?q=cache:http://lolengine.net/blog/2011/9/17/playing-with-the-cpu-pipeline&safe=off&strip=1 http://webcache.googleusercontent.com/search?q=cache:http://...

zhemao 13y ago

I'm really skeptical whether the author's "optimizations" are actually doing what the author thinks they do. Read-after-write hazards do not always result in a stall. Modern CPU pipelines have backward propagation that can resolve RAW hazards without stalling the pipeline. More likely it's the fact that x86 processors are superscalar and have multiple ALUs and FPUs. Therefore, they can dispatch multiple floating point instructions at once, as long as there is no data dependence.

djcapelis 13y ago
Yes, the author ironically doesn't actually understand what's happening in the pipeline for the processor they're writing about. It is a superscalar processor using reservation stations and tomasulo's algorithm, a RAW hazard doesn't stall the pipeline. But instructions which would be affected by RAW hazards will slow down execution if those instructions are on the critical path. So paying close attention to instruction-level dependencies will produce better results in both since you can increase the ILP possible in the instruction sequence. This helps a lot especially on code which might run on in-order pipelines (a lot of mobile and embedded chips still use in-order pipelines) too.
- pslam 13y ago
  That's just nit-picking the nomenclature. The author is simplifying things greatly but he's essentially correct - the naive version with less operations ends up slower because there is a long chain of dependencies. With out-of-order execution this isn't really a stall, because non-dependent instructions can still execute/retire with renamed registers alongside it, but it still effectively delays progress of the dependent chain the same way an in-order pipeline would operate. You might say: its progress is stalled.
  - alain94040 13y ago
    No. A read-after-write hazard has not stalled a cpu in the last 10 years. So the article will mislead all the beginner architects out there. A clear explanation of dependencies would be much more appropriate.
    - brigade 13y ago
      Intel released Atom not 6 years ago, and is still selling Bonnell-derived CPUs to this day... Cortex-A7 and A53 are in-order as well, and are/will be quite common among low-end Chinese smartphones and tablets.
    - weland 13y ago
      There are CPUs that have been stalled by RAWs and appeared in the last 10 years, and they are here to stay. That being said, I think the downvotes are unfair on your post. The author of the post is writing about CPUs that are indeed unlikely to be ever stalled by RAWs.
    - Tuna-Fish 13y ago
      Sadly, this is only true on proper desktop cpus. For an example of a CPU that does horribly on RAW hazards, look no further than the Xenon CPU in the XBox360.
- knappador 13y ago
  If you need a result to perform the next operation, you have something greater than a RAW hazard. RAW is not necessarily guaranteed to stall whereas a dependency in the result, regardless of the register it's supposed to land in, can't be optimized away without creating opportunities for register renaming and instruction re-ordering to work. It's probably going a little far to say that the author doesn't understand the pipeline. I thought they were over-simplifying the pipeline stages, but the potential for register renaming an instruction reordering don't fundamentally change on AMD vs Intel's x86 CPU's while they do change depending on how you write your C. The results speak for themselves.
  - djcapelis 13y ago
    > but the potential for register renaming an instruction reordering don't fundamentally change on AMD vs Intel's x86 CPU's People are writing code to run on a lot more than x86_64 these days. The author's way of optimizing is actually more correct for an in-order pipeline than an out-of-order one and that is probably the correct approach for multi-architecture code. But the author's approach is not particularly well informed by knowledge of what's actually happening in the pipeline of a modern x86 processor. Nor does, in this case, it particularly matter. Which is why the author's assertion that knowing about the pipeline will help with code optimization is somewhat ironic, since they are modeling their optimization using a completely different pipeline than the processor actually implements. And more interestingly, that's probably the correct way to do it for code that you expect to run on more than one processor generation, or certainly for code that runs on more than one processor architecture.
    - pslam 13y ago
      He points out this is a simplification several times: "For the sake of simplicity, imagine the CPU’s pipeline depth is 3. At a given time, it can fetch, execute and finish one instruction" and later: "I don’t know whether this scheduling is optimal for the (incorrect) assumption of a 3-stage pipeline, but it does look pretty good. Also, loading a0, a1 etc. from memory hasn't been covered for the sake of simplicity." This wouldn't be anywhere near as readable an article if it covered the gory details of multiple decode, dispatch and register renaming. The same analysis still applies reasonably well to an out-of-order pipeline.
brigade 13y ago
Even without superscalar execution it'd still help, since no sane architecture has floating-point arithmetic with an effective latency of 1 cycle. Current Intel cores have a latency of 3 cycles for FP add, and 4 cycles for FP multiply. OoOE is another matter though...

knappador 13y ago

Related work demonstrating that ultra-tight mapping loops benefit from multiple inputs per loop iteration: https://github.com/knappador/pipe-packing-demo https://github.com/knappador/pipe-packing-demo

nkurz 13y ago
Nice article, I submitted it here: https://news.ycombinator.com/item?id=7176576 https://news.ycombinator.com/item?id=7176576 I also added a comment on this thread that might interest you: https://news.ycombinator.com/item?id=7176553 https://news.ycombinator.com/item?id=7176553

userbinator 13y ago

The CPU he was using is spec'd for a base frequency of 2.7GHz but for microbenchmarks like these, will more likely be at the full turbo frequency of 3.4GHz, That's a 0.294ns instruction cycle, and the fastest result of his optimisation is 15.617ns/call, which is almost exactly 53 cycles/call. That's right in the middle of the timings for the FSINCOS instruction, which on this CPU model (http://www.agner.org/optimize/instruction_tables.pdf http://www.agner.org/optimize/instruction_tables.pdf ) runs in 20-110 cycles -- calculating both sin and cos, to 80 bits of precision. From my experience these FPU instructions will take more cycles for edge cases since they'll do more iterations to guarantee a specific precision, but for the majority of the input range will be closer to the lower end. So I don't think the author really optimised anything here.

knappador 13y ago
The author optimized a Taylor series expansion that is way more generic than just a sin/cos function, and they explained why, at the atomic level of data dependency in the pipeline, their optimization worked.
- userbinator 13y ago
  He did, and then benchmarked it against sin(), so it looked like that was the goal rather than a general polynomial evaluation function, and I'm saying there are faster (and shorter) ways to do that quickly.

epx 13y ago

Old ball game, the fad is to calculate sin(x) using 10,000 machines!

solarexplorer 13y ago

It would be interesting to see what Intel's compiler would do to his mini benchmarks.

Lockal 13y ago

He forgot about 3 things: 1) FMA. The most important optimization that GCC can do automatically on Haswell with ffast-math. With FMA and AVX one can calculate 4 (!) doubles simultaneously only for 10 instructions! 2) Register spill. His final version uses 5 xmm registers, while sin3 uses only 3. Sine function is just a primitive, used in more complex calculations. If the final result can't fit in 16 XMMs, each load/store will bite him. More spill -- more blood. 3) Unordered memory access. His final version accesses polynomial coeffs in random order. In some cases compiler may reorder static vars, but not in his benchmark. In synthetic tests all 8 coefficients stay in L1 cache, but in real HPC applications such situation is extremely rare.

pascal_cuoq 13y ago
FMA? Have you seen the date of the post? He would have been writing for PowerPC and IA-64 users, all six of them, if he had based his post on FMA.
- Lockal 13y ago
  If somebody writes a + x(b + x(c + ...)) one should expect this code to be future-proof and work with any compiler. But if code is mixed with inline assembly, the result will be doubtful, at least. No need to be a prophet. First CPU with AVX appeared 3 years ago. Haswell was announced 6 months ago. There are no AVX-512 solutions for home users yet, but one can write AVX512-opimized code without any special knowledge.

anon4 13y ago

This basically shows that if you don't need to shave off that last nanosecond, sin1 is the fastest variant for a modern optimising compiler.

nkurz 13y ago

Some people have asked about how these optimizations fare with different compilers. Do the "optimizations" hurt as one changes compilers? Do they help? Do any of them manage to vectorize? Here's some data: http://lolengine.net/attachment/blog/2011/9/17/playing-with-the-cpu-pipeline/poly.cpp http://lolengine.net/attachment/blog/2011/9/17/playing-with-... Intel(R) Xeon(R) CPU E5-1620 0 @ 3.60GHz stepping 07 uname -a: Linux 3.5.0-41-generic #64-Ubuntu SMP clang++ -v: clang version 3.2 icpc -v: icpc version 14.0.1 g++ -v: gcc version 4.7.2: Compiled with "-std=c++11" plus the options mentioned in the names. At a glance, all versions produced the same results to reasonable precision (no gross errors). "-ffast-math" only worked with g++, and did not offer substantial improvement, so I've omitted it from the tests. g++_O3 icpc_O3 clang++_O3 sin: 18.193 ns 7.0174 ns 14.6862 ns sin1: 22.5272 ns 8.0225 ns 9.6777 ns sin2: 14.9128 ns 4.7247 ns 7.1016 ns sin3: 18.943 ns 5.1121 ns 6.169 ns sin4: 13.9225 ns 4.8979 ns 5.6666 ns sin5: 14.2042 ns 5.0435 ns 6.3257 ns sin6: 12.2543 ns 4.2955 ns 5.2681 ns sin7: 11.6969 ns 5.0538 ns 5.5793 ns So yes, these optimizations can still have a positive effect, but generally less than that of using a better compiler. In this case, that means if you care about performance use Intel, or if not possible, use CLang. But what about vectorization? Perhaps the compiler can do a better job if you let it make full use of modern SIMD: g++_O3_mavx icpc_O3_mavx clang++_O3_mavx sin: 18.1148 ns 3.7879 ns 14.1987 ns sin1: 22.3675 ns 6.4376 ns 9.2589 ns sin2: 14.5665 ns 3.2823 ns 6.2089 ns sin3: 18.3841 ns 3.6652 ns 5.2409 ns sin4: 13.0917 ns 3.0374 ns 4.9839 ns sin5: 13.1144 ns 3.598 ns 5.177 ns sin6: 11.7605 ns 2.8766 ns 4.2239 ns sin7: 11.4222 ns 3.3261 ns 4.612 ns Yes, it looks like Intel gains quite a bit from vectorizing the result with 256-bit AVX (4-wide for doubles). If you care about autovectorization, use Intel. This performance here generally matched my expectations. I have no affiliation with Intel other than having a free academic license, but find that in general their compiler offers better performance than GCC or CLang. In this case, Intel's best (sin6 with AVX) is 4x faster than GCC's best. I'd usually expect something more like a 20%-40% improvement, but vectorization is one of Intel's strong suits. For those who wish to explore the reasons for the difference in performance, here are the results of 'objdump -C -d' for the functions in question: g++_O3: http://pastebin.com/VstqvcHJ http://pastebin.com/VstqvcHJ icpc_O3: http://pastebin.com/3LjtXAhS http://pastebin.com/3LjtXAhS clang++_O3: http://pastebin.com/aSyCyULh http://pastebin.com/aSyCyULh g++_O3_mavx: http://pastebin.com/81vYueEp http://pastebin.com/81vYueEp icpc_O3_mavx: http://pastebin.com/XRdCuusV http://pastebin.com/XRdCuusV clang++_O3_mavx: http://pastebin.com/KJqUpUBE http://pastebin.com/KJqUpUBE Personally, I'd be very interested to see what an experienced x64 SIMD programmer could do to improve these further. My usual estimate is a further 2x, but I don't know how well that applies to this case. I'd also welcome analysis of the code produced by the compilers.