Übung 2: Zelluläre Automaten (Teil 1)

Ziel

Mit dieser Übung soll eine erste Einarbeitung mit Lua in ein bekanntes paralleles und verteiltes Berechnungsmodell und Architektur stattfinden: Dem Zellulären Automaten.

Hinweise

• In den Übungen werden alternativ drei verschiedene Lua VM Implementierungen verwendet:
  1. LuaJit+ LVM (parallelisierbar, externes Binary)
  2. Fengari Lua VM (eingebaut, Reimplementierung der Lua C VM in JavaScript, eingeschränkt parallelisierbar, WebWorker fähig)
  3. LuaJS Transpiler (eingebaut, übersetzt Lua Anweisungen und Funktionen in JavaScript) ⇒ bessere Performanz als Fengari Lua VM!

Der Transpiler besteht im wesentliche aus einem Lua Parser (https://github.com/fstirlitz/luaparse) der Esprima AST Bäume erzeugt (https://github.com/jquery/esprima), und schließlich mit Escodegen (https://github.com/estools/escodegen) in JavasScript Code umgewandelt wird. Der JavaScript Code wird schließlich ausgeführt.

• Die Ausführung des Lua Codes findet hier aus Performanzgründen unter Benutzung des LuaJS Transpilers (Lua → JS) direkt im Notebook statt. Es gilt zu beachten:
  • Der Lua Parser des Transpilers ist unvollständig, d.h. u.U. wird nicht jede gültige Lua Syntax akzeptiert
  • Keine Methodenaufrufe verketten (z.B. arr:keys():join(',') ⇒ local k=arr:keys(); local s=kjoin(',')
  • Der Übersetzungsvorgang kann erfolgreich sein, aber bei der Ausführung des JS Codes tritt ein Fehler auf (schwierig zu analysieren, noch einmal genau den Lua Code untersuchen und z.B. nach falsch geschrieben Namen suchen)
  • Wichtig: Bei Listen (Arrays und Records) unbedingt darauf achten dass nach dem letzten Element kein Komma angehängt wird!!!
  • Wichtig: Wenn die letzte Anweisung in einem Funktionsblock return ist: Kein Semikolon am Ende!

• Dieses interaktive Notebook enthält statische Inhalte und Code Snippets die direkt im Notebook ausgeführt werden können

• In Code Snippets: Linker Play Knopf startet die Ausführung des Codes. Der rechte Knopf ermöglicht das Löschen der Ausgabe!

• Bei Animationen gibt es es noch einen Stop Knopf der zur unmittelbaren Terminierung der Animation führt.

• Der Code kann verändert werden!

• Alle editierbaren Inhalte können gespeichert werden: Rechts oben (Save Notebook) Knopf

• Alle editierbaren Inhalte können wieder geladen werden und überschreiben Inhalte: Links oben (Load Notebook) Knopf

• Es können Notizen in Markdown Syntax gemacht werden, die auch gespeichert werden (Oben, Stift Knopf) oder Sticky Notes einfügren

• Der Code ist in Lua - eine Einführung gibt es hier luaTutorial.html

• Das ZA Modell wird in Lua programmiert

Einführung

• Ein zellulärer Automat besteht aus einer Menge von zustandsbasierten Zellen ZA={z₁,z₂,..,z_n}.

• Eine Zelle besitzt eine Anzahl von Zellenvariablen die den veränderlichen (Daten) Zustand S bestimmen: S(z_i)={x₁,..,x_k}

• Der nächste Zustand der Zellen wird über eine activity Funktion berechnet.

• Der Zustandsübergang einer Zelle erfolgt i.A. in der before oder after Funktion.

• Ein Scheduler führt die einzelnen Berechnungsfunktionen einer Zelle sequenziell in drei Phasen aus (obwohl ein ZA ein parelleles System ist!):

  1. before
  2. activity
  3. after

Architektur und Grundprinzip

• Der Zelluläre Automat ist hier ein Simulationswerkzeug der ein künstliche zweidimensionale Welt aus Entitäten repräsentiert!
• Zur Visualisierung bekommt jede Zelle eine Farbe aus einer definierten Farbpalette

Zellulärer Automat als Netzwerk aus einfachen kommunizierenden Berechnungseinheiten

CALUA

Simulationsemodell

• Die Definition eines ZA Modells mit calua Bibliothek erfolgt in zwei Schritten:

  1. Definition einer Zellenklasse (siehe Beispiel)
  2. Definition des Weltmodells (Kartesische Koordinaten: Oben links ist Koordinatenursprung (0,0))

• Das Weltmodell ist ein Gitternetzwerk mit farbigen Kacheln für die grafische Visualisierung

  • Die Farben werden durch eine diskrete Farbpalette definiert
  • Das Weltmodell definiert auch globale Daten (Feld data), die von allen Zellen gelesen und geschrieben werden können

• Eine Zellenklasse besitzt zwei wichtige Parameter: name und state

  • state definiert die privaten Daten einer Zelle (Datenzustand)

-- 1. Leere Zellenklasse erzeugen
local cell=CA.Cell({
  name = S,
  state = { var = ε, .. }
})

• Eine Zellenklasse muss mindestens drei Methoden definieren:

  • initialize
  • activity
  • color die einen Indexwert aus der Farbtabelle liefern muss (Startindex: 1 gleich erste Farbe in der Palette)

• Optional gibt es die Methoden:

  • before
  • after

-- 2. Eigene Methoden hinzufügen
function cell:initialize (x,y)
  ..
end
function cell:before (x,y)
  ..
end
function cell:activity (x,y)
  ..
end
function cell:after (x,y)
  ..

end
function cell:color (x,y)
  return N
end

• Schließlich wird das Weltmodell erzeugt.

• Es muss folgende Parameter enthalten:

  • rows, columns,
  • size (visuelle Zellengröße),
  • neighbors (4:Neumann/8:Moore),
  • scheduler (UPRIGHT, DOWNLEFT, RANDOM, RANDOM0),
  • palette (Liste aus Farbnamen)
  • cell (bereits definierte Zellenklasse)
  • data (optional)

model = {
  rows : N,
  columns : N,
  size : N,
  neighbors : N,
  scheduler : S,
  palette : { S, S,  ..},
  cell : cell,
  data : { .. }
}

Sensoren und Aktoren

• Der Zustand einer Zelle besteht aus einer oder mehreren Variablen

• I.A. ist eine Variable ein Sensor, der von der Nachbarzellen gelesen wird

• I.A. ist eine andere Variable der zustandsbestimmende Aktor einer Zelle, die auch die Farbe einer Zelle bestimmt

• Die Nachbarzellen sind durch das Objekt self.neighbors erreichbar (direkt mit dem Shared Memory Modell, indirekt durch get/set Methoden über Kommunikationskanäle im Distributed Memory Modell). Die Felder und relativen Positionen sind wie folgt gezeigt:

if model.neighbors == 4 then
    -- Neumann
    self.neighbors = {
      left    = {-1,0},
      right   = {1,0},
      bottom  = {0,1},
      top     = {0,-1}
    }
elseif model.neighbors == 8 then
    -- Moore
    self.neighbors = {
      left        = {-1,0},
      right       = {1,0},
      bottom      = {0,1},
      top         = {0,-1},
      topleft     = {-1,-1},
      topright    = {1,-1},
      bottomleft  = {-1,1},
      bottomright = {1,1}
    }
end

┌──────────┬──────────┬──────────┬────▶ x
│          │          │          │       
│ topleft  │   top    │ topright │       
│          │          │          │       
├──────────┼──────────┼──────────┤       
│          │          │          │       
│ left     │  pixel   │ right    │       
│          │          │          │       
├──────────┼──────────┼──────────┤       
│          │          │          │       
│ bottom-  │  bottom  │ bottom-  │       
│ left     │          │ right    │       
├──────────┴──────────┴──────────┘       
│                                        
│                                        
▼  y                                     

• Eine Zelle kann auf seine Nachbarn auf zwei Arten zugreifen:
  1. Shared Memory: self.neighbors.left[key] (Je nach Position einer Zelle in der Welt können Nachbarelemente == nil sein → vorher testen!)
  2. Distributed Memeory: self.read(from,key) und self.write(to,key,val) (mit Nachrichtenaustausch)

Simulation

• Die Simulation ist in Schritte unterteilt

• In einem Schritt werden je nach Scheduler die Zellen des Netzwerks der Reihe nach ausgeführt.

• Wenn der Schedulername nicht mit einer "0" endet werden die Funktionen der Zellen in drei Phasen ausgeführt (jede Phase durchläuft immer alle Zellen):

  0. initialize wird bei der Erstellung des Simulators einmalig ausgeführt
  1. before wird ausgeführt (Sensoren der Nachbarzellen erfassen)
  2. activity wird ausgeführt (Zustand ändern)
  3. after wird ausgeführt

• Die Phasen sind Synchronisationsbarrieren (d.h., Ausführung einer Phase ist eine Forkoperation, Terminierung einer Joinoperation)!

• Wenn der Schedulername mit einer "0" endet werden die drei Funktionen before, activity und after für jede Zelle einzeln zusammenhängend ausgeführt (Einphasensimulation)

Ein einfacher ZA

1. Das Modell erstellen
   • Die Variable wasOpen ist der Sensor
   • Die Variable open ist der Aktor

2. Einen Simulator mit dem Modell erzeugen

3. Einen Simulationsschritt ausführen (oben sollte sich die ZA Welt verändern)

4. Modelle

Verschiedene Modelle (Pseudonotation) zum Ausprobieren.

Cave

state    : {open,wasOpen}
before   : wasOpen=open
acitivty : 
  surrounding = count(neighbors,wasopen==true)
  open=(wasOpen and surrounding >= A) or surrounding >= B 
initialize : open=random()>density

Maze

state    : {alive,wasAlive,simulated}
before   : wasAlive=alive
activity : 
  surrounding = count(neighbors,wasopen==true)
  simulated < 20?
    alive = surrounding == 1 or surrounding == 2 and alive;
  simulated > 20 and surrounding == 2?
    alive = true;
  simulated = self.simulated+1
initialize : alive = random() > 0.6; simulated=0

Game Of Live

state    : {alive,wasAlive}
before   : wasAlive=alive
activity : 
  surrounding = count(neighbors, wasAlive==true)
  alive = surrounding == 3 or surrounding == 2 and alive
initialize : alive = random() > 0.5

Aufgaben