Suche Home Einstellungen Anmelden Hilfe  

UNI Didaktik der
Informatik		 DdI

Spezialvorlesung
"Parallele Algorithmen"

Veranstalter: Prof. Dr. Andreas Schwill
Zielgruppe: Hauptstudium
Umfang: 2 SWS Vorlesung, Übung nach Bedarf
Informatikfach-
zuordnung:		 Theoretische Informatik
Leistungspunkte: 3 benotete Punkte
Beginn: 24.4.2009
Zeit: freitags 14.00-16.00 Uhr
Ort: H01
Aktuelles: Am 19.6. findet die Vorlesung abweichend in Raum 3.01.H09 statt.
    Inhaltsübersicht
    Die gängigen zur Zeit verfügbaren Rechnersysteme stoßen mehr und mehr an  Leistungsgrenzen, die durch einen physikalischen Grenzwert vorgegeben werden: Ein Signal kann von einem Verarbeitungselement zu einem anderen nicht schneller als mit Lichtgeschwindigkeit transportiert werden. Durch Miniaturisierung der Bauelemente können die Distanzen und damit die Übertragungszeiten zwischen Verarbeitungselementen zwar noch verringert werden, die dadurch absehbaren Leistungssteigerungen betragen jedoch "nur" noch einige wenige Zehnerpotenzen.
    Eine nennenswerte weitere Beschleunigung der Rechengeschwindigkeit scheint mit den üblichen Rechnern auf der Basis der Von-Neumann-Architektur nicht möglich. Als einziger Ausweg wird die Parallelverarbeitung genannt: Mehrere Prozessoren arbeiten gleichzeitig an einem Problem. Bei einer in Zukunft zu erwartenden Verknüpfung von 1.000.000 und mehr Prozessoren ergibt sich so ein weiterer beachtlicher Leistungszuwachs. Diese Steigerung setzt jedoch voraus, daß das zu lösende Problem in irgendeiner Weise parallelisierbar ist, d.h. auf die Prozessoren verteilt werden kann. Dies scheint jedoch nicht bei allen Problemen möglich zu sein.
    Wir befassen uns in der Vorlesung mit Problemen, die effizient und nicht effizient parallelisierbar sind, und mit typischen Lösungsverfahren.
    Inhalte:
    • Maschinenmodelle (SIMD, MIMD, PRAM, Hypercube)
    • Parallelisierungstechniken (Binärbaummethode, list ranking, pointer doubling, parallel prefix, symmetry breaking)
    • Auswertung arithmetischer Ausdrücke
    • VLSI-Algorithmen
    • Färben von Graphen
    • Sortieren
    • Komplexitätsklassen
    Leistungserfassungsprozeß
    Die Abschlußnote wird durch folgenden Prozeß ermittelt: 
    • Mündliche Prüfung im Umfang von etwa 20 Minuten über den Stoff der Vorlesung. Der Prüfungstermin wird gegen Ende des Semesters festgelegt.
    Sie erhalten eine Note gem. §10 der Prüfungsordnung. 

    Belegung
    Die Belegung erfolgt elektronisch entsprechend der Bestimmungen des Instituts für Informatik.

    Literaturhinweise

    • B. Monien, J. Schulze, S. Grothklags: Parallele Algorithmen, Skriptum Uni Paderborn, 2001 (mit umfangreichem Literaturverzeichnis)
    • P. Chaudhuri: Parallel algorithms, design and analysis, Prentice-Hall 1992
    • A. Gibbons, W. Rytter: Efficient parallel algorithms, Cambridge Univ. Press 1988
    • J. JaJa: Introduction to parallel algorithms and architectures, Addison-Wesley 1992
    Skriptum
    • Als Begleitmaterial zur Vorlesung eignet sich o.g. Skriptum von B. Monien et al. von der Uni Paderborn.
    Note: §10 der Prüfungsordnung bestimmt die Form der Noten: Zulässig sind 1,0 bis 4,0 mit Zwischennoten sowie 5,0 (= nicht bestanden, kein Erwerb von Leistungspunkten).

info  Ankündigung SS 2003
info  Ankündigung SS 2006
info  Parallel algorithms - G.E. Blelloch/B.M. Maggs - 1998
M.J. Atallah (ed.), Handbook of Algorithms and Theory of Computation, CRC Press, Boca Raton, FL, 1998
info  Parallele Algorithmen - B. Monien/J. Schulze/S. Grothklags - 2001
Skriptum zur gleichnamigen Vorlesung an der Universität Paderborn
info  Parallele Algorithmen - E. Speckenmeyer - 2005
Skriptum zur geleichnamigen Vorlesung an der Universität zu Köln
info  Übersicht über den Leistungsstand aller Teilnehmer - SS2003
info  Vortragsvorlagen Nr. 1-8 - 2003
Die Vorträge sind durchnumeriert und durch Striche voneinander abgegrenzt.
info  Vortragsvorlagen Nr. 9-16 - 2003
Die Vorträge sind durchnumeriert und durch Striche voneinander abgegrenzt.

Benutzer: gast • Besitzer: schwill • Zuletzt geändert am: