使用包含每个重复次数的列表生成重复的升序整数序列，带有推力

Question

我想生成一个重复递增整数序列，给定一个包含每个整数所需的重复次数的列表：

thrust::device_vector<int> reps {3, 2, 5, 1};
//This vector should yield a resulting list:
// {0,0,0, 1,1, 2,2,2,2,2, 3}

理想情况下，我想使用推力 API。

我考虑过这种方法：

前缀总和代表列表以生成累积代表列表。
使用累积次数列表中的最后一个元素分配生成的整数向量。
使用内核，运行代表列表的每个元素的线程，并从 i = 0 : reps[tid] 开始循环，将 tid 存储在 cumulative_reps[tid]+i。

这可行，但最终可能会以串行方式完成大部分工作，并破坏了使用 CUDA 的意义。

我想知道是否有推力迭代器和算法的组合来简洁地生成整数列表？或者，即使没有推力，也可以采用比我概述的方法更好的方法。

Answer 1

你完全可以用推力做到这一点，使用与你类似的方法。

对输入进行前缀和以确定步骤 2 的结果大小，并为步骤 3 分散索引
创建一个输出向量来保存结果
将 ones 分散到输出向量中的适当位置，由步骤 1 中的索引给出
对输出向量进行前缀求和。

请注意，如果允许输入代表向量包含值 0，则必须修改此方法。

这是一个有效的例子：

$ cat t404.cu
#include <thrust/scan.h>
#include <thrust/device_vector.h>
#include <thrust/copy.h>
#include <thrust/iterator/constant_iterator.h>
#include <thrust/iterator/permutation_iterator.h>
#include <iostream>

int main(){

  int host_reps[] = {3, 2, 5, 1};
  int ds = sizeof(host_reps)/sizeof(int);
  thrust::device_vector<int> reps(host_reps, host_reps+ds);
  thrust::inclusive_scan(reps.begin(), reps.end(), reps.begin());
  thrust::device_vector<int> result(reps[reps.size()-1]);
  thrust::copy_n(thrust::constant_iterator<int>(1), reps.size()-1, thrust::make_permutation_iterator(result.begin(), reps.begin()));
  thrust::inclusive_scan(result.begin(), result.end(), result.begin());
  thrust::copy_n(result.begin(), result.size(), std::ostream_iterator<int>(std::cout, ","));
  std::cout << std::endl;
}
$ nvcc -o t404 t404.cu
$ ./t404
0,0,0,1,1,2,2,2,2,2,3,
$

使用包含每个重复次数的列表生成重复的升序整数序列，带有推力

Generate sequence of repeating, ascending integers, using a list containing the number of repetitions for each, with thrust

c++

parallel-processing

cuda

thrust