Efficient от руки разворачивания цикла

Question

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

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), мне нужно unloop это вручную, поэтому я попытался:

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; 

и с тем, что Лопп зависит от каждого прогона на «ñ_ñ», и вручную I должен написать код столько раз, сколько будет получено максимальное значение «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

Для первой проблемы вам не нужно «выполнять» тело цикла при выполнении условия. Для этой конкретной проблемы вы можете просто поместить логическое отрицание этого условия в состояние условия 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 для этого случая).

Answer 3

при условии ñ_ñ является константой во время компиляции, то цикл может быть тривиальным раскатывают так:

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 части, если заявление

Edit: поскольку n_n не является постоянной времени компиляции, вы все равно можете развернуть цикл, выполнив несколько циклов цикла в цикле, а затем закончите с помощью оператора switch-case. на самом деле, вы можете комбинировать их, как это так, это называется Duff's device.

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

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

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

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

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, являются неотрицательными (будет иметь место, если ваш тип - это ints, float или real-value vector class), вы можете упростить это дальше. Вобще:

a |= d2; 

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

Answer 6

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