Parallele Programmierung mit C++

Ziel der Vorlesung ist es, parallele Anwendungen insbesondere auf technischer Ebene zu modellieren und effizient zu implementieren. Die Inhalte sind sehr praxisorientiert und bieten eine Übersicht der gängigsten Parallelisierungstechniken und Architekturen. C++ kommt hier zum Einsatz, da es die einzige moderne Programmiersprache ist, die bei allen vorgestellten Techniken eingesetzt werden kann.

Termine

Vorlesung: Donnerstag, 14-16 Uhr, Helmholtzstraße 18, Raum E20. Am 11. und 12. Juni finden zwei Vorlesungen hintereinander statt, d.h. der Übungstermin am 12. Juni wird überwiegend für die Vorlesung genutzt. Am 16. Juli findet wegen einer terminlichen Kollision keine Vorlesung statt. Die letzte Vorlesung ist somit am 9. Juli.
Übungen: Freitag, 14-16 Uhr, Helmholtzstraße 22, Raum E18. Der letzte Übungstermin ist am 3. Juli.

Inhalt

Modellierung paralleler Systeme mit der Prozessalgebra CSP
Architekturen paralleler Systeme, Speichermodelle
Parallelisierungstechniken: Threads, OpenMP, MPI, GPUs mit CUDA und OpenCL
Design-Patterns paralleler Systeme

Voraussetzungen

Es werden einführende Vorlesungen in die praktische Informatik vorausgesetzt. Hilfreich (aber nicht zwingend notwendig) wären grundlegende Kenntnisse in

systemnaher Programmierung,
Unix/Linux einschließlich der Shell-Ebene und
Netzwerkprogrammierung, insbesondere TCP/IP und BSD-Sockets, wie sie beispielsweise in Systemnahe Software II vermittelt werden.

Eine Einführung in C++ findet zu Beginn in den Übungen statt. Wer keine Vorkenntnisse zu C++ hat, sollte diese Gelegenheit nutzen.

Prüfungen

Die Vorlesung ist für die Master-Studiengänge Mathematik, Wirtschaftsmathematik, Informatik und Medieninformatik vorgesehen. Bei den Bachelor-Studiengängen Informatik und Software-Engineering kann dies als Schwerpunktfach gewählt werden. (Die Einzelheiten dazu lassen sich dem Modulhandbuch entnehmen.) Die Prüfung erfolgt mündlich zu individuell verabredeten Terminen.

Vorlesungen

Begleitend zur Vorlesungen werden hier kapitelweise die zugehörigen Vortragsfolien und ggf. weitere Materialien veröffentlicht:

16. April 2015: Syllabus, Einführung in CSP, csp.tar.gz (Paket mit einem interaktiven Werkzeug zur Simulation einer Teilmenge von CSP, aktualisiert am 20. April 2015, um neuere bison-Versionen zu unterstützen)
21. April 2015: Fortsetzung zu CSP, ein erster Überblick zu parallelen Architekturen
30. April 2015: Einführung zu Threads und Mutex-Variablen in C++
8. Mai 2015: Bedingungsvariablen, std::promise und std::future in C++
21. Mai 2015: Zugriffe auf gemeinsamen Speicher
22. Mai 2015: Konkurrierende Zugriffe auf gemeinsamen Speicher
28. Mai 2015: Einführung zu OpenMP, openmp-rootfinder.tar.gz (Beispiel zum rekursiven Teile- und Herrsche-Pattern mit OpenMP)
11. Juni 2015: Multicomputer ohne gemeinsamen Speicher, Einführung in MPI, mpi-simpson.tar.gz (Trivialbeispiel zu MPI), mpi-chase.tar.gz (Werkzeug zur Messung der Versandzeiten bei MPI)
12. Juni 2015: Dynamische Auftragsverarbeitung mit MPI, synchrone Kommunikation mit MPI_Send und MPI_Recv, mpi-gemv.tar.gz (Trivialbeispiel für das Master/Worker-Pattern mit MPI), gemv.csp (das Beispiel in CSP), mpi-deadlock.tar.gz (Austesten der Pufferung bei MPI_Send / MPI_Recv bis zum Deadlock), mpi-deadlock.csp (das Deadlock-Beispiel in CSP), mpi-buffered.csp (analog, aber mit Pufferung)
18. Juni 2015: Scatter & Gather, Partitionierungs- und Kommunikationsstrategien, Abbildung eines Kommunikationsgraphen auf eine physische Netzwerkstruktur, mpi-gemv-sg.tar.gz (einfaches Beispiel zu Scatter & Gather), mpi-jacobi.tar.gz (Jacobi-Verfahren mit eindimensionaler Aufteilung), mpi-jacobi-2d.tar.gz (Jacobi-Verfahren mit zweidimensionaler Aufteilung, eingebettet ist eine ältere Fassung der FLENS-Bibliothek von Dr. Michael Lehn)
25. Juni 2015: Einführung zur Parallelisierung mit Hilfe grafischer Prozessoren, cuda-properties.tar.gz (CUDA-Programm, das die wichtigsten Merkmale einer Nvidia-Karte ausgibt), cuda-simpson.tar.gz (Trivialfassung mit Aggregierung durch die CPU), cuda-simpson2.tar.gz (Fassung mit blockweiser Aggregierung durch die Kernel-Funktionen)
2. Juli 2015: Speicherbereiche einer GPU, Fallbeispiel: Matrix-Matrix-Multiplikation, CUDA-Streams, cuda-mmm.tar.gz (Matrix-Matrix-Multiplikation mit CUDA)
9. Juli 2015: opencl.tar.gz (OpenCL-Beispiele: opencl-compile, opencl-properties und opencl-simpson; das Makefile ist vorbereitet für Linux mit CUDA und nvcc im Pfad und für OS X mit Xcode und clang)
Alle bisher veröffentlichten Folien in einer Datei (Stand: 2. Juli 2015)

Übungen

Melden Sie sich bitte für die Teilnahme in den Übungen bei SLC an.
Die Übungen sind zeitintensiv und integraler Teil einer praxisorientierten Vorlesung. Die Inhalte aus den Übungen sind prüfungsrelevant, die Teilnahme an den Übungen ist aber nicht Voraussetzung zur Prüfungsanmeldung.
Blatt 1 (Abgabe am 24. April; zu CSP und zur Einführung in C++), Materialien: Makefile, gcc-makedepend (Manualseite), Nim.hpp, Beispiellösung: handshake.csp, 01.tar.gz (Nim-Spiel)
Blatt 2 (Abgabe am 8. Mai; zu Nichtdeterminismus in CSP und zu dynamischen Polymorphismus in C++), Beispiellösung: dnsreq.csp, 02.tar.gz (Nim-Spiel)
Blatt 3 (Abgabe am 22. Mai; zu Fork-and-Join-Pattern mit Threads und den gegenseitigen Ausschluss bei einer gemeinsamen Datenstruktur), Beispiellösung: 03.tar.gz (pgrep)
Blatt 4 (Abgabe am 29. Mai; Implementierung eines neuen Synchronisierungsmechanismus auf Basis von Bedingungsvariablen), Beispiellösung: 04.tar.gz (Bedingungen und Bedingungsmengen)
Blatt 5 (Abgabe am 12. Juni; Jacobi-Verfahren wahlweise direkt mit Threads oder mit OpenMP), Materialien: Makefile (bei OpenMP ist hier noch „-fopenmp“ bei CXXFLAGS und LDFLAGS hinzuzufügen), gen-mp.pl, Beispiellösung: 05.tar.gz (Jacobi-Verfahren mit Threads)
Blatt 6 (Abgabe am 20. Juni; Finden bestimmter Primzahl-Konstellationen in einem Intervall mit MPI), Beispiellösung: 06.tar.gz
Blatt 7 (Abgabe am 26. Juni; Visualisierung der Mandelbrotmenge mit MPI), Materialien: converter.tar.gz (Werkzeug und Funktion, die es erlauben, die Erzeugung der JPG-Datei herauszufaktorisieren), Beispiellösung: 07.tar.gz
Blatt 8 (Abgabe am 3. Juli; auf dem Fork-and-Join-Pattern beruhender Ray-Tracer mit Hilfe von CUDA), Materialien: vorlage.tar.gz, Beispiellösung: 08.tar.gz
Blatt 9 (Abgabe am 9. Juli zur letzten Vorlesung; globale zwei-dimensionale Aggregierung für den Abbruchtest des Jacobi-Verfahrens auf Basis von CUDA), Materialien: jacobi.tar.gz, Beispiellösung: 09.tar.gz
Alle Folien zu dem Crashkurs in C++ in einem PDF-Dokument