| Übung 8 zu Verteilte und Parallele Programmierung: Verteilte Programming mit VNetOS (PD Stefan Bosse) |
VNetOS ermöglich die Vernetzung von Fengari-basierten Lua VM Knoten (interne Knoten) untereinander oder mit externen Lua LVM Knoten mit einer grafischen Oberfläche im Web Browser.
In VNetOS gibt es grafische Elemente die die Knoten (virtuelle oder phyisische) abbilden. Ein Knoten besteht aus einer Plattform auf der eine oder mehrere Lua VMs angekoppelte werden. Alle VMs eines Knoten können aus Kommunikationsports zugreifen. Jeder Knoten (nicht VM!) kann bis zu 4 Ports besitzen (mit den Namen NORTH, SOUTH, WEST, und EAST).
Ein folgendes Beispielsnetzwerk besteht aus 4 Knoten mit jeweils einer Lua VM:
Ein Port kann zu einem Knoten durch rechtes Klicken nahe der entsprechendnen Kante und Auswahl "New Com Port" hinzugefügt werden.
Eine neue VM Instanz wird zunächst durch Hinzufügen einer "Slice+Editor" erzeugt. Dort kann ein Lua Programm erstellt oder geladen werden dass dann durch Drücken des "Play" Knopfes eine neue VM Instanz in einem eigenen WebWorker erstellt (bei internen Knoten). Ein Monitor Fenster öffnet sich. Das Schließen des Fensters führt zur Terminierung der VM Instanz.
Ein Lua Programm kann Nachrichten von einem Port über einen Listener empfangen:
Ports[DIR.WEST]:listen()
Ports[DIR.WEST]:receiver(function (msg)
end)
Ein Nachricht kann mittels der send Methode versendet werden:
Ports[DIR.EAST]:send({...})
Die Nachrichten können skalare Daten oder Tabellen sein. Nachrichten werden durch die Mainloop zwischen Knoten vermittelt. Ports von Knoten können durch Erzeugung einer Verbindung (linkes Klicken und ziehen) Nachrichten (i.A. bidirektional) austauschen.
Es gibt vier Richtungen:
DIR.WEST == 1
DIR.EAST == 2
DIR.NORTH == 3
DIR.SOUTH == 4
Es ist sehr mühselig in einem größeren Netzwerk den Programmkode für alle Slices und Knoten einzeln einzugeben. Häufig führt man den gleichen (parametrisierten) Kode auf allen Knoten aus. Dafür kann man Knoten zu einem Cluster zusammenfassen und benötigt nur noch die Erzeugung einer Slice (und einem Editor) auf dem i.A. ersten Knoten. Startet man nun den Kode im Editor über den Play Button wird eine VM auf allen Clusterknoten erzeugt (mit eigenen Monitoren).
Um Knoten in einen Cluster zu vereinen klickt man mit der rechten Maustaste (Kontextmenü) in jedem Knoten, öffnet das Config Menü und trägt im Feld "Cluster" einen einheitlichen Namen oder einheitliche Nummer ein. Alle Knoten mit der gleichen Clusterkennung gehören zum gleichen Cluster. Das sollte erfolgen bevor man eine Slice mit Editor erzeugt.
Das Problem bei einem SIMD Rechner (Single Instruction == Program Code, Multiple Data == Nodes) ist die eigene Knotenidentifikation. In realen Netzwerken hätten die Knoten eventuell überhaupt keine Kenntnis vom Netzwerk und keine Adresse. Wichtig wäre dann für einen Knoten nur seine Nachbarschaft. Diese kann über die Ports abgefragt werden:
local west = Ports[DIR.WEST]:connected()
local east = Ports[DIR.EAST]:connected()
local north = Ports[DIR.NORTH]:connected()
local south = Ports[DIR.SOUTH]:connected()
local left = west <= 0 and east >= 0
local middle = west > 0 and east > 0
local right = west >= 0 and east <= 0
local top = north == 0
local bottom = south == 0
Mittels der Portverbindungen können nur Nachrichten von einem Knoten zu den direkten nachbarn gesendet und empfangen werden. Weiter reichende Kommunikation benötigt ein Vermittlungsprotokoll (Routing).
Ein Δ-Vektor beschreibt die relative Distanz zu einem Zielknoten mit der Anzahl der Knoten:
Bei jeder Weiterleitung in eine kartesische Richtung (x, y, usw.) wird entsprechend des Vorzeichens der Laufrichtung das entsprechende Feld im Vektor um eins reduziert (in Richtung Ziele) oder erhöht (Entfernung vom Ziel).
Das Ziel ist erreicht wenn alle Felder des Δ-Vektors gleich Null sind.
M= ┌―――▶x
{ │
Δ=(1,1) │
Data │
} ▼y
┌―――┐ ┌―――┐
│ │ │ │
│N1 ○――――――――○N2 │
│ │ │ │
└―○―┘ Δ=(0,1)└―○―┘
│ M―――――――▶ │ │
│ │ │
│ │ │Δ=(0,0)
│ │ │
│ │ │
│ │ ▼
┌―○―┐ ┌―○―┐
│ │ │ │
│N3 ○――――――――○N4 │
│ │ │ │
└―――┘ └―――┘
Eine Nachricht besteht daher wenigstens aus dem aktuellen Δ-Vektor und Nutzlastdaten. Damit der Empfänger Kenntnis über der Ursprung der Nachricht hat fügt man noch eine Kopie des Δ-Vektors hinzu, die aber nicht verändert wird (Δ0).
Die Rücksendung einer Nachricht an den ursprünglichen Sender kann durch die Negierung der Felder des Δ0 Vektors erfolgen.
Weiterhin sollte die aktuelle Anzahl von Vermittlungen (hops) und eine Maximalanzahl (Lebenszeit der Nachricht, maxhops) hinzugefügt werden:
M = {
Δ,
Δ0,
hop=0,
maxHop=N,
dir='x'|'y',
lastdir,
Data
}
Wenn jetzt mehrere Felder des Δ-vektors ungleich Null sind gibt es mehrere Möglichkeiten die Nachricht weiterzuleiten (sofern es Verbindungen in die entsprechende Richtung gibt). Man kann eine zunächst bevorzugte Routingrichtung im feld dir angeben.
Lese SLIP10, insbesondere Abschnitt "Slip/Delta Adressing"
Aufgabe. Erstelle ein 3x3 Netzwerk Cluster (siehe oben) in der VNetOS IDE. Verbinde zunächst alle Knoten vollständig (als 2D Gitter). Der Wurzelknoten ist (1,1), d.h. ohne linken und oberen Nachbarn (benutze die Ports[]:connected Funktion um dieses heraus zu finden.
Aufgabe. Implementiere eine Funktion route(M), die eingehende Nachrichten an Nachbarn weiterleitet bis Δ=0. Dann wird die Nachricht an die Funktion deliver(M) übergeben (zunächst Ausgabe der Nachricht). Trage den Programmkode unten ein. Teste mit exemplarischen Nachrichtenzustellungen.
Aufgabe. Erweitere die deliver Funktion mit einer Rücksendung der Nachricht an den Absender (Echo, muss vermerkt werden, sonst gibt es endloses Ping-Pong). Dazu soll die Funktion sendback hinzugefügt werden. Teste mit exemplarischen Nachrichtenzustellungen.
Aufgabe. Lese [SLIP10]. Entferne zwei Verbindungen aus dem Netzwerk (die ursprünglich für die Zustellung benötigt wurden). Erweitere die Routingfunktion und das Nachrichtenformat gemäß oder ähnlich [SLIP10] mit alternativen Routingstrategien um fehlende Verbindungen zu umgehen. Teste einen Pfad der unterbrochen ist.