The functional programming language Haskell provides a very easy
way of parallelization. Consider the following naive implementation of the
Fibonacci function.
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
This implementation has a bad exponential time complexity, so it should be improved, for example with caching.
But this is beyond the scope of this article. For this demonstration we need a function that takes a long time
to finish.
In Haskell there are two operators that have to be used for parallelization:
pseq and par.
-
pseq a b evaluates a then b in sequential order.
-
par a b is some kind of a "fork" operation:
a is started in parallel and b is returned.
par seemed to be a little bit weird on first sight. My first question was:
if b is returned, why is a started anyway?
But keep in mind that Haskell has a lazy evaluation strategy: a is only evaluated if it is needed. Another
feature is, that nodes can be shared. So in a i can compute a value and use it later on somewhere else.
Equipped with this two operations it is very easy to parallelize fib.
parfib n
| n < 11 = fib n -- For small values of n we use the sequential version
| otherwise = f1 `par` (f2 `pseq` (f1+f2)) -- calculate f1 and f2 in parallel, return the sum as the result
where
f1 = parfib (n-1)
f2 = parfib (n-2)
So first we calculate f1 and f2 in parallel and after that we
add them up.
The code has to be compiled with the -threaded option.
ghc -O3 -threaded --make -o parfib ParFib.hs
The number of threads is specified at runtime with the -N command line option.
./parfib +RTS -N7 -RTS
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 parallelization is effective and efficient.
