Martin Luther University Halle-Wittenberg

Further settings

Login for editors

Contents Parallel Algorithms Winter 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

Up