Разматывание петель (C)

Question

Однако я понимаю концепцию развертывания циклов. Может ли кто-нибудь объяснить мне, как развернуть простой цикл?

Было бы здорово, если бы вы показали мне цикл, а затем развернутую версию этого цикла с объяснениями того, что происходит.

Answer 1

Я думаю, что важно уточнить, когда развертывание цикла наиболее эффективно: с цепочками зависимостей. Цепочка зависимостей - это последовательность операций, в которой каждый расчет зависит от предыдущего расчета. Например, следующий цикл имеет цепочку зависимостей.

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, поэтому вы должны развернуть три раза. С процессором 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

Давайте также предположим, что процессор может выполнить пять из этих инструкций за цикл. В этом случае существует семь инструкций на итерацию, но только пять могут быть выполнены за цикл. Развертывание цикла может использоваться для амортизации скалярного сложения со счетчиком. i и условный прыжок. Например, если вы полностью развернули цикл, эти инструкции не понадобятся.

Для амортизации стоимости счетчика цикла и прыжка -funroll-loops отлично работает с GCC. Он разворачивается восемь раз, что означает добавление счетчика, и переход должен выполняться один раз каждые восемь итераций вместо каждой итерации.

Answer 2

Процесс развертывания циклов использует важную концепцию в информатике: компромисс между пространством и временем, когда увеличение используемого пространства часто может привести к сокращению времени работы алгоритма.

Допустим, у нас есть простой цикл,

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 инструкций.

Как видите, общая тенденция заключается в том, что для уменьшения количества инструкций, выполняемых ЦП, мы должны увеличить требуемое пространство.

Неэффективно полностью развернуть цикл, так как требуемое пространство становится чрезвычайно большим. Частичное развертывание дает огромные преимущества с очень уменьшающимся возвратом, чем больше вы разворачиваете цикл.

Хотя это хорошая идея, чтобы понять развертывание цикла, имейте в виду, что компилятор умный и сделает это за вас.

Answer 3

Прокат (обычный):

#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 ...
}

раскатали:

#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 ...
}

Развертывание может потенциально повысить производительность за счет увеличения размера программы. Повышение производительности может быть связано с уменьшением штрафов за переходы, отсутствием кэша и выполнением инструкций. Некоторые недостатки очевидны, такие как увеличение объема кода и снижение читабельности, а некоторые не так очевидны.