Couple comments here:  GPGPU programming is really good if you can construct your problem as a sorting problem (eg &quot;sort results so interesting tags are at the start of the array&quot;).  From what I&#x27;ve seen this is reliably the most successful approach.<p>One problem can be when the number of output items from a given input item is unpredictable.  You typically want to run a prefix-scan within a block to compact the block&#x27;s output into a single chunk until your shared-memory buffer is full, or you&#x27;ve reached the end of the data set.  Then, you do an ATOMIC increment on a global &quot;slots-used&quot; counter for your output buffer, and write as a big chunk.  This is a lot more complex than sorting, but reasonably fast.<p>If you want to guarantee that your output will fit in the buffer, you need to run the operation twice.  The first run is a &quot;dummy&quot; that writes no output, just figures out the last input element that can write data without the output buffer overflowing.  In some cases it may be preferential to just allocate a reasonable guesstimate of the 95% case and not write past the end if a true worst-case scenario happens.<p>Try like hell to keep everything in registers or shared-memory and avoid writing intermediate data.  High utilization of memory (order complexity) kills performance, both directly (hitting global memory incurs lots of latency) and indirectly (GPUs have the greatest speedup when working on the largest possible working set).