Vorlesung über "Parallele Algorithmen"

Behandelt werden 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 Probleme ist gemeinsam, dass sie auf einer PRAM mit polynomiell vielen Problemen in polylogarithmischer Zeit gelöst werden können, also in der sogenannten Klasse NC liegen. Dann wird untersucht, ob für alle in Polynomzeit lösbaren Probleme NC-Algorithmen existieren. Dabei werden schwierigste P-Probleme vorgestellt, für die vermutlich keine NC-Algorithmen existieren.

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), einige interessante Hypercubevarianten sowie Einbettbarkeitsfragen für verschiedene Vernetzungen, um die Kommunikation bei geänderter Vernetzungstopologie nicht immer neu berücksichtigen zu müssen.

Abschließend behandelm 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: Beherrschung der Inhalte des Grundstudiums (Programmierkurs, Informatik I und II, Programmierpraktikum)

Qualifizierte Teilnahmebescheinigung durch Bearbeitung von Übungsaufgaben sowie eine ca. 3 stündige Klausur oder eine ca. 30 minütige mündliche Prüfung am Semesterende (richtet sich nach der Teilnehmerzahl).

Hauptstudiumsveranstaltung im Diplomstudiengang Wirtschaftsinformatik, Mathematik und Wirtschaftsmathematik sowie weitere Studienfächer mit Nebenfach Informatik (9 CPs)

Prüfungsblockmodul Wirtschaftsinformatik

Die Vorlesung Parallele Algorithmen fällt unter die Zuordnung Praktische Informatik III.

Prüfungsnummer 75006

Meldung zur Prüfung: 15.12.07

Mündliche Prüfung: 30.01.08

Skript

Die Mitschrift der Vorlesung finden Sie hier als pdf-Datei pdf. Bitte teilen Sie uns Fehler mit, die Sie im Skript finden. Danke!

Der "Algorithmus der Woche" wurde in der Vorlesung behandelt ist aber nicht im Skript erfasst. Zu finden unter:

"http://www-i1.informatik.rwth-aachen.de/~algorithmus/"

Besprochen wurde der Algorithmus Nr. 12: Paralleles Sortieren

Literatur

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