CS 652 - Parallele und verteilte Algorithmen
12 113 11652 Parallele und verteilte Algorithmen
Prof. Dr. R. Loogen
Mi, 13.30 - 14.10 Uhr, HS IV (Lahnberge)
Do, 09.15 - 11.00 Uhr, HS IV (Lahnberge)
Beginn: 18. April 2007
Achtung: In der letzten Juni-Woche wird die Vorlesung von der Gastdozentin Prof. Dr. Yolanda Ortega-Mallén aus Madrid gehalten. Die Vorlesungstermine sind wie folgt:
Dienstag, 26. Juni 2007, 16.15 - 18.00 Uhr, HS IV, Lahnberge
Donnerstag, 28. Juni 2007, 9.15 - 10.00 Uhr, HS IV, Lahnberge
Übungen Mo, 11:15 - 13:00 Uhr, HS I (Lahnberge), Jost Berthold
Mo, 14.15 - 16.00 Uhr, HS III (Lahnberge), Mischa Dieterle
Beginn: 23. April 2007, HS IV
Fachgebiet Klassifikation Semester Leistungspunkte Skript
Informatik Hauptstudium, Theoretische Informatik >=3 7 nein

Voraussetzungen: Grundkenntnisse in Informatik und Mathematik
Scheinkriterien: Es kann nur ein benoteter Schein erworben werden und zwar durch
  1. aktive Teilnahme an den Übungen
  2. Bearbeitung von mindestens 50 % der Übungsaufgaben, Abgabe in Zweiergruppen
  3. erfolgreiche Präsentation der Lösungen von mindestens zwei Übungsaufgaben
  4. Bestehen einer Klausur oder eines Kolloquiums

Klausurtermin: Donnerstag, 19.7.2007, 9:00 bis 10:30 im HS IV
Ergebnisse: siehe Aushang gegenüber dem Sekretariat D5
Klausureinsicht Di., 24.7.07, 10 Uhr, in SR V (D5)
Übungsblätter:
...erscheinen donnerstags und enthalten schriftliche Aufgaben und Programmieraufgaben.
Die Aufgaben sind am darauffolgenden Donnerstag in Papierform abzugeben, Programme zusätzlich per E-Mail. Vor den Feiertagen Christi Himmelfahrt (17.5.) und Fronleichnam (7.6.) wird bereits am Mittwoch abgegeben.
Blatt 1, 19.04.2007 (Postscript, PDF)
Blatt 2, 26.04.2007 (Postscript, PDF)
Blatt 3, 03.05.2007 (Postscript, PDF) Shuffle-Exchange-Version
Blatt 4, 10.05.2007 (Postscript, PDF) Abgabe bereits am Mittwoch (Christi Himmelfahrt) Laufzeitdaten zu Aufgabe 1
Blatt 5, 16.05.2007 (Postscript, PDF) Bearbeitungszeit: 2 Wochen Odd-Even-Transposition Sort
Blatt 6, 31.05.2007 (Postscript, PDF) Abgabe bereits am Mittwoch (Fronleichnam)
Blatt 7, 06.06.2007 (Postscript, PDF) Ausgabe: Mittwoch
Blatt 8, 14.06.2007 (Postscript, PDF)
Blatt 9, 21.06.2007 (Postscript, PDF)
Blatt 10, 28.06.2007 (Postscript, PDF)
Blatt 11, 05.07.2007 (Postscript, PDF) letztes schriftliches Übungsblatt
Blatt 12, 12.07.2007 (Postscript, PDF) mündliche Aufgaben

Software für die Übungen:
Üblicherweise werden parallele Algorithmen zur Laufzeitbeschleunigung eingesetzt und entsprechend von Experten in für Cluster-Systeme geeigneten Sprachen entwickelt, in der Regel unter Linux. Häufig werden etablierte imperative Sprachen wie Fortran und C sowie geeignete Middleware zur Kommunikation und Synchronisation eingesetzt. Fortgeschrittene Programmiersprachen zur Parallelverarbeitung wie Skelettbibliotheken und parallel-funktionale Sprachen nutzen abstraktere Konzepte zur Konzentration auf den Algorithmus.

Für die Programmieraufgaben kommen Linux als Betriebssystem und Sprachen mit MPI-Anbindung (C und Fortran, evtl. Java) sowie paralleles Haskell infrage.
Nachfolgend Links zu MPI, C-Programmierung, Java-Anbindung von MPI und Eden (paralleles Haskell). Im ersten Tutorium können Fragen zur Benutzung und Konfiguration der Werkzeuge geklärt werden. Bei Problemen können Sie sich an den Tutor wenden.

MPI (Message Passing Interface): Der MPI-Standard (siehe auch unter wikipedia) definiert ein Interface für den Datenaustausch mit verteiltem Speicher. Im wesentlichen sind zwei Implementierungen relevant:
  • Open MPI (am Fachbereich: /app/lang/parallel/openmpi-1.2) ist aus verschiedenen Implementierungen vergangener Jahre hervorgegangen, unter anderem aus Los-Alamos-MPI und LAM-MPI (letzere ebenfalls am Fachbereich unter /app/lang/parallel zu finden)
  • Daneben gibt es MPICH, die erste Implementierung überhaupt. Federführende Autoren des Standards waren hier beteiligt.

Java-MPI binding: Eine Anbindung von Java an MPI ist problematisch, da MPI insgesamt nicht objektorientiert ist. Gleichwohl gab und gibt es Bemühungen, diese Anbindung zu realisieren, weil damit (unter Umständen, je nach Implementierung) die erzeugten Programme von vorn herein plattformunabhängig würden.
In den Übungen kann MPJ ausprobiert(!) werden, entsprechende Dateien befinden sich unter /app/lang/parallel/mpj.

Zusätzliches Material - lokal:

C-Programmierung: (Wikipedia: Infos über die Sprache C)
Es gibt unzählige Webseiten, die bei der Programmierung in C helfen können.
Explizit genannt sei hier (willkürlich ausgewählt): Material von wikibooks(nicht sehr ausführlich), ein Online-Buch, eine kürzere Zusammenfassung, der Online Kurs C++ (was eigentlich nicht C ist!) unseres Fachbereichs, sowie der Obfuscated C Code Contest.

Paralleles Haskell: Die Sprache Eden realisiert ein explizit paralleles Haskell. Es können Prozessabstraktionen (über die zu berechnende Funktion) definiert und instanziert werden. Prozesskommunikation ist weitgehend automatisiert, aber auch explizit beeinflussbar. Bei Interesse wenden Sie sich an den Tutor.

Literatur:
  • A. Gibbons, W. Rytter: Efficient Parallel Algorithms, Cambridge University Press 1988
  • Ananth Grama, Anshul Gupta, George Karypis: Introduction to Parallel Computing, Addison Wesley; 2. Auflage, 2003.
  • Michael J. Quinn: Parallel Programming in C with MPI and OpenMP, Mc Graw Hill 2003.
  • F. Thomas Leighton: Introduction to parallel algorithms and architectures: arrays, trees, hypercubes. Morgan Kaufmann Publishers 1992
  • G. Tel: Introduction to Distributed Algorithms, Cambridge University Press 2000.
Links: Sort Benchmark Homepage
Übersicht Sequentielle und parallele Sortierverfahren (FH Flensburg)
NowSort
Demo Sortieralgorithmen

Inhalt: Nach einer Einführung in die Grundbegriffe der Parallelverarbeitung werden zunächst elementare parallele Algorithmen diskutiert. Anschließend werden parallele Algorithmen für verschiedene Problemklassen wie Sortieren, Matrizen-Operationen, Graphenverfahren behandelt. Außerdem werden verteilte Basisverfahren wie Schnappschussverfahren, Terminationserkennung, Garbage Collection und Verfahren für verteilte Probleme wie das n-Körper-Problem vorgestellt. In den begleitenden Übungen sollen verschiedene Verfahren in parallelen Sprachen implementiert werden. Als Plattform dienen voraussichtlich MPI mit C und eventuell Java unter Linux und Eden (paralleles Haskell).

Zuletzt geändert: Wednesday, 17-Oct-2007 11:57:57 CEST