Parallele und Verteilte Programmierung
Dimensionen der Paralleltät
Dimension I: Was wird auf mehrere Prozessoren verteilt ?
Daten
leichter Parallelismus (Farm-Parallelismus/Bauernhof-Parallelismus)
- Charaktristik
- Es besteht keinerlei Abhängigkeit zwischen den Teilen
- Lösungsstrategie
- Master-Slave: Ein Masterprozess verteilt die Arbeiten an Arbeitsprozesse,
die ihre Ergebnisse dann wieder an den Master zurückmelden.
- Eigenschaften:
-
- Kommunikation erfolgt nur zwischen dem Master und den Sklaven
- Master kann seine Sklaven voll auslasten
- hohe Effizienzen
- Anwendungen
-
- Parameterparallität: Eine Funktion wird mit verschiedenen Parametern berechnet
Zahlentheoretische Aufgaben wie Primzahlzerlegung und ihre praktischen Anwendung: Paßwortknacken
- Hochenergiephysik: Simulationen auf vielen Ereignismengen
- Monte Carlo-Simulationen
- Datenbanken: Mehrere Transaktionen
Geometische Parallelität
- Charakteristik
- Es gibt eine geometische Struktur auf dem Datenraum, der in kleine Teile zerlegt werden kann. Es besteht aber lokale Abhängigkeiten zwischen einem Teil und seinem unmittelbaren Nachbarn
- Lösungsstrategie
- Jede region wird einem Prozessor zugeteilt. Nach jeder Iteration wird derAustausch der Randdaten zwischen benachbarten Regionen vorgenommen
- Eigenschaften
- Wenn die Last zwischen den prozessoren gleichmäßig verteilt wird, und die Granularität nicht zu klein ist, können gute Effizienzen erziehlt werden.
- Anwendungen
-
Iterative Lösung von Gleichungssystemen, die aus ellitischen Differenzialgleichungen resultieren:
- Strömungsmechanik
- Elektrodynamik
- Werkstoffwissenschaften
Long Range Parallelität
- Charakteristik
- Der zu berechnete Zustand eines Teils hängt von dem vorhergehenden Zuständen aller berechneten Teile im System ab
- Lösungsstrategie
- Die teile werden gleichmäßig auf den Prozessoren verteilt. Die Daten eines Teils werden zu jedem Prozessorgesandt. Jeder Prozessor sammelt und berechnet die Effekte die auf die anderen Teile zurückzuführen sind.
Meist werden die Prozessoren dazu in einem Ring angeordnet, und die Emfangenen nachrichten vom Vorgänger an den nachfolger im Ring weitergeleitet. Bei symetrischen effakten braucht eine Nachricht nur dieHälfte der Prozessoren zu besuchen.
- Eigenschaften
- hoher kommunikationsaufwend und niedirge Effizienzen
- Anwendungen
-
- n-Körperproblemin der Astronomie
- Simmulation von Vielteilchenmodellen in der Molekulardymanik
- Charakteristik
- Die Daten wandern von einer Station zur nächsten
- Lösungsstrategie
- Der Algorithmus wird in Teile zerlegt. Jeder Prozessor berarbeitet seinen Teil und liefert die Daten an seinen Nachfolger weiter
- Eigenschaften
- unregelmäßige Struktur
- Anwendungen
-
- Fließbandfertigung in der Automobilindustrie
- UNIX-Pipelines
Dimension 2: Wann wird verteilt ?
statische Parallität
- Charakteristik
- Die Verteilung der Aufgaben erfolgt zur Designzeit und ändert sich nicht
dynamische Parallelität
- Charakteristik
- Neue Prozesse werden anhängig von den Daten generiert
- Lösungsstrategie
-
Wenn ein Prozeß arbeitslos wird, übernimmt er von anderen Aufgaben
- Anwendungen
-
- sog. kümstliche Inteligenz, bei der die teile- und Herrsche-Strategie ein Problem zur Laufzeit in Teilprobleme zerlegt wird.
Dimension 3: Granularität
Die Granularität ist das Maß, wieviele Rechenoperationen ausgeführt werden, bevor kommuniziert wird.
- Suboperationsebene (Vektorbefehle)
- Instruktionsebene (Datenflußrechner, Superskalarrechner)
- Blockebene (Parallelsierung von Schleifen)
- Prozeßebene (Multitasking)
- Programmebene (Rechenzentrumsbetrieb)
Erkenntnis: In einem Lösungsverfahren können verschiedene Phasen verschiedene Parallelität haben. So hat ein Gleichungslöser während derIteration geometische Parallelität, die Berechnung des globalen Residuums hat Long Range Paralelität.
Literatur
- [Wads92]
- Chris Wadsworth:"Who shold think Parallel ?" in "Software for Parallel Computers", ed by P.H.Perrot, London u.a: Chapman Hall, 1992
Informatik- und Netzwerkverein Ravensburg e.V
RW