如何并行地从数组中删除零值

Question

如何使用CUDA并行高效地从数组中删除零值。预先了解有关零值数量的信息应该简化此任务。

重要的是，复制到结果数组时，数字保持源数组中的顺序。

示例：

例如，数组包含以下值： [0, 0, 19, 7, 0, 3, 5, 0, 0, 1] 还有额外的信息，即5个值为零。 然后希望得到另一个数组，其中仅包含： [19, 7, 3, 5, 1]

- diver_182

---

你肯定想删除零吧？如果你删去非零元素，你最终会得到一个只有零的数组！ - Digital Lightcraft

是的，我已经纠正了。我正在寻找一种有效的方法来从源数组中删除零值。 - diver_182

我想通过CUDA线程替换for循环，有效地并行化删除过程。 - diver_182

这听起来像是一次标准的流压缩操作。 - talonmies

当寻找算法方法时，这绝对是正确的。感谢您的回答。 - diver_182

Answer 1

为了从数组中消除一些元素，您可以使用Thrust Library's reordering operations。给定一个谓词is_not_zero，它对于零值返回false，对于其他值返回true，您可以像这样编写操作。

thrust::copy_if(in_array, in_array + size, out_array, is_not_zero);

输出数组将只包括非零值，因为谓词指示如此。

您还可以使用带有反向谓词的“remove_if”函数，该函数对于零返回true，对于其他情况返回false。

thrust::remove_if(in_array, in_array + size, is_zero);

我建议您查看Thrust库的压缩示例或一般的压缩概念。

https://github.com/thrust/thrust/blob/master/examples/stream_compaction.cu

- phoad

---

那个项目可能不允许使用推力（thrust），但是如果可以的话，我会采纳你的建议。谢谢你的帮助。 - diver_182

有类似的库和只有内核实现的压实函数。你可能不需要为此功能使用Thrust，但我建议你使用它。只需查看CUDA SDK的示例即可。 - phoad

Answer 2

如果您不想使用Thrust，而更喜欢使用CUDA，那么最好的做法可能是运行Sum Scan，这里详细描述了它：https://developer.nvidia.com/gpugems/gpugems2/part-iv-general-purpose-computation-gpus-primer/chapter-36-stream-reduction。请注意保留HTML标签。

- mosh442

Answer 3

对于奇偶归并排序的变体，或者实际上任何排序算法，如果排序规则定义为a < b === (a != 0 && b == 0)，会有什么影响呢？

- wilx

---

这是一种单位排序算法，因此可以比普通的归并排序更高效地执行。 - Jared Hoberock

@JaredHoberock：嗯，我还没有看到你提出一个更好的工作方法。 - wilx

使用排序的方法还有一个问题，那就是它会破坏输入数组，而@diver_182希望保留原始输入。正如@phoad上面指出的那样，使用remove_copy_if可以更好地解决这个问题。 - Jared Hoberock

@JaredHoberock：这不是问题，他可以先复制然后排序。 - wilx