C 中的快速 2D 卷积

我正在尝试用 Python 实现卷积神经网络。最初，我使用 scipy.signal 的 convolve2d 函数来进行卷积，但它有很多开销，而且用 C 实现我自己的算法并从 python 调用它会更快，因为我知道我的输入是什么样的。

我实现了2个功能：

1. 将矩阵与不可分离核进行卷积
2. 将矩阵与可分离的内核进行卷积（现在我假设 python 在将其传递到 C 之前进行排名检查和分割）

这些函数都没有填充，因为我需要降维。

不可分离的二维卷积

// a - 2D matrix (as a 1D array), w - kernel
double* conv2(double* a, double* w, double* result)
{
    register double acc;
    register int i; 
    register int j;
    register int k1, k2;
    register int l1, l2;
    register int t1, t2;

    for(i = 0; i < RESULT_DIM; i++) 
    {
        t1 = i * RESULT_DIM; // loop invariants
        for(j = 0; j < RESULT_DIM; j++) 
        {   
            acc = 0.0;
            for(k1 = FILTER_DIM - 1, k2 = 0; k1 >= 0; k1--, k2++)
            {
                t2 = k1 * FILTER_DIM;  // loop invariants
                for(l1 = FILTER_DIM - 1, l2 = 0; l1 >= 0; l1--, l2++)
                {
                    acc += w[t2 + l1] * a[(i + k2) * IMG_DIM + (j + l2)];
                }
            }
            result[t1 + j] = acc;
        }
    }

    return result;
}

可分离的二维卷积

// a - 2D matrix, w1, w2 - the separated 1D kernels
double* conv2sep(double* a, double* w1, double* w2, double* result)
{
    register double acc;
    register int i; 
    register int j;
    register int k1, k2;
    register int t;
    double* tmp = (double*)malloc(IMG_DIM * RESULT_DIM * sizeof(double));

    for(i = 0; i < RESULT_DIM; i++) // convolve with w1 
    {
        t = i * RESULT_DIM;
        for(j = 0; j < IMG_DIM; j++)
        {
            acc = 0.0;
            for(k1 = FILTER_DIM - 1, k2 = 0; k1 >= 0; k1--, k2++)
            {
                acc += w1[k1] * a[k2 * IMG_DIM + t + j];
            }
            tmp[t + j] = acc;
        }
    }

    for(i = 0; i < RESULT_DIM; i++) // convolve with w2
    {
        t = i * RESULT_DIM;
        for(j = 0; j < RESULT_DIM; j++)
        {
            acc = 0.0;
            for(k1 = FILTER_DIM - 1, k2 = 0; k1 >= 0; k1--, k2++)
            {
                acc += w2[k1] * tmp[t + (j + k2)];
            }

            result[t + j] = acc;
        }
    }

    free(tmp);
    return result;
}

使用 gcc -O3 标志进行编译并在 2.7GHz Intel i7 上进行测试，使用 4000x4000 矩阵和 5x5 内核，我分别得到（平均值为 5）：

271.21900 ms
127.32000 ms

与 scipy.signal 的 convolve2d 相比，这仍然是一个相当大的改进，相同的操作大约需要 2 秒，但我需要更快的速度，因为我将调用这个函数数千次。目前无法将数据类型更改为浮点型，尽管这会带来相当大的加速。

有没有办法进一步优化这些算法？我可以应用任何缓存技巧或例程来加快速度吗？

任何建议，将不胜感激。

如果您仅在 x86 上运行，请考虑使用 SSE 或 AVX SIMD 优化。为了double数据吞吐量的提高将是适度的，但如果你可以切换到float那么使用 SSE 或许可以将性能提升 4 倍左右，而使用 AVX 则可以提升 8 倍左右。 StackOverflow 上已经有很多关于这个主题的问题和答案，您可以从中获得一些关于实现的想法。另外，还有许多可用的库，其中包括高性能 2D 卷积（过滤）例程，并且这些例程通常利用 SIMD 来提高性能，例如Intel 的 IPP（商业）或 OpenCV（免费）。

另一种可能性是利用多个核心 - 将图像分割成块并在其自己的线程中运行每个块。例如。如果您有 4 核 CPU，则将图像分成 4 个块。 （看pthreads http://linux.die.net/man/3/pthread_create).

如果您确实想完全优化此操作，您当然可以结合上述两种想法。

您可以将一些小的优化应用于当前的代码以及任何未来的实现（例如 SIMD）：

• 如果您的内核是对称（或奇对称）的，那么您可以通过添加（减去）对称输入值并执行一次乘法而不是两次乘法来减少运算数量

• 对于可分离的情况，不要分配全帧临时缓冲区，而是考虑使用“条带挖掘”方法 - 分配一个较小的缓冲区，它是全宽的，但行数相对较少，然后在“条带”中处理图像，交替应用水平核和垂直核。这样做的优点是您拥有更加缓存友好的访问模式和更小的内存占用。

关于编码风格的一些评论：

• the register关键字多年来一直是多余的，如果您尝试使用它，现代编译器会发出警告 - 放弃它可以节省一些噪音（和一些打字）

• 铸造结果malloc在 C 中是不受欢迎的 - 它是多余且有潜在危险 https://stackoverflow.com/q/605845/253056.

• 任意输入参数const（即只读）并使用restrict对于任何永远不能使用别名的参数（例如a and result） - 这不仅可以帮助避免编程错误（至少在以下情况下）const），但在某些情况下，它可以帮助编译器生成更好的优化代码（特别是在可能存在别名指针的情况下）。