"Parallele Algorithmen 001.ps.gz" - читать интересную книгу автора

Parallele Algorithmen

Vorlesung gehalten im SS '98

Oliver Vornberger Frank M. Thiesing

Fachbereich Mathematik/Informatik

Universit"at Osnabr"uck

Literatur Vipin Kumar, Ananth Grama, Anshul Gupta, George Karypis: `Introduction to Parallel Computing -- Design and Analysis of Algorithms' The Benjamin/Cummings Publishing Company, Inc. 1994

Michael J. Quinn: `Parallel Computing -- Theory and Practice (Second Edition)' McGraw-Hill International Editions 1994

Danksagung Wir danken : : :

: : : Frau Gerda Holmann f"ur sorgf"altiges Erfassen des Textes und Erstellen der Grafiken, : : : Herrn Frank Lohmeyer und Herrn Volker Schnecke f"ur ihre engagierte Mitarbeit bei der

inhaltlichen und "ausserlichen Gestaltung des Textes,

: : : Herrn Axel H"adicke und Herrn Curd Reinert f"ur sorgf"altiges Korrekturlesen. : : : Herrn Viktor Herzog f"ur die Konvertierung des Skripts nach HTML.

HTML-Version Der Inhalt dieser Vorlesung kann online betrachtet werden unter http://www-lehre.informatik.uni-osnabrueck.de/~pa

Osnabr"uck, im Juli 1998 (Oliver Vornberger) (Frank M. Thiesing)

Inhaltsverzeichnis 1 Einf"uhrung 1

1.1 Grand Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Historische Entwicklung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Begriffsabgrenzungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Argumente gegen Parallelismus . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.5 Definitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Maschinenmodelle 9

2.1 Kontrollmechanismus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Speicherorganisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Verbindungsstruktur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.4 Granularit"at . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.5 PRAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3 Topologien 17

3.1 Dynamische Verbindungsnetzwerke . . . . . . . . . . . . . . . . . . . . . . . . 17