Parallele Algorithmen (SS 99)

(Vertiefungsvorlesung der theoretischen Informatik.)

Ort:

Di u. Do, 11-13, SR 015, Geb. 45.

Erste Vorlesung:

13.4.99

Dozenten:

Dr. Peter Sanders, Geb. 46, Raum 315, Tel. 0681 9325 115, sanders@mpi-sb.mpg.de; Priv.-Doz. Dr. Jop Sibeyn, Geb. 46, Raum 318, Tel. 0681 9325 118, jopsi@mpi-sb.mpg.de

Sprechstunde:

Immer

Vorkenntnisse:

Vordiplom, Grundkenntnisse über sequentielle Algorithmen

Der Einsatz vieler Prozessoren zur gemeinsamen Lösung eines Problems ist einer der wichtigsten Ansätze zur Erhöhung der Leistung von Programmen. In dieser Vorlesung sollen die wichtigsten Techniken zum Entwurf paralleler Algorithmen vermittelt werden. Der Schwerpunkt liegt dabei auf praxisnahen Techniken und Ihrer Analyse.

Vorläufige Inhaltsübersicht

Parallele Maschinen und ihre Modellierung; logische und physikalische Verbindungsnetzwerke; kollektive Kommunkationsmuster; Routing; Matrizenrechnung; Lastbalancierung; Sortieren; parallele Datenstrukturen; Algorithmen für Graphen und Listen; gegenseitige Simulation von Berechnungsmodellen

Materialien zur Vorlesung

• In der Bibliothek des MPII gibt es einen Handapparat mit den wichtigsten Büchern zur Vorlesung.
• Überblick, parallele Berechnungsmodelle. Folien
• Mehr Modelle, Arithmetik. Folien
• Aufgabenblatt 1.
• Work-Time-Framework, Gitter, Zellularautomatensimulation & Co., Verbindungsnetzwerke, kollektive Kommunikation. Folien Aufgabenblatt 2. Aufgabenblatt 3. Aufgabenblatt 4.
• Lineare Algebra
  • für dichtbesetzte Matrizen Folien aus der Vorlesung Parallele Programmierung
  • für dünnbesetzte Matrizen Folien aus der Vorlesung Parallele Programmierung
• Lastbalancierung
• Eine Inhaltszusammenfassung der von Jop Sibeyn gehaltenen Vorlesungen.

Literatur

1

J. Jájá. An Introduction to Parallel Algorithms. Addison Wesley, 1992. PRAM Algorithmen.

2

T. Leighton. Introduction to Parallel Algorithms and Architectures. Morgan Kaufmann, 1992. Algorithmen für Verbindungsnetzwerke.

3

J. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

4

V. Kumar, A. Grama, A. Gupta, and G. Karypis. Introduction to Parallel Computing. Design and Analysis of Algorithms. Benjamin/Cummings, 1994. einfaches, praxisnahes Buch.

5

T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. McGraw-Hill, 1990.

6

P. Sanders and T. Worsch. Parallele Programmierung mit MPI - ein Praktikum. Logos Verlag Berlin, 1997. für Leute, die etwas zur Vorlesung programmieren möchten.

7

R. Vollmar and T. Worsch. Modelle der Parallelverarbeitung. Teubner, 1995.

8

Peter Sanders, Roland Vollmar, and Thomas Worsch. Feasible models of computation. In C. Lengauer, M. Griebl, and S. Gorlatch, editors, Euro-Par, number 1300 in LNCS, pages 384-388, Passau, 1997. Springer. Extended version as Technical Report IB 2/97, University of Karlsruhe, 1997.

9

W. J. Paul. Komplexitätstheorie. Teubner, 1978.