Verteilte und Parallele Programmierung

Mit Virtuellen Maschinen

PD Stefan Bosse

Universität Bremen - FB Mathematik und Informatik

1 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten ::

Zelluläre Automaten

Einführung von Grundprinzipien beim Entwurfs von VP Systemen

Zelluläre Automaten als einfache VP Architektur und Datenverarbeitungsmodell

2 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Grundprinzipen beim Entwurf von Verteilten Systemen

Grundprinzipen beim Entwurf von Verteilten Systemen

Nach Werner Vogel, Amazon [101]

Dezentralisierung ⇒ Verbesserung der Skalierung;
Asynchronität ⇒ Ein System schreitet unter "allen" Umständen voran;
Autonomie ⇒ Das System besteht aus Einheiten die autonom Entscheidungen mit lokalen Informationen treffen können;
Lokalität ⇒ Systemeinheiten arbeiten auf lokalen Daten;
Wettbewerb (Konk.) ⇒ Die Einheiten sind so gebaut, dass kaum oder kein Wettbewerb um geteilte Ressourcen auftritt (gesteuerter Wettbewerb);
Fehlertoleranz ⇒ Der Ausfall einzelner Einheiten ist der Normalfall und beeinträchtigt das Systemevrhalten nicht (und das Endergebnis);
Parallelität ⇒ P. erhöht die Performanz und Robustheit;

3 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Grundprinzipen beim Entwurf von Verteilten Systemen

Elementarzellenansatz ⇒ Dekomposition eines großen und komplexen Systemes in viele kleine und einfache Einheiten;
Symmetrie ⇒ Die Einheiten des Systems sind identisch in Hinsicht auf Funktionalität und benötigen keine spezifische Konfiguration;
Einfachheit ⇒ KISS (Keep it Simple and Safe), die Elementarzellen sollen durch einfache Modelle und Algorithmen implementiert werden und möglichst geringe Abhängigkeiten untereinander besitzen.

Zelluläre Automaten vereinen fast alle dieser Grundprinzipien.

4 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Parallele Semantik

Parallele Semantik

mogill.github.io/ems/Docs/index.html Arten von Parallelität

5 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Parallele Semantik

Kommunikationsmodelle

Ungeteilte Parallelität: Die einzelnen Prozesse werden nebenläufig ohne gemeinsam geteilte Ressourcen ausgeführt (aber partitionierte Datenverteilung und Datenzusammenführung möglich → Map&Reduce Verfahren)

Communicating Sequential Processes (CSP): Prozesse werden parallel aber mit geteilten Ressourcen und Synchronisation ausgeführt

6 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Parallele Semantik

Prozessmodelle

Fork-Join Multiprozesse: Die Ausführung beginnt mit einem einzelnen Prozess, der bei Bedarf neue Prozesse erstellt und dann auf deren Terminierung wartet.

Bulk Synchron Parallel: Die Ausführung beginnt mit einer Menge von Prozessen, die das Programm am Haupteinstiegspunkt startet und alle Anweisungen ausführt.

Benutzerdefiniert: Parallelität durch Ad-hoc-Prozesse und heterogene Anwendungen.

7 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Zelluläre Automaten

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

8 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Zelluläre Automaten

Ü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):

$\sigma_{i,j}(t + 1) = \Phi(\{\sigma_{k,l}(t) | \sigma_{k,l}(t) \in N \})$

9 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Zelluläre Automaten

Zelluläre Automaten

Architektur und Grundprinzip

Hoekstra,SCSCA,2010 Zellulärer Automat als Netzwerk aus einfachen kommunizierenden Berechnungseinheiten

10 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Zelluläre Automaten

Zelluläre Automaten

Nachbarschaftsrelationen sind auch bei Agenten wichtige Eigenschaft

Hoekstra,SCSCA,2010 Verschiedene Nachbarschaftsrelationen

11 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Zelluläre Automaten

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ß!!

Hoekstra,SCSCA,2010 Anzahl der Regeln eines ZA in Abhängigkeit der Anzahl der Zustände pro Zelle und des Verbindungsgrades der Zellen

12 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Zelluläre Automaten

Zelluläre Automaten

Parallele Datenverarbeitung

Den ZA kann man als verteilten Rechner betrachten:
- 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!!!

13 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Zelluläre Automaten

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)

14 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Zelluläre Automaten

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)

$\sigma_{i,j}(t + 1) = f(\sigma_{i,j}(t))$

15 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Zelluläre Automaten

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

$N_r= |\sigma|^{|\sigma|^n}$

16 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Zelluläre Automaten

Zelluläre Automaten

Beispiel: Bildverarbeitung auf ZA

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

17 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Zelluläre Automaten

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)

18 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Zelluläre Automaten

Rosin,2002 Alle 51 möglichen Muster (Regeln) damit ein Pixel seinen Wert (binär, SW Bild) invertiert (Mooresche Nachbarschaft mit 8 Nachbarn); gezeigt sind nur zentrale schwarze Pixel, durch Invertierung weitere 51 Regeln für weiße Pixel

19 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Zelluläre Automaten

Zelluläre Automaten

Rauschunterdrückung

Rosin,2002 Rauschunterdückung durch einen binären ZA: (a) Originalbild (b) Verrauschtes Bild (c) Entrauschtes Bild mit dem unten gezeigten Regelsatz

20 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Zelluläre Automaten

Zelluläre Automaten

Kantendetektion

Rosin,2002 Kantendetektion (oben,links) Originalbild (oben,rechts) Konv. Alg. (unten, links) CA - ein Zyklus ZA (unten rechts) zwei Zyklen CA

21 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Zelluläre Automaten

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übergangsfunktion einer Zelle beschrieben werden
- Annahme: Uniformer ZA, d.h. gleiches Φ gilt für alle Zellen!
Visualisierung mit einer festen Kachelgitterwelt und einer Farbpalette
Die Zustandsübergangsfunktion ist dreischrittig und unterteilt (optional):
- Before
- Activity
- After

22 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Zelluläre Automaten

Die Ausführung

Es gibt einen Scheduler der die Zellen in einer bestimmten oder randomisierten Reihenfolge aktiviert
Dabei kann es bis zu drei Phasen geben:
- Voraktivierung (Before),
- Hauptaktivierung (Activity),
- Nachaktivierung (After).

Die Reihenfolge der Zellenaktivierungen kann aufgrund der Nachbarschaftskommunikation zu unetrschiedlichen globalen Zuständen führen!

23 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Zelluläre Automaten

ZA Modell

type model = {
  rows : number, columns : number,
  neighbors: number,
  palette : string [],
  cell : cell class,
  data? : {},
  start : { name:string, distribution:number }
}
type cell class = {
  method before (),
  method activity (neighbors),
  method after (),
  method color () -> number,
  method initialize (x,y),
}

Modell eines ZA der cellauto Bibliothek (Typsignatur)

24 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: ZA Beispiel in Lua

ZA Beispiel in Lua

local cell=CA.Cell({
  name = "wall",
  size = 4,
  state = { open = 0, wasOpen = 0 }
})
function cell:before ()
  self.wasOpen = self.open
end
function cell:activity (neighbors,x,y)
  local surrounding = self.ask(neighbors, 'count', 'wasOpen', true)
  self.open = (self.wasOpen and surrounding >= 4) or surrounding >= 6
end
function cell:initialize (x,y)
  self.open = self.data[y][x] > 0.40
end
function cell:color ()
  return conditional(self.open,1,2)
end

Definition der Zellenklasse: Das dynamische Höhlensystem

25 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: ZA Beispiel in Lua

Das Modell definiert die:
- Welt (2D Kachelgitter),
- Farbpalette,
- Globale Daten, und den
- Zellenkonstruktor

model = {
  rows = 100,
  columns = 100,
  neighbors = 8,
  palette = {'white','red'},
  scheduler = 'UPRIGHT',  -- two phase all before; all process
  cell = cell,
  data = math.matrix(100,100,math.random),
  start = { name = 'wall', distribution = 100 }
}

Das ZA Modell in Lua

26 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: ZA Beispiel in Lua

27 / 28

PD Stefan Bosse - VPP - Zelluläre Automaten :: Zusammenfassung

Zusammenfassung

Verteilte und Parallele Systeme (VP) basieren auf einem gemeinsamen Satz von Entwurfsregeln → KISS Prinzip!
Zelluläre Automaten sind ein Beispiel für eine parallele und verteilte Datenverarbeitungsarchitektur nach dem KISS Prinzip:
- Zerlegung eines komplexen Problems auf einfache kommunizierende Elementarzellen
- Abbildung von Datenmatrizen auf Zellengitternetzwerk
- Jede Zelle verarbeitet nur lokale Daten
- Jede Zelle kommuniziert nur mit den unmittelbaren Nachbarn (kurzreichweitige Komm. und Datenabhängigkeit)
ZA können sequenziell simuliert werden (u.A. mit Asynchronität)
ZA sind Virtuelle Maschinen und können Rechencluster bilden!

28 / 28