Differences

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

Link to this comparison view

teaching:hamburg:sommersemester_2015: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 || Mittwoch, 16--18 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 ||  Mi, 8. Apr. 2015, 16:15 Uhr ||
 +|| Vorbesprechung || Mi, 8. Apr. 2015, 16:15 Uhr ||
 +|| Mailingliste || [[http://​wr.informatik.uni-hamburg.de/​listinfo/​papo-15|PAPO-15]] ||
 +
 +===== Dozenten =====
 +
 +  * [[about:​people:​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** (08.04.2015),​ Architekturen,​ Programmierkonzepte von OpenMP und MPI, Gebietszerlegung und Aufgabenteilung.
 +  - **Theoretische Grundlagen** (in der Vorlesungszeit)
 +    * //​15.04.2015//​ - 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. {{:​teaching:​sommersemester_2015:​papo-15-01-cluster-git-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, Threads: 304-381
 +        * Versionsverwaltung:​ http://​www.wr.informatik.uni-hamburg.de/​teaching/​wintersemester_2011_2012/​git-workshop
 +    * //​22.04.2015//​ - 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. {{:​teaching:​sommersemester_2015:​papo-15-02-gdb-valgrind.pdf|Übungsblatt 2}} {{:​teaching:​sommersemester_2010:​papo-01-gdb-valgrind-mpi-matrizen.tgz|Matrizen}}
 +      * [[https://​sites.google.com/​a/​case.edu/​hpc-upgraded-cluster/​home/​important-notes-for-new-users/​debugging-segmentation-faults|Debugging Segmantation Faults]]
 +      * Debugging: [[http://​sourceware.org/​gdb/​current/​onlinedocs/​gdb/​|GDB]] [[http://​valgrind.org/​docs/​manual/​mc-manual.html|Valgrind]]
 +      * [[http://​en.wikipedia.org/​wiki/​Executable_and_Linkable_Format|Executables]]
 +      * [[https://​computing.llnl.gov/​tutorials/​mpi/​|MPI Tutorial]]
 +      * [[http://​wr.informatik.uni-hamburg.de/​_media/​teaching/​wintersemester_2011_2012/​hr-1112.pdf|Vorlesung]] MPI: 251-277
 +    * //​29.04.2015//​ Leistungsbewertung von Anwendungen,​ PGAS - {{:​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
 +        * https://​www.sharcnet.ca/​help/​index.php/​Measuring_Parallel_Scaling_Performance
 +        * [[http://​cnx.org/​content/​m20649/​latest/​| An introduction to PGAS programming languages]]
 +      * //Übung:// Amdahls Gesetz, Speedup-Diagramme bewerten, Projekt-Aufgabenstellung.{{:​teaching:​sommersemester_2015:​papo-15-03-mpi-ip-pgas.pdf|Übungsblatt 3}}  - {{:​teaching:​sommersemester_2015:​papo15-mpi-speedup.zip|MPI Program zur Speedup-Bestimmung}} {{:​teaching:​sommersemester_2010:​papo-juliamengen.tgz|Julia Mengen SourceCode}} ​
 +    * //​05.05.2015//​ -- **Termin fällt aus!!!**
 +    * //​12.05.2015//​ -- OpenMP, Programmanalyse Werkzeuge [[http://​openmp.org/​mp-documents/​ntu-vanderpas.pdf|Tolle Präsentation -- OpenMP and Performance]] [[http://​openmp.org/​sc13/​sc13.tasking.ruud.pdf|Tasking Präsentation]] [[http://​openmp.org/​wp/​resources/​|OpenMP Tutorials sind hier verlinkt]]
 +    * {{:​teaching:​sommersemester_2015:​papo-15-vampir-notes.pdf|Folien zur Leistungsanalyse mit Vampir}}
 +      * //Übung:// OpenMP, Leistungsanalyse,​ Verschiedene Code-Fragmente parallelisieren und die Leistung bewerten. ​ {{:​teaching:​sommersemester_2015:​papo-15-03-openmp.pdf|Übungsblatt 4}}
 +  - **Projektbearbeitung** (je nach Absprache auch in der vorlesungsfreien Zeit)
 +    * Hinweise zur Projektbearbeitung {{:​teaching:​sommersemester_2015:​papo-15-04-projekt.pdf|Übungsblatt 5}}
 +    * //​03.06.2015// ​ -- Projektvorstellung und Präsentation der algorithmischen Lösung und Projektplan
 +    * //​08.07.2015//​ Statustreffen -- Vorstellung der bisherigen Arbeiten und aufgetretene Probleme
 +    * //​05.08.2015//​ Statustreffen -- Vorstellung der bisherigen Arbeiten und aufgetretene Probleme, erste Leistungsergebnisse
 +    * //​09.09.2015//​ Abschlußtreffen -- Präsentation der Ergebnisse
 +
 +===== Ergebnisse =====
 +
 +==== Conway'​s Game of Life in 3D ====
 +
 +//Autoren: Elena Bergmann, Tobias Wesseler//
 +
 +Conway'​s Game of Life wurde 1970 von John Horton Conway entworfen und stellt einen
 +zweidimensionalen zellulären Automaten dar. Das Spielfeld besteht aus einzelnen Zellen, die
 +quadratisch angeordnet sind und zwischen zwei Zuständen wechseln können. Lebendige Zellen
 +sind aktiv und tote Zellen inaktiv. Die Regeln beschreiben,​ wann eine tote Zelle lebendig wird,
 +wann eine lebendige Zelle stirbt und wann sie weiterlebt.
 +
 +Nachdem im zweidimensionalen Spielfeld schon statische, oszillierende,​ sich bewegende,
 +erzeugende und vernichtende Objekte gefunden wurden, bleibt im dreidimensionalen Bereich
 +noch weiteres zu entdecken. Wir werden daher dreidimensionale Spielfelder verarbeiten und das
 +ganze mit MPI parallelisieren.
 +
 +{{:​teaching:​sommersemester_2015:​papo-15-parcol-ausarbeitung.pdf|Ausarbeitung}} -- {{:​teaching:​sommersemester_2015:​papo-15-parcol-presentation.pdf|Präsentation}} -- {{:​teaching:​sommersemester_2015:​papo-15-parcol-source.tar.gz|Source}}
 +-- [[https://​github.com/​Toastgeraet/​CGoL|Git Repository]]
 +
 +==== NBody Sonnensystem ====
 +
 +//Autoren: Oliver Heidmann, Tronje Krabbe //
 +
 +Die Idee, die unserem Projekt zugrunde liegt, ist relativ simpel zu formulieren:​
 +Wir wollen ein Sonnensystem simulieren. In diesem System sollten die enthalte-
 +nen Objekte realistisch miteinander interagieren. Alle Objekte beinflussen sich
 +durch die Gravitation und durch physischen Kontakt, also Kollisionen.
 +
 +{{:​teaching:​sommersemester_2015:​papo-15-nbody-ausarbeitung.pdf|Ausarbeitung}} -- {{:​teaching:​sommersemester_2015:​papo-15-nbody-presentation.pdf|Präsentation}} ​ -- {{:​teaching:​sommersemester_2015:​papo-15-nbody-source.tgz|Source}} -- [[https://​www.youtube.com/​watch?​v=ODZCdPfrr2E|Video]]
 +
 +==== Neugengo ====
 +
 +//Autoren: Armin Schaare, Theresa Eimer, Lennart Braun//
 +
 +In diesem Projekt wurden eigens implementierte,​ künstliche neuronale Netze trainiert,
 +das asiatische Brettspiel Go spielen zu können. Da das Training enorm vieler Kalkula-
 +tionen bedarf, haben wir uns für die Umsetzung auf einem Rechencluster mit entspre-
 +chenden Parallelisierungsschemata auseinander gesetzt.
 +
 +{{:​teaching:​sommersemester_2015:​papo-15-neurengo-ausarbeitung.pdf|Ausarbeitung}} -- {{:​teaching:​sommersemester_2015:​papo-15-neurengo-presentation.pdf|Präsentation}} -- {{:​teaching:​sommersemester_2015:​papo-15-neugengo.tar.gz|Source}}
 +
 +==== Objekterkennung beim Tischkicker ====
 +
 +//Autoren: Michael Straßberger,​ Philip Gawehn //
 +
 +Tischkicker ist ein beliebter Sport. Schnelligkeiten,​ Geschick, Konzentration und viele
 +weitere Eigenschaften machen ihn oft unvorhersehbar und spannend. Haufig ist der Ball
 +durch seine hohe Geschwindigkeit mit dem bloßen Auge nicht mehr zu erkennen. Unter
 +anderem aus diesem Grund haben wir uns als Aufgabe gestellt den Ball mit Hilfe einer
 +Kamera verfolgen (tracken) zu können.
 +
 +{{:​teaching:​sommersemester_2015:​papo-15-tischkicker-ausarbeitung.pdf|Ausarbeitung}} -- {{:​teaching:​sommersemester_2015:​papo-15-tischkicker-presentation.pdf|Präsentation}} -- {{:​teaching:​sommersemester_2015:​papo-15-tischkicker-source.tar.gz|Source}}
 +
 +==== Platzierung von Fluggästen ====
 +
 +//Autoren: Frederik Wille, Alexander Timmermann //
 +
 +Die Problemstellung bestand im Wesentlichen aus der Erstellung, Im-
 +plementation und anschließenden Parallelisierung eines Algorithmus,​ der
 +Fluggäste auf Flüge bzw. dann auch auf Sitzplätze im gewählten Flug-
 +zeug verteilt.
 +
 +{{:​teaching:​sommersemester_2015:​papo-15-placement-ausarbeitung.pdf|Ausarbeitung}} -- {{:​teaching:​sommersemester_2015:​papo-15-placement-presentation.pdf|Präsentation}} -- {{:​teaching:​sommersemester_2015:​papo-15-placement-source.tar.gz|Source}}
 + 
 +
 +==== VampireSim ===
 +
 +// Autoren: Jun-Patrick Raabe, Kolya Feierabend //
 +
 +Dieses Projekt zielt darauf ab, die Entwicklung der Bevölkerungsgrößen in einer fiktiven Welt
 +mithilfe einer Simulation darzustellen. Die Bevölkerungsgruppen Mensch, Vampirjäger und
 +Blade kämpfen gegen die Vampire ums Überleben. Durch die Möglichkeit,​ verschiedene
 +Parameter, wie zum Beispiel die einzelnen Bevölkerungsgrößen,​ zu Simulationsbeginn
 +anzupassen, können viele vollkommen unabhängige Resultate erzielt werden.
 +
 +{{:​teaching:​sommersemester_2015:​papo-15-vampire-ausarbeitung.pdf|Ausarbeitung}} -- {{:​teaching:​sommersemester_2015:​papo-15-vampire-presentation.pdf|Präsentation}} -- {{:​teaching:​sommersemester_2015:​papo-15-vampire-source.tar.gz|SourceCode}} -- [[https://​www.youtube.com/​watch?​v=Z_yo-qgYOYc&​feature=youtu.be|Video]]
 +
 +
 +==== SoundSim ====
 +
 +// Autoren: Frank Röder, Julius Plehn //
 +
 +Da es sich in der Realität als sehr unpraktisch erweist, wenn man Lautsprecher in einem großen Raum mehrmals umplatzieren muss, durch wiederholtes
 +ausprobieren,​ hinhören und erneutes umstellen nicht gerade schnell zu einem
 +guten Ergebnis kommt, haben wir uns als Ziel gesetzt ein Modell zur Simulation von Schall in einem 3-dimensionalen Raum zu entwicklen.
 +
 +{{:​teaching:​sommersemester_2015:​papo-15-soundsim-ausarbeitung.pdf|Ausarbeitung}} -- {{:​teaching:​sommersemester_2015:​papo-15-soundsim-präsentation.pdf|Präsentation}}-- {{:​teaching:​sommersemester_2015:​papo-15-soundsim-sourcecode.tar.gz|Source}} -- [[https://​www.youtube.com/​watch?​v=sj-BHK7s7Dk&​authuser=1|Video]]
 +===== Literaturhinweise =====
 +==== Links ====
 +  * [[http://​pages.tacc.utexas.edu/​~eijkhout/​Articles/​EijkhoutIntroToHPC.pdf|Introduction to HPC (BUCH!)]]
 +  * [[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]]
 +  * [[http://​en.wikipedia.org/​wiki/​Executable_and_Linkable_Format|Executables]]
 +  * [[https://​sites.google.com/​a/​case.edu/​hpc-upgraded-cluster/​home/​important-notes-for-new-users/​debugging-segmentation-faults|Debugging Segmantation Faults]]
 +  * [[https://​computing.llnl.gov/​tutorials/​mpi_advanced/​DavidCronkSlides.pdf|Nice MPI Presentation]]
 +  * [[http://​mpi.deino.net/​mpi_functions/​|MPI Function Man-Pages sehr detailliert mit Beispielen!]]
 +  * [[http://​www.mpi-forum.org/​docs/​mpi-2.2/​mpi22-report/​mpi22-report.htm|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. ​