Übungsblatt

Prof. Dr. rer. nat. Roland Wismüller
Parallelverarbeitung
Wintersemester 2015/16
Aufgabenblatt 2
(Zu bearbeiten bis 07.01.2016)
Vorbereitung: Laden Sie sich die Programme für das Aufgabenblatt aus dem Internet:
http://www.bs.informatik.uni-siegen.de/web/wismueller/vl/ws1516/pv/u2Files.zip
Aufgabe 1: Parallelisierung von Schleifen
In loops.cpp finden Sie einige Schleifen, die Arrays bearbeiten. Analysieren Sie diese Schleifen und entscheiden Sie, ob sie (ohne Synchronisation) parallelisierbar sind. Ggf. können Sie die Schleifen auch umstrukturieren,
um Abhängigkeiten zu beseitigen.
Testen Sie Ihre Analyse, indem Sie die parallelisierbaren Schleifen mit Hilfe der OpenMP-Direktive parallel
for parallelisieren (verwenden Sie keine anderen Direktiven). Wenn Sie das Programm übersetzen (mit Hilfe
von make) und ausführen, prüft der Code in main.cpp, ob Ihr paralleler Code noch exakt dasselbe Eegebnis
berechnet und gibt ggf. eine Fehlermeldung aus. Der Code in main.cpp darf nicht verändert werden!
Aufgabe 2: Parallelisierung einer numerischen Integration mit OpenMP
Der Code in integrate.cpp berechnet das Integral einer vorgegebenen Funktion f(x) von 0 bis 1 mit Hilfe der Mittelpunktsregel. Die Funktion f(x) berechnet dabei den Ausdruck 4/(1 + x ∗ x), so daß das Integral
genau den Wert π hat. Die Datei enthält den Integrations-Code viermal: eine Version (implementiert in der Funktion Serial Integration()) soll zum Vergleich sequentiell bleiben, die anderen drei (in den Funktionen
Parallel Integration1() bis Parallel Integration3()) sollen Sie wie folgt parallelisieren:
1. mit Hilfe einer OpenMP Reduktion,
2. mit Hilfe der OpenMP ordered Direktive,
3. durch Aufteilen der Schleife in einen parallelisierbaren und einen sequentiellen Teil.
Die main()-Funktion ruft alle vier Funktionen auf und druckt das Ergebnis, den Fehler, die Laufzeit und ggf.
den Speedup aus. Das makefile enthält die nötigen Befehle zum Kompilieren und Binden des Programms (Sie
brauchen nur das Kommando ‘make’ aufzurufen).
Messen Sie, wieviel Zeit Ihre Funktionen jeweils benötigen. Probieren Sie dabei verschiedene Werte für die Anzahl
der Threads und der Intervalle aus (Anhaltswert: 100.000) und vergleichen Sie die Zeiten für die sequentielle und
die parallelen Implementierungen. Interpretieren Sie Ihre Ergebnisse.
Überlegen Sie bei der zweiten Variante (mit ordered Direktive), wie Sie durch geeignetes Scheduling der Schleife die Laufzeit verbessern können!
Die erste parallele Version (mit der OpenMP Reduktion) berechnet nicht genau dasselbe Ergebnis wie die sequentielle. Warum nicht? Achten Sie bei den Versionen 2 und 3 darauf, daß das Ergebnis exakt mit dem der sequentiellen
Version übereinstimmt!
Aufgabe 3: Parallelisierung des Jacobi-Verfahrens mit OpenMP
In dieser Aufgabe betrachten wir das Jacobi-Verfahren zur iterativen Lösung eines Randwertproblems. Beim der
Jacobi-Iteration wird aus einer gegebenen Wertematrix eine neue berechnet, indem jedem inneren Element der
1
neuen Matrix der Mittelwert der vier Nachbarelemente der alten Matrix zugewiesen wird. Die Iteration wird dabei
solange wiederholt, bis die maximale Änderung eines Elementes unter einer vorgegebenen Schranke liegt.
Parallelisieren Sie den sequentiellen Code der Jacobi-Iteration in der Datei solver-jacobi.cpp mit Hilfe
von OpenMP Direktiven. Die hier vorkommende Berechnung der maximalen Änderung ist eine Reduktion, die in
dieser Form von OpenMP erst ab der Version 4.0 direkt unterstützt wird. Verwenden Sie zur parallelen Berechnung
daher die Methode, die am Ende des Abschnitts 2.6 Synchronisation“ gezeigt wird.
”
Testen Sie das Programm mit verschiedenen Matrix-Größen und Thread-Anzahlen. Das Programm gibt am Ende
die Werte mehrerer Matrix-Elemente aus. Achten Sie darauf, daß diese Ergebnisse bei ihrer parallelen Version
exakt (d.h. in allen Kommastellen) mit denen des sequentiellen Programms übereinstimmen müssen!
Zur weiteren Kontrolle können Sie auch die ausgegebene Lösung (in der Datei Matrix.txt) mit dem JavaProgramm ViewMatrix am Bildschirm betrachten. Diese Ausgabe erfolgt jedoch nur bis zu einer Matrix-Größe
von 1000.
Führen Sie eine Leistungsanalyse mit Scalasca durch und versuchen Sie, Ihr Programm z.B. durch Einsparung von
Barrieren weitestgehend zu optimieren. Bestimmen Sie den erreichbaren Speedup für unterschiedliche Anzahlen
von Threads. Verwenden Sie einen Knoten des HorUS-Clusters, um mehr als 4 Threads nutzen zu können.
Zum Nachdenken: Warum bekommen Sie auf den Dual-Core CPUs mit Hyperthreading im H-A 4111 (bslab0106, 11-12 und 14-18) keinen Speedup über 2 hinaus, wenn Sie sequentielle und parallele Version mit eingeschalteter Optimierung (-O) übersetzen?
Aufgabe 4: Parallelisierung des Gauss/Seidel-Verfahrens mit OpenMP
In dieser Aufgabe soll das Gauss/Seidel-Verfahren parallelisiert werden. Im Gegensatz zum Jacobi-Verfahren verwendet das Gauss/Seidel-Verfahren nur eine Matrix, in der jedes Element durch den Mittelwert seiner Nachbarelemente ersetzt wird. Der Wert des linken und oberen Nachbarn stammt daber bereits aus der aktuellen Iteration, so
daß sich hier Datenabhängigkeiten ergeben.
In dieser Aufgabe sollen Sie das Verfahren parallelisieren, indem die Schleifen so umstrukturiert werden, daß die
Matrix diagonal durchlaufen wird.
Parallelisieren Sie den sequentiellen Code der Gauss/Seidel-Relaxation in der Datei solver-gauss.cpp mit
Hilfe von OpenMP Direktiven. Der für diese Aufgabe vorgegebene Code unterscheidet sich von dem der Aufgabe 2
nur durch die unterschiedliche Implementierung der Funktion solver(). Zur Vereinfachung iteriert dieser Löser
nicht, bis die maximale Änderung unter einem Schwellwert liegt, sondern schätzt vorab die notwendige Zahl der
Iterationen ab.
Beachten Sie für die Parallelisierung die Hinweise in Aufgabe 3 sowie aus der Vorlesung (Abschnitt 2.5).
Aufgabe 5 (für 8 LP): Pipelineartige Parallelisierung des Gauss/Seidel-Verfahrens mit
OpenMP
Wenn die Zahl der Iterationen fest ist, kann das Gauss/Seidel-Verfahren auch pipelineartig parallelisiert werden
(vgl. Abschnitt 2.5 der Vorlesung). Bei der parallelen Ausführung der i-Schleife muß dazu eine Synchronisation
vorgesehen werden, die folgende (durch die Datenabhängigkeiten vorgegebenen) Bedingungen sicherstellt: bevor
in der Iteration k die i-te Zeile berechnet wird, muß
1. die i-1-te Zeile in Iteration k und
2. die i+1-te Zeile in Iteration k-1
berechnet worden sein. Da OpenMP keine Punkt-zu-Punkt“-Synchronisation, z.B. über Bedingungsvariablen un”
terstützt, muß ein eigenes Synchronisationskonstrukt verwendet werden. Dieses ist als Klasse Cond in der Datei
cond.h vorgegeben:
• Cond(int n): Konstruktor. Der Parameter n gibt die Matrixgröße des Gauss/Seidel-Verfahrens an.
• void signal(int k, int i): Signalisiert, daß Zeile i in Iteration k vollständig berechnet wurde.
• void wait(int k, int i): Wartet solange (aktiv), bis Zeile i in Iteration k vollständig berechnet
wurde.
2
Parallelisieren Sie mit Hilfe der oben genannten Synchronisation das Gauss/Seidel-Verfahren. Vergleichen Sie den
erzielbaren Speedup mit der Parallelisierung aus Aufgabe 4. Verwenden Sie Scalasca zur Leistungsanalyse und
versuchen Sie, Ihr Programm weiter zu optimieren.
Hinweis: Diese Aufgabe darf auch von motivierten Studierenden bearbeitet werden, die nur 5 LP benötigen!
3

Download Report