How to reduce nonconsecutive segments of numbers in array with Thrust

Question

I have 1D array "A" which is composed from many arrays "a" like this :

I'm implementing a code to sum up non consecutive segments ( sum up the numbers in the segments of the same color of each array "a" in "A" as follow:

Any ideas to do that efficiently with thrust?

Thank you very much

Note: The pictures represents only one array "a". The big array "A" contains many arrays "a"

sort-by-key to bring the like segments together. Then reduce-by-key to create the segment sums. — Robert Crovella, Apr 27 '19 at 22:50
There is another solution to do it without using sorting operation since it is expensive and also the segments have fixed size.? @RobertCrovella — Driss DS Idrissi, Apr 28 '19 at 12:44
are the segments always of size 3? (in other words, if the size of the segment is fixed, is that fixed size known a-priori?) Are there only 3 different types of segments (pink, yellow, and green)? Do the segments always appear in the order pink-yellow-green-pink-yellow-green... ? — Robert Crovella, Apr 28 '19 at 13:44
The size of the segments is known a-priori( it is fixed), also the type of segments( the numbers of segments in ''a'' is fixed ) also known a-priori. the numbers of arrays "a" in the big array "A" is fixed a-priori. The big array "A" contains thousands of arrays of the type "a". @RobertCrovella — Driss DS Idrissi, Apr 28 '19 at 14:45
Do the segments always follow the same order pink-yellow-green? — Robert Crovella, Apr 28 '19 at 18:55

Robert Crovella · Accepted Answer · 2019-05-02T20:49:24.153

In the general case, where the ordering of the data and grouping by segments is not known in advance, the general suggestion is to use thrust::sort_by_key to group like segments together, and then use thrust::reduce_by_key to sum the segments. Examples are given here.

However, if the input data segments follow a known repeating pattern, such as is suggested here, we can eliminate the sorting step by using a thrust::permutation_iterator to "gather" the like segments together, as the input to thrust::reduce_by_key.

Using the example data in the question, the hard part of this is to create the permutation iterator. For that, and using the specific number of segment types (3), segment lengths (3) and number of segments per segment type (3) given in the question, we need a map "vector" (i.e. iterator) for our permutation iterator that has the following sequence:

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

This sequence would then "map" or rearrange the input array, so that all like segments are grouped together. I'm sure there are various ways to create such a sequence, but the approach I chose is as follows. We will start with the standard counting iterator sequence, and then apply a transform functor to it (using make_transform_iterator), so that we create the above sequence. I chose to do it using the following method, arranged in a stepwise sequence showing the components that are added together:

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 ...

Here is a fully worked example:

$ 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,
$

How to reduce nonconsecutive segments of numbers in array with Thrust

1 Answers1

Linked