6

对于我的应用程序，我必须处理一堆对象（比如说ints），这些对象随后被划分并分类到更小的桶中。为此，我将元素存储在一个连续的数组中

arr = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14...}

并且有关桶（子列表）的信息由各个桶中第一个元素的偏移量和子列表的长度给出。

因此，例如，给定

offsets = {0,3,8,..}
sublist_lengths = {3,5,2,...}

将导致以下分裂：

0 1 2 || 3 4 5 6 7 || 8 9 || ...

我正在寻找的是一种通用且有效的方法来运行算法，如减少，仅使用自定义内核或thrust库在桶上。对桶求和应该给出：

3 || 25 || 17 || ...

我想出了什么：

  • 选项 1：自定义内核需要大量修改、复制到共享内存、正确选择块和网格大小以及自己的算法实现，如扫描、减少等。此外，每个操作都需要自己的自定义核心。一般来说，我很清楚如何做到这一点，但在thrust过去几天使用之后，我的印象是可能有更聪明的方法

  • 选项 2：从偏移量生成一个键数组（{0,0,0,1,1,1,1,1,2,2,3,...}在上面的示例中）并使用thrust::reduce_by_key. 不过，我不喜欢额外的列表生成。

  • 选项 3：thrust::transform_iterator与 一起使用thrust::counting_iterator以即时生成上述给定的密钥列表。不幸的是，我想不出一个不需要增加设备上偏移列表的索引并破坏并行性的实现。

实现这一点的最明智的方法是什么？

4

2 回答 2

4

Within Thrust, I can't think of a better solution than Option 2. The performance will not be terrible, but it's certainly not optimal.

Your data structure bears similarity to the Compressed Sparse Row (CSR) format for storing sparse matrices, so you could use techniques developed for computing sparse matrix-vector multiplies (SpMV) for such matrices if you want better performance. Note that the "offsets" array of the CSR format has length (N+1) for a matrix with N rows (i.e. buckets in your case) where the last offset value is the length of arr. The CSR SpMV code in Cusp is a bit convoluted, but it serves as a good starting point for your kernel. Simply remove any reference to Aj or x from the code and pass offsets and arr into the Ap and Av arguments respectively.

于 2012-02-01T06:43:27.130 回答
1

你没有提到桶有多大。如果存储桶足够大，也许您可​​以将偏移量和 sublist_lengths 复制到主机，迭代它们并为每个存储桶执行单独的推力调用。Fermi 可以同时运行 16 个内核，因此在该架构上，您可能能够处理较小的存储桶并仍然获得良好的利用率。

于 2012-02-03T00:53:54.217 回答