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: 11.4.2003
Zeit: freitags 11.15-12.45 Uhr
Ort: 3.04.0.02
Aktuelles:
    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: 
    • Halten eines verständlichen und übersichtlich strukturierten Vortrags (Folien, Powerpoint etc.) im Umfang von etwa einer halben Stunde über ein vorgegebenes Thema aus dem Themenbereich. Sie erhalten als Vorlage einen Zeitschriftenartikel oder ein Kapitel aus einem Buch. Bitte beachten Sie bei der Vorbereitung des Vortrags die Anleitungen zum wiss. Arbeiten.
    Sie erhalten eine Note gem. §10 der Prüfungsordnung. 
    Einen Überblick über Ihren aktuellen Leistungsstand erhalten Sie jederzeit auf diesem Server.

    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).

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