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

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), переписывая первую часть цикла, используя следующую форму без ветвей (это псевдокод. Он незамедлительно применим для целых чисел, но вам нужно использовать встроенные методы, чтобы получить побитовую)ops on float):

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

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

Answer 4

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

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 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);

по существу, все после оператора continue входит в часть 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 для этого случая).