Futhark the Conqueror

[jxxcarlson]

I have been experimenting with Futhark as a way of doing computationally intensive work on behalf of an Elm app. The idea is to use a specialized functional language to offload those computations to the computer’s GPU – the graphical processing unit. The GPU is far faster than the CPU. Think of it as your personal supercomputer. Here is what you need to know:

Futhark is a small programming language designed to be compiled to efficient parallel code. It is a statically typed, data-parallel, and purely functional array language in the ML family, and comes with a heavily optimising ahead-of-time compiler that presently generates GPU code via CUDA and OpenCL, although the language itself is hardware-agnostic and can also run on multicore CPUs.

The little Elm app pictured above illustrates what can be done with current technology. The app runs a simulation of heat conduction in a thin metal plate. The idea is that if a point on the plate is hotter than than it is nearby, heat will flow from hot to cold; thus the temperature at that point will drop, approaching the average nearby temperature more and more closely as time increases. This idea can easily be put in precise mathematical form, whereupon it can be translated into a computer program… In the example above, there is a 400x400 grid of “cells” inside each of which the temperature is constant. One updates the temperature at each tick of the clock using the algorithm alluded to above. This requires 400x400 = 160,000 computations per step. One can, however, ask the GPU to carry out k such updates before sending the data back to the Elm app. In the example pictured below, we do this k=100 times. Thus each “big update” step requires 16,000,000 computations, Looking at the bottom of the image, we see that this took the GPU 21 milliseconds – just over one Elm animation frame. The app code is on GitHub

NOTE ADDED. I forgot to commit a file needed in ./futhark-server/image/. Should be working now (10:45 am, April 29). Please let me know if not.

The approach used in the demo is a bit on the clunky side. Futhark is not a general-purpose programming language and must always be hosted by another system. At the moment this can be done in C, Python, and Haskell. (Like Elm, the Futhark compiler is written in Haskell). What we do is to rig up a small Python server that hosts the Futhark code, then send data from 'Elm to Python. Futhark processes the data, and Python sends it back to Elm.

A simpler solution with fewer moving parts is desirable. While at the Elm In the Spring conference this week, I learned about the webGPU API project, which could provide a much better means of integration with Elm. Troels Henriksen, the creator of Futhark has said that he wants to provide a browser-compatible means of integrating Futhark. If this comes to fruition, it will open up new spaces in which Elm can play a useful role, e.g., statistics, scientific computing, and modeling.

Some technical details

In the Github repo for the demo app, there are two branches. Both feature an Elm app wired to Futhark using a Python server. In the master branch version, the computed temperature distribution is sent to Elm as an array of floats and is visualized by rendering the NxN comstituent squares as SVG. The results in a huge performance bottleneck that dominates all others as N approaches 100. With N = 100, the app must create 10,000 DOM nodes for each “frame” of the simulation. Gets veeery sluggish. In the png branch, an approach suggested by @gampleman and @folkertdev is used. The result of the computation is rendered as a PNG file by the Python server, and this file is displayed by the Elm app (and requiring just one DOM node). Using this solution, the app is quite snappy with N = 400. Another problem surface, however. The display “blinks” when the temperature map is upddated. Well, sometimes it does, other times it doesn’t, which is weird. Various solutions have been suggested by @ilias and @danabrams. I’ll be working on those ideas.

Learning Futhark

Futhark code is not hard to understand for someone with experience in Elm. Below is an example – a function which computes the average of a list of numbers.

   let average (xs: []f64) = reduce (+) 0.0 xs / r64 (length xs

Note the reduce function, which is just a fold. A great deal of Futhark code is consists of map and reduce. There is also a convenient loop.

Plans

I will continue to use rhe heat conduction app as a test bed for finding better ways of integrating Elm and Futhark. I am also working on a package to do PCA (Principal Component Analysis) computations in statistics and data science.

Note. One can view the heat conduction model as a cellular automaton, that is, in the same conceptual family as Conway’s Game of Life. An interesting detour would be to couple the Game of Life to the heat condiction (diffusion) model so as to have a sort of Game of Life with diffusion. This would be akin to some of the reaction-diffusion models used to study chemical reactions and spontaneous pattern formation.

I’d be very interested in any comments, info that you might have and also hearing from people who are interested in using or are using Futhark. Let’s make the future functional!

Acknowledgements

I have received a lot of help on this project. It was a comment by @folkertdev mentioning Futhark on the Elm Slack that got me started. I’m a bit afraid to list everyone that has helped for fear of overlooking someone. But I thank you all. It is a joy to work in this community and to learn from so many smart and generous people.

Notes

1. “Futhark” stands for the first six letters of the Elder Runic alphabet. The “th” is pronounced like Greet theta. See the inscription below.

2. Futhark the computer language was conceived in Troels Henriksen’s PhD thesis at the University of Copenhagen, 2017. Troels describes himself as a compiler writer, not a language designer. The thesis abstract gives a succinct account of the contributions that the language and compiler bring to the problem of making GPU code writable by standard humans.

3. Troels Henriksen speaking at BornHack.2018 (video). The talk has a lot of interesting technical detail, but the discussion that begins around 23:00 is particularly interesting to aficionados of functional programming.

[Dan_Abrams]

I think the intervention between elm and a high-performance computational server outside the browser is extremely interesting. This is a very impressive demo.

I know that a number of us are trying to find a way to do processing that’s not possible or practical inside the browser into the browser because we love making our UIs with Elm. It’s a major limitation of the browser platform. It would be really nice if Electron offered a “OpenGL context widget” or something that let an independent futhark process render to a dom node in a high performance way.

And of course it would be lovely if all the lovely elm APIs could work with native uis, for this very reason…

Anyway, it’s very impressive example.

[ondrej-tucek]

Woah that’s very interesting a project. I’ve a couple notes:

• I was a little bit confused by a phrase “a simulation of heat conduction in a thin metal plate” and found no code (in repo git) for the numerical method of solving heat PDE + initial / boundary conditions The matrix would look different and the calculations would be much faster. But I got it, as an example it is great.

• is visualized by rendering the NxN comstituent squares as SVG.

  I think there are two possibilities now:

  1. for each submatrix of matrix NxN find the best fit of SVG color gradient, so the final count would be less then NxN.

  2. or with this point is related what was mentioned above. I mean a mathematical background of the problem. Because this is 2D problem, it can be meshed by different sizes of squares or rectangles (the area of plate is also square). And now you can proceed as at point 1).

• small Python server that hosts the Futhark code, then send data from 'Elm to Python. Futhark processes the data, and Python sends it back to Elm.

  What try Phonix Live view (with or without Elm) + websocket + Elixir + Futhark?

[jxxcarlson]

Thanks for the suggestions … I’ll see if I am able to do something better. The blinking really must be fixed. Have never tried Phoenix live view or websockets – will look into it. But maybe the mesh/gradient idea will work. As long as it is not too hard for me One reason that I used Python is that Futhark can compile code for pyopencl.

Re the heat equation, the code is in ./futhark-server/heat.fut. The computation is done by the two functions below. The newValue function computes the temperature at location [i,j] at time t + 1 from the values of the temperature field nearby at time time t. It is just moving the temperature at [i,j] closer to the average temperature nearby. This uses a numerical Laplacian – it is the coefficient of beta in the last expression (expand and collect terms).

let newValue [rows][cols]
         (beta: f32) (field: [rows][cols]f32) (row: i32) (col: i32): f32 =
  unsafe
  let sum =
      field[row-1,col] + field[row+1,col]
      + field[row,  col-1] + field[row,  col+1]
  in (1-beta) * field[row,col] + beta * (sum / 4f32)

Then the newValue function is mapped over the current temperature field to produce the next temperature field. The parameter beta (in the range (0,1)) is the diffusion coefficient.

let newField [rows][cols]
                (beta: f32) (field: [rows][cols]f32): [rows][cols]f32 =
  unsafe
  map (\row ->
        map(\col ->
              if row > 0 && row < rows-1 && col > 0 && col < cols-1
              then newValue beta field row col
              else field[row,col])
            (0...cols-1))
      (0...rows-1)