如何使用 Thrust 减少数组中不连续的数字段

Question

我有一个一维数组 "A"，它由许多数组 "a" 组成，如下所示：

我正在实现一个代码来总结不连续的段（总结"A"中每个数组"a"相同颜色的段中的数字如下：

有什么想法可以用推力有效地做到这一点吗？

非常感谢

注：图片仅代表一个数组"a"。大数组 "A" 包含许多数组 "a"

Answer 1

在一般情况下，事先不知道数据的顺序和按段分组，一般建议是使用thrust::sort_by_key将类似的段分组在一起，然后使用thrust::reduce_by_key 总结段。示例给出 here.

但是，如果输入数据段遵循已知的重复模式，例如此处建议的那样，我们可以通过使用 thrust::permutation_iterator 到 "gather" 类似的段来消除排序步骤，因为thrust::reduce_by_key.

的输入

使用问题中的示例数据，困难的部分是创建排列迭代器。为此，并使用问题中给出的特定段类型数 (3)、段长度 (3) 和每个段类型的段数 (3)，我们需要一个映射 "vector"（即迭代器）用于我们的具有以下序列的置换迭代器：

0  1  2 9 10 11 18 19 20 3 4 5 12 13 14 21 22 23 ...

然后该序列将 "map" 或重新排列输入数组，以便将所有相似的段组合在一起。我敢肯定有多种方法可以创建这样的序列，但我选择的方法如下。我们将从标准的计数迭代器序列开始，然后对其应用变换仿函数（使用 make_transform_iterator），以便创建上述序列。我选择使用以下方法来完成，按逐步顺序排列，显示添加在一起的组件：

counting iterator: (_1)                         0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 ...
---------------------------------------------------------------------------------------------------
((_1/seg_len)%seg_types)*(seg_len*seg_types):   0  0  0  9  9  9 18 18 18  0  0  0  9  9  9 18 18 18 ...
 _1%seg_len:                                    0  1  2  0  1  2  0  1  2  0  1  2  0  1  2  0  1  2 ...
_1/(seg_len*seg_types)*seg_len:                 0  0  0  0  0  0  0  0  0  3  3  3  3  3  3  3  3  3 ...
 Sum:                                           0  1  2  9 10 11 18 19 20  3  4  5 12 13 14 21 22 23 ...

这是一个完整的示例：

$ cat t457.cu
#include <thrust/reduce.h>
#include <thrust/iterator/permutation_iterator.h>
#include <thrust/iterator/transform_iterator.h>
#include <thrust/iterator/discard_iterator.h>
#include <thrust/device_vector.h>
#include <thrust/copy.h>
#include <iostream>

typedef int dtype;
const int seg_len = 3;
const int seg_types = 3;

using namespace thrust::placeholders;

int main(){

  dtype data[] = {10,16,14,2,4,4,1,2,1,8,2,10,3,1,6,8,0,2,9,1,0,3,5,2,3,2,1};
  //                0   1  2 9 10 11 18 19 20 3 4 5 12 13 14 21 22 23 ...
  //              ((_1/seg_len)%seg_types)*(seg_len*seg_types) + _1%seg_len + (_1/(seg_len*seg_types)*seg_len

  int ads = sizeof(data)/sizeof(data[0]);
  int num_groups = ads/(seg_len*seg_types); // ads is expected to be whole-number divisible by seg_len*seg_types
  int ds = num_groups*(seg_len*seg_types);  // handle the case when it is not
  thrust::device_vector<dtype> d_data(data, data+ds);
  thrust::device_vector<dtype> d_result(seg_types);
  thrust::reduce_by_key(thrust::make_transform_iterator(thrust::counting_iterator<int>(0), _1/(ds/seg_types)), thrust::make_transform_iterator(thrust::counting_iterator<int>(ds), _1/(ds/seg_types)), thrust::make_permutation_iterator(d_data.begin(), thrust::make_transform_iterator(thrust::counting_iterator<int>(0), ((_1/seg_len)%seg_types)*(seg_len*seg_types) + _1%seg_len + (_1/(seg_len*seg_types)*seg_len))), thrust::make_discard_iterator(), d_result.begin());
  thrust::copy(d_result.begin(), d_result.end(), std::ostream_iterator<dtype>(std::cout, ","));
  std::cout << std::endl;
}
$ nvcc -o t457 t457.cu
$ ./t457
70,30,20,
$

如何使用 Thrust 减少数组中不连续的数字段

How to reduce nonconsecutive segments of numbers in array with Thrust

cuda

nvidia

gpgpu

thrust