Seminar Paralleles Rechnen

In dem Seminar sollen aktuelle Themen aus dem Bereich High Performance Computing bearbeitet werden. Dabei wird ein Schwerpunkt auf selbständiges praktisches Arbeiten gelegt. Die Themen werden teilweise in Kooperation mit wissenschaftlichen Einrichtungen wie beispielsweise dem GeoForschungszentrum (GFZ) und dem Potsdamer Institut für Klimafolgenforschung (PIK) bzw. Anwendern aus den naturwissenschaftlichen Instituten der Universität Potsdam gestellt.

Veranstalter

Prof. Dr. Bettina Schnor, Institut für Informatik
Steffen Christgau, Institut für Informatik

Ort/Termine

Das Seminar wird Mittwoch von 16:00 Uhr bis 20:00 Uhr im Raum 03.04.1.03 stattfinden.

Materialien

• Vorlesungsfolien
• Übungsfolien
• zusätzliches Material

Anforderungen

• Selbstständige Einarbeitung in die Aufgabenstellung und Absprachen mit den Betreuern
• Teilnahme an den Zwischenstandstreffen und Berichte zum aktuellen Zwischenstand bzw. individuelle Vorträge
• Abschlussvortrag
• Schriftliche Ausarbeitung zwei Wochen nach Abschlussvortrag (doppelseitig ausgedruckt)

Themenliste

1. MPI-Backend für "odeint"
   Bereich: MPI, Parallelisierung
   Gewöhnliche Differentialgleichen spielen eine wichtige Rolle in vielen Wissenschafts- und Ingenieursdisziplinen. In diesem Praktikum soll ein MPI-Backend für odeint - eine moderne und generische C++ Bibliothek zum Lösen von gewöhnlichen Differentialgleichungen entwickelt werden und deren Performance und Anwendungsbereiche mit existierenden Lösungen (OpenCL, Cuda, OpenMP) verglichen werden.
   Betreuer: Karsten Ahnert
2. Leistungsanalyse von pCRASH
   Bereich: Leistungsanalyse, Parallelisierung
   pCRASH ist eine parallele Anwendung zur Simulation der ersten Sterne im Universum. Grundlage des Programms ist die Berechnung von Strahlausbreitungen. Zu Beginn der Simulation konzentriert sich die Strahlausbreitung und damit die Berechnung auf einen kleinen Bereich des simulierten Universums. Erst im Verlauf der Simulation verteilen sich die Strahlen auf das gesamte berechnete Gebiet. Bei einer statischen Zerlegung der Berechnung ergibt sich somit im zeitlichen Verlauf eine unausgewogene Last für die einzelnen Prozesse. Perspektivisch soll in das Programm eine dynamische Lastverteilung integriert werden. Im Rahmen des Praktikums sollen jedoch zunächst Zeitmetriken für verschiedene Stufen der Berechnung und verschiedene physikalische Parameter sowohl mit entsprechenden Analysetools (Scalasca, Intel Trace Analyzer, Jumpshot, o.ä.) als auch durch die vorzunehmende Instrumentierung des Codes bestimmt werden.
   Betreuer: Adrian Partl, Astrophysikalisches Institut Potsdam (AIP)
   Bearbeitet von Hannes S.
3. Paralleler Dateizugriff für pCRASH
   Bereich: MPI, Parallelisierung
   pCRASH (vgl. Thema 3) verwendet zur Zeit einen zentralen Ansatz für das Einlesen und Schreiben der benötigen bzw. erzeugten Daten. Dieser Ansatz funktioniert in kleineren Clustersystemen gut, skaliert allerdings nicht in großen Umgebungen und großen Datenmengen. Jedoch sind im MPI-Standard Methoden zur parallelen Arbeit auf Dateien definiert (vgl. Kapitel 13, MPI 2.2). Diese bieten die Möglichkeit, den bisher verwendeten zentralen Ansatz durch eine verteilte Lösung zu ersetzen. Im Praktikum soll ein entsprechender Ansatz auf Basis der MPI-I/O-Routinen entwickelt und umgesetzt werden.
   Betreuer: Adrian Partl, Astrophysikalisches Institut Potsdam (AIP)
   Bearbeitet von Sebastian T.
4. Parallelisierung mit k-d-Bäumen
   Bereich: Bereich: MPI, Parallelisierung
   Betreuer:Arman Khalatyan, Astrophysikalisches Institut Potsdam (AIP)
   Bearbeitet von Patrick W. und Sebastian R.
5. Determinisierung von endlichen Automaten
   Bereich: Parallelisierung
   Die Determinisierung (gewichteter) endlicher Automaten ist eine wichtige Operation, nicht nur zur Erhöhung des Durchsatzes von Systemen, die auf endlichen Automaten basieren, sondern z.B. auch Voraussetzung für die Berechnung des Komplements einer regulären Sprachen oder die Entscheidung, ob zwei endliche Automaten die gleiche Sprache akzeptieren. Grundlage der Automatendeterminisierung ist die Teilmengenkonstruktion, d.h. ein Zustand des deterministischen Automaten ist eine Menge von Zuständen des gegebenen nicht-deterministischen Automaten. Bisher gibt es noch nicht allzuviele Versuche, parallele Algorithmen für die Automatendeterminisierung zu finden. Dies liegt inhärent daran, dass endlichen Automaten eigentlich Graphen zugrunde liegen, die man im allgemeinen Fall nicht so einfach in unabhängige Teile aufspalten kann, die dann weitgehend sperrungsfrei von Teilprozessen weiterverarbeitet werden können. Potentielle Ansätze reichen von naheliegenden Ideen der Parallelisierung einzelner Phasen des seriellen Algorithmus bis hin zur Anwendung graphentheoretischer Begriffe zur Identifizierung weitgehend unabhängiger Teilgraphen.
   Betreuer: Thomas Hanneforth, Department Linguistik, Computerlinguistik
   Bearbeitet von Christian S.
6. GPU-API-Vergleich
   Bereich: MPI, Multicore-Programmierung
   Mit CUDA C, OpenCL und OpenACC stehen verschiedene Programmierschnittstellen zur Ausnutzung der massiven Parallelität in Grafikkarten bereit. Im Rahmen des Praktikums soll zunächst eine einfache Stencil-Berechnung sequentiell implementiert und für Multicore-Systeme parallelisiert werden. Im Anschluss wird das sequentielle Original mit den genannten Schnittstellen auf die GPU portiert. Betrachtet werden sollen dabei zum einen die Benutzbarkeit für den Programmierer als auch die Leistungsfähigkeit der GPU-Portierung.
   Betreuer: Steffen Christgau
   Bearbeitet von Torsten K und. Stefan P.
7. Non-blocking Collectives
   Bereich: MPI, Parallelisierung
   Nichtblockierende kollektive Operationen (z.B. IBcast in Analogie zu ISend) sind für den MPI-Standard Version 3 vorgesehen. Es existieren bereits entsprechende Implementierungen. Im Rahmen des Praktikums sollen vorhandene Anwendungen (bereits parallelisierte Klimasimulation POTSDAM-3, FFT) mit Blick auf die NBCs optimiert werden.
   Betreuer: Steffen Christgau
8. Multicore Programming with OpenMP and MPI / Erweiterung des Zellularautomaten
   Bereich: MPI, Multicore-Programmierung, NoC, SCC
   Der aus der Vorlesung Paralleles Rechnen bekannte Zellularautomat soll um eine 2-dimensionale Zerlegungen erweitert werden. Zusätzlich sollen Topologieinformationen (MPI-2) ergänzt werden, von der die Anwendung u.U. auf entsprechenden Plattformen (Cluster und Intel SCC) profitieren kann. Weiterhin werden Muticorearchitekturen immer wichtiger. Daher kommen Fragen auf wie: Wie verhalten sich reine MPI Anwendungen auf einem Cluster von Multicoremaschinen im Gegensatz zu hybriden Ansätzen die MPI und OpenMP nutzen? Diese Frage soll beantwortet werden, indem der aus der Zellularautomat mit MPI, OpenMP und einer Hybriden Variante implementiert und anschließend, die verschiedenen Varianten verglichen werden. Plattform: Zuse-Node mit Dual-Quadcore Nehalem (8 Cores), ZEIK-Computeserver mit Quad-12 Core Magny Cours (48 Cores).
   Betreuer: Steffen Christgau
   Bearbeitet durch Mohammad K. und Jorge K.

Literatur

• Michael J. Quinn: Parallel Programming, Mcgraw-Hill Higher Education, 2004
• Peter Sanders, Thomas Worsch: Parallele Programmierung mit MPI, Logos Verlag, 1997
• Ian Foster: Designing and Building Parallel Programs, Addison Wesley, 1995
• Hwang/Xu: Scalable Parallel Computing: Technology, Architecture, Programming, Boston, WCB/McGraw-Hill, 1998
• Jakub Kurzak, David A. Bader, Jack Dongarra (Eds): Scientific Computing with Multicore and Accelerators, CRC Press Taylor & Francis Group