Table of Contents
Praktikum „Parallele Programmierung“
Beschreibung
Um Mehrkernprozessoren und Multiprozessoren effizient zu nutzen, genügt es nicht, ein serielles Programm zu schreiben. Vierkernsysteme sind auch schon bei Arbeitsplatzrechnern weit verbreitet. Standards wie MPI und OpenMP, erlauben es, in den Programmiersprachen C(++) und Fortran Code zu schreiben, welcher auch auf Hochleistungsrechnern lauffähig ist.
Im Praktikum werden wir das parallele Programmieren mit MPI und OpenMP erlernen und auch eigenständige Anwendungen (z.B. Spielelöser) in Gruppen entwickeln. Im Vergleich zu der Vorlesung Hochleistungsrechnen wird der Fokus auf der Praxis liegen.
Die Veranstaltung wird zum Teil auf Englisch gehalten.
Beachten Sie auch unsere allgemeinen organisatorischen Hinweise zu Praktika.
Lernziel
Ziel des Praktikums ist es, die wichtigsten Parallelisierungskonzepte kennen zu lernen und Problemstellungen selbstständig im Team zu bearbeiten. Die Studierenden gewinnen eine Übersicht über hilfreiche Werkzeuge zur Entwicklung und Bewertung von Anwendungen.
Zielgruppe
Das Projekt eignet sich für Studierende der Informatik in den Diplom- und Bachelorstudiengängen. Studierende anderer Studiengänge müssen die Anrechnung mit dem jeweiligen Prüfungsausschuss klären.
Interessierte Zuhörer sind auch herzlich willkommen.
Die Veranstaltung wird auf Englisch stattfinden.
Daten der Veranstaltung
Dozenten
- Prof. Dr. Julian Kunkel (Ansprechpartner)
Vorgehen
Zunächst werden die Grundlagen theoretisch vermittelt und mit kleinen Beispielen geübt. Im zweiten Teil werden in kleinen Gruppen jeweils unterschiedliche Problemstellungen bearbeitet. Hierbei wird ein (kleiner) Projektplan erstellt und im Team eine Anwendung zur Problemlösung implementiert. Status und aufgetretene Probleme werden regelmäßig gemeinsam besprochen.
Beispiel Problemstellungen
- Optimale Spielzüge ermitteln (Suchbaumverfahren) für Spiele.
- (Einfache) Räuber-Beute-Beziehung eines abgeschlossenen Systems mit Tierwanderung.
- Autos im Straßenverkehr eines Stadtnetzes und entstehende Staus.
Für weitere Vorschläge sind wir offen. Wichtig ist vor allem die korrekte Parallelisierung (evtl. mit Alternativen) und Auswertung. Detaillierte Kenntnisse der Numerik sind nicht erforderlich.
Vorgeschlagene Themen:
- Astrophysikalische Berechnungen
- Skat, Go oder Robotersimulation
- Längste Wege Problem
- Lösen großer logischer Formeln
- Algorithmen aus der Bioinformatik
- Strategien zur Platzierung von Flugzeugpassagieren
Bearbeitung des Projektes
Bei der Durchführung der Projektes sollten einige Inhalte bearbeitet werden und entsprechend in Präsentation und Ausarbeitung einfließen.
- Konzepte des zugrundeliegenden (Anwendungs)-Modells
- Parallelisierungsschema (Kommunikationsmuster, Verteilung der Daten & Aufgaben)
- Es sollte mit MPI parallelisiert werden (optional: Shared-Memory Parallelisierung mit Threads oder OpenMP).
- Leistungsanalyse des sequentiellen Codes (Verhält sich dieser Erwartungskonform)
- Skalierungsverhalten der parallelen Version
- Speedup-Diagramme
- Potentiell Analyse mit Vampir/Sunshot
- Durchführung einer Optimierung der parallelen Version (Kommunikationsschema etc.)
Zeitplan und Materialien
- Vorbesprechung (04.04.2017), Beschreibung des Praktikums, Architekturen, Programmierkonzepte von OpenMP und MPI, Gebietszerlegung und Aufgabenteilung.
- Theoretische Grundlagen (in der Vorlesungszeit)
- 11.04.2017 - Praktisches: Einführung in C, Versionsverwaltung, Clusternutzung, Programmierkonzepte von OpenMP und MPI (2)
- Übung: erste Schritte mit OpenMP und MPI auf unserem Cluster, anlegen eines Repositories und Testbeispiele verwalten. Übungsblatt 1
- Literatur zum Nachlesen:
- Folien in der Vorlesung: Architekturen: 17-46, Anwendungsklassen: 201-241, Threads: 304-381
- 18.04.2017 - Speichermanagement von C/Fortran, Einführung in Debugging, MPI, Individuelle und kollektive Operationen im Detail, nicht-blockierende Aufrufe, Parallelisierung von Anwendungen
- Übung: einfache Probleme selbständig parallelisieren. Werkzeuge: GDB bzw. DDT+Valgrind. Übungsblatt 2
- Vorlesung MPI: 251-277
- 25.04.2017 Der Termin fällt aus.
- 02.05.2017 Leistungsbewertung von Anwendungen, PGAS - Folien
- Einfaches Modell für Leistungsengpässe; CPU: Betrachtungen zu FLOPS, Instructions per Second, Cache-Hit/Miss Ratio, …
- Literatur:
- Übung: Amdahls Gesetz, Speedup-Diagramme bewerten, Projekt-Aufgabenstellung. Übungsblatt 3
- 09.05.2017 – OpenMP, Programmanalyse Werkzeuge Tolle Präsentation -- OpenMP and Performance Tasking Präsentation OpenMP Tutorials sind hier verlinkt
-
- Übung: OpenMP, Leistungsanalyse, Verschiedene Code-Fragmente parallelisieren und die Leistung bewerten. Übungsblatt 4
- 23.05.2017 – Processor-level parallelism, intrinsics in C, low-level memory management (Nabeeh Jum'ah)
- Projektbearbeitung (je nach Absprache auch in der vorlesungsfreien Zeit)
- Hinweise zur Projektbearbeitung Hinweise zur Projektarbeit
- 06.06.2017 – Projektvorstellung und Präsentation der algorithmischen Lösung und Projektplan
- 11.07.2017 Statustreffen – Vorstellung der bisherigen Arbeiten und aufgetretene Probleme
- 15.08.2017 Statustreffen – Vorstellung der bisherigen Arbeiten und aufgetretene Probleme, erste Leistungsergebnisse
- 02.10.2017 Abschlusstreffen – Präsentation der Ergebnisse
Ergebnisse
Direct Gravitational N-body Simulation
Autoren: Nicholas Hickson-Brown, Michael Eidus
Diese Arbeit beschäftigt sich mit der effektiven Parallelisierung eines N-body Codes zur Simulierung der Evolution von Kugelsternhaufen unter Einfluss von Gravitation, sogenannten ”Direct Gravitational N-body Simulations”. Im Kern dieser Arbeit steht die Frage, ob Algorithmen zur numerischen Integration mit Komplexitäten von O(n2) mit entsprechender Parallelisierung effektiver gestaltet werden können, ohne dabei an Genauigkeit zu verlieren. Dazu implementieren wir das dreidimensionale Plummer Dichteprofil zur Generierung initialer Konditionen eines Kugelsternhaufens und das Hermite Schema vierter Ordnung zur Lösung der numerischen Integralrechnung. An- schließend stellen wir ein Parallelisierungschema dar, mit dem die Arbeit auf mehrere Prozesse aufgeteilt werden kann, und implementieren dieses mittels des Message Passing Interface. Zum Abschluss analysieren wir Laufzeiten, Leistung und Skalierbarkeit unserer Anwendung.
Smart Pathing
Autoren: Rami Aly, Christoph Hüter
In dieser Arbeit wird die parallelisierte intelligente Wegfindung und Bewegung von Objek- ten durch einen Graphen für den Anwendungsbereich des Hochleistungsrechnen simuliert. Hierfür wurde das Programm in zwei Teile unterteilt. Im ersten Abschnitt wird eine Routingtable erzeugt, eine Tabelle in der für selektierte Knoten der optimale Pfad und dazugehörige Eigenschaften zu allen Anderen ausgewählten Knoten gespeichert wird. Zwei implementierte Parallelisierungsstrategien werden miteinander verglichen und Verwen- dungszwecke erörtert. Abschließend wird die parallelisierte Bewegung der Objekte im Graphen simuliert. Der Pfad des Objektes wird in Abhängigkeit der Pfade aller weiteren Autos gewählt. Ziel hierbei ist es, alternative Pfade zu erkennen, auf denen ein Auto sein Ziel trotz längerer Strecke schneller erreichen kann.
4-Gewinnt
Autoren: Nikolai Elich, Merlin Sewina
Spiele Vier Gewinnt gegen eine AI die jeden Zug kennt und mit dem MinMax Algorithmus die beste Strategie ausrechnet um dich zu schlagen!
Vier-Gewinnt
Autoren: Timo Hahn
Das Ziel des Projektes war es das Spiel “Vier Gewinnt” selbstspielend mithilfe des Minimax-Algorithmus in C umzusetzen und anschließend mit OpenMP zu parallelisieren.
Literaturhinweise
Links
- C: Wir empfehlen zum Erlernen der Sprache den: Unser Interaktiver C Kurs
- Interne Verarbeitung von OpenMP und Auto-Parallisierung im GCC (von 2006) - OpenMP and automatic parallelization in GCC
- GCC Features um parallel zu programmieren, auch eine schöne kurze Übersicht über die parallele Programmierung Parallel programming with GCC
- GCC Optimierungsflags GCC Handbuch HTML
- Details zu Intel Architektur http://www.intel.com/products/processor/manuals/
- Speicherbandbreite / Ausnutzung abschätzen mit Performance Countern http://software.intel.com/en-us/articles/detecting-memory-bandwidth-saturation-in-threaded-applications/
- What Every Computer Scientist Should Know About Floating-Point Arithmetic http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html
Bücher
- Using MPI, 2nd Edition, by William Gropp, Ewing Lusk, and Anthony Skjellum, published by MIT Press ISBN 0-262-57132-3.
- MPI: The Complete Reference, by Marc Snir, Steve Otto, Steven Huss-Lederman, David Walker, and Jack Dongarra, The MIT Press.
- MPI: The Complete Reference - 2nd Edition: Volume 2 - The MPI-2 Extensions, by William Gropp, Steven Huss-Lederman, Andrew Lumsdaine, Ewing Lusk, Bill Nitzberg, William Saphir, and Marc Snir, The MIT Press.
- Parallel Programming With MPI, by Peter S. Pacheco, published by Morgan Kaufmann.