Computerprozessoren werden heutzutage nicht mehr mit jeder neue Generation
schneller und schneller. Stattdessen konzentrieren sich die Chiphersteller
darauf mehr Prozessorkerne in unsere Rechner einzubauen. Für die
Softwareentwicklung bedeutet dies dass Software nicht mehr automatisch mit
jeder Prozessorgeneration schneller läuft sondern dass die Entwickler
dafür etwas tun müssen.
Ein Zauberwort heißt daher parallele Programmierung. Damit ist gemeint
dass verschiedene Teile eines Programms gleichzeitg ablaufen können, somit
mehrere Prozessorkerne auslasten und im Endeffekt schneller an‘s Ziel
kommen. Die automatische Parallelisierung von Software ist allerdings
immer noch ein Traum; stattdessen muss Parallelität von Hand in die Software
eingebaut werden. Funktionale Programmierung eignet sich hervorragend zur
parallelen Programmierung, insbesondere weil funktionale Programme
diszipliniert und sparsam mit Seiteneffekten umgehen und damit ein großes
Hindernis für Parallelität von Grund auf vermeiden.
Dieser Artikel demonstriert, wie man in der funktionalen Sprache
Haskell sehr einfach und elegant parallele Programme
schreiben kann. Dazu stelle ich eine Haskell-Bibliothek vor, die Parallelität
ermöglicht ohne dabei auf ein deterministisches Programmverhalten zu verzichten.
Das bedeutet dass ein mit der Bibliothek entwickeltes paralleles Programm
garantiert dasselbe Ergebnis liefert, egal ob es auf einem, zwei oder 32
Prozessorkernen läuft (sofern das Programm keine anderen, nicht-deterministischen
Teile enthält).
In anderen Sprachen ist im Gegensatz dazu Parallelität häufig nicht-deterministisch.
Damit werden Programme deutlicher schwerer zu debuggen,
da sie beispielsweise auf einem Kern wunderbar funktionieren, auf zwei Kernen aber
das falsche Ergenbis berechnen und es auf vier Kernen hin und wieder
zu einem Deadlock kommt.
Als kleine Vorausblick hier der Speedup in Relation zur Anzahl der Kerne,
den wir mit Parallelität in Haskell
durch eine sehr einfache Modifikation eines ursprünglich sequentiellen Programms
erzielen können:
</img>
Zum Verständnis des Artikels sind Grundkenntnisse in Haskell sowie Bekanntschaft
mit der do-Notation hilfreich.
Bevor wir richtig loslegen, noch eine kurze Abgrenzung zwischen Parallelität
und Nebenläufigkeit. Wie oben geschrieben hat Parallelität zum Ziel ein
Programm schneller zu machen. Nebenläufigkeit hingegen ist eine inherente
Eigenschaft eines Programm und dient dazu, gleichzeitig mehrere
Interaktionen mit der Außenwelt führen zu können. Ein nebenläufiges Programm
ist damit zwangsläufig nicht-deterministisch, wohingegen parallele Programme
durchaus deterministisch sein können und es in diesem Artikel auch sind.
So, jetzt aber zu unserem konkreten Beispiel. Ich möchte in diesem Artikel
zeigen wie man in Haskell ein paralleles Programm zum Lösen von Sudokurätseln
entwickeln kann. Das Programm soll dabei auf beliebig viele Prozessorkerne
skalieren und die vorhandenen Kerne möglichst effizient ausnützen. Das gezeigte
Beispiel basiert auf einem Tutorial
von Simon Marlow. Ich habe den Code mit dem Glasgow Haskell Compiler
in Version 7.6.2 getestet.
In einem ersten Schritt schreiben wir ein sequentielles Programm. Wir
importieren zunächst das Modul Sudoko, welches eine Funktion solve
zum Lösen eines Sudokus bereitstellt. Da es in diesem Artikel nicht um Algorithmen
zum Lösen von Sudokurätsel geht und alle Parallelisierungsarbeit außerhalb
des Solvers stattfinden wird, spielt die eigentliche Implementierung des Sudoku-Moduls
keine Rolle. Außerdem importieren wir ein
spezielles Drivermodul
sowie ein Standardmodul.
-- Datei SudokuSeq.hs
import Sudoku
import Driver
import Data.Maybe
Das Drivermodul, dessen Implementierung an dieser Stelle irrelevant ist,
stellt eine Funktion driver zur Verfügung.
Diese Funktion übernimmt für uns das Parsen der Kommandozeilenargumente,
das Einlesen der Eingabedatei sowie das Extrahieren der einzelnen Rätsel
aus dieser Datei. Wir müssen driver lediglich mit einer Funktion zum
Lösen aller Sudokurätsel aufrufen. Die driver Funktion berechnet dann die
Lösungen und gibt die Anzahl der gelösten Rätsel aus.
Das restliche sequentielle Programme sieht dann wie folgt aus:
main = driver computeSolutions
where
computeSolutions puzzles =
filter isJust (map solve puzzles)
Das Argument puzzles von computeSolutions ist
eine Liste von Sudokurätseln.
Der Ausdruck map solve puzzles wendet die solve-Funktion auf jedes dieser Rätsel an.
Mit filter isJust können wir
aus der Ergebnisliste die echten Lösungen herausfiltern.
Jetzt können wir das Programm mit folgendem Befehl kompilieren:
ghc --make -O2 -threaded -rtsopts SudokuSeq.hs
Der komplette Code zu diesem Artikeln kann auch
heruntergeladen werden.
In dem .zip-Archiv befindet sich auch eine Datei sudoku17.1000.txt, welche 1000
Rätseln mit jeweils 17 vorbelegten Feldern enthält. Wenn wir nun das kompilierte
SudokuSeq mit dieser Datei aufrufen erhalten wir als Ausgabe tatsächlich 1000.
Da wir an der Laufzeit interessiert sind müssen wir dem Aufruf noch ein paar
extra Argumente spendieren:
./SudokuSeq +RTS -s -RTS sudoku17.1000.txt
Der Text zwischen +RTS und -RTS sind Parameter für das Laufzeitsystem. Damit
erhalten wir u.a. folgende Zusatzinformationen:
Total time 1.52s ( 1.53s elapsed)
Hier wird die gesamte CPU Zeit des Programms mit 1,52 Sekunden angegeben. Die komplette Laufzeit
(„wall time“) betrug 1,53 Sekunden. Nicht wirklich überraschend, schließlich handelt es sich um ein
sequentielles Programm.
Wir möchten nun dieses Programm parallelisieren. In Haskell stehen dazu mehrere Möglichkeiten
zur Verfügung. Wir beschäftigen uns in diesem Artikel mit einer Möglichkeit welche Parallelität
explizit einführt und Datenabhängigkeiten über spezielle Boxen repräsentiert.
Wenn Sie die folgenden Beispiel ausprobieren möchten, müssten Sie zunächst das
Paket monad-par installieren. Am einfachsten geschieht dies über den Befehl
cabal install monad-par-0.3
Nun zu unserer ersten Version des parallelen Sudoku-Solvers. Damit sie die Grundlagen
des monad-par Bibliothek besser kennenlernen, benutzt diese Version die Primitivoperationen
der Bibliothek. Wir werden dann in einer zweiten Version sehen, wie man das Problem
einfacher und effizienter mit von der Bibliothek bereitgestellten Abstraktionen lösen kann.
-- Datei SudokuPar1.hs
import Sudoku
import Driver
import Data.Maybe
import Control.Monad.Par
main = driver computeSolutions
where
computeSolutions puzzles =
let (as, bs) = splitAt (length puzzles `div` 2) puzzles
in runPar (do b1 <- new
b2 <- new
fork (put b1 (map solve as))
fork (put b2 (map solve bs))
res1 <- get b1
res2 <- get b2
return (filter isJust (res1 ++ res2)))
Um die Funktionalität des Pakets monad-par nutzen zu können ist der Import
von Control.Monad.Par hinzugekommen. Außerdem ist die Funktion computeSolutions deutlich
komplizierter geworden. Mittels splitAt teilen wir zunächst die Eingabe in zwei
etwa gleich große Teile as und bs auf. Auf diesen beiden Teilen soll
nun die Lösung parallel berechnet werden. Dazu bedienen wir uns folgender
primitiven Operationen aus dem Control.Monad.Par Modul:
-
new Legt eine neue „Box“ an in der später das Ergebnis einer parallelen Berechnung
gespeichert wird. Da wir zwei Berechnungen parallel ausführen möchten legen
wir zwei solcher Boxen b1 und b2 an.
-
put Speichert das Ergebnis einer Berechnung in einer Box. Damit parallele Berechnungen
deterministisch bleiben ist es verboten ein Ergebnis in eine volle Box zu schreiben.
-
get Holt das Ergebnis einer Berechnung aus einer Box. Falls die Box leer ist wartet
get solange bis ein Ergebnis vorliegt.
-
fork Stößt eine Berechnung an die dann parallel abläuft. In unserem Beispiel
benutzen wir fork um zwei parallele Berechnungen zu starten, die ihre Ergebnisse
in die Boxen b1 und b2 schreiben. Während die Berechnungen noch laufen
warten wir mittels get bis die Ergebnisse in b1 und b2 vorliegen.
-
runPar Um aus der Welt der parallelen Berechnungen das Ergebnis in die Welt der „normalen“
Haskell-Berechnungen zurückzureichen, müssen wir die parallele Berechnung auf oberster
Ebene in ein runPar einpacken.
Schauen wir uns nun mal die sequentielle Performance unserer ersten parallelen Version an.
Dies ist immer eine gute Prüfung um sich zu vergewissern, dass man nicht völligen
Blödsinn programmiert hat:
./SudokuPar1 +RTS -s -RTS sudoku17.1000.txt
Total time 1.52s ( 1.54s elapsed)
Wir erinnern uns, die sequentielle Version benötigt für denselben Benchmark insgesamt 1,53
Sekunden, es scheint also alles zu passen. Um nun mehrere Prozessorkerne zu verwenden
müssen wir dem Haskell Laufzeitsystem (RTS) die Option -N<K> mitgeben, wobei
<K> die Anzahl der Kerne ist:
./SudokuPar1 +RTS -s -N2 -RTS sudoku17.1000.txt
Total time 1.57s ( 0.97s elapsed)
Aha, jetzt brauchen wir nur noch 0,97 Sekunden anstatt 1,53 Sekunden im sequentiellen Fall.
Der Speedup berechnet sich wie üblich als Quotient dieser beiden Zeiten, also
1,53 / 0,97 = 1,55. Das ist leider nicht ganz das was wir erwartet haben, denn
da das Problem fast vollständig parallelisierbar ist sollte der Speedup bei zwei Kernen irgendwo
knapp unterhalb von 2 liegen.
Um dem Problem auf den Grund zu gehen erstellen wir während des Programmlaufs ein
Eventlog, das wir danach analysieren. Dazu müssen wir das
Programm mit der -eventlog Flag neu kompilieren
ghc --make -O2 -threaded -rtsopts -eventlog -o SudokuPar1_e SudokuPar1.hs
und dann mit der RTS Option -ls nochmals ausführen:
./SudokuPar1_e +RTS -s -N2 -ls -RTS sudoku17.1000.txt
Dann benutzen wir threadscope
um das damit erzeugte Eventlog SudokuPar1_e.eventlog
zu analysieren. Hier ist ein Screenshot des Hauptfensters von threadscope:
</img>
Richtig interessant am obigen Screenshot sind eigentlich nur die unteren beiden,
etwas dünneren, grünen Streifen. Diese zeigen die Aktivitäten der Prozessorkerne an.
Offensichtlich laufen die zwei Kerne nach einer kurzen Startphase schön parallel.
Aber nach etwas mehr als der Hälfte der Zeit geht einem Kern offensichtlich die Arbeit aus
und es ist nur noch ein Kern aktiv. Das Problem ist, dass
das Lösen zweier Sudokurätsel unterschiedlich lange dauern kann und dass unsere
Strategie, die Liste der Rätsel einfach in zwei Hälften zu teilen, diesen
Aspekt nicht berücksichtigt.
Schauen wir uns auch noch an was unsere erste parallele Version macht wenn wir ihr vier Kerne
zur Verfügung stellen:
./SudokuPar1 +RTS -s -N4 -RTS sudoku17.1000.txt
Total time 1.80s ( 1.03s elapsed)
Oh, die Performance ist sogar ein klein wenig schlechter geworden, obwohl meine Maschine
vier echte Kerne hat. Die etwas schlechtere Performance liegt am größeren Overhead
der durch die Verteilung auf mehrere Kerne entsteht.
Es sollte aber auch einleuchtend sein, dass wir mit unserer
fixen Aufteilung der Sudokurätsel in zwei Teile niemals mehr als zwei Kerne
beschäftigen können.
Wir benötigen daher eine flexiblere Strategie zur Aufteilung der Sudokurätsel
in parallele Berechnungen. Wir bedienen uns dabei eines Ansatzes der sich
dynamische Partitionierung nennt. Die Idee ist dass wir die Sudokurätsel
in viele kleine Einheiten aufteilen, und dass sich das Laufzeitsystem von Haskell
darum kümmert diese kleinen Einheiten in sinnvolle Arbeitspakete für einen Prozessorkern
zusammenzupacken. Mit diesem Ansatz lösen wir beide Probleme die mit unserer
ersten Version aufgetreten sind:
-
Es ist egal wie groß die einzelnen Teilprobleme sind. Wenn ein Prozessorkern
nichts mehr zu tun hat schiebt ihm das Laufzeitsystem neue Arbeit zu.
-
Wir müssen nicht im voraus die Anzahl der zur Verfügung stehenden Prozessorkerne
planen, denn das Laufzeitsystem kümmert sich auch um diesen Aspekt.
Hier nun die überarbeitete parallele Version mit dynamischer Partitionierung:
-- Datei SudokuPar2.hs
import Sudoku
import Driver
import Data.Maybe
import Control.Monad.Par
main = driver computeSolutions
where
computeSolutions puzzles =
filter isJust (runPar (parMap solve puzzles))
Der einzige Unterschied zur ursprünglichen, sequentiellen Version ist, dass wir anstelle von
map solve puzzles nun runPar (parMap solve puzzles) schreiben. Die Funktion
parMap kommt dabei aus dem Modul Control.Monad.Par. Der Aufruf
parMap solve puzzles ruft nun solve für jedes Rätsel in puzzles auf und
zwar so dass dem Laufzeitsystem Gelegenheit gegeben wird die Aufrufe von solve
geeignet zu parallelisieren. Sie sehen also: Parallelisierung ist in Haskell sehr einfach
und die monad-par Bibliothek garantiert, dass alles deterministisch abläuft
und dass keine Deadlocks oder sonstige, bei nebenläufigen Programmen typischen Probleme
auftreten.
Wir werden uns am Ende des Artikels auch noch die
Implementierung von parMap anschauen, wollen jetzt aber zunächst sehen welche
Performance unsere verbesserte parallele Version mit dynamischer Partitionierung
liefert:
Zunächst wieder eine sequentielle Ausführung als Lakmustest:
./SudokuPar2 +RTS -s -RTS sudoku17.1000.txt
Total time 1.51s ( 1.53s elapsed)
Und jetzt parallele Ausführungen mit zwei, drei und vier Kernen:
./SudokuPar2 +RTS -s -N2 -RTS sudoku17.1000.txt
Total time 1.54s ( 0.78s elapsed)
Speedup: 1,96
./SudokuPar2 +RTS -s -N3 -RTS sudoku17.1000.txt
Total time 1.55s ( 0.53s elapsed)
Speedup: 2,88
./SudokuPar2 +RTS -s -N4 -RTS sudoku17.1000.txt
Total time 1.56s ( 0.41s elapsed)
Speedup: 3,71
Ich habe testweise auch mal eine größere Eingabedatei mit 16.000 Sudokurätseln
getestet, hier ergeben sich sehr ähnliche Speedups.
Wie versprochen schauen wir uns zum Schluss noch eine mögliche
Implementierung von parMap an:
parMap f xs =
do bs <- mapM g xs
mapM get bs
where
g x =
do b <- new
fork (put b (f x))
return b
Die Funktion g legt für jedes Listenelement mit new eine neue Box and
und benutzt dann fork um f x parallel zu berechnen und das Ergebnis
in der Box zu speichern. Der Aufruf mapM g xs wendet nun g auf jedes Element
von xs an, so dass wir danach in bs die Boxen für die Ergebnisse von f
vorfinden. Schließlich holen wir mittels mapM get bs
die Ergebnisse aus den Boxen.
So, das war‘s für heute. Den Code zum Artikel finden Sie
hier.
Ich freue mich über jede Art von Rückmeldung!