Эффективная раскрутка петли вручную

Question

У меня есть этот код C:

for (k = 0; k < n_n; k++) {
    if (k == i || k == j) continue;
    dd=q2_vect[k]-q1_vect;
    d2=dd*dd;
    if (d2<0) {
        a=1;
        break;
    }       
}  

По причинам оптимизации компилятора (на SPE процессора Cell) мне нужно отменить это вручную, поэтому я попытался:

dd=q2_vect[0]-q1_vect;
d2=dd*dd;
if (d2<0)goto done;

dd=q2_vect[1]-q1_vect;
d2=dd*dd;
if (d2<0)goto done;

dd=q2_vect[2]-q1_vect;
d2=dd*dd;
if (d2<0)goto done;

.....
.....

// end
goto notdone;

done: 
ok=0;

notdone:
.....

но я не знаю, как бороться с

if (k == i || k == j) continue;

и с тем фактом, что lopp зависит от каждого запуска "n_n", и вручную я должен писать код столько раз, сколько получит максимальное значение "n_n".

Как вы думаете, это можно исправить?

Answer 1

Вы уверены, что написанный код верен? Текущий код имеет неопределенное поведение, если dd целочисленный тип со знаком, и условие if никогда не выполняется, если d2 без знака или если dd а также d2 являются типами с плавающей точкой. Похоже, вы делаете неправильный поиск по первому индексу k Кроме как i или же j где квадрат выражения q2_vect[ k]-q1_vect переполняется.

Что касается эффективного пропуска i а также j итерации, я бы вместо этого просто посмотреть, где остановился развернутый "цикл", и перезапустить его в k+1 если k был равен i или же j, Предполагается, что код в вашем цикле не имеет побочных эффектов / промежуточного результата, что верно в том виде, в котором оно было написано, но я ожидаю, что вы, возможно, хотели, чтобы код делал что-то еще (например, суммирование квадратов).

Наконец, я очень скептически отношусь к вашему желанию развернуть цикл вручную, когда у вас, кажется, даже нет рабочего кода для начала. Любой хороший компилятор может развернуть цикл для вас, но часто тот тип развертывания цикла, который вы ищете, делает производительность хуже, а не лучше. Я думаю, вам лучше сначала заставить свой код работать правильно, затем измерять (и смотреть на asm, сгенерированный компилятором), и пытаться улучшить его только после того, как определите, что есть проблема.

Answer 2

Этот код, как написано, довольно непригоден для SPE, так как он очень тяжелый. Кроме того, информация о типах вовлеченных переменных могла бы помочь; тест, как написано, кажется довольно неясным (даже с >0 исправить), но код выглядит так, как если бы это был C++, использующий некоторый векторный класс, который перегружает operator - означать векторное вычитание и operator * из двух векторов для вычисления точечного произведения.

Первое, что нужно сделать с такими простыми циклами в SPE, - это освободить их от разветвлений (по крайней мере, внутреннего цикла; т.е. развернуть пару раз и проверять только ранний выход через каждые N итераций) и использовать инструкции SIMD: SPE имеют только SIMD инструкции, поэтому не использование SIMD-обработки в ваших циклах мгновенно тратит 75% вашего доступного пространства регистров и вычислительной мощности. Точно так же SPE могут загружать только выровненные qwords (16 байтов) одновременно, использование меньших типов данных требует дополнительной работы, чтобы перетасовать содержимое регистров вокруг так, чтобы значение, которое вы пытаетесь загрузить, попало в "предпочтительный слот".

Вы избавляетесь от if (k == i || k == j) переписав первую часть цикла, используя следующую форму без ветвей (это псевдокод. Он незамедлительно применим для целых, но вам нужно будет использовать встроенные методы для получения побитовых операций над числами с плавающей запятой):

dd = q2_vect[k] - q1_vect;
d2 = dd * dd;
d2 &= ~(cmp_equal(k, i) | cmp_equal(k, j));

Вот, cmp_equal соответствует соответствующей внутренней части SPE (семантика: cmp_equal(a,b) == (a == b) ? ~0u : 0). Это силы d2 в ноль, когда k == i или же k == j,

Чтобы избежать if (d2 > 0) переходите во внутренний цикл, сделайте следующее:

a |= cmp_greater(d2, 0);

и только проверить, если a отличен от нуля (до начала) каждые несколько итераций цикла. Если все значения рассчитаны для d2 являются неотрицательными (будет иметь место, если ваш тип - целые числа, числа с плавающей запятой или вещественный векторный класс), вы можете упростить это далее. Просто делать:

a |= d2;

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

Answer 3

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

for(i=0;i<count;i++) {
    printf("%d", i);
}

может быть развернут в

i=0;
if(count%2==1) {
    printf("%d", i);
    i=1;
}
while(i<count) {
    printf("%d", i);
    printf("%d", i+1);
    i+=2;
}

Answer 4

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

Answer 5

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

do
{ 
  k=0
  if (k == i || k == j) 
    ;
  else
  {
    dd=q2_vect[ k]-q1_vect;
    d2=dd*dd;
    if (d2<0)
    {
      a=1;
      break;
    }
  }

  k=1
  if (k == i || k == j) 
    ;
  else
  {
    dd=q2_vect[ k]-q1_vect;
    d2=dd*dd;
    if (d2<0)
    {
      a=1;
      break;
    }
  }

  /* and so on, n_n times */

  k= n_n-1
  if (k == i || k == j) 
    ;
  else
  {
    dd=q2_vect[ k]-q1_vect;
    d2=dd*dd;
    if (d2<0)
    {
      a=1;
      break;
    }
  }

} while (0);

по сути, все после продолжения переходит в else часть заявления if

Редактировать: с n_n не является постоянной времени компиляции, вы все равно можете развернуть цикл, выполнив несколько прогонов цикла в цикле, а затем завершить оператором switch-case. на самом деле, вы можете объединить их так, это называется устройство Даффа.

#define LOOP_BODY              \
do{                            \  
  if (k == i || k == j)        \
    ;                          \
  else                         \
  {                            \
    dd=q2_vect[ k]-q1_vect;    \
    d2=dd*dd;                  \
    if (d2<0)                  \
    {                          \
      a=1;                     \
      break;                   \
    }                          \
  } while (0)          


k = 0;
switch(n_n % 8)
{
  case 0: for (; k < n_n; k++) { LOOP_BODY; k++; 
  case 7:                        LOOP_BODY; k++;
  case 6:                        LOOP_BODY; k++;
  case 5:                        LOOP_BODY; k++;
  case 4:                        LOOP_BODY; k++;
  case 3:                        LOOP_BODY; k++;
  case 2:                        LOOP_BODY; k++;    
  case 1:                        LOOP_BODY; k++;}
}

Answer 6

Для первой проблемы вам не нужно "выполнять" тело цикла при выполнении условия. Для этой конкретной проблемы вы можете просто поместить логическое отрицание этого условия в if условие заявления.

Обычно развертывание происходит с коэффициентом; развернутый код все еще живет в цикле (если не известно, что границы цикла очень малы). Кроме того, вам нужно выполнить "остаток" работы (соответствующий оставшейся части размера задачи, деленной на коэффициент развертывания) вне цикла.

Итак, пример развертывания цикла:

for (i = 0; i < n; ++i) do_something(i);

можно развернуть в 2 раза:

for (i = 0; i < n-1; i += 2) { do_something(i); do_something(i+1); }
for (; i < n; ++i) do_something(i);

где второй цикл делает "остаток" (он также устанавливает i быть таким же, как развернутый цикл, но если i после этого не нужно, вся строка может быть просто if (i < n) etc для этого случая).