[LUA]
[DE]
[PLUGIN] popup.plugin
[PLUGIN] lvm.plugin
[PLUGIN] file.plugin
[PLUGIN] button.plugin

[TITLE] Parallel Lua: Map-Reduce Tutorial
[AUTHOR] Stefan Bosse
[VERSION] 6.2024

# Parallel Lua: Map-Reduce Tutorial

In dieser Übung findet eine erste Einführung in die Programmierung von parallelen Systemen nach dem Map & Reduce Modell statt.

## Vorbereitung und Verwendung

- 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*, *Windows 32bit* und *MacOS X 64bit* zur Verfügung. Da Microsoft Windows zu keinem guten Informatikkonzept kompatibel ist kann es dort zu funktionalen Abweichungen und Einschränkungen von *lvm* kommen → [lvm](http://edu-9.de/Lehre/vpp2k)
  + 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 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/Csp. 
  + 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!)
  + 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
  + **Ein Neustart des lvm 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!
  + Es kann sein dass in Worker Prozessen die *print* Ausgabe nicht hier im Code Snippet Konsolenfenster angezeigt wird (aber in der Terminalkonsole wo weblvm ausgeführt wird).
  
>! Es wird das `AES.lua` Modul benötigt. Die Datei muss sich im gleichen Verzeichnis befinden wie `weblvm-lua`.

## Partitionierung

Das *lvm* Modul *parallel* kann verwendet werden um selbstsynchronisierende parallele Datenverarbeitung von partitionierbaren Datensätzen nach dem Map & reduce (MaR) prinzip zu ermöglichen. Im Gegensatz zum CSP Modell gibt es keine explizite Interprozesskommunikation zwischen einzelnen parallel ausgeführten Berechnungsprozessen. Daher kann die MaR Architektur eher als Datenpfadparallelität verstanden werden.

Folgende Bedingungen müssen erfüllt sein:

1. Ein Datensatz **D** kann in unabhängige Teilsätze {**d**}^i^ zerlegen
2. Es gibt eine Berechnungsfunktion *f*(*x*):*x* → *y* die auf Fraktionen oder einzelne Elemente des Datensatzes angewendet werden kann
3. Es gibt i.A. eine Kette von Berechnungsfunktionen *f*(*g*(*h*(...(*x*)))) : *x* → *y*
4. Die Teilberechnungen sind vertikal unabhängig, horizotntal strikt sequenziell.

Das *lvm* MaR Modul definiert eine parallele Berechnung als Sequenz von synchronisierten Operationen (horizontal Verabeitungskette). Dabei wird eine folgende Operation erst dann ausgeführt wenn die vorherige terminiert ist.

Es gibt folgende Operationen:

- *time*() startet oder stoppt einen Zeitmesser;
- *map*(*worker*) partitioniert und verteilt die Eingabedatenmenge auf *options*.*workers* parallele Prozesse die jeweils die *worker* Funktion ausführen, das Ergebnis besitzt die gleiche Dimensionalität wie die Eingabedaten, aber u.U. eine andere Typsignatur;
- *apply*(*fun*) wendet (sequenziell, Master Prozess) eine Funktion auf den Eingabedatenvektor an;
- *reduce*(*fun*) wendet eine Reduktionsfunktion *fun*(*a*,*b*) : (*a*,*b*) → *c* auf den Datenvektor an und liefert einen reduzierten Vektor oder meistens einen Skalarwert.

## Prozessfluss

```ascii
                     +----+
                     | P0 | (map)
                     +--+-+
                       A|   
        +-------+-------+-------+-------+            
  A= {a1|     a2|     a3|     a4|     a5|    ...}  <--+
     +--+-+  +--+-+  +--+-+  +--+-+  +--+-+           |
     | P1 |  | P2 |  | P3 |  | P4 |  | P5 |  ...      |
     +--+-+  +--+-+  +--+-+  +--+-+  +--+-+           |
  B= {b1|     b2|     b3|     b4|     b5|    ...} ----+
        +-------+-------+-------+-------+            
                       B|
                     +--+-+
                     | P0 | (reduce)
                     +--+-+
                       c|  
                        /
                      Result
```

- *A* und *B* sind Vektoren oder Matrizen, und *c* ein reduzierter niderigdimensionalerer Wert.

- Die Anzahl der Partitionen wird den Worker Prozessen angepasst.

>! Bei ungradzahliger Verteilung können die EIngabedatenpartitonen unterschiedlich groß sein.

## Beispiele

### Einfaches Beispiel

- Ziel: Parallele Berechnung der Fibonacci Zahlen in einem Wertebereich von [*a*,*b*].
- Eingabedaten: Eine Menge von Startwerten **D**~1~={*x*}^i^
- Ausgabedaten: Die abgebildete Menge von Fibonacci Zahlen **D**~2~={*fib*(*x*)}^i^
- Reduktion: Summe alle Element von **D**~2~

[LVM] Parallele Berechnung (1)
```lua
Parallel=require 'parallel';
function sequence(a,b)
  local result = T{}
  for i=a,b do result:push(i) end
  return result
end
local function fib(n)
  if n < 2 then return 1 else return  fib(n - 1) + fib(n - 2) end
end
local function worker (id,set)
  local results = T{}
  -- print('start '..id)
  for i = 1,#set do
    results:push(fib(set[i]))
  end
  -- print('stop '..id)
  return results
end

local data = sequence(30,42)
function sum (x,y) return x+y  end

local p = Parallel:new(data,{
 workers = 2
})
print('Start ..')

p:time():
  map(worker):
  apply(function (r) print(r:print()) end):
  reduce(sum):
  apply(print):
  time()
print('After MaR..')
```

[QUESTION] 
Welcher Speed-up wird für *workers*=1,2,3,4 erzielt?

[INPUT]

[QUESTION] 
Wieso ist das Ergebnis enttäuschend? Wo lieht hier das Problem bei der Parallelisierung (bzgl. Beschleunigung)? Hinweis: Betrachte die Rechenkomplexität (in Abhängigkeit des Startwertes *x*)

[INPUT]

[QUESTION] 
Wie könnte eine gleichmäßige(re) Auslastung der Prozesse ohne a-priori Kenntnis der Berechnung erfolgen?

[INPUT]

### Verschlüsselung

- Im folgenden Beispiel soll eine Matrixberechnung parallel mit MaR durchgefphrt werden die typisch in der Bildverrabeitung ist

- Es wird das Modul *AES.lua* benötigt (Datei muss sich im gleichen Verzeichnis wie weblvm befinden).

[LVM] MaR in der Verschlüsselung
```lua
Parallel=require 'parallel';
local AES = require 'AES';

local key = 0x68C756C6C186436C9EC51C174C32AE81761389B5E5904E30BA57CCD911290ECC

function sequence(a,b)
  local result = T{}
  for i=a,b do result:push(i) end
  return result
end
local charset = {}

-- qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM1234567890
for i = 48,  57 do table.insert(charset, string.char(i)) end
for i = 65,  90 do table.insert(charset, string.char(i)) end
for i = 97, 122 do table.insert(charset, string.char(i)) end

local function strrnd(length)
  if length > 0 then
    return strrnd(length - 1) .. charset[math.random(1, #charset)]
  else
    return ""
  end
end

-- Create random strings
local function worker1(id,set)
  -- Create random string
  local results = T{}
  for i = 1,#set do
    local s = strrnd(32);
    results:push(s)
  end
  return results  
end

-- Encrypt all strings
local function worker2(id,set)
  -- Create encrypted strings
  local results = T{}
  for i = 1,#set do
    results:push(AES.ECB_256(AES.encrypt, key, set[i]))
  end
  return results  
end

local data = sequence(1,1000)
local p = Parallel:new(data,{
 workers = 1
})
print('Start ..')
p:time():
  map(worker1):
  map(worker2):
  time()
print('After MaR')
```
[QUESTION] 
Welcher Speed-up wird für *workers*=1,2,3,4 erzielt?

[INPUT]

[QUESTION] 
Wieso ist das Ergebnis hier besser (im Vergleich zu Beispiel 1)?

[INPUT]

---

[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-12331 ) { 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-12331',
  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,
}
```

---

Parallel Lua: Map-Reduce Tutorial

In dieser Übung findet eine erste Einführung in die Programmierung von parallelen Systemen nach dem Map & Reduce Modell statt.

Vorbereitung und Verwendung

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, Windows 32bit und MacOS X 64bit zur Verfügung. Da Microsoft Windows zu keinem guten Informatikkonzept kompatibel ist kann es dort zu funktionalen Abweichungen und Einschränkungen von lvm kommen → 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 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/Csp.
- 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!)
- 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
- Ein Neustart des lvm 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!
- Es kann sein dass in Worker Prozessen die print Ausgabe nicht hier im Code Snippet Konsolenfenster angezeigt wird (aber in der Terminalkonsole wo weblvm ausgeführt wird).

Es wird das AES.lua Modul benötigt. Die Datei muss sich im gleichen Verzeichnis befinden wie weblvm-lua.

Partitionierung

Das lvm Modul parallel kann verwendet werden um selbstsynchronisierende parallele Datenverarbeitung von partitionierbaren Datensätzen nach dem Map & reduce (MaR) prinzip zu ermöglichen. Im Gegensatz zum CSP Modell gibt es keine explizite Interprozesskommunikation zwischen einzelnen parallel ausgeführten Berechnungsprozessen. Daher kann die MaR Architektur eher als Datenpfadparallelität verstanden werden.

Folgende Bedingungen müssen erfüllt sein:

Ein Datensatz D kann in unabhängige Teilsätze {d}ⁱ zerlegen
Es gibt eine Berechnungsfunktion f(x):x → y die auf Fraktionen oder einzelne Elemente des Datensatzes angewendet werden kann
Es gibt i.A. eine Kette von Berechnungsfunktionen f(g(h(...(x)))) : x → y
Die Teilberechnungen sind vertikal unabhängig, horizotntal strikt sequenziell.

Das lvm MaR Modul definiert eine parallele Berechnung als Sequenz von synchronisierten Operationen (horizontal Verabeitungskette). Dabei wird eine folgende Operation erst dann ausgeführt wenn die vorherige terminiert ist.

Es gibt folgende Operationen:

time() startet oder stoppt einen Zeitmesser;
map(worker) partitioniert und verteilt die Eingabedatenmenge auf options.workers parallele Prozesse die jeweils die worker Funktion ausführen, das Ergebnis besitzt die gleiche Dimensionalität wie die Eingabedaten, aber u.U. eine andere Typsignatur;
apply(fun) wendet (sequenziell, Master Prozess) eine Funktion auf den Eingabedatenvektor an;
reduce(fun) wendet eine Reduktionsfunktion fun(a,b) : (a,b) → c auf den Datenvektor an und liefert einen reduzierten Vektor oder meistens einen Skalarwert.

Prozessfluss

                     ┌────┐                            
                     │ P0 │ (map)                      
                     └──┬─┘                            
                       A│                              
        ┌───────┬───────┼───────┬───────┐              
  A= {a1│     a2│     a3│     a4│     a5│    ...}  ◀──┐
     ┌──┴─┐  ┌──┴─┐  ┌──┴─┐  ┌──┴─┐  ┌──┴─┐           │
     │ P1 │  │ P2 │  │ P3 │  │ P4 │  │ P5 │  ...      │
     └──┬─┘  └──┬─┘  └──┬─┘  └──┬─┘  └──┬─┘           │
  B= {b1│     b2│     b3│     b4│     b5│    ...} ────┘
        └───────┴───────┼───────┴───────┘              
                       B│                              
                     ┌──┴─┐                            
                     │ P0 │ (reduce)                   
                     └──┬─┘                            
                       c│                              
                        ▼                              
                      Result

A und B sind Vektoren oder Matrizen, und c ein reduzierter niderigdimensionalerer Wert.
Die Anzahl der Partitionen wird den Worker Prozessen angepasst.

Bei ungradzahliger Verteilung können die EIngabedatenpartitonen unterschiedlich groß sein.

Beispiele

Einfaches Beispiel

Ziel: Parallele Berechnung der Fibonacci Zahlen in einem Wertebereich von [*a*,*b*].
Eingabedaten: Eine Menge von Startwerten D₁={x}ⁱ
Ausgabedaten: Die abgebildete Menge von Fibonacci Zahlen D₂={fib(x)}ⁱ
Reduktion: Summe alle Element von D₂

Parallele Berechnung (1)

Parallel=require 'parallel';
function sequence(a,b)
  local result = T{}
  for i=a,b do result:push(i) end
  return result
end
local function fib(n)
  if n < 2 then return 1 else return  fib(n - 1) + fib(n - 2) end
end
local function worker (id,set)
  local results = T{}
  -- print('start '..id)
  for i = 1,#set do
    results:push(fib(set[i]))
  end
  -- print('stop '..id)
  return results
end

local data = sequence(30,42)
function sum (x,y) return x+y  end

local p = Parallel:new(data,{
 workers = 2
})
print('Start ..')

p:time():
  map(worker):
  apply(function (r) print(r:print()) end):
  reduce(sum):
  apply(print):
  time()
print('After MaR..')

▸

◼

✗

↻

≡

Frage. Welcher Speed-up wird für workers=1,2,3,4 erzielt?

Frage. Wieso ist das Ergebnis enttäuschend? Wo lieht hier das Problem bei der Parallelisierung (bzgl. Beschleunigung)? Hinweis: Betrachte die Rechenkomplexität (in Abhängigkeit des Startwertes x)

Frage. Wie könnte eine gleichmäßige(re) Auslastung der Prozesse ohne a-priori Kenntnis der Berechnung erfolgen?

Verschlüsselung

Im folgenden Beispiel soll eine Matrixberechnung parallel mit MaR durchgefphrt werden die typisch in der Bildverrabeitung ist
Es wird das Modul AES.lua benötigt (Datei muss sich im gleichen Verzeichnis wie weblvm befinden).

MaR in der Verschlüsselung

Parallel=require 'parallel';
local AES = require 'AES';

local key = 0x68C756C6C186436C9EC51C174C32AE81761389B5E5904E30BA57CCD911290ECC

function sequence(a,b)
  local result = T{}
  for i=a,b do result:push(i) end
  return result
end
local charset = {}

-- qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM1234567890
for i = 48,  57 do table.insert(charset, string.char(i)) end
for i = 65,  90 do table.insert(charset, string.char(i)) end
for i = 97, 122 do table.insert(charset, string.char(i)) end

local function strrnd(length)
  if length > 0 then
    return strrnd(length - 1) .. charset[math.random(1, #charset)]
  else
    return ""
  end
end

-- Create random strings
local function worker1(id,set)
  -- Create random string
  local results = T{}
  for i = 1,#set do
    local s = strrnd(32);
    results:push(s)
  end
  return results  
end

-- Encrypt all strings
local function worker2(id,set)
  -- Create encrypted strings
  local results = T{}
  for i = 1,#set do
    results:push(AES.ECB_256(AES.encrypt, key, set[i]))
  end
  return results  
end

local data = sequence(1,1000)
local p = Parallel:new(data,{
 workers = 1
})
print('Start ..')
p:time():
  map(worker1):
  map(worker2):
  time()
print('After MaR')

▸

◼

✗

↻

≡

Frage. Welcher Speed-up wird für workers=1,2,3,4 erzielt?

Frage. Wieso ist das Ergebnis hier besser (im Vergleich zu Beispiel 1)?

Hilfe

Einreichung (Assignment #2024-12331 )

Prüfen

Bewerten (Lehrer)

Created by the NoteBook Compiler Ver. 1.27.2 (c) Dr. Stefan Bosse (Sat Jun 29 2024 19:36:28 GMT+0200 (Central European Summer Time))