Как я могу ускорить этот цикл (в C)?

Я пытаюсь распараллелить функцию свертки в C. Здесь исходная функция, которая свертывает два массива 64-битных поплавков:

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] += in1[i] * in2[j];
        }
    }
}

Чтобы разрешить concurrency (без семафоров), я создал функцию, которая вычисляет результат для определенной позиции в массиве results:

void convolveHelper(const Float64 *in1,
                    UInt32 in1Len,
                    const Float64 *in2,
                    UInt32 in2Len,
                    Float64 *result,
                    UInt32 outPosition)
{
    UInt32 i, j;

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

Проблема заключается в том, что использование convolveHelper замедляет код примерно в 3,5 раза (при запуске в одном потоке).

Любые идеи о том, как я могу ускорить convolveHelper, сохраняя при этом безопасность потоков?

Ответ 1

Конвоиции во временной области становятся умножениями в области Фурье. Я предлагаю вам захватить быструю библиотеку FFT (например, FFTW) и использовать ее. Вы перейдете от O (n ^ 2) к O (n log n).

Алгоритмическая оптимизация почти всегда превзошла микрооптимизации.

Ответ 2

Наиболее очевидной вещью, которая могла бы помочь, было бы предварительно вычислить начальные и конечные индексы цикла и удалить дополнительные тесты на 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 < in1Len и i < outPosition.

В теории вы также можете избавиться от назначения j и превратить i++ в ++i, но компилятор, вероятно, уже делает эти оптимизации для вас.

Ответ 3

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

Ответ 4

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

Забудьте о текущем convolveHelper, который слишком сложный и не поможет.
Разделите внутреннюю часть цикла на функцию потока. То есть просто сделайте
```
for (j = 0; j < in2Len; j++) {
    results[i+j] += in1[i] * in2[j];
}
```

в свою собственную функцию, которая принимает i как параметр вместе со всем остальным.

Пусть тело convolve просто запускает потоки. Для максимальной эффективности используйте семафор, чтобы убедиться, что вы никогда не создаете больше потоков, чем у вас есть ядра.

Ответ 5

Ответ лежит в Simple Math и NOT multi-threading (ОБНОВЛЕНО)

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

рассмотрите ab + ac

U может оптимизировать его как a * (b + c) (один мультипликация меньше)

В урном случае есть in2Len ненужные умножения в внутреннем контуре. Который может быть устранен.

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

( ПРИМЕЧАНИЕ: Следующий код возвращает круговое сверление, которое должно быть развернуто для получения результата 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

Ответ 6

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

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];
}

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

Ответ 7

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

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

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