====== 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]]. Für diese Veranstaltung würden wir gerne individuelles Feedback zu den einzelnen Lehreinheiten sammeln, bitte füllt nach jeder Veranstaltung die [[http://goo.gl/5W8bj5|Google Umfrage]] aus. ===== 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, 2. Apr. 2014, 16:15 Uhr || || Vorbesprechung || Mi, 2. Apr. 2014, 16:15 Uhr || || Mailingliste || [[http://wr.informatik.uni-hamburg.de/listinfo/papo-14|PAPO-14]] || ===== Dozenten ===== * [[People:Alumni:Julian Kunkel]] (Ansprechpartner) * [[People:Alumni:Nathanael Hübbe]] ===== 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** (02.04.2014) - **Theoretische Grundlagen** (in der Vorlesungszeit) * //09.04.2014// - 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 * //16.04.2014// - 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}} * //30.04.2014// 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}} * //07.05.2014// - //Vorsicht, wir sind in Raum 023// -- Optimierung {{:teaching:sommersemester_2014:papo-optimierung.pdf|Folien}} * //14.05.2014// -- //Vorsicht, wir sind in Raum 023// -- SIMD-Programmierung {{:teaching:sommersemester_2012:papo-simd-programmierung.pdf|Folien}}{{:teaching:sommersemester_2013:papo-13-04-projekt.pdf|Projektinformationen und Leistungsanalyse}} * //21.05.2014// -- 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]] * //Übung:// Verschiedene Code-Fragmente parallelisieren und die Leistung bewerten. {{:teaching:sommersemester_2013:papo-13-03-openmp.pdf|Übungsblatt 3}} - **Projektbearbeitung** (je nach Absprache auch in der vorlesungsfreien Zeit) * Aufgabenstellung * //18.06.2014// -- Projektvorstellung und Präsentation der algorithmischen Lösung und Projektplan * //02.07.2014// -- Statustreffen -- Vorstellung der bisherigen Arbeiten und aufgetretene Probleme * //21.08.2014// Statustreffen -- Vorstellung der bisherigen Arbeiten und aufgetretene Probleme, erste Leistungsergebnisse * //24.09.2014// Abschlußtreffen -- Präsentation der Ergebnisse ===== Ergebnisse ===== ===== Ideenverbreitung ===== //Autoren: Arne Struck, Jonathan Werner// Dieses Projekt soll die Verbreitung und Konkurrenz von Ideen - im Sinne einer Weltanschauung oder eines kontroversen Themas - innerhalb einer begrenzten Population untersuchen und deren Mechanismen simulieren. Die Ideen sollen hierbei durch Kommunikation der Individuen und durch individuelle Entwick- lung veränderbar sein. {{:teaching:sommersemester_2014:papo-14-struck-ideas-report.pdf|Ausarbeitung}} -- {{:teaching:sommersemester_2014:papo-14-struck-ideas-presentation.pdf|Präsentation}} -- {{:teaching:sommersemester_2014:papo-14-struck-ideas.tar.gz|Source Code}} -- [[http://youtu.be/ALM7SeljPP4|Video]] ===== Raytracing ===== //Autoren: Alexander Koglin, Dennis Steinhoff// Wir haben verschiedene Parallelisierungsmethoden auf den von Kevin Beason entwickelten Pathtracer (eine Art Raytracer) smallpt (http://www.kevinbeason.com/smallpt/) angewendet. Dieser setzt sich u.a. aus einer for-Schleife für die Zeilen und einer für die Spaltenelemente zusammen. Die serielle Ausführung mit 48 Strahlen pro Pixel (sogenannte Samples) benötigt auf dem Cluster 102s. Zum einen haben wir eine Zeilenparallelisierung mit OpenMP vorgenommen, welche einen fast linearen Speedup aufweist. Zum anderen haben wir mit MPI eine Aufteilung nach Zeilenbereichen (Blöcken), eine abwechselnde Aufteilung der Zeilen und schließlich eine Master-Slave-Warteschleife, bei der die Slaves nach beendigter Abarbeitung der Aufgaben den Master nach weiteren Aufgaben (Zeilen) fragen, durchgeführt. Von den MPI-Möglichkeiten bietet die Methode der Master-Slave-Warteschleife den stärksten Speedup (wenn man nur die Slaves zählt), kurz darauf folgt die abwechselnde Zeilenaufteilung. Der Speedup ist nicht komplett linear mit zunehmender Prozessanzahl, aber durchaus zufriedenstellend: bei sechs Prozessen 5,5; bei zehn fast acht. Die Warteschleife ist im Allgemeinen ein sehr mächtiges Werkzeug. Alles in allem haben wir bei der Parallelisierung des Raytracing gewinnbringende Techniken wie beispielsweise die Erstellung einer benutzerdefinierten Reduktionsfunktion und eines Datentyps kennengelernt. {{:teaching:sommersemester_2014:papo14-steinhoff-koglin-ausarbeitung.pdf|Ausarbeitung}} -- {{:teaching:sommersemester_2014:papo14-steinhoff-koglin-praesentation.pdf|Präsentation}} -- {{:teaching:sommersemester_2014:papo14-steinhoff-koglin-sources.tar.gz|Source Code}} -- [[http://youtu.be/EcdoXcnCjPc|Video]] ===== Fluidsim ==== //Autor: Paul Bienkowski// This report describes my experiences of the development of a parallel cluster- enabled Simulation using MPI. My project in particular simulates fluid particles in two-dimensional space by a simple repulsion formula and collision with polygon meshes. The goal was to be able to simulate air flow around a wing shape and determine a possible uplift that was generated only by the particles collisions. {{:teaching:sommersemester_2014:papo14-bienkowski-fluidsim-ausarbeitung.pdf|Ausarbeitung}} -- {{:teaching:sommersemester_2014:papo14-bienkowski-fluidsim-presentation.pdf|Präsentation}} -- {{:teaching:sommersemester_2014:papo14-bienkowski-fluidsim.tar.gz|Source Code}} ===== Genetic Maze ===== //Authors: Sascha Schulz// {{:teaching:sommersemester_2014:papo14-schulz-praesentation.pdf|Präsentation}} -- {{:teaching:sommersemester_2014:papo14-schulz-ausarbeitung.pdf|Ausarbeitung}} -- {{:teaching:sommersemester_2014:papo14-schulz-sources.tgz|Source Code}} -- [[https://www.youtube.com/watch?v=zN1m3yy7uho|Video]] ===== SwarmFlocking ===== //Autoren: Fabian Besner, Dominik Lohmann, Jakob Rieck// Swarm behaviour is incredibly useful for a multitude of (scientific) applications, but certainly not easily computed. Based on Craig Reynolds paper "Flocks, Herds and Schools: A Distributed Behavioral Model" from 1987, we designed an application capable of simulating swarm behaviour in a three-dimensional world. Utilising the power of MPI, we were able to drastically reduce the calculation time. For more information please refer to the listed paper and the source code. {{:teaching:sommersemester_2014:papo14-besner-swarmflocking-report.pdf|Report}} -- {{:teaching:sommersemester_2014:papo14-besner-swarmflocking-presentation.pdf|Präsentation}} -- {{:teaching:sommersemester_2014:papo14-besner-swarmflocking.tar.gz|Source Code}} -- [[http://youtu.be/B44bKouHo0E|Video]] ===== 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.