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

Question

我是 Cuda 的新手，我已经阅读了一些书籍章节并在网上阅读了很多教程。我自己实现了 vector 加法和乘法。

我想更进一步，假设我们要实现一个函数，该函数将一个排序的整数数组作为输入。

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

我们可以依次扫描数组一次以生成输出。时间复杂度为 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 值，但是线程 2 正在处理其他 1 值。为了实现并行性，这些线程必须处理不相关的数据。假设我们将使用此逻辑，每个线程将计算以下结果:

   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，它可以有效地为单个线程计算的每个值更新 total 变量。然而

1. Cuda编译器不支持Unordered_map

2. 这意味着线程将无法利用共享内存，因为来自不同 block 的两个线程可能使用相同的值，因此 HashMap 必须位于全局内存中。

3. 即使以上两个不是问题，我们在更新 HashMap 时仍然会在线程之间出现竞争条件。

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

提前致谢

Answer 1

正如@tera 已经指出的，您所描述的是直方图。

您可能对 thrust histogram sample code 感兴趣.如果我们以 dense_histogram() 例程为例，您会注意到第一步是对数据进行排序。

所以，是的，您的数据已排序这一事实将为您节省一步。

简而言之，我们是:

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

如示例代码所示，thrust 可以在单个函数中完成上述每个步骤。由于您的数据已排序，因此您可以有效地跳过第一步。