Vorlesung SS 05

(2 SWS Vorlesung,  Nr. 042783, 2 SWS Übung, Nr: 042784)

 

Verteilte numerische Algorithmen

Zeit:

            Montag:                     12:15-14:00 HG I, HS 2
            Donnerstag               16.15-12.00 GB IV R 13 

Veranstalter:

            Peter Buchholz (Tel.: (0231) 755 4746, Email: peter.buchholz@udo.edu)
            Sprechstunde: Donnerstag 10:00-11.30 und n.V.     GB V R 406a

Inhalt:

Die Analyse vieler komplexer natürlicher und technischer Systeme erfordert den Einsatz rechenintensiver numerischer Verfahren. Typische Anwendungsgebiete sind die Wetter- oder Klimavorhersagen, die Analyse von Meeresströmungen, die Optimierung des Luftwiderstands im Fahrzeugbau, die Dimensionierung von Puffern in Kommunikationssystemen und viele andere mehr. Für die meisten dieser Probleme sind Analysealgorithmen grundsätzlich bekannt, eine genügend genaue Analyse erfordert aber einen immensen Rechenaufwand, der den Einsatz von Multiprozessorsystemen oder mehreren lose gekoppelten Workstations notwendig macht. Um die Rechenkapazität dieser Systeme zu nutzen, müssen entsprechende Algorithmen verfügbar sein, die sich in vielen Fällen nicht unmittelbar aus sequentiellen Algorithmen herleiten lassen. Gerade im Bereich des wissenschaftlichen Rechnens, zu dem auch die genannten Anwendungsgebiete gehören, wurden effiziente und praktisch einsetzbare parallele Algorithmen in den letzten Jahren entwickelt. Im Rahmen der Vorlesung werden wir uns mit der Parallelisierung numerischer Algorithmen beschäftigen. Wegen der Breite des Gebiets kann nur ein kleiner Teilbereich behandelt werden. Als Voraussetzungen für die Realisierung numerischer Verfahren in verteilten Umgebungen ist ein Überblick über heute verfügbare Formen paralleler und verteilter Rechnersysteme notwendig. Ein solcher Überblick wird zu Anfang der Vorlesung gegeben. Weiterhin sind parallele und verteilte Algorithmen sehr stark vom verwendeten Programmiermodell abhängig. Insofern muss bei einer Beschäftigung mit der Parallelisierung von numerischen Algorithmen auch die konkrete Programmierumgebung einbezogen werden. Im Rahmen der Vorlesung wird deshalb ein Überblick über parallele Programmiermodelle gegeben. Dabei wird insbesondere auf die Programmierung über Message-Passing mit Hilfe der Bibliotheken MPI und PVM eingegangen. Auf Basis dieser Bibliotheken werden unterschiedliche Algorithmen eingeführt und in den Übungen praktisch realisiert. Der zweite Teil der Vorlesung beschäftigt sich mit der parallelen Realisierung konkreter numerischer Algorithmen aus unterschiedlichen Anwendungsgebieten. Für jedes Anwendungsgebiet werden  Analysealgorithmen vorgestellt und bzgl. ihrer Parallelisierbarkeit untersucht.

In den vorlesungsbegleitenden Übungen werden die eingeführten Techniken an Hand einfacher Beispiele praktisch angewendet.

 

Kapitelgliederung

Folienkopien werden im Laufe des Semesters verfügbar gemacht.

  1. Einführung und Übersicht (Folien: parnum_1.ps)
  2. Parallele Rechnerarchitekturen   (Folien: parnum_2.ps)
    1. Ebenen der Parallelität
    2. Speicherorganisation von Parallelrechnern
    3. Verbindungsnetzwerke
    4. Beispiele realer Systeme
    5. Workstationnetze und –cluster
    6. Die TOP 500 Liste
  3. Parallele Programmierung  (Folien: parnum_3.ps)
    1. Parallele Programmiermodelle
    2. Laufzeitanalyse paralleler Programme
    3. Programmierung mit gemeinsamen Variablen
    4. Message Passing Programmierung
      1. PVM
      2. MPI
  4. Verteilte numerischer Algorithmen (Folien: Teil1 parnum_4_1.ps, Teil2 parnum_4_2.ps)
  5.  
    1. Numerische Basisalgorithmen
    2. Lösung linearer Gleichungssysteme
    3. Lösung nichtlinearer Gleichungssysteme
    4. Schnelle Fourier-Transformation
    5. Einige Optimierungsmethoden
    6. Asynchrone Verfahren

Literaturhinweise:

Für die Vorbereitung der Vorlesung wurden insbesondere die folgenden Bücher verwendet:

Erwünschte Vorkenntnisse:

Wünschenswert, aber nicht zwingend vorausgesetzt sind Basiskenntnisse numerischer Mathematik.

 

Übungsblätter

·        Blatt 1

·        Blatt 2

·        Blatt 3

·        Blatt 4

·        Blatt 5 (Musterlösung)

·        Blatt 6 (Musterlösung)

·        Blatt 7

·        Blatt 8