3 ms·

It's a little tricky to implement irregular algorithms in Futhark, but I'd like to give it a try. Do you know of a nice data-parallel algorithm for string sort

by Athas 9y ago

It's a little tricky to implement irregular algorithms in Futhark, but I'd like to give it a try. Do you know of a nice data-parallel algorithm for string sorting?

amelius 9y ago
That would be cool! Radix-sort is an algorithm that is both simple and it can be parallelized [1]. There's also a sorting-contest [2], perhaps it can bring some more inspiration. [1] https://en.wikipedia.org/wiki/Radix_sort https://en.wikipedia.org/wiki/Radix_sort [2] http://sortbenchmark.org/ http://sortbenchmark.org/
- Athas 9y ago
  We already have both a radix sort[0] and a bitonic merge sort[1]. They perform alright - nothing world-shaking, but fine. I was more interested in whether string sorting has some particularly clever algorithms. [0]: https://github.com/diku-dk/futhark/blob/master/futlib/radix_sort.fut https://github.com/diku-dk/futhark/blob/master/futlib/radix_... [1]: https://github.com/diku-dk/futhark/blob/master/futlib/merge_sort.fut https://github.com/diku-dk/futhark/blob/master/futlib/merge_...
  - amelius 9y ago
    Nice to see that you have radix-sorting covered! I'm not aware of sorting algorithms that use "clever" tricks; the challenge with sorting seems to be in the low-level optimization (e.g. making sure that no unnecessary data-copying takes place). If you are looking for a challenge, then you could try sorting arbitrary length strings (more difficult since the comparison operator is of non-constant time). Or do something like the Burrows-Wheeler transform [1], where you sort all rotations of a very large string. This is actually a very useful operation for building a large search index [2]. Many people in e.g. bioinformatics would be very interested in a fast solution. [1] https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf... [2] https://en.wikipedia.org/wiki/FM-index https://en.wikipedia.org/wiki/FM-index

by Athas 9y ago

It's a little tricky to implement irregular algorithms in Futhark, but I'd like to give it a try. Do you know of a nice data-parallel algorithm for string sorting?

amelius 9y ago

That would be cool! Radix-sort is an algorithm that is both simple and it can be parallelized [1]. There's also a sorting-contest [2], perhaps it can bring some more inspiration. [1] https://en.wikipedia.org/wiki/Radix_sort https://en.wikipedia.org/wiki/Radix_sort [2] http://sortbenchmark.org/ http://sortbenchmark.org/

Athas 9y ago
We already have both a radix sort[0] and a bitonic merge sort[1]. They perform alright - nothing world-shaking, but fine. I was more interested in whether string sorting has some particularly clever algorithms. [0]: https://github.com/diku-dk/futhark/blob/master/futlib/radix_sort.fut https://github.com/diku-dk/futhark/blob/master/futlib/radix_... [1]: https://github.com/diku-dk/futhark/blob/master/futlib/merge_sort.fut https://github.com/diku-dk/futhark/blob/master/futlib/merge_...
- amelius 9y ago
  Nice to see that you have radix-sorting covered! I'm not aware of sorting algorithms that use "clever" tricks; the challenge with sorting seems to be in the low-level optimization (e.g. making sure that no unnecessary data-copying takes place). If you are looking for a challenge, then you could try sorting arbitrary length strings (more difficult since the comparison operator is of non-constant time). Or do something like the Burrows-Wheeler transform [1], where you sort all rotations of a very large string. This is actually a very useful operation for building a large search index [2]. Many people in e.g. bioinformatics would be very interested in a fast solution. [1] https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf... [2] https://en.wikipedia.org/wiki/FM-index https://en.wikipedia.org/wiki/FM-index