[JS]
[DE]
[PLUGIN] popup.plugin
[PLUGIN] lvm.plugin
[PLUGIN] file.plugin
[PLUGIN] pixels.plugin
[PLUGIN] math.plugin
[PLUGIN] button.plugin

[TITLE] Übung 3 zu Verteilte und Parallele Programmierung: Parallele Zelluläre Automaten (Teil 2)
[AUTHOR] PD Stefan Bosse

[VERSION] 4.2024

[USE] plot
[USE] math

[FUN]
```js
// PIXELS caworld handler and LUA event handler (simu:draw)
window.caworld={
}
// LUA event handler (via @event messages)
lvmShells.event = function (ev) {
  console.log('lvmShells.event',ev)
  if (ev=='grid') {
    // grid was updated via @data messages from lua
    // must conform with caluaP.lua!
    // update PIXELS world here
    if (PIXELS.rendered('myworld')) PIXELS.update('myworld',lvmShells.grid);
    else if (lvmShells.model) {
      console.log(lvmShells.model)
      // create simulation world
      caworld.grid=lvmShells.grid;
      if (lvmShells.model.palette) lvmShells.model.palette.unshift('white'); // LUA color index starts with 1!
      for(var p in lvmShells.model) window.caworld[p]=lvmShells.model[p];
      PIXELS.create('myworld',{handler:'caworld',index:'myworld'})
    }
  }
}
```

# Übung 3: Parallele Zelluläre Automaten mt Lua

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

- Es wird die parallele LuaJit VM *lvm* für das jeweilige eigene Betriebssystem benötigt
  + Momentan steht *lvm* für die Betriebssysteme *Linux 32bit*, *Linux 64bit*, *Solaris 32bit*, und *Windows 32bit* zur Verfügung. Das *lvm* Programm ist u.A. hier verfügbar: [lvm](http://edu-9.de/Lehre/vpp3k#mcb_toc_head6)
  + Lua/Csp Programme können direkt von der Konsole ausgeführt werden:
```
# lvm myprog.lua
```
  + Die Programme (oder Teile davon) können ebenso in diesem Notebook ausgeführt werden wenn *lvm* mit einem WEb browser Shell Wrapper gestartet wird (lokaler Rechner, Konsole):
```
# lvm weblvm.lua
Service thread 2 started.
[2@1592562880] HTTP server (2) listening to http://0.0.0.0:4610
Monitor thread 4 started.
[4@1592562880] HTTP server (4) listening to http://0.0.0.0:4611
```
  + Diese Variante erlaubt das schrittweise Erlernen von Lua/CA/Csp über die WEB Browser Oberfläche. 
  + Alle Code Snippets in diesem Notebook haben dann den gleichen Ausführungskontext (d.h. globale Variablen und Funktionen können von den einzelnen Snippets geteilt werden!)
  + Achtung: Wenn das Notebook neu geladen wird behält die *lvm* weiterhin ihren Zustand (globale Variablen, Funktionen usw.)
  + Dieser geteilte Kontext kann aber auch zu Problemen führen und bei Fehlern in parallelen Prozessen können Geisterprozesse übrig bleiben die nicht beendet werden können (ich arbeite daran dass das nicht eintritt und alle gestarten parallelen Prozesse == Threads abbrechbar sind)
  + **Ein Neustart des WEB Wrappers kann daher hin und wieder notwendig werden!**. Das Notebook muss dann nicht neu geladen werden und funktioniert sofort nach dem Neustart von *lvm* wieder. Nur der globale VM Kontext ist wieder "leer"!
  + Die Konsolenausgabe (mittels der *print* Anweisung) bei der Ausführung eines Programabschnitts wird automatisch weitergeleitet und hier angezeigt. Es kann aber nach einer gewissen Zeit erforderlich werden diese automatische Ausgabeweiterleitung wieder durch Drücken des Refresh Buttons anzustoßen (rechts an der *jeweiligen* Ausgabekonsole hier im Notebook) 
  + Jedes Codesnippet hat seine eigene Ausgabekonsole
  
> Unter seltenen Bedingungen (Race conditions!) kann *lvm* fehlerhaft arbeiten und "abstürzen" (IO Fehler) → *lvm* neu starten, und die Snippets im Notebook nochmals ausführen!

- **Zusätzlich werden im gleichen Verzeichnis benötigt**:
  + `caluaP.lua`
  + `weblvm.lua`

## Lua Code Ausführen

1. Der Programmcode kann in dem oberen Teilfenster eines Snippets verändert werden.
2. Der Programmcode wird ausgeführt durch Drücken der Playtaste ▸ im unteren Teilfenster (Ausgabekonsole).
3. Die Ausgabekonsole kann auf der rechten Seite gelöscht werden durch Drücken von ✗.
4. Hin und wieder kann eine Aktualisierung des Ausgabefensters durch Drücken des Knopfes ↻ erforderlich sein.
5. Bei parallelen Prozessen werden jeweils neue VM Instanzen in Threads gestartet. Wenn etwas schief läuft kann das Programm hängen und nicht terminieren (also der aktuelle Codeabschnitt). Der Abbruch kann versucht werden durch Drücken des Knopfes ◼.

[LVM] Programmierung der *lvm*
```lua
function foo () 
  local result=T{}
  for i=1,10 do
    result:push(math.random())
  end
  return result
end
print(foo():join(','))
```

## ZA Simulation

- Die Simulation bzw, die Berechnung des ZA wird direkt über die (p)lvm durchgeführt
- Die ZA Welt kann in Partitionen unterteilt werden
- Jede Partition wird in einem eigenen Worker Prozess mit einer eigenen VM Instanz berechnet
- Verteilung und Zusammenführung durch einen Master Prozess
- Anstelle der Klasse *CA.Simulation* wird nun die Klasse *CA.SimulationPar* verwendet

>! Wichtig: Da Shared Memory verwendet wird (intern über ein SM-Matrix Objekt) dürfen die Zustandsdatenvariablen der Zellen nur noch vom Typ *number* sein (Integer, Float)!

- Boolesche Ausdrücke müssen in numerische Werte kodiert werden, z.B. mit der `conditional(bexpr,vtrue,vfalse)` Hilfsfunktion.

- Weiterhin ist bei paralleler partitionierter Berechnung die randomisierte Initialisierung abzuändern. Es sollte eine globale geteilte Matrix für alle Partitionen verwendet werden, die mit Pseudozufallszahlen in einem Prozess berechnet wird.
  + Grund: In der Lua VM/lvm startet der Pseudozufallszahlengenerator (*math.random*) immer mit der gleichen Sequenz!
  + Würde man daher die randomisierte Zelleninitialisierung in jedem Partitionsprozess (jeweils eine Lua VM Instanz) getrennt berechnen erhielte man in allen Partitionen das gleiche Startmuster!

### Eine Partition

- Rein sequenzielle Berechnung, aber schon in einem separaten Worker Prozess (wie *CA.Simulation*).
- Wichtig: Globale Initialisierung der Zellen (über verteilbare Modelldaten *data*)

### Mutiple Partitionen

- Jede Partition wird sequenziell, aber alle Partitionen parallel ausgeführt
- Wichtig: Globale Initialisierung der Zellen (über verteilbare Modelldaten *data*)
- Simulationsschritte sind synchronisiert

#### Unterstütze Paritionsformate

```ascii
+-----+   +-----+  +-----+-----+
|     |   |  1  |  |  1  |  2  |
|  1  |   +-----+  +-----+-----+
|     |   |  2  |  |  3  |  4  |
+-----+   +-----+  +-----+-----+

+-----+-----+    +-----+-----+    +-----+-----+-----+-----+
|  1  |  2  |    |  1  |  2  |    |  1  |  2  |  3  |  4  |
+-----+-----+    +-----+-----+    +-----+-----+-----+-----+
|  3  |  4  |    |  3  |  4  |    |  5  |  6  |  7  |  8  |
+-----+-----+    +-----+-----+    +-----+-----+-----+-----+
|  5  |  6  |    |  5  |  6  |    |  9  | 10  | 11  | 12  |
+-----+-----+    +-----+-----+    +-----+-----+-----+-----+
                 |  7  |  8  |    | 13  | 14  | 15  | 16  |
                 +-----+-----+    +-----+-----+-----+-----+
```

>! Wichtig: Die Partitionierung in x- und y-Richtung muss ganzzahlig sein, d.h. die Größe der Automatenwelt muss durch die Anzahl Spalten und Zeilen ganzzahlig teilbar sein!

### 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:

```lua#box
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
```

### Modell

[LVM] Das Zellenmodell { lines:10 }
```lua
require "caluaP"
-- Create a new individual cell class 
cell=CA.Cell({
  name = "wall",
  monitor = true,
  state = { open = 0, wasOpen = 0 }
})
function cell:before (x,y)
  self.wasOpen = self.open
end
function cell:activity (x,y)
  local surrounding = self:ask(self.neighbors, 'count', 'wasOpen', 1)
  self.open=conditional(self.wasOpen==1 and surrounding >= 4 or surrounding >= 6,1,0)
end
function cell:initialize (x,y)
  self.open = conditional(self.data.init[y][x] > 0.40,1,0)
end
function cell:color ()
  return conditional(self.open==1,1,2)
end
```

[LVM] Das Welt- und Simulationsmodell { lines:10 }
```lua
model = {
  rows = 100,      -- N
  columns = 100,   -- N
  size = 4,
  neighbors = 8,
  palette = {'white','red'},
  partitions = 1,
  scheduler = 'RANDOM',  -- two phase all before; all process
  cell = cell,
  data = {
    -- must be consistent with rows/cols=N!
    init = math.matrix(100,100,function () return math.random() end),
  },
  start = { name = 'wall', distribution = 100 }
}
```

### Simulation erzuegen

[LVM] Den Simulator erzeugen { lines:10 }
```lua
model.partitions=1;
simulator = CA.SimulationPar:new(model);
```

### Simulation/Ausführung

- Der Aufruf der `simulator:draw` Methode überträgt das aktuelle Zellenbild an das Notebook wo es im nachfolgenden Fenster entsprechend der Farbpalette dargestellt wird.

>! Nachfolgendes Snippet ausführen (Play Button drücken) - es wird zunächst **keine** Grafik sichtbar werden!

[PIXELS] ZA World { handler:'caworld'; index:'myworld' }

- Wenn der Simulator ausgeführt wird, sollte im obigen "ZA World" Fenster die grafische Simulationswelt erscheinen.

[LVM] Die Simulation { lines:10 }
```lua
local t0=luv.milli()
local steps=20
for i=1,steps do
  print('Step '..i)
  simulator:step()
end
local t1=luv.milli()
print((t1-t0)/steps,'ms/step')
-- update visual world in notebook
simulator:draw()
```

[LVM] Simulation terminieren{ lines:10 }
```lua
simulator:stop()
simulator=nil
```
### Test

[LVM] Test (Aufgabe 5) { lines:10 }
```lua
model.partitions=1;
simulator = CA.SimulationPar:new(model);
for i=1,10 do simulator:step() end
-- g enthält matrix (rows array x columns array) der Welt (Farbpalettenindex)
local g1 = simulator:snapshot()
-- Beispiel: 
print(g1[1][2])
model.partitions=4;
simulator = CA.SimulationPar:new(model);
for i=1,10 do simulator:step() end
local g2 = simulator:snapshot()
print(g2[1][2])
-- Hier über eine Schleife testen ob alle Element in g1 und g2 gleiche
-- Werte besitzen
-- TODO
```

### Modelle

Verschiedene Modelle (Pseudonotation) zum Ausprobieren.

#### Cave

```pseudo
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

```pseudo
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

```pseudo
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
```

### Maßzahlen

#### Speed-up *S*:

$
%% ascii
S(N)=T_1/T_N
$

#### Skalierung

$
%% ascii
eta(N)=S_N/N
$

## Aufgaben

[EXERCISE]

1. Implementiere den Maze Algorithmus (oben) mit *N*=128 × 128 (120 für *P*=6) und teste die Berechnung für Partitionsgrößen  *P*={1,2,4,6,8,16}. Verwende den *UPRIGHT* Scheduler.

2. Wie verändert sich die Rechenzeit mit der Anzahl der Partitionen *P*? Erstelle einen Plot (für *P*={1,2,4,6,8,16}. Berechne den Speed-up aus den gemessenen Zeitwerten für einen Simulationsschritt und pro Zelle, trage die Werte in dem y-Array ein. Messe die Zeit für 20 Simulationsschritte.

[PLOT] Plot Speed-up
```
Plot({x:[1,2,4,6,8,16],
      y:[1,2,4,6,8,16]},
      {width:600,labels:{y:'S(P)',x:'P'}})
```

3. Berechne aus 2. die Skalierung

[PLOT] Plot Skalierung
```
Plot({x:[1,2,4,6,8,16],
      y:[1,2,4,6,8,16]},
      {width:600,labels:{y:'η',x:'P'}})
```

4. Was passiert wenn bei *P*=4 die Weltgröße verändert wird mit der Rechenzeit für einen Simulationsschrit pro Zelle? Wähle *N*={50,80,100,150,200,300,400,500}. Keine Visualisierung (entferne `simulator:draw`)!

[PLOT] Plot Rechenzeit / Zelle
```
Plot({x:[50,80,100,150,200,300,400,500],
      y:[1,1,1,1,1,1,1,1]},
      {width:600,labels:{y:'T(N)',x:'N'}})
```

5. Prüfe ob der Simulator korrekt arbeitet indem das Ergebnis für *P*=1 mit *P*={2,4,6,8,16} verglichen wird. Wichtig: Alle Experimente mit dem gleichen Startwerten (*data.init*).

[INPUT]

[EXERCISE]

---

[BUTTON] Hilfe { action:post; label:Absenden; style:"color:red" }
```
{
  url:function (url) { return url.indexOf('https')==0?'https://edu-9.de:28889':'http://edu-9.de:28888'},
  // url:'localhost:28888',
  form:['Name','Email','Pin','Frage'],
  email:{from:'$Email', to:'sbosse@uni-bremen.de', name:'$Name'},
  subject:'Hilfe Kurs ML $TITLE',
  message:'$Name: $Frage',
  attachments:[{filename:'$FILE.json',content:'$CODE'}],
  pin:1827,
}
```

[BUTTON] Einreichung (Assignment #2024-88224 ) { action:post; label:Absenden; style:"color:green" }
```
{
  url:function (url) { return url.indexOf('https')==0?'https://edu-9.de:28889':'http://edu-9.de:28888'},
  // url:'localhost:28888',
  form:['Name','Email','Pin','Kommentar'],
  submit: { from:'$Email', to:'sbosse@uni-bremen.de' },
  assignment:'2024-88224',
  name : '$Name',
  comment : '$Kommentar',
  attachments:[{filename:'$FILE.json',content:'$CODE'}],
  pin:1827,
}
```

[BUTTON] Prüfen { action:post; label:Laden; style:"color:browm" }
```
{
  url:function (url) { return url.indexOf('https')==0?'https://edu-9.de:28889':'http://edu-9.de:28888'},
  // url:'localhost:28888',
  form:['ID','Pin'],
  load: { id:'$ID' },
  pin:[1827,9223],
}
```

[BUTTON] Bewerten (Lehrer) { action:post; label:Absenden; style:"color:blue" }
```
{
  url:function (url) { return url.indexOf('https')==0?'https://edu-9.de:28889':'http://edu-9.de:28888'},
  // url:'localhost:28888',
  form:['ID','Marking','Pin','Remarks'],
  submit: { id:'$ID', from:'sbosse@uni-bremen.de', name:'$Name' },
  marks : '$Marking',
  remarks : '$Remarks',
  attachments:[{filename:'$FILE.json',content:'$CODE'}],
  pin:9223,
}
```

---

Übung 3: Parallele Zelluläre Automaten mt Lua

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!
Es wird die parallele LuaJit VM lvm für das jeweilige eigene Betriebssystem benötigt
- Momentan steht lvm für die Betriebssysteme Linux 32bit, Linux 64bit, Solaris 32bit, und Windows 32bit zur Verfügung. Das lvm Programm ist u.A. hier verfügbar: lvm
- Lua/Csp Programme können direkt von der Konsole ausgeführt werden:
```
# lvm myprog.lua
```
- Die Programme (oder Teile davon) können ebenso in diesem Notebook ausgeführt werden wenn lvm mit einem WEb browser Shell Wrapper gestartet wird (lokaler Rechner, Konsole):
```
# lvm weblvm.lua
Service thread 2 started.
[2@1592562880] HTTP server (2) listening to http://0.0.0.0:4610
Monitor thread 4 started.
[4@1592562880] HTTP server (4) listening to http://0.0.0.0:4611
```
- Diese Variante erlaubt das schrittweise Erlernen von Lua/CA/Csp über die WEB Browser Oberfläche.
- Alle Code Snippets in diesem Notebook haben dann den gleichen Ausführungskontext (d.h. globale Variablen und Funktionen können von den einzelnen Snippets geteilt werden!)
- Achtung: Wenn das Notebook neu geladen wird behält die lvm weiterhin ihren Zustand (globale Variablen, Funktionen usw.)
- Dieser geteilte Kontext kann aber auch zu Problemen führen und bei Fehlern in parallelen Prozessen können Geisterprozesse übrig bleiben die nicht beendet werden können (ich arbeite daran dass das nicht eintritt und alle gestarten parallelen Prozesse == Threads abbrechbar sind)
- Ein Neustart des WEB Wrappers kann daher hin und wieder notwendig werden!. Das Notebook muss dann nicht neu geladen werden und funktioniert sofort nach dem Neustart von lvm wieder. Nur der globale VM Kontext ist wieder "leer"!
- Die Konsolenausgabe (mittels der print Anweisung) bei der Ausführung eines Programabschnitts wird automatisch weitergeleitet und hier angezeigt. Es kann aber nach einer gewissen Zeit erforderlich werden diese automatische Ausgabeweiterleitung wieder durch Drücken des Refresh Buttons anzustoßen (rechts an der jeweiligen Ausgabekonsole hier im Notebook)
- Jedes Codesnippet hat seine eigene Ausgabekonsole

Unter seltenen Bedingungen (Race conditions!) kann lvm fehlerhaft arbeiten und "abstürzen" (IO Fehler) → lvm neu starten, und die Snippets im Notebook nochmals ausführen!

Zusätzlich werden im gleichen Verzeichnis benötigt:
- caluaP.lua
- weblvm.lua

Lua Code Ausführen

Der Programmcode kann in dem oberen Teilfenster eines Snippets verändert werden.
Der Programmcode wird ausgeführt durch Drücken der Playtaste ▸ im unteren Teilfenster (Ausgabekonsole).
Die Ausgabekonsole kann auf der rechten Seite gelöscht werden durch Drücken von ✗.
Hin und wieder kann eine Aktualisierung des Ausgabefensters durch Drücken des Knopfes ↻ erforderlich sein.
Bei parallelen Prozessen werden jeweils neue VM Instanzen in Threads gestartet. Wenn etwas schief läuft kann das Programm hängen und nicht terminieren (also der aktuelle Codeabschnitt). Der Abbruch kann versucht werden durch Drücken des Knopfes ◼.

Programmierung der lvm

function foo () 
  local result=T{}
  for i=1,10 do
    result:push(math.random())
  end
  return result
end
print(foo():join(','))

▸

◼

✗

↻

≡

ZA Simulation

Die Simulation bzw, die Berechnung des ZA wird direkt über die (p)lvm durchgeführt
Die ZA Welt kann in Partitionen unterteilt werden
Jede Partition wird in einem eigenen Worker Prozess mit einer eigenen VM Instanz berechnet
Verteilung und Zusammenführung durch einen Master Prozess
Anstelle der Klasse CA.Simulation wird nun die Klasse CA.SimulationPar verwendet

Wichtig: Da Shared Memory verwendet wird (intern über ein SM-Matrix Objekt) dürfen die Zustandsdatenvariablen der Zellen nur noch vom Typ number sein (Integer, Float)!

Boolesche Ausdrücke müssen in numerische Werte kodiert werden, z.B. mit der conditional(bexpr,vtrue,vfalse) Hilfsfunktion.
Weiterhin ist bei paralleler partitionierter Berechnung die randomisierte Initialisierung abzuändern. Es sollte eine globale geteilte Matrix für alle Partitionen verwendet werden, die mit Pseudozufallszahlen in einem Prozess berechnet wird.
- Grund: In der Lua VM/lvm startet der Pseudozufallszahlengenerator (math.random) immer mit der gleichen Sequenz!
- Würde man daher die randomisierte Zelleninitialisierung in jedem Partitionsprozess (jeweils eine Lua VM Instanz) getrennt berechnen erhielte man in allen Partitionen das gleiche Startmuster!

Eine Partition

Rein sequenzielle Berechnung, aber schon in einem separaten Worker Prozess (wie CA.Simulation).
Wichtig: Globale Initialisierung der Zellen (über verteilbare Modelldaten data)

Mutiple Partitionen

Jede Partition wird sequenziell, aber alle Partitionen parallel ausgeführt
Wichtig: Globale Initialisierung der Zellen (über verteilbare Modelldaten data)
Simulationsschritte sind synchronisiert

Unterstütze Paritionsformate

┌─────┐   ┌─────┐  ┌─────┬─────┐                           
│     │   │  1  │  │  1  │  2  │                           
│  1  │   ├─────┤  ├─────┼─────┤                           
│     │   │  2  │  │  3  │  4  │                           
└─────┘   └─────┘  └─────┴─────┘                           
                                                           
┌─────┬─────┐    ┌─────┬─────┐    ┌─────┬─────┬─────┬─────┐
│  1  │  2  │    │  1  │  2  │    │  1  │  2  │  3  │  4  │
├─────┼─────┤    ├─────┼─────┤    ├─────┼─────┼─────┼─────┤
│  3  │  4  │    │  3  │  4  │    │  5  │  6  │  7  │  8  │
├─────┼─────┤    ├─────┼─────┤    ├─────┼─────┼─────┼─────┤
│  5  │  6  │    │  5  │  6  │    │  9  │ 10  │ 11  │ 12  │
└─────┴─────┘    ├─────┼─────┤    ├─────┼─────┼─────┼─────┤
                 │  7  │  8  │    │ 13  │ 14  │ 15  │ 16  │
                 └─────┴─────┘    └─────┴─────┴─────┴─────┘

Wichtig: Die Partitionierung in x- und y-Richtung muss ganzzahlig sein, d.h. die Größe der Automatenwelt muss durch die Anzahl Spalten und Zeilen ganzzahlig teilbar sein!

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

Modell

Das Zellenmodell

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

▸

◼

✗

↻

≡

Das Welt- und Simulationsmodell

model = {
  rows = 100,      -- N
  columns = 100,   -- N
  size = 4,
  neighbors = 8,
  palette = {'white','red'},
  partitions = 1,
  scheduler = 'RANDOM',  -- two phase all before; all process
  cell = cell,
  data = {
    -- must be consistent with rows/cols=N!
    init = math.matrix(100,100,function () return math.random() end),
  },
  start = { name = 'wall', distribution = 100 }
}

▸

◼

✗

↻

≡

Simulation erzuegen

Den Simulator erzeugen

model.partitions=1;
simulator = CA.SimulationPar:new(model);

▸

◼

✗

↻

≡

Simulation/Ausführung

Der Aufruf der simulator:draw Methode überträgt das aktuelle Zellenbild an das Notebook wo es im nachfolgenden Fenster entsprechend der Farbpalette dargestellt wird.

Nachfolgendes Snippet ausführen (Play Button drücken) - es wird zunächst keine Grafik sichtbar werden!

ZA World

▸

✗

Wenn der Simulator ausgeführt wird, sollte im obigen "ZA World" Fenster die grafische Simulationswelt erscheinen.

Die Simulation

local t0=luv.milli()
local steps=20
for i=1,steps do
  print('Step '..i)
  simulator:step()
end
local t1=luv.milli()
print((t1-t0)/steps,'ms/step')
-- update visual world in notebook
simulator:draw()

▸

◼

✗

↻

≡

Simulation terminieren

simulator:stop()
simulator=nil

▸

◼

✗

↻

≡

Test

Test (Aufgabe 5)

model.partitions=1;
simulator = CA.SimulationPar:new(model);
for i=1,10 do simulator:step() end
-- g enthält matrix (rows array x columns array) der Welt (Farbpalettenindex)
local g1 = simulator:snapshot()
-- Beispiel: 
print(g1[1][2])
model.partitions=4;
simulator = CA.SimulationPar:new(model);
for i=1,10 do simulator:step() end
local g2 = simulator:snapshot()
print(g2[1][2])
-- Hier über eine Schleife testen ob alle Element in g1 und g2 gleiche
-- Werte besitzen
-- TODO

▸

◼

✗

↻

≡

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

Maßzahlen

Speed-up S:

\[ {S}{\left({N}\right)}=\frac{{T}_{{1}}}{{T}_{{N}}} \]

Skalierung

\[ \eta{\left({N}\right)}=\frac{{S}_{{N}}}{{N}} \]

Aufgaben

Aufgabe.

Implementiere den Maze Algorithmus (oben) mit N=128 × 128 (120 für P=6) und teste die Berechnung für Partitionsgrößen P={1,2,4,6,8,16}. Verwende den UPRIGHT Scheduler.
Wie verändert sich die Rechenzeit mit der Anzahl der Partitionen P? Erstelle einen Plot (für P={1,2,4,6,8,16}. Berechne den Speed-up aus den gemessenen Zeitwerten für einen Simulationsschritt und pro Zelle, trage die Werte in dem y-Array ein. Messe die Zeit für 20 Simulationsschritte.

Plot Speed-up

Plot({x:[1,2,4,6,8,16],
      y:[1,2,4,6,8,16]},
      {width:600,labels:{y:'S(P)',x:'P'}})

▸

✗

≡

Berechne aus 2. die Skalierung

Plot Skalierung

Plot({x:[1,2,4,6,8,16],
      y:[1,2,4,6,8,16]},
      {width:600,labels:{y:'η',x:'P'}})

▸

✗

≡

Was passiert wenn bei P=4 die Weltgröße verändert wird mit der Rechenzeit für einen Simulationsschrit pro Zelle? Wähle N={50,80,100,150,200,300,400,500}. Keine Visualisierung (entferne simulator:draw)!

Plot Rechenzeit / Zelle

Plot({x:[50,80,100,150,200,300,400,500],
      y:[1,1,1,1,1,1,1,1]},
      {width:600,labels:{y:'T(N)',x:'N'}})

▸

✗

≡

Prüfe ob der Simulator korrekt arbeitet indem das Ergebnis für P=1 mit P={2,4,6,8,16} verglichen wird. Wichtig: Alle Experimente mit dem gleichen Startwerten (data.init).

Hilfe

Einreichung (Assignment #2024-88224 )

Prüfen

Bewerten (Lehrer)

Created by the NoteBook Compiler Ver. 1.27.2 (c) Dr. Stefan Bosse (Mon Apr 22 2024 15:16:48 GMT+0200 (Central European Summer Time))