在 GPU 上计算积分图像真的比 CPU 快吗？

Question

我是 GPU 计算的新手，所以这可能是一个非常幼稚的问题。
我查了几次，似乎在 GPU 上计算积分图像是个不错的主意。
然而，当我真正深入研究它时，我想知道它可能不比 CPU 快，尤其是对于大图像。所以我只想知道您对此的想法，以及 GPU 是否真的更快的一些解释。

因此，假设我们有一个 MxN 图像，CPU 积分图像的计算将需要大约 3xMxN 相加，即 O(MxN)。
在GPU上，按照"OpenGL Super Bible" 6th edition提供的代码，需要进行一些KxMxNxlog2(N) + KxMxNxlog2(M)的运算，其中K是大量的移位运算，乘法运算，另外...
GPU 可以并行工作，比如说，一次 32 个像素取决于设备，但它仍然是 O(MxNxlog2(M)).
我认为即使在 640x480 的常见分辨率下，CPU 仍然更快。

我错了吗？
[编辑] 这是直接来自书本的着色器代码，想法是使用 2 遍：计算行的积分，然后计算来自第 1 遍的结果的列的积分。此着色器代码用于 1 遍。

#version 430 core
layout (local_size_x = 1024) in;
shared float shared_data[gl_WorkGroupSize.x * 2];
layout (binding = 0, r32f) readonly uniform image2D input_image;
layout (binding = 1, r32f) writeonly uniform image2D output_image;
void main(void)
{
    uint id = gl_LocalInvocationID.x;
    uint rd_id;
    uint wr_id;
    uint mask;
    ivec2 P = ivec2(id * 2, gl_WorkGroupID.x);
    const uint steps = uint(log2(gl_WorkGroupSize.x)) + 1;
    uint step = 0;
    shared_data[id * 2] = imageLoad(input_image, P).r;
    shared_data[id * 2 + 1] = imageLoad(input_image,
    P + ivec2(1, 0)).r;
    barrier();
    memoryBarrierShared();
    for (step = 0; step < steps; step++)
    {
        mask = (1 << step) - 1;
        rd_id = ((id >> step) << (step + 1)) + mask;
        wr_id = rd_id + 1 + (id & mask);
        shared_data[wr_id] += shared_data[rd_id];
        barrier();
        memoryBarrierShared();
    }
    imageStore(output_image, P.yx, vec4(shared_data[id * 2]));
    imageStore(output_image, P.yx + ivec2(0, 1),
    vec4(shared_data[id * 2 + 1]));
}

Answer 1

integral image 是什么意思？

我的假设是将 K 个具有相同分辨率 MxN 的图像加在一起。在这种情况下，O(K.M.N) 在 CPU 和 GPU 上，但常数时间在 [=75 上可能更好=]GPU 因为 gfx 内存访问比 CPU 快得多。 GPU 内核通常也多于 CPU 内核，因此有利于 GPU。

如果 K 太大而无法一次放入 GPU 纹理单元 U，那么您需要使用多个通道，所以 O(K.M.N.log(K)/log(U)) K>U... 其中 CPU 在某些情况下可能更快。但是正如之前的评论所建议的那样，您只能猜测而无需测试。您还需要考虑到像无绑定纹理和纹理数组这样的东西允许在单次通过中执行此操作（但我不确定是否有任何性能成本）。

[Edit1]清除你真正想做的事情后

首先，为简单起见，我们假设我们得到方形输入图像 NxN 像素。所以我们可以把任务分成H线和V线分别（类似于2D FFT）来简化这个过程。最重要的是，我们可以将每行细分为 M 像素组。所以：

N = M.K

其中 N 是分辨率，M 是区域分辨率，K 是区域数。

第一。通过

为每个组渲染行，所以我们得到 K 行大小 M。使用片段着色器计算每个区域的整体图像，仅输出到某些纹理。这是 T(0.5*K*M^2*N) 这整个事情可以在覆盖屏幕的单个 QUAD 呈现的片段中完成...
第二。通过

将区域积分转换为完整图像积分。因此再次渲染 K 行并在片段中添加每个前一组的所有最后像素。这是 T(0.5*K^3*N) 这整个事情也可以在覆盖屏幕的单个 QUAD 呈现的片段中完成...
在另一个轴方向的结果上做#1,#2

这整个事情转换为

T(2*N*(0.5*K*M^2+0.5*K^3))
T(N*(K*M^2+K^3))
O(N*(K*M^2+K^3))

现在您可以调整 M 以在您的设置中发挥最大性能...如果我将整个内容重写为 M,N 那么：

T(N*((N/M)*M^2+(N/M)^3))
T(N*(N*M+(N/M)^3))

所以你应该尽量减少热量，所以我会尝试使用周围的值

N*M = (N/M)^3
N*M = N^3/M^3
M^4 = N^2
M^2 = N
M = sqrt(N) = N^0.5

所以整个事情转换为：

T(N*(N*M+(N/M)^3))
T(N*(N*N^0.5+(N/N^0.5)^3))
T(N^2.5+N^1.5)
O(N^2.5)

这比 naive 快 O(N^4) 但是你是对的 CPU 需要做的操作较少 O(N^2) 而不是需要数据副本或多次通过，因此您应该为您的任务找出特定 HW 的阈值分辨率，并根据测量结果进行选择。 PS 希望我没有在计算的某个地方犯下愚蠢的错误。此外，如果您在 CPU 上分别执行 H 和 V 线，那么 CPU 方面的复杂度将为 O(N^3) 并使用这种方法甚至 O(N^2.5) 而无需每轴 2 遍。

看看这个类似的 QA：

我认为这是一个很好的起点。

在 GPU 上计算积分图像真的比 CPU 快吗？

Is computing integral image on GPU really faster than on CPU?

c++

opengl

performance

gpgpu

image-processing