C中的快速2D卷积

Question

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

我实现了2个功能:

1. 使用不可分离的内核卷积矩阵
2. 用可分离的内核对矩阵进行卷积(现在我假设python在将它传递给C之前进行等级检查和拆分)

由于我需要降低维数,因此这两个函数都没有填充.

不可分离的2D卷积

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

可分离的2D卷积

// 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秒钟,但我需要更多速度,因为我将调用此函数数千次.将数据类型更改为浮动目前不是一种选择,即使它会导致相当大的加速.

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

任何建议,将不胜感激.

Answer 1

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

另一种可能性是利用多个核心 - 将图像分割成块并在其自己的线程中运行每个块。例如，如果您有 4 核 CPU，则将图像分成 4 个块。（参见pthreads）。

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

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

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

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

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

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

• 在 C 中强制转换结果malloc是不受欢迎的——这是多余的并且有潜在的危险。

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