4 ms·

Streaming Combinators and Extracting Flat Parallelism

143 points by Athas 9y ago

fulafel 9y ago
Has anyone here tried Futhark? Is it ready to use or mostly PL research?
- DannyBee 9y ago
  These types of things are mostly PL research. Staring at their repo, Futhark is better than most in terms of "readyness", but it's still probably not something you'd want to start programming all your GPU code in :) It lacks a lot of developer friendliness.
  - Athas 9y ago
    What would be a good starting point for adding more friendliness?
    - tombert 9y ago
      I would say good tooling really lowers the barrier of entry for these things. Things like good editor integrations (such as being able to see the type under the cursor, or highlight errors inline) and a package manager make things a million times easier for a developer to get started on this. I'm not entirely sure how to do the package management , as that's kind of a religious argument, but it's relatively easy to make basic Vim/NeoVim, Emacs, or Atom integrations, which I think would make a lot more people be willing to check it out. I am nearly positive that the tooling that came with Go is a pretty big reason for its success.
      - CyberDildonics 9y ago
        I don't know why this seems to be contentious, tooling is a major issue and driving force behind languages and modern programming. Debuggers, syntax checking editors etc are huge factors in productivity.
    - DannyBee 9y ago
      It doesn't even always produce sane error messages right now :) It also misses a bunch of syntactic sugar that make programming inconsistent from what one would expect in a bunch of cases (they acknowledge this up front). Past that, in part, getting people to adopt new languages is about either providing them an ecosystem that is amazing to start and trying to convince them to jump ... OR meeting them where they are now (IE building integration into existing editors, tooling, etc). Usually people try to get people to jump. You'll note that this rarely works and is a very long and slow burn when it does. This is true even when the new ecosystem is huge. The successful jump cases are usually somewhere in the middle, where they are leveraging existing ecosystems but providing something better enough. Futhark is neither providing a better ecosystem to jump to, or meeting people where they are.
      - Athas 9y ago
        Insightful and reasonable, thanks! In particular, I agree that the error messages could probably do with a few hints of what to do next. I find Elm's work on user-friendly error messages rather inspiring. Editor integration would definitely also be interesting. I suspect the best approach would be to implement the language server protocol, as there are too many editors to handle all of them individually. The hope for Futhark is that a "jump" will be much smaller than for other languages, since it's not really supposed to replace any language, just to augment existing ones. It should feel more like using a library than adding a new language to a project. Of course, there is still a compilation step, but if necessary, that can be crudely circumvented by simply adding the (portable) code generated by the Futhark compiler to source control. So, the strategy is definitely to meet people where they are - building an entire ecosystem is not really feasible for such a small and specialised language. Most people don't even have the problems that Futhark tries to solve, which is certainly a nontrivial hindrance to usage.
    - abstractcontrol 9y ago
      I do not feel like writing an entire essay on language integration right now - most likely I will open an issue 6-12 months from now on Futhark's Github repo just to talk about it, but let me start with agreeing everything what DannyBee said and adding a few thoughts of my own. 1) Let me just say that language integration is a very serious issue. It is not just between completely different languages, but also between modules written in the same language. Once you start using algebraic datatypes to emulate language features the main language lacks, you essentially step into a dynamic sublanguage and have to deal with the friction caused by crossing module boundaries. This friction is both on the programmer's side – he has to deal with writing boilerplate for crossing the boundaries, and on the computer's side which has to do marshaling which is terrible for performance and just nasty. 2) This friction in the case of Futhark will be magnified manifold as it is a completely different language. Since Futhark is not a general purpose language, a realistic use case for it to be called indirectly directly by other languages who will generate code for it. This is generally how high-speed anything is used today. There is a collection of highly optimized, assembly written routines (such as BLAS) bundled into a library and they are called from very slow high-level languages such as Python. Futhark today is not fit for such a purpose. * It would be difficult to partition the program written for it into separate pieces. For very simple programs, at a minimum it will generate 2k lines of code (in the C backend). * This is compounded by the fact that it does not link to the aforementioned optimized libraries, but generates all the code internally. You could then imagine using Futhark intermittently – calling those fast libraries in the main language and using Futhark for the rest since writing code in Futhark is much more convenient compared to C, but then you would need to partition the program and will immediately run into the code bloat issues in the first bullet point. * Futhark is a very high level language and takes on all the responsibility for managing memory on itself. That even further clashes with the idea of partitioning the program. Memory allocations are extremely slow on the GPU, and in addition to that, they block the whole device meaning they are not asynchronous. * A minor point of friction compared to the above is that Futhark supports OpenCL which has minor market share instead of Cuda. 3) Based on the above, I question the current integration strategy by Futhark of making backend for different languages. It currently has a C and a Python backend, and an OpenCL CPU backend, and F# is planned, and you can imagine many different backends… What might be worth trying instead would be to make Futhark an embedded interpreted language. This is not as crazy as it seems – it would define a natural API point for other languages to access it and the interpreter would be responsible for managing GPU memory. It would be a much better model than disposing everything once the program stops running and would allow for efficient intermingling of multiple Futhark programs that could reside in memory. Right now, that sort of thing would be very high friction. I do not have much advice on how this could be accomplished and would no doubt require much design work, but I am going to try something like that in my own language at some point. I had this crucial insight when I was trying to use it from the language it was written in and realized that it is actually very difficult. Scala, Clojure and F# in particular had the master stroke of latching themselves to already established ecosystems. Languages targeting the GPU cannot use that strategy directly and will need to be more inventive.
- jlg23 9y ago
  Apparently you can write APL and have it transpiled to Futhark[1]. Now to the question whether APL is ready for production use... ;) [1] http://futhark-lang.org/blog/2016-06-20-futhark-as-an-apl-compiler-target.html http://futhark-lang.org/blog/2016-06-20-futhark-as-an-apl-co...
  - throwaway7645 9y ago
    I know that's a joke, but it has been around in production since the 60's, so probably not that bad lol.
- ngws 9y ago
  As someone else pointed out, Futhark can be compiled into a Python program or library that uses PyOpenCL. For some "ecosystem" uses of this, you can look for the 'futhark' tag on GitHub: https://github.com/search?q=topic%3Afuthark&type=Repositories https://github.com/search?q=topic%3Afuthark&type=Repositorie... (Disclaimer: Currently just my own silly projects, but hopefully more will follow.)
purpleog 9y ago
I'm curious to know how Futhark relates in performance to halide -- halide is more specific to image processing, but uses a similar approach (domain-specific language compiled to multiple target platforms): http://halide-lang.org http://halide-lang.org
tibbe 9y ago
The Data Parallel Haskell work on flattening ran into problems with space blow-up due to replicating arrays to perform flattening. Does Futhank avoid those problems?
- Athas 9y ago
  Yes. Since Futhark does not perform full flattening, replication is limited to how much parallelism is exploited, not how much parallelism is available. (That said, memory explosion is still a common symptom when the compiler misjudges how much parallelism should be exploited.)

143 points by Athas 9y ago

fulafel 9y ago

Has anyone here tried Futhark? Is it ready to use or mostly PL research?

DannyBee 9y ago
These types of things are mostly PL research. Staring at their repo, Futhark is better than most in terms of "readyness", but it's still probably not something you'd want to start programming all your GPU code in :) It lacks a lot of developer friendliness.
- Athas 9y ago
  What would be a good starting point for adding more friendliness?
  - tombert 9y ago
    I would say good tooling really lowers the barrier of entry for these things. Things like good editor integrations (such as being able to see the type under the cursor, or highlight errors inline) and a package manager make things a million times easier for a developer to get started on this. I'm not entirely sure how to do the package management , as that's kind of a religious argument, but it's relatively easy to make basic Vim/NeoVim, Emacs, or Atom integrations, which I think would make a lot more people be willing to check it out. I am nearly positive that the tooling that came with Go is a pretty big reason for its success.
    - CyberDildonics 9y ago
      I don't know why this seems to be contentious, tooling is a major issue and driving force behind languages and modern programming. Debuggers, syntax checking editors etc are huge factors in productivity.
  - DannyBee 9y ago
    It doesn't even always produce sane error messages right now :) It also misses a bunch of syntactic sugar that make programming inconsistent from what one would expect in a bunch of cases (they acknowledge this up front). Past that, in part, getting people to adopt new languages is about either providing them an ecosystem that is amazing to start and trying to convince them to jump ... OR meeting them where they are now (IE building integration into existing editors, tooling, etc). Usually people try to get people to jump. You'll note that this rarely works and is a very long and slow burn when it does. This is true even when the new ecosystem is huge. The successful jump cases are usually somewhere in the middle, where they are leveraging existing ecosystems but providing something better enough. Futhark is neither providing a better ecosystem to jump to, or meeting people where they are.
    - Athas 9y ago
      Insightful and reasonable, thanks! In particular, I agree that the error messages could probably do with a few hints of what to do next. I find Elm's work on user-friendly error messages rather inspiring. Editor integration would definitely also be interesting. I suspect the best approach would be to implement the language server protocol, as there are too many editors to handle all of them individually. The hope for Futhark is that a "jump" will be much smaller than for other languages, since it's not really supposed to replace any language, just to augment existing ones. It should feel more like using a library than adding a new language to a project. Of course, there is still a compilation step, but if necessary, that can be crudely circumvented by simply adding the (portable) code generated by the Futhark compiler to source control. So, the strategy is definitely to meet people where they are - building an entire ecosystem is not really feasible for such a small and specialised language. Most people don't even have the problems that Futhark tries to solve, which is certainly a nontrivial hindrance to usage.
  - abstractcontrol 9y ago
    I do not feel like writing an entire essay on language integration right now - most likely I will open an issue 6-12 months from now on Futhark's Github repo just to talk about it, but let me start with agreeing everything what DannyBee said and adding a few thoughts of my own. 1) Let me just say that language integration is a very serious issue. It is not just between completely different languages, but also between modules written in the same language. Once you start using algebraic datatypes to emulate language features the main language lacks, you essentially step into a dynamic sublanguage and have to deal with the friction caused by crossing module boundaries. This friction is both on the programmer's side – he has to deal with writing boilerplate for crossing the boundaries, and on the computer's side which has to do marshaling which is terrible for performance and just nasty. 2) This friction in the case of Futhark will be magnified manifold as it is a completely different language. Since Futhark is not a general purpose language, a realistic use case for it to be called indirectly directly by other languages who will generate code for it. This is generally how high-speed anything is used today. There is a collection of highly optimized, assembly written routines (such as BLAS) bundled into a library and they are called from very slow high-level languages such as Python. Futhark today is not fit for such a purpose. * It would be difficult to partition the program written for it into separate pieces. For very simple programs, at a minimum it will generate 2k lines of code (in the C backend). * This is compounded by the fact that it does not link to the aforementioned optimized libraries, but generates all the code internally. You could then imagine using Futhark intermittently – calling those fast libraries in the main language and using Futhark for the rest since writing code in Futhark is much more convenient compared to C, but then you would need to partition the program and will immediately run into the code bloat issues in the first bullet point. * Futhark is a very high level language and takes on all the responsibility for managing memory on itself. That even further clashes with the idea of partitioning the program. Memory allocations are extremely slow on the GPU, and in addition to that, they block the whole device meaning they are not asynchronous. * A minor point of friction compared to the above is that Futhark supports OpenCL which has minor market share instead of Cuda. 3) Based on the above, I question the current integration strategy by Futhark of making backend for different languages. It currently has a C and a Python backend, and an OpenCL CPU backend, and F# is planned, and you can imagine many different backends… What might be worth trying instead would be to make Futhark an embedded interpreted language. This is not as crazy as it seems – it would define a natural API point for other languages to access it and the interpreter would be responsible for managing GPU memory. It would be a much better model than disposing everything once the program stops running and would allow for efficient intermingling of multiple Futhark programs that could reside in memory. Right now, that sort of thing would be very high friction. I do not have much advice on how this could be accomplished and would no doubt require much design work, but I am going to try something like that in my own language at some point. I had this crucial insight when I was trying to use it from the language it was written in and realized that it is actually very difficult. Scala, Clojure and F# in particular had the master stroke of latching themselves to already established ecosystems. Languages targeting the GPU cannot use that strategy directly and will need to be more inventive.
jlg23 9y ago
Apparently you can write APL and have it transpiled to Futhark[1]. Now to the question whether APL is ready for production use... ;) [1] http://futhark-lang.org/blog/2016-06-20-futhark-as-an-apl-compiler-target.html http://futhark-lang.org/blog/2016-06-20-futhark-as-an-apl-co...
- throwaway7645 9y ago
  I know that's a joke, but it has been around in production since the 60's, so probably not that bad lol.
ngws 9y ago
As someone else pointed out, Futhark can be compiled into a Python program or library that uses PyOpenCL. For some "ecosystem" uses of this, you can look for the 'futhark' tag on GitHub: https://github.com/search?q=topic%3Afuthark&type=Repositories https://github.com/search?q=topic%3Afuthark&type=Repositorie... (Disclaimer: Currently just my own silly projects, but hopefully more will follow.)

purpleog 9y ago

I'm curious to know how Futhark relates in performance to halide -- halide is more specific to image processing, but uses a similar approach (domain-specific language compiled to multiple target platforms): http://halide-lang.org http://halide-lang.org

tibbe 9y ago

The Data Parallel Haskell work on flattening ran into problems with space blow-up due to replicating arrays to perform flattening. Does Futhank avoid those problems?

Athas 9y ago
Yes. Since Futhark does not perform full flattening, replication is limited to how much parallelism is exploited, not how much parallelism is available. (That said, memory explosion is still a common symptom when the compiler misjudges how much parallelism should be exploited.)