{"id":14518,"date":"2022-10-08T03:14:35","date_gmt":"2022-10-07T21:44:35","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-loop-unrolling-not-giving-expected-speedup-for-floating-point-dot-product\/"},"modified":"2022-10-08T03:14:35","modified_gmt":"2022-10-07T21:44:35","slug":"solved-loop-unrolling-not-giving-expected-speedup-for-floating-point-dot-product","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-loop-unrolling-not-giving-expected-speedup-for-floating-point-dot-product\/","title":{"rendered":"[Solved] loop unrolling not giving expected speedup for floating-point dot product"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\n
\n
<\/div>\n
\n
\n<\/div>\n
\n

Your unroll doesn’t help with the FP latency bottleneck:<\/p>\n

sum + x + y + z<\/code> without -ffast-math<\/code> is the same order of operations as sum += x;<\/code> sum += y;<\/code> … so you haven’t done anything about the single dependency chain running through all the +<\/code> operations. Loop overhead (or front-end throughput) is not<\/em> the bottleneck, it’s the 3 cycle latency of addss<\/code> on Haswell, so this unroll makes basically no difference.<\/p>\n

What would work is sum += u[i]*v[i] + u[i+1]*v[i+1] + ...<\/code> as a way to unroll without multiple accumulators, because then the sum of each group of elements is independent<\/strong>.<\/p>\n

It costs slightly more math operations that way, like starting with a mul and ending with an add, but the middle ones can still contract into FMAs if you compile with -march=haswell<\/code>. See comments on AVX performance slower for bitwise xor op and popcount for an example of GCC turning a naive unroll like sum += u0*v0;<\/code> sum += u1*v1<\/code> into sum += u0*v0 + u1*v1;<\/code>. In that case the problem was slightly different: sum of squared differences like sum += (u0-v0)**2 + (u1-v1)**2;<\/code>, but it boils down to the same latency problem of ultimately doing some multiplies and adds.<\/p>\n

The other way to solve the problem is with multiple accumulators, allowing all the operations to be FMAs. But Haswell has 5-cycle latency FMA, and 3-cycle latency addss<\/code>, so doing the sum += ...<\/code> addition on its own, not as part of an FMA, actually helps with the latency bottleneck on Haswell (unlike on Skylake add\/sub\/mul are all 4 cycle latency). The following all show unrolling with multiple accumulators, instead of with adding groups together like the first towards pairwise summation like you’re doing:<\/p>\n