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
maps, 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 maps 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 foopairs 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 ysOne of the great strengths of Futhark is that parallelism can be
nested. For example, to add two matrices, we simply use two nested
map2s:
def matadd xss yss =
map2 (\xs ys -> map2 (\x y -> x + y)
xs ys)
xss yssmap is the simplest parallel function, yet is surprisingly
versatile. Other common parallel function are
reduce and scatter.