小编M. *_*G. 的帖子

我有以下问题:给定两个排序的数组A和B,我必须生成一个排序的数组C,其元素为A和B.

我找到了一些解决这个问题的解决方案,使用CUDA:Merge Path,例如http://www.cc.gatech.edu/~bader/papers/GPUMergePath-ICS2012.pdf

但是,它们的问题是由原始数组的大小给出的,至少有10k个元素.我有一个不同的问题.

我要合并的数组要小得多(最多1000个元素),并且复杂度由要完成的合并次数给出(10次幂的顺序为10,10 ^ 5个大小为1000的数组)相互合并).

他们的部分问题是将原始数组拆分为同等大小的并行处理的部分.我必须合并的数组足够小,完全适合GPU共享内存.

Thrust不是我的第一选择,因为我的过程的输出不是排序数组本身,而是带有元素的计算:所以我认为专门的内核应该比首先排序元素索引更快,然后使用它们进行计算.

该算法的串行版本如下所示:

i=0
j=0
k=0
T=4
while i<N and j<M:
    if A[i]<B[j]:
        start_i = max(0,i-T)
        C[k]=sum(A[start_i:i+1])
        i+=1
    else:
        start_j = max(0,j-T)
        C[k]=sum(B[start_j:j+1])
        j+=1
    k+=1

while i<N:
    start_i = max(0,i-T)
    C[k]=sum(A[start_i:i+1])
    i+=1
    k+=1
while j<M:
    start_j = max(0,j-T)
    C[k]=sum(B[start_j:j+1])
    j+=1
    k+=1

如何利用CUDA功能来解决这个问题？