Teil I - Handwerkszeug des Parallelprogrammierers |
1. Introduction
-
Steigender Appetit, aber die Zukunft ist Multi-Core
-
Fach-Jargon
-
Basiswissen über Petri-Netze
|
2. Generation of parallelism in programs
-
Programmiersprachliche Konzepte (fork, join, cobegin, forall)
-
Aktivitätsfäden in Java:
Thread und Runnable , Zustände
-
Arbeitspakete;
ExecutorService
-
Future -Objekte und Ausdrücke
|
3. data synchronisation
-
Wettlaufsituationen
-
Gemeinsamer Zustand
-
Kritische Abschnitte
-
synchronized
-
Rechnen mit Petri-Netzen
|
4. thread-safety
-
Zusammenhang von Sichtbarkeit und Speichermodell
-
volatile und atomic
-
Flüchtende Objekte
-
Typische Fehler
|
5. liveness problems
-
Verklemmung
-
- Philosophen
-
- Bedingungen
-
- Gegenmaßnahmen
-
Verhungern
|
Teil II - Anwendungstypen und Effizienzfragen |
6. task-parallel approaches (1)
-
Einfache Task-Abhängigkeiten (Granularität)
-
Klient & Dienstleister (Mindestproblemgröße)
-
- Web-Server (Lastbalance)
-
Chef & Arbeiter (Arbeitspaktgröße)
-
- Seitenanzeige im Web-Browser (Speedup)
-
- Monte-Carlo-Simulation (Amdahl)
|
7. task-parallel approaches (2)
-
Arbeitsdiebstahl (Parallelitätsbegrenzung)
-
- Strahlverfolgung
-
Fließband, Produzent & Konsument (Fließbandgewinne)
-
- Dateisystemindizierung
-
Paralleles teile-und-herrsche (Mindestnutzarbeit)
-
- Fibonacci (Umstiegspunkte)
-
- Sortieren durch Mischen
-
- Suchraumdurchforstung
|
8. data-parallel approaches (1)
-
Geometrische Dekomposition
-
- Grafikfilter
-
Synchronisationsbarriere
-
Turnier-Ansatz zur Reduktion (Lemma von Brent)
-
- Maximumssuche im Feld (Schneller trotz Mehrarbeit)
-
- Summe aller Feldelemente
-
Paralleler Algo. von Prim
-
Paralleler Algo. von Dijkstra
|
9. data-parallel approaches (2)
-
Verzeigerte Datenstrukturen
-
- Zeigerverdopplung
-
Deklarativer Ansatz: MapReduce
-
Konzept
-
Anwendungsbeispiele
-
- Algo. von Dijkstra
-
- Web-Seitenwichtigkeit
|
Teil III - Funktionale Programmierung |
10. Introduction and Basics
-
Einführung und Motivation
- Nebenwirkung / Werttreue
- Funktionale vs. imperative Programmierung
-
Funktionale Programmierung (mit Scala)
- Datentypen (Liste, Tupel, String, Funktion)
- Currying und Sektionen
- Bedingte Ausdrücke
- Mustervergleich (Pattern Matching)
- Mengenabstraktionen, Generatoren, Wächter (Guards)
|
11. Main Features of Functional Programming
-
Funktionale Programmierung (mit Scala) - Fortsetzung
- Funktionen höherer Ordnung
- Bedarfsauswertung (Lazy Evaluation)
- Ströme: „unendliche“ Datenstrukturen mit Stream
-
Eigene Datentypen
- Type Aliasing
- Aufzählungsdatentypen
- Algebraische Datentypen (case class / object)
|
12. Parallelization
-
Datenstrukturen: Parallel Immutable Collection
-
Kontrollfluss: Future
-
Spezialkonzept: Actor
|
13. Functional programming - illustrated
-
Vergleich: Scala vs. Java 8
-
Anwendungsbeispiele zu MapReduce
- Googles MapReduce / Apache Hadoop
- Dijkstra mit MapReduce
|