title: CUDA stream compaction algorithm
body: <p>I'm trying to construct a parallel algorithm with CUDA that takes an array of integers and removes all of the <code>0</code>'s with or without keeping the order.</p>
  
  <p>Example:</p>
  
  <p>Global Memory: {0, 0, 0, 0, 14, 0, 0, 17, 0, 0, 0, 0, 13}</p>
  
  <p>Host Memory Result: {17, 13, 14, 0, 0, ...}</p>
  
  <p>The simplest way is to use the host to remove the <code>0</code>'s in <code>O(n)</code> time. But considering I have around <code>1000</code> elements, it probably will be faster to leave everything on the GPU and condense it first, before sending it.</p>
  
  <p>The preferred method would be to create an on-device stack, such that each thread can pop and push (in any order) onto or off of the stack. However, I don't think CUDA has an implementation of this. </p>
  
  <p>An equivalent (but much slower) method would be to keep attempting to write, until all threads have finished writing:</p>
  
  <pre><code>kernalRemoveSpacing(int * array, int * outArray, int arraySize) {
      if (array[threadId.x] == 0)
          return;
  
      for (int i = 0; i &lt; arraySize; i++) {
  
           array = arr[threadId.x];
  
           __threadfence();
  
           // If we were the lucky thread we won! 
           // kill the thread and continue re-reincarnated in a different thread
           if (array[i] == arr[threadId.x])
               return;
      }
  }
  </code></pre>
  
  <p>This method has only benefit in that we would perform in <code>O(f(x))</code> time, where <code>f(x)</code> is the average number of non-zero values there are in an array (<code>f(x) ~= ln(n)</code> for my implementation, thus <code>O(ln(n))</code> time, but has a high <code>O</code> constant)</p>
  
  <p>Finally, a sort algorithm such as quicksort or mergesort would also solve the problem, and does in fact run in <code>O(ln(n))</code> relative time. I think there might be an algorithm faster than this even, as we do not need to waste time ordering (swapping) zero-zero element pairs, and non-zero non-zero element pairs (the order does not need to be kept).</p>
  
  <blockquote>
    <p>So I'm not quite sure which method would be the fastest, and I still
    think there's a better way of handling this. Any suggestions?</p>
  </blockquote>