小编Dan*_*hie的帖子

我正在尝试用CUDA构造一个并行算法,它采用一个整数数组,并删除所有0的有或没有保持顺序.

例:

全局内存:{0,0,0,0,14,0,0,17,0,0,0,0,13}

主机内存结果:{17,13,14,0,0,...}

最简单的方法是使用主机删除0中的O(n)时间.但考虑到我有各种各样的1000元素,在发送之前将GPU上的所有内容保留并首先压缩它可能会更快.

优选的方法是创建设备上堆栈,使得每个线程可以(以任何顺序)弹出和推送到堆栈上或从堆栈中推出.但是,我不认为CUDA有这个实现.

等效(但速度要慢得多)的方法是继续尝试写入,直到所有线程都写完为止:

kernalRemoveSpacing(int * array, int * outArray, int arraySize) {
    if (array[threadId.x] == 0)
        return;

    for (int i = 0; i < arraySize; i++) {

         array = arr[threadId.x];

         __threadfence();

         // If we were the lucky thread we won! 
         // kill the thread and continue re-reincarnated in a different thread
         if (array[i] == arr[threadId.x])
             return;
    }
}

这种方法的好处在于我们会O(f(x))及时执行,其中f(x)是数组中非零值的平均数(f(x) ~= ln(n)对于我的实现,因此是O(ln(n)) …