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
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
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?