18 ms·

Beating C with Futhark Running on GPU

114 points by Athas 7y ago

yiyus 7y ago
Very honest discussion of the results. I liked it. Would it be possible to use Futhark to rewrite the APL implementation instead of the Haskell one? That would make an interesting comparison.
- Athas 7y ago
  > Would it be possible to use Futhark to rewrite the APL implementation instead of the Haskell one? That would make an interesting comparison. Sadly, from what I can see, the APL version makes use of so-called nested arrays in the 'words' function, specifically arrays of strings (this is different from multidimensional arrays). Futhark does not directly support nested arrays. A rewrite of the APL implementation would require using a quite different algorithm (or a nontrivial encoding). But my APL is a bit rusty, so I may be wrong.
  - ummaycoc 7y ago
    In my original version I didn't use a nested array of strings, but [Olzd](https://news.ycombinator.com/user?id=olzd https://news.ycombinator.com/user?id=olzd) pointed out a way you could do that and I added it as a theoretical first attempt (theoretical since it wasn't my first attempt, but would have been had I been better at APL). My first attempt did some stuff with subtracting items in an array from their neighbor. Now with info I got from [mlochbaum](https://news.ycombinator.com/user?id=mlochbaum https://news.ycombinator.com/user?id=mlochbaum) I have another version that uses windowed reductions. So those are three versions there; after that I just split it up just to see where that leads and that actually ends up feeling a lot like the Haskell / Futhark solution to me.
_wldu 7y ago
C is the Mike Tyson of programming languages. There will never be another like it. It's simple, dangerous and fast. You can't beat C, but everyone will keep trying. It may beat itself in the end though as it's too rough for the modern world.
- pjmlp 7y ago
  "Oh, it was quite a while ago. I kind of stopped when C came out. That was a big blow. We were making so much good progress on optimizations and transformations. We were getting rid of just one nice problem after another. When C came out, at one of the SIGPLAN compiler conferences, there was a debate between Steve Johnson from Bell Labs, who was supporting C, and one of our people, Bill Harrison, who was working on a project that I had at that time supporting automatic optimization...The nubbin of the debate was Steve's defense of not having to build optimizers anymore because the programmer would take care of it. That it was really a programmer's issue.... Seibel: Do you think C is a reasonable language if they had restricted its use to operating-system kernels? Allen: Oh, yeah. That would have been fine. And, in fact, you need to have something like that, something where experts can really fine-tune without big bottlenecks because those are key problems to solve. By 1960, we had a long list of amazing languages: Lisp, APL, Fortran, COBOL, Algol 60. These are higher-level than C. We have seriously regressed, since C developed. C has destroyed our ability to advance the state of the art in automatic optimization, automatic parallelization, automatic mapping of a high-level language to the machine. This is one of the reasons compilers are ... basically not taught much anymore in the colleges and universities." -- Fran Allen interview, Excerpted from: Peter Seibel. Coders at Work: Reflections on the Craft of Programming
  - dooglius 7y ago
    I wonder if Allen considered that there might be a reason people chose to use C, it's not as if they were forced into it. "Something where experts can really fine-tune without big bottlenecks" is not a requirement specific to operating systems. It's a bit ironic to think that the inability to run fancy optimizations is considered a problem with C when one of the most widely recognized flaws in the C ecosystem is the way mainstream compilers will exploit behavior that was labeled "undefined" just to support old obscure architectures, to run all kinds of crazy transformations.
    - pjmlp 7y ago
      The same reason people got to choose JavaScript or PHP years later, the platform's adoption, in this case UNIX.
sword_smith 7y ago
This sounds smart. I haven't programmed Futhark yet, though, but I really enjoy functional programming. Where is this language primarily used, at universities or also in industry?
- olodus 7y ago
  I got to use it in university in a course about parallel functional programming. I think it is still mostly a research language, but if you need to do computation on the GPU and like func prog then it probably would be an interesting alternative to try out. It really does a great job of optimizing and parallizing you program.
  - sword_smith 7y ago
    Which university? :)
    - olodus 7y ago
      Chalmers University of Technology, in Gothenburg. Though Futhark is developed in Copenhagen I think. We had a guest lecture with one of the developers of the language. Was a really interesting lecture together with some exercise for us to play with the Lang. Though it has gotten even better since then from what I've seen in their blog.
      - sword_smith 7y ago
        I wonder if this language has spread beyond Europe yet. Do any Americans use it?
tom_mellior 7y ago
I'm starting to sound like a broken record on this, but if you're going to compare to your system wc without trying to figure out if it was compiled with -O3 [EDIT: and what source code it was compiled from], you haven't shown anything in the sequential case. What this article does show is that Futhark really does allow one to express this in a much simpler way than Haskell.
- Athas 7y ago
  That's a good point, but the -O3 doesn't actually do a whole lot here. I recompiled the Futhark-generated C code with just -O and performance was unchanged. If you look at the generated C code, there isn't really a lot to do either: https://gist.github.com/athas/7c8ffc2620a9406e4bbb0df89f2fc9f6 https://gist.github.com/athas/7c8ffc2620a9406e4bbb0df89f2fc9... I hope I can assume that RHEL compiles their wc with at least -O.
  - tom_mellior 7y ago
    > That's a good point, but the -O3 doesn't actually do a whole lot here. True, maybe it's not about -O3 but about some factor in the unknown source code of the system wc. I did compile one version of wc with -O3 and it beat my system wc (Ubuntu) by 2x: https://news.ycombinator.com/item?id=21271951 https://news.ycombinator.com/item?id=21271951
    - Athas 7y ago
      Honestly, I would expect the main reason my wc is faster is that mmap()ing the file and then reading it in a huge chunk is about as fast as the kernel's IO can go. GNU wc cannot do this in general because it's supposed to work on pipes as well, and I doubt anyone cared enough about the tiny performance difference to exploit the case where the input file is mmap()able. (I had actually hoped Futhark would be slower sequentially, just so this wouldn't be the focus of the discussion!)
      - deleted 7y ago
        [deleted]
jacquesm 7y ago
Beating CPU with GPU would have been a better title.
- Svip 7y ago
  I think the title is a reference to the two previous articles that inspired it. Like the old 'X considered harmful' format.
raphlinus 7y ago
Monoid homomorphisms for the win. I discussed a very similar approach for computing the length of the longest line in a "rope science" article[1], as well as unquoting strings[2]. In this case, it was very nice to see actual code, and Futhark looks like a good language. For the string unescaping, I used Nvidia's Thrust, which is a templated C++ library; generally pretty similar to the Futhark code, and generally similar results. [1]: https://xi-editor.io/docs/rope_science_01.html https://xi-editor.io/docs/rope_science_01.html [2]: https://raphlinus.github.io/personal/2018/04/25/gpu-unescaping.html https://raphlinus.github.io/personal/2018/04/25/gpu-unescapi...
jsd1982 7y ago
One could easily amortize the startup cost by putting the backend logic into a background service where it only starts up once and continues running. A frontend program like `wc` would just forward requests to the backend service.
e12e 7y ago
> Word counting is primarily IO-bound, and it is much too expensive to ferry the file contents all the way to the GPU over the (relatively) slow PCI Express bus just to do a relatively meagre amount of computation. After seeing that it's possible to play crysis using software rendering on an AMD Rome cpu with 128 hw threads [1] - might this lead to some vindication for AMD sticking with opencl (assuming exposing such a cpu via opencl) - or is it just simpler to ignore that (in general and for futark) and just use regular threads for parallelizing aacross many cpu cores? [1] https://news.ycombinator.com/item?id=21339652 https://news.ycombinator.com/item?id=21339652
- Mathnerd314 7y ago
  CUDA is proprietary to NVidia, and is pretty much the standard for GPU computing. AMD's been chipping away with OpenCL, Vulkan/GLSL, https://github.com/RadeonOpenCompute/hcc/wiki https://github.com/RadeonOpenCompute/hcc/wiki, etc. but not much luck so far. I wouldn't say AMD's been "sticking with" OpenCL, if anything it seems like they will deprecate it in a few years, as the plan is to fold OpenCL into Vulkan. I guess it is possible to use OpenCL on the CPU as well, but it seems to be intended mostly for testing purposes. The Crysis software renderer uses threads: https://github.com/google/swiftshader/blob/master/src/Common/Thread.hpp https://github.com/google/swiftshader/blob/master/src/Common...
  - rrss 7y ago
    Last I checked, AMD implemented the cuda apis as "hip."
tempodox 7y ago
A nice, unobtrusive way of showing monads at work.
- tathougies 7y ago
  These are monoids, not monads.
Herrin 7y ago
I found this more readable and understandable than the Haskell post, although I can't quite say why. It might simply be the repetition. I'm really interested in Futhark, though I haven't found a project where it would be make sense to use it. But I feel like it has the same potential to make GPU programming not feel overwhelming the same way Elm did with frontend work for me.
- mjaniczek 7y ago
  Since Futhark has sum types, I wonder whether we could transpile Elm syntax to Futhark. I'll have to dig into what's possible with Futhark and how well it would map...
  - Athas 7y ago
    The biggest problem would be the absence of recursion, but a recursion-free subset of Elm (with a different standard library) would be straightforward.
  - earth_walker 7y ago
    James Carson gave a talk at this year's Elm Conf on using Elm to talk to Futhark: https://www.youtube.com/watch?v=FVP8zxpZKV8 https://www.youtube.com/watch?v=FVP8zxpZKV8
makz 7y ago
GPU supremacy
LuvDoctor08 7y ago
Wonderful
hellofunk 7y ago
A lot of the Futhark demos you see are rather basic algorithms like matrix multiplication, and the documentation for Futhark does say that it is not well-suited to complex kernels, so that to me puts a big limiting factor on how useful it could be to invest in it. I really like technologies like this and Sycl which aim to greatly simplify the process of writing GPU code. The important thing is that it can handle what you'd throw at it as if you were writing directly in Metal, Cuda, OpenCL, and I don't think that is the case (yet?) with Futhark.
- Athas 7y ago
  It depends on what you consider a "complex kernel". Futhark is only for regular non-recursive data parallelism, but I'll argue that something like a genetic algorithm that does calibration of market parameters in the Heston model[0] is pretty complex. It comprises multiple levels of parallelism and several kernels (last I checked, the core work is done in four kernels which are invoked in a loop). But more importably, this benchmark is written as a composition of two reusable parts (a genetic algorithm that is parametric in its objective function, and a specific objective function that does option pricing) that are then put together in an efficient and automatic way by the compiler. You literally could not write it this way in OpenCL or CUDA (modulo extreme amounts of template metaprogramming in the latter). While you could certainly write a specialised GPU program that did exactly this calibration, and probably outperform Futhark, you would not be able to structure it as reusable components without significant performance loss. This, I think, is the main advantage of using a high-level language together with an optimising compiler. [0]: https://github.com/diku-dk/futhark-benchmarks/tree/master/misc/heston https://github.com/diku-dk/futhark-benchmarks/tree/master/mi...
  - hellofunk 7y ago
    Thank you for this thoughtful reply, really appreciate it.
ngcc_hk 7y ago
No time working on my I Ching course for my master degree. However I join a programming competition many years ago About an incident of a crazy assignment for a kid. My clone of the github here: https://github.com/kwccoin/ABCDEFGHPPP https://github.com/kwccoin/ABCDEFGHPPP It is fun. I think I even try to use a micro version of cobol to do it. But the fastest is still c. May be we can start one. Sadly no time to join. (I think there is a web site that post many versions of the same program. It must have Wc. If not these should be there. )

114 points by Athas 7y ago

Very honest discussion of the results. I liked it. Would it be possible to use Futhark to rewrite the APL implementation instead of the Haskell one? That would make an interesting comparison.

Athas 7y ago
> Would it be possible to use Futhark to rewrite the APL implementation instead of the Haskell one? That would make an interesting comparison. Sadly, from what I can see, the APL version makes use of so-called nested arrays in the 'words' function, specifically arrays of strings (this is different from multidimensional arrays). Futhark does not directly support nested arrays. A rewrite of the APL implementation would require using a quite different algorithm (or a nontrivial encoding). But my APL is a bit rusty, so I may be wrong.
- ummaycoc 7y ago
  In my original version I didn't use a nested array of strings, but [Olzd](https://news.ycombinator.com/user?id=olzd https://news.ycombinator.com/user?id=olzd) pointed out a way you could do that and I added it as a theoretical first attempt (theoretical since it wasn't my first attempt, but would have been had I been better at APL). My first attempt did some stuff with subtracting items in an array from their neighbor. Now with info I got from [mlochbaum](https://news.ycombinator.com/user?id=mlochbaum https://news.ycombinator.com/user?id=mlochbaum) I have another version that uses windowed reductions. So those are three versions there; after that I just split it up just to see where that leads and that actually ends up feeling a lot like the Haskell / Futhark solution to me.

_wldu 7y ago

C is the Mike Tyson of programming languages. There will never be another like it. It's simple, dangerous and fast. You can't beat C, but everyone will keep trying. It may beat itself in the end though as it's too rough for the modern world.

pjmlp 7y ago
"Oh, it was quite a while ago. I kind of stopped when C came out. That was a big blow. We were making so much good progress on optimizations and transformations. We were getting rid of just one nice problem after another. When C came out, at one of the SIGPLAN compiler conferences, there was a debate between Steve Johnson from Bell Labs, who was supporting C, and one of our people, Bill Harrison, who was working on a project that I had at that time supporting automatic optimization...The nubbin of the debate was Steve's defense of not having to build optimizers anymore because the programmer would take care of it. That it was really a programmer's issue.... Seibel: Do you think C is a reasonable language if they had restricted its use to operating-system kernels? Allen: Oh, yeah. That would have been fine. And, in fact, you need to have something like that, something where experts can really fine-tune without big bottlenecks because those are key problems to solve. By 1960, we had a long list of amazing languages: Lisp, APL, Fortran, COBOL, Algol 60. These are higher-level than C. We have seriously regressed, since C developed. C has destroyed our ability to advance the state of the art in automatic optimization, automatic parallelization, automatic mapping of a high-level language to the machine. This is one of the reasons compilers are ... basically not taught much anymore in the colleges and universities." -- Fran Allen interview, Excerpted from: Peter Seibel. Coders at Work: Reflections on the Craft of Programming
- dooglius 7y ago
  I wonder if Allen considered that there might be a reason people chose to use C, it's not as if they were forced into it. "Something where experts can really fine-tune without big bottlenecks" is not a requirement specific to operating systems. It's a bit ironic to think that the inability to run fancy optimizations is considered a problem with C when one of the most widely recognized flaws in the C ecosystem is the way mainstream compilers will exploit behavior that was labeled "undefined" just to support old obscure architectures, to run all kinds of crazy transformations.
  - pjmlp 7y ago
    The same reason people got to choose JavaScript or PHP years later, the platform's adoption, in this case UNIX.

sword_smith 7y ago

This sounds smart. I haven't programmed Futhark yet, though, but I really enjoy functional programming. Where is this language primarily used, at universities or also in industry?

olodus 7y ago
I got to use it in university in a course about parallel functional programming. I think it is still mostly a research language, but if you need to do computation on the GPU and like func prog then it probably would be an interesting alternative to try out. It really does a great job of optimizing and parallizing you program.
- sword_smith 7y ago
  Which university? :)
  - olodus 7y ago
    Chalmers University of Technology, in Gothenburg. Though Futhark is developed in Copenhagen I think. We had a guest lecture with one of the developers of the language. Was a really interesting lecture together with some exercise for us to play with the Lang. Though it has gotten even better since then from what I've seen in their blog.
    - sword_smith 7y ago
      I wonder if this language has spread beyond Europe yet. Do any Americans use it?

tom_mellior 7y ago

I'm starting to sound like a broken record on this, but if you're going to compare to your system wc without trying to figure out if it was compiled with -O3 [EDIT: and what source code it was compiled from], you haven't shown anything in the sequential case. What this article does show is that Futhark really does allow one to express this in a much simpler way than Haskell.

Athas 7y ago
That's a good point, but the -O3 doesn't actually do a whole lot here. I recompiled the Futhark-generated C code with just -O and performance was unchanged. If you look at the generated C code, there isn't really a lot to do either: https://gist.github.com/athas/7c8ffc2620a9406e4bbb0df89f2fc9f6 https://gist.github.com/athas/7c8ffc2620a9406e4bbb0df89f2fc9... I hope I can assume that RHEL compiles their wc with at least -O.
- tom_mellior 7y ago
  > That's a good point, but the -O3 doesn't actually do a whole lot here. True, maybe it's not about -O3 but about some factor in the unknown source code of the system wc. I did compile one version of wc with -O3 and it beat my system wc (Ubuntu) by 2x: https://news.ycombinator.com/item?id=21271951 https://news.ycombinator.com/item?id=21271951
  - Athas 7y ago
    Honestly, I would expect the main reason my wc is faster is that mmap()ing the file and then reading it in a huge chunk is about as fast as the kernel's IO can go. GNU wc cannot do this in general because it's supposed to work on pipes as well, and I doubt anyone cared enough about the tiny performance difference to exploit the case where the input file is mmap()able. (I had actually hoped Futhark would be slower sequentially, just so this wouldn't be the focus of the discussion!)
    - deleted 7y ago
      [deleted]

jacquesm 7y ago

Beating CPU with GPU would have been a better title.

Svip 7y ago
I think the title is a reference to the two previous articles that inspired it. Like the old 'X considered harmful' format.

raphlinus 7y ago

Monoid homomorphisms for the win. I discussed a very similar approach for computing the length of the longest line in a "rope science" article[1], as well as unquoting strings[2]. In this case, it was very nice to see actual code, and Futhark looks like a good language. For the string unescaping, I used Nvidia's Thrust, which is a templated C++ library; generally pretty similar to the Futhark code, and generally similar results. [1]: https://xi-editor.io/docs/rope_science_01.html https://xi-editor.io/docs/rope_science_01.html [2]: https://raphlinus.github.io/personal/2018/04/25/gpu-unescaping.html https://raphlinus.github.io/personal/2018/04/25/gpu-unescapi...

jsd1982 7y ago

One could easily amortize the startup cost by putting the backend logic into a background service where it only starts up once and continues running. A frontend program like `wc` would just forward requests to the backend service.

e12e 7y ago

> Word counting is primarily IO-bound, and it is much too expensive to ferry the file contents all the way to the GPU over the (relatively) slow PCI Express bus just to do a relatively meagre amount of computation. After seeing that it's possible to play crysis using software rendering on an AMD Rome cpu with 128 hw threads [1] - might this lead to some vindication for AMD sticking with opencl (assuming exposing such a cpu via opencl) - or is it just simpler to ignore that (in general and for futark) and just use regular threads for parallelizing aacross many cpu cores? [1] https://news.ycombinator.com/item?id=21339652 https://news.ycombinator.com/item?id=21339652

Mathnerd314 7y ago
CUDA is proprietary to NVidia, and is pretty much the standard for GPU computing. AMD's been chipping away with OpenCL, Vulkan/GLSL, https://github.com/RadeonOpenCompute/hcc/wiki https://github.com/RadeonOpenCompute/hcc/wiki, etc. but not much luck so far. I wouldn't say AMD's been "sticking with" OpenCL, if anything it seems like they will deprecate it in a few years, as the plan is to fold OpenCL into Vulkan. I guess it is possible to use OpenCL on the CPU as well, but it seems to be intended mostly for testing purposes. The Crysis software renderer uses threads: https://github.com/google/swiftshader/blob/master/src/Common/Thread.hpp https://github.com/google/swiftshader/blob/master/src/Common...
- rrss 7y ago
  Last I checked, AMD implemented the cuda apis as "hip."

tempodox 7y ago

A nice, unobtrusive way of showing monads at work.

tathougies 7y ago
These are monoids, not monads.

Herrin 7y ago

I found this more readable and understandable than the Haskell post, although I can't quite say why. It might simply be the repetition. I'm really interested in Futhark, though I haven't found a project where it would be make sense to use it. But I feel like it has the same potential to make GPU programming not feel overwhelming the same way Elm did with frontend work for me.

mjaniczek 7y ago
Since Futhark has sum types, I wonder whether we could transpile Elm syntax to Futhark. I'll have to dig into what's possible with Futhark and how well it would map...
- Athas 7y ago
  The biggest problem would be the absence of recursion, but a recursion-free subset of Elm (with a different standard library) would be straightforward.
- earth_walker 7y ago
  James Carson gave a talk at this year's Elm Conf on using Elm to talk to Futhark: https://www.youtube.com/watch?v=FVP8zxpZKV8 https://www.youtube.com/watch?v=FVP8zxpZKV8

makz 7y ago

GPU supremacy

LuvDoctor08 7y ago

Wonderful

hellofunk 7y ago

A lot of the Futhark demos you see are rather basic algorithms like matrix multiplication, and the documentation for Futhark does say that it is not well-suited to complex kernels, so that to me puts a big limiting factor on how useful it could be to invest in it. I really like technologies like this and Sycl which aim to greatly simplify the process of writing GPU code. The important thing is that it can handle what you'd throw at it as if you were writing directly in Metal, Cuda, OpenCL, and I don't think that is the case (yet?) with Futhark.

Athas 7y ago
It depends on what you consider a "complex kernel". Futhark is only for regular non-recursive data parallelism, but I'll argue that something like a genetic algorithm that does calibration of market parameters in the Heston model[0] is pretty complex. It comprises multiple levels of parallelism and several kernels (last I checked, the core work is done in four kernels which are invoked in a loop). But more importably, this benchmark is written as a composition of two reusable parts (a genetic algorithm that is parametric in its objective function, and a specific objective function that does option pricing) that are then put together in an efficient and automatic way by the compiler. You literally could not write it this way in OpenCL or CUDA (modulo extreme amounts of template metaprogramming in the latter). While you could certainly write a specialised GPU program that did exactly this calibration, and probably outperform Futhark, you would not be able to structure it as reusable components without significant performance loss. This, I think, is the main advantage of using a high-level language together with an optimising compiler. [0]: https://github.com/diku-dk/futhark-benchmarks/tree/master/misc/heston https://github.com/diku-dk/futhark-benchmarks/tree/master/mi...
- hellofunk 7y ago
  Thank you for this thoughtful reply, really appreciate it.

ngcc_hk 7y ago

No time working on my I Ching course for my master degree. However I join a programming competition many years ago About an incident of a crazy assignment for a kid. My clone of the github here: https://github.com/kwccoin/ABCDEFGHPPP https://github.com/kwccoin/ABCDEFGHPPP It is fun. I think I even try to use a micro version of cobol to do it. But the fastest is still c. May be we can start one. Sadly no time to join. (I think there is a web site that post many versions of the same program. It must have Wc. If not these should be there. )