Parallele Algorithmen, Vorlesung, WS17/18

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

07 | 0:00:00 Starten 0:00:10 Analyse von Sample Sort 0:07:27 Samples Sortieren 0:07:46 Mehrwegemischen 0:12:51 Multisequence Selection 0:16:24 Splitter Selection 0:19:44 Verteilte Multisequence Selection 0:30:41 CRCW Sortieren in logarithmischer Zeit 0:35:50 Beispiel 0:37:54 Kollektive Kommunikation 0:39:18 Präfixsummen 0:41:29 Einfache Pipeline 0:42:41 Hyperwürfelalgorithmus 0:57:22 Analyse 0:58:35 Pipeline-Binärbaum-Präfixsummen 1:10:07 23-Präfixsummen 1:10:33 Analyse 1:10:56 Verallgemeinerung 1:11:17 Gossiping 1:20:02 Analyse 1:21:25 All-to-all Personalized Communication 1:25:04 Analyse, Telefonmodell

06 | 0:00:00 Starten 0:00:25 Schnelles ineffizientes Ranking 0:02:41 Sortieren größerer Datenmengen 0:02:48 Zurück zum schnellen Ranking 0:04:42 Verallgemeinerung für m >>p nach schema F? 0:10:01 Distributed memory parallel quicksort 0:10:16 Load Balance 0:24:28 Die gute Nachricht: 0:32:19 Bessere Lastbalanceierung? 0:35:32 Multi-Pivot Verfahren 0:42:23 Analyse 0:49:20 Lemma2. 0:50:46 Lemma 1:06:48 Chernoff-Schranke 1:15:21 Analyse von Sample Sort 1:30:48 Sample Sortieren

05 | 0:00:00 Starten 0:00:10 Analyse 0:02:11 Noch ein optimaler Algorithmus 0:02:22 Analyse, Telefonmodell 0:02:38 Diskussion 0:03:28 Sortieren 0:04:04 Schnelles ineffizientes Ranking 0:12:47 Sortieren größerer Datenmengen 0:17:01 Zurück zum schnellen Ranking 0:29:25 Beispiel 0:29:40 row all-gather-merge 0:32:47 Genauere Analyse, n 10 byte elemente pro PE 0:36:04 Rechenbeispiel 0:41:01 Quicksort 0:42:35 Anfänger-Parallelisierung 0:44:10 Theoretiker-Parallelisierung 0:54:57 Beispiel 1:14:41 Analyse 1:16:00 Veraalgemeinerung für m>>p nach Schema F? 1:19:27 Distrinuted memory parallel qicksort 1:26:11 Load Balance 1:34:41 Die gute Nachricht:

04 | 0:00:00 Starten 0:00:10 Übung 0:01:09 Starten 0:17:12 Analyse 0:19:48 Diskussion 0:20:39 H-Trees 0:22:18 Nachteile baumbasierter Broadcasts 0:23:21 23-Broadcast: Two T(h)rees for the Price of one 0:24:27 Root Process 0:25:30 Other Process 0:26:26 Belibiege Prozessorzahl 0:28:35 Aufbau der Bäume 0:29:21 Aufbau kleinerer Bäume(ohne Wurzel) 0:30:39 Kanten färben 0:33:32 Offene Frage: Parallele Färbung? 0:34:32 Jocken Speck's Lösung 0:35:55 Analyse 0:38:59 Implementierung im Simplex-Modell 0:40:39 23-Reduktion 0:41:10 Noch ein optimaler Algorithmus 0:42:05 Hyperwürfel Hd 0:43:15 ESBT-Broadcasting 0:44:50 Analyse, Telefonmodell 0:47:33 Diskussion 0:50:00 Reality Check 0:51:46 Broadcast für Bibliotheksimplementierer 0:52:57 Jenseits Broadcast 0:53:45 Sortieren

02 | 0:00:00 Starten 0:02:01 Analyse paralleler Algorithmen 0:02:17 PRAM vs. reale Parallelrechner 0:03:55 (Symmetric) Shared Memory 0:05:03 Probleme 0:07:22 Realistische Shared Memory Modelle 0:09:05 Atomare Instruktionen: Compare-And-Swap 0:09:17 Parallel External Memory 0:10:15 Modelle mit Verbindungsnetzwerken 0:11:13 Reale Maschinen Heute 0:11:40 Umgang mit komplexen Hierarchien 0:13:07 Explizites ,,Store-and-Forward'' 0:17:03 Diskussion 0:19:57 Typische Verbindugsnetzwerke 0:28:30 Vollständige Verknüpfung 0:34:17 Vollständige Verknüpfung: Varianten 0:37:14 BSP 0:40:35 Diskussion 0:49:19 Schaltkreise 0:51:23 Zusammenhang mit PRAMs 0:56:31 DAG-- Verbindungsnetzwerke 0:58:11 Beispiel: Assoziative Operationen (=Reduktion) 1:02:13 Beweisskize für n=2^k (oBdA?) 1:03:33 PRAM Code 1:10:02 Analyse 1:12:25 Weniger ist Mehr 1:17:44 Distributed Memory Machine 1:21:46 Analyse

03 | 0:00:00 Starten 0:00:10 Ein einfaches paralleles Modell: PRAMs 0:00:46 PRAM vs. reale Parallelrechner 0:01:33 Shared Memory 0:01:58 Modelle mit Verbindungsnetzwerken 0:02:23 Explizites ,,Store-and-Forward'' 0:04:17 Typische Verbindungsnetzwerke 0:04:37 Vollständige Verknüpfung 0:06:03 Graph- und Schaltkreisdarstellung v.Algorithmen 0:07:06 Schaltkreise 0:07:37 PRAM Code 0:10:03 Analyse 0:10:34 Weniger ist Mehr 0:11:09 Distributed Memory Machine 0:11:59 Analyse 0:12:22 Diskussion Reduktionsoperation 0:12:55 Analyse 0:13:58 Matrixmultiplikation 0:18:10 Ein erster PRAM Algorithmus 0:21:13 Verteilte Implementierung I 0:24:06 Verteilte Implementierung II-1 0:29:42 Verteilte Implementierung II-2 0:38:09 Analyse, Fully Connected u.v.a.m. 0:42:23 Diskussion Matrixmultiplikation 0:44:42 Broadcast (Rundruf?) und Reduktion 0:45:46 Broadcast --> Reduktion 0:46:43 Modellannahmen 0:47:15 Naiver Broadcast 0:50:22 Binomialbaum-Broadcast 0:56:34 Analyse 0:58:36 Lineare Pipeline 1:06:43 Diskussion 1:07:32 Procedure 1:10:58 Beispiel 1:13:51 Analyse 1:16:57 Fibonacci-Bäume 1:19:31 Analyse 1:24:08 Procedure 1:26:11 Analyse

01 | 0:00:00 Starten 0:01:22 Warum Parallelverarbeitung 0:05:36 Thema der Vorlesung 0:06:52 Überblick 0:09:05 Schwesterveranstaltungen 0:12:53 RAM/von Neumann Modell 0:14:17 Algorithmenanalyse 0:17:04 Ein einfaches paralleles Modell: PRAMs 0:19:52 Zugriffskonflikte 0:25:51 Beispiel: Global Or 0:27:30 Beispiel: Maximum auf common CRCW PRAM 0:33:07 Formulierung paralleler Algorithmen 0:35:13 Synchron versus asynchron 0:38:42 Analyse paralleler Algorithmen 0:45:01 PRAM vs. reale Parallelrechner 0:46:13 Shared Memory 0:47:43 Probleme 0:49:08 Realistische Shared Memory Modelle 0:54:15 Atomare INstruktionen: Compare-And-Swap 0:59:08 Weitere Operationen für konsistenten Speicherzugriff 0:59:44 Parallel External Memory 1:02:12 Modelle mit Verbindungsnetzwerken 1:03:03 Reale Maschinen Heute 1:06:40 Umgang mit komplexen Hierarchien