Vorlesung über "Algorithmen für netzwerkgekoppelte Systeme"

In der Vorlesung "Algorithmen für netzwerkgekoppelte Systeme" werden die folgenden Themen behandelt:

• Semisystolische und systolische Netzwerke;
• Paket-Routing in Gitternetzwerken, Analyse des erwarteten Verhaltens von Greedy-Routing;
• Eine untere Laufzeitschranke für oblivious Routing in beliebigen Netzen;
• Hypercube Netzwerke (HCN): Eigenschaften, Routing, Einbettung von Bäumen in HCN, Einbettung mehrdimensionaler Gitter in HCN;
• Shuffle-Exchange-Netzwerke (SEN): Zwei Kartentricks, Simulation normaler HC-Algoithmen auf SEN, de Bruijn-Netzwerke;
• Butterfly Netzwerke (BFN): Eigenschaften, Routing, Odd-Even-Mergesort, Diskrete Fourier-Transformation und Implementation auf BFN, Emulation von PRAM's auf BF-Netzwerken, Permutationsnetzwerke von Benes.

Termine

• Mittwochs 13:30-15:00 und Donnerstags 10:30-12:00 im Hörsaal 301, Pohlighaus.
• Übungen: nach Vereinbarung, im Pohlighaus; Betreuer: Stefan Porschen.

Mitschrift

Eine (alpha-Version) des Skripts finden sie hier als ps und pdf-Datei. Bei Fehlern im Skript schicken Sie bitte eine E-Mail an Lech Nieroda. Danke!

Literatur

• Frank T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan-Kaufman, 1992
• Ananth Grama, George Karypis, Vipin Kumar, Anshul Gupta, Introduction to Parallel Computing, 2nd Edition, Addison-Wesley, 2003

Von der Literaturliste ist das (empfehlenswerte) Buch von Leighton zur Zeit nicht verfügbar, für Januar 2006 ist eine neue Auflage (mit dem Untertitel "Algorithms and VLSI") angekündigt. Das letztgenannte Buch in der Liste enthält eine Einführung in MPI.