Как может я ускорение этот цикл (в C)?

• Вместо двух if в цикле, вы можете вычислить правильные минимальные / максимальные значения для i перед циклом.

• Вы рассчитываете каждую позицию результата отдельно. Вместо этого вы можете разделить массив results на блоки и заставить каждый поток вычислять блок. Расчет для блока будет выглядеть как функция convolve .

Я наконец понял, как правильно предварительно вычислить начальный / конечный индексы (предложение, данное как Тайлером МакГенри , так и Интерджеем ):

if (in1Len > in2Len) {
    if (outPosition < in2Len - 1) {
        start = 0;
        end = outPosition + 1;
    } else if (outPosition >= in1Len) {
        start = 1 + outPosition - in2Len;
        end = in1Len;
    } else {
        start = 1 + outPosition - in2Len;
        end = outPosition + 1;
    }
} else {
    if (outPosition < in1Len - 1) {
        start = 0;
        end = outPosition + 1;
    } else if (outPosition >= in2Len) {
        start = 1 + outPosition - in2Len;
        end = in1Len;
    } else {
        start = 0;
        end = in1Len;
    }
}

for (i = start; i < end; i++) {
    *result = in1[i] * in2[outPosition - i];
}

К сожалению, предварительное вычисление индексов дает нет заметного уменьшения времени выполнения : (

Ответ заключается в простой математике, а НЕ в многопоточности (ОБНОВЛЕНО)

Вот почему ...

рассмотрите a b + a c

Вы можете оптимизировать это как a * (b + c) (на одно умножение меньше)

В вашем случае есть in2Len ненужных умножений во внутреннем цикле . Что можно устранить.

Следовательно, изменение кода следующим образом должно дать нам требуемую свертку:

( ПРИМЕЧАНИЕ: Следующий код возвращает круговую свертку , которую необходимо развернуть, чтобы получить результат linear-convolution .

void convolve(const Float64 *in1,
              UInt32 in1Len,
              const Float64 *in2,
              UInt32 in2Len,
              Float64 *results)
{
    UInt32 i, j;

    for (i = 0; i < in1Len; i++) {

        for (j = 0; j < in2Len; j++) {
            results[i+j] += in2[j];
        }

        results[i] = results[i] * in1[i];

    }
}

Это должно дать U максимальный скачок производительности больше, чем что-либо еще. Попробуйте сами и убедитесь !!

GoodLUCK !!

CVS @ 2600Hertz

Позвольте помощнику convolve работать с большими наборами, вычисляя несколько результатов, используя короткий внешний цикл.

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

Распределите работу поровну между всеми потоками. С такого рода проблемами сложность работы каждого потока должна быть одинаковой.

Самым очевидным, что могло бы помочь, было бы предварительное вычисление начального и конечного индексов цикла и удаление лишних тестов на i и j (и связанные с ними скачки). Это:

for (i = 0; i < in1Len; i++) {
   if (i > outPosition)
     break;
   j = outPosition - i;
   if (j >= in2Len)
     continue;
   *result += in1[i] * in2[j];
}

можно переписать как:

UInt32 start_i = (in2Len < outPosition) ? outPosition - in2Len + 1 : 0;
UInt32 end_i = (in1Len < outPosition) ? in1Len : outPosition + 1;

for (i = start_i; i < end_i; i++) {
   j = outPosition - i;
   *result += in1[i] * in2[j];
}

Таким образом, условие j> = in2Len никогда не будет истинным, и проверка цикла по сути представляет собой комбинацию тестов i и i .