Nächste Seite:
Einleitung
Sprachkonzepte
der Parallelen Programmierung
Vorlesung
Wintersemester 2011
Johannes Waldmann, HTWK Leipzig
Einleitung
Motivation
Inhalt
Klassische Nebenläufigkeit
Sicherer Datenaustausch
Software Transactional Memory
Funktionales und paralleles Programmieren
Parallele Auswertungsstrategien
Funktionales und paralleles Programmieren
Algorithmik
Map/Reduce
Data Parallelism
Threads, Thread-Sicherheit
Einleitung, Definitionen
Zustandsänderungen
Object Confinement
Übung:
this
escapes during construction
Atomare Aktionen
Zusammengesetzte Aktionen
Locks
Granularität der Locks
Warteschlangen
Beispiel: Philosophen in der Mensa
Modellierung des Ressourcenzugriffs
Petri-Netze
Einleitung
Definition: Netz
Zustände, Übergänge
Petri-Netze modellieren...
Sprache eines Netzes
Kapazitäten und -Schranken
Bedingung/Ereignis-Netze
Transitionen in Java
Lokale Prozeßkommunikation
Motivation
Rendez-Vous (I) in Ada
Rendezvous (II)
Rendezvous (III)
Actors (Scala)
Kommunikations-Kanäle
Rendezvous-Zusammenfassung
Communicating Sequential Processes
Einleitung
Die Prozeß-Algebra (Syntax)
Die Prozeß-Algebra (operationale Semantik)
Sequentielle Komposition
Nebenläufige Komposition
Iteration (Rekursion)
Endliche Systeme
Spur-Semantiken
Spur/Ablehnungs-Semantik
Divergenz
CSP-Literatur
Ableitungen (1)
Ableitungen (2)
Ableitungen (3)
Ableitungen (4)
Ableitungen (5)
Beschränkte Rekursion
Bisimulation von Prozessen
Plan
Definition
Beispiele, Kommentar
Bestimmung einer Bisimulation (Plan)
Bestimmung einer Bisimulation (Impl.)
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)
Das ABA-Problem
Elimination Tree Stack
Semantik von nebenläufigen Stacks
Elimination Array
Baum von Stacks
Baum mit Eliminatoren
Software Transactional Memory
Einleitung
Literatur zu STM
Plan
Beispiel (ohne STM)
Beispiel (mit STM)
STM-Typen und -Operationen
Philosophen mit STM
STM in Clojure (Beispiele)
STM in Clojure (Sicherheit)
Transaktion mit Nebenwirkung
STM und persistente Datenstrukturen
Ameisen
Ameisen (Modell)
Ameisen (Aufgabe)
Ameisen (Haskell) (Vorbereitung)
Ameisen (Haskell) (Aufgaben)
Ameisen (Haskell) (Diskussion)
Parallele Auswertungsstrategien
Überblick
Beispiel: Primzahlen
Beispiel: Mergesort
Algebraische Datentypen und Pattern Matching
Alg. Datentypen (Beispiele)
Bedarfsauswertung
Verifikation funktionaler Programme
Term-Gleichungen
Append ist assoziativ
Verifikation -- Beispiele
Rekursionsmuster
.
Rekursion über Bäume (Beispiele)
Rekursion über Bäume (Schema)
Anonyme Funktionen
Rekursion über Listen
Rekursionsmuster (Prinzip)
Rekursion über Listen (Übung)
Fold/Besucher in C#
Besucher-Muster für Bäume
Beispiel: Baum-Besucher
Homomorphiesätze
Begriffe (allgemein)
Homomorphismen von Listen
Literatur
foldr, foldl, reduce
Beispiel: maximale Präfix-Summe
Schwache Inverse
Intel Manycore Testing Lab
Beweis 3. Homomorphie-Satz
Beispiel: Größte Teilsumme
Implementierung von Folgen
Implementierung Max.-Präfixsumme
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)
Ausblick, Zusammenfassung
Data Parallelism
Parallel Linq
Komplexitätstheorie
Zusammenfassung
Über dieses Dokument ...
Johannes Waldmann 2011-06-29
