是否可以使用CUDA来有效地计算排序数组内元素的频率？

Question

我对Cuda很新,我从书中读了几章,在线阅读了很多教程.我已经在矢量加法和乘法上实现了自己的实现.

我想进一步移动,所以假设我们想要实现一个函数,它将整数的排序数组作为输入.

我们的目标是找到数组中每个整数的频率.

顺序我们可以扫描一次数组以产生输出.时间的复杂性将是O(n).

由于这些群体不同,我想必须有可能利用CUDA.

假设这是数组

   1
   1
   1
   1
   2
   2
   3
   3
   5
   5
   6
   7

为了实现完全并行性,每个线程必须确切地知道它必须扫描的数组的哪个部分才能找到总和.只有当我们使用另一个数组时才能实现int dataPosPerThread[]这一点,对于每个线程id,dataPosPerThread[threadId]它将具有初始数组上的起始位置作为值.因此,这意味着每个线程都知道从哪里开始以及在哪里完成.

然而,通过这种方式,我们将无法获得任何收益,因为我们需要O(n)时间来找到这些位置.最终的总成本将O(n) + cost_to_transfer_the_data_to_the_gpu + O(c) + cost_to_transfer_the_results_to_the_gpu 在那里O(c)是恒定的时间,将采取的线程,找到最终的输出,假设,当然我们有最初的数组中许多不同的整数.

我想避免额外的O(n)费用.

到目前为止我所想的是,如果有一个大小的数组arraySize,我们指定将要使用的线程总数,让我们说totalAmountOfThreads这意味着每个线程都必须扫描totalAmountOfThreads/arraySize值.

第一个线程(id 0)将从位置0开始扫描到位置totalAmountOfThreads/arraySize.

第二个线程将从此开始totalAmountOfThreads/arraySize + 1,依此类推.

问题是虽然某些线程可能正在使用不同的整数组,或者有一个组具有更多值由其他线程处理.例如,在上面的例子中,如果我们假设我们将有6个线程,每个线程将采用数组的2个整数,所以我们将有这样的东西:

   1     <-------- thread 0
   1
   1     <-------- thread 1
   1
   2     <-------- thread 2
   2
   3     <-------- thread 3
   3
   5     <-------- thread 4
   5
   6     <-------- thread 5
   7

正如您所看到的,线程0只有1值,但是1线程2正在处理其他值.为了实现并行性,这些线程必须处理不相关的数据.假设我们将使用此逻辑,每个线程将计算以下结果:

   thread 0 => {value=1, total=2}
   thread 1 => {value=1, total=2}
   thread 2 => {value=2, total=2}
   thread 3 => {value=3, total=2}
   thread 4 => {value=5, total=2}
   thread 5 => {{value=6, total=1}, {value=7, total=1}}

通过这个结果可以进一步实现什么？有人可以建议使用额外的hash_map,这样unordered_map可以有效地更新由单个线程计算的每个值的总变量.然而

1. Unordered_map cuda编译器不支持

2. 这意味着线程将无法利用共享内存,因为来自不同块的两个线程可能使用相同的值,因此哈希映射必须位于全局内存中.

3. 即使上面两个不是问题,我们在更新哈希映射时仍然会在线程之间存在竞争条件.

什么是解决这个问题的好方法？

先感谢您

Answer 1

正如@tera已经指出的那样,你所描述的是直方图.

您可能对推力直方图示例代码感兴趣.如果我们以dense_histogram()例程为例,您将注意到第一步是对数据进行排序.

所以,是的,您的数据已排序的事实将为您节省一步.

简而言之,我们是:

1. 排序数据
2. 标记数据中不同元素的边界
3. 计算边界之间的距离.

如示例代码所示,推力可以在单个函数中执行上述每个步骤.由于您的数据已排序,您可以有效地跳过第一步.