teaching:sommersemester_2016:parallele_programmierung

Differences

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

Link to this comparison view

teaching:sommersemester_2016: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 wird der Fokus auf der Praxis liegen.
 +
 +Die Veranstaltung wird zum Teil auf Englisch gehalten.
 +
 +Beachten Sie auch unsere allgemeinen organisatorischen [[:​Teaching:​Organisatorische Hinweise#​praktika|Hinweise zu Praktika]].
 +
 +===== Lernziel =====
 +Ziel des Praktikums ist es, die wichtigsten Parallelisierungskonzepte kennen zu lernen und Problemstellungen selbstständig 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.
 +
 +Die Veranstaltung wird auf Englisch stattfinden.
 +===== Daten der Veranstaltung =====
 +|| Zeit || Mittwoch, 16--18 Uhr ||
 +|| Ort || [[https://​www.uni-hamburg.de/​onTEAM/​campus/​index.html?​loc=i12340438|DKRZ]],​ Raum 034 ||
 +|| Beginn ||  Mi, 6. Apr. 2016, 16:15 Uhr ||
 +|| Vorbesprechung || Mi, 6. Apr. 2016, 16:15 Uhr ||
 +|| Mailingliste || [[https://​wr.informatik.uni-hamburg.de/​listinfo/​papo-16|PAPO-16]] ||
 +
 +===== Dozenten =====
 +
 +  * [[People:​Alumni:​Julian Kunkel]] ​ (Ansprechpartner)
 +  * [[People:​Nabeeh Jumah]] ​
 +===== 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** (06.04.2016),​ Beschreibung des Praktikums, Architekturen,​ Programmierkonzepte von OpenMP und MPI, Gebietszerlegung und Aufgabenteilung.
 +  - **Theoretische Grundlagen** (in der Vorlesungszeit)
 +    * //​13.04.2016//​ - 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_2016:​papo-16-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
 +        * [[http://​www.wr.informatik.uni-hamburg.de/​teaching/​wintersemester_2011_2012/​git-workshop|Versionsverwaltung]]
 +    * //​20.04.2016//​ - 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_2016:​papo-16-02-gdb-valgrind.pdf|Übungsblatt 2}} 
 +      * [[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
 +    * //​27.04.2016//​** Der Termin fällt aus.**
 +    * //​04.05.2016//​ 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_2016:​papo-16-03-mpi-ip-pgas.pdf|Übungsblatt 3}}  ​
 +    * //​11.05.2016//​ -- 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_2016:​papo-16-03-openmp.pdf|Übungsblatt 4}}
 +    *  //​25.05.2016//​ ** Wir sind in R207 ** -- Processor-level parallelism,​ intrinsics in C, low-level memory management (Nabeeh Jum'​ah)
 +      * {{:​teaching:​sommersemester_2016:​papo_simd.pdf|SIMD}}
 +      * {{:​teaching:​sommersemester_2016:​papoalignment.c.pdf|Alignment}}
 +      * {{:​teaching:​sommersemester_2016:​papointrinsics4badd.c.pdf|Intrinsics for 4-byte integer addition, 4 integers at once}}
 +      * {{:​teaching:​sommersemester_2016:​papointrinsics1badd.c.pdf|Intrinsics for 1-byte integer addition, 16 integers at once}}
 +      * {{:​teaching:​sommersemester_2016:​papoassembly.c.pdf|Assembly}}
 +  - **Projektbearbeitung** (je nach Absprache auch in der vorlesungsfreien Zeit)
 +    * Hinweise zur Projektbearbeitung {{:​teaching:​sommersemester_2016:​papo-16-04-projekt.pdf|Hinweise zur Projektarbeit}}
 +    * //​08.06.2016// ​ -- Projektvorstellung und Präsentation der algorithmischen Lösung und Projektplan
 +    * //​13.07.2016//​ Statustreffen -- Vorstellung der bisherigen Arbeiten und aufgetretene Probleme
 +    * //​17.08.2016//​ Statustreffen -- Vorstellung der bisherigen Arbeiten und aufgetretene Probleme, erste Leistungsergebnisse
 +    * //​21.09.2016//​ Abschlusstreffen -- Präsentation der Ergebnisse
 +===== Ergebnisse =====
 +
 +
 +==== Emissions-Simulation ====
 +Autor: **Jonas Tietz**
 +
 +In diesen Projekt habe ich versucht Emissionen im zweidimenstionalen Raum zu simulieren.
 +Dafür habe ich statt einzelne Partikel zu simulieren alles in Zellen unterteilt.
 +
 +{{ :​teaching:​sommersemester_2016:​papo-16-tietz-presentation.pdf|Präsentation}} -- {{ :​teaching:​sommersemester_2016:​papo-16-tietz-report.pdf|Bericht}} -- {{ :​teaching:​sommersemester_2016:​papo-16-tietz-code.zip|Code}}
 +===== Literaturhinweise =====
 +==== Links ====
 +  * [[https://​try.github.io/​levels/​1/​challenges/​1|Git online kurs]]
 +  * [[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/​]]
 +  *  What Every Computer Scientist Should Know About Floating-Point Arithmetic ​ http://​docs.oracle.com/​cd/​E19957-01/​806-3568/​ncg_goldberg.html
 +
 +==== 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_2016/parallele_programmierung.txt · Last modified: 2018-05-09 17:25 (external edit)