teaching:sommersemester_2014:parallele_programmierung

Differences

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

Link to this comparison view

teaching:sommersemester_2014:parallele_programmierung [2018-05-09 17:25] (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:Organisatorische Hinweise#praktika|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: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. 
teaching/sommersemester_2014/parallele_programmierung.txt · Last modified: 2018-05-09 17:25 (external edit)