Hi,

I am quite new to this parallel programming. I am trying to implement bwt in openCL. I want to use C for host code . how to use the radix sort program or CLPP library for sorting strings. please help

Hi,

I am quite new to this parallel programming. I am trying to implement bwt in openCL. I want to use C for host code . how to use the radix sort program or CLPP library for sorting strings. please help

Radix sort operates on integers rather than strings, so you’ll need to construct an integer key for each string. If you implement the Burrows-Wheeler Transform using the suffix array approach then you’ll probably get an enumeration out of the core algorithm. For example, once you’ve sorted all substrings of length 2^i, you next want to sort all prefixes of length 2^(i+1). So start by assigning each string of length 2^i a key, which is just its position in the sorted list. A string of length 2^(i+1) is two strings of length 2^i pasted together, so if they have keys A and B you can make a combined key of, say, (A << 32) + B, and sort the strings on this combined key.

By the way, Google for “suffix array prefix doubling” to see the algorithm I’m referring to. I saw that in a previous post you’d used the brute-force algorithm, which is probably going to be much harder to run under OpenCL as the amount of work is data-dependent.