Martin Luther University Halle-Wittenberg

Further settings

Login for editors

Contents Parallel Algorithms summer 2010

3+1 hours per week (master, diploma)

1.     Einführung

2.     Grundlagen
2.1    Modelle                                           
2.1.1  Gerichtete azyklische Graphen
2.1.2  Shared-Memory-Modell
2.1.3  Distributed-Memory-Modell
2.1.4  Netzwerk-Modell
2.1.5  Modellvergleich, PRAM-Bedeutung
2.1.6  Weitere Modelle
2.2    Analyse paralleler Algorithmen
2.3    Arbeit-Zeit-Paradigma
2.4    Optimalität
2.5    Kommunikationskomplexität

3.     Verbindungsnetzwerke und Kommunikationsalgorithmen
3.1    Ausgewählte Topologien
3.2    Einbettungen
3.3    Routing und Kommunikation
3.3.1  Broadcast
3.3.2  Permutationsrouting
3.3.3  All-to-All Routing
3.3.4  Gossiping
3.3.5  Cut-through Routing, Circular Shift
3.3.6  Teilung langer Nachrichten
3.4    Randomisierung

4.     Basis-Techniken
4.1    Divide and Conquer
4.2    Partitionierung
4.3    Kaskadierung
4.4    Balancierte Bäume

5.     Sortieren
5.1    Shearsort
5.2    Quicksort
5.3    Bitonic Sort, Sortiernetzwerke

6.     Schnelle Fourier-Transformation

7.     Graph-Algorithmen
7.1    Minimaler Spannbaum
7.2    Kürzeste Wege -- eine Quelle
7.3    Kürzeste Wege -- alle Knotenpaare
7.3.1  Dijkstra-Parallelisierung
7.3.2  Parallelisierung Floyd-Algorithmus
7.4    Zusammenhangskomponenten

8.    List Ranking
8.1   Pointer Jumping
8.2   Einfaches optimales List Ranking

Up