It's nice seeing Futhark on here. I prefer my array languages to be more like APL or J, but perhaps this is better for longer code. I know it is easier for the compiler to put on the GPU I guess?
The biggest issue with compiling APL and J is the presence of dynamic types (and other dynamic behaviour). For the subset of APL can that can be resolved statically, I don't see why they should be particularly difficult (Co-dfns[0] seems to be making good progress). To handle anywhere near full APL, you probably need some complicated JIT compiler, unfortunately.
Big follower of Aaron's work even though I don't use it. He gave two recent talks at Dyalog 17' last week. Both worth at least flipping through the slides.
Hooray! I've been playing with Futhark from time to time (and it's lovely).
I have eagerly been awaiting this development! This is great!
I write much of my code in Rust these days and being able to generate plain C entrypoints to my Futhark functions will allow me to bridge both worlds :)
That's good to hear! You will probably encounter some limitations due to the missing support for error recovery. When you do, we'd very much like to hear from you, to get an understanding of what a proper solution should look like.
For example, we probably should not handle "catastrophic" errors like GPU/compiler bugs the same way we handle "incidental" errors like bounds check failures. The former might well poison the entire context, while the latter should permit subsequent entry points to work.
I have a question regarding the new library generation: is this also supported by futhark-c (or are there plans to support this down the line)?
I'd like to be able to fall back to CPU execution when OpenCL is not available on a platform. I realize this means I will need to reduce the problem set significantly, but it would be nice to be able to run a small demo on unsupported platforms as well.
I'd like to see "efficient string sorting" as one of the examples, as it is structurally very different from most vector operations, yet it can be parallelized very well.
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?
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.
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.
15 comments
[ 7.2 ms ] story [ 38.1 ms ] thread[0]: https://github.com/arcfide/Co-dfns
https://futhark-lang.org/performance.html
I have eagerly been awaiting this development! This is great!
I write much of my code in Rust these days and being able to generate plain C entrypoints to my Futhark functions will allow me to bridge both worlds :)
For example, we probably should not handle "catastrophic" errors like GPU/compiler bugs the same way we handle "incidental" errors like bounds check failures. The former might well poison the entire context, while the latter should permit subsequent entry points to work.
I'd like to be able to fall back to CPU execution when OpenCL is not available on a platform. I realize this means I will need to reduce the problem set significantly, but it would be nice to be able to run a small demo on unsupported platforms as well.
There's also a sorting-contest [2], perhaps it can bring some more inspiration.
[1] https://en.wikipedia.org/wiki/Radix_sort
[2] http://sortbenchmark.org/
[0]: https://github.com/diku-dk/futhark/blob/master/futlib/radix_...
[1]: https://github.com/diku-dk/futhark/blob/master/futlib/merge_...
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_transf...
[2] https://en.wikipedia.org/wiki/FM-index