Parallele Algorithmen


Prof. Dr. Stefan Näher

Proseminar im Grundstudium über 2 SWS


Inhalt

Verfahren der Algorithmischen Geometrie sind meist sehr rechenintensiv. Bei vielen Anwendungen, z. B. in der Bildverarbeitung (vor allem in Echtzeit), sind kurze Bearbeitungszeiten, also schnelle Algorithmen, gefragt. Berechnungen auf modernen Hochleistungsrechnern erfordern aber speziell parallelisierte Algorithmen. Dieser Thematik wird sich das Seminar widmen. Nach der Einführung zu parallelen Berechnungsmodellen sollen parallele Algorithmen betrachtet werden, z. B. zu den Problemkreisen Sortieren, Graphalgorithmen, Konvexe Hülle, Nächste Nachbarn, Linienschnitte, Voronoi-Diagramme.


Vorkenntnisse

Elementare Kentnisse über Datenstrukturen und Algorithmen (Info II).

Termin

Donnerstag, 10-12 Uhr, V 301


Themen

1.Einführung/Überblick

2.Array/Tree - Architekturen: Sortieren

3.Array/Tree - Architekturen: Matrixalgorithmen

4.Array/Tree - Architekturen: Graphalgorithmen

5.Meshes of Trees: Überblick, Elementare Algorithmen, Matrixalgorithmen

6.Meshes of Trees: Graphalgorithmen

7.Hypercubes und verwandte Architekturen: Überblick

8.Hypercubes und verwandte Architekturen: Sortieren

9.Parallele Algorithmen in der Algorithmischen Geometrie

10.Praktische Parallele Programmierung - PVM (Parallel Virtual Machine)

11.Praktische Parallele Programmierung - MPI (Message Passing Interface)


Literatur

[Leigh92]
F.T. Leighton:
Introduction to Parallel Algorithms and Architectures,
Morgan Kaufmann, San Mateo, 1992

[AklLyons93]
S.G. Akl, K.A. Lyons:
Parallel Computational Geometry,
Prentice Hall, Englewood Cliffs, 1993


Last modified on 2002-09-26
Email: Matthias Bäsken