Fork me on GitHub
We are hiring a PhD student to do research on functional high performance computing, including work on Futhark itself. See here for more details. Source file: basic-parallelism.fut

# Basic parallelism

Futhark is a parallel language, but the Futhark compiler is not a parallelising compiler. What this means is that parallelism in Futhark is explicit, and ultimately boils down to a small collection of primitive functions that the compiler knows how to turn into a parallel code. You cannot simply write down independent subexpressions and expect them to run in parallel: you must use a parallel function.

The simplest form of parallelism is `map`, which applies a function to each element of an array, producing a new array.

``def xs = map (+2) [1,2,3]``

Now `xs` has the value `[3,4,5]`. Of course, this is a trivial example. In most cases, arrays must have tens of thousands of elements for parallel execution to be worthwhile. However, for these examples, we will stick to arrays of a size that human minds can comprehend.

You generally don’t need to worry about chaining together multiple `map`s, as the compiler performs map fusion to combine multiple traversals.

``````def foo = map (*3) (map (+2) [1,2,3])

def bar = map (\x -> (x + 2) * 3) [1,2,3]``````

The definitions `foo` and `bar` will be exactly the same after optimisations, so feel free to use multiple `map`s with simpler functions if it makes the code more readable - it will have no effect on performance.

Two arrays can be combined to an array of pairs using `zip`:

``def pairs = zip xs foo``

`pairs` now has the value `[(3, 9), (4, 12), (5, 15)]`. This can be used to implement a function for adding vectors:

``````def vecadd xs ys =
map (\(x,y) -> x + y) (zip xs ys)``````

This pattern is quite common, so there is a `map2` function that allows us to forgo the explicit `zip`:

``````def vecadd_2 xs ys =
map2 (\x y -> x + y) xs ys``````

One of the great strengths of Futhark is that parallelism can be nested. For example, to add two matrices, we simply use two nested `map2`s:

``````def matadd xss yss =
map2 (\xs ys -> map2 (\x y -> x + y)
xs ys)
xss yss``````

`map` is the simplest parallel function, yet is surprisingly versatile. Other common parallel function are reduce and scatter.