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