How to count a sequence of 1's

Hello

I have an array with a sequence of 0’s and 1’s. I want to produce an array that counts
each sequence of 1’s. For example, if my input looks like this

0,0,0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0,

I want the output in an another array to be

2, 5, 3

How do I do this?

I would say, upload the array to GPU memory and than let each thread evaluate a subset of the sums. On one side this task is perfectly parallel; on the other it will be totally constrained by the PCIe bus, so you will not either get close to the peak performance your GPU is capable of.

is this a compress algorithm?

You may pay attention at the atomicAdd() function, this function not all the thing you need but it gives you some suggestions.

Here’s some code to compute the result using Thrust. This implementation should be pretty quick, although I there may be more clever ways to accomplish the same goal.

[codebox]#include <thrust/device_vector.h>

#include <thrust/segmented_scan.h>

#include <thrust/transform.h>

#include <thrust/remove.h>

#include <thrust/copy.h>

#include // for printing

#include

template

struct filter_values

{

__host__ __device__

T operator()(T value, T next)

{

    if(next == 0)

        return value;

    else

        return 0;

}

};

int main(void)

{

const int N = 17;

int h_input[N] = {0,0,0,1,1,0,0,1,1,1,1,1,0,1,1,1,0};

// copy input to the device

thrust::device_vector<int> d_input(h_input, h_input + N);

// temporary storage

thrust::device_vector<int> d_temp(N, 0);

// sum segments of 1s together

thrust::experimental::inclusive_segmented_scan(d_input.begin

(), d_input.end(), d_input.begin(), d_temp.begin());

// zero out all values except the last one in each segment

thrust::transform(d_temp.begin(), d_temp.end() - 1, d_input.begin() + 1, d_temp.begin(), filter_values<int>());

// remove all zeros

thrust::device_vector<int>::iterator temp_end = thrust::remove(d_temp.begin(), d_temp.end(), 0);

// copy remaining values to output vector

thrust::device_vector<int> d_output(d_temp.begin(), temp_end);

// print the result

thrust::copy(d_output.begin(), d_output.end(), std::ostream_iterator<int>(std::cout, "\n"));

return 0;

}[/codebox]