Inhalt Parallele Algorithmen Winter 2007/2008
(3+1 SWS)
1. Grundlagen
1.1 Warum Parallelverarbeitung?
1.2 Modelle
1.2.1 Gerichtete azyklische Graphen
1.2.2 Shared-Memory-Modell
1.2.3 Distributed-Memory-Modell
1.2.4 Netzwerk-Modell
1.2.5 Modellvergleich, PRAM-Bedeutung
1.2.6 Weitere Modelle
1.3 Leistung paralleler Algorithmen
1.4 Arbeit-Zeit-Paradigma
1.5 Kommunikationskomplexität
2. Verbindungsnetzwerke und Kommunikationsalgorithmen
2.1 Ausgewählte Topologien
2.2 Einbettungen
2.3 Routing und Kommunikation
2.3.1 Broadcast
2.3.2 Permutationsrouting
2.3.3 All-to-All Routing
2.3.4 Gossiping
2.3.5 Cut-through Routing, Circular Shift
2.3.6 Teilung langer Nachrichten
2.4 Randomisierung
3. Basis-Techniken
3.1 Balancierte Bäume
3.2 Divide and Conquer
3.3 Partitionierung
3.4 Kaskadierung
4. Sortieren
4.1 Shearsort
4.2 Quicksort
4.3 Bitonic Sort, Sortiernetzwerke
5. Graph-Algorithmen
5.1 Minimaler Spannbaum
5.2 Kürzeste Wege: eine Quelle
5.3 Kürzeste Wege: alle Knotenpaare
5.3.1 Dijkstra-Parallelisierung
5.4 Zusammenhangskomponenten
6. List Ranking
6.1 Pointer Jumping
7. Schnelle Fourier-Transformation