How to remove a recurring set of integers from an array


I have an array of 4 million 4 byte integers. The integers themselves can range from 0 to 65535.
The integers represent the linear index into a 256x256 bitmap. I zero out the bitmap. Then I typically
launch 4 million threads and each thread writes a “color” (like 0x00FF0000 = red) into the bitmap.
Many of the threads will write to the same index location … but that’s ok since they are writing
the same value. When the process is done a subset of the 65536 locations in the bitmap have
been colored.

I am trying to devise an algorithm that will remove a recurring set of integers from the array so that
the pixel locations are written to exactly once. Forum member Navier Stokes recently turned me on
to the parallel prefix scan and the compaction algorithm to solve another problem I had. I am trying
to reapply the prefix scan operation (possibly with a different associative operator?) to solve my
present problem.

For example, let’s say I have this list of integers

0, 0, 5, 10, 11, 12, 0, 0, 5, 20, 30, 40, 5, 99, 200, 5

I want to remove the duplicates and pack them into

0, 5, 10, 11, 12, 20, 30, 40, 99, 200

It is not necessary that the order of the list be preserved.

Can anyone suggest an algorithm or an example I should look at?




I’m not an expert on such reduction issues. But my idea is to sort the array in parallel and then to copy the array omitting recurrent values. I don’t know how to manage the latter sensibly in parallel.



Exactly right. That last step of eliminating recurrent values in parallel is tricky, but not that hard, see the post linked below.

This problem is very similar to a bucket sort, just with a modified last step of putting the values in an array instead of a bucket. See this post: for my description of a per-block bucket sort. You can also look at the Particles example in the SDK which does a similar operation on a global list.