In der funktionalen Programmiersprache Haskell gibt es eine sehr
einfache Möglichkeit der Parallelisierung. Betrachte die folgende naive Implementierung
der Fibonacci-Funktion.
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
Diese Implementierung hat eine exponentielle Laufzeit und müsste eigentlich verbessert werden.
Aber hier ist es so gewollt, denn wir benötigen eine langlaufende Funktion.
In Haskell gibt es zwei Operatoren, die zur Parallelisierung verwendet werden:
pseq und par.
-
pseq a b wertet a und dann b in sequentieller Reihenfolge aus.
-
par a b ist eine Art von "fork":
a wird parallel gestartet und der Wert von b wird zurückgegeben.
par erscheint anfangs etwas merkwürdig, aber Haskell hat eine Lazy-Auswertungsstrategie und das
Ergebnis von a kann ja auch später weiterverwendet werden.
Ausgestattet mit diesen beiden Operationen ist eine Parallelisierung von fib sehr einfach.
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)
Erst werden parallel f1 und f2 berechnet und anschließend werden sie addiert.
Das Programm muss mit der Option -threaded kompiliert werden.
ghc -O3 -threaded --make -o parfib ParFib.hs
Die Anzahl der Threads wird zur Laufzeit mit -N angegeben.
./parfib +RTS -N7 -RTS
Mit einem Intel Core i7 920 gab es für n=38 einen
Speedup von 4.13.
Dieser Prozessor hat vier physikalische Kerne, also ist die Parallelisierung effektiv und effizient.
