Verteilte und Parallele Programmierung

Einführung in die verteilte und parallele Datenverarbeitung

Verteilte vs. Parallele Systeme

Verteiltes System

Ein verteiltes System ist eine Sammlung von lose gekoppelten Prozessoren oder Computern, die über ein Kommunikationsnetzwerk miteinander verbunden sind (Multicomputer).

• Speichermodell: Verteilter Speicher → Jeder Prozessor verfügt über privaten Speicher
• Kommunikation: Nachrichtenbasiert über Netzwerke
• Ressourcen: Nicht direkt geteilt

Paralleles System

Ein paralleles System ist eine Sammlung von stark gekoppelten Prozessoren (Multiprozessoren)

• Speichermodell: Gemeinsamer Speicher
• Kommunikation: Direkt über elektrische Signale → Switched Network (Kreuzschiene) | Bus → Punkt-zu-Punkt | Punkt-zu-N-Netzwerke
• Ressourcen: Gemeinsam genutzt (Bus, Speicher, IO)

Verteilte vs. Parallele Systeme

Verteilte vs. Parallele Systeme

Verteilte Systeme

• Historisch basierend auf Netzwerk-Betriebssystemen (z. B. Linux-Clustern): Benutzer sind sich der Vielzahl von Maschinen bewusst!

  • Tools: Remote Login (telnet, ssh), Remote Desktop (Windows), Dateitransfer (FTP, SSH), Netzwerk Dateisystem (NFS)

• Ein Verteiltes Betriebssystem verbirgt die einzelnen Maschinen: Benutzer sind sich der Vielzahl von Maschinen nicht bewusst!

  • Zugriff auf entfernte Ressourcen ähnlich wie der Zugriff auf lokale
  • Übertragung von Prozessen (Berechnung) und Programmcode (anstatt Daten)

[Tanenbaum]

Verteilte Systeme

Geschichte der Verteilten Betriebssysteme (DOS)

Verteilte Systeme

Entwurfskriterien und Eigenschaften

Parallele Systeme

Definition

• Zerlegung (Partitionierung) eines sequenziellen Algorithmus oder eines Programms in parallele Tasks (Prozesse) → Parallele Komposition

• Ausführung der Prozesse parallel (nebenläufig und ggfs. konkurrierend) auf mehreren Verarbeitungseinheiten (u. A. generische programmgesteuerte Prozessoren)

Motivation für parallele Datenverarbeitung

• Verkleinerung der Berechnungslatenz

Def. Latenz: Gesamte oder Teilbearbeitungszeit eines Datensatzes

• Erhöhung des Datendurchsatzes

Def. Datendurchsatz: Anzahl der verarbeiteten Datensätze pro Zeiteinheit

Parallele Systeme

• Latenz und Bandbreite sind zunächst unabhängig!

• Pipelining kann die Bandbreite erhöhen (nur Sinnvoll bei Datenströmen)

• Parallele Tasks können die Latenz verringern

Parallele Systeme

Man unterscheidet: Parallele Rechnerarchitektur und parallele Datenverarbeitung

Motivation für parallele Datenverarbeitung

• Steigerung der Energieeffizienz von mikroelektronischen Systemen:

  • Komplexe generische Einprozessoranlagen besitzen ungünstige Energieeffizienz, aber:
  • Parallelisierung kann zu verbesserter Energieeffizienz des Gesamtsystems führen!

• Skalierung von parallelen Rechnern auf reine Digitallogiksysteme für anwendungsspezifische Lösungen kann deutliche Reduktion der Hardware-Komplexität und der elektrischen Leistungsaufnahme bedeuten!

  • System-on-Chip Entwurf
  • Leistungsaufnahme eine CMOS Digitalschaltkreises (f: Frequenz, N: Schaltende Elemente, U: Spannung, C: Technologie):

(1)

Parallele Systeme

Parallele Systeme

Anwendung paralleler Datenverarbeitung

• Digitale Bildverarbeitung und automatische Bildinterpretation (Vision)

• Datenkompression (Video, mpeg)

• Komplexe Steuerungssysteme mit großer Anzahl von Freiheitsgraden, wie z.B. Positionierungssteuerung von Robotergelenken und Maschinen

• Kommunikation, z. B. nachrichtenbasiertes Routing

• Kryptoverfahren

• Parallele numerische Verfahren, wie z. B. Lösung von Differentialgleichungen (Strömungsmechanik, Elektromagnetische Wellenausbreitung, Wetter- und Klimamodelle)

Parallele Systeme

Beispiel Numerik und Digitale Bildverarbeitung

• Welche Probleme und Nachteile gibt es?

Parallele Systeme

Ebenen der Datenverarbeitung in Abhängigkeit vom Parallelisierungsgrad

Parallele Systeme

Rechnerarchitekturen in der Datenverarbeitung

• Für sequenzielle Datenverarbeitung existieren generische programmgesteuerte Rechneranlagen (von-Neumann Architektur), die die meisten sequenziellen Algorithmen effizient ausführen können.

• Das Programm besteht dabei aus einer Vielzahl elementarer einfacher Maschinenbefehle → Sequenzielle Komposition

Es gibt keine generischen Rechneranlagen und Architekturen für parallele Datenverarbeitung

• Parallele Algorithmen kann man klassifizieren.

• Die Klasse bestimmt die Rechnerarchitektur, die diese Algorithmen effizient verarbeiten können.

Parallele Systeme

Beispiel Sensorisches Material

Parallele Systeme

[blog.golang.org]

Parallele Systeme

Parallele und verteilte Datenverarbeitungssysteme vereinen Nebenläufigkeit und Konkurrenz

• Nebenläufigkeit durch Ausführungsplattform
• Konkurrenz muss durch Programmierung gelöst werden

Sequenzielle vs. parallele Datenverarbeitung

• Bei der sequenziellen Datenverarbeitung gibt es einen Algorithmus, der durch ein Programm implementiert wird, das durch einen Prozess auf einem Prozessor ausgeführt wird.

• Das Programm besteht aus einer Sequenz von Operationen die exakt in der Reihenfolge hintereinander ausgeführt werden.

• Bei einem parallelen Programm findet eine Partitionierung in Unterprogramme statt, die von mehreren Prozessen i.A. auf verschiedenen Prozessoren ausgeführt werden.

• Drei Phasen einer parallelen Programmausführung:

  1. Verteilungsphase der Eingabedaten
  2. Ausführungsphase mit Paralleler Verarbeitung
  3. Zusammenführungsphase der Ausgabedaten

Sequenzielle vs. parallele Datenverarbeitung

Zelluläre Automaten

• Zelluläre Automaten besitzen diskrete Zustände und ändern ihren Zustand nur zu diskreten Zeitpunkten

• Einfachstes paralleles bzw. eher verteiltes Berechnungsmodell → Verteilter Speicher mit expliziter Kommunikation!

• Netzwerk aus einfachen kommunizierenden Rechnern (Zellen)

• Eine Zelle besitzt eine endliche (kleine) Menge von Zuständen σ = { s₁,..,s_n}.

• Eine Berechnung mit Eingabe- und internen Daten (Perzeption und innerer Zustand) führt i.A. zu einer Änderung des Zustandes der Zelle → es gibt einen Zustandsübergang

• Übergangsregeln Φ können aus einfachen arithmetischen Operationen (Funktionen) bestehen, und beziehen den Zustand der Zellen aus der Nachbarschaft N(i,j)={σ (i ± Δ_i, j ± Δ_j) | Δ_i ≠ 0 ∨ Δ_j ≠ 0} mit ein (durch Kommunikation):

Zelluläre Automaten

Architektur und Grundprinzip

Zelluläre Automaten

• Nachbarschaftsrelationen sind auch bei Agenten wichtige Eigenschaft

Zelluläre Automaten

• Die Nachbarschaftskonnektivität und die Anzahl der Zustände je Zelle bestimmen die Anzahl der möglichen lokalen Regeln die zu einem Zustandsübergang in der Nachbarschaftsgruppe führen → wird sehr schnell sehr groß!!

Zelluläre Automaten

Parallele Datenverarbeitung

• Betrachtet man den ZA als verteilten Rechner:

  • Alle Zellen führen ihren Zustandsübergang parallel durch, d.h., die Anwendung der Übergangsfunktion Φ(σ)
  • Daraus können sich unerwartete globale Zustände ergeben da der Zustand einer Zelle (i,j) von den Zuständen der Nachbarn abhängt, jedoch die Nachbarzellen ebenso von dem Zustand dieser Zelle abhängen
  • Ohne Synchronisation u.U. randomisierte Ergebnisse und Zustandsübergänge!!!

• Betrachtet man den ZA als Simulator:

  • Die Zellen werden der Reihe nach (sequenziell) in einer bestimmter Ausbreitungsrichtung (z.B. von links unten nach rechts oben) der Reihe nach aktiviert!

• Es gibt keinen gemeinsamen globalen Speicher; durch die Kommunikation mit den Nachbarn (ersteinmal nur lesender Zugriff auf Nachbarspeicher) erhält man lokalen Gruppenspeicher (glokaler Bereich)

Zelluläre Automaten

Zustände

• Eine Zelle des ZA ist ein endlicher Zustandsautomat

• Ein Zustandsautomat hat einen Kontrollzustand γ und Datenzustand δ, d.h., σ(t)=〈γ,δ〉(t)

• Rein “funktionale” Automaten besitzen nur einen Datenzustand der sich durch eine Übergangsfunktion schrittweise ändert (einfachste Zelle), d.h., σ(t)=δ(t)

• Die Anzahl möglicher Regeln (also möglicher Zustandsübergänge) ist dann abhängig von der Anzahl der Zustände |σ| und Nachbarn n:

Zelluläre Automaten

Beispiel: Bildverarbeitung auf ZA

• Die einzelnen Pixel des Bilds (Sensoren) sind den Zellenrechnern zugeordnet
• Typische Operationen: Rauschunterdückung, Kantenfilter, Histogrammberechnung usw.
• Eine Zelle verändert immer nur seinen eigenen Datenwert durch Anwendung einfacher Regeln der Menge Φ mit Nachbarzellendaten

Zelluläre Automaten

Das Problem: Anders als bei klassischen Algorithmen sind diese Regeln nicht bekannt! Diese Transformationsregeln werden daher häufig gelernt (d.h. die geeigneten Regeln z.B. für Kantentendetektion aus der Menge aller möglichen Kombination von Pixeloperationen ausgewählt)

Zelluläre Automaten

Rauschunterdrückung

Zelluläre Automaten

Kantendetektion

Zelluläre Automaten

Die Programmierung

• Um einen ZA zu programmieren muss dessen Größe (Netzwerk Zeilen und Spalten), die Nachbarschaftsverbindungen (Reichweite und Richtung) sowie die Zustandsübergangsfunktione einer Zelle beschrieben werden
  • Annahme: Uniformer ZA, d.h. gleiches Φ gilt für alle Zellen!

model = {
  width: 100, height: 100,
  neighbors: 4,
  cell : {
   state : { x:0, xold:0 },
   before : function () { xold=x },
   activity : function (neighbors) { x=f(xold,neighbors) },
   after : function () { ... },
   color : function () { return color(x) }, // visual
   size: 6,  // visual
  }  
}