我认为澄清循环展开何时最有效很重要:使用依赖链。依赖链是一系列操作,其中每个计算都依赖于先前的计算。例如,下面的循环有一个依赖链。
for(i=0; i<n; i++) sum += a[i];
Run Code Online (Sandbox Code Playgroud)
大多数现代处理器每个周期可以执行多个乱序操作。这增加了指令吞吐量。但是,乱序操作不能在依赖链中做到这一点。在上面的循环中,每个计算都受到加法运算延迟的限制。
在上面的循环中,我们可以将它展开成两个这样的依赖链
sum1 = 0, sum2 = 0;
for(i=0; i<n/2; i++) sum1 += a[2*i], sum2 += a[2*i+1];
for(i=(n/2)*2; i<n; i++) sum += a[i]; // clean up for n odd
sum += sum1 + sum2;
Run Code Online (Sandbox Code Playgroud)
现在,乱序处理器可以独立地在任一链上运行,并同时依赖于处理器。
通常,您应该展开一个等于操作延迟乘以每个时钟周期可以完成的操作数的量。例如,对于 x86_64 处理器,它每个时钟周期至少可以执行一次 SSE 添加,并且 SSE 添加的延迟为 3,因此您应该展开 3 次。使用 Haswell 处理器,它可以在每个时钟周期执行两次 FMA 操作,并且每个 FMA 操作的延迟为 5,因此您需要展开 10 次才能获得最大吞吐量。
就编译器而言,GCC 不会展开依赖链(即使使用-funroll-loops
)。您必须使用 GCC 展开自己。使用 Clang 它可以展开四次,这通常非常好(在某些情况下,在 Haswell 和 Broadwell 上,您需要展开 10 次,而在 Skylake 中则需要展开 8 次)。
展开的另一个原因是当循环中的操作数超过每个时钟周期可以推送的指令数时。例如在以下循环中
for(i=0; i<n; i++) b[i] += 3.14159*a[i];
Run Code Online (Sandbox Code Playgroud)
没有依赖链,所以不存在乱序执行的问题。但是让我们考虑一个指令集,它每次迭代都需要以下操作。
2 SIMD load
1 SIMD store
1 SIMD multiply
1 SIMD addition
1 scalar addition for the loop counter
1 conditional jump
Run Code Online (Sandbox Code Playgroud)
我们还假设处理器每个周期可以执行五个这样的指令。在这种情况下,每次迭代有 7 条指令,但每个周期只能执行 5 条指令。然后可以使用循环展开来分摊标量添加到计数器i
和条件跳转的成本。例如,如果您完全展开循环,则不需要这些指令。
为了分摊循环计数器和跳转的成本,-funroll-loops
GCC 可以正常工作。它展开八次,这意味着计数器加法和跳转必须每八次迭代而不是每次迭代进行一次。