Inhalt Parallele Algorithmen WS 2008/2009
4+2 SWS
(in German)
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 Pipelining
3.5 Kaskadierung
4. Sortieren
4.1 Shearsort
4.2 Quicksort
4.3 Bitonic Sort, Sortiernetzwerke
5. Schnelle Fourier-Transformation
6. Graph- Algorithmen
6.1 Minimaler Spannbaum
6.2 Kürzeste Wege: eine Quelle
6.3 Kürzeste Wege: alle Knotenpaare
6.3.1 Dijkstra-Parallelisierung
6.3.2 Parallelisierung Floyd-Algorithmus
6.4 Transitive Hülle
6.5 Zusammenhangskomponenten
7. List Ranking
7.1 Pointer Jumping
7.2 Einfaches optimales List Ranking