View Full Version : string sorting in opencl

amrit

09-01-2012, 12:46 AM

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, 07: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, 07: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.

Powered by vBulletin® Version 4.2.2 Copyright © 2017 vBulletin Solutions, Inc. All rights reserved.