Praktikum „Parallele Programmierung“

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 werden wird der Fokus auf der Praxis liegen.

Beachten Sie auch unsere allgemeinen organisatorischen Hinweise zu Praktika.

Ziel des Praktikums ist es, aktuelle Parallelisierungskonzepte kennen zu lernen und Problemstellungen im Team zu bearbeiten. Die Studierenden gewinnen eine Übersicht über hilfreiche Werkzeuge zur Entwicklung und Bewertung von Anwendungen.

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.

• Dr. Julian Kunkel (Ansprechpartner)
• Nathanael Hübbe
• Michaela Zimmer

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.

• 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.

Konkret vorgeschlagene Themen:

• Astrophysikalische Berechnungen
• Skat, Go oder Robotersimulation
• Längste Wege Problem
• Lösen großer logischer Formeln
• Ein Algorithmus aus der Bioinformatik

1. Theoretische Grundlagen (in der Vorlesungszeit)
   • 11.04.2013 - Architekturen, Programmierkonzepte von OpenMP und MPI, Versionsverwaltung, Anwendungsklassen, Gebietszerlegung und Aufgabenteilung.
     • Ü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, MPI: 251-277, Threads: 304-381
       • Versionsverwaltung: http://www.wr.informatik.uni-hamburg.de/teaching/wintersemester_2011_2012/git-workshop
   • 18.04.2013 - Speichermanagment 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. (In Blatt 1 enthalten) Matrizen
   • 25.04.2013 (VORSICHT, wir sind in Raum 207 (2 OG. DKRZ)) - Leistungsbewertung von Anwendungen, PGAS, MPI-IO - Folien
     • Einfaches Modell für Leistungsengpässe; CPU: Betrachtungen zu FLOPS, Instructions per Second, Cache-Hit/Miss Ratio, …
     • Literatur:
       • http://de.wikipedia.org/wiki/Amdahlsches_Gesetz
       • http://de.wikipedia.org/wiki/Instructions_per_Second
       • http://duartes.org/gustavo/blog/post/what-your-computer-does-while-you-wait
       • http://de.wikipedia.org/wiki/Cache#Cache_Hits_und_Misses
       • An introduction to PGAS programming languages
     • Übung: Amdahls Gesetz, Speedup-Diagramme bewerten, PGAS, MPI-I/O. Übungsblatt 2 Julia Mengen SourceCode
   • 02.05.2013 - OpenMP, Programmanalyse Werkzeuge OpenMP Tutorials sind hier verlinkt
     • Übung: Verschiedene Code-Fragmente parallelisieren und die Leistung bewerten. Übungsblatt 3
   • 16.05.2013 – Optimierung
   • 30.05.2013 – SIMD-Programmierung FolienProjektinformationen und Leistungsanalyse
2. Projektbearbeitung (je nach Absprache auch in der vorlesungsfreien Zeit)
   • Aufgabenstellung
   • 13.06.2013 – (VORSICHT, wir sind in Raum 207 (2 OG. DKRZ)) -Projektvorstellung und Präsentation der algorithmischen Lösung und Projektplan
   • 27.06.2013 – Statustreffen – Vorstellung der bisherigen Arbeiten und aufgetretene Probleme
   • Statustreffen – Vorstellung der bisherigen Arbeiten und aufgetretene Probleme, erste Leistungsergebnisse
   • Präsentation der Ergebnisse

Authors: Martin Poppinga, Marcel Ellermann, Miriam Freiin Heereman von Zuydtwyck

In dieser Arbeit wird ein System zur Verkehrssimulation auf Basis von OpenStreetMap Daten implementiert und Möglichkeiten zur Parallelisierung aufgezeigt, sowie diese implementiert. Die verschiedenen Implementationen werden dann hinsichtlich ihrer Leistung und Skalierbarkeit verglichen.

Präsentation – Ausarbeitung – Source Code – Video Hamburg – Video Kreisverkehr

Authors: Alisa Dammer, Sven-Hendrik Haase

ParaQuest ist eine hochparallele Simulation von Kreaturen in einer 2D-Welt mit einem simplen Kampf- und Kollisionssystem. Die technische Umsetzung erfolgte mit C++11, cereal (für die Serialisierung) und MPI (für die Prozesskommunikation) sowie Qt (für die Visualisierung).

Präsentation – Ausarbeitung – Source Code

Authors: Kira Duwe, Enno Zickler

Solitaire-Schach ist eine Solitairevariante, die ebenfalls allein aber nach Schachregeln gespielt wird. Ziel ist es, dass nur noch eine Figur auf dem Spielbrett übrig bleibt. In jedem Zug muss genau eine Figur geschlagen werden. Die Figuren sind normale Schachfiguren mit ihren üblichen Zugmöglichkeiten. Ausnahme ist nur der Bauer, da er hier in alle Richtungen ziehen kann. Die Startaufstellung auf einem 4×4 Schachbrett besteht aus einer beliebigen Kombination der folgenden Figuren: 1x Dame, 1x König, 2x Springer, 2x Läufer, 2x Turm und 2x Bauer. Unser Programm errechnet, wie viele dieser Startpositionen lösbar sind. Dies ist für Spielbretter bis zur Größe von 21 Feldern (3×7) möglich. Da es für ein 4×4 großes Spielbrett bereits 6,7 Milliarden gültiger Startbelegungen gibt, kann unser Programm auch mit verschiedenen Parallelisierungsstufen auf einem Cluster aufgerufen werden. Parallelisiert wurde mit MPI und OpenMP.

Präsentation – Ausarbeitung – Source Code

Authors: Alexander Droste, Florian Flachsenberg

Die Infektsimulation ermittelt wie sich Infektionskrankheiten innerhalb einer “Bevölkerung” ausbreiten und verhalten.

Präsentation – Ausarbeitung – Source Code (seriell) – Source Code (parallel) – Source Code (better collission detection) – Video

Authors: Markus Fasselt, Julian Schmid, Kim Korte

This project aims to show the consequences resulting from a simulation of prey and predator in a virtual world. By altering one or many of the key parameters, the behavior of the animals is controlled and different outcomes can be observed. Outcome does not necessarily mean a final state of the world in which the simulation eventually runs into but rather the state of the world after a pre-defined number of rounds. It is possible for the simulation to reach a dead-end before completing the set number of rounds. This can happen, for instance, if one population dies from starvation or one eats the other. The final program is able to visualize the results and show appropriate data about the actions leading up to the results. Furthermore, it can be run simultaneously on multiple cores in order to improve performance. The project is written mainly in the programming language C. The parallelization and communication between the processes is based on OpenMPI.

Präsentation – Ausarbeitung – Source Code – Video

Author: Ihar Aleinikau

Das TSP oder auch das Problem des Handlungsreisenden besteht darin, eine Reihenfolge zu finden, damit die Gesamtstrecke des Handlungsreisenden nach der Rückkehr zum Ausgangsort möglichst kurz ist. Das Problem wird folgendermaßen formuliert: Ein Handlungsreisender muss Kunden in einer Reihe von Städten besuchen und zwar in jeder Stadt genau einen. Da er möglichst wenig unterwegs sein möchte, will er die kürzest mögliche Route für seine Tour zusammenstellen. Die kürzesten Entfernungen zwischen je zwei Städten sind ihm bekannt.

Bericht – Präsentation – Source Code

Author: Eugen Betke

Simulators have found a wide application in science. They have established in almost all fields of research and help to answer to some of the open key questions. They are often used to simulate problems were other methods have been proven to be too complicated in some situations. Another strength of simulations is that the additional complexity can often be easily integrated in the simulated model. The main objective of this project is to develop a multi-core capable simulator for the prey-predator model. The simulator shall have the ability to visualize the world, to show statistics about the population development and allow users to control the most important parameters. The simulator doesn’t comply with a special prey- predator model, but implements the model, that is developed in this project. The programming languages used in this project are C and C++. The project benefits from open source software, particularly gtkmm for graphical user interface and pthreads for the implementation of the multi-core capable simulation.

Präsentation – Ausarbeitung – Source Code

Author: Alexander Beifuss, Johann Weging

This project aims to implement bindings of the Message Passing Interface for Googles programming language Go. Go is a young, clean, to native machine code compiling programming language which has the potential to gain ground inside the scientific community and the field of high performance computing. It offers a variety of concurrency features that can be used for parallel programming on shared memory architectures. There all ready exists bindings for different data formates like HDF5 or approaches for GPGPU-Computing with OpenCL or CUDA. This project will enable Go to be run on compute clusters and parallel programming over the network in general. The project uses cgo to wrap Go around existing MPI implementations like OpenMPI and MPICH2. The final implementation of the bindings is than benchmarked against C to determine it’s usefulness and potential. Go, like expected is slower than C but there are still a lot of possibilities for improvements to catch up with the performance of C. The current bindings support a C like interface to MPI according to the standard with only minor changes. Supported is MPI version two and the implementations OpenMPI and MPICH2. In the future support for MPI version 3 and other implementations will follow.

Ausarbeitung – Link to the source code

• Empfehlenswerte Übersicht
• Vorlesung HR Folien
• Programmierung: C Fortran
• Debugging: GDB Valgrind
• Wikipedia MPI
• MPI Tutorial
• Git for Computer Scientists
• Heap vs. Stack Call Stack/Stackframe Stack im Detail auf Deutsch
• OpenMP Tutorials sind hier verlinkt
• OpenMP Tutorial GCC Doku zu OpenMP und Links zum Standard
• Links zu den MPI Standards
• Nice MPI Presentation
• MPI-2 Features als Folien
• MPI Function Man-Pages sehr detailliert mit Beispielen!
• MPI-2 Standard Beschreibung
• MPI-2 Beschreibung von Maui
• Pthread-Programmierung und schöne Erklärung von Threads
• 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
• SIMD Assembler Instruction Sets HTML , GCC Inline Assembly Guide HTML Assembly Language FPU
• Analyse: gprof Jumpshot Perf - Linux Counter + Kernel Analyse
• 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/

• 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.