小编dan*_*n_x的帖子

我有两个数组,a和b,我想计算"min convolution"来产生结果c.简单的伪代码如下所示:

for i = 0 to size(a)+size(b)
    c[i] = inf
    for j = 0 to size(a)
        if (i - j >= 0) and (i - j < size(b))
            c[i] = min(c[i], a[j] + b[i-j])

(编辑:更改循环从0开始而不是1)

如果min是一个和,我们可以使用快速傅立叶变换(FFT),但在最小的情况下,没有这样的模拟.相反,我想通过使用GPU(CUDA)尽可能快地制作这个简单的算法.我很乐意找到执行此操作的现有代码(或实现没有FFT的总和情况的代码,以便我可以根据我的目的调整它),但到目前为止我的搜索没有发现任何好的结果.我的用例将涉及大小在1,000到100,000之间的a和b.

问题:

• 有效执行此操作的代码是否已经存在？

• 如果我要在结构上自己实现这一点,那么CUDA内核应如何看待以最大限度地提高效率？我尝试过一个简单的解决方案,其中每个c [i]由一个单独的线程计算,但这似乎不是最好的方法.关于如何设置线程块结构和内存访问模式的任何提示？