Nächste Seite:
Einleitung
Sprachkonzepte
der Parallelen Programmierung
Vorlesung
SS 11, WS 12, SS 13
Johannes Waldmann, HTWK Leipzig
Einleitung
Motivation
Inhalt
Organisation
Literatur
Klassische Nebenläufigkeit
Sicherer Datenaustausch
Atomare Objekte, ...in Datenstrukturen
Software Transactional Memory
Funktionales und paralleles Programmieren
Parallele Auswertungsstrategien
Funktionales und paralleles Programmieren
Algorithmik
Map/Reduce
Threads, Thread-Sicherheit
Threads erzeugen und starten
Gemeinsamer Speicher, Synchronisation
Übung: einfache Thread-Operationen in Java
Thread-Sicherheit: Definitionen
Zustandsänderungen
Object Confinement
Übung:
this
escapes during construction
Atomare Aktionen
Zusammengesetzte Aktionen
Locks
Granularität der Locks
Threads, Locks, Übung
Semaphore
Semaphore
Gegenseitiger Ausschluß (grundsätzlich)
Gegenseitiger Ausschluß (in Java)
Namen für Semaphore
Implizite und explizite Semaphore in Java
Beispiel: Philosophen in der Mensa
Modellierung des Ressourcenzugriffs
5 Philosophen: Aufgaben/Übung
Übung Semaphore
Spezifikation und Verifikation nebenläufiger Prozesse
Einleitung
Literatur
Kripke-Strukturen, Omega-Wörter
Omega-Wörter und -Sprachen
PLTL: propositional linear time logic
PLTL-Spezifikationen von Systemeigenschaften
PLTL: Algorithmen
ω
-(reguläre) Sprachen
Übung PLTL
Nicht blockierende Synchronsiation
Einleitung
Literatur
Compare-and-Set (Benutzung)
Compare-and-Set (Implementierung)
Compare-and-Set (JVM)
Non-Blocking Stack
Spezifikation f. Concurrent Stacks
Abstraktion, Linearisierbarkeit
Non-Blocking Queue (Problem)
Non-Blocking Queue (Lösung)
Non-Blocking Übung
Software Transactional Memory
Motivation/Plan
Beispiel: Kontoführung (I)
Beispiel: Kontoführung (II)
Beispiel: Kontoführung (III)
Locks are Bad
Speicher-Transaktionen
Nebenwirkungen in Haskell: IO a
Nebenwirkungen auf den Speicher
Transaktionen: STM a
Bedingungen und Auswahl
STM-Typen und -Operationen
The Santa Claus Problem
Philosophen mit STM
Verteiltes Zählen
Motivation
Spezifikation für Zählnetze
Folgerung aus Spezifikation für Zählnetze
Netzwerke aus Verteilern
Bitonisches Zählen und Zusammenfügen (I)
Bitonisches Zählen und Zusammenfügen (II)
Implementierung für Verteiler und Netze
Anwendungen von Zählnetzen
Übung Zählnetze
Lokale Prozeßkommunikation (I)
Motivation
Communicating Sequential Processes (CSP)
CSP: Syntax
CSP: Semantik (Spur-Semantik)
Verschiedene Prozeß-Semantiken
Ablehnungs-Semantik
Rendez-Vous (I) in Ada
Rendezvous (II)
Rendezvous (III)
Lokale Prozeßkommunikation (II)
Kommunikations-Kanäle
Kanäle in Haskell
Actors (Scala)
Good Actors Style
Rendezvous-Zusammenfassung
Übung: Kanäle in Go
Verteilte Programme
Verteiltes Rechnen
Erlang
Cloud Haskell: Übersicht
Cloud-Haskell: elementare Operationen
Parallele Auswertungsstrategien
Überblick
Algebraische Datentypen und Pattern Matching
Alg. Datentypen (Beispiele)
Bedarfsauswertung
Beispiel: Primzahlen
Beispiel: Mergesort
Parallel LINQ
Homomorphiesätze
Begriffe (allgemein)
Homomorphie-Sätze für Listen
Literatur
foldr, foldl, map, reduce
Beispiel: maximale Präfix-Summe
Schwache Inverse
Beweis 3. Homomorphie-Satz
Beispiel: Größte Teilsumme
Beispiel: Binäre Addition
Implementierung von Folgen
Implementierung Max.-Präfixsumme
Diskussion: Kommutativität
Das Map/Reduce-Framework
Schema und Beispiel
Literatur
Implementierungen
Implementierung in Haskell
Anwendung: Wörter zählen
Hadoop
Hadoop-Benutzung
Wörter zählen
Sortieren
Page Rank (I)
Page Rank (Eindeutigkeit)
Page Rank (Berechnung)
Übung Map/Reduce
Ausblick, Zusammenfassung
Ausblick: Hochparallele preiswerte Hardware
Komplexitätstheorie
Zusammenfassung
Über dieses Dokument ...
Johannes Waldmann 2013-06-18
