PDA

View Full Version : string sorting in opencl



amrit
08-31-2012, 11:46 PM
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

bmerry
09-19-2012, 06:47 AM
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.

bmerry
09-19-2012, 06:52 AM
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.