parallel remove zero in a string on GPUs

Accelerated Computing CUDA CUDA Programming and Performance
1

Hi All,

I need to remove all 0 in a string.
For example: I have a string like " a b 0 c 0 0 0 a b", i need to output " a b c a b", do you have any suggestions?

Thanks a lot.

2

Actually the original question is to merge duplicate string: say I have a string like " a b a a a c c a", i need to merge continuous chars to output " a b a 3 c 2 a", any ideas?

My idea is let each thread merge 3 bytes and replace duplicate char with 0, then the string will bed converted to “a b a 3 0 c 2 a”.

We can demonstrate this with a better example, my process is as below:

" a b a a a a a c c c a a",

a b a 2 a 2 a c c 2 a 2

a b a 4 a 1 0 c 3 0 a 2

a b a 5 0 0 0 c 3 0 a 2

Then the problem is how to remove 0, any good idea?

3

This is outside my area of expertise, but I wonder whether the following paper might be of help:

Markus Billeter, Ola Olsson, and Ulf Assarsson
Efficient Stream Compaction on Wide SIMD Many-Core Architectures
Proceedings of the Conference on High Performance Graphics 2009, New Orleans, LA, 2009, pp. 159-166
http://www.cse.chalmers.se/~billeter/pub/pp/paper.pdf

More generally, the problem at hand appears to be a special case of parallel scan, you might want to search Google Scholar or CiteSeer for that.

4

Thank you so much :)