Parallele Algorithmen, Vorlesung, WS17/18 Karlsruher Institut für Technologie (KIT)

13 |
0:00:00 Starten
0:00:36 Was wissen wir über die Jobs?
0:02:32 Was wissen wir über die Prozessoren?
0:05:44 Zufälliges Zuordnen
0:07:08 Work Stealing
0:10:58 Backtracking over Transition Functions
0:12:02 An Abstract Model: Tree Shaped Computations
0:17:37 Splitting Stacks
0:21:27 Other Problem Categories
0:27:01 Limits of the Model
0:29:35 Receiver Initiated Load Balancing
0:31:40 Random Polling
0:41:11 Synchronous Random Polling
0:45:21 Analysis
0:51:22 Bounding Idleness
0:57:08 A Simplified Algorithm
1:03:22 Many Consecutive Splits
1:05:49 Many Processors
1:09:03 Superliner Speedup
1:15:12 Static vs Dynamic LB
1:18:35 MapReduce in 10 Minutes

12 |
0:00:00 Starten
0:00:10 Parallele Prioritätslisten
0:02:03 Branch-and-Bound
0:05:17 Einfache Probabilistische Eigenschaften
0:08:11 Parallele Realisierung II
0:09:58 Randomisierte Selektion
0:15:14 Parallele Implementierung
0:21:11 Implementierung IBM SP-2 m=2^24
0:23:27 Implementierung Cray T3D, m=2^24
0:26:07 Lastverteilung
0:30:25 Kostenmaß
0:34:35 Was wissen wir über die Jobs und die Prozessoren?
0:37:26 Ein ganz einfaches Modell
0:51:04 Atomare Jobs
0:58:56 Beispiel Mandelbrotmenge
1:02:56 Angenäherte Berechnung
1:05:56 Code
1:08:31 Statische Äpfelverteilung
1:13:01 Zufälliges Zuordnen
1:19:42 Parallelisierung der Zuordnungsphase
1:21:34 Pseudorandom Permutations
1:24:37 Das Master-Worker-Schema
1:28:22 Größe der Teilprobleme

11 |
0:00:00 Starten
0:00:14 Finding lightest incident edges
0:01:19 Pseudotrees - Rooted Trees
0:03:00 Randomized Linear Time Algorithm
0:04:24 Parallel Filter Kruskal
0:05:40 Parallele Prioritätlisten
0:10:34 Naive Implementierung
0:11:30 Branch-and-Bound
0:25:18 Sequentielles Branch-and-Bound
0:35:27 Paralleles Branch-and-Bound
0:38:20 Analyse
0:52:09 Der Algorithmus von Karp und Zhang
1:01:47 Einfache Probabilistische Eigenschaften
1:04:01 Parallele Realisierung I
1:16:04 Parallele Realisierung II

10 |
0:00:00 Starten
0:00:10 Minimum Spannung Trees
0:03:06 Selecting and Discarding MST Edges
0:09:01 Kruskal's Algorithm
0:12:41 Edge Contraction
0:16:29 Finding lightest incident edges
0:24:06 Structure of Resulting Components
0:28:51 Pseudotrees -> Rooted Trees
0:31:07 Rooted Trees -> Rooted Stars by Doubling
0:32:43 Contraction
0:42:36 Recursion
0:45:21 Analysis
0:52:10 Randomized Linear Time Algorithm
0:55:08 Parallel Filter Kruskal
1:05:43 Running Time: Random graph with 2^16 nodes
1:09:12 More on Parallel MST

09 |
0:00:00 Starten
0:00:10 Datenaustausch bei unregelmäßigen Nachrichtenlängen
0:02:02 Der Vogel-Strauß-Algorithmus
0:05:41 h-Relation
0:07:37 Offline h-Relationen im duplex Modell
0:17:17 Offline h-Relationen im Simplex-Modell
0:22:08 How Helper Hasten h-Relations
0:23:02 Ein ganz simpler Fall
0:24:53 Zwei Dreiecke
0:31:25 Reduktion h-Relation =>(h/2) 2-Relationen
0:33:06 Offline h-Relationen im duplex Modell
0:36:24 ""-Relationen routen für gerade p
0:39:24 Zwei Ungerade Kreise mit >= 3 Knoten
0:43:16 Offene Probleme
0:50:39 Ein einfacher verteilter Algorithmus - Der Zweiphasenalgorithmus
0:53:54 Abstrakte Beschreibung
1:00:40 Offene Probleme zum nichtpräemptiven offline Algorithmus
1:02:07 Zusammenfassung: All-to-All
1:04:26 Noch allgemeinere kollektive Kommunikation: Multicommodity Multicasting

08 |
0:00:00 Starten
0:01:52 Kollektive Kommunikation
0:05:06 All-to-all Personalized Communication
0:08:09 Der 1-Faktor-Algorithmus
0:14:46 Datenaustausch bei unregelmäßigen Nachrichtenlänge
0:17:42 Ein einfacher verteilter Algorithmus- Der Zweiphasenalgorithmus
0:33:27 List Ranking
0:42:37 Motivation II
0:45:26 Doubling using CREW PRAM, n=p
0:55:37 Entfernung unabhängiger Teilmengen
1:13:01 Finden unabhängiger Teilmengen
1:20:05 Neuere Implementierungsergebnisse
1:22:45 Minimum Spanning Trees
1:25:09 The Jarník-Prim Algorithm