CUDA stream compaction algorithm

by

What you are asking for is a classic parallel algorithm called stream compaction1.

If Thrust is an option, you may simply use thrust::copy_if. This is a stable algorithm, it preserves relative order of all elements.

Rough sketch:

#include <thrust/copy.h>

template<typename T>
struct is_non_zero {
    __host__ __device__
    auto operator()(T x) const -> bool {
        return x != 0;
    }
};

// ... your input and output vectors here

thrust::copy_if(input.begin(), input.end(), output.begin(), is_non_zero<int>());

If Thrust is not an option, you may implement stream compaction yourself (there is plenty of literature on the topic). It’s a fun and reasonably simple exercise, while also being a basic building block for more complex parallel primitives.

(1) Strictly speaking, it’s not exactly stream compaction in the traditional sense, as stream compaction is traditionally a stable algorithm but your requirements do not include stability. This relaxed requirement could perhaps lead to a more efficient implementation?

More Related Contents:

  1. Apply Quicksort to the list M,E,R,G,E,S,O,R,T
  2. What is tail call optimization?
  3. How to determine if a point is in a 2D triangle? [closed]
  4. How does the Google “Did you mean?” Algorithm work? [closed]
  5. Algorithm for Determining Tic Tac Toe Game Over
  6. How to find all combinations of coins when given some dollar value [closed]
  7. How to make rounded percentages add up to 100%
  8. Write a function that returns the longest palindrome in a given string
  9. Data structures for loaded dice?
  10. Writing your own square root function
  11. Merge Sort a Linked List
  12. How do you like your primary keys? [closed]
  13. How do I efficiently determine if a polygon is convex, non-convex or complex?
  14. Cycles in an Undirected Graph
  15. Generating permutations lazily
  16. How to determine if a linked list has a cycle using only two memory locations
  17. Compute the minimal number of swaps to order a sequence
  18. Best word wrap algorithm? [closed]
  19. Find the missing and duplicate elements in an array in linear time and constant space
  20. Function for creating color wheels [closed]
  21. Selection algorithms on sorted matrix
  22. How do I check if a directed graph is acyclic?
  23. Basic Recursion, Check Balanced Parenthesis
  24. How to find the smallest number with just 0 and 1 which is divided by a given number?
  25. Count the number of set bits in a 32-bit integer
  26. Find all pairs of integers within an array which sum to a specified value
  27. Big O when adding together different routines
  28. What are the pitfalls in implementing binary search? [closed]
  29. Can a Fibonacci function be written to execute in O(1) time?
  30. Check if array B is a permutation of A

Leave a Comment