c - 展开循环 (C)

Question

我理解展开循环的概念，但是有人可以向我解释如何展开一个简单的循环吗？

如果您能向我展示一个循环，然后是该循环的展开版本并解释正在发生的事情，那就太好了。

Answer 1

我认为澄清循环展开何时最有效很重要:使用依赖链。依赖链是一系列操作，其中每个计算都依赖于先前的计算。例如，下面的循环有一个依赖链。

for(i=0; i<n; i++) sum += a[i];

大多数现代处理器可以在每个周期执行多个乱序操作。这增加了指令吞吐量。但是，乱序操作不能在依赖链中执行此操作。在上面的循环中，每个计算都受到加法运算延迟的限制。

在上面的循环中，我们可以将它展开成两个这样的依赖链

sum1 = 0, sum2 = 0;
for(i=0; i<n/2; i+=2) 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;

现在，乱序处理器可以独立地在任一链上运行并同时依赖于处理器。

一般来说，您应该展开一个等于操作延迟乘以每个时钟周期可以完成的操作数的量。例如，对于 x86_64 处理器，它可以在每个时钟周期执行至少一次 SSE 添加，而 SSE 添加的延迟为 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];

没有依赖链所以不存在乱序执行的问题。但是让我们考虑一个指令集，它每次迭代都需要以下操作。

2 SIMD load
1 SIMD store
1 SIMD multiply
1 SIMD addition
1 scalar addition for the loop counter
1 conditional jump

我们还假设处理器每个周期可以执行其中的 5 条指令。在这种情况下，每次迭代有 7 条指令，但每个周期只能执行 5 条指令。然后可以使用循环展开来分摊标量加法到计数器 i 和条件跳转的成本。例如，如果您完全展开循环，则不需要这些指令。

为了分摊循环计数器和跳转的成本，-funroll-loops 与 GCC 配合良好。它展开八次，这意味着计数器加法和跳转必须每八次迭代而不是每次迭代都进行一次。