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.
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
reduce function, which is just a fold. A great deal of Futhark code is consists of
reduce. There is also a convenient
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!
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.
“Futhark” stands for the first six letters of the Elder Runic alphabet. The “th” is pronounced like Greet theta. See the inscription below.
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.
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.