zum Inhalt springen

Parallele Algorithmen

Behandelt wird zunächst das Shared-Memory Maschinenmodell der PRAM (Parallel Random Access Machine), auf dem die Entwicklung paralleler Algorithmen dadurch vereinfacht wird, dass die Organisation der Kommunikation zwischen den Prozessoren sehr einfach über den gemeinsamen Speicher möglich ist. Für dieses Modell werden Basis-Techniken und -Algorithmen behandelt, die in vielen komplexen Problemen als Subprobleme auftauchen. Den behandelten Problemen ist gemeinsam, dass sie auf einer PRAM mit polynomiell vielen Prozessoren in polylogarithmischer Zeit gelöst werden können, also in der sogenannten Klasse NC (Nick's Class) liegen. Dann wird untersucht, ob für alle sequentiell in Polynomzeit lösbaren Probleme NC-Algorithmen existieren. Dabei werden schwierigste P-Probleme vorgestellt, für die es vermutlich keine NC-Algorithmen gibt.

Im zweiten Teil der Vorlesung widmen wir uns dann der bisher ausgeklammerten Frage, wie für netzgekoppelte Maschinen - skalierbare Architekturen sind immer netzgekoppelt – Kommunikation zwischen den Prozessoren organisiert werden kann. Dazu betrachten wir verschiedene Vernetzungstypen wie Gitter, Bäume, Hypercubes (mehrdimensionale Würfel) sowie einige interessante Hypercubevarianten. In diesem Zusammenhang untersuchen wir außerdem Einbettbarkeitsfragen für verschiedene Vernetzungen, um die Kommunikation bei geänderter Vernetzungstopologie nicht immer neu berücksichtigen zu müssen.

Abschließend behandeln wir noch ein automatisches Verfahren, um Algorithmen für semisystolische Netze, die z.B. über Broadcastfähigkeit verfügen, in kaum langsamere, systolische zu verwandeln. Semisystolische Algorithmen lassen sich oft einfach entwickeln, während der Entwurf systolischer Netze - nur die sind technisch realisierbar - in der Regel sehr schwierig ist.

Voraussetzungen: Für eine erfolgreiche Teilnahme wird die Beherrschung der Inhalte der Veranstaltungen Programmierkurs, Informatik I und II, sowie des Programmierpraktikums vorausgesetzt.

Leistungsnachweis: Es kann eine qualifizierte Teilnahmebescheinigung durch Bearbeitung von Übungsaufgaben sowie einer ca. 2-3 stündigen Klausur oder einer ca. 30 minütigen mündlichen Prüfung am Semesterende erlangt werden. Die Prüfungsform richtet sich nach der Teilnehmerzahl.

Literatur:

  • JaJa: An Introduction to Parallel Algorithms. Addison Wesley, 1992.
  • Leighton, F.T.: Einführung in Parallele Algorithmen und Architekturen. Thomson Publishing, 1997.