 |
Kommunikation in Parallelen Rechenmodellen
| Dozent |
Rolf Wanka |
Modulbeschreibung
|
Kommunikation in Parallelen Rechenmodellen |
| Umfang |
V2 + Ü2, 7,5 ECTS
Vertiefung Theoretische Informatik
Bachelor- oder Master-Studium
Studenten der Informatik, des
Computational Engineering, aus I&K,
Interessenten anderer
Fächer |
Ort
und Zeit der Vorlesung
|
Mi. 08:30-10:00, E 1.11, E-Technik-Gebäude
|
Ort
und Zeit der Übung
|
Mo. 8:30-10:00, E 1.11, E-Technik-Gebäude
|
Termine:
-
Beginn der Vorlesungen: Mittwoch, 20.10.2010
Beschreibung:
In dieser Vorlesung werden Algorithmen für die in parallelen Rechnersystemen
benötigten Basisoperationen
vorgestellt und Techniken für deren Analyse präsentiert.
Inhalte:
Parallele Systeme wie dedizierte Parallelrechner oder
PC-Cluster haben das Potential, durch Zusammenarbeit
schwierige Probleme, insbesondere auch auf großen Eingaben,
erheblich schneller lösen zu können als konventionelle
Ein-Prozessor-Rechner.
Eine Reihe von Basisoperationen wird bei der Implementierung von
Parallelen Algorithmen immer wieder benötigt: Zwischen
den Prozessoren werden Botschaften ausgetauscht, d.h. es
muß ein effizientes Routing gewährleistet
werden;
unterschiedliche Belastungen des Systems müssen durch
Lastverteilung vermieden werden;
sehr oft müssen die vorhandenen Daten sortiert werden;
spezielle Parallelrechnerarchitekturen müssen auf dem
tatsächlich vorhandenen parallelen System effizient
simuliert werden.
Diese Vorlesung stellt für die genannten Aufgaben
Algorithmen und ihre Analysen vor.
Im Einzelnen werden behandelt:
-
Permutationsrouting: Das Waksman-Netzwerk und mehrdimensionale Gitter
-
Sortiernetzwerke: Der Bitone Sortierer und mehrdimensionale Gitter
-
Netzwerksimulationen: Untere und obere Schranken
-
Das Multibutterfly-Netzwerk: Expander-Graphen sind nützlich
-
Probabilistisches Routing: Analyse des Random-Rank-Protokolls
-
PRAM-Simulationen: Universelle Hash-Funktionen
-
Lastverteilung: Token Distribution, Diffusionsverfahren
Übungsblätter:
(noch nicht aktualisiert)
Skript:
Den ersten Teil des Skripts gibt's als
pdf-File hier.
Jetzt gibt's auch den zweiten Teil, und
zwar hier.
Und da ist der dritte Teil:
click
Der Teil über die Simulationen ist hier.
Literatur:
-
R. Wanka.
Paralleles
Sortieren - Parallel geht schnell (Download mit
IP-Adresse der FAU), pp. 31-41, in:
B. Vöcking et al.
Taschenbuch der Algorithmen. Springer 2008.
-
F. T. Leighton.
Introduction to Parallel Algorithms and Architectures.
Morgan Kaufman, 1992.
-
J. H. Reif (Ed.).
Synthesis of Parallel Algorithms.
Morgan Kaufman, 1993.
-
I. Parberry. Parallel Complexity Theory. Pitman/Wiley, 1987.
-
Zahlreiche Originalarbeiten.
|
|
