Differences

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

Link to this comparison view

teaching:hamburg:sommersemester_2012: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 05.04.2012 ||
 +|| Vorbesprechung || Do 05.04.2012 ||
 +|| Mailingliste || [[http://​wr.informatik.uni-hamburg.de/​listinfo/​papo-12|PAPO-12]] ||
 +
 +===== Dozenten =====
 +
 +  * Thomas Ludwig
 +  * [[about:​people:​julian kunkel]]
 +  * Petra Nerge
 +  * 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.
 +
 +Konkret vorgeschlagene Themen:
 +  * Astrophysikalische Berechnungen
 +  * Mastermind
 +  * Skat, Go oder Robotersimulation
 +  * Längste Wege Problem
 +  * Lösen großer logischer Formeln
 +  * Gezeitenmodell
 +  * Ein Algorithmus aus der Bioinformatik
 +===== Zeitplan und Materialien =====
 +  - **Theoretische Grundlagen** (in der Vorlesungszeit)
 +    * //​12.04.2012//​ - 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.
 +    * //​19.04.2012//​ - Parallelisierung von Anwendungen,​ Einführung in Debugging, Speichermanagment von C/Fortran, MPI, Individuelle und kollektive Operationen im Detail, nicht-blockierende Aufrufe
 +      * //Übung:// einfache Probleme selbständig parallelisieren. Werkzeuge: DDT+Valgrind. {{:​teaching:​sommersemester_2010:​papo-01-gdb-valgrind-mpi.pdf|Übungsblatt 1}} {{:​teaching:​sommersemester_2010:​papo-01-gdb-valgrind-mpi-matrizen.tgz|Matrizen}}
 +    * //​26.04.2012//​ - Leistungsbewertung von Anwendungen,​ PGAS, MPI-I/​O ​ - {{:​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, ...
 +      * //Übung:// Amdahls Gesetz, Speedup-Diagramme bewerten, PGAS, MPI-I/O. {{:​teaching:​sommersemester_2010:​papo-uebung-02-mpi-io-pgas.pdf|Übungsblatt 2}}  {{:​teaching:​sommersemester_2010:​papo-juliamengen.tgz|Julia Mengen SourceCode}}{{:​teaching:​sommersemester_2010:​papo-ioantriebsdaten.tgz|Antriebsdaten + SoureCode}}
 +    * //​03.05.2012//​ - OpenMP, Programmanalyse Werkzeuge ​ [[http://​openmp.org/​wp/​resources/​|OpenMP Tutorials sind hier verlinkt]]
 +      * //Übung:// Verschiedene Code-Fragmente parallelisieren und die Leistung bewerten. {{:​teaching:​sommersemester_2010:​papo-uebung-03-openmp.pdf|Übungsblatt 3}}
 +    * //​10.05.2012//​ -- SIMD-Programmierung {{:​teaching:​sommersemester_2012:​papo-simd-programmierung.pdf|Folien}}
 +    * //​24.05.2012//​ -- Leistungsanalyse
 +      * //Übung:// Verschiedene Code-Fragmente parallelisieren und die Leistung bewerten. Sunshot bzw. Jumpshot zur Analyse verwenden. Programm mit Hardware-Countern laufen lassen und bewerten.
 +  - **Projektbearbeitung** (je nach Absprache auch in der vorlesungsfreien Zeit)
 +    * //​14.06.2012// ​ -- Projektvorstellung und Präsentation der algorithmischen Lösung und Projektplan
 +    * //​28.06.2012// ​ -- Statustreffen -- Vorstellung der bisherigen Arbeiten und aufgetretene Probleme
 +    * Statustreffen -- Vorstellung der bisherigen Arbeiten und aufgetretene Probleme, erste Leistungsergebnisse
 +    * Präsentation der Ergebnisse
 +
 +===== Ergebnisse =====
 +  *  Daisyworld -- //Christoph Bockhahn, ​ Max Hänze// -- {{:​teaching:​sommersemester_2012:​papo-12-daisyworld-presentation.pptx|Präsentation}} -- {{:​teaching:​sommersemester_2012:​papo-12-daisyworld-ausarbeitung.pdf|Ausarbeitung}} -- {{:​teaching:​sommersemester_2012:​papo-12-daisyworld-sourcecode.tgz|Source Code}} ​
 +  * Drop-7 -- //Jakob Lüttgau// -- {{:​teaching:​sommersemester_2012:​papo-12-drop-7-presentation.pdf|Präsentation}} -- {{:​teaching:​sommersemester_2012:​papo-12-drop-7-ausarbeitung.pdf|Ausarbeitung}} -- {{:​teaching:​sommersemester_2012:​papo-12-drop-7-sourcecode.tgz|Source Code}}
 +  *  Populationsdynamik -- //Nils Petersen// -- {{:​teaching:​sommersemester_2012:​papo-12-popolutationsdynamik-presentation.pdf|Präsentation}} -- {{:​teaching:​sommersemester_2012:​papo-12-popolutationsdynamik-ausarbeitung.pdf|Ausarbeitung}} -- {{:​teaching:​sommersemester_2012:​papo-12-popolutationsdynamik-sourcecode.tgz|Source Code}}
 +  *  Ameisensimuation -- //Christian Peter, Dominik Rupp// -- {{:​teaching:​sommersemester_2012:​papo-12-ants-presentation.pdf|Präsentation}} -- {{:​teaching:​sommersemester_2012:​papo-12-ants-ausarbeitung.pdf|Ausarbeitung}} -- {{:​teaching:​sommersemester_2012:​papo-12-ants-sourcecode.tgz|Source Code}} ​ -- {{:​teaching:​sommersemester_2012:​papo-12-ants-video.mkv|Video}}
 +  *  Seiler Tide Model -- //Anna Fuchs// -- {{:​teaching:​sommersemester_2012:​papo-12-fuchs-gezeitensimulation-praesentation.pdf|Präsentation}} -- {{:​teaching:​sommersemester_2012:​papo-12-fuchs-gezeitensimulation-ausarbeitung.pdf|Ausarbeitung}} ​ -- {{:​teaching:​sommersemester_2012:​papo-12-fuchs-gezeitensimulation-sourcecode.tgz|Source Code}}
 +  * Outbreak -- //Hajo Möller// -- {{:​teaching:​sommersemester_2012:​papo-12-outbreak-presentation.pdf|Präsentation}} -- {{:​teaching:​sommersemester_2012:​papo-12-outbreak-auswertung.pdf|Auswertung}} -- {{:​teaching:​sommersemester_2012:​papo-12-outbreak-sourcecode.tgz|Source Code}} -- {{http://​dasjoe.de/​tmp/​outbreak_200.mp4|Video}} ​
 +==== Mastermind ====
 +Authors: //Fabian Fiedler, Nicole Tänzer//
 +
 +This program calculates for each of the 1296 possible Mastermind colour codes how many steps the algorithm spends for guessing the right code. The algorithm was described by Donald Knuth in his Work "The Computer as Master Mind". You can use the program to identify the codes, that are easy to guess and the codes, wich are difficult.
 +
 +{{:​teaching:​sommersemester_2012:​papo-12-mastermind-presentation.pdf|Präsentation}} -- {{papo-12-mastermind-ausarbeitung.pdf|Ausarbeitung}} -- {{:​teaching:​sommersemester_2012:​papo-12-mastermind-sourcecode.tgz|Source Code}}
 +
 +==== Fish & Shark ====
 +Authors: //  Sebastian Rothe, Alexander Lambertz//
 +
 +This simulation is a modification of a Wator Theory. ​
 +It simulates fishs, sharks and plankton. ​
 +Fishs die and respawn after a certain period of time. 
 +Sharks eat fishs and duplicate themselves. ​   ​
 +Plankton is just growing all the time. 
 +This simulation was parallized by using the MPI Framework.
 +
 +{{:​teaching:​sommersemester_2012:​papo-12-fishShark-presentation.pdf|Präsentation}} -- {{:​teaching:​sommersemester_2012:​papo-12-fishShark-ausarbeitung.pdf|Ausarbeitung}} -- {{:​teaching:​sommersemester_2012:​papo-12-fishShark-sourcecode.tgz|Source Code}}
 +
 + 
 +===== Literaturhinweise =====
 +==== Links ====
 +  * [[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/​mpi2_1/​index.htm|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. ​