4 ms·

Calling Futhark from C and Haskell

88 points by Athas 9y ago

throwaway7645 9y ago
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?
- Athas 9y ago
  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. [0]: https://github.com/arcfide/Co-dfns https://github.com/arcfide/Co-dfns
  - throwaway7645 9y ago
    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.
jarman 9y ago
Chuckled at relevant favicon https://futhark-lang.org/performance.html https://futhark-lang.org/performance.html
- warent 9y ago
  Good eye! Sanic sped
dsign 9y ago
I love the integration C and Haskell. And of course Python. Looking forward to play with it soon!
sspiff 9y ago
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 :)
- Athas 9y ago
  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.
  - sspiff 9y ago
    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.
    - Athas 9y ago
      Yes, both futhark-c and futhark-opencl use the exact same infrastructure.
amelius 9y ago
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.
- 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

88 points by Athas 9y ago

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?

Athas 9y ago
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. [0]: https://github.com/arcfide/Co-dfns https://github.com/arcfide/Co-dfns
- throwaway7645 9y ago
  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.

jarman 9y ago

Chuckled at relevant favicon https://futhark-lang.org/performance.html https://futhark-lang.org/performance.html

warent 9y ago
Good eye! Sanic sped

dsign 9y ago

I love the integration C and Haskell. And of course Python. Looking forward to play with it soon!

sspiff 9y ago

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 :)

Athas 9y ago
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.
- sspiff 9y ago
  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.
  - Athas 9y ago
    Yes, both futhark-c and futhark-opencl use the exact same infrastructure.

amelius 9y ago

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.

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