Results 1 to 3 of 3

Thread: string sorting in opencl

  1. #1
    Junior Member
    Join Date
    Aug 2012
    Posts
    2

    string sorting in opencl

    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

  2. #2

    Re: string sorting in opencl

    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.

  3. #3

    Re: string sorting in opencl

    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.

Similar Threads

  1. error to string?
    By ibbles in forum OpenCL
    Replies: 4
    Last Post: 10-20-2009, 05:29 AM
  2. OpenVG 1.0.1 specification: VG_VERSION string
    By muratmat in forum OpenVG and VGU
    Replies: 1
    Last Post: 05-07-2008, 02:57 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •