Uni-GH Paderborn - Informatik

---

Seminar
Parallele Algorithmen für realitätsnahe Rechenmodelle

Professor
Friedhelm Meyer auf der Heide

Mitarbeiter
Armin Bäumker, Wolfgang Dittrich, Ingo Rieping

Abgabe der Ausarbeitungen:
Spätestens 06.01.1996

Seminarvorträge:
Freitag, 17.01.1996, 9:00 Uhr (c.t.)
gegebenenfalls wird bereits am Donnerstag (16.01.) begonnen

Teilnehmer:

• Oliver Pettenpaul (topper), PRAM Techniken (Valiant/Shiloach/Vishkin), Betreuer Friedhelm Meyer auf der Heide
  
• Markus Bornefeld (mabo), Das BSP Modell, Betreuer: Ingo Rieping
  
• Francisco Cortes (cortes), Samplesort auf dem BSP Modell, Betreuer: Ingo Rieping
  
• Christian Rüther (ruether), Kommunikationseffizientes Paralleles Sortieren (Goodrich), Betreuer: Armin Bäumker
• Andreas Grote (grote), Realitätsnahe geometrische Algorithmen, Betreuer: Wolfgang Dittrich
  

Inhaltsübersicht:
Beim Algorithmenentwurf ist die Wahl des zugrundeliegenden Rechenmodells entscheidend für die Effizienz des Algorithmus auf realen Maschinen. Das Rechenmodell sollte soweit von der realen Maschine abstrahieren, daß man sich bei der Algorithmenentwicklung auf Wesentliches konzentrieren kann, ohne sich in Details zu verlieren. Andererseits sollte das Rechenmodell alle effizienzkritischen Aspekte von realen Maschinen erfassen. Im Bereich der sequentiellen Algorithmen stellt das RAM-Modell einen gelungenen Kompromiß hinsichtlich des Abstraktionsniveaus dar. Im Bereich der parallelen Algorithmen ist das PRAM-Modell sehr populär. Dieses Modell abstrahiert jedoch so stark von realen Parallelrechnern, daß die in diesem Modell entwickelten Algorithmen nur bedingt für den praktischen Einsatz tauglich sind. In letzter Zeit findet man in der Literatur häufig Vorschläge für alternative parallele Rechnermodelle, die eine bessere Beschreibung realer Parallelrechner bieten. In diesem Seminar sollen Arbeiten vorgestellt werden, die sich mit Algorithmen für solche "realitätsnahen" parallelen Rechenmodelle beschäftigen.
Das Seminar teilt sich in drei thematische Bereiche auf. Im ersten Teil werden klassische Parallelisierungstechniken für einige wichtige und grundlegende Probleme behandelt. Das zugrundeliegende Rechenmodell ist die PRAM. Hier geht es vor allem darum, zu zeigen, daß parallele Problemlösungen mitunter völlig andere Techniken erfordern als die aus dem sequentiellen Bereich bekannten. Im zweiten Teil werden die oben erwähnten "realitätsnahen" parallelen Rechenmodelle vorgestellt und miteinander verglichen. Im dritten Teil werden dann Algorithmen für realitätsnahe parallele Rechenmodelle vorgestellt.

Anfragen an:
Armin Bäumker (Tel. 606451),
Wolfgang Dittrich (Tel. 606451)
Ingo Rieping (Tel. 606452)
Büro F1.203

Voraussetzungen:
Vordiplom

Scheinerwerb:
Ausarbeitung, Seminarvortrag und aktive Teilnahme

Prüfungsgebiet:
H II: Theoretische Informatik

Parallelveranstaltungen:
Vorlesung Parallele Algorithmen

Literatur zu den Seminarthemen:

• Teil I: Parallele algorithmische Techniken
  • Leslie G. Valiant
    Parallelism in comparison problems
    SIAM Journal on Computing, Nr.3, Band 4, pp. 348-355, 1975
    
    Yossi Shiloach, Uzi Vishkin
    Finding the maximum, merging, and sorting in a parallel computation model
    Journal of Algorithms, 1981
    
    
  • M. Luby
    A Simple Parallel Algorithm for the Maximal Independent Set Problem
    SIAM Journal on Computing, 1986
    
    
  • Ketan Mulmuley, Umesh V. Vazirani, Vijay V. Vazirani
    Matching is as easy as matrix inversion
    Combinatorica, pp. 105-113, 1987
    
    
  • L. Csanky
    Fast parallel matrix inversion algorithms
    SIAM Journal on Computing, Nr.5, pp. 618-623, 1976
    

• Teil II: Modelle
  • Alok Aggarwal, Ashok K. Chandra, Marc Snir
    Communication complexity of PRAMs
    Theoretical Computer Science, pp. 3-28, 1990
    
    
  • Gibbons, Matias, Ramachandran
    The QRQW PRAM: Accounting for Contention in Parallel Algorithms
    Proc. of 5th SODA, 1994
    
    
  • Alexandros V. Gerbessiotis, Leslie G. Valiant
    Direct bulk-synchronous parallel algorithms. Teil 1: Das Modell
    Technischer Bericht, 1992
    
    W. F. McColl
    A BSP realisation of Strassen's algorithm
    In: Abstract Machine Models for Parallel and Distributed Computing,
    IOS Press, Niederlande, 1995
    
    
  • G. Bilardi, K. T. Herley, A. Pietracaprina, G. Pucci, P. Spirakis
    BSP vs LogP
    Proc. of 8th SPAA, 1996
    
    Culler, Karp, Patterson, Sahay, Schauser, Santos, Subramonian, von Eicken
    LogP: Towards a Realistic Model of Parallel Computation
    ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming: PPOPP

• Teil III: Realitätsnahe Algorithmen
  • M. T. Goodrich
    Communication-Efficient Parallel Sorting
    Proc. of 28th STOC, 1996
    
    
  • Frank Dehne, Andreas Fabri, Andrew Rau-Chaplin
    Scalable parallel geometric algorithms for coarse grained multicomputers
    Technischer Bericht, 1992
    
    
  • Olivier Devillers and Andreas Fabri
    Scalable algorithms for bichromatic line segment intersection problems on coarse grained multicomputers
    Proc. 3rd Workshop on Algorithms and Data Structures WADS, 1993
    
    
  • S. Sahni, J. Woo
    Computing biconnected components on a hypercube.
    The Journal of Supercomputing, Nr.5, 1991
    
    
  • Alexandros V. Gerbessiotis, Leslie G. Valiant
    Direct bulk-synchronous parallel algorithms. Teil 2: Sortieren
    Technischer Bericht, 1992
    
    
  • A. Bäumker, W. Dittrich, F. Meyer auf der Heide.
    Truly Efficient Parallel Algorithms: 1-Optimal Multisearch for an Extension of the BSP model
    Technischer Bericht, 1996
    
    
  • A. Bäumker and W. Dittrich
    Parallel Algorithm for Image Processing: Practical Algorithms with Experiments.
    Proc. of the 10th IPPS, pp. 429-433, 1996
    
    D.A. Bader, J. JaJa.
    Parallel Algorithms for Image Histogramming and Connected Components with an Experimental Study.
    Proc. of 5th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 1995