Differences

This shows you the differences between two versions of the page.

Link to this comparison view

teaching:hamburg:sommersemester_2013:parallele_programmierung [2019-01-04 18:02] (current)
Line 1: Line 1:
 +====== 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 werden wird der Fokus auf der Praxis liegen.
 +
 +Beachten Sie auch unsere allgemeinen organisatorischen [[:​teaching:​hamburg:​organisatorisches:​start#​praktika|Hinweise zu Praktika]].
 +
 +===== Lernziel =====
 +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.
 +
 +===== 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.
 +
 +===== Daten der Veranstaltung =====
 +|| Zeit || Do 14:15-15:45 Uhr ||
 +|| Ort || [[http://​maps.google.com/​maps?​q=DKRZ,​+Bundesstra%C3%9Fe+45a,​+20146+Hamburg&​hl=de&​cd=2&​ei=BUxYS-GvKIuLOKaotbgJ&​sig2=Kv8CBjHeXm8lAVC3XxRrIQ&​ie=UTF8&​view=map&​cid=262423906154203330&​ved=0CBsQpQY&​hq=DKRZ,​+Bundesstra%C3%9Fe+45a,​+20146+Hamburg&​hnear=&​z=16&​iwloc=A|DKRZ]],​ Raum 034 ||
 +|| Beginn || Do 11.04.2012 ||
 +|| Vorbesprechung || Do 11.04.2012 ||
 +|| Mailingliste || [[http://​wr.informatik.uni-hamburg.de/​listinfo/​papo-13|PAPO-13]] ||
 +
 +===== Dozenten =====
 +
 +  * [[about:​people:​julian kunkel]] ​ (Ansprechpartner)
 +  * Nathanael Hübbe
 +  * Michaela Zimmer
 +
 +===== 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.
 +
 +Konkret vorgeschlagene Themen:
 +  * Astrophysikalische Berechnungen
 +  * Skat, Go oder Robotersimulation
 +  * Längste Wege Problem
 +  * Lösen großer logischer Formeln
 +  * Ein Algorithmus aus der Bioinformatik
 +===== Zeitplan und Materialien =====
 +  - **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. {{:​teaching:​sommersemester_2013:​papo-13-01-gdb-valgrind-mpi.pdf|Übungsblatt 1}}
 +      * Literatur zum Nachlesen: ​
 +        * Folien in der [[http://​wr.informatik.uni-hamburg.de/​_media/​teaching/​wintersemester_2011_2012/​hr-1112.pdf|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) {{:​teaching:​sommersemester_2010:​papo-01-gdb-valgrind-mpi-matrizen.tgz|Matrizen}}
 +    * //​25.04.2013//​ //​(VORSICHT,​ wir sind in Raum 207 (2 OG. DKRZ))// - Leistungsbewertung von Anwendungen,​ PGAS, MPI-IO - {{:​teaching:​sommersemester_2010:​papo-10-modell.pdf|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
 +        * [[http://​cnx.org/​content/​m20649/​latest/​| An introduction to PGAS programming languages]]
 +      * //Übung:// Amdahls Gesetz, Speedup-Diagramme bewerten, PGAS, MPI-I/O. {{:​teaching:​sommersemester_2013:​papo-13-uebung-02-mpi-io-pgas.pdf|Übungsblatt 2}}  {{:​teaching:​sommersemester_2010:​papo-juliamengen.tgz|Julia Mengen SourceCode}}
 +    * //​02.05.2013//​ - OpenMP, Programmanalyse Werkzeuge ​ [[http://​openmp.org/​wp/​resources/​|OpenMP Tutorials sind hier verlinkt]]
 +      * //Übung:// Verschiedene Code-Fragmente parallelisieren und die Leistung bewerten. {{:​teaching:​sommersemester_2013:​papo-13-03-openmp.pdf|Übungsblatt 3}}
 +    * //​16.05.2013//​ -- Optimierung
 +    * //​30.05.2013//​ -- SIMD-Programmierung {{:​teaching:​sommersemester_2012:​papo-simd-programmierung.pdf|Folien}}{{:​teaching:​sommersemester_2013:​papo-13-04-projekt.pdf|Projektinformationen und Leistungsanalyse}}
 +  - **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
 +
 +===== Ergebnisse =====
 +
 +==== Verkehrssimulation zur Stauerkennung auf Basis von OpenStreetMap Karten ====
 +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.
 +
 +{{:​teaching:​sommersemester_2013:​papo13-ellermannpoppingaheereman-verkehrssimulation-praesentation.pdf|Präsentation}} -- {{:​teaching:​sommersemester_2013:​papo13-ellermannpoppingaheereman-verkehrssimulation-ausarbeitung.pdf|Ausarbeitung}} -- {{:​teaching:​sommersemester_2013:​papo13-ellermannpoppingaheereman-verkehrssimulation-code.tar.gz|Source Code}} -- [[http://​youtu.be/​QPfPW1Vvq1s|Video Hamburg]] -- [[http://​youtu.be/​bh5K8h0DhjY|Video Kreisverkehr]]
 +
 +
 +==== Paraquest ====
 +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).
 +
 +{{:​teaching:​sommersemester_2013:​PAPO13-Alisa-Dammer-Sven-Hendrik-Haase-Praesentation.pdf|Präsentation}} -- {{:​teaching:​sommersemester_2013:​PAPO13-Alisa-Dammer-Sven-Hendrik-Haase-Ausarbeitung.pdf|Ausarbeitung}} -- {{:​teaching:​sommersemester_2013:​PAPO-13-Alisa-Dammer-Sven-Hendrik-Haase-Code.tar.gz|Source Code}}
 +
 +==== Solitaire-Schach ====
 +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 4x4 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 (3x7) möglich. Da es für ein 4x4 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.
 +
 +{{:​teaching:​sommersemester_2013:​PAPO13-Duwe-Zickler-Solitaire-Schach-Praesentation.pdf|Präsentation}} -- {{:​teaching:​sommersemester_2013:​PAPO13-Duwe-Zickler-Solitaire-Schach-Ausarbeitung.pdf|Ausarbeitung}} -- {{:​teaching:​sommersemester_2013:​PAPO13-Duwe-Zickler-Solitaire-Schach-Code.tar.gz|Source Code}}
 +
 +==== Infektsimulation ====
 +Authors: //Alexander Droste, Florian Flachsenberg//​
 +
 +Die Infektsimulation ermittelt wie sich Infektionskrankheiten innerhalb einer “Bevölkerung”
 +ausbreiten und verhalten. ​
 +
 +{{:​teaching:​sommersemester_2013:​PAPO13-Droste-Flachsenberg-Infektsimulation-Präsentation.pdf|Präsentation}} -- {{:​teaching:​sommersemester_2013:​PAPO13-Droste-Flachsenberg-Infektsimulation-Ausarbeitung.pdf|Ausarbeitung}} -- {{:​teaching:​sommersemester_2013:​PAPO13-Droste-Flachsenberg-Infektsimulation-Seriell-Code.tgz|Source Code (seriell)}} -- {{:​teaching:​sommersemester_2013:​PAPO13-Droste-Flachsenberg-Infektsimulation-Parallel-Code.tgz|Source Code (parallel)}} -- {{:​teaching:​sommersemester_2013:​PAPO13-Droste-Flachsenberg-Infektsimulation-Parallel-improved-collision-detection-BETA-Code.tgz|Source Code (better collission detection)}} -- [[http://​youtu.be/​nVXJWDtVBDw|Video]]
 +
 +==== The Predators'​ Guide ====
 +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.
 +
 +{{:​teaching:​sommersemester_2013:​PAPO13-Fasselt-Schmid-Korte-Predators-Guide-presentation.pdf|Präsentation}} -- {{:​teaching:​sommersemester_2013:​PAPO13-Fasselt-Schmid-Korte-Predators-Guide-Ausarbeitung.pdf|Ausarbeitung}} -- {{:​teaching:​sommersemester_2013:​PAPO13-Fasselt-Schmid-Korte-Predators-Guide-Code.tgz|Source Code}} -- [[http://​youtu.be/​0TlvmhYjw4w|Video]]
 +
 +==== Traveling Salesman ====
 +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.
 +
 +{{:​teaching:​sommersemester_2013:​papo-13-aleinikau-report.ppt|Bericht}} -- {{:​teaching:​sommersemester_2013:​papo-13-aleinikau-presentation.pdf|Präsentation}} -- {{:​teaching:​sommersemester_2013:​papo-13-aleinikau-code.tar.gz|Source Code}}
 +
 +==== PreyPredator ====
 +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.
 +
 +{{:​teaching:​sommersemester_2013:​paps-1213-betke-preypredatorsimulator-praesentation.pdf|Präsentation}} -- {{:​teaching:​sommersemester_2013:​paps-1213-betke-preypredatorsimulator-ausarbeitung.pdf|Ausarbeitung}} -- {{:​teaching:​sommersemester_2013:​proj_code.tar.gz|Source Code}}
 +
 +==== A Golang Wrapper for MPI ====
 +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.
 +
 +{{:​teaching:​sommersemester_2013:​paps-1213-beifuss_weging-golang_bindings_for_mpi-report.pdf|Ausarbeitung}} -- [[https://​github.com/​JohannWeging/​go-mpi|Link to the source code]]
 +
 +
 +
 +===== Literaturhinweise =====
 +==== Links ====
 +  * [[http://​www.compunity.org/​training/​tutorials/​2%20Basic_Concepts_Parallelization.pdf|Empfehlenswerte Übersicht]]
 +  * [[http://​wr.informatik.uni-hamburg.de/​_media/​teaching/​wintersemester_2011_2012/​hr-1112.pdf|Vorlesung HR Folien]]
 +  * Programmierung:​ [[http://​de.wikibooks.org/​wiki/​C-Programmierung|C]] [[http://​de.wikibooks.org/​wiki/​Fortran|Fortran]]
 +  * Debugging: [[http://​sourceware.org/​gdb/​current/​onlinedocs/​gdb/​|GDB]] [[http://​valgrind.org/​docs/​manual/​mc-manual.html|Valgrind]]
 +  * [[http://​de.wikipedia.org/​wiki/​Message_Passing_Interface|Wikipedia MPI]]
 +  * [[https://​computing.llnl.gov/​tutorials/​mpi/​|MPI Tutorial]]
 +  * [[http://​eagain.net/​articles/​git-for-computer-scientists/​|Git for Computer Scientists]]
 +  * [[http://​de.wikipedia.org/​wiki/​Dynamischer_Speicher|Heap vs. Stack]] [[http://​en.wikipedia.org/​wiki/​Call_stack|Call Stack/​Stackframe]] [[http://​www.a-m-i.de/​tips/​stack/​stack.php| Stack im Detail auf Deutsch]]
 +  * [[http://​openmp.org/​wp/​resources/​|OpenMP Tutorials sind hier verlinkt]]
 +  * [[https://​computing.llnl.gov/​tutorials/​openMP/​|OpenMP Tutorial]] [[http://​gcc.gnu.org/​wiki/​openmp|GCC Doku zu OpenMP und Links zum Standard]]
 +  * [[http://​www.mpi-forum.org/​docs/​docs.html|Links zu den MPI Standards]]
 +  * [[https://​computing.llnl.gov/​tutorials/​mpi_advanced/​DavidCronkSlides.pdf|Nice MPI Presentation]]
 +  * [[http://​cs.boisestate.edu/​~amit/​teaching/​530/​notes/​mpi-advanced.pdf|MPI-2 Features als Folien]]
 +  * [[http://​mpi.deino.net/​mpi_functions/​|MPI Function Man-Pages sehr detailliert mit Beispielen!]]
 +  * [[http://​www.mpi-forum.org/​docs/​mpi21-report/​mpi21-report.htm#​Node0|MPI-2 Standard Beschreibung]]
 +  * [[http://​www.mhpcc.edu/​training/​workshop2/​mpi_io/​MAIN.html|MPI-2 Beschreibung von Maui]]
 +  * [[https://​computing.llnl.gov/​tutorials/​pthreads/​|Pthread-Programmierung und schöne Erklärung von Threads]]
 +  * Interne Verarbeitung von OpenMP und Auto-Parallisierung im GCC (von 2006) - [[http://​www.airs.com/​dnovillo/​Papers/​gcc2006.pdf|OpenMP and automatic parallelization in GCC]]
 +  * GCC Features um parallel zu programmieren,​ auch eine schöne kurze Übersicht über die parallele Programmierung [[http://​www.airs.com/​dnovillo/​Papers/​rhs2006.pdf|Parallel programming with GCC]]
 +  * GCC Optimierungsflags [[http://​gcc.gnu.org/​onlinedocs/​gcc/​Optimize-Options.html|GCC Handbuch HTML]]
 +  * SIMD Assembler Instruction Sets [[http://​softpixel.com/​~cwright/​programming/​simd/​|HTML]] , GCC Inline Assembly Guide [[http://​www.ibiblio.org/​gferg/​ldp/​GCC-Inline-Assembly-HOWTO.html|HTML]] [[http://​www.roma1.infn.it/​SIC/​_OLD_documentazione/​unix/​migr/​digital-unix-doc/​DOCUMENTATION/​HTML/​AA-PS31D-TET1_html/​asm5.html|Assembly Language FPU]]
 +  * Analyse: [[http://​www.cs.utah.edu/​dept/​old/​texinfo/​as/​gprof_toc.html|gprof]] [[http://​www.mcs.anl.gov/​research/​projects/​perfvis/​software/​viewers/​index.htm|Jumpshot]] [[https://​perf.wiki.kernel.org/​index.php/​Main_Page|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/​]]
 +
 +==== 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. ​
 +  * [[http://​mitpress.mit.edu/​book-home.tcl?​isbn=0262571234|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. ​