如何加速此循环(在C中)？

Question

我正在尝试并行化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];
        }
    }
}

为了允许并发(没有信号量),我创建了一个函数来计算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,同时保持线程安全的任何想法？

Answer 1

时域中的卷积在傅立叶域中成为乘法.我建议你抓住一个快速FFT库(如FFTW)并使用它.你将从O(n ^ 2)到O(n log n).

算法优化几乎总是优于微优化.