python - C中的快速二维卷积

Question

我正在尝试用 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;
}

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

271.21900 ms
127.32000 ms

与 scipy.signal 的 convolve2d 相比，这仍然是一个相当大的改进，convolve2d 对于相同的操作大约需要 2 秒，但我需要更快的速度，因为我将调用此函数数千次。将数据类型更改为 float 目前不是一个选项，即使它会导致相当大的加速。

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

如有任何建议，我们将不胜感激。

Answer 1

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

另一种可能性是利用多核——将您的图像分成 block 并在其自己的线程中运行每个 block 。例如。如果你有一个 4 核 CPU，那么将你的图像分成 4 个 block 。 (参见 pthreads)。

如果你真的想完全优化这个操作，你当然可以结合以上两种想法。

---

您可以将一些小的优化应用于您当前的代码以及任何 future 的实现(例如 SIMD):

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

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

---

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

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

• 在 C 中转换 malloc 的结果是不受欢迎的 - 它是 redundant and potentially dangerous .

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