Hasso-Plattner-Institut Potsdam Operating Systems and Middleware Group at HPI University of Potsdam, Germany
Operating Systems and Middleware Group at HPI

Programmierung paralleler und verteilter Systeme

Sommersemester 2015

Frank Feinbube, M.Sc., Felix Eberhardt, M.Sc.,
Prof. Dr. Andreas Polze

Hinweis: Für die mündliche Prüfung bitte im Büro von Frau Wagner in die Einschreibelisten eintragen.

Prozessoren besitzen heute eine Vielzahl von Verarbeitungseinheiten (cores). Jede Verarbeitungseinheit kann zudem mehrere Kontrollflüsse gleichzeitig verarbeiten (hyperthreading). Damit ist heute jeder Standardprozessor eigentlich ein "Parallelrechner".

Die Vorlesung setzt sich mit den Wurzeln, technischen Grundlagen, Programmiermodellen und Problemen auseinander, die vor etlichen Jahren für spezialisierte Parallelrechner diskutiert wurden. Die gleichen Themen sind heute aber relevant wenn es darum geht, die funktionalen Einheiten eines Standardprozessors (Multicore/Manycore) optimal auszulasten.

Graphikkarten (GPGPU) stellen SIMD-Parallelrechner auf einem Chip dar. Cluster-Systeme sind heute oftmals innerhalb eines Racks aufgebaut und von klassischen Multiprozessoren nicht zu unterscheiden. Wir diskutieren Programmiermodelle, Speicherarchitekturen, Verbindungsnetzwerke und Fehlertoleranzmechanismen über das gesamte Spektrum paralleler Systeme.

Vorlesungen / Leistungserfassung

Mi, 11:00 - 12:30, HS 3

Die Vorlesung findet mittwochs mit einem Umfang von 2 SWS statt. Nach erfolgreich absolvierter mündlicher Prüfung (voraussichtlich Ende September 2015) erwerben Studierende 3 benotete ECTS-Punkte.

Die Vorlesung kann durch eine praktische Projektarbeit ergänzt werden. Über diese Projektarbeit können Studierende mit einem Vortrag im Forschungsseminar "Betriebssysteme" (Di, 11:00-12:30) berichten und dafür weitere 3 benotete ECTS-Punkte erwerben.
Eine Übersicht der möglichen Projektthemen gibt es hier. Themenwünsche bitte bis zum 06.05.2015 per E-Mail an Frank.Feinbube@hpi.de oder einfach bei uns vorbeikommen.

Ablauf / Themen

Grundlegende Begriffe paralleler Programmierung

  • Klassifikationen: Rechnerklassifikationen, Parallelitätsebenen, Parallele Operationen
  • Konzepte der Parallelverarbeitung:
    • Coroutinen, Fork und Join, ParBegin und ParEnd, Prozesse, RPC, explizite vs. implizite Parallelität
    • Shared-Address-Space vs. Message Passing
    • Data Parallelism vs. Control Parallelism
  • Grundlegende Kommunikations-Operationen: Message Transfer, One-to-all broadcast, all-to-all broadcast
  • Idealisierte Parallelrechner: PRAM, LogP, BSP

Synchrone Parallelität

  • SIMD-Rechner: Aufbau, Datenparallelität, Virtuelle Prozessoren
  • Kommunikation: Verbindungsstrukturen, Datenaustausch, Vektorreduktion
  • Probleme bei synchroner Parallelität:
    • virtuelle vs. physische Prozessoren
    • I/O-Problem
    • Netzwerk-Bandbreite
    • Mehrbenutzerbetrieb, Fehlertoleranz
  • Massiv parallele Algorithmen: 
Numerische Integration, Zelluläre Automaten, Primzahlen, Sortieren, Systolische Matrixmultiplikation, Fraktale
  • Seminarvorträge über SIMD-Programmiersprachen: 
FORTRAN 90, HPF, C*, MasPar Prog. Language MPL, Parallaxis

Asynchrone Parallelität

  • MIMD-Rechner, SPMD-Ansatz
  • Synchronisation und Kommunikation in MIMD-Systemen: Softwarelösung, Hardwarelösung, Semaphore, Monitore, Nachrichten, RPC
  • Probleme bei asynchroner Parallelität: inkonsistente Daten, Verklemmungen, Lastbalanzierung
  • Grobkörnig parallele Algorithmen: 
bounded Buffer Semaphor/Monitor, Scheduling über Monitore
  • Seminarvorträge über MIMD-Programmiersprachen: 
Concurrent Pascal, CSP, Occam, Ada, Sequent-C, Linda, Modula-P, COOL

Parallelität in verteilten Systemen

  • ISIS-System
  • Linda, Posybl
  • Mach: netzwerktransparente Kommunikation, message passing, Microkernel, EMM, Shared Objects Memory (SOM), testbed
  • SUN RPC, rpcgen, XDR
  • AT&T System V IPC auf Multiprozessor
  • Posix pthreads API
  • CORE - Consensus for Responsiveness - Responsive Cluster Computing

Regeln für Projektaufgaben

Die nachfolgenden Aufgaben können in Gruppen von 1-2 Teilnehmern bearbeitet werden und durch einen benoteten Vortrag im Forschungsseminar der Gruppe Betriebssysteme und Middleware vorgestellt werden.

Vorschläge für Projektaufgaben

Liste möglicher Projektthemen

Literaturliste

Loading content from CiteMaster ...