The functional programming language Haskell provides a very easy way of parallelization.

Consider the following naive implementation of the Fibonacci function.

This implementation has a bad expontential time complexity, so it should be improved, for example with caching. But this is beyond the scope of this article. We just need a function that takes a while to finish.

In Haskell there are two operators that have to be used for parallelization: `par`

and `pseq`

. `par a b`

is some kind of a “fork” operation: `a`

is started in parallel and `b`

is returned. Keep in mind that Haskell is has a lazy evaluation strategy. `a`

is only evaluated if it is needed The function `pseq a b`

evaluates first `a`

then `b`

.

Equipped with this two operations it is very easy to parallelize `fib`

.

The code has to be compiled with the `-threaded`

option.

The number of threads is specified at runtime with the `-N`

command line option.

On an Intel Core i7 920 this resulted in a speedup of 4.13 for `n=38`

. This processor has four physical cores. So this is efficient. Haskell is still one of the best programming languages.

****

Remark: This post was adapted to the new blog format in November 2016.