1

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

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

4

3 回答 3

5

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

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

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

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

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;

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

通常，您应该展开等于操作延迟乘以每个时钟周期可以完成的操作数的数量。例如，对于 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];

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

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-loopsGCC 可以正常工作。它展开八次，这意味着计数器加法和跳转必须每八次迭代而不是每次迭代进行一次。

于 2016-04-13T07:44:41.073 回答
3

展开循环的过程利用了计算机科学中的一个基本概念：时空权衡，其中增加使用的空间通常会导致减少算法的时间。

假设我们有一个简单的循环，

const int n = 1000;

for (int i = 0; i < n; ++i) {
    foo();
}

这被编译成如下所示的程序集：

mov eax, 0

loop:

call foo
inc eax
cmp eax, 1000
jne loop

因此，时空权衡是 5 行汇编代码，执行 ~(4 * 1000) = ~4000 条指令。

所以，让我们试着展开循环。

for (int i = 0; i < n; i += 10) {
    foo();
    foo();
    foo();
    foo();
    foo();
    foo();
    foo();
    foo();
    foo();
    foo();
}

及其组装：

mov eax, 0

loop:

call foo
call foo
call foo
call foo
call foo
call foo
call foo
call foo
call foo
call foo
add eax, 10
cmp eax, 1000
jne loop

时空权衡是 14 行汇编代码，执行 ~(14 * 100) = ~1400 条指令。

我们可以进行完全展开，如下所示：

foo();
foo();
// ...
// 996 foo()'s
// ...
foo();
foo();

它在汇编中编译为 1000 条调用指令。

这给出了 1000 条装配线与 1000 条指令的时空权衡。

可以看到，总的趋势是，要减少 CPU 执行的指令量，就必须增加所需的空间。

完全展开循环效率不高，因为所需的空间变得非常大。部分展开会带来巨大的好处，但收益会大大减少，展开循环的次数越多。

虽然了解循环展开是一个好主意，但请记住，编译器很聪明，会为您完成。

于 2016-04-13T04:28:05.443 回答
1

Rolled (regular):

#define N 44

int main() {
    int A[N], B[N];
    int i;

    // fill A with stuff ...

    for(i = 0; i < N; i++) {
        B[i] = A[i] * (100 % i);
    }

    // do stuff with B ...
}

Unrolled:

#define N 44

int main() {
    int A[N], B[N];
    int i;

    // fill A with stuff ...

    for(i = 0; i < N; i += 4) {
        B[i] = A[i] * (100 % i);
        B[i+1] = A[i+1] * (100 % i+1);
        B[i+2] = A[i+2] * (100 % i+2);
        B[i+3] = A[i+3] * (100 % i+3);
    }

    // do stuff with B ...
}

Unrolling can potentially increase performance at the cost of a larger program size. Performance increases could be due to a reduction in branch penalties, cache misses and execution instructions. Some disadvantages are obvious, like an increase in the amount of code and a decrease in readability, and some are not so obvious.

于 2016-04-13T04:22:25.790 回答