Nächste Seite:
Einleitung
Sprachkonzepte
der Parallelen Programmierung
Vorlesung
SS 11, WS 12
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
Einleitung, Definitionen
Zustandsänderungen
Object Confinement
Übung:
this
escapes during construction
Atomare Aktionen
Zusammengesetzte Aktionen
Locks
Granularität der Locks
Spezifikation und Verifikation nebenläufiger Prozesse
Einleitung
Literatur
Kripke-Strukturen, Omega-Wörter
Omega-Wörter und -Sprachen
PLTL: propositional linear time logic
PLTL: Algorithmen
PLTL-Spezifikationen von Systemeigenschaften
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
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
Nicht blockierende Synchronsiation
Einleitung
Literatur
Compare-and-Set (Benutzung)
Compare-and-Set (Implementierung)
Compare-and-Set (JVM)
Non-Blocking Stack
Non-Blocking Queue (Problem)
Non-Blocking Queue (Lösung)
Verteiltes Zählen
Verteiler, Netzwerke
Bitonisches Zählen und Zusammenfügen (I)
Bitonisches Zählen und Zusammenfügen (II)
Bitonisches Zählen und Zusammenfügen (Aufgaben)
Lokale Prozeßkommunikation
Motivation
Communicating Sequential Processes (CSP)
CSP: Syntax
CSP: Semantik (Spur-Semantik)
Rendez-Vous (I) in Ada
Rendezvous (II)
Rendezvous (III)
Kommunikations-Kanäle
Actors (Scala)
Good Actors Style
Rendezvous-Zusammenfassung
Verteilte Programme
Verteiltes Rechnen
Erlang
Cloud Haskell: Übersicht
Cloud-Haskell: elementare Operationen
Übungsaufgabe zu Prozessen
50 Gefangene
Denksport
Parallele Auswertungsstrategien
Überblick
Algebraische Datentypen und Pattern Matching
Alg. Datentypen (Beispiele)
Bedarfsauswertung
Beispiel: Primzahlen
Beispiel: Mergesort
Parallel LINQ
Verifikation funktionaler Programme
Term-Gleichungen
Append ist assoziativ
Verifikation -- Beispiele
Rekursionsmuster
.
Rekursion über Bäume (Beispiele)
Rekursion über Bäume (Schema)
Rekursion über Listen
Rekursionsmuster (Prinzip)
Rekursion über Listen (Übung)
Fold/Besucher in C#
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-02-01
