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

Book

  • R. H. Perrott, Parallel Programming. Addison-Wesley Publishing Company, 1987.
  • J. Jaja, An introduction to parallel algorithms. Redwood City, CA, USA: Addison Wesley Longman Publishing Co., Inc., 1992.
  • I. Foster, Designing and Building Parallel Programs. Addison-Wesley, 1995.
  • N. Lynch, Distributed Algorithms. Morgan Kaufmann Series in Data Management Systems, 1997.
  • S. Schneider, Concurrent and Real Time Systems: The CSP Approach. New York, NY, USA: John Wiley Sons, Inc., 1999.
  • P. B. Hansen, Ed., The origin of concurrent programming: From semaphores to remote procedure calls. New York, NY, USA: Springer-Verlag New York, Inc., 2002.
  • T. G. Mattson, B. A. S, ers, and B. L. Massingill, Patterns for Parallel Programming (Software Patterns Series), 1st ed. Addison-Wesley Professional, 2004.
  • M. Herlihy and N. Shavit, The Art of Multiprocessor Programming. Morgan Kaufmann, 2008.
  • C. Breshears, The Art of Concurrency: A Thread Monkey's Guide to Writing Parallel Applications. O'Reilly Media, Inc., 2009.
  • D. B. Kirk and W. W. Hwu, Programming Massively Parallel Processors: A Hands-on Approach, 1st ed. Morgan Kaufmann, 2010.
  • K. Mani Chandy and J. Misra, Parallel Programming Design. .

Book Section

  • G. M. Amdahl, "Validity of the single processor approach to achieving large scale computing capabilities," San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2000, pp. 79-81.
  • P. J. Courtois, F. Heymans, and D. L. Parnas, "Concurrent control with 'readers' and 'writers'," D. M. Hoffman and D. M. Weiss, Eds. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 2001, pp. 389-392.
  • C. A. R. Hoare, "Towards a theory of parallel programming," in The origin of concurrent programming: From semaphores to remote procedure calls, New York, NY, USA: Springer-Verlag New York, Inc., 2002, pp. 231-244.
  • E. W. Dijkstra, "Cooperating sequential processes," in The origin of concurrent programming: From semaphores to remote procedure calls, New York, NY, USA: Springer-Verlag New York, Inc., 2002, pp. 65-138.
  • E. W. Dijkstra, "Hierarchical ordering of sequential processes," in The origin of concurrent programming: From semaphores to remote procedure calls, New York, NY, USA: Springer-Verlag New York, Inc., 2002, pp. 198-227.

    • Journal Article

  • M. E. Conway, "Design of a separable transition-diagram compiler," Commun. ACM, vol. 6, no. 7, pp. 396-408, Jul. 1963.
  • P. Brinch Hansen, "Structured multiprogramming," Commun. ACM, vol. 15, no. 7, pp. 574-578, 1972.
  • C. A. R. Hoare, "Monitors: an operating system structuring concept," Commun. ACM, vol. 17, no. 10, pp. 549-557, 1974.
  • C. Antony Richard Hoare, "Communicating Sequential Processes," Commun. ACM, vol. 21, no. 8, pp. 666-677, 1978.
  • P. Brinch Hansen, "Distributed processes: a concurrent programming concept," Commun. ACM, vol. 21, no. 11, pp. 934-941, 1978.
  • D. Gelernter, "Generative communication in Linda," ACM Trans. Program. Lang. Syst., vol. 7, no. 1, pp. 80-112, Jan. 1985.
  • J. L. Gustafson, "Reevaluating Amdahl's law," Commun. ACM, vol. 31, no. 5, pp. 532-533, 1988.
  • L. G. Valiant, "A bridging model for parallel computation," Commun. ACM, vol. 33, no. 8, pp. 103-111, 1990.
  • H. Sutter, "The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software," Dr. Dobb's Journal, vol. 30, no. 3, Mar. 2005.
  • M. D. Hill and M. R. Marty, "Amdahl's Law in the Multicore Era," IEEE Computer, vol. 41, no. 7, pp. 33-38, Jul. 2008.
  • F. Feinbube, P. Tröger, and A. Polze, "Joint Forces: From Multithreaded Programming to GPU Computing," IEEE Software (Software), vol. 28, no. 1, pp. 51-57, Oct. 2010.
  • H. González-Vélez and M. Leyton, "A survey of algorithmic skeleton frameworks: high-level structured parallel programming enablers," Software: Practice and Experience, vol. 40, no. 12, pp. 1135-1160, Nov. 2010.

Conference Paper

  • E. W. Dijkstra, "The structure of the 'THE'-multiprogramming system," in SOSP '67: Proceedings of the first ACM symposium on Operating System Principles, 1967.
  • D. E. Culler, R. M. Karp, D. A. Patterson, A. Sahay, K. E. Schauser, E. Santos, R. Subramonian, and T. von Eicken, "LogP: Towards a Realistic Model of Parallel Computation," 1993, pp. 1-12.
  • R. D. Blumofe and C. E. Leiserson, "Scheduling Multithreaded Computations by Work Stealing," in In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS, 1994, pp. 356-368.
  • K. Kennedy, C. Koelbel, and H. Zima, "The rise and fall of High Performance Fortran: an historical object lesson," in third ACM SIGPLAN conference on History of programming languages, 2007, pp. 7-1.
  • G. Bronevetsky, I. Laguna, S. Bagchi, B. R. de Supinski, D. H. Ahn, and M. Schulz, "AutomaDeD: Automata-based debugging for dissimilar parallel tasks," in International Conference on Dependable Systems and Networks (DSN), 2010, pp. 231-240.
  • W. Gellerich and M. . Gutzmann, "Massively Parallel Programming Languages - A Classification," in ISCA International Conference on Parallel and Distributed Computing Systems, vol. 1, pp. 110-118.
  • A. P. Chandrakasan, M. Potkonjak, R. Mehra, J. Rabaey, and R. W. Brodersen, "Optimizing Power Using Transformations."
  • D. M. Tullsen, S. J. Eggers, and H. M. Levy, "Simultaneous Multithreading: Maximizing On-Chip Parallelism," in 22nd Annual International Symposium on Computer Architecture.

Web Page

  • "Classification of the principal programming paradigms." [Online]. Available: http://www.info.ucl.ac.be/~pvr/paradigms.html. [Accessed: 29-Mar-2011].
  • G. V. Wilson, "The History of the Development of Parallel Computing." .
  • B. Barney, "Introduction to Parallel Computing." .
  • C. Breshears, "Intro to Parallel Programming - Video Course." [Online]. Available: http://www.dailymotion.com/playlist/x1pc0m_Intel_Academic_EMEA_intro-to-parallel-programming/1

Slide

  • A. Bechtolsheim, The Road To Exascale. 2009.