2

我对 Cuda 很陌生，我已经阅读了书籍中的几章并在线阅读了很多教程。我已经对向量加法和乘法进行了自己的实现。

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

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

我们可以依次扫描数组一次以产生输出。时间复杂度为O(n)。

由于组不同，我想一定可以利用 CUDA。

假设这是数组

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

为了实现完全并行，每个线程必须准确地知道它必须扫描数组的哪一部分才能找到总和。这只有在我们使用另一个名为的数组时才能实现，该数组int dataPosPerThread[]对于每个线程 iddataPosPerThread[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)费用。

到目前为止我的想法是，拥有一个 size 数组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_mapcuda 编译器不支持

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

  3. 即使上述两个没有问题，在更新哈希映射时，我们仍然会在线程之间出现竞争条件。

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

先感谢您

4

1 回答 1

5

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

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

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

简而言之，我们是：

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

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

于 2013-04-10T03:03:09.507 回答