CUDA流压缩算法

Question

我正试图用CUDA构建一个并行算法，该算法接受一个整数数组，并删除所有0，不管是否保持顺序。

示例：

全局内存：{0，0，0，0，14，0，0，0，17，0，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))时间，但具有较高的O常数)。

最后，快速排序或合并等排序算法也可以解决这个问题，并且实际上是在O(ln(n))相对时间内运行的。我认为可能会有比这更快的算法，因为我们不需要浪费时间来排序(交换)零元素对和非零非零元素对(不需要保持顺序)。

所以我不太确定哪种方法会是最快的，我仍然认为有更好的方法来处理这个问题。有什么建议吗？

Answer 1

流压缩是一个众所周知的问题，为此编写了大量代码( which、Chagg引用了在CUDA上实现流压缩的两个库)。

如果您有一个相对较新的具有CUDA功能的设备，它支持__ballot (计算能力>= 3.0)的内在功能，那么值得尝试一个小的CUDA过程，它比推力快得多，可以执行流压缩。

这里找到了代码和最小的文档。https://github.com/knotman90/cuStreamComp

它以单一内核的方式使用投票函数来执行压缩。

编辑：

我写了一篇文章，解释了这种方法的内部工作原理。如果你感兴趣的话，你可以找到它这里。

Answer 2

有了这个答案，我只想提供更多的细节，大卫斯帕塔罗的方法。

正如您所提到的，流压缩包括根据谓词删除集合中不想要的元素。例如，考虑一个整数数组和谓词p(x)=x>5，数组A={6,3,2,11,4,5,3,7,5,77,94,0}被压缩到B={6,11,7,77,94}。

流压缩方法的一般思想是将不同的计算线程分配给要压缩的数组的不同元素。每个这样的线程必须决定将其对应的元素写入输出数组，这取决于它是否满足相关的谓词。因此，流压缩的主要问题是让每个线程知道必须在输出数组中写入对应元素的位置。

1,2中的方法是替代上面提到的推力的copy_if，由三个步骤组成：

1. 步骤1.让P是启动线程的数量，使用N>P表示要压缩的向量的大小。输入向量被划分为大小等于块大小的子向量S。__syncthreads_count(pred)块内蕴被利用，它计算满足谓词pred的块中的线程数。作为第一步的结果，数组d_BlockCounts的每个元素(其大小为N/P )都包含相应块中满足谓词pred的元素数。
2. 步骤2.对数组d_BlockCounts执行独占扫描操作。作为第二步的结果，每个线程都知道前面块中有多少个元素写入了一个元素。因此，它知道写入相应元素的位置，但对于与自己块相关的偏移量。
3. 步骤3.每个线程使用翘曲内禀函数计算上述偏移量，并最终写入输出数组。应该注意的是，步骤3的执行与翘曲调度有关。因此，输出数组中的元素顺序不一定反映输入数组中的元素顺序。

在上述三个步骤中，第二个步骤由CUDA推力的exclusive_scan原语执行，在计算上比其他两个步骤的要求要小得多。

对于一个2097152元素数组，上述方法已经在0.38ms中在NVIDIA GTX 960卡上执行，这与CUDA Thrust的copy_if的1.0ms不同。上述方法看起来更快有两个原因: 1)它是专门针对支持翘曲内在元素的卡而量身定制的；2)该方法不保证输出顺序。

应该注意的是，我们也根据inkc.sourceforge.net上可用的代码测试了该方法。虽然后一段代码被安排在一个单独的内核调用中(它不使用任何CUDA推力原语)，但与三个内核版本相比，它没有更好的性能。

完整的代码是可用的这里，与原始的Davide例程相比略有优化。

[1] M.Biller, O. Olsson, U. Assarsson, “Efficient stream compaction on wide SIMD many-core architectures,” Proc. of the Conf. on High Performance Graphics, New Orleans, LA, Aug. 01 - 03, 2009, pp. 159-166.
[2] D.M. Hughes, I.S. Lim, M.W. Jones, A. Knoll, B. Spencer, “InK-Compact: in-kernel stream compaction and its application to multi-kernel data visualization on General-Purpose GPUs,” Computer Graphics Forum, vol. 32, n. 6, pp. 178-188, 2013.