50 Jahre Uni Lübeck

Institut für Theoretische Informatik

SS 2006 – Theorie paralleler und verteilter Systeme (PVS)


[ Art und Inhalt | Die Vorlesung | Die Übung ]

Art und Inhalt
Titel: Theorie paralleler und verteilter Systeme (PVS)
Veranstalter: Tantau
Einordnung: Diplom-Studiengang 6. Semester, Pflicht
Inhalt:

Veranstaltungslernziele

Die Veranstaltungslernziele sind:

  • Modellierung von parallelen und verteilten Systemen kennen
  • Parallele und verteilte Algorithmen kennen, erstellen und analysieren können
  • Grenzen der Parallelisierbarkeit kennen
  • Verteilte Systeme modellieren und spezifizieren können

Lernziele der einzelnen Vorlesungen und der zugehörigen Übungen

Vorbereitung

  • 1. VL: Einführung, Organisatorisches, Erwartungsabfrage

Parallele Systeme

  • 2. VL: Parallele Modelle Leitbild: Wie rechnet man parallel?
    1. Modell des DAGs kennen und anwenden können
    2. Modelle der PRAM kennen und anwenden können
    3. Modelle mit Netzwerkkommunikation kennen
    4. Vor- und Nachteile benennen können
  • 3. VL: Ressourcemaße bei parallelen Programmen Leitbild: Lohnt sich der ganze Aufwand?
    1. Die Ressourcen Zeit, Arbeit, Kosten, Speedup und Effizienz kennen
    2. Beziehungen unter diesen Ressourcen kennen
    3. Ressourceverbrauch von Algorithmen bestimmen können
    4. Optimalitätsbegriffe bei parallelen Algorithmen kennen
  • 4. VL: Einfache parallele Algorithmen Leitbild: Präfixsumme hilft immer
    1. Algorithmus für parallele Präfixsumme kennen
    2. Algorithmus Pointer-Jumping kennen
    3. Die Algorithmen in anderen Problemen anwenden können
  • 5. VL: Paralle Divide-and-Conquer Algorithmen Leitbild: Teile und Herrsche
    1. Divide-and-Conquer Algorithmus für die konvexe Hülle kennen
    2. Divide-and-Conquer Algorithmus für parallelen Merge-Sort kennen
  • 6. VL: Pipelining Algorithmen Leitbild: Arbeiter am Fließband
    1. Konzept des Pipelining verstehen und anwenden können
    2. Konzept des 2-3-Baumes verstehen
    3. Beispiel eines Pipelining Algorithmus kennen (Einfügen in 2-3-Bäume)
  • 7. VL: Accelerated-Cascading Leitbild: Gut und schnell
    1. Konzept des Accelerated Cascading verstehen und anwenden können
    2. Beispiel eines Accelerated-Cascading Algorithmus kennen (Maximum finden)
  • 8. VL: Aufbrechen von Symmetrien Leitbild: Alle Tiere sind gleich, aber manche sind gleicher als andere
    1. Problematik der Symmetrie kennen
    2. Einfachen 2-Färbealgorithmus kennen
    3. Schnellen und optimalen 3-Färbealgorithmus kennen
  • 9. VL: List-Ranking Algorithmen Leitbild: Bewerber in einer Reihenfolge bringen
    1. Problematik des List-Rankings kennen und anwenden können
    2. Schnellen und optimalen List-Ranking Algorithmus kennen
  • 10. VL: Auswerten von arithmetischen Ausdrücken Leitbild: Gemeinschaftliches Rechnen
    1. Algorithmen zur Blattsortierung in Bäumen kennen
    2. Konzept der Baumkontraktion kennen
    3. Schnelle und optimale Algorithmen zur Auswertung arithmetischer Ausdrücke kennen und eigene Erstellen können
  • 11.+12. VL: Paralleles Sortieren Leitbild: Gemeinschaftliches Sortieren
    1. Einfachen Merge-Sort kennen
    2. Bitonischen Merge-Sort kennen
    3. Coles Merge-Sort kennen
  • 13. VL: Boolesche Schaltkreise Leitbild: Die einfachsten Parallelrechner
    1. Formalisierung von Schaltkreisen kennen
    2. AC-, NC- und TC-Schaltkreisklassen kennen
    3. Verhältnis der Klassen kennen
    4. NC1-Additionsalgorithmus kennen
  • 14. VL: Multiplizieren und Dividieren Leitbild: Computer rechnen nicht so, wie wir es in der Schule gelernt haben
    1. NC1-Multiplikationsalgorithmus kennen
    2. NC2-Divisionsalgorithmus kennen
  • 15. VL: Verhältnis von Platz und Parallelisierbarkeit Leitbild: Wenig Platz = gut parallelisierbar
    1. Kleine Platz-Klassen wiederholen
    2. Logspace-Reduktion wiederholen
    3. Inklusionsstruktur der NC-Klassen und der kleinen Platzklassen kennen
  • 16.+17. VL: Grenzen der Parallelisierbarkeit Leitbild: Besser geht’s nicht
    1. Konzepte der unteren Schranke, des Vergleichsbaums und von Adversary-Argumenten kennen
    2. Untere-Schranken-Beweise für Comparison-PRAMS kennen und einfache führen können
    3. P-Schwere wichtiger Probleme kennen und einfache Härtebeweise führen können

Verteilte Systeme – Grundlegende Algorithmen

  • 18. VL: Verteilte versus parallele Systeme Leitbild: Von Agenten und Schwärmen
    1. Unterschiede zwischen parallen und verteilten Systemen benennen können
    2. Probleme für verteilte Systeme kennen
    3. Ressourcen für und Eigenschaften von verteilten Systeme kennen
  • 19.+20. VL: Leader-Election Leitbild: Von der Schwierigkeit, einen Kanzler zu wählen
    1. Das Leader-Election-Problem kennen
    2. Verteilte Algorithmen zur Leader-Election-Problem kennen
    3. Untere Schranken zum Leader-Election-Problem kennen
  • 21. VL: Sychronisationsprobleme Leitbild: Wir können nicht alle gleichzeitig drucken
    1. Das Mutex-Problem kennen
    2. Algorithmen für das Mutex-Problem kennen
  • 22. VL: Weitere verteilte Algorithmen

Verteilte Systeme – Spezifikation mittels Petrinetzen

  • 23. VL: Petrinetze Leitbild: Visualisierung von verteilten Systemen
    1. Konzept des Petrinetz kennen
    2. Formalisierung von Petrinetzen kennen
    3. Problemstellungen mit Petrinetzen beschreiben können
  • 24. VL: Netzdynamik Leitbild: Werden wir jemals unser Geld bekommen?
    1. Problemstellungen der Netzdynamik kennen
    2. Bezug zur Linearen Algebra kennen
    3. Netzdynamik analysieren können
  • 25.+26. VL: Weiteres zu Petrinetzen

Schluss

  • 27. VL: Zusammenfassung, Abschlussevaluation, Diskussion, Ausblick
Puffer: 2VL
Buchempfehlungen:
  • J. JaJa: An Introduction to Parallel Algorithms. Addison-Wesley, 1992.
  • N. Lynch: Distributed Algorithms. Morgan Kaufmann 1996
  • Z. Manna and A. Pnueli: The Temporal Logic of Reactive and Concurrent Systems. Springer 1992
  • W. Reisig: Elements of Distributed Algorithms : Modeling and Analysis with Petri Nets. Springer 1998

Vorlesung
Veranstalter: Tantau
Umfang: 4 SWS
Termine: Di, 14.00h – 16.00h und Fr, 08.30h – 10.00h, R3
Vorlesungkarte: Vorlesungskarte
Skripte:

„Vorläufiges Script“ zu den ersten sechs Kapitel. Weitere Kapitel werden im Laufe des Semesters zur Verfügung gestellt.
Evaluation: 09.05.2006
WS2005/06 und SS 2006

Übung
Veranstalter: Tantau, Balbach
Umfang: 2 SWS

Für Erlangung des Übungsscheins müssen folgende Leistungen erbracht werden:

  1. Bearbeitung der ein- bis zweiwöchentlichen Übungsblätter in Einer- bis Dreiergruppen. Auf allen bis auf zwei Übungsblättern muss die Hälfte der möglichen Punkte erreicht werden.
  2. Bestehen der mündlichen Rücksprache am Semesterende.
Termine: Mo. 12.00h – 14.00h, ITCS-Seminarraum 21, 2. OG. u. Seminarraum Informatik 1 und 2*, Geb. 64
Übungsblätter: