====== 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:organisatorische_hinweise:praktikum|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 ===== * [[People:Alumni: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.