Rechnen in Parallelen und Verteilten Systemen

Skripte zur Vorlesung sind im Entstehen begriffen. :(beschränkter Zugang).

Der Halbkurs bietet eine Einführung in die Verfahren und Techniken zur Programmierung von Parallelrechnern. Wir diskutieren typische Vorgehensweisen im Detail und vergleichen sie mit Verfahren, die im Bereich verteilter Systeme üblich sind. Augenmerk wird dabei auf das Ziel ``Paralleles Rechnen in verteilten Umgebungen'' gelegt.

Teilnehmer des Kurses sollen anhand von Beispielalgorithmen Programmiererfahrungen für verschiedene parallele Umgebungen erwerben. Ziel ist eine vergleichende Analyse der Umgebungen. Der Halbkurs besteht aus Vorlesung und Seminar. Einige Veranstaltungen mit Kolloquiumscharakter sollen dem Austausch der bei der Implementation der Beispielalgorithmen gesammelten Erfahrungen dienen.

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

• Arbeiten am Lehrstuhl Rechnerorganisation und Kommunikation
  • Responsive CORBA Unififed Environment (RESCUE)
  • Shared Objects Net-interconnected Computer (SONiC), testbed
  • CORE - Consensus for Responsiveness
• ISIS-System
• Linda, Posybl
• Mach:
  • netzwerktransparente Kommunikation, message passing,
  • Microkernel, EMM
  • OSF/1, MkLinux
  • Mach4, Lites
• SUN RPC, rpcgen, XDR
• AT&T System V IPC auf Multiprozessor
• Teknetron Information Bus (TIB)
• Parallel Virtual Machine (PVM), Trapper
• Common Object Request Broker Architecture (CORBA)
  • Umgang mit Inter Language Unification (ILU) und Orbacus-CORBA Implementationen
  • thread-Modelle, Parallelität
  • vorhersagbares Zeitverhalten, RT-CORBA

Projektarbeit

Implementation mehrerer paralleler Beispielalgorithmen (Primzahlsuche, Gaußsches Eliminationsverfahren, Fraktale, Labyrinth-Suche, Paralleles Rendering, Benchmarks) in verschiedenen Umgebungen:


• Transputer, Parix, Occam (?)
• Linda, Posybl
• CORBA: ILU / Orbacus
• SUN RPC, rpcgen
• Mach, SONiC, testbed
• Modula-P auf mehreren SUN Sparc
• Parallaxis
• ISIS 2.3
• Teknekron Information Bus (TIB): publisher/subscriber communication
• Parallel Virtual Machine (PVM), Trapper

Einige Beispielprogramme sind hier zu finden :(beschränkter Zugang).

Literatur

Vipin Kumar et al., "Introduction to Parallel Computing", ISBN 0-8053-3170-0, Benjamin/Cummings 1993;


Thomas Bräunl, "Parallele Programmierung: eine Einführung", ISBN 3-528-05142-6, Vieweg 1993;


Theo Ungerer, "Parallelrechner und parallele Programmierung", (Spektrum-Hochschultaschenbuch), ISBN 3-8274-0231-X, Spektrum Akademischer Verlag GmbH, 1997.


Joseph Boykin et al., "Programming under Mach", ISBN 0-201-52739-1, Addison-Wesley 1993.


Bruce P. Lester, "The Art of Parallel Programming", ISBN 0-13-045923-2, Prentice-Hall, 1993.


Nicholas Carriero, David Gelernter, "How to Write Parallel Programs", ISBN 0-262-03171-X, MIT Press, 1990.


Michael Weber , "Verteilte Systeme", (Spektrum-Hochschultaschenbuch), ISBN 3-8274-0221-2, Spektrum Akademischer Verlag GmbH, 1998.

CA&C-Page