Как использовать циклическое развертывание и повторную ассоциацию?

Question

Я пытаюсь использовать циклическое развертывание для оптимизации моего кода.

Это был оригинальный код

int a[N]; //arbitrary array
int vara; //arbitrary variable
int varb; //arbitrary variable
for (int i=0;i<N;i++)
     a[i]=(a[i+1]* vara) + varb;

, поэтому я попытался сделать это

for (int i=0;i<N-1;i+=2)
{
    int a=a[i+1]*vara;
    int b=a[i+2]*vara;
    int c=a+varb;
    int d=b+varb;
    a[i]=c;
    a[i+1]=d;
}

Я думал, что это сработает, потому что я позволяю компилятору выполнять сложение и умножение для нескольких итераций одновременно, что, как я думал, увеличит параллелизм на уровне команд.Тем не менее, выполнение этого вовсе не ускоряет мой код, что я делаю неправильно?

Любые другие предложения по оптимизации этого кода также будут высоко оценены.

Answer 1

Скорее всего, ваш компилятор разворачивается уже на высоких уровнях оптимизации, возможно, вам нужно -funroll-loops или что-то в этом роде.Но даже документы предупреждают, что это не волшебная опция для увеличения скорости, так как она стоит кеш инструкций и пространство программы.

Развертывание цикла - это в основном то, что вы сделали: просто сделайте меньше итераций цикла и сделайтеработа нескольких меньших итераций.То, будет ли он быстрее, сильно зависит от тела цикла и фактического компьютера, на котором выполняется код.

Развертывание также действительно имеет смысл только в том случае, если переходы дороги и есть усиление параллелизма на уровне команд, что дает-зависимость и настроенные предсказатели ветвления в современных процессорах маловероятны.

Тем не менее, вам нужно как минимум запустить какой-нибудь микробенчмаркинг со статистическим анализом.

Если бы мне пришлось рисковать путемВы можете повысить скорость на этом: удалить зависимость от следующего элемента в массиве.Затем он превращается в базовый вектор, кратно накапливающийся, что тривиально для векторизации.