使用Thrust进行直方图计算

Question

如果 i 是一个随机游走（每个索引不唯一），并且有一个填充了零的设备向量 A。

{0, 1, 0, 2, 3, 3,  ....}

是否可能使用 thrust 让 A[i] 自动递增，执行操作后，A 可能如下所示：

//2 means appears count of 0's
//1 means appears count of 1's
//1 means appears count of 2's
//2 means appears count of 3's
{2, 1, 1, 2}

我曾尝试了几种情况，但这些情况只在A作为主机向量时才有效。我猜这是因为thrust进行并行处理，它之前的结果不能影响新的结果，结果可能看起来像：

//只计算一次，无论索引出现多少次 {1, 1, 1, 1}

使用设备向量A和随机游走索引向量，Thrust能实现我的目标吗？

- user1995868

---

thrust::sort是指使用Thrust库中的sort函数进行排序，thrust::reduce_by_key是指使用Thrust库中的reduce_by_key函数进行按键归约。 - kangshiyin

我尝试了排序，但性能不够好，所以现在我使用“主机向量+直方图”方法来实现我的目标。新方法的执行时间（包括设备<-->主机开销）比排序版本更短。我对更好的解决方案很感兴趣，并在这里提问。 - user1995868

http://docs.nvidia.com/cuda/cuda-samples/index.html#cuda-histogram - kangshiyin

你需要使用推力吗？ - eLRuLL

使用Thrust或CUDA内核代码都可以！但我仍然想知道当使用device_vector时，Thrust能够达到多快？ - user1995868

Answer 1

如果您正在寻求Thrust的直方图计算，那么您可能需要注意有一个Thrust文档示例提供了两种不同的算法：

1. 密集直方图，使用sort对数组进行排序，然后使用upper_bound确定累积直方图，最后使用adjacent_difference计算直方图；
2. 稀疏直方图，使用sort对数组进行排序，然后使用reduce_by_key，如@Eric在他的评论中提到的。

这两个线程来自于：

• 直方图或count_by_key；
• 如何从已排序的序列中获取直方图。

我认为以上是使用Thrust实现直方图的唯一两种方法。我在Kepler K20c卡上测试了这两种方法，结果如下：

- N=1024*16; # bins = 16*16; Dense = 2.0ms; Sparse = 2.4ms; - N=1024*128; # bins = 16*128; Dense = 3.4ms; Sparse = 3.1ms;

考虑到计时取决于输入数组的事实，我认为结果看起来并没有显著不同。

需要注意的是，CUDA示例提供了一个直方图计算示例，但它仅针对64或256个bin进行了优化，因此与上述Thrust代码不同。

- Vitality