2

How to do stream compaction with boost::compute?

E.g. if you want to perform heavy operation only on certain elements in the array. First you generate mask array with ones corresponding to elements for which you want to perform operation:

mask = [0 0 0 1 1 0 1 0 1]

Then perform exclusive scan (prefix sum) of mask array to get:

scan = [0 0 0 0 1 2 2 3 3]

Then compact this array with:

if (mask[i])
    inds[scan[i]] = i;

To get final array of compacted indices (inds):

[3 4 6 8]

Size of the final array is scan.last() + mask.last()

KindDragon
  • 6,558
  • 4
  • 47
  • 75
DikobrAz
  • 3,557
  • 4
  • 35
  • 53
  • I'm not sure what scan has to with things. If I understand correctly it looks like `len(mask) == len(scan)`, scan somehow needs to be an ascending sequence. I'm not getting how "the result" (which variable is that, what is the compaction algorithm that applies that operation shown?) and I'd guess the size of the result is actually `sum(mask)`? I think you might want to clarify the question a bit. – sehe Sep 09 '16 at 09:22
  • @sehe scan is a prefix sum operation, it's a common operation in GPGPU computing, I suggest you to look at https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf – DikobrAz Sep 09 '16 at 23:04

1 Answers1

2
#include <boost/compute/algorithm/copy_if.hpp>

using namespace boost::compute;

detail::copy_index_if(mask.begin(), mask.end(), inds.begin(), _1 == 1, queue);
DikobrAz
  • 3,557
  • 4
  • 35
  • 53