Parallele Algorithmen

In der Vorlesung "Entwurf und Analyse von Algorithmen" sind Algorithmen behandelt worden, die sequentiell ausgeführt werden. Ein wesentlicher Schritt, die Rechenzeit von Algorithmen zu verkürzen, besteht nun darin, Parallelismus oder Nebenläufigkeit zuzulassen. Der Grundgedanke dabei besteht darin, dass große Berechnungsaufgaben in mehrere Teilaufgaben zerlegt werden, die unabhängig voneinander simultan gelöst werden. Das gesuchte Gesamtergebnis kann dann aus den Teilergebnissen zusammengesetzt werden, sobald alle Teilberechnungen beendet sind.

Das Konzept des Parallelismus kann in zwei Richtungen verfolgt werden:

  1. Hardware-orientiert:
    Finde für eine gegebene parallele Rechnerarchitektur solche parallelen Algorithmen, die die gegebene Architektur möglichst vorteilhaft ausnutzen.
    Stichworte:
  2. Problem-orientiert:
    Welche Probleme lassen sich prinzipiell mit parallelen Algorithmen schneller lösen als mit sequentiellen Algorithmen?

    Hier werden wir als grundlegendes Rechnermodell die parallele RAM verwenden. Die betrachteten Probleme reichen vom Suchen und Sortieren über Algorithmen in Graphen bis zu arithmetischen Berechnungen.

Literatur:

Kapitel 6 des Skripts "Effiziente Algorithmen"
von K. Madlener und F. Otto, Univ. Kaiserslautern, Ausgabe 1994.
Joseph Ja'Ja':
An Introduction to Parallel Algorithms
Addison-Wesley, Reading, MA, 1992.
L. Kronsjoe:
Computational Complexity of Sequential and Parallel Algorithms
John Wiley, Chichester, 1986.

Diese Vorlesung richtet sich an Studenten in mittleren und höheren Semestern mit guten Kenntnissen in den Grundlagen der Informatik.