Einführung in die verteilte und parallele Datenverarbeitung

Was unterscheidet verteilte und parallele Datenverarbeitung?

Welche Eigenschaften besitzen verteilte gegenüber parallelen Systemen?

Performanz

Wir werden noch Metriken und Maßzahlen für die Bewertung von verteilten und parallelen Systemen und Programmen kennen lernen

Startpunkt: Sequenzielle Performanz

Rechenzeit

Speicherbedarf

Messung der sequenziellen Performanz sollte vergleichbar (also normiert) sein bezüglich:

Rechnerarchitektur

Speicherarchitektur

Programmiersprache und ggfs. VM

Benchmarks

Es gibt eine Vielzahl von Benchmarks um die Rechenleistung von Rechnern zu bestimmen:

Häufig elementare Maschineninstruktionen / Zeiteinheit (GIPS/FIPS)

Aber sind solche Masszahlen für uns hilfreich?

Besser Vergleich verschiedener Programmiersprachen und deren VM Leistung

Whetstone

Dhrystone

Dhrystone

Berücksichtigt eine große Menge von Operationen die typischerweise in Programmen vorkommen:

Berechnung und Zuweisungsanweisung

Verschiedene Datentypen: Skalare, Arrays, Rekords, Objekte (mit Methoden)

Statische und dynamische Speicherallokation (in VMs i.a. immer dynamisch!)

Funktionen und Funktionsaufrufe

Kontrollflusskonstrukte (Schleifen, bedingte Verzweigungen)

https://dl.acm.org/doi/pdf/10.1145/358274.358283 Weicker, R. P. (1984). Dhrystone: a synthetic systems programming benchmark. Communications of the ACM, 27(10), 1013-1030

Abbildung 1-1. Analyse der prozentualen Verteilung von verschiedenen Anweisungen in verschiedenen Programmiersprachen [Weicker, R. P. (1984)]

Führe den Dhrystone Benchmark Test auf verschiedenen Rechnern und verschiedenen VM (und native C Version) aus. VMs: JavaScript, Python, Lua

Ergebnisse:

Terminologie

Prozessor

Eine physische Datenverarbeitungseinheit als Teil einer Maschine die i.A. sequenziell einen Strom aus Anweisungen schrittweise verarbeitet.

Virtuelle Maschine

Ein Programm dass einen Prozessor emuliert.

Programm

Eine Menge aus Anweisungen, die von einem Prozessor oder einer Virtuellen Maschine verarbeitet werden kann. Ein Programm enthält neben Anweisungen auch Daten.

Prozess

Ein Programm in Ausführung mit einem zeitlich veränderlichen Daten- und Kontrollzustand

Verteilte vs. Parallele Systeme

Verteiltes System

Ein verteiltes System ist eine System aus lose gekoppelten Prozessoren oder Computern, die über ein Kommunikationsnetzwerk miteinander verbunden sind (Multicomputer).

Speichermodell: Verteilter Speicher → Jeder Prozessor verfügt über privaten Speicher

Kommunikation: Nachrichtenbasiert über Netzwerke

Ressourcen: Nicht direkt geteilt

Paralleles System

Ein paralleles System ist ein Zusammenführung von stark gekoppelten Prozessoren (Multiprozessoren)

Speichermodell: Gemeinsamer geteilter Speicher (Shared Memory)

Kommunikation: Prozessoren greifen auf Speicher direkt über elektrische Signale zu → Switched Network (Kreuzschiene) | Bus → Punkt-zu-Punkt | Punkt-zu-N-Netzwerke

Ressourcen: Gemeinsam genutzt (Bus, Speicher, IO)

Man unterscheidet: Mehrkern und Mehrprozessor Rechner

[1]

Taxonomie von verteilten und parallelen Systemen

Verteilter Speicher

Jeder Prozessor hat eigenen Speicher

Netzwerk aus Prozessoren/Maschinen

Zugriff auf Speicher erfordert nachrichtenbasierte Netzwerkkommunikation

Vorteil: Speicher ist skalierbar mit Anzahl der Prozessoren

Nachteil: Langsamer Speicherzugriff zwischen Prozessen

[computing.llnl.gov]

Geteilter Speicher

Unified Memory Architecture

Symmetrisches Multiprocessing (SMP)

Vorteil: Konstante Zugriffszeit auf Speicher

Vorteil: Schneller Speicherzugriff zwischen Prozessen

Non Unified Memory Architecture

Vorteil: Clustering von SMPs

Nachteil: Ungleiche Zugriffszeiten auf Speicher

Speichermodell und Speicherarchitekturen

Das Speichermodell und die Speicherarchitektur einer Rechneranlage bestimmen wesentlich über die Performanz und Skalierbarkeit von paralleler und verteilter Datenverarbeitung!

Speicherhierarchie

Speichersysteme sind in modernen Rechneranlagen mehrstufig aufgebaut.

Speicher enthält: 1. Daten 2. Anweisungen (Code)

Das Speichersystem S eines Rechners besteht aus einer Pipeline von unterschiedlichen Speichermodulen si mit unterschiedlichen Speichergrößen mi:

image-placeholder
(1-1)

Warum gibt es ein hierarchisches Speichersystem?

Je größer die Speicherkapazität eines Speichermodules ist, desto langsamer ist der Speicherzugriff. Daher unterschiedliche Ebenen mit unterschiedlichen Größen und Zugriffszeiten (Cachekonzept)

Verteilte Systeme

Entwurfskriterien und Eigenschaften

Namensgebung

Wie können wir ein Objekt benennen, das weit entfernt an einem unbekanntem Ort ist?

Robustheit

Was passiert, wenn eine Maschine oder ein Netzwerk ausfällt?

Sicherheit

Wie können wir unser System vor Versagen, Betrug, Eindringen, Diebstahl von Daten, ... schützen?

Performance

Langsamer als je zuvor?

Konsistenz

Ich mache eine Banktransaktion, die Bestätigung der Transaktion ging verloren, und die Transaktion wurde wiederholt. Mein Konto wurde zweimal belastet? Was passiert bei gleichzeitigen Zugriff?

Skalierbarkeit

Was passiert mit diesen Kriterien, wenn wir die Anzahl der Prozessoren/Maschinen um das Zehnfache erhöhen?

Parallele Systeme

Definition

Zerlegung (Partitionierung) eines sequenziellen Algorithmus oder eines Programms in parallele Tasks (Prozesse) → Parallele Komposition

Ausführung der Prozesse parallel (nebenläufig und ggfs. konkurrierend) auf mehreren Verarbeitungseinheiten (u. A. generische programmgesteuerte Prozessoren)

Motivation für parallele Datenverarbeitung

Verkleinerung der Berechnungslatenz

Def. Latenz: Gesamte oder Teilbearbeitungszeit eines Datensatzes

Erhöhung des Datendurchsatzes

Def. Datendurchsatz: Anzahl der verarbeiteten Datensätze pro Zeiteinheit

Latenz und Bandbreite sind zunächst unabhängig!

Pipelining kann die Bandbreite erhöhen (nur sinnvoll bei Datenströmen), aber nicht die Latenz!

Parallele Tasks können die Latenz verringern

Unterschied von Latenz (oben, einzelner Datensatz) zu Bandbreite (unten, Datensatzstrom)

Parallelität und Nebenläufigkeit

Parallelität und Nebenläufigkeit ist ein zeitliches Ablaufmodell

Beschreibt eine zeitliche Überlappung oder Gleichzeitigkeit bei der Ausführung von parallelen Prozessen

Nebenläufigkeit kann ohne Synchronisation auskommen!

Konkurrenz

Concurrent → übereinstimmend!

Konkurrenz beschreibt den Wettbewerb um geteilte Ressourcen!

Wettbewerb bedeutet Konflikt welcher aufgelöst werden muss!

Synchronisation zw. Prozessen!

Konsens Programmiermodell!

Abbildung 1-2. (Links) Zeitlich überlappende parallele Ausführung von Datenverarbeitung (Rechts) Zeitlich versetzte und synchroniserte Datenverabeitung mit geteilten Ressourcen und Konkurrenz [blog.golang.org]

Abbildung 1-3. (Links) Zeitlich überlappende parallele Ausführung von Datenverarbeitung (Rechts) Zeitlich versetzte und synchroniserte Datenverabeitung mit geteilten Ressourcen und Wettbewerb (Konkurrenz)

Konkurrenz (Wettbewerb)

Es gibt eine oder mehrere geteilte Ressourcen ℝ={R₁,R₂,..}, die nicht atomar sind und daher immer nur einzeln verändert werden dürfen (nicht parallel) → Datenkonsistenz

Gleichzeitiger Zugriff wird bei paralleler Ausführung irgendwann zu einem Zeitpunkt t ≥ 0 auftreten

Die Ausführung des gleichzeitigen Zugriffs wird dann aber sequenziell durchgeführt!

Parallelität/Nebenläufigkeit wird durch die Ausführungsplattform bereitgestellt!

Wettbewerb/Konkurrenz muss i.A. durch Programmierung gelöst werden!

Sequenzielle Programmierung mit Lua

Lua ist eine einfach zu erlernende sequenzielle Programmiersprache für Klasse 1/2/3 Interpreter und Skriptprogrammierung

Lua bringt aber auch wichtige Konzepte für die parallele Programmierung mit: Anonyme Funktionen, Funktionale Ausdrücke, Programmflussblockierung

Lua :: Daten und Variablen

Variablen werden mit dem Schlüsselwort local definiert → Erzeugung eines Datencontainers!

Es gibt keine Typendeklaration in Lua! Dynamische Typisierung zur Laufzeit. Kerndatentypen:

Tcore={number, boolean, table, string, function, nil}

Alle Variablen sind polymorph und können alle Werttypen aufnehmen (auch dynamisch wechselnd zur Laufzeit).

Bei der Variabledefinition kann ein Ausdruckswert zugewiesen werden

local v = ε;  v = ε; u = ε(v);

Definition 2-1. Definition von lokalen Variablen und Verwendung in Anweisungen und Ausdrücken

Beispiele Variablen und Ausdrücke

/shelllvm

size

var

local a
local b,c=1,2
print(b,c)
print(type(a),type(b))
print(a+1)

assign

local x
local y=1.5
x = 1
x = x+1
x = x*y-1
print(x)
print(x/2+y)

Lua :: Funktionen

Funktionen können mit einem Namen oder anonym definiert werden

Funktionen sind Werte 1. Ordnung → Funktionen können Variablen oder Funktionsargumenten zugewiesen werden

Eine Funktion kann einen Wert mit der return Anweisung zurückgeben. Ohne explizite Wertrückgabe → undefined

Es wird nur Call-by-value Aufruf unterstützt - jedoch werden Objekte, Funktionen und Arrays als Referenz übergeben; Parameter pi sind an Funktionsblock gebunden

function foo (p1,p2,..)
  local p;
  statements;
  return ε
end
⇒
foo(ε1,ε2,..)

Definition 2-2. Funktionsdefinition und Anwendung

Da in Lua Funktionen Werte erster Ordnung sind können

Funktionen an Funktionen übergeben werden und

Funktionen neue Funktionen zurückgeben (als Ergebnis mit return)

Und Funktionsaufrufe können geschachtelt und rekursiv sein:

function f(x) return ε(x) end
function g(x) return f(ε(x)) end
function fac(n) if n>1 then return n*fac(n-1)
                else return n end
x=g(f(ε))

Es können daher anonyme Funktionen function (..) .. end definiert werden die entweder einer Variablen als Wert oder als Funktionsargument übergeben werden:

local foo = function (pi) return ε(pi) end
a = T{1,2,3}
b = a:map(function(elem,index) return ε(elem,index) end)

Beispiele Funktionen

/shelllvm

size

fun1

function sq(x)
  return x*x
end
function foo(v,i)
  return sq(v)+i
end
function log(v)
  print('Wert von v='..v)
end
local a,b
a=112
b=sq(a)/(1-sq(a+1))
print(type(sq))
print (a,b)
log (foo(a,b))

fun2

function fib(n)
  if n <= 2 then
    return 1
  else
    return fib(n-1)+fib(n-2)
  end
end
print(fib(4))

Lua :: Datenstrukturen

In Lua sind Objekte universelle Datenstrukturen (sowohl Datenstrukturen als auch Objekte) die mit Hashtabellen implementiert werden. Arrays werden in Lua ebenfalls als Hashtabelle implementiert!. D.h. Objekte == Datenstrukturen == Arrays == Hashtabellen.

Es gibt kein nutzerdefinierbares Typensystem in Lua.

Eine Datenstruktur kann jederzeit definiert und verändert werden (d.h. Attribute hinzugefügt werden)

local dataobject = {
  a=ε,
  b=ε, ..
  f=function () .. ed
}
..
dataobject.c = ε

Auswahl eines Arrayelements: array[index]

Auswahl eines Datenobjektelements (Attribut): dataobject.attribute

Dadurch dass Objekte und Arrays mit Hashtabellen implementiert (d.h. Elemente werden durch eine Textzeichenkette referenziert) werden gibt es verschiedene Möglichkeiten auf Datenstrukturen und Objektattribute zuzugreifen:

dataobject.attribute ↔ dataobject["attribute"] ↔
array[index] ↔ array["attribute"]

Definition 2-3. Lua Äquivalenz Array und Datenstruktur

local data = { 1,2,3,4 }
local complex = { r=1, i=-1 }

Beispiel 2-1. Lua Datenobjekte

Lua :: Objekte

Objekte zeichnen sich in der objektorientierten Programmierung durch Methoden aus mit der ein Zugriff auf die privaten Daten (Variablen) eines Objekts möglich wird.

In Lua kann auf Variablen eines Objekts (die Attribute) immer direkt zugegriffen werden.

Attribute können Funktionen sein - jedoch können die Funktionen nicht wie Methoden direkt auf die Daten des Objektes zugreifen.

Daher definiert man Methoden über Prototypenerweiterung in Lua.

Die Methoden können über die self Variable direkt auf das zugehörige Objekt zugreifen (also auch auf die Variablen/Attribute)

Es gibt eine Konstruktionsfunktion (Muster über class Funktion erzeugbar) für solche Objekte mit Prototypendefinition der Methoden

Objekte werden mit dem new Operation durch die Konstruktionsfunktion erzeugt.

constructor=Class() -- Alt: class()
function constructor:init (pi)
  self.x=ε
  ..
end
function constructor:method (..) {
  self.x=ε;
  ..
}
...

local obj =  constructor:new(..);
obj:method(..)

Definition 2-4. Lua Objektklassen mit Definition einer Konstruktorfunktion, Objektinstanziierung, und Methodenanwendung

/shelllvm

size

objects1

stru = {
  x=100,
  y=200,
  z={name='test',id=0}
}
arra = {
  100,
  200,
  'test'
}
table.insert(arra,'more')
print(arra)

objects2

arra = T{
  100,
  200,
  'test'
}
arra:push('more')
print(arra)

objects3

c = class()
function c:init( start)
  self.x = start
end
function c:up ()
  self.x = incr(self.x)
end
function c:down ()
  if self.x > 0 then
    self.x = decr(self.x)
  end
end
function c:get ()
  return self.x
end
s = c:new(1)

Zusammenfassung

Verteilte und parallele Systeme unterscheiden sich vor allem durch die Kopplungsstärke der Verarbeitungselemente (Prozessoren) und dem Speichermodell:

Geteilter Speicher

Verteilter Speicher

Es wird unterschieden zwischen paralleler == nebenläufiger Ausführung und Wettbewerb um geteilte Ressourcen

Eine sequenzielle Programmiersprache wie Lua bietet direkt keine Sprachkonstrukte für die Parallelisierung von Programmen, aber:

Funktionen als Werte 1. Ordnung erlauben die funktionale Parallelisierung, die noch behandelt wird.

Zelluläre Automaten

Einführung von Grundprinzipien beim Entwurfs von VP Systemen

Zelluläre Automaten als einfache VP Architektur und Datenverarbeitungsmodell

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;

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.

Parallele Semantik

Abbildung 3-1. Arten von Parallelität [mogill.github.io/ems/Docs/index.html]

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

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.

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₁,..,sn}.

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

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

image-placeholder
(3-1)

Architektur und Grundprinzip

Abbildung 3-2. Zellulärer Automat als Netzwerk aus einfachen kommunizierenden Berechnungseinheiten [Hoekstra,SCSCA,2010]

Nachbarschaftsrelationen sind auch bei Agenten wichtige Eigenschaft

Abbildung 3-3. Verschiedene Nachbarschaftsrelationen [Hoekstra,SCSCA,2010]

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

Abbildung 3-4. Anzahl der Regeln eines ZA in Abhängigkeit der Anzahl der Zustände pro Zelle und des Verbindungsgrades der Zellen [Hoekstra,SCSCA,2010]

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

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)

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)

image-placeholder
(3-2)

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

image-placeholder
(3-3)

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

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)

Abbildung 3-5. 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 [Rosin,2002]

Rauschunterdrückung

Abbildung 3-6. Rauschunterdückung durch einen binären ZA: (a) Originalbild (b) Verrauschtes Bild (c) Entrauschtes Bild mit dem unten gezeigten Regelsatz [Rosin,2002]

Kantendetektion

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

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

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!

ZA Modell

 1: type model = {
 2:   rows : number, columns : number,
 3:   neighbors: number,
 4:   palette : string [],
 5:   cell : cell class,
 6:   data? : {},
 7:   start : { name:string, distribution:number }
 8: }
 9: type cell class = {
10:   method before (),
11:   method activity (neighbors),
12:   method after (),
13:   method color () -> number,
14:   method initialize (x,y),
15: }

Kode 3-1. Modell eines ZA der cellauto Bibliothek (Typsignatur)

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

Kode 3-2. Definition der Zellenklasse: Das dynamische Höhlensystem

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 }
}

Kode 3-3. Das ZA Modell in Lua

/webwork

ca1

load('cat.plugin');
this.model = {
  rows: 100,
  columns : 100,
  neighbors : 8,
  palette : ['white','red'],
  scheduler : 'UPRIGHT',  // two phase all before; all process
  cell : {
    name : 'wall',
    size : 4,
    state : { open:0, wasOpen:0 },
    before : function () {
      this.wasOpen = this.open;
    },
    activity : function (neighbors,x,y) {
      // neighbors: ordering [<x-r,y-r>,<x-r+1,y-r>,<x-r+2,y-r>,..,<x-r,y-r+1>,..]
      var surrounding = this.ask(neighbors, 'count', 'wasOpen', true);
      this.open = (this.wasOpen && surrounding >= 4) || surrounding >= 6;
    },
    init : function (x,y) {
      // this.open = Math.random() > 0.40;
      this.open = this.data[y][x] > 0.40;
    },
    color : function () { return this.open ?  0:1 },
  },
  data : Math.Matrix.Random(100,100).data,
  start :  [{ name: 'wall', distribution: 100 }],
};

ca2

var steps=10,self=this;
this.ca=CA.create({model:this.model});
print(this.ca)
CA.init(this.ca);
later(500,function () { CA.step(self.ca); return steps--; },function () { print('End.') });

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!

Parallele und Verteilte Zelluläre Automaten

Wie kann das ZA Modell für die Parallelisierung und Verteilung genutzt werden?

Wie können geteilte und verteilte Speichermodelle sinnvoll eingesetzt werden?

Wie kann CALUA parallelisiert werden?

Das 1:1 Modell

Die einzelnen Zellen eines ZA sind zunächst völlig unabhängig voneinander → Kontrollpfadparallelität

Die Datenabängigkeit einer Zelle ist auf die Zellen seiner unmittelbaren Umgebung beschränkt → Kurzreichweitige Datenabhängigkeit

Synchronisation erfolgt primär (implizit) durch einen zentralen Takt, der aber nur die einzelnen Phasen des ZA (before, activity, after) einleitet.

Weitere implizite Synchronisation beim Zugriff auf Zustand (Variablen) von Nachbarzellen

Abbildung 4-1. (a) Das parallele (oder verteilte) 1:1 ZA Modell wo jede Zelle von einem physischen Prozessor ausgeführt wird → Verteiltes Speichermodell (b) Das partitionierte 1:N ZA Modell wo ein Bereich des ZA von einem Prozessor ausgeführt wird → Geteiltes und verteiltes Speichermodell

Das Partitionsmodell

Partitionierung der Zellen des ZA in parallele Felder:

Jedes Feld besteht aus einer Gruppe aus Zellen Fi={z∈Z} ⊂ Z für sich: Ein P mit SM, Zellen eng gekoppelt

Alle Felder: Verteilter Zellenrechner, Multi-P, Felder lose gekoppelt über Verteilten und geteilten Speicher (DSM)

Man unterscheidet:

Kernbereiche eines Feldes (Untergruppe von Zellen aus F) mit reinem SM Modell, und

Überlappende Randbereiche mit DM Modell

Es gibt weiterhin einen gemeinsamen Takt (Synch.)

Abbildung 4-2. Partitionierter ZA mit gemischten SM und DSM Modellen (Kern- und Randbereiche)

Parallele Programmierung des ZA

Da das Speichermodell der Kern- und Randzellen unterschiedlich ist müsste explizit bei der Programmierung zwischen Zellen im eigenen Feld und im Nachbarfeldern unterschieden werden!

Die Kommunikation bei Zellen innerhalb eines Feldes ist ein direkter Speicherzugriff,

bei verteilten Feldern (physisch getrennte Rechner) ein Nachrichtenversand (DSM),

und bei SM auf einem Parallelrechner (Multi-core Rechner) wieder ein direkter Speicherzugriff, aber bei Verwendung einer VM auf ein spezielles geteiltes Speicherobjekt!

Monitore

Um heterogene und nicht einheitliche Programmierung (Siehe Entwurfsprinzipien von Verteilten Systemen!) können Objektmonitore eingesetzt werden

Sogenannte getter/setter Funktionen überwachen den Zugriff auf Feldern von Objekten (Proxy)

Bei Nachbarzellen innerhalb eines Feldes wird direkt auf die Objektvariablen zugegriffen

Bei Nachbarzellen außerhalb des Feldes wird entweder Nachrichtenkommunikation verwendet (Achtung: ausführungsblockierend!) oder bei SM auf ein spezielles geteiltes Speicherobjekt zugegriffen

function C:initialize (..)
    for k,v in pairs(parameter.state) do
      if shared then
        self.__state[k]=v
      else
        self[k]=v;
      end
    end
end
function C:__newindex( index, value )
   if index ~= '__state' and self.__state ~= nil and self.__state[index] ~= nil then
     if shared then model.shared[index]:write(value,self.y,self.x)
     else self.__state[index] = value end
   else
     rawset( self, index, value )
   end
end
function C:__index( index )
    if index ~= '__state' and self.__state ~= nil and self.__state[index] ~= nil then
      if shared and then return model.shared[index]:read(self.y,self.x)
      else return self.__state[index] end
    else
      local value = rawget( self, index )
      if value == nil then return rawget (getmetatable(self), index)
      else return value end
    end
end

Bei einem Zugriff auf die Zustandsvariablen einer Zelle, also z.B. self.open, werden die Setter und Getter Funktionen aufgerufen

Handelt es sich um eine geteilte Randzelle und bei dem Objektzugriff um eine Zustandsvariable (aus der state Definition der Zelle), wird ein von allen Randzellen geteilter Speicher verwendet, ansonsten die lokale private Speicher einer Zelle

Anstelle des geteilten Speicherzugriffs könnte auch nachrichtenbasierte Kommunikation verwendet werden (read/write Remote Procedure Call)

Abbildung 4-3. Objektmonitore implementieren lokalen, geteilten, und verteilten Speicherzugriff: Virtualisierung des Speicherzugriffs durch getter und setter Methoden

Aber: Sowohl der Zugriff auf geteilten (und geschützen) als auch vor allem auf verteilten Speicher verursacht erhöhte Laufzeitkosten!

Da die Zelloperationen i.A. geringe Rechenkomplexität aufweisen kann das parallele ZA Modell schnell ineffizient werden (Skalierunsgproblem)

Abbildung 4-4. (Links) Partitionierter ZA mit lokalen und geteilten Speicher in den Randbereichen (Rechts) Prozessablaufmodell: Fork & Join Phasen (jeweils einzeln für *before*, *activity*, *after*)

Multi-Computer Parallelrechner: GreenArrays GA144

Abbildung 4-5. GA144 Array Rechner (ein Mikrochip!) [www.greenarraychips.com]

Der GA144 Parallelrechner bietet:

144 F18A FORTH Prozessoren (FORTH: Interpretersprache, stackbasiert)

Anordnung der einzelnen Prozessoren in einem 2D Gitter mit Nachbarknotenkommunikation

Pro F18A Knoten: 9k Word RAM

96GIPS!

14μW - 650mW Leistungsaufnahme

Kein zentraler Takt! Asynchrone Digitallogik

Zusammenfassung

Parallelisierung und Verteilung von Zellulären Automaten erfordert ein hybrides Speichermodell (lokal privat, geteilt, und verteilt)

Durch die kurzreichweitige Datenabhängigkeit der Zellen kann durch Feldpartitionierung der Kommunikationsaufwand deutlich reduziert werden (nur Randzellen benötigen geteiltes Speichermodell mit direkten oder nachrichtenbasierten Zugriff)

Objektmonitore können ein einheitliches Programmierkonzept erzielen und Virtualisierung von dem darunterliegenden Speichermodell erreichen

Virtuelle Maschinen

Virtualisierung

Motivation von Virtualisierung:

Abstraktion der Maschine und Speicher

Abstraktion und einfache Wiederverwendung von Algorithmen

Abstraktion von Kommunikation

Abstraktion von Parallelisierung und Verteilung!

Abstraktion der Maschineninstruktion ⇒ Instruction Set Architecture (ISA) ⇒ ISA kann physisch oder nur virtuell existieren

Virtualisierung V ist die Abstraktion und Vereinheitlichung von:

Mikroprozessor ISA

Multitasking, Synchronisation

Sensoren, per. Geräte, Aktoren

Kommunikation und Konnektivität (Protokolle)

Speicher (GC, Tupelräume)

Semantische Daten, Kontext und Ort

Virtualisierung V transformiert i.A. eine Applikationsprogrammierschnittstelle (API) in eine andere API höherer Komplexität.

image-placeholder
(5-1)

VM für eingebettete Systeme:

Lua (eLua, 32 Bit, 64kB RAM, 256kB ROM, GC, speed-down 1:100)

FORTH (Mecrisp, 32 Bit (≥8), 1kB RAM, 16 kB ROM, JIT!, no GC, speed-down 1:10)

Abbildung 5-1. Computer System Architektur mit verschiedenen Ebenen (Software, Betriebssystem, Hardware) → verschiedene Virtualisierungsebenen [A]

     Java Application
           │
           │  Java VM jvm (bytecode)
           ∇
       Linux IA32
           │
           │  VMWARE (x86)
           ∇
      Windows IA32
           │
           │  Code Morphing (x86 ──▶ Risc)
           ∇
      Crusoe VLIW

Beispiel 5-1. Drei Ebenen von VMs. Eine Java-Anwendung, die auf einer Java-VM ausgeführt wird (Linux OS), die auf einer System-VM ausgeführt wird (Windows OS), die wiederum auf einem Code Morphing Prozessor VM läuft (VLIW: Very Large Instruction Word)

Prozessvirtualisierung

Einzelne Ausführungsprozesse werden virtualisiert

Häufig werden Programme in einer eigenen Metasprache und einem speziellen Anweisungsformat ausgeführt (Bytecode, Text)

Java Virtual Machine (jvm)

Lua Virtual Machine (lua, luajit, plvm)

JavaScript Virtual Machine (Google v8, jerryscript, spidermonkey)

OCaML Bytecode VM (funktionale Programmierung)

Benötigt spezielle Verabeitung der Programme (nur auf dieser VM ausführbar)

Abstraktion von Hardware und Betriebssystemebene

Abbildung 5-2. Prozessvirtualisierung (Abstraktion von Hardware und Software) → Highlevel Language VM → Parallelisierung auf VM Instanzebene (1:1 Zuordnung P:VM) [A]

Systemvirtualisierung

Hier wird die Maschine (Hardware) virtualisiert

Verschiedene Programme und Programmformate können konventionell ausgeführt werden

Parallele Ausführung verschiedener gekapselter Betriebssysteme

Parallelisierung kann entsprechend des Betriebssystem auf OS und Prozessebene erfolgen

Die VM selbst kann parallele IO Ausführung nutzen

Abbildung 5-3. Systemvirtualisierung (Abstraktion von Hardware) und Parallelisierung (1:1 Zuordnung einer VM Zone zu virtuellen Prozessor) [A]

Abbildung 5-4. Beispiel: Zwei Betriebssysteme werden auf virtualisierter Hardware (parallel) ausgeführt [A]

Compiler

Abbildung 5-5. Klassischer Softwareentwurf mit Compiler und Linker (C)

Interpreter

Abbildung 5-6. Edit - Compile - Execute Zyklus bei einem Interpreter

Virtuelle Maschine und Bytecode Interpreter

Die Übersetzung des Quelltextes in Bytecode kann vor und während der Ausführung des Programms erfolgen!

Bytecode kann privat und abstrakt sein (nur interne Datenstrukturen) oder öffentlich in kodierter Binär- oder Assemblerform.

Ausführung des Bytecodes durch VM. Vorteile:

Unabhängig von Hostplattform

Virtuelle Maschine kann optimiert werden ohne dass der Bytecode neu erzeugt werden muss

Abstraktion der Speicherverwaltung (automatisches Speichermanagement)

Parallelisierung kann durch VM automatisch erfolgen (wenn möglich)

Abstraktion der IO Schnittstellen und Kommunikation

VM kann Bytecode zu Beginn der Ausführung oder zur Laufzeit dynamisch und nach Bedarf optimieren (JIT)

Abbildung 5-7. Vergleich Interpreter mit Bytcode Compiler-Interpreter System [Python]

Bytecode Ausführung

Bytecode wird i.A. durch eine große Ausführungsschleife ausgeführt. Diese besteht i.A. aus einem Dekoder (Mehrfachauswahl) und operationalen Programmabschnitten. Nach jeder Instruktion kann ein Taskwechsel erfolgen (Scheduling Point) um fein granuliertes Multitasking zu ermöglichen.

1: while not terminated do
2:   operation = decode(code[next])
3:   select operation.code of
4:     case OP₁ => DO IT
5:     case OP₂ => DO IT ..
6:   endcase
7:   compute next
8:   if scheduling point then yield endif
9: done

Serialisierung

Da Bytecode unabhängig von der Hostplattform sein sollte, kann Bytecode einfach von einer Maschine zu einer anderen übertragen und ausgeführt werden

Dazu ist eine Serialisierung von Daten und Code erforderlich (Flache Liste von Bytes), mit anschließender Deserialisierung (Wiederherstellung der Daten- und Codestruktur)

Abbildung 5-8. Serialisierung transformiert ein Objekt in ein implementierungs- und systemunabhängiges Format (a) für die Netzwerkübertragung (Text!) (b) für die persistente Speicherung [A]

Abbildung 5-9. Bytecode VM [Peter Cawley]

Lua Bytecode

Lua Bytecode besteht aus Instruktionen mit konstanter Wortlänge (4 Byte)

Abbildung 5-10. Lua Byte Code Format und Beispiel [102]

JIT Compiler

Neben der Bytecode Ausführung kann während der Laufzeit des Programms der Bytecode stückweise optimiert werden → Erzeugung von Maschinencode durch einen Just-in-Time Compiler (JIT)

Abbildung 5-11. Vergleich Bytecode VM Interpreter mit JIT Compiler-Interpreter Systemen [King Fahd University of Petroleum and Minerals]

Virtualisierung

Aufgabe

Überlege Dir die Vor- und Nachteile von

Compilern

Interpretern

Bytecode Interpretern

JIT Compiler und Interpreter

Was sind die Bewertungskriterien?

Welche Ausführungsarchitekturen könnten für Parallele Systeme mit VMs geeignet sein?

Wo gibt es Engpässe?

Rechenleistung, Speicherbedarf, und Ein-Ausgabe Durchsatz/Latenz sind wichtige Metriken für den Einsatz in Eingebetteten Systemen → Sensornetzwerke / Internet der Dinge (IoT)

Abbildung 5-12. Typische Datenverarbeitungsebenen in Eingebetteten Systemen und Virtualisierung [B]

NODE.JS Architektur

Neben der Bytecode+JIT VM gibt es einen großen Bereich für Ein- und Ausgabeverarbeitung (IO) und nativen Bibliothekenbindungen (Wrappers)

Abbildung 5-13. Die "Eventloop" und die UV Bibliothek sind neben der Google V8 JS VM zentraler Architekturbestandteile

Performanz von Interpretern

Dhrystone Benchmark (Kombination aus Berechnung, Objekten, Arrays, Strings, Funktionen)

VM/OS-ARCH | Linux-i686 | Linux-armv6l (PI-3B) | Linux-armv6l (PI Zero)
python2.7¹ | 105k/s | 23k/s | 4k/s
lua 5.1² | 140k/s | 36k/s | -
luajit 2.0.5X/lvm² | 660k/s | 108k/s | 40k/s
jerryscript 1.1.7X³ | 45k/s | - | -
nodejs/V8-4³ | 6300k/s | 879k/s | 40k/s
C/gcc | 18000k/s | 3700k/s | ?

(1: Python, 2: Lua, 3: JavaScript)

Speicherbedarf von Interpretern

Dhrystone Benchmark (Kombination aus Berechnung, Objekten, Arrays, Strings, Funktionen)

VM/OS-ARCH | Linux-i686 | Linux-armv6l (PI-3B) | Linux-armv6l (PI Zero)
python2.7 | - | - | -
lua 5.1 | - | - | -
luajit 2.0.5X/lvm | 2MB | 2MB | -
jerryscript 1.1.7X | 2MB | - | -
nodejs 4/10 | 24MB | 32MB | -
C/gcc | 1MB | ? | ?

Automatisches Speichermanagement

In C/C++ muss für jedes zur Laufzeit dynamisch erzeugte Datenobjekt (Array, String, Record, ..) immer explizit Speicherplatz im Hauptspeicher angefragt werden (malloc,new) und wieder frei gegeben werden wenn das Datenobjket nicht mehr benötigt wird (free,delete)

In Skriptsprachen gibt es i.A. ein automatisches Speichermanagement mit einem sog. Garbage Collector und Objektreferenzierung

Jedes Datenobjekt welches verwendet wird (z.B. in Variablen oder Funktionen) besitzt eine Referenz

Es muss eine Wurzeltabelle geben von der aus alle Referenzen auf verwendete Objekte auffindbar sind

Objekte und Referenzen

Objekte: In C/C++/JAVA usw: Variablen, in Lua/JavaScript/OCaML: Werte!

1: local o₁ = { a=1, b={1,2,3,4} }
2: local o₂ = { op = o₁, index=2 }
3: function show (o) print (o₂.op.a-o.a } end;
4: show(o₁)

Beispiel 5-2. Beispiel von Objektreferenzierungen in Lua: Wo existieren Referenzen?

Variablen, Referenzen, Werte in Lua

/shelllvm

ref1

local o1 = { a=1 }
local o2 = { a=2 }
print(o1.a,o2.a)
o2=o1;
o1.a=3;
print(o1.a,o2.a)

ref2

local o1 = { a=1, b={1,2,3,4} }
local o2 = { op = o1, index=2 }
function show (o) print (o2.op.a-o.a) end;
show(o1)

Abbildung 5-14. Verschiedene Objekte: Objekte die nicht mehr referenziert sind, werden freigegeben [A]

Speicherarchitektur von Programmen

Code

Statischer oder dynamischer Speicherbereich mit Maschinenanweisungen (und eingebetteten Daten als Anweisungsoperanden)

Heap

Datenobjekte mit längerer Lebensdauer (Tabellen- oder Listenstruktur) → Benötigt Speichermanagement

Stack

Datenobjekte mit kurzer Lebensdauer (Stapelstruktur) → Benötigt kein Speichermanagement

Abbildung 5-15. Speicherhierarchie von Programmen und Zusammenhang mit Maschinenanweisungen

Speicherorganisation von Virtuellen Maschinen

Speicherbereiche sind segmentiert

Statisch

Größe

Inhalten (Daten)

Dynamisch

Größe

Inhalten (Daten)

Fragmentierung

Stack, Code: nein

Heap: ja!

Speicher

Die meisten Objekte in Programmiersprachen benötigen Speicher

Lokale, temporäre, und globale Variablen

Objekte

Arrays

Zeichenketten

Funktionen (!)

Native Codereferenzen (Speicheradresse)

Der Kontext von Speicherobjekten ist wichtig:

Modul → limitierte Programmsichtbarkeit

Lokal → stark limitierte Programmsichtbarkeit

Global → uneingeschränkte Sichtbarkeit

Speicher und Variablen

Beispiele: Die globale Variable Global ist überall, auch außerhalb des Definitionsmoduls, sichtbar, die Variable lokal ist im gesamtem Modul und den Funktionen f1 und f2 sichtbar, wo hingegen lokal1 und lokal2 jeweils nur ihrem Funktionskontext sichtbar sind.

Global = 1
local lokal = 2
function f1 ()
  local lokal1 = 3
end
function f2 ()
  local lokal2 = 3
end

Nur wenn Variablen bei der Ausführung sichtbar sind belegen sie Speicher!

Ein Teil des Speicher ist vorbelegt:

Globale Variablen

Funktionen, ausführbarer Code, ...

Ein anderer Teil des Speichers wird zur Laufzeit auf dem Stack und Heap belegt und benötigt Verwaltung:

Lokale und temporäre Variablen, ..

Funktionen, ausführbarer Code, ...

Achtung: Bei Programmiersprachen bei denen Funktionen Werte erster Ordnung sind befindet sich auch Code im Heap oder auf dem Stack!

Polymorphie und Dynamische Typisierung

Nativer Maschinencode unterscheidet Operanden nach ihren Datentypen → Speicherumfang von Datentypen ist sehr unterschiedlich (Boolean, Float64, Int16, Arrays, Records, ..)

HLL Skript Programmierung bietet häufig dynamische Typisierung, d.h., eine Variable hat zunächst keinen Datentyp

Der Datentyp einer Variable ergibt daher sich nur aus den Datentypen von konkreten Werten die die Variable referenziert!

Welche Vor-und welche Nachteile hat dynamische Typisierung zur Laufzeit?

typedef struct {  typedef union {
  int t;            GCObject *gc;
  Value v;          void *p;
} TObject;          lua_Number n;
                    int b;
                  } Value;

Definition 5-1. Lua Werte werden als "tagged unions" repräsentiert (C)

Abbildung 5-16. Lua Tabellen (Arrays, Records) sind Referenzlisten auf weitere Objekte aus Werten

Speichersegmente und Fragmentierung

Ein (statisches oder dynamische) Speichersegment ist ein linearer zusammenhängender Bereich

Mit Virtuellen Speichermanagement kann ein Segment aus einer Reihe verstreuter physischer Speicherbereiche zusammengesetzt werden

Es wird eine Speicherzuordnungsfunktion MMU(VA) → PA benötigt (LUT, nur in Hardware effizient)

Hochsprachen haben kein Speichermodell, sondern nur Speicherobjekte (Variablen)

Man unterscheidet Name, Daten, Datenkontainer und Referenz auf Datenkontainer

Für die Ausführung mit einer Maschinen müssen diese abstrakten Speicherobjekt

Speicherbereiche in Segmenten Seg belegen (allocate(O))

Diese Speicherbereiche referenzieren MMU(O) → Seg,SA

Speicherbereiche in Segmenten müssen wieder frei gegeben werden wenn Objekt nicht mehr verwendet wird (free(O))

Durch Speicherallokation und Freigabe Zyklen (Speicherbedarf der Objekte variiert) kommt es zu Fragmentierung, d.h., der einst lineare Speicherbereich eines Segments besteht aus einer irregulären Folge aus freien und belegten Bereichen

            Segment S
      alloc ┌───────┐  free ┌───────┐   compact ┌───────┐
a:=1 ──────▶│  a=1  │       │  a=1  │           │  a=1  │
b:=2 ───┐   ├───────┤  /b   ├───────┤           ├───────┤
        │   │       │       │       │       ┌──▶│  c=3  │
..      └──▶│  b=2  │       │       │       │   ├───────┤
            ├───────┤       ├───────┤       │   │       │
c:=3 ──────▶│  c=3  │       │  c=3  │       └───┤       │
            └───────┘       └───────┘           └───────┘
               (a)             (b)                 (c)

Beispiel 5-3. (a) Speicherbelegung, (b) Freigabe, und (c) Kompaktierung

Welches Problem tritt bei Kompaktierung auf?

Speicherverwaltung

Listen

Freie und belegte Speicherbereiche werden durch Listen (einfach- oder doppelt verkettet) verwaltet

Tabellen

Tabellen (Hashtabellen) werden zur Speicherverwaltung verwendet

Manuelle Verwaltung

Speicherbelegung explizit vom Programmierer und teils vom Compiler auszuführen

Vorteile

Optimale Speicherbelegung (tatsächlich naiv und falsch) und Performanz/Effizienz

Nachteile

Speicherlecks (nicht mehr benötigter Speicher wird nicht frei gegeben)

Mehrfachfreigabe (Inkonsistenz der Speicherverwaltung)

Benutzung von Speicherobjekten nach Freigabe

Automatische Verwaltung

Die Freigabe von Speicherbereichen wird automatisch durch einen Garbage Collector durchgeführt. Dieser bestimmt auch automatisch ob Speicherobjekte noch benötigt werden.

Vorteile

Speicherlecks werden vermieden

Keine Mehrfachfreigabe (Inkonsistenz der Speicherverwaltung)

Keine Benutzung von Speicherobjekten nach Freigabe

Nachteile

Nicht optimale Speicherbelegung und schlechtere Performanz/Effizienz

Garbage Collection

Wie soll der GC heraus finden ob ein Objekt noch benötigt wird?

Referenzzähler wird jedem Objekt hinzugefügt und bei jeder neuen Referenzierung erhöht (Allocate). Ein Objekt mit Referenzwert Null kann frei gegeben werden.

Der GC rechnet Objektabhängkeiten aus und markiert Objekte die freigegeben werden können

Beispiel von Referenzen und Sichtbarkeit (Programmkontext)

 1: local o₁ = { x=100,y=200 }e₁          [e₁.ref=1(o₁)]
 2: local o₂ = { pos=o₁, color="red" }e₂  [e₁.ref=2(o₂,o₁)]
 3: function draw (o)
 4:   local o₃ = { pos=o.pos, color="white" }e₃  [e₃.ref=1(o₃), e₁.ref=4(o₃,..)]
 5:   local o₄ = { pos={x=o.pos.x,y=o.pos.y}e₄, color="black" } [e₁.ref=5(o₄,o₄,..)]
 6:   draw(o₃)
 7:   draw(o₄)
 8:   → [e₃.ref=0, e₄.ref=0, e₁.ref=3, e₂.ref=2]
 9: end
10: draw(o₂)  [e₂.ref=2(o,o₂), e₁.ref=3(o,o₂,o₁)]
11: o₂=nil    [e₂.ref=0, e₁.ref=1(o₁)]
12: o₁=nil    [e₁.ref=0]

Wichtig: Referenzzähler beziehen sich auf Werte (ei), nicht auf die Variablen selber (die nur Zeiger auf Werte besitzen)

D\.h. wenn ein Wert als Referenz an eine weitere Variable zugewiesen wird erhöht sich der Referenzzähler!

GC: Referenzzählung

Wenn ein Objekt (also ein Wert) erzeugt wird, wird der Referenzzähler auf Null gesetzt

Jede weitere Referenzierung erhöht den Zähler um eins (also bereits das zuweisen eines Objektes an eine variable!)

Wird eine Referenzierung vom Objekt entfernt (explizit → =null, oder implizit durch Entfernen des referenzierenden Objektes), dann wird der Zähler um eins erniedrigt

Ist der Zähler wieder Null, dann wird der Speicher freigegeben

Nachteile

Zyklische Referenzen können nicht aufgelöst werden:

local o1 = { x=100,y=100 }
local o2 = { prev=o1 }
o1.next = o2

Daher werden u.U. nicht alle Objekte freigegeben → Speicherlecks

Der Referenzzähler belegt selber Speicher (gehört zum Objekt). Bei low-resource Plattformen wird z.B. eine Datenwortbreite von 16 Bit für den Zähler verwendet, und der maximale Referenzwert ist 65536 (jerryscript ist so ein Kandidat)!

Allokation ist langsamer (verlangsamt Zuweisung)

Vorteile

Einfach zu implementieren

Freigabe ist effizient (wenig Rechenaufwand)

GC: Mark & Sweep

Bestimmte Objekte sind direkt zugänglich, und es muss herausgefunden werden welche Objekte erreichbar sind → Graphensuche

Es gibt einen Stammsatz von Speicherplätzen im Programm, dessen Objekte direkt erreichbar sind.

Mark-and-Sweep verläuft in zwei Phasen

Markierungsphase

Erreichbare Objekte suchen:

Der Stammsatz wird zu einer Arbeitsliste hinzugefügt

Solange die Arbeitsliste nicht leer ist wird ein Objekt von der Liste entfernt. Wenn es nicht markiert ist, markiere es als erreichbar und alle Objekte die davon aus erreichbar sind werden zur Arbeitsliste hinzugefügt.

Sweepphase

Für alle belegten Objekte:

Ist das Objekt nicht markiert so lösche es (Speicher freigeben)

Ist das Objekt markiert, lösche die Markierung

Vorteile

Auch zyklische Referenzen können über die Arbeitsliste aufgelöst werden

Alle Objekte können frei gegeben werden

Allokation schnell

Nachteile

Rechenintensiv und langsam!

Abbildung 5-17. Beispiel eines M&S Durchlaufes mit anschließender Freigabe von nicht mehr erreichbaren == benötigten Objekten

Multitasking

Auf einem Rechnerknoten gibt es eine Vielzahl von Aufgaben die bearbeitet werden müssen:

Datenverarbeitung

Kommunikation

Speicherung und Ein/Ausgabe

Zum Teil müssten Aufgaben parallel verarbeitet werden → Multitasking → Parallelisierung → nur bedingt möglich → Task Scheduling erforderlich

Es gibt verschiedene Ausführungsebenen für Tasks:

Prozesse

Threads

Fibers/Koroutinen

Prozesse, Threads, Fibers

            (a)                      (b)                     (c)
┌─────────┐    ┌─────────┐  ┌─────────────────────┐  ┌─────────────────────┐
│         │    │         │  │ ┌───────┐ ┌───────┐ │  │            Fiber    │
│ Process │    │ Process │  │ │Thread ├─┤Thread │ │  │   Fiber             │
│         │    │         │  │ └───────┘ └───────┘ │  │       Fiber         │
└────┬────┘    └────┬────┘  └────┬────────────────┘  └─────┬───────────────┘
     │              │            │  Process                │  Process/Thread
┌────┴──────────────┴────────────┴─────────────────────────┴───────────────┐
│                         Operating System                                 │
└──────────────────────────────────────────────────────────────────────────┘

Abbildung 5-18. (a) Zwei isolierte Prozess (b) Zwei gekoppelte Threads in einem Prozess (c) Koroutine (Fibers), nicht isoliert mit einem Kontrollpfad

Virtualisierung und Parallelisierung

Grundkonzept: Aufteilung einer Berechnung in eine Menge von Teilberechnungen die auf verschiedenen Prozessoren parallel ausgeführt werden.

Auf generischen Mehrprozessorsystemen (Multicore) wird Multithreading unf Multiprocessing Kontrollpfade

Auf spezialisierten Mehrprozessorsystemen (GPU) wird sowohl Mutlithreading als auch Datenpfadparallelität ausgenutzt (Mehrere Kontroll- und Datenpfade)

Aber: Bei Virtuellen Maschinen lassen sich diese Konzepte nicht direkt übertragen!

Automatisches Speichermanagement ("stop the world" Phase) schwierig zur parallelisieren (Konkurrenz und Ressourcenkonflikte)

Speicherraum einer VM ist gekapselt (man spricht von einer Ausführungsinstanz oder einem isolierten Kontainer)

VM arbeiten daher i.A. mit nur einem einzigen Kontrollfluss (auf Programmierebene)!

Architekturen Paralleler VMs

Background/Foreground Systeme

Es gibt einem Hauptthread der das Programm ausführt (VM Main Loop)

Es gibt einen Nebenthread der die GC ausführt

Multithreading

Es gibt einen oder mehrere Threads die das Programm ausführen

Es gibt einen oder mehrere Threads die den GC ausführen

Abbildung 5-19. (a) Sequenzielles System (1 Prozess/Thread) Stop-the-world GC (b) Multithreading Stop-the-world GC (c) Multithreading und paralleler/nebenläufiger GC

Parallelisierung des GC Algorithmus

Parallele Markierung

Paralleles Kopieren

Paralleles Sweeping

Paralleles Kompaktieren

Es wird weiterhin Synchronisation zw. den parallel ausgeführten GC Threads und dem eigentlichen VM Ausführungsthread (oder mehreren) benötigt!

Es gibt zwei Motivationen:

GC soll möglich wenig Rechenzeit des Hauptprogramms "kosten" (Horizontale Par.)

GC soll beschleunigt werden (Vertikale Par.)

Synchronisation

Neben der Synchronisierung von Operationen an Kollektordatenstrukturen kann es auch erforderlich sein, Operationen auf einzelnen Objekten zu synchronisieren.

Das Markieren ist im Prinzip eine idempotente Operation: Es spielt keine Rolle, ob ein Objekt mehr als einmal markiert wird.

Wenn z.B. ein Kollektor jedoch einen Vektor von Markierungsbits verwendet, muss der Marker diese Bits atomar setzen

Befehlssätze moderner Prozessoren bieten nicht die Möglichkeit, ein einzelnes Bit in einem Wort oder Byte zu setzen → Setzen einer Markierung erfordert eine Schleife, die versucht, den Wert des gesamten Bytes atomar zu setzen.

Wenn das Markierungsbit im Header des Objekts enthalten ist oder der Markierungsvektor ein Vektor von Bytes ist (einer pro Objekt), ist keine Synchronisation erforderlich

⇒ Also: Die Details von Rechnerarchitektur und GC Algorithmus bestimmen notwendige Synchronisation

Zum GC Algorithmus gehören auch immer die Datenstrukturen und Allokationsmethoden!

Schließlich muss die Beendigung einer Sammelphase korrekt bestimmt werden!

Die Verwendung paralleler Threads macht die Terminierungserkennung deutlich komplexer.

Grundsätzlich besteht das Problem darin, dass ein Thread möglicherweise versucht zu erkennen, ob die Phase beendet wurde, während ein anderer noch arbeitet und eine neue Phase startet!

Barrieren können z.B. für die Synchronisation bei der konkurrierenden/parallelen Kollektion eingesetzt werden

Parallele vs. Konkurrierend

Und wieder muss zwischen paralleler und konkurrierender Ausführung unterschieden werden, was zu unterschiedlichen Abläufen des GC und der VM Main Loop führen

Weitere Unterscheidung durch Horizontale und Vertikale Parallelisierung (Zeit/Raumdimension)

Abbildung 5-20. (rot) Parallele und synchronisierte Ausführung (VM Main Loop angehalten) (blau) Konkurrierende Ausführung und überlappend mit VM Main Loop [Jones, 2012, TGCH]

Parallele VM Instanzen

Parallelität daher durch mehrere VM Instanzen möglich.

Eine Instanz ↠ Ein Prozess (Thread)

Aber: Die Start- und Initialisierungszeit einer VM Instanz kann hoch sein (JS nodejs/v8: 100ms, LuaJit: 1ms)

Weiterhin ist der Speicherbedarf einer VM Instanz zu beachten ("baseline" ohne Nutzprogramm, nodejs: 20MB, LuaJit: 1MB)

Bei hoher Initialisierungszeit einer VM Instanz muss diese im voraus gestartet werden (in-advance) und über eine Service Loop auf Prozesscode warten.

Bei kleiner Initialisierungszeit einer VM Instanz kann ein VM Prozess ad-hoc und dynamisch gestartet werden.

Stack vs Register vs Speichermaschinen

┌─────────┐          ┌─────────┐     ┌──────────┐        ┌─────────┐
│  Stack  │          │  Code   │     │ Register │        │   RAM   │
├─────────┤          ├─────────┤     ├──────────┤        ├─────────┤
│         │◀───┐     │         │  ┌─▶│    R1    │     ┌──┤  Instr  │◀──┐
│         │    │     │         │  │  │          │     │  │         │   │
│  Instr  ├────┤     │  Instr  │◀─┼──┤    R2    │     │  │    Op   ├───┤
│         │    │     │         │  │  │          │     │  ├─────────┤   │
│    Op   ├────┤     │    Op   ├──┘  │    R3    │     │  │  Data   ├───┘
│         │    │     │         │     │          │     │  │         │
│    Op   ├────┘     │         │     │          │     └─▶│         │
└─────────┘          └─────────┘     └──────────┘        └─────────┘
    (a)                          (b)                          (c)

Abbildung 5-21. (a) Stack Maschine (keine ext. Abhängigkeit) (b) Register Maschine (c) Speichermaschine

Parallelisierungsgrad (Multi-Instanz VM): Stack ≫ Register ≫ Speicher

Echtzeitverarbeitung

Echtzeitverarbeitung bedeutet die Ausführung eines Tasks innerhalb eines vorgegebenen Zeitintervalls [t₀,t₁]

Soft Realtime: Zeitüberschreitung bei weicher Echtzeitanforderung → Tolerierbar

Hard Realtime: Zeitüberschreitung bei harter Echtzeitanforderung → Systemfehler

Abbildung 5-22. Echtzeitspektrum: Weiche und harte Echtzeitanforderungen bei unterschiedlichen Applikationen [B]

Abbildung 5-23. Periodische, sporadische, und aperiodische Tasks [B]

Preemption

Wenn schon nicht alles Tasks gleichzeitig verarbeitet werden können, dann wenigstens die wichtigsten vorrangig ausführen

Das erfordert aber:

Festlegung einer Priorität

Bei Echtzeitanforderungen die Unterbrechung von unterlegenen (kleiner Priorität) Tasks

Abbildung 5-24. Unterschied preemptive und nicht preemptive Ausführung von Tasks [B]

Virtuelle Maschinen

Schon die Parallelisierung der Programmausführung ist schwierig und eher schwergewichtig!

Dis Ausführungszeiten von Programmen sind nicht im voraus bekannt und deterministisch

JIT beeinflusst die Ausführungszeit zur Laufzeit signifikant (Übersetzung kostet Zeit, Maschinenkode spart Zeit)

Automatisches Speichermanagement (GC) führt zu teils stark variierenden Laufzeiten und Performanz von Programmen

Bei längerer Laufzeit kann sich die Performanz (Latenz/Datendurchsatz) verringern. Warum?

Echtzeitfähigkeit bei automatischen Speichermanagement ("stop the world" Phase), JIT und umfangreiche Nutzung dynamischer Datenstrukturen kaum zu gewährleisten!

Multiinstanz VM: Beispiel (P)LVM

┌──────────────┬─────┐         ┌─────┬──────────────┐
│     VMI 1    │ GC  │  Ref.   │ GC  │      VMI 2   │
│ X=1          │     │  Count  │     │ X=1          │
│ local c=IPC  ├──▶  │ ◀─────▶ │  ◀──┤ local c=IPC  │
│ function foo │     │ ┌─────┐ │     │ function foo │
│   local x=X  │     │ │     │ │     │   local x=X  │
│   c()   ◀────┬─────┬─┬─────┬─┬─────┬─▶ c()        │
│              │     │ │ IPC │ │     │              │
└──────────────┴─────┘ └─────┘ └─────┴──────────────┘
                        alloc/free
┌───────────────────────────────────────────────────┐
│ ┌──────────────────┐         ┌──────────────────┐ │
│ │   Thread T1      │         │      Thread T2   │ │ Process P
│ └──────────────────┘         └──────────────────┘ │
└───────────────────────────────────────────────────┘

Abbildung 5-25. Zwei Lua LVM Instanzen mit gemeinsamen eng gekoppelten Interprozeßkommunikationsobjekten und implizite GC Kopplung über Referenzzählung

Zusammenfassung

Die Parallelisierung von VMs ist stark eingeschränkt

Hauptsächlich Einschränkungen durch das autom. Speichermanagenent (GC)

Parallel ausgeführte getrennte VM Instanzen auf Prozessebene (Cluster) immer möglich (geringe Kopplung) → Interprozesskommunikation über Nachrichten optional mit generischen SM

Parallel ausgeführte VM Instanzen auf Threadebene mit gemeinsam geteilten Objekten und spezialisierten SM die teils durch GC behandelt werden ist die optimale Lösung!

Parallele Programmierung

Grundlagen der parallelen Programmierung

Unterscheidung zwischen Parallelisierung im Daten- und Kontrollfluss von Programmen

Prozessmodelle und Prozesskonstruktoren

Parallelisierungsklassen

Datenfluss

Der Datenfluss beschreibt den Fluss von Daten durch Verarbeitungs- und Speichereinheiten (Register).

Die Verarbeitungseinheiten sind Knoten eines gerichteten Graphens, die Kanten beschreiben den Datenfluss und bilden die Datenpfade. Die Verarbeitungseinheiten müssen aktiviert werden.

Kontrollfluss

Der Kontrollfluss beschreibt die temporale schrittweise Verarbeitung von Daten im Datenpfad durch zustandsbasierte selektive Aktivierung von Verarbeitungseinheiten.

Der Kontrollfluss kann durch Zustandsübergangsdiagramme beschrieben werden.

Programmfluss

Der Programmfluss setzt sich kombiniert aus Daten- und Kontrollfluss zusammen.

Programmanweisungen werden Zuständen S₁,S₂,.. zugeordnet.

Einfache Anweisungen (Berechnungen) werden jeweils einem Zustand, komplexe Anweisungen i.A. mehreren Unterzuständen zugeordnet.

Abbildung 6-1. Programm-, Kontroll-, und Datenflussgraphen

Datenparallelität

In vielen Programmen werden dieselben Operationen auf unterschiedliche Elemente einer Datenstruktur angewendet. Im einfachsten Fall sind dies die Elemente eines Feldes.

Wenn die angewendeten Operationen unabhängig voneinander sind, kann diese verfügbare Parallelität dadurch ausgenutzt werden, um die zu manipulierenden Elemente der Datenstruktur auf verschiedene Prozessoren zu verteilen, so dass jeder Prozessor die Operation auf den ihm zugeordneten Elementen ausführt.

Parallelität im Datenpfad → Feine Granularität

Bei der Datenparallelität wird unterschieden zwischen:

Parallele Ausführung der gleichen Instruktion auf verschiedenen Daten (Vektorparallelität) → Vektoranweisung

Ausführung verschiedener Instruktionen die nur Daten verarbeiten (reine Datenanweisungen, keine Kontrollpfadverzweigungen)

Zur Ausnutzung der Datenparallelität wurden sequenzielle Programmiersprachen zu datenparallelen Programmiersprachen erweitert. Diese verwenden wie sequenzielle Programmiersprachen einen Kontrollfluß, der aber auch datenparallele Operationen ausführen kann.

Z\.B. μRTL: Bindung von mehreren Datenpfadanweisungen durch Kommasyntax: x ← ε , y ← ε , .. , z ← ε ;

Häufig werden Vektoranweisungen deklarativ und nicht prozedural imperativ beschrieben.

Beispiel für eine deklarative Vektoranweisung und die dazugehörige imperative Anweisungssequenz in Schleifenform (Fortran 90):

1: a(1 : n) = b(0 : n − 1) + c(1 : n) ⇔
2: for (i=1:n)
3:   a(i) = b(i-1) + c(i)
4: end

Datenabhängigkeiten können zwischen der linken und rechten Seite einer Datenzuweisung bestehen, so dass

zuerst auf alle auf der rechten Seite auftretenden Felder zugegriffen wird und die auf der rechten Seite spezifizierten Berechnungen durchgeführt werden,

bevor die Zuweisung an das Feld auf der linken Seite der Vektoranweisung erfolgt!

Daher ist folgende Vektoranweisung nicht in die folgende Schleife sequenziell transformierbar:

1: a(1 : n) = a(0 : n − 1) + a(2 : n + 1) ≠
2: for (i=1:n)
3:   a(i) = a(i-1) + a(i+1)
4: end

Datenparallelität benötigt i.A. keine weitere Synchronisation

Aber Datenabhängigkeiten können zu einer impliziten oder expliziten Synchronisation führen (z.B. mit Queues)

Durch die Verwendung von Queues (oder allg. Kommunikationskanälen) werden Datenabhängigkeiten über einen Blockierungsmechanismus (Verzögerung) aufgelöst. Es gibt Produzenten und Konsumenten. Der Konsument wird solange blockiert bis der Produzent (i.a. der vorherige Prozess) Daten liefert. Umgekehrt kann ein Produzent verzögert werden wenn ein Konsument noch nicht zur Aufnahme neuer Daten bereit ist.

image-placeholder
(6-1)

Instruktionsparallelität

Parallelität im Kontrollpfad (Zustandsautomat) auf Instruktions- und Prozessebene → Grobe Granularität je nach Anzahl der Instruktionen pro Prozess (Task)

Gebundene Instruktionsblöcke sind Parallelprozesse (Par Prozesskonstruktor)

Bekannt als Multithreading als Programmier- und Ausführungsmodell (z.B. pthreads)

Instruktionsparallelität benötigt i.A. Synchronisation zwischen den einzelnen Prozessen

Möglichkeiten der Parallelisierung

Vertikale Parallelität auf Bitebene (jegliche funktionale Operation)

Horizontale Parallelität durch Pipelining (nur Datenströme)

Parallelität durch mehrere Funktionseinheiten:

Superskalare Prozessoren

Very Large Instruction Word (VLIW) Prozessoren

Funktionsparallelität (Evaluierung der Funktionsargumente und Rekursion)

Vertikale Parallelität auf Prozess- bzw. Threadebene (Kontrollpfadebene)

Fluss und Pfadgraphen

Ein Datenfluss (Graph aus Operationen oder Variablen) beschreibt den Verlauf und die Verarbeitung von Daten durch Operationen → Verhaltensbeschreibung

Ein Datenpfad beschreibt die Verbindung von Komponenten zur Implementierung des Datenflusses → Strukturbeschreibung

Der Kontrollfluss beschreibt die zustandsbasierte Steuerung einer Berechnung

Bedingte (↔ Datenfluss) Verzweigungen im Kontrollfluss

Schleifen im Kontrollfluss

Der Kontrollpfad implementiert den Kontrollfluss → Zustandsautomat

Daten- und Kontrollpfade

Jeder generische Mikroprozessor und i.A. jedes anwendungsspezifische Digitallogiksystem lässt sich in die zwei funktionale Bereiche aufteilen:

Datenfluss → Datenpfade

Kontrollfluss → Kontrollpfad → Zustandsautomat

Datenpfad

Führt Berechnungen durch

Kann rein funktional (speicherlos, kombinatorisch) oder speicherbasiert mir Register-Transfer Architektur sein

Kontrollpfad

Der Kontrollpfad ist immer zustandsbasiert (Speicher) und bestimmt die Reihenfolge von Operationen und Berechnungen

Parallelisierung

Der Programmfluss kann in Daten- und Kontrollfluss zerlegt werden, die jeweils im Daten- und Kontrollpfad eines Datenverarbeitungssystems verarbeitet werden.

Kontrollpfad

Parallelität auf Prozessebene (Multithreading) mit Interprozesskommunikation → Mittlere bis geringe Beschleunigung, mittlerer Overhead

Datenpfad

Parallelität auf Dateninstruktionsebene ohne explizite Kommunikation → Hohe Beschleunigung, geringer Overhead

Programm

Ein (prozedurales/imperatives) Programm besteht aus mindestens einem Daten- und Kontrollpfad (oder Fluss)

Ein Programm ist aus einer Vielzahl von Komponenten zusammengesetzt → Komposition

Komposition von Datenfluss und Datenpfad:

Funktionale Komposition

(Sequenzielle Komposition)

Parallele Komposition

Komposition von Daten- und Kontrollfluss/pfad:

Sequenzielle Komposition

Parallele Komposition

Funktionale Programmierung

Funktionale Programmierung beschreibt grundlegend den Datenpfad. Es gibt keinen Zustand und keinen expliziten Kontrollfluss.

Funktionale Komposition

Eine Berechnung setzt sich aus der verschachtelten und verketteten Applikation von Funktionen zusammen, die jeweils aus elementaren Ausdrücken E={ε₁,ε₂,..} bestehen → Funktionale Komposition F(X)=f₁(f₂(f₃..(X)))

Jede Funktion fi beschreibt einen Teil der Berechnung.

Ausdrücke bestehen aus:

Konstante und variable Werte 1,2.0,'c',"hello",x,y,z

Einfache arithmetische Ausdrücke ε=x+y

Zusammengesetzte Ausdrücke (arithmetische Komposition) ε=(x+1)*(y-1)*z

Relationale Ausdrücke x < 0

Boolesche Ausdrücke a and b or c

Bedingte Ausdrücke liefern Werte if x < 0 then x+1 else x-1

Funktionsapplikation f(x,y,z)

Entspricht dem mathematischen Modell was auf Funktionen und Ausdrücken gründet mit den Methoden

Definition f(x) = λ.x → ε(x)

Applikation f(ε), bei mehreren Funktionsargumenten f(ε₁,ε₂,..)

Komposition f ∘ g ∘ h ∘ .. = f(g(h(..(x)))

Rekursion f(x) = λ.x → ε(f,x)

und Substitution a=ε

Zeitliches Modell: unbestimmt (t ↦ 0), Auswertereihenfolge nicht festgelegt

Abbildung 6-2. Beispiel für Funktionsdefinition und Applikation

Funktionale Komposition von Systemen

Parallelisierung durch Modellierung unterschiedlich detaillierter Datenflussdiagramme, die untereinander einen hierarchischen Zusammenhang aufweisen.

Abbildung 6-3. (Links) Datenflüsse von Ein- und Ausgabegeräten EA eines Systems (Rechts) Komposition des Systems durch Funktionen mit inneren Datenflüssen (teils parallelisierbar)

Sequenzielle Komposition

Eine imperative Berechnung setzt sich aus einer Sequenz I=(i₁ , i₂ , ..) von elementaren Anweisungen A={a₁,a₂,..} zusammen →
Sequenzielle Komposition i₁ ; i₂ ; ...

Die Anweisungen werden sequentiell in exakt der angegebenen Reihenfolge ausgeführt

Die Menge der Anweisungen A lässt sich in folgende Klassen unterteilen:

Arithmetische, relationale, und boolesche Ausdrücke (in Verbindung mit 2./3.) x+1, a*(b-c)*3, x<(a+b), ...

Datenanweisungen: Wertzuweisungen an Variablen x := a+b

Kontrollanweisungen wie bedingte Verzweigungen und Sprünge (Schleifen)

if a < b then x := 0 end
while x < 100 do  x:=x+1 end

Man fasst die Sequenz I als ein imperatives Programm X == Ausführungsvorschrift zusammen.

Die Ausführung des Programms (statisch) bezeichnet man als Prozess (dynamisch)

Ein Prozess befindet sich aktuell immer in einem Zustand σ einer endlichen Menge von Zuständen Σ={σ₁ , σ₂ , ..}.

Der gesamte Zustandsraum Σ des Prozesses setzt sich aus dem

Kontrollzustand s ∈ S={s₁, s₂, ..}, und dem

Datenzustand mit der Menge aller Speicherzustände (Daten) d ∈ D={d₁, d₂, ..} zusammen.

Der Fortschritt eines sequenziellen Programms bedeutet ein Änderung des Kontroll- und Datenzustandes → Zustandsübergänge

Die Zustandsübergänge können durch ein Zustandsübergangsdiagramm dargestellt werden.

Das Prozessmodell

Es werden zwei Prozesstypen unterschieden:

Sequenzieller Prozess

Ein einziger Programm- und Kontrollfluss mit strikter sequenzieller Ausführung von Anweisungen

Paralleler Prozess

Es gibt zwei oder mehr parallel ausgeführte Programm- und Kontrollflüsse (Ausführung kann zeitlich überlappend sein, muss aber nicht → Scheduling)

Sequenzieller Prozess

Ausführungszustände

Ein Prozess P besitzt einen "makroskopischen" Metaausführungszustand ps. Die Basismenge der Ausführungszustände PS ist ("Milestones"):

Start/Bereit aber noch nicht rechnend (START)

Rechnend (RUN)

Terminiert und nicht mehr rechnend (END)

Dazu kann es eine erweiterte Menge PS\*an Metaausführungszuständen geben:

Auf ein Ereignis wartend (AWAIT)

Blockiert (BLOCKED)

Rechenbereit aber nicht rechnend (nach Ereignis) (READY)

image-placeholder
(6-2)

Befindet sich der Prozess im Ausführungszustand RUN (also ausführend), dann werden strikt sequenziell die Instruktionen des Programms I={i₁,i₂,..,in} ausgeführt.

Dabei ist jede Instruktion eine Anweisung aus der endlichen Anweisungsmenge A={a₁,..} der Maschine (z.B. Bytecode Anweisung add(x,y)).

Ein Wechsel des Ausführungszustandes führt nicht zu einer Änderung der Instruktionsreihenfolge.

Sequenzieller Prozess: Zeitliches Modell

Ein Prozess führt die Anweisungen der Reihe nach aus. Das symbolische Semikolon teilt den Anweisungen eigene Ausführungsschritte (Zeitpunkte ti) zu.

image-placeholder
(6-3)

Die gesamte Ausführungszeit T(p) eines sequenziellen Prozesses p ist die Summe der Ausführungszeiten der Elementarprozesse

Sequenzieller Prozess

Prozessblockierung

Das Konzept der Prozessblockierung ist elementar für kommunizierende Prozesse

Kommunikation: Lesen und Schreiben von Daten, Ein- und Ausgabe, Netzwerknachrichten, usw.

Befindet sich ein Prozess im Ausführungszustand BLOCKED wartet dieser auf ein Ereignis:

Daten sind verfügbar

Zeitüberschreitung

Geteilte Ressource ist frei

Synchronisation mit anderen Prozessen

Bei einem blockierten Prozess schreitet der Kontrollfluss nicht weiter voran (keine Terminierung der aktuellen Operation)

Die Ausführung einer Operation (Instruktion) kann verzögert werden bis das zu erwartende Ereignis eintritt

Das Ausführungsmodell von Lua unterstützt die Blockierung des Programmflusses

Koroutinen

In Koroutinen (Fiber) z.B. mittels der yield Anweisung

Der Programmfluss wird über einen Scheduler an eine andere Koroutine übergeben

Schließlich wird die Programmausführung der ursprünglichen Koroutine nach der yield Anweisung wieder fortgesetzt (durch resume Anweisung)

Ebenso auch bei Ein- und Ausgabeoperationen (IO: read, write)

In Threads ebenfalls via yield und IO Operationen

Aber hier findet das Scheduling außerhalb der VM statt (multiple VM Instanzen)

Symmetrische Koroutinen

Das Scheduling der Koroutinen erfolgt semiautomtisch und es gibt nur die yield Operation (Reaktivierung von Koroutinen implizit durch Scheduler).

Asymmetrische Koroutinen

Die Suspendierung und Reaktivierung von Koroutinen erfolgt explizit (yield und resume Operationen).

Tatsächlich gibt es in Lua auf programmatischer Ebene aber nur einen einzigen Kontrollfluss und Pfad (eine VM Instanz)!

┌─────────┐            ┌─────────┐
│         │     resume │         │
│ 1       │      ┌────▶│ 4       │
│ 2       │      │     │ 5       │
│ 3 yield ├───┐  │ ┌───┤ 6 yield │
│ 7       │   │  │ │   │ 9       │
│ 8 read  ├─┐ │  │ │   │         │
│         │ │ │  │ │   │         │
└────┬────┘ │ │  │ │   └────┬────┘
     │      ▼ ▼  │ ▼        │
┌────┴───────────┴──────────┴───────────┐
│           LUA VM Instanz              │
└───────────────────────────────────────┘

Abbildung 6-4. Zwei Koroutinen im Wechsel; eine VM Instanz

co1 = coroutine.create(function ()
           for i=1,10 do
             print("co1", i)
             coroutine.yield()
           end
         end)
co2 = coroutine.create(function ()
           for i=1,10 do
             print("co2", i)
             coroutine.yield()
           end
         end)
coroutine.resume(co1)
coroutine.resume(co2)
...

/shelllvm

size

co1

co1 = coroutine.create(function ()
           for i=1,10 do
             print("co1", i)
             coroutine.yield()
           end
         end)
co2 = coroutine.create(function ()
           for i=1,10 do
             print("co2", i)
             coroutine.yield()
           end
         end)
coroutine.resume(co1)
coroutine.resume(co2)
print(coroutine.status(co1))

Parallele Prozesse

Ausgangspunkt sind sequenzielle Prozesse

Ein sequenzieller Prozess Ps besteht aus einer Sequenz von Anweisungen I=(i₁ ; i₂ ;..) (Berechnungen), die schrittweise und nacheinander ausgeführt werden: Ps=P(i₁ ; i₂ ; .. ; in) ⇒ p₁ ↦ p₂ ↦ .. ↦ pn

Parallele Komposition

Datenverarbeitungssystem als paralleler Prozess kann aus einer Vielzahl nebenläufig ausgeführter Prozesse P={P₁, P₂, P₃,...} bestehen

Parallele Komposition P=P₁ ∥ P₂ ∥ P₃ ∥ ..

Paralleler Prozess

Prozesskonstruktor

image-placeholder
(6-4)

Lua

Par({
  function (pid) .. end,
  function (pid) .. end,..
},{
  -- shared environment
  v = ε, ..
})

Ausführungsreihenfolge

Achtung! Wenn keine Kommunikation (Synchronisation) zwischen den Prozessen stattfindet ist die Ausführung und das Endergebnis (der Berechnung) gleich der sequenziellen Ausführung der Prozesse:

image-placeholder
(6-5)

Paralleler Prozess: Zeitliches Modell

image-placeholder
(6-6)

Prozessflussdiagramme

Der Prozessfluss in einem parallelen System kann durch Übergangs- und Terminierungsdiagramme dargestellt werden. (wie bereits im seq. Fall gezeigt wurde).

Eingehende Kanten (Pfeile) des Graphen beschreiben den Start eines Prozesses, ausgehende Kanten die Terminierung.

Abbildung 6-5. Beispiel eines Prozessflussdiagramms für vier Prozesse. *P*~1~ startet *P*~3~, und *P*~2~ spaltet *P*~4~ ab. (mit *P*~_,i~ = *Instruktion*(*P*,*i*))

Paralleler Prozess

Prozesserzeugung und Synchronisation

Ein neuer paralleler Prozess kann durch den entsprechenden Prozesskonstruktor erzeugt werden

Geschieht dies innerhalb eines Prozesses Pi so wird dessen Prozessausführung blockiert bis alle Teilprozesses des parallelen Prozessen terminiert sind!

Forking

Ein neuer Prozess Pj kann mittels Forking erzeugt werden (Aufspaltung des Kontrollflusses, so auch von einem anderen Prozess Pi) ohne dass ein ausführender Prozess auf die Terminierung des Parallelprozesses warten muss:

image-placeholder
(6-7)

Lua

Fork({
  function (pid) .. end,
  function (pid) .. end, ..
},{
  -- shared environment
})

Parallele Prozesse in Lua

/shelllvm

size

Par

require('Csp')
local function log(msg)
  print('[' .. luv.milli() ..'] '..msg)
end
local function busy ()
  for i = 1,100000000 do end
end
Par({
  function (pid) busy(); log('P1: pid='..pid) end,
  function (pid) busy(); log('P2: pid='..pid) end,
  function (pid) busy(); log('P3: pid='..pid) end,
  function (pid) log('P4: pid='..pid) end
})
log('After Par...')
luv.sleep(1)

Fork

require('Csp')
local function log(msg)
  print('[' .. luv.milli() ..'] '..msg)
end
local function busy ()
  for i = 1,100000000 do end
end
Fork({
  function (pid) busy(); log('P1: pid='..pid) end,
  function (pid) busy(); log('P2: pid='..pid) end,
  function (pid) busy(); log('P3: pid='..pid) end,
  function (pid) log('P4: pid='..pid) end
})
log('After Par...')
luv.sleep(1)

Zusammenfassung

Parallele Prozesse werden aus nebenläufig oder verwoben ausgeführten sequenziellen Prozessen gebildet

Prozesse besitzen drei wesentliche Ausführungszustände: Bereit, Rechnend, Terminiert

Prozessynchonisation kann durch Prozessflussgraphen (PFG) dargestellt werden

Ein nachfolgender Prozess (Knoten im PFG) wird erst gestartet wenn der vorherige terminiert

Prozessblockierung ist wesentliche Eigenschaft von synchronisierenden Prozessen

Parallelisierung von Algorithmen und Programmen

Wie können Algorithmen und Programmen parallelisiert werden?

Wann ist Kontrollpfadparallelität sinnvoll?

Was unterscheidet Datenpfad- von Kontrollpfadparallelität?

Unterschied zwischen Koroutinen, Threads, und Prozessen

Asynchrone vs. Synchrone Verarbeitung

Parallelisierungsmethoden

Sequenzielle Schleifen und Abrollung

Schleifen stellen eine reine Sequenz von elementaren Prozessen dar (parametrisierbare Replikate): I=i₁→i₂→ ...

Das Abrollen von Schleifen ist eine der gängigsten Parallelisierungsmethoden bei der Schleifen durch Replikation der Schleifeninstruktionen (Schleifenkörper) in eine sequenzielle und parallelisierbare Anweisungssequenz

teilweise (partitioniert)

oder vollständig transformiert werden.

Dabei wird der Schleifenkörper B(I,p) in Abhängigkeit von der Iterationsvariable p parametrisiert

Kontrollpfaparallelität durch Partitionierung: Jede Instanz oder eine Menege von B(pi) kann einem separaten Prozess Pi zugeordnet werden

 1: for i = i₁ to i₂ do
 2:   for j = j₁ to j₂ do
 3:     ..
 4:     IB(i,j,x(i,j),x(i+1,j),..,);
 5:   end
 6: end
 7: ──────────────────────────
 8: IB(i₁,j₁,x(i₁,j₁),x(i₁+1,j₁),..) ||
 9: IB(i₁+1,j₁,x(i₁+1,j₁),x(i₁+2,j₁),..) ||
10: IB(i₁+n,ij+m,x(i₁+n,ij+m),x(i₁+n+1,j₁+m),..) ||
11: ..

Definition 7-1. Schleifenparallelität und mögliche Parallelisierung (von Datenabhängigkeit verschiedener Instanzen *B*~i~ begrenzt)

Zu beachten sind Datenabhängigkeiten zwischen einzelnen Anweisungsiterationen und Kosten durch die Abrollung (Overhead)

Beispiel: Abrollbar aber nicht parallelisierbar durch Datenabhängikeit ISb(ISb-1(ISb-2(..)) !

1: X := 1;
2: for i = a to b do
3:   IS: X := X*i;
4: end

Deklarative Beschreibung von Vektoroperationen

In der Bildverarbeitung werden Vektoroperationen (und Matrixoperationen) sehr häufig verwendet. Dabei werden häufig die gleichen Operationen auf alle Pixel eines Bildes (Feldelemente) angewendet → Datenpfadparallelität.

Anstelle der iterativen Berechnung mittels Schleifen definiert man deklarativ die Berechnung eines Pixels (Punktoperator) oder eines Bereiches des Bildes (Lokaloperator):

1: img' = F(img):: = { f(x)|x ∈ img }
2: ──────────────────────────
3: procedure F (img: vector of type):
4: begin
5:   return f(img)
6: end

Definition 7-2. Deklarative Beschreibung von Vektoroperationen

Beispiel Punktoperator

Abbildung 7-1. Algorithmus: Transformation von Farb- in

Listen mit Map&Reduce

Funktionale Komposition bietet inherente Parallelität bei Listenoperationen ("Punktoperatoren")

Häufige Listenoperationen (und auch bei Arrays) sind:

map transformiert eine Liste in eine neue Liste gleicher Länge über eine Transformationsfunktion (Punktoperator) f(x): x → y

reduce reduziert eine Liste mittels eines Akkumulators entweder auf ein Element oder eine neue Liste mit kürzerer Länge über eine Reduktionsfunktion f(accu,x): accu,x → accu

Mapping kann vollständig parallel ausgeführt werden (Unabhängigkeit der Teiloperationen)

Reduce kann als Baumstruktur teil-parallel ausgeführt werden (dynamische Partitionierung)

Parallelisierung bei Map/Reduce

{1,2,3,4,5,6,8,9,..}:map(f):reduce(g)
 │ │ │ │ │ │ │ │    ┌─▶{*,*,*,*,*,*,*,*,..}
 │ │ │ │ │ │ │ │    │   │ │ │ │ │ │ │ │
 f f f f f f f f    │  g└┬┘ └┬┘ └┬┘ └┬┘g
 | | | | | | | |    │    │   │   │   │
{*,*,*,*,*,*,*,*,..}*   g└─┬─┘  g└─┬─┘
                           │       │
                          g└───┬───┘
                               │

Definition 7-3. Parallele Anwendung der Elementfunktionen *f* und *g* → funktionale Datenpfadparallelität

Real wird die Datenpfadparallelität durch partitionierte Kontrollpfadparallelität abgebildet!

Parallelisierungsmethoden

JavaScript und Lua

JavaScript (und andere funktionalen Programmiersprachen) arbeiten intensiv mit Listen und Arrays

Listen und Arrays lassen sich mittels eines Abbildungsoperators und einer Elementfunktion (Punktoperator) transformieren (map-and-reduce)

local img = T{21,2,6,28,2,3,4,6,9,100,20};
function gray2color (img)
  return {r=img,g=img,b=img }
end
local img2 = img:map(gray2color);
local meanlevel = img2:map(function (p)
  return (p.r+p.g+p.b)/3
end):reduce(function (accu,level)
  return accu+level
end)

Beispiel 7-1. Bildtransformation mit map&reduce Operation

/shelllua

size

Point

local img = T{21,2,6,28,2,3,4,6,9,100,20};
function gray2color (img)
  return {r=img,g=img,b=img }
end
local img2 = img:map(gray2color);
local meanlevel = img2:map(function (p)
  return (p.r+p.g+p.b)/3
end):reduce(function (accu,level)
  return accu+level
end)
print(meanlevel)

Lokaloperatoren

Lokale Operatoren (Zelluläre Automaten!) sind rechenintensiver als Punktoperatoren. Um ein neues Pixel zu berechnen wird der alte Wert des Pixels sowie die alten räumlich benachbarten Werte der Pixel innerhalb einer definierten maximalen Entfernung verwendet.

Für eine 3x3-Nachbarschaftsberechnung werden zum Beispiel Neun Datenwerte für jedes Pixel benötigt.

Für die Berechnung lokaler Operatoren wird eine bestimmte Anzahl von parallelen Datenaustauschvorgängen benötigt → Kommunikation.

Wenn jedes Pixel auf einem anderen Prozessor gespeichert wird ist Kommunikation teuer!

Beispiel Lokaloperator

Abbildung 7-2. Komplexitätsreduktion durch Separation der Operatoren: (1) Alle Zeilenoperationen werden parallel ausgeführt (2) Alle Spaltenoperationen werden parallel ausgeführt

Abbildung 7-3. Algorithmus: Parallele Nachbarschaftsberechnung

Basisblock Optimierer und Scheduler

Nebenläuﬁgkeits- und Datenabhängigkeitsanalyse

Ziele: Reduktion von Zeitschritten, Minimierung der Latenz, Parallelisierung

Basisblöcke sind Bereiche im Programmﬂussgraphen, die nur einen Kontrollzugang am Kopf und nur einen Kontrollausgang am Ende haben, und keine weiteren Seiteneingänge.

Ein Basisblock der nur aus Datenanweisungen besteht ist ein Major-Block. Dieser wird in elementare Minor-Blöcke zerlegt, die wenigstens eine Anweisung enthalten (bei einem gebunden Block der ganze Block)

Es werden Datenabhängigkeitsgraphen für jeden Major-Block erstellt.

Nicht abhängige Anweisungen werden durch einen Scheduler mit ASAP-Verhalten in einen gebundenen Block (paralleler Prozess) zusammengefasst.

x=0 ──────────────▶ MinBl 1.1 ┌───▶ MajBl 1:
y=0 ──────────────▶ MinBl 1.2 │     P(1.1)||P(1.2)
if x < y then
  t=x  ───────────▶ MinBl 2.1 ┌───▶ MajBl 2:
  x=y  ───────────▶ MinBl 2.2 │     P(2.1);P(2.2)||P(2.3)
  y=t  ───────────▶ MinBl 2.3 │
end

Beispiel 7-2. Basisblöcke und parallele Prozesskomposition

Funktionale Programmierung

Determinismus macht paralleles Auswerten der Argumente und Parallelisierung bei Rekursion möglich

Parameter von Funktionen sind datenunabhängig → Parallele Evaluierung der Funktionsargumente bei der Funktionsapplikation

Funktionsaufrufe sind gänzlich oder partiell datenunabhängig → Parallelisierung der Funktionsaufrufe (Endrekursion, Kopfrekursion bringt kein Vorteil)

Probleme:

Argumente haben teils kein ausreichendes Potential (Ausdrücke zu einfach und zu flach)

Große Rekursionstiefen können zu einer zu feinen Aufteilung führen → nicht gut auf Prozessoren aufzuteilen

Lua - Ausführungsmodelle

Systemprozesse

Isolierte Programmprozesse ohne direkte Synchronisation und Datenaustausch zwischen den VMs

Synchronsiation nur über

Dateien

Sockets (lokal, TCP, UDP)

Pipes (Streams)

Jeder Prozess führt eine VM aus ohne (zunächst) direkte Kopplung und Kommunikation mit anderen Prozessen

Kommunikation über lokale Unix/Windows oder UDP/TCP Sockets, benannten Semaphoren (über Dateisystem), und geteilten Speicher

Kontrollpfadparallelität

Threads

Es werden parallele Prozesse auf Threads abgebildet die bestenfalls 1:1 auf den CPUs / Cores ausgeführt werden, ansonsten durch einen Scheduler im Zeitmultiplexverfahren ausgeführt werden → Kontrollpfadparallelität

Prozesse können synchronisiert auf geteilte Objekte (konkurrierend) zugreifen:

Channel

Semaphore, Mutex

Event, Timer

Shared Memory Store

Prozessblockierung blockiert den gesamten Thread (somit auch alle Fibers)

Jeder parallele Prozess in einem Thread läuft in eigener VM Instanz

Daten können nicht zwischen VMs ausgetauscht werden (Automatsisches Speichermanagement und GC) → nur Austausch über Serialisierung und Kopie von Daten oder geteilte Byte Datenspeicher (Shared Buffer)!

Fibers und Koroutinen

Es werden konkurrierende (aber nicht notwendig nebenläufige) Prozesse (Koroutinen) auf Fibers abgebildet die grundsätzlich in Lua nur sequenziell durch einen Scheduler im Zeitmultiplexverfahren ausgeführt werden.

Diese Prozesse können synchronisiert auf geteilte Objekte (nicht nebeläufig) zugreifen:

Channel

Semaphore

Event, Barriere, Timer

Prozessblockierung blockiert nur eine Koroutine

Alle quasi-parallelen Prozesse mit Fibers laufen in einer VM Instanz und teilen sich den VM Datenkontext sowie besitzen den gleichen Programmkontext (direkte Teilung von Variablen und Funktionen)

Abbildung 7-4. Threadmodell und Kommunikation der Prozesse mit geteilten Objekten

IO Paralellisierung

Neben Threads, Fibers, und Prozessen kann auch die Parallelisierung von Ein- und Ausgabeoperation genutzt werden → Kontrollpfadparallelität

Asynchrone IO wird sowohl in nodejs (JavaScript) als auch in Lua (lvm) mittels der libuv Bibliothek implementiert

Verwendung von Callback Funktionen für die Daten- und Ereignisverarbeitung

Anders als in JavaScript (nodejs) wird asynchrone IO in Lua eher seltener verwendet

Fibers (Koroutinen) werden in Lua direkt durch die Lua VM verarbeitet

Threads werden über die libuv einzelnen VM Instanzen zugeordnet

Verbindung der Instanzen über libuv

Jede VM Instanz hat ihre eigene Event Loop!

Abbildung 7-5. Asynchrone IO mit der *libuv* Architektur [docs.libuv.org/en/v1.x/design.html]

LVM

Die Parallel LuaJit Virtual Machine (P)LVM erlaubt die parallele Programmierung auf allen drei Ebenen (Koroutinen, Threads, Prozesse)

Abbildung 7-6. Parallelisierung durch multiple VM Instanzen mit Inter-VM Kommunikation

Asynchrone Ereignisverarbeitung

Neben der Parallelisierung der reinen Datenverarbeitung (Berechnung) kann auch eine Partitionierung von Ein- und Ausgabe bzw. der Ereignisverarbeitung erfolgen

Bekanntes Beispiel: Geräteinterrupts mit einfachen Foreground-Background System mit zwei Prozessen:

P1: Hohe Priorität (Ereignisverarbeitung → Interrupthandler → Foreground Prozess)

P2: Niedrige Priorität (Berechnung → Hauptprogramm → Background Prozess) mit Preemption durch Ereignisverarbeitung

Ein- und Ausgabeoperationen eines Programms können synchron (blockierend) oder asynchron (im Hintergrund verarbeitet und nicht blockierend) ausgeführt werden.

Alle Programme/Prozesse können blockieren, aber nur wenige Programmierumgebungen erlauben ein Scheduling (Multiprozessverarbeitung)

Beispiel Lua

Synchrone Operationen liefern das Ergebnis in einer Datenanweisung zurück die den Programmfluss solange blockiert bis das Ereignis eintritt (Ergebnisdaten verfügbar sind).

Dabei werden zwei aufeinander folgende Operationen sequenziell ausgeführt, und eine folgende Berechnung (nicht ereignisabhängig) erst nach den Ereignissen ausgeführt:

x = IO1(arg1,arg2,..);
y = IO2(arg1,arg2,..);
z = f(x,y);

Bei der asynchronen (nebenläufigen) Ausführung von ereignisabhängigen Operationen wird das Ergebnis über eine Callback Funktion verarbeitet. Die IO Operation blockiert nicht. Vorteil: Folgende Berechnungen können unmittelbar ausgeführt werden.

IO1(arg1,arg2,..,function (res) x=res; end);
IO2(arg1,arg2,..,function (res) y=res; end);
z = f(x,y); -- Problem?

Prozessmodell ohne Synchronisation (so wie in Lua/JS):

image-placeholder
(7-1)

Mit Synchronisation:

image-placeholder
(7-2)

Abbildung 7-7. Ereignisbasierte Verarbeitung von asynchronen Operationen in *lvm*: Ein Lua Thread verbunden über die Eventloop mit *N* IO Threads

Synchronisation

Asynchrone Ereignisverarbeitung mit preemptiven (unterbechenden) Verhalten benötigt explizite Synchronisation (Locks...) zur Atomarisierung von kritischen Bereichen

Asynchrone Ereignisverarbeitung spaltet den Kontroll- und Datenfluss auf und benötigt Daten- und Ergebnissynchronisation über Prädikatfunktionen oder explizite Synchronisation:

local x,y,z;
function P(f,x,y,z)
  if x~=nil and y~=nil then
    return f(x,y)
  else return z end
end
IO1(arg1,arg2,..,function (res) x=res; z=P(f,x,y,z) end);
IO2(arg1,arg2,..,function (res) y=res; z=P(f,x,y,z) end);

Definition 7-4. Verwendung einer Prädikatfunktion *P* zur Auflösung von Abhängigkeiten und Asynchronität / Unbekannter Ausführungsreihenfolge

Synchronisierung von Callbacks

Neben der Prädikatfunktion kann Deasynchronisierung verwendet werden um den Programmfluss zu sequenzialisieren und zu synchronisieren

Dazu wird eine zusätzliche Synchronisation eingeführt die die auszuführende asynchrone Funktion blockiert

Der Kontrollfluss spaltet sich dabei auf (der Hauptfluss wird verlassen)

Die Callback Funktion ist der Nebenfluss der schließlich die Blockierung des Hauptflusses wieder aufhebt

In Lua gibt es asynchrones Schedulung (yield,resume) dafür

JavaScript kann dieses nur durch Modifikation der VM erreichen

Deasynchronisierung in Lua

function fooAsync (callback)
  .. callback(result) ..
end
-- Nur in Koroutine ausführbar!
function fooSync ()
  local result
  fooAsync(function (_result)
    result=_result
    coroutine.resume()
  end)
  coroutine.yield()
  return result
end

Definition 7-5. Deasync Wrapper für asynchrone Funktionen

Koroutinen in JavaScript

In JavaScript ist zunächst kein Scheduling des Kontrollflusses möglich

Es kann nur der gesamte Programmfluss blockieren

Ansonsten müssen asynchrone Funktionen verwendet werden

Aber: Auch hier führt die VM entweder den Hauptfluss oder Callbacks (Nebenfluss über die Event Loop) aus

function fooAsync(data) {
  ... compute A1 ...
}
...compute M1 ...
setInterval(fooAsync,1000)
...compute M2...

Beispiel 7-3. Beispiel einer asynchronen Ausführung einer Berechnung durch einen Timer. Solange in M1/M2 berechnet wird findet keine Ausführung von fooAsync statt (wird verzögert)

Promises und Async/Await

Promises wurden in EcmaScript ES2015 eingeführt um die Verschachtelung von callbacks zu linearisieren ("Callback Hölle")

Ein Promise ist eine Funktion die die Ausführung einer Sequenz von Operationen sequenzialisiert (sequenzielle Blockierung) → Ansatz von Scheduling

Aber: Ein Promise blockiert nicht den Hauptfluss!

Mit await kann auf eine explizit gekennzeichnte async Funktion aber auf deren Terminierung eines Promise gewartet werden

[developer.mozilla.org]

var myPromise = new Promise(function (resolve, reject) {
  setTimeout(function () {
    if (Math.random()<0.5) resolve('granted');
    else reject('denied');
  }, 300);
});
myPromise
  .then(handleResolvedA, handleRejectedA)
  .then(handleResolvedB, handleRejectedB)
  .then(handleResolvedC, handleRejectedC);

Koroutinen (mit Scheduling) lassen sich in JavaScript nun mittels neuer async Funktionen (Definition) und warten auf Terminierung mittels await (Applikation) implementieren

Aber: Asynchrone Funktionen und await Blockierungen dürfen hier nicht geschachtelt werden (anders als in Lua mit yield/resume!!)

var waiters=[];
function yield() {
  var getResolver = function (resolve) {
    waiters.push({resolve:resolve,event:'yield'});
  }
  return new Promise(getResolver);
}
async function coro() {
  for(;;) { ..; await yield(); .. }
}
function schedule() {
  var next = waiters.shift();
  if (next) {
    next.resolve();
  }
}
coro() .. schedule() ..

Koroutinen mit Kontrollflussverzweigung in JavaScript

/shelljs

size

coro1

var waiters=[];
function yield() {
  var getResolver = function (resolve) {
    waiters.push({resolve:resolve,event:'yield'});
  }
  return new Promise(getResolver);
}
async function coro(id) {
  for(var i=0;i<5;i++) { print(id+':'+i); await yield();  }
}
function schedule() {
  var next = waiters.shift();
  print('schedule '+(next?1:0));
  if (next) {
    setTimeout(schedule,1);
    next.resolve();
  }
}
coro('A')
coro('B')
setTimeout(schedule,1);

Zusammenfassung

Funktionale Ausdrücke und Vektoroperationen bieten Möglichkeiten der Parallelisierung auf Datenpfadebene

Sequenzielle Schleifen und Rekursion bieten Möglichkeiten der Parallelisierung auf Kontrollpfadebene

Basisblockparititionierung erlaubt Parallelisierung auf Daten- und Kontrollpfadebene

Asynchrone (quasi nebenläufige) Ausführung von Funktionen bietet Parallelisierung auf Kontrollpfadebene

Verteilte Programmierung (Web)

Wie können Web Browser für die verteilte Datenverarbeitung genutzt werden?

Zentrales Thema Kommunikation: Wie können WEB Browser (und WEB Seiten) vernetzt werden?

Prozesskommunikation mit Channels über WEB Sockets und WEB Real-time Communication

Gruppenkommunikation

Verteilte Systeme

Parallele Systeme sind eng gekoppelt. Kommunikation zwischen Prozessen nutzt:

Physisch geteilten Speicher (Unsynchronisierter Datenauschtausch);

Semaphoren (Synchronisation, Kooperation, Schutz), häugfig durch Betriebssystem implementiert;

Datenkanäle (Channels, Synchronisierter Datenaustausch).

Verteilte Systeme sind lose gekoppelt und können für die Synchronisation nicht auf das Betriebssystem und die technischen Eigenschaften des Hostrechners zurückgreifen!

Aber Channels können auch zwischen getrennten Rechner mit Nachrichtenkommunikation implementiert werden!

Channels können dann genutzt werden um andere Synchronisationsobjekte (z.B. Semopahore) zu implementieren

Parallele Systeme sind i.A. synchrone Prozesssysteme

Verteilte Systeme sind inhärent asynchron und können nicht grundsätzlich und zuverlässig synchronisiert werden!

Kommunikation mit Nachrichten erfordert ein Kommunikationsprotokoll (siehe ISO Netzwerkschichten)

HTTP/HTTPS (Hyper Text Transfer Protocol + Secure, temporär verbindungsorientiert) →

TCP (Transmission Control Protocol, verbindungsorientiert, zuverlässig) |

UDP (User Datagram Protocol, verbindungslos, nicht zuverläassig)

Web Sockets (aufbauend auf HTTP/HTTPS/TCP)

Parallele Systeme arbeiten häufig nach dem Prinzip der Produzenten-Konsumenten Interaktion und Partitionierung

Es gibt häufig einen ausgewiesenen Master und eine Vielzahl von Worker Prozessen

In verteilten Systemen gibt es häufig ein Leader Prozess (der selbst aber auch Worker sein kann)

Leader und Worker bilden eine (temporäre) Gruppe

Der Leader kann vorher ein fest stehen oder von der Gruppe gewählt werden → Leader Election Algorithmen

Der Leader vermittelt Worker und Kommunikation

Kommunikation kann zwischen Worker und Leader und zwischen Workern stattfinden

Gruppenkommunikation (Broad- und Multicast)

  ┌────────┐          ┌────────┐
  │ P1     │          │ P2     │
  │ Worker │ ◀──────▶ │ Worker │
  └────────┘          └────────┘
     ▲  ▲                  ▲
     │  │   ┌───────┐      │
     │  └─▶ │ P5    │ ◀────┘
     │  ┌─▶ │ Master│ ◀────┐
     │  │   └───────┘      │
     ▼  ▼                  ▼
  ┌────────┐          ┌────────┐
  │ P3     │          │ P4     │
  │ Worker │ ◀──────▶ │ Worker │
  └────────┘          └────────┘

Abbildung 8-1. Verteiltes Prozesssystem mit Leader(Master) und Workern und Kommunikationskanälen

Sockets

Ein Socket ist sowohl ein Kommunikationsendpunkt (zum Empfang von Nachrichten) als auch ein Sender von Nachrichten

Sockets (die i.A. zu Prozessen gehören) können miteinander verbunden werden (verbindungsorientierte Kommunikation mit Sessions) oder verbindungslos Datenpakete sich gegenseitig zusenden

Ein Socket wird durch eine lokale oder netzwerkweite Identifikation (Pfad, Nummer, Nummer und Netzwerkadresse des Gerätes, Namen usw.) erreicht

 <ip:port>                       <ip:port>
┌────────┐        data msg       ┌────────┐
│ Socket ├──────────────────────▶│ Socket │
└────────┘        send(data)     └────────┘

Beispiel: TCP Socket in Lua/LVM

Server

local server = luv.net.tcp()
server:bind(host, port)
 function on_conncetion(chanClient)
  -- handle client request
  client:write(data)
end
server:listen(128, function(err)
  -- Accept the client
  local chanClient = luv.net.tcp()
  server:accept(chanClient)
  on_connection(chanClient)
end)

Klient

local chanClient = luv.net.tcp()
chanClient:connect(host, port,
  function (err)
    -- check error and carry on.
    chanClient:write(data)
    data=chanClient:read()
end)

Beispiel 8-1. Lua Socket mit bidirektionaler TCP Kanalverbindung

Web Sockets

HTTP bietet sogenannte "pull" Anfragen (GET/POST), auf die es eine Antwort gibt (response).

WEB Sockets bieten eine Zweiweg (bidirektionale) Kommunikation zwischen ursprünglich einem Server und einem Klienten (d.h. auch die andere Seite kann direkt Daten senden)

WEB Sockets werden über das HTTP(S) Protokoll verhandelt und eine Socket Verbindung aufgebaut

Auch für die bidirektionale Kommunikation zwischen Web Browsern geeignet

Web Sockets nutzen (zwei) TCP Verbindungen um Datenströme zu übertragen. Die Übertragung ist als zuverläassig anzusehen (anders als bei UDP)

Abbildung 8-2. Aufbau eines Web Sockets über eine HTTP(S) Verbindung [www.pubnub.com]

Channels

Ein Kommunikationskanal zwischen zwei Prozessen kann

unidirektional (ein Sender, ein Empfänger);

einseitig bidirektional (ein Sender und Empfänger einer Rückantwort, request-reply);

beidseitig bidirektional sein (zwei getrennte Sender und Empfänger).

Ein Kommunikationskanal basiert auf einer FIFO Warteschlange (Queue)

Es gibt zwei wesentliche Operation auf Kanälen:

read → data

Liest ein Datenelement aus der Warteschlange; wenn die Queue leer ist blockiert die Operation

write(data)

Schreibt ein Datenelement in die Warteschlange; wenn die Qeuee "voll" ist blockiert die Operation

     ┌───────┐                 ┌───────┐
     │       │    send(d)      │       │
     │       ├────────────────▶│       │
     │ Port  │    send(d)      │ Port  │
     │       │◀────────────────┤       │
     ├───────┤                 ├───────┤
     │ Queue │                 │ Queue │
     └────┬──┘                 └─┬─────┘
       ▲  │                      │  ▲
       │  │                      │  │
 write(d) ▼ read()        read() ▼  write(d)
 ─────────────────        ──────────────────
    process P1                process P2

Abbildung 8-3. Kanalkommunikation zwischen zwei (entfernten) Prozessen

Netzwerkkommunikation

Netzwerkkommunikation findet i.A. zwischen Prozessen und nicht Geräten statt

Dazu werden Kommunikationsports auf einem Gerät verwendet (Sockets)

Ein Kommunikationsport wird in IP (Internet Protocol) Netzen durch das Tupel ⟨ipaddr,ipport⟩ referenziert

Ein Gerät (Hostrechner) hat mindestens eine wenigstens lokal eindeutige IP(4) Adresse ip, im Format "XX:XX:XX:XX" (X: hexadezimal Ziffer), oder "DDD:DDD:DDD:DDD".

Öffentliche und Private Netzwerke

Ein Kommunikationsport muss mit seiner Adresse ⟨ipaddr,ipport⟩ öffentlich im Internet sichtbar sein (man spricht von einem Server)

Aber: Schon allein aufgrund der hohen Anzahl von Geräten reicht der IP4 Adressraum nicht mehr aus, und jeder öffentlich erreichbare Rechner ist ein Angriffspunkt

Es werden private/virtuelle Netzwerke aufgespannt mit zwei Adressräumen:

Öffentlich → Das ganze virtuelle Netzwerk hat eine eintige IP4 Adresse!

Virtuell → Jedes Gerät hat innerhalb des Subnetzwerkes eine eindeutige nicht öffentlich sichtbare Geräteadresse

Problem: Kommunikation nach außen erfordert Network Address Translation (NAT)

Abbildung 8-4. Öffentliche und private Netzwerke mit unterschiedlichen Adressräumen und Adressumrechnung (NAT) [bford.info/pub/net/p2pnat]

Network Address Translation

Immer wenn eine Kommunikation zwischen zwei Kommunikationsports zweier Prozesse auf zwei Geräten in unterschiedlichen Netzwerken stattfinden soll muss an der Grenze Öffentliches Internet ↔ Virtuelles Netzwerk die private Adresse ⟨ipaddr,ipport⟩ in eine öffentliche ⟨V2P(ipaddr),V2P(ipport)⟩ umgerechnet werden

Man unterscheidet:

Symmetrisches NAT: IP Addresse ipaddr und auch die Portnummer (ipport) werden transformiert

Asymmetrisches NAT: Nur die IP Addresse ipaddr wird umgerechnet, die Portnummer bleibt unverändert.

Auch durch NAT werden aber Ports in virtuellen Netzwerken öffentlich nicht sichtbar.

Hier fangen jetzt die Probleme für Kanalkommunikation via UDP/TCP an!!!

Abbildung 8-5. Kanalkommunikation zwischen zwei (entfernten) Prozessen [bford.info/pub/net/p2pnat]

NAT und UDP Hole Punching

https://bford.info/pub/net/p2pnat/

Das Problem: Das öffentlich sichtbare Tupel ⟨ipaddr,ipport⟩ eines Peer Ports muss auch für eingehende Datenströme verwendet werden.

Wenn ein Klient Daten über einen Port mit NAT sendet merkt sich der NAT das Mapping und eine Rücksendung an den Sendeport wird an das richtige Gerät und den Prozess vermittelt.

Aber wie soll Klient A mit Klient B Kontakt aufnehmen wenn zuvor Klient B keinen Kontakt mit A aufgenommen hat? Es muss versucht werden den NAT von B "durchzuschalten"

Dazu werden (leere Ping) UDP Pakete zwischen den Klienten gegenseitig zugesendet.

STUN, TURN

https://help.estos.com/help/de-DE/procall/7/erestunservice/dokumentation/htm/IDD_FUNCTIONALITY.htm

[help.estos.com]

Signaling Server

Signaling Server dienen zum indirekten Austausch von Daten zwischen zwei Klienten. Dies kann ein Dienst sein, der von beiden Klienten erreichbar ist oder auch mehrere Dienste die mittels Zusammenschluss miteinander verbunden sind

Abbildung 8-6. Klient A ist direkt erreichbar. Klient B kann Daten direkt an Klient A senden

Abbildung 8-7. Erfolgloser Verbindungsaufbau über einen NAT-Router hinweg.

STUN - Session Traversal Utilities for NAT (RFC5389)

Dieses Protokoll ermöglicht es einem Klienten in einem lokalen Netzwerk (LAN), seine eigene, öffentliche IPv4-Adresse zu ermitteln. Der rufende Client im LAN kann auf diese Weise dem angerufenen Klienten ausserhalb des LAN mitteilen, welche IPv4-Adresse (und Portnummer) verwendet werden kann um eine direkte Kommunikation mit ihm zu ermöglichen ("Peer-to-Peer" Verbindung).

Abbildung 8-8. Erfolgreiche Kommunikation unter Zuhilfenahme eines STUN-Servers.

TURN - Traversal Using Relays around NAT (RFC5766)

Ein Server im Internet, der das TURN-Protokoll implementiert, ermöglicht es zwei Klienten, Daten ohne eine direkte Verbindung auszutauschen ("Relais Server"). Dies wird notwendig, wenn es keine Möglichkeit gibt, eine direkte Klient-zu-Klient-Verbindung aufzubauen.

Abbildung 8-9. Erfolgloser Kommunikationsversuch über ein "Symmetric NAT".

Abbildung 8-10. Erfolgreicher Kommunikationsversuch über ein "Symmetric NAT" durch Nutzung eines TURN-Servers.

ICE - Interactive Connectivity Establishment (RFC5245)

Zwei Klienten können die mit Hilfe von STUN und TURN ermittelten Verbindungsinformationen (und andere Daten) mit Hilfe des ICE Protokolls austauschen. Die Übermittlung der Informationen muß dabei über einen eigenen Dienst erfolgen, einen sog. "Signaling Server". Dieser Dienst muß von beiden Klienten erreichbar sein.

Symmterisches NAT

Kaum für direkte Peer-to-Peer Verbindungen einzusetzen (wenn beide Prozesse hinter NATs sitzen)

Typisch für mobile Netzwerkverbindungen (4G/LT/UMTS)

Die lokalen und öffentlichen Portnummern unterscheiden sich

Häufig ein Paar für jede ausgehende und eingehende Datenübertragung (bei gleichen lokaler Portnummer!)

Einige UDP Hole Punching Algorithmen versuchen das Transformationsschema zu untersuchen. Randomisierte Zuordnungen sind kaum durchdringbar, inkrementelle mittels Probing eventuell!

Abbildung 8-11. Hier ist das Problem bei einem sym. NAT gezeigt: Der Klient fragt zwei STUN Server nach seinem öffenteln Port Tupel und bekommt zwie verschiedene Antworten. Und von außen kann über dieses Mapping auch keine Nachricht an den Port gesendet werden! [webrtchacks.com]

PeerJS

https://github.com/peers/peerjs

PeerJS besteht aus einer Klienten API und einem Server, dem Signaling Server

PeerJS kapselt WEB Sockets mit WEB RTC (Realtime Comm.)

Ein Peer Port in PeerJS ist mit einer (eindeutigen) ID Nummer verknüpft, z.B. a53d9c76-4119-4d82-be5c-88fc11ffc943

Ein Peer Port ist (unter Verwendung von STUN und TURN Servern) im ganzen Internet erreichbar

Beliebig viele Verbindungen von anderen Klienten können aufgebaut werdem

Damit die ID eindeutig ist wird ein PeerJS Server für die Anfrage und Verwaltung verwendet.

Jedoch kann auch eine feste ID verwendet werden, so z.B..

Abbildung 8-12. Alle Server zusammen: STUN+TURN+PeerJS [toptal.com]

WEB Browser-Browser Cluster

  ┌───────────────┐         ┌───────────────┐        ┌───────────────┐
  │ Browser       │         │ Browser       │        │ Browser       │
  ├───────────────┤         ├───────────────┤        ├───────────────┤
  │ Message       │         │ Message       │        │ Group         │
  │ Server, Chat  │         │ Server, Chat  │        │ Server        │
  ├───────────────┤         ├───────────────┤        ├───────────────┤
  │ Lua VM, Coro  │         │ LuaVM, Core   │◀──────▶│ Channel       │
  ├───────────────┤    ▲    ├───────────────┤        ├───────────────┤
  │ LuaJS Bridge  │    │    │ LuaJS Bridge  │        │ PeerJS        │
  ├───────────────┤    │    ├───────────────┤        ├───────────────┤
  │ Channel,Group │◀───┼───▶│ Channel,Group │        │ WEB Sockets   │
  ├───────────────┤    │    ├───────────────┤        └───────────────┘
  │ PeerJS        │    │    │ PeerJS        │
  ├───────────────┤    ▼    ├───────────────┤
  │ WEB Sockets   │         │ WEB Sockets   │
  └───────────────┘         └───────────────┘

Abbildung 8-13. Browser Cluster mit Gruppenserver (Master und Koordinator)

Lua Web Gruppenkommunikation

Es wird folgend aufgebauter Kommunikationsstack im WEB Browser verwendet:

Group (Lua/JS)

Channel (Lua/JS)

Socket (JS)

PeerJS (JS)

WEB Sockets (JS, Browser API)

HTTP/HTTPS

Es werden folgende Server verwendet:

PeerJS (Signaling Server)

STUN (IP Adressen und Port Resolver)

TURN (IP Realais bei symmetrischen NATs)

Es wird die fengari Lua VM für Programmausführung verwendet

Lua Group API

iceServers = [
    { url: 'stun:stun.l.google.com:19302' },
    { url: 'turn:numb.viagenie.ca',
      credential: 'muazkh', username: 'webrtc@live.com'
    }
]
group = Group (mygroup)   -- Gruppe erzeugen bzw. bekanntgeben
status = group:join()     -- Der Gruppe beitreten
status = group:unjoin()   -- Die Gruppe verlassen
members = group:members() -- Liefert alle momentanen Gruppen
                          -- Mitglieder
chan = group:connect(member) -- Kanal zu member ∈ members aufbauen
chan:write(data)          -- In den Kanal schreiben
data=chan:read(timeoutInMs?) -- Aus dem Kanale lesen

Definition 8-1. Lua WEB Socket Gruppenkommunikation

Alle Operationen sind synchron und blockierend bis entweder die Operation erfolgreich ausgeführt wurde oder abgebrochen wurde (Rückgabe i.A. nil).

Zusammenfassung

Synchronisiert Kommunikationskanäle (Channels) stellen wichtigistes Interprozesskommunikation in parallelen und verteilten Systemen dar

Channels in lokalen parallelen Systemen sind "einfach" zu implementieren

Channels über nachrichtenbasierte Netzwerkverbindungen können einen hohen Aufwand und Kosten verursachen

Vebrindung von Netzwerkprozessen in unterschiedlichen privaten/virtuellen Netzwerken erfordern Hilfsserver (Signaling, STUN, TURN)

Synchronisation und Prozesskommunikation

Wie können parallele und nebenläufige Prozesse synchronisiert werden?

Wie wird Datenkonsistenz in parallelen Programmen gewährleistet?

Synchronisationsobjekte: Mutex, Semaphore, Event, Barrier, Timer, Channel, Monitor

Gruppenkommunikation

Prozesskommunikation

Start und Terminierung von Prozessen kann durch die Prozesse selbst, den Prozesskonstruktoren oder explizit durch Synchronisationsobjekte erfolgen

Aber auch zwischen Start und Terminierung eines Prozesses ist es häufig erforderlich den inneren Prozessfluss von einer Gruppe von Prozessen zu synchronisieren, d.h. an bestimmten Punkten (Milestones) den Kontrollfluss abgleichen.

Synchronisationsklassen

Bei geteilten Resourcen und konkurrierenden Zugriff

Gegenseitiger Ausshluß und Schutz von kritischen Programmbereichen (Lock)

Kooperation

Verteilung und Zusammenführung von Prozessen und Daten

Koordination

Reihenfolge, Abläufe, Aufgabenverteilung

Invarianten

Synchronisationsobjekte müssen bestimmte Bedingungen erfüllen, damit Konsistenz, Sicherheit und Lebendigkeit in parellelen Prozessystemen jederzeit gewährleistet sind!

Eine Invariante ist häufig eine Boolescher oder relationer Ausdruck der sowohl Parameter des Objekts als auch die Prozessinteraktion berücksichtigt

Lock und atomare Operationen

Mutualer Ausschluss mit Lock Objekt

Ein LOCK Objekt ist ein geteiltes Objekt dass sich in zwei verschiedenen Zuständen σLock={FREE,LOCKED} befinden kann und eine Ressource schützt:

State FREE

Die Ressource ist nicht in Verwendung

State LOCKED

Die Ressource wird bereits von einem Prozess verwendet, andere Prozesse müssen warten

Ein LOCK Objekt stellt Prozessen zwei Operationen zur Verfügung:

Operation acquire (lock)

Ein Prozess kann eine Ressource anfordern. Ist der Lock im Zustand σLock=FREE, wird dem anfordernden Prozess die Ressource gewährt (Zustandsübergang σLock: FREE ⇒ LOCKED), andernfalls wird er blockiert bis die Ressource (vom Eigentümer) freigegeben wird.

Operation release (unlock)

Ein Prozess gibt eine zuvor mit acquire beanspruchte Ressource wieder frei (Zustandsübergang σLock: LOCKED ⇒ FREE).

Ein Prozess muss die Operationen acquire und release immer paarweise verwenden!

Abbildung 9-1. Zustandsübergangsdiagramm des Lock Objekts

Beispiel der Nutzung eines Lock Objekts für den Schutz von kritischen Bereichen beim Zugriff auf geteilte Ressourcen

 1: OBJECT L: LOCK
 2: VAR V
 3: PAR
 4:   PROCESS P₁ IS                         PROCESS P₂ IS
 5:   WHILE (True)                          WHILE (True)
 6:     non-critical section                  non-critical section
 7:     L.ACQUIRE()                           L.ACQUIRE()
 8:      critical section(V)                   critical section(V)
 9:     L.RELEASE()                           L.RELEASE()
10:     non-critical section                  non-critical section
11:   DONE                                  DONE

Das Lock Objekt löst das mutuale Ausschlussproblem (mutual exclusion), und wird daher auch als Mutex bezeichnet.

Mehr als zwei Prozesse können mit einem Lock synchronisiert werden.

Synchronisation durch Blockierung

Ereignisbasierte Synchronisation blockiert die Ausführung von Prozessen bis das Ereignis auf das gewartet wurde eingetreten ist.

Hier die Freigabe eines belegten Lock Objekts

Atomare Ressourcen: Register

Ein Schreib-Lese Register ist die einfachste Form einer geteilten Ressource und wird für die Implementierung eine Lock Objektes benötigt.

Aber: Operationen auf dieses Register müssen atomar und konfliktfrei sein, d.h., sequenzialisierbar sein!

Der Zugriff auf ein atomares Register R erfolgt mittels zweier Operationen op={read,write}: R.read(), welches den aktuellen Wert von R zurück liefert, und R.write(v), welche einen neuen Wert in das Register schreibt. Dabei ist ein Konflikt durch konkurrierende Schreib- und Lesezugriffe von einer Menge von Prozessen durch mutualen Ausschluss aufgelöst!

Atomares Register

Eigenschaften eines atomaren Registers

Ein atomares geteiltes Register erfüllt dabei folgende Eigenschaften:

Zugriffe (op=read/write) erscheinen als wären sie zu einem einzigen Zeitpunkt τ(op) ausgeführt worden.

Der Zeitpunkt der Ausführung der Operation liegt garantiert innerhalb des Intervalls:

τ(opS) ≤ τ(op) ≤ τ(opE), mit

S: Start und E: Ende der Operation (gemeint ist: Aktivierung durch Prozess)

Für zwei verschiedene Operationen op₁ und op₂ gilt:

τ(op₁) ≠ τ(op₂)

Jede Lese-Operation gibt den Wert zurück der von der am nächsten (in der Vergangenheit) liegenden Schreibe-Operation resultiert.

Das bedeutet: ein atomares Register verhält sich so als ob die Ausführung aller Operationen sequenziell ausgeführt worden wäre.

Komposition mit atomaren Objekten

Atomarität erlaubt die einfache Komposition von geteilten (atomaren) Objekten zu neuen geteilten und atomaren Objekten ohne zusätzlichen (Synchronisations-) Aufwand.

D\.h. wenn eine Menge von für sich atomaren Registern {R₁,R₂,..} mit den Operationen {R₁.read,R₁.write}, {R₂.read,R₃.write}, .. zu einem neuen Objekt (R₁,R₂,...) zusammengefasst (komponiert) werden, so ist dieses ebenfalls atomar.

Lock und atomare Operationen { - }

Abbildung 9-2. Beispiel von konkurrierenden und zeitlich überlappenden Schreib/Lese Zugriffen auf ein atomares Register

Mutex: Der Mutuale Ausschluß

Protokolle

Es muss in jedem Prozess der einen kritischen Bereich ausführen muss ein Eingangs- und Ausgangsprotokoll eingehalten werden damit der mutuale Ausschluss garantiert werden kann.

Für die Implementierung dieses Protokolls soll gelten:

Mutualer Ausschluss und Einhaltung der Lock Invariante (logische Bedingung): Höchstens ein Prozess zur Zeit führt seinen kritischen Abschnitt aus.

Keine Deadlocks und Livelocks: Wenn zwei oder mehr Prozesse versuchen, ihre kritischen Abschnitte zu betreten, wird mindestens einer erfolgreich sein.

Niedrige Latenz (niedrige Verzögerung): Wenn ein Prozess versucht, in seinen kritischen Abschnitt einzutreten, und die anderen Prozesse ihre nicht kritischen Abschnitte ausführen oder beendet haben, wird der erste Prozess nicht daran gehindert, in seinen kritischen Abschnitt einzutreten.

Garantierter Eintritt: Ein Prozess, der versucht, in seinen kritischen Abschnitt einzutreten, wird schließlich erfolgreich sein.

Mutex Objekt

Eine Mutex ist das einfachste aber wichtigste Synchronisationsobjekt für parallele Systeme. Es dient der Datenkonsistenz durch Schutz von krtischen nicht atomaren Ausführungsbereichen.

Das Objekt bietet mindest zwei Operationen:

lock (acquire)

Ein Prozess versucht den Mutex Lock zu erlangen. Wenn dieser Prozess der einzige Bewerber ist bekommt er den Lock und kann in der Ausführung fortfahren. Ist der Lock bereits an einen anderen Prozess vergeben, wir der Aufrufer blockiert (Warten).

unlock (release)

Ein Prozess gibt den Lock zurück. Wenn es wartende Prozesse gibt wird maximal einer ausgewählt und erhält den Lock.

Lua CSP

local mu = Mutex()

Par({
  function () .. mu:lock() .. mu:unlock() .. end,
  function () .. mu:lock() .. mu:unlock() .. end,
  function () .. mu:lock() .. mu:unlock() .. end,
  ...
}, {
  mu = mu
})

Beispiele für den Einsatz einer Mutex

Nicht atomare Operationen auf geteilte Dateneregister

local mu = Mutex()
local x  = Register:new('float');
Par({
  function ()
    mu:lock(); x:write(x:read() + 1); mu:unlock()
  end,
  function ()
    mu:lock(); x:write(x:read() - 1); mu:unlock()
  end,
}, {
  mu = mu,
  x = x
})
print(x:read())

Nicht atomare Operationen auf geteilte Datenestrukturen, z.B. Listen oder Graphen

/shelllvm

size

Mu

require "Csp"
local Register = class()
function Register:init (datatype,init)
  self.__class=Register;
  if datatype == nil then
    if type(init) == 'number' then self.type='double'
    else self.type='int' end
  else self.type=datatype end
  self.data=luv.thread.buffer.create(1,self.type,init)
end
function Register:read()
  return self.data:get(1)
end
function Register:write(v)
  return self.data:set(1,v)
end
local mu = Mutex()
local x  = Register:new('float');
Par({
  function ()
    mu:lock();
    x:write(x:read() + 1);
    mu:unlock()
  end,
  function ()
    mu:lock();
    x:write(x:read() - 1);
    mu:unlock()
  end,
}, {
...

Mutex

Invariante

Zu jedem Zeitpunkt t darf maximal ein Prozess den Lock besitzen. Weitere Anfragen des Locks müssen garantiert abgewiesen werden. Nur ein Prozess darf maximal den Wettbewerb gewinnen.

Man unterscheidet schwache und starke Mutex Objekte:

Bei starken Mutex Objekten darf nur der Prozess den Lock freigeben der ihn agefordert hat und besitzt. Ein Versuch eines Nichteigentümers führt zu einem Programmfehler (Versagen)

Bei schwachen Mutex Objekten darf jeder Prozess den Lock freigeben (und auch wenn dieser garnicht vergeben ist)

Semaphore

Eigenschaften

Ein Semaphore Objekt S ist ein Lock basiertes Synchronisationsobjekt und ein geteilter Zähler mit Warteschlange S.counter, das folgende Eigenschaften erfüllt:

Die Bedingung S.counter ≥ 0 ist immer erfüllt.

Der Semaphorenzähler wird mit einem nicht-negativen Wert s₀ initialisiert.

Es gibt zwei wesentliche Operationen {S.down, S.up} um den konkurrierenden und synchronisierenden Zugriff auf eine Semaphore zu ermöglichen.

Wenn #(S.DOWN) und #(S.UP) die Anzahl der Operationsaufrufe ist, die terminiert sind, so gilt die Invariante:

image-placeholder
(9-1)

Operationale Semantik

Operation down (wait)

S.down erniedrigt den Zähler S.counter atomar um den Wert 1 sofern S.counter > 0.
Wenn S.counter=1 und mehrere Prozesse versuchen gleichzeitig die down Operation anzuwenden, so wird einer den Wettbewerb gewinnen (Mutualer Ausschluss = Lock). Wenn S.counter = 0 dann werden Prozesse blockiert und in einer Warteschlange S.Q eingereiht.

Operation up (signal)

S.up erhöht den Zähler S.counter atomar um den Wert 1. Diese Operation kann immer ausgeführt werden, und blockiert nicht die Ausführung des aufrufenden Prozesses.
Wenn S.counter = 0 ist und es blockierte Prozesse gibt, wird einer aus S.Q ausgewählt und freigegeben (d. h. der Zähler ändert sich effektiv nicht).

Eine Semaphore mit s₀=1 ist eine binäre Semaphore vergleichbar mit einer Mutex! Eine Semaphore ist stark wenn die blockierten (wartenden) Prozesse in der Reihenfolge wieder freigegeben werden in der sie blockiert wurden (First In First Out / FIFO Ordnung).

Lua

local sem = @Semaphore(init)
Par({
  function () P:down() .. C:up()end,
  function () P:down() .. C:up()end,
  function () loop(2) P:up() .. loop(2) C:down() end
},{ P = Semaphore(0), C =Semaphore(0) })

/shelllvm

size

SemaProCon

require "Csp"
local A = Matrix:new({20});
A:random()
local B = Matrix:new({2});
Par({
  function ()
    local x=0
    P:down()
    for i=1,10 do x = x + A:read(i) end
    B:write(x,1)
    C:up()
  end,
  function ()
    local x=0
    P:down()
    for i=11,20 do x = x + A:read(i) end
    B:write(x,2)
    C:up()
  end,
  function ()
    for i=1,2 do P:up() end
    for i=1,2 do C:down() end
    -- collect results
    print(B:print())
  end
},{
  P = Semaphore(0),
  C = Semaphore(0),
  A = A,
  B = B
...

Algorithmus

 1: OBJECT SEMAPHORE(init) IS
 2:   VAR counter:INT
 3:   OBJECT Q:QUEUE, L:LOCK
 4:   OPERATION down(i) IS
 5:     L.lock()
 6:     IF counter = 0 THEN
 7:       Q := Q + {i}
 8:       |L.unlock(),BLOCK(i)|
 9:     ELSE
10:       counter := counter - 1
11:       L.unlock()
12:     END IF
13:     RETURN
14:   END OPERATION

 1: OPERATION up(i) IS
 2:   L.lock()
 3:   IF counter = 0 THEN
 4:     IF Q = {} THEN
 5:       counter := counter + 1
 6:     ELSE
 7:       j := Head(Q), Q := Tail(Q)
 8:       UNBLOCK(j)
 9:     END IF
10:   ELSE counter := counter + 1
11:   END IF
12:   L.unlock()
13:   RETURN
14: END OPERATION

Algorithmus 9-1. Semaphore mit Lock Objekt

Implementierung mit Channels

Verwendung von voll synchronisierten Channels (Rendezvous):

Vom Teilnehmer- zum Semaphoreprozess ein Request Channel chr

Vom Semaphore- zum Teilnehmerprozess ein Ack. Channel chg

Semaphoreprozess benutzt Alt Operator für alle Request Channels

Semaphore - Produzenten-Konsumenten Systeme

Semaphoren können eingesetzt werden um konkurrierende Produzenten-Konsumenten Probleme zu lösen. Beispiel ist ein Pufferspeicher mit First-In First-Out Reihenfolge, der eine endliche Anzahl von Speicherzellen eines geschützten Speichers Buf[0..k-1] mit k=size besitzt, und die beiden Zustände S={FREE, FULL} annehmen kann.

Schutz des Speichers bedeutet: gleichzeitiger Zugriff zweier Prozesse auf gleiche Speicherzelle Buf[x] muss verhindert werden.

Schutz durch zwei Semaphoren FREE(k) und BUSY(0).

Implementierung eines Pufferspeichers mit Semaphoren

 1: OBJECT BUFFER (size) IS
 2:   VAR BUF: datatype[size], in,out: INT
 3:   OBJECT FREE: SEMA(size),
 4:          BUSY:SEMA(0)
 5:   OPEARTION produce(v) IS
 6:     FREE.down()
 7:     BUF[in].write(v)
 8:     in := (in+1) mod size
 9:     BUSY.up()
10:   END OPERATION

1:   OPERATION consume IS
2:     BUSY.down()
3:     r := BUF[out].read()
4:     out := (out+1) mod size
5:     FREE.up()
6:     RETURN r
7:   END OPERATION
8: END OBJECT

Algorithmus 9-2. Synchronisierter Pufferspeicher (Queue)

Abbildung 9-3. Synchronisation von Produzenten und Konsumenten von Daten mittels zweier Semaphoren

Semaphore - Dining Philosophers

Das Problem der fünf dinierenden Philosophen ist ein Beispiel für Deadlocks in verteilten und parallelen (asynchronen) Systemen mit dem Communicating Sequential Processes Modell!

5 Philosophen an einem Tisch

5 Gabeln, jeweils eine zwischen zwei Philosophen

Ein Philosoph braucht zwei Gabeln zum Essen!

Eine Gabel wird durch eine Semaphore repräsentiert (atomare Ressource, Startwert des Zählers ist 1)

 1: OBJECT ARRAY Forks [N]: SEMA(1)
 2: PROCESS ARRAY Philosopher [N]
 3:   FOR try = 1 TO 10 DO
 4:     THINKING ...
 5:     Forks[#id].down()
 6:     Forks[#id+1 % N].down()
 7:     EATING ...
 8:     Forks[#id+1 % N].up()
 9:     Forks[#id].up()
10:   DONE
11: END

Kode 9-1. Dinining Philosophers Template

Klassisches Problems das zu Deadlocks führt!

Deadlockefreie Lösungen

Einführung einer zentralen Instanz die die Gabeln mittels Prioritäswarteschlangen verwaltet

Prozess fragt mit einer Nachricht zwei Gabeln an (Input Channel)

Verwalter prüft Verfügbarkeit und gewährt die Gabeln durch eine Antwortnachricht (Output Channel)

Ein Prozess gibt Gabeln mit einer Nachricht wieder zurück

Abfrage des Semaphorenwertes beider Gabeln bevor die Ressource angefragt wird ggf. über eine globale Mutex geschützt:

sema[left]:down();
if sema[right]:level() == 1 then sema[right]:down()
else sema[left]:up(); sleep(random time) end

Münzwurf und Reihenfolge des Zugriffs: Eine Zufallszahl zwischen 0..1 entscheidet ob zuerst die linke und dann rechte Gabel beansprucht wird oder umgekehrt.

Ergeinisobjekt (Event)

Ein Event ist ein Signalobjekt. Ein oder mehrere Prozesse können auf das Eventsignal warten. Ein weiterer Prozess signalisiert schließlich das Event

Es gibt zwei Operationen:

Opeartion await

Ein Prozess wartet auf das Eintreten des Ereignisses (das Signal). Der Prozess blockiert bis das Signal eintrifft und wird in eine Warteschlange Q eingereiht.

Operation wakup

Ein Prozess signalisiert das Ereignis. Alle in die Warteschlange befindlichen Prozesse werden aktiviert.

Lua CSP

local ev = Event()
Par({
  function () ev:await() .. end,
  function () ev:await() .. end,
  function () ev:wakeup() .. end
},{ ev:ev })

Wenn das Signal vor dem Erwarten ausgelöst wird ist das Signal verloren und wartende Prozesse werden nicht frei gegeben!

Barriere

Um das Problem des Wettrennens bei Events zu vermeiden ist es besser eine Barriere für eine Prozessgruppe bekannter Größe zu verwenden.

Da Barriere ist selbstauslösend, d.h. der letzte Prozess löst das Signal aus.

local ba = Barrier(groupsize)
Par({
  function () ba:await() .. end,
  function () ba:await() .. end,
  function () ba:await() .. end
},{ ba:Barrier(3) })

/shelllvm

size

Barrier

require "Csp"
local A = Matrix:new({20});
A:random()
local B = Matrix:new({2});
Par({
  function ()
    local x=0
    P:await()
    for i=1,10 do x = x + A:read(i) end
    B:write(x,1)
    C:await()
  end,
  function ()
    local x=0
    P:await()
    for i=11,20 do x = x + A:read(i) end
    B:write(x,2)
    C:await()
  end,
  function ()
    P:await();
    -- collect results
    C:await();
  end
},{
  P = Barrier(3),
  C = Barrier(3),
  A = A,
  B = B
})
...

Timer

Ein Timer ist ein automatisch synchronisierendes Event

local t = Timer(interval, once, fiber?)
Par({
  function () loop t:await() .. end
  function () loop t:await() .. end
  function () t:start() .. end
},{t:Timer(1000,false)}}

Definition 9-1. Lua CSP Timer

Channel

Ein Kanal ist ein synchronisierter Pufferspeicher mit First-In First-Out Reihenfolge und wird in Produzenten-Konsumenten Systemen eingesetzt.

Operationen und Verhalten

Operation read

Ein Datenelement wird aus dem Puffer gelesen. Wenn der Puffer leer ist wird der Prozess in eine Wartschlange eingereiht: Q=Q ∩ {P}

Operation write

Ein Datenelement wird in den Puffer geschrieben. Wenn die Warteschlange Q ≠∅, dann wird ein Prozess entfernt und die ausstehende read Operation ausgeführt.

Ist die Puffergröße Null, dann Rendezvous Handshake!

local ch = Channel(size,fiber?)
Par({
  function () local v = ch:read() .. end,
  function () ch:write(ε) .. end
},{ch=ch})

Definition 9-2. Lua CSP Channels

/shelllvm

size

ChannelProCon

require "Csp"
local A = Matrix:new({20});
A:random()
Par({
  function ()
    local x=0
    local range = P1:read()
    for i=range[1],range7-1 do x = x + A:read(i) end
    C1:write(x)
  end,
  function ()
    local x=0
    local range = P2:read()
    for i=range[1],range7-1 do x = x + A:read(i) end
    C2:write(x)
  end,
  function ()
    P1:write({1,10});
    P2:write({11,20});
    local b1 = C1:read()
    local b2 = C2:read()
    print(b1,b2)
  end
},{
  P1 = Channel(1),
  P2 = Channel(1),
  C1 = Channel(1),
  C2 = Channel(1),
  A = A,
})

Der Alt Prozesskonstruktor

Die Arbeit mit Channels kann bedeuten dass ein Prozess aus mehreren Channels gleichzeitig Daten lesen muss, aber aufrgund des synchronen Verhaltens nicht alle Channel einer Gruppe Ch={chi} abfragen kann.

Ein Lösung bietet der Alt(ernative) Prozesskonstruktur der es ermöglich auf das Eintreten mehrerer Ereignsse (hier die Verfügbarkeit von Daten in Channels) zu warten und eines auszuwählen.

Der Alt Prozess garantiert Mutual Exclusion Verhalten, d.h.:

Treten mehrere Ereignisse gleichzeitig ein, wird genau eines (wie auch immer) ausgewählt und ein Verarbeitungsprozess gestartet

Nur maximal eine Operation (also channel:read) wird aus Ch={chi} ausgeführt, auch wenn die anderen bereist eingetretende Ereignisse (Daten) haben (Mikro Event loop!!)

Alt Prozesskonstruktor

ch1 = Channel()
ch2 = Channel() ...
  local x
  Alt({
    function () x=ch1:read(); <optional handler code> end,
    function () x=ch2:read(); <optional handler code> end,
    ..
  })
  <process x>

Definition 9-3. Lua CSP Auswahlprozesskonstruktor. Es wird immer nur einer der Alt Prozesse aktiviert wenn die blockierende Anweisung (read) bereit wird

Monitor

Mutex und Semaphore sind low-level Synchronisationsobjekte

Monitore erlauben die Definition von konkurrierenden Objekten auf der Abstraktionsebene der imperativen Programmiersprachen → high-level.

Ein Monitor ist eine Generalisierung eines Objekts, welches Daten und Operationen kapselt. Zugriff auf die interne Repräsentation erfolgt durch die Operationen mutual exklusiv.

Aber immer mit dem Ziel die Datenkonsistenz möglichst frein granular zu gewährleisten.

Abbildung 9-4. Objektmonitor mit automatischen Schutz (Datenkonsistenz des Objekts)

Konzepte

Mutualer Ausschluss

Der Monitor stellt sicher dass immer nur ein Prozess eine Operation des Objektes ausführen kann ⇒ geschützter kritischer Ausführungsbereich = mutualer Ausschluss.

Ein Prozess muss das Schloss des Monitors öffnen. Nachdem der Prozess den Monitor "betritt" (nutzt), schließt das Schloss automatisch wieder. Wenn der Prozess den Monitor verlässt wird das Schloss wieder automatisch geöffnet.

Events: Bedingungsvariablen mit Queues

Bedingungsvariablen C sind Objekte die interne Synchronisation ermöglichen sollen.

Bedingungsvariablen können nur innerhalb des Monitors durch folgende Operationen verwendet werden:

Operation C.wait(cond)

Diese Operation blockiert = stoppt den aufrufenden Prozess p und reiht ihn in die Warteschlange C.Q ← C.Q + {p} ein. Für den Prozess der nicht mehr aktiv ist, kann der Mutex LOCK aufgehoben werden.

Die Wait Operation stellte eine boolesche Bedingung cond dar auf deren Erfüllung gewartet wird.

Operation C.signal()

Ein Prozess p ruft diese Operation auf und erfüllt damit die Bedingung cond.

Wenn C.Q = ∅ ist dann hat die Operationen keinen Effekt

Wenn C.Q = {q,...} dann wird ein Prozess q aus Q ausgewählt und aktiviert, so dass C.Q ← C.Q \\ {q}

Bewahrung des mutualen Ausschlusses in Fall ii.) erforderlich:

Der aktivierte Prozess q fährt innerhalb des Monitors fort (bekommt den Eintritt wieder) und führt die Anweisungen nach C.wait() aus.

Der aktivierende Prozess p wird blockiert, hat aber höchste Priorität den Monitor danach wieder zu erlangen um die Anweisungen nach C.signal() auszuführen.

Operation C.empty()

Liefert das Ergebnis für die Bedingung C.Q = ∅

Algorithmik der Bedingungsvariablen (vereinfacht)

1: OBJECT CONDITION
2:   (M:MONITOR) IS
3:   OBJECT q: QUEUE               OPERATION signal IS
4: 	 p: PROCESS               IF q != {} THEN
5:   OPERATION wait IS                 p := Head(q), q := Tail(q)
6:     p := MYSELF()                   UNBLOCK(p)
7:     q := q + {p}                  END IF
8:     |BLOCK(p) & M.l.unlock()|   END OPERATION
9:   END OPERATION

Implementierung einer Semaphore mit Bedingungsvariablen (vereinfacht)

1: MONITOR SEM IS
2:   VAR s:INT
3:   OBJECT c: CONDITION
4:   OPERATION down IS         OPERATION up IS
5:     IF s=0 THEN c.wait()      s := s + 1
6:       s := s - 1              c.signal();
7:     RETURN                    RETURN
8:   END OPERATION             END OPERATION

Algorithmus 9-3. Semaphore mit Bedingungsvariablen

Um den mutualen Ausschluss zu garantieren muss Vorrang der Prozessausführung und Aktionen mit Bedingungsvariablen definiert werden.

Wartende bereite Prozesse (Menge 𝕎) deren Bedingung cond erfüllt ist.

Signalisierende Prozesse (Menge 𝕊)

Prozesse die noch keinen Eintritt in den Monitor erhalten haben (blockiert, Menge 𝔼)

Prioritäten: Prio(𝕎) > Prio(𝕊) > Prio(𝔼)

Ein signalisierter (blockierter) Prozess der auf eine Bedingung C wartet wird sofort aktiviert (d. h. die Bedingung ist erfüllt).

Abbildung 9-5. Verschiedene Prozessmengen bei Monitoren

Würde nach Aktivierung des wartenden Prozesses (cond=TRUE) auch der signalisierende Prozess im Monitor aktiv sein könnte er die Bedingung, die der Bedingungsvariablen zu Grunde liegt, wieder ungültig (cond=FALSE) machen und müsste ebenfalls wieder blockiert werden.

Es gilt daher für den Monitor die Erfüllung eines Prädikats P (Boolesche Bedingung), das die Datenkonsistenz des Objektes sicher stellen muss.

Varianten

signal-and-wait

Der signalisierende Prozess wartet nach der Signalisierung und der mutuale Ausschluss ist sichergestellt und die Wahrung P=TRUE. Der wartende Prozess führt aus: IF ¬P THEN C.wait() END IF

signal-and-continue (re-check)

Der signalisierende Prozess läuft weiter! Das könnte zur Verletzung des Prädikats P führen, daher muss der signalisierte Prozess nochmals die Gültigkeit P=TRUE prüfen so dass für ihn auszuführen ist: WHILE ¬P DO C.wait () END WHILE

Objektmonitore in Lua

local S = class()
function S:init (i)
  self.counter=i;  self.L=Mutex()
end
function S:up ()
  self.counter=self.counter+1
end
function S:down ()
  self.counter=self.counter+1
end
function S:__index (index)
  local value = rawget( self, index )
  if value == nil then
    return function (...)
      rawget( self, 'L' ):lock();  -- LOCK
      rawget(getmetatable(self), index)(...) -- CALL PROT
      rawget( self, 'L' ):unlock() -- UNLOCK
    end
  else return value end
end

Kode 9-2. Beispiel für einen einfachen und naiven geschützten Monitor in Lua. Wo könnte es Probleme geben?

Zusammenfassung

Es gibt verschiedene Synchronisations- und Kommunikationsobjekete für Prozesssysteme (parallel wie sequenziel) ⇒ Interprozesskommunikation

Häufige Objekte: Mutex, Semaphore, Event, Barriere, Timer, Channel, Monitor

Diese Objekte müssen Invarianten erfüllen die zu keinem Zeitpunkt verletzt werden dürfen (d.h. ungültig werden)

Metriken und Verhalten von Parallelen Programmen

Wie können parallele und nebenläufige Prozesse quantitativ erfasst werden?

Was kann schief gehen?

Was begrenzt die Parallelisierung?

Zustands-Raum Diagramme

Für die Visualisierung und Analyse von nebenläufigen Prozessen und Aktionen

Zustands-Raum Diagramme beschreiben die möglichen Zustands-Entwicklungen - das temporale Verhalten - von parallelen Programmen.

Computer sind endliche Zustandsautomaten. Der Zustandsübergang wird durch die Programminstruktionen hervorgerufen.

Der Zustand S eines parallelen Programms welches aus N Prozessen Pi besteht setzt sich zusammen aus folgenden Tupeln:

Globale Variablen des Programms: <V1,V2,V3,... >

Lokale Variablen und Instruktionszeiger von Prozess 1: <v1,1,v1,2,v1,3,...,I1 >

Lokale Variablen und Instruktionszeiger von Prozess 2: <v2,1,v2,2,v2,3,...,I2 > usw.

Die Berechnung ändert globale und lokale Variablen (Datenfluss) sowie Instruktionszeiger (Kontrollfluss) und führt zu einer Zustandsänderung comp: si → sj.

Nebenläufige Programmierung: Zustands-Raum Diagramme

Wesentliche Zustandsänderung ist die Änderung von lokalen und globalen Speicher (Daten).

Variablen sind Bestandteil von Ausdrücken und erlauben zwei Operationen: {read,write}

1: var x: read(x) ⇔ RHS value(x) → ε (value(x))
2:        write(x,v) ⇔ LHS reference(x) → x := v

Beschreibung eines parallelen Programms auf Programmierebene

Der Zugriff auf globale und somit geteilte Variablen muss atomar sein, d.h. immer nur ein Prozess kann den Wert einer Variable lesen oder einen neuen Wert schreiben.

Der parallele Zugriff auf eine geteilte Ressource muss aufgelöst werden (Konflikt): i.A. mutualer Ausschluss durch Sequenzialisierung der parallelen Zugriffe!

Beispiel

1:   write(X,v₁) || write(X,v₂) || x₃:=read(X) →
2:   write(X,v₁); read(X,x₃); write(X,v₂) |
3:   x₃=read(X);  write(X,v₂); write(X,v₂) | ..

Algebraisch ausgedrückt ergibt sich die Transformation:

image-placeholder
(10-1)

Es gibt eine Menge von möglichen Entwicklungen des parallelen Systems!

Instruktionen von Prozessen werden sequenziell ausgeführt. Instruktionen können auf prozesslokale und programmglobale Variablen zugreifen.

Definition eines parallelen Programms: globale Variablen (V) und Prozesse mit lokalen Variablen (v)

1: var V₁,V₂,...
2: process p₁(a₁,a₂,...)   process p₂(a₁,a₂,...)
3:   var v₁,v₂,....          var v₁,v₂,....
4:   <Instruktion₁ i₁>       <Instruktion₁ i₁>
5:   <Instruktion₂ i₂>       <Instruktion₁ i₂>
6:   Vi := ε(ai,vi,Vi)        Vi := ε(ai,vi,Vi)
7:   vi := ε(ai,vi,Vi)        vi := ε(ai,vi,Vi)
8: end                     end

Bei einem sequenziellen Programm ist das Ergebnis einer Berechnung (d.h. die Werte aller Variablen) deterministisch allein durch die Anweisungssequenz und die Eingabedaten gegeben, und kann beliebig oft wiederholt werden - immer mit dem gleichen Ergebnis → Reihenfolge aller Anweisungen der Berechnung vorgegeben und fest

Bei einem parallelen Programm können mehrere Anweisungen verschiedener Prozesse gleichzeitig oder überlappend ausgeführt werden bzw. konkurrieren.

Die Reihenfolge parallel ausgeführter Anweisungen von einzelnen Prozessen kann hingegen undeterministisch = zufällig sein!!

Jeder der Prozesse kann als nächster den Zustand des Programms ändern.

Ein Zustands-Raum Diagramm beschreibt die Änderung des Programmzustandes als sequenzielle Auswertung aller möglichen Prozessaktivitäten.

Das Diagramm ist ein gerichteter Graph, dessen Knoten den aktuellen Programmzustand s ∈ S beschreiben, und dessen Kanten die möglichen Zustandsübergänge beschreiben.

Es gibt einen ausgewiesen Startzustand (Initialisierung) und einen oder mehrere Endzustände.

Gibt es mehrere Endzustände liegt wohl möglich ein Entwurfsfehler vor, da das Programm unterschiedliche Endergebnisse liefern kann.

Algorithmus: Entwicklung des Zustands-Raum Diagramms

Es gebe ein paralleles Programms welches aus N Prozessen P={p₁,p₂,..,pN} besteht.

Initialisiere den Startzustand sx=s₀ und erzeuge Wurzel-Knoten s₀ im Diagramm.

Aktueller Zustand: sx. Setze P*:=P mit P={p₁,p₂,..,pN} als Prozessliste und S*={}

Wähle (entferne) einen beliebigen Prozess px aus der Prozessliste P* und setze P*:= {pn| pn ∈ P* ∧ pn ∉ px}

Evaluiere die nächste Instruktion ix,n von px und berechne die Wirkung auf lokale und globale Variablen sowie den Instruktionszeiger Ix,n.

Erzeuge einen neuen Zustandsknoten sj/=x , füge ihn zur Liste S*:=S* ∪ {sj} hinzu und verbinde ihn mittels einer Kante tx→j mit dem aktuellen Ausgangszustand sx

Wiederhole Schritt 3 bis 5 für alle anderen verbleibenden Prozesse p ∈ P bis P*={}

Setze S**:=S*. Für jeden Knoten sx ∈ S** wiederhole die Schritte 2 bis 6. Iteriere Schritt 7 bis alle Prozesse terminiert sind oder keine Zustandsänderung mehr auftritt.

Beispiel

1: Sequenzielles Programm      Paralleles Programm
2: for i := 1 to 3 do i₁        process p₁
3:                                for i := 1 to 3 do i₁
4:                              end
5:                              process p₂
6:                                for j := 1 to 3 do i₂
7:                              end

Abbildung 10-1. Beispiel und mögliche Entwicklung des Programmzustandes (lokale Var. i,j)

Globale Ressourcen und Synchronisation

Globale Ressourcen

In dem bisherigen Programmiermodell gibt es nur globale Variablen als globale geteilte Ressourcen, die konkurrierend von Prozessen gelesen und verändert werden können.

Die globalen Variablen dienen dem Datenaustausch = Kommunikation zwischen den Prozessen (Shared Memory Model!).

Shared Memory dient aber nur dem Datenaustausch, es bietet keine höhere Synchronisation zwischen Prozessen

Bei nachrichtenbasierter Kommunikation (und auch Channels/Queues) ist das anders.

Atomare Aktionen

Atomare Operationen, Schreibweise |A| werden in einem Schritt ausgeführt und können nicht durch andere Prozesse unterbrochen werden (keine Interferenz).

Einzelne Lese- und Schreibe-Operationen mit globalen Variablen sind atomar. Nebenläufigkeit wird durch Sequenzialisierung aufgelöst.

t1: |X := v|

Nicht atomare Aktionen und Synchronisation

Zusammengesetzte Ausdrücke können aus mehreren Berechnungsschritten bestehen, so ist z. B. X := X + 1 als Ganzes nicht mehr atomar!

1: t₁: |temp=X|
2: t₂: |X:=temp+1|
3: ⇔
4:     |X:=X+1| ??

Beispiel einer unzureichend geschützten nicht atomaren Aktion

1: var X := 0
2: INCR(X)     DECR(X)
3: process p₁     process p₂
4:   var t:=0       var t:=0
5:   t := X         t := X
6:   X := t + 1     X := t - 1
7: end            end

Abbildung 10-2. Zustands-Raum Diagramm mit unterschiedlichen Endergebnissen (X=0,-1,1)

Experiment

/shelllvm

size

Counter

require "Csp"
local Register = class()
function Register:init (datatype,init)
  self.__class=Register;
  if datatype == nil then
    if type(init) == 'number' then self.type='double'
    else self.type='int' end
  else self.type=datatype end
  self.data=luv.thread.buffer.create(1,self.type,init)
end
function Register:read()
  return self.data:get(1)
end
function Register:write(v)
  return self.data:set(1,v)
end
local ba = Barrier(2)
local x  = Register:new('float');
Par({
  function (id)
    ba:await()
    local t
    for i=1,100000 do
      t = x:read()
      t = t + 1
      x:write(t)
    end
    print(id..':t='..t)
  end,
  function (id)
...

Nicht atomare Aktionen (Sequenz von Aktionen) mit globalen Ressourcen müssen durch Mutuale Ausschlusssynchronisation geschützt werden→ Schutz von kritischen Kodebereichen ⇒ Datenkonsistenz!

Semaphor

Ein Semaphor S ist ein Zähler s>0 der niemals negative Werte annehmen kann.

Es gibt zwei atomare Operationen die von einer Menge von Prozessen P={p₁,p₂,...} auf einem Semaphor S angewendet werden können:

1: operation down(S) ∈ p:
2:   |if s > 0
3:    then s := s - 1
4:    else WAITERS+(S,p),block(p)|
5: operation up(S) ∈ p:
6:   |if s = 0 and WAITERS(S) ≠ []
7:    then pi=WAITERS-(S),unblock(pi)
8:    else s := s + 1|

Definition 10-1. Operationen der Semaphore

Ein Semaphor mit einem Startwert s=1 entspricht einer Mutex (binärer Semaphor). Ein DOWN(S) leitet einen kritischen Bereich in einer Sequenz i₁,i₂,i₃, ... ein, und ein UP(S) gibt ihn wieder frei:

1: semaphore S(1)
2: ... down(S) |i₁,i₂,i₃,..,in)| up(S) ...

Beispiel einer mit einem Semaphor geschützten nicht atomaren Aktion

 1: var X := 1
 2: semaphore S := 1
 3: INCR(X)        DECR(X)
 4: process p₁     process p₂
 5:   var t:=0       var t:=0
 6:   down(S)        down(S)
 7:   t := X         t := X
 8:   X := t + 1     X := t - 1
 9:   up(S)          up(S)
10: end            end

Abbildung 10-3. Zustands-Raum Diagramm mit einem Endergebnis (X=0)

Eigenschaften von Parallelen Systemen

Konkurrieren mehrere Prozesse um die Ressource K, so gewinnt maximal einer, die anderen verlieren den Wettbewerb.

Wettbewerb

Ein solches Wettbewerbsproblem ist gekennzeichnet durch die Eigenschaften Sicherheit und Lebendigkeit.

Sicherheit bedeutet: Bedingung für Anzahl der Prozesse im kritischen Bereich K muss |{ p | I(p) ∈ K}| ≤ 1 immer erfüllt sein.

Eigenschaft (Liveness) Lebendigkeit → Starvation Freiheit

Starvation Freiheit bedeutet dass ein Prozess pi der eine Ressource/den kritischen Bereich anfragt maximal eine endliche Anzahl von Zeiteinheiten / Wettbewerben n ≠ ∞ durch jeden anderen Prozess umgangen werden kann (Bypass, die anderen haben den Wettbewerb gewonnen).

Eigenschaft Deadlock Freiheit

Wenn bis zu einem beliebigen Zeitpunkt t eine Reihe von Prozessen versucht haben die Ressource / den kritischen Bereich zu erlangen, ihn aber nicht erhalten haben, so wird es in der Zukunft eine Zeit t' > t geben wo sie erfolgreich sind (d.h. die Anfrage-Operation terminiert).

D\.h. eine Anfrage der Ressource terminiert mit einem gewonnen Wettbewerb garantiert irgendwann.

Starvation Freiheit impliziert Deadlock Freiheit!

Worst case eines Deadlocks: alle Prozesse verlieren den Wettbewerb, keiner kann die Ressource mehr nutzen/zugeteilt bekommen!

Eigenschaft Begrenztes (Bounded) Bypass Kriterium

Es gibt eine Funktion f(N) für N Prozesse die die maximale Anzahl von verlorenen Wettbewerben (bei Konkurrenz) angibt.

Benötigt First-In-First-Out Puffer Scheduler!

Service gegen Klient Sichtweise

Der Service ist die Ressource, der kritische Bereich. Der Klient ist der Prozess, der die Ressource anfragt.

Aus Sicht des Service (Ressource) ist die Bewahrung von Invarianten (z.B. Semaphore immer positiv) wichtigstes Kriterium (Sicherheit) gefolgt von der Deadlock Freiheit. Der konkurrierende Wettbewerb führt immer dazu, dass irgendein Prozess die Ressource nutzen kann → die Ressource gewinnt immer.

Aus Sicht des Klienten (eines Prozesses) ist die Starvation Freiheit wichtigstes Kriterium. Wenn immer ein Prozess die Ressource anfragt, wird er sie (eventuell) zugeteilt bekommen → der Prozess gewinnt immer.

Aus der Sicht aller (um eine Ressource konkurrierenden) Prozesse sind die Freiheit von Deadlock und Starvation wichtigstes Kriterien.

Es gibt daher eine Hierarchie der Lebendigkeits- und Sicherheitseigenschaften (entsprechend ihrer Stärke):

1\. Bounded Bypass f(N)=X ≫

2\. Starvation Freiheit ≡ Endlicher Bypass f(N) ≠ ∞ ≫

3\. Deadlock Freiheit ≫

4\. Bewahrung von Invarianten (Konsistenz der Ressource)

Deadlock

Tritt häufig ein wenn zwei (oder mehrere) Prozesse gegenseitig eine Ressource (Lock) beanspruchen die aber jeweils vom anderen bereits belegt ist.

Prozesse, die bereits Sperren halten, fordern neue Sperren an.

Die Anforderungen für neue Sperren werden gleichzeitig gestellt.

Zwei oder mehr Prozesse bilden eine kreisförmige Kette, in der jeder Prozesse auf eine Sperre wartet, die vom nächsten Prozess in der Kette gehalten wird → Dining Philosopher Problem.

Abbildung 10-4. Deadlocksituation zweier Prozesse die wechselseitig gesperrte Ressourcen anfordern

Experimentf

/shelllvm

size

DiningPhil

require('Csp')
local s = {Semaphore(1),Semaphore(1),Semaphore(1)}
local b = Barrier(3)
local function eat(id)
  print('Eating '..id)
end
local function think(id)
  print('thinking '..id)
end
Par({
  function () b:await(); for i = 1,10 do
    s[1]:down(); s7-1:down(); eat(1); s7-1:up(); s[1]:up(); think(1)
  end end,
  function () b:await(); for i = 1,10 do
    s7-1:down(); s[3]:down(); eat(2); s[3]:up(); s7-1:up(); think(2)
  end end,
  function () b:await(); for i = 1,10 do
    s[3]:down(); s[1]:down(); eat(3); s[1]:up(); s[3]:up(); think(3)
  end end
})
print('Done.')

Parallelität

Unterteilung in räumliche und zeitliche Parallelität

Parallele Datenverarbeitung bedeutet Partitionierung eines seriellen Programms in eine Vielzahl von Subprogrammen oder Tasks

Weitere Unterteilung beider Dimensionen in Abhängigkeit von:

Art der Tasks/Algorithmen

Ausführungsmodell der Tasks und verwendete Rechnerarchitektur

Art und Umfang der Wechselwirkung zwischen Tasks

Kontroll- und Datenﬂuss eines Tasks

Räumliche Parallelität

Die Datenmenge D kann in Teilmengen di ⊃ D zerlegt werden. Die minimal erreichbare Größe der Teilmenge gibt Granularität bei der Parallelisierung wieder. Die Datenmenge D wird durch eine Verarbeitungsstufe in eine neue Datenmenge D' transformiert, die dann von nachfolgenden Verarbeitungsstufen weiter verarbeitet wird.
Beispiel : D=Bild ⇒ Glättung ⇒ D₁ ⇒ Objekterkennung ⇒ D₂

Zeitliche Parallelität

Zeitliche Parallelität ist vorhanden, wenn eine Folge von gleichartigen Datenmengen D(n) repitierend mit dem gleichen Algorithmus verarbeitet werden → Pipeline-Verfahren

Datenabhängigkeit

Räumliche und zeitliche Parallelität führen zu räumlicher und zeitlicher Datenabhängigkeit.

Räumliche Datenabhängigkeit findet auf Intra- und Intertaskebene statt.

Intrataskebene: Subtasks tauschen Daten aus → Sequenzielle Ausführung. Beispiel: ST₁: a=x+y; ST₂: b=a+1; → b(a) → ST₂(ST₁)

Intertaskebene: Übertragung von Daten zwischen Tasks in einer Pipeline.

Zeitliche Datenabhängigkeit: Ergebnisse aus der Vergangenheit gehen in aktuelle Datenberechnung ein. Beispiel: Bewegungserkennung aus einer Bild-Sequenz.

Abbildung 10-5. Räumliche und zeitliche Datenabhängigkeit ⇔ Vertikale und horizontale Parallelisierung

Rechenzeit

Die Rechenzeit ttot für die Ausführung einer Pipeline T₁...TM enthält:

Zeit zum Einlesen der Daten I(n),

Zeit für die Ausgabe der Daten und Ergebnisse,

Summe aller Ausführungszeiten der Tasks in der Pipeline, die sich aus Rechen- und Kommuniaktionszeiten zusammensetzten.

image-placeholder
(10-2)

als die Zeit die benötigt wird, einen Task i unter Berücksichtigung von Datenabhängigkeiten der ni Subtasks T(dj) zu bearbeiten.

Längste Bearbeitungszeit eines Subtasks bestimmt Bearbeitungszeit des Tasks τi!

Ti ist der i-te Task in der horizontalen Pipeline,

dj die Teildatenmenge eines Subtasks Ti,i(dj) eines Tasks Ti,

tcomp ist die Rechenzeit,

tcomm die Intertaskkommunikationszeit,

tin und tout die Zeit zum Datentransfer in und aus der Pipeline, und

td(Di,i+1) die Datentransferzeit zwischen zwei Tasks.

In Vision-Systemen sind die ersten Tasks i.A. low- und mid-level Algorithmen, und die letzten Tasks high-level Algorithmen, die auf den Daten der unteren Ebenen aufbauen. Die einzelnen Datenströme Di können daher von unterschiedlicher Größe und Art sein.

Klassiﬁkation von parallelen Algorithmen

Datenabhängigkeit

Lokal, statisch

Ausgangsdaten (≡Ergebnisse) hängen nur von eng begrenzter kurzreichweitiger Region der Eingangsdaten ab. Die Größe der Eingangsdatenregion ist unveränderlich (statisch). → Kommunikationsbedarf ist gering.

Lokal, dynamisch

Die Größe der Eingangsdaten-Region ist parametrisiert und veränderlich (dynamisch). Z.B. bei mathematischer Faltung von Bildmatrizen ändert sich Größe der Region.

Global, statisch

Die Ausgangsdaten hängen gänzlich vom gesamter Eingangsdatenmenge ab. Abhängigkeit hängt nur von der Größe des Bildes, aber nicht von dessen Inhalt ab. Z.B. Fouriertransformation oder Histogramm-Funktionen. → Kommunikationsbedarf ist groß.

Global, dynamisch

Ausgangsdaten hängen von variierenden Ausschnittsregion der Eingangsdaten ab. Die Berechnung ist vollständig datenabhängig. Z.B. Hough-Transformation.

Abbildung 10-6. Klassiﬁkation nach Kommunikationsbedarf aufgrund Datenabhängigkeit zwischen einzelnen Tasks eines parallelen Programms

Weiterhin Klassifikation nach:

Eingabedatenabhängigkeit

Ergebnisabhängigkeit

Speed-up

Bei der Datenverarbeitung gibt es drei Randbedingungen:

Gesamte Rechenzeit → Zeitdimension

Gesamte Ressourcenbelegung → Flächendimension

Bei der Parallelverarbeitung wird eine weitere Dimension hinzugefügt: Anzahl der Verarbeitungseinheiten N

Die Nutzung von Parallelität führt zu einem Performanzgewinn (Speedup) durch Vergleich sequenzielles Programm (N=1) mit parallelen Programm (N Prozessoren):

image-placeholder
(10-3)

Die sog. Skalierung bei der Parallelisierung ist i.A. nicht linear:

image-placeholder
(10-4)

Kommunikation ist weitere Randbedingung bei der parallelen Datenverarbeitung.

Kosten und Laufzeit

Beispiel: Matrixmultiplikation

 1: FUN matmult(A:ARRAY (p,q), B: ARRAY(p,q)) -> C:ARRAY (p,r)
 2: DEF matmult(A, B) =
 3:   FOR i = 1 to p DO
 4:     FOR j = 1 to r DO
 5:       C[i,j] <- 0;
 6:       FOR k = 1 to q DO
 7:        C[i,j] <- C[i,j] + A[i,k] * B[k,j]
 8:       END FOR k
 9:     END FOR j
10:   END FOR i
11: END

Partitionierung kann beliebig erfolgen, da die einzelnen Ergebniswerte Ci,j nicht voneinander abhängen.

Datenabhängigkeit des Problems: Die Berechnung eines Ci,j Wertes hängt außerhalb der FOR-k-Schleife von keinem anderen Wert Cn,m mit n ≠ i und m ≠ j ab.

Mögliche Partitionierungen der drei For-Schleifen auf N parallel arbeitenden Verarbeitungseinheiten (VE):

Jede VE berechnet einen Ci,j-Wert. D.h. eine VE führt die FOR-k-Schleife für ein gegebenes i und +j* durch.

Jede VE benötigt dazu die i-te Zeile von A und die j-te Spalte von B.

Keine weitere Datenabhängigkeit!

Es werden N=p•r VEs benötigt.

Eine VE berechnet eine Ergebnisspalte, d.h. führt die FOR-k und FOR-j-Schleifen durch.

Jede VE benötigt A und eine Spalte von B.

Es werden N=p VEs benötigt.

Eine VE führt eine Multiplikation und Addition innerhalb der FOR-K-Schleife durch.

Jede VE benötigt einen A und B-Wert.

Es werden N=p•r•q VEs benötigt.

Jeweils eine VE für einen gegebenen Ci,j-Wert führt die Zusammenführung der Zwischenwerte der FOR-k-VEs durch.

Zusammenführung der Ergebnisdaten in den Fällen 1&2 trivial. Im Fall 3 besteht Zusammenführung im wesentlichen in der Summation der Zwischenergebnisse.

Abbildung 10-7. Mögliche Partitionierungen der Matrixmultiplikation

Abbildung 10-8. Kosten und Laufzeitanalyse der verschiedenen Parititionierungen

Kommunikation

Berechnung der Kommunikation mit Einheitswerten eines Nachrichtenaustauschs: Message Passing (MP) → Aufwand eine Zelle einer Matrix zu versenden ist MP=1.

Abbildung 10-9. Kommunikation Fall 1

Abbildung 10-10. Kommunikation Fall 2

Abbildung 10-11. Kommunikation Fall 3

Bisher konnten Matrizen ganzzahlig auf VEs verteilt werden. In der Realität ist aber p=q=r,n!

Bisher wurde angenommen, dass alle VEs mit jeder anderen VE Daten mit einer Distanz/Ausdehnung D=1 austauschen kann. Nur möglich mit vollständig verbundenen Netzwerktopologien unter Verwendung von Kreuzschaltern.

Gängige parallele und ökonomische Rechnertopologie: Maschennetz

Besteht aus n × n VEs.

Jede VE kann mit seinem direkten Nachbarn kommunizieren.

Eine Nachricht hat eine maximale Reichweite von (2n-1) VEs, Θ(n).

Bisherige statische Partitionierung resultiert in zu hohen Kommunikationsaufwand in der Verteilung der Matrizen A und B sowie in der Zusammenführung der Matrix C.

Dynamisch veränderliche Partitionierung passt sich effizienter an Netzwerktopologie an.

Bei Matrixoperationen mit zwei Matrizen (n=p=q=r) ist dafür ein 2n × 2n Netz optimal geeignet.

Abbildung 10-12. Zweidimensionales Maschennetzwerk

Dynamische Verteilung der Matrizen

Das 2n x 2n Netz wird in vier Quadranten der Größe n × n unterteilt.

Die Matrizen A und B befinden sich initial im linken unteren und rechten oberen Quadranten

Die Ergebnismatrix C wird schließlich im rechten unteren Quadranten zusammen- geführt.

Alle VEs die ein A1,j-Element besitzen werden dieses nach rechts verschieben.

Alle VEs die ein Bi,1-Element besitzen werden dieses nach unten verschieben.

Dieser Vorgang wird für weitere Zeilen (A) und Spalten (B) fortgesetzt.

Die einzelnen Elemente von A und B passieren die VEs im C-Quadranten. Die einzelnen C-Werte können mittels Summation berechnet werden.

Abbildung 10-13. Dynamische und überlagerte Verteilung der Matrizen *A*, *B*, und *C*

Die Laufzeit der Matrixmuliplikation auf dem Netz beträgt Θ(n), da n Verschiebungen durchgeführt werden.

Die Kosten betragen Θ(n³), vergleichbar mit sequenzieller Ausführung. D.h. diese Partitionierung und Architektur ist kostenoptimal.

Das 2n x 2n Netz wird nur in drei Quadranten genutzt. Benötigt werden daher nur 3n² VEs.

Aus Sicht der Rechnerarchitektur ungünstig zu implementieren und nicht generisch, d.h. abhängig vom verwendeten Algorithmus.

Reduktion dieses Verfahrens auf n × n Netz möglich

Dazu werden die Matrizen A, B und C überlagert, d.h. VE1,1 ⇒ {A1,1,B1,1,C1,1}.

Die Zeilenelemente von A werden dann nach vorherigen Ablaufschema gegen den Uhrzeigersinn rotiert (nur horizontal), und die Spaltenelemente von B im Uhrzeigersinn (vertikal).

Man erhält gleiche asymptotische Grenzwerte für die Laufzeit Θ(n) und Kosten Θ(n³)!

Abbildung 10-14. Überlagerte Verarbeitung der Matrizen *A*, *B*, und *C* auf einem Maschennetzwerk

Maßzahlen für Parallele Systeme

Berechnungszeit

Die Berechnungszeit Tcomp (computation time) eines Algorithmus als Zeit, die für Rechenoperationen verwendet wird.

Kommunikationszeit

Die Kommunikationszeit Tcomm (communication time) eines Algorithmus als Zeit, die für den Daten- bzw. Nachrichtenaustausch (Sende- und Empfangsoperationen) zwischen Subprogrammen und Verarbeitungseinheiten verwendet wird.

Untätigkeitszeit

Die Untätigkeitszeit Tidle (idle time) eines Systems als Zeit, die mit Warten (auf zu empfangende oder sendende Nachrichten) verbracht wird → Prozessblockierung trägt zur Untätigskeitszeit bei!

Es gilt (bei N Prozessen):

image-placeholder
(10-5)

Übertragungszeit

Die Übertragunszeit Tmsg (message time) ist die Zeit, die für das Übertragen einer Nachricht mit der Länge L Datenwörter zwischen zwei Prozessen oder Prozessoren benötigt wird.

Sie setzt sich aus einer Startzeit Ts (message startup time) und einer Transferzeit Tw für ein Datenwort zusammen.

Es gilt: Tmsg = Ts + L • Tw

Voraussetzung: Verbindungsnetz arbeitet konfliktfrei.

Startzeit

Die Startzeit wird durch die Kommunikationshard- und software bestimmt, die zur Initiierung eines Datentransfers benötigt wird, z.B. Overhead des Protokollstacks bei einer Software-Implementierung.

Transferzeit

Die Transferzeit wird durch die Bandbreite des Kommunikationsmediums und zusätzlich bei Software-Implementierung durch den Protokollstack (Datenkopie) bestimmt.

Parallelisierungsgrad P

Die maximalze Anzahl von binären Stellen (bits) pro Zeiteinheit (Taktzyklus) die von einer Datenverarbeitungsanlage verarbeitet werden kann.

Es gilt: P = W • B

Wortlänge W

Die Wortlänge oder Wortbreite gibt die Anzahl der Bits eines Datenpfades an.

Bitslice-Länge B

Die Bitslice-Länge setzt sich zusammen aus der Anzahl von Verarbeitungseinheiten VE, die parallel ausgeführt werden können, und der Anzahl der Pipeline-Stufen einer VE.

Es gilt: B = NVE • NStages

Abbildung 10-15. Illustration Parallelisierungsgrad und Beispiel

Beschleunigung S und Kosten C

Die Beschleunigung gibt die Steigerung der Verabeitungsgeschwindigkeit bzw. die Re-duzierung der Verarbeitungszeit T an beim Übergang Anzahl Prozessoren N=1 → N>1. Die Kosten C skaliert die Verarbeitungszeit (Komplexitätsklasse) mit den Ressourcen.

image-placeholder
(10-6)

Effizienz E

Die Effizienz gibt die relative Verbesserung in der Verarbeitungsgeschwindigkeit an, da die Leistungssteigerung S mit der Anzahl der Prozessoren normiert wird.

image-placeholder
(10-7)

Mehraufwand R

Bezieht sich auf die Anzahl X der auszuführenden (Einheits-)Operationen des Programms:

image-placeholder
(10-8)

Parallelindex I

Der Parallelindex gibt die Anzahl der parallelen Operationen pro Zeit-/Takteinheit an.

image-placeholder
(10-9)

Auslastung U

Entspricht dem normierten Parallelindex:

image-placeholder
(10-10)

Beispiel zur Auslastung

Ein Einprozessorsystem benötigt für die Ausführung von 1000 Operationen genau 1000 (Takt-)Schritte. Ein Multiprozessorsystem mit 4 Prozessoren benötigt dafür 1200 Operationen, die aber insgesamt in 400 Schritten ausgeführt werden können:

X(1)=1000 und T(1)=1000, X(4)=1200 und T(4)=400
S(4)=2.5 und E(4)=0.625,I(4)=3 und U(4)=0.75

Im Mittel sind 3 Prozessoren gleichzeitig aktiv, da jeder Prozessor nur zu 75% ausgelastet ist!

Amdahl’s Gesetz

Eine kleine Zahl von sequenziellen Operationen kann den Performanzgewinn durch Parallelisierung signifikant reduzieren.

Sequenzieller Anteil der Berechnungszeit T eines Algorithmus in [%]: η

Paralleler Anteil dann: (1-η)

Kommunikation (Synchronisation) zwischen nebenläufig ausgeführten Tasks oder Verarbeitungseinheiten verursacht immer η>0!

Beispiel: Schutz einer geteilten Ressource mit einer Mutex.

Beispiel: Datenverteilung über eine Queue

Zugriff auf geteilte Ressourcen verursacht immer η>0!

Beispiel: Geteilte Ressource Hauptspeicher in einer PRAM

Der Kommunikationsanteil ist schwer im Voraus abzuschätzen, und der genaue Wert hängt auch von temporalen Konkurrenzverhalten ab (wie häufig gibt es verlorene Wettbewerbe)!

Das Amdahlsche gesetzt gilt nur für Probleme mit fester Größe!

Es gilt dann für die gesamte Berechnungszeit eines parallelen Systems:

image-placeholder
(10-11)

Daraus lässt sich eine Obergrenze der Beschleunigung S mit zusätzlicher Abhängigkeit von η ableiten:

image-placeholder
(10-12)

Beispiel

Ein Algorithmus mit einem sequenziellen Anteil von η=10% und einem parallelen Teil von 90% wird A.) mit N=10 Prozessoren, und B.) mit N=20 Prozessoren ausgeführt. Die Obergrenze der Beschleunigung S ist dann:

A.) S(10)=5.26
B.) S(20)=6.0

Verdopplung der Prozessoren erhöht nicht mehr signifikant die Beschleunigung!

(Berechnung)

Abbildung 10-16. Beschleunigung *S* in Abhängigkeit von η und Anzahl der Prozessoren *N*

Simulation eines einfachen Systems

Abbildung 10-17. Simulation der Beschleunigung *S* in Abhängigkeit des Kommunikationsanteils η% bei *N* Prozessen und einem vollständigen Kommunikationsnetzwerkgraphen *N*:*N*

Gustafson's Gesetz

Amdahl's Gesetzt gilt bei Problemen mit fest vorgegebener Größe (also z.B. die Größe einer Matrix)

Für verteiltes Rechnen mit N > 1000 eine Katastrophe!

Aber die theoretische Begrenzung der Beschleunigung S gilt so nicht mehr für Probleme die mitwachsen

Einfach ausgedrückt: Die Hinzunahme von Prozessoren bei zunehmender Größe des Problems bringt i.A. einen Vorteil!

Es kann (min.) zwei Motivationen geben:

Die Rechenzeit soll effizient und wirtschaftlich reduziert werden

Die Rechenzeit soll beim Anwachsen des Problems (z.B. die Anzahl von WEB Seiten die eine Suchmaschine indizieren soll) nicht anwachsen (egal was es kostet, oder noch mit vertretbaren Kostenaufwand)!

Geschichte

[C]

In einer Konferenzdebatte von 1967 über die Verdienste von Parallelen Rechnen, IBM's Gene Amdahl argumentiert, dass ein wesentlicher Anteil der Arbeit von Computern inhärent seriell ist, sowohl aus algorithmischen als auch aus architektonischen Gründen.

Er schätzte die serielle Fraktion f auf etwa 0.25-0.45. Er behauptete, dass dies den Ansatz stark einschränken würde parallele Verarbeitung zur Reduzierung der Ausführungszeit einzusetzen.

Amdahl argumentierte, dass selbst die Verwendung von zwei Prozessoren weniger kosteneffektiv als ein serieller Prozessor. Außerdem, die Verwendung einer großen Anzahl von Prozessoren würde niemals die Ausführungszeit um mehr als 1/f reduzieren, was durch seine Schätzung ein Faktor von etwa 2-4 war.

Trotz vieler Bemühungen, einen Fehler in Amdahls Gesetz zu finden, ist Amdahls Gesetz seit über 20 Jahren die Begründung für die fortgesetzte Verwendung von seriellem Rechnern und seriellen Programmiermodellen.

Die Zeit die ein Nutzer auf eine Berechnung warten will sei konstant (Einheitswert, P=1)

Der Anteil der Berechnung der seriell ist sei f, und unabhängig von der Parallelisierung (Stimmt das wirklich??)

Der serielle Anteil kann mit zunehmender Problemgröße (relativ!) abnehmen!

Der verbleibende Anteil 1-f parallelisiert ideal so dass ein serieller Prozessor P mal länger braucht um diesen zu berechnen (P: Anzahl der Prozessoren)

Das Verhältnis der parallelen zur seriellen Berechnung ist dann:

image-placeholder
(10-13)

Abbildung 10-18. Vergleich paralleler zu serieller Berechnung [C]

Abbildung 10-19. (a) Beschleunigung *S* möglich mit 32 Prozessoren in Abhängigkeit vom parallelen Anteil, Gustafson’s vs Amdahl’s Gesetz (b) Verschiedene Skalierungstypen und Kommunikationskosten sowie Randbedingungen[] [C]

Zusammenfassung

Parallele Programme können sich auf unterschiedliche Weise entwickeln. Zustandsraum Diagramme verdeutlichen die möglichen Entwicklungen von parallelen Systemen.

Es gibt eine Vielzahl von metrischen Größen um parallele und verteilte Systeme messbar und vergleichbar zu machen → Beschleunigung.

Es können Fehler in parallelen Systemen durch Wettrennen und Wettbewerbe auftreten: Deadlock, Starvation

Kommunikation ist der limitierende Faktor in der Parallelisierung.

Verteile Systeme: Synchronisation und Gruppenkommunikation

Übergang von eng zu lose gekoppelten Systemen

Wo liegen die Unterschiede in der Prozesskommunikation zu eng gekoppelten SM Systemen?

Wie geschieht die Synchronisation bei Fehlern und Asynchronität?

Map & Reduce

Ein Web-Programmiermodell für die skalierbare Datenverarbeitung in großen Clustern über große Datenmengen basierend auf impliziter Master-Worker Gruppenkommunikation (aber via peer-to-peer Nachrichten).

Das Modell wird häufig in Web-Scale-Search- und Cloud-Computing-Anwendungen eingesetzt.

Aber auch funktionale und parallele Programmierung macht von MapReduce Methoden Gebrauch

Methode:

Es wird eine Map-Funktion angegeben, um eine Gruppe von Schlüssel/Wert-Zwischenpaaren zu generieren.

Dann wird eine Reduce-Funktion auf diesen Paaren angewendet, um alle Zwischenwerte mit demselben Zwischenschlüssel zusammenzuführen.

MapReduce ist hochgradig skalierbar, um hohe Parallelitätsgrade auf verschiedenen Arbeitsebenen zu erreichen.

Ein typischer MapReduce-Berechnungsprozess kann Terabytes an Daten auf Zehntausenden oder mehr Client-Computern verarbeiten. Hunderte von MapReduce-Programmen können gleichzeitig ausgeführt werden.

Tatsächlich werden jeden Tag Tausende von MapReduce-Jobs in Clustern von Google ausgeführt.

Das Hadoop Framework bietet für WEB Anwendungen MapReduce Services an → Master-Slave Architektur!

Die Map-Funktion verarbeitet ein Paar (Schlüssel, Wert) und gibt eine Liste von Zwischenpaaren (Schlüssel, Wert) zurück:

image-placeholder
(11-1)

Die Reduzierungsfunktion führt alle Zwischenwerte zusammen, die die gleichen Zwischenschlüssel haben:

image-placeholder
(11-2)

Abbildung 11-1. Ausführungsphasen einer generischen MapReduce Applikation

MapReduce Phasen

Ein Master-Prozess erhält einen Jobdeskriptor, der den auszuführenden MapReduce-Job angibt. Der Jobdeskriptor enthält neben anderen Informationen den Ort der Eingabedaten, auf die unter Verwendung eines verteilten Dateisystems zugegriffen werden kann.

Gemäß dem Jobdeskriptor startet der Master eine Anzahl von Mapper- und Reducer-Prozessen auf verschiedenen Maschinen. Gleichzeitig startet es einen Prozess, der die Eingabedaten von seinem Speicherort liest, diese Daten in eine Gruppe von Aufteilungen unterteilt und diese Aufteilungen an verschiedene Zuordner verteilt.

Nach dem Empfang seiner Datenpartition führt jeder Zuordnungsvorgang die Zuordnungsfunktion aus (die als Teil des Jobdeskriptors bereitgestellt wird), um eine Liste von Zwischenschlüssel / Wert-Paaren zu erzeugen. Dann werden diese Paare auf der Basis ihrer Schlüssel gruppiert.

Alle Paare mit den gleichen Schlüsseln sind dem gleichen Reduziervorgang zugeordnet. Daher führt jeder Reduzierprozess die Reduktionsfunktion (definiert durch den Jobdeskriptor) aus, die alle Werte vereinigt, die mit dem gleichen Schlüssel assoziiert sind, um einen möglicherweise kleineren Satz von Werten zu erzeugen.

Dann werden die von jedem Reduktionsprozess erzeugten Ergebnisse gesammelt und an einen durch den Jobdeskriptor spezifizierten Ort geliefert, um die endgültigen Ausgabedaten zu bilden.

Beispiel

local options = {workers = 2}
local data = {34,35,36,37,38,39,40,41}

local function worker (id,set)
  local results = T{}
  for i = 1,#set do
    results:push(fib(set[i]))
  end
  return results
end
-- Parallel Processing
local Parallel = require('parallel')
local p = Parallel:new(data,options)
function sum (x,y) return x+y  end
p:time():
  map(worker):
  apply(function (r) print(r:print()) end):
  reduce(sum):
  apply(print):
  time()

Gruppenkommunikation

Die bisherigen Synchronisationsmethoden basierten auf einem sicheren Lock Objekt und Master-Worker Hierarchien

Verteilte Systeme sind i.A. strikt asynchron und können nicht direkt synchronisiert werden

Der verteile mutuale Ausschluss ist zentrales Problem in verteilten Systemen

In verteilten Systemen kann es lose gekoppelte Gruppen aus Prozessen geben und es muss zunächst ein Master/Leader gewählt werden!

MPI

Message Passing Interface: MPI

Ziele und Eigenschaften

Anwendungsprogrammierschnittstelle (nicht unbedingt für Compiler oder eine Systemimplementierungsbibliothek).

Effiziente Kommunikation:

Vermeidung von Arbeitsspeicher-Arbeitsspeicher Kopien

Überlappung von Berechnung und Kommunikation

Auslagerung auf Kommunikations-Koprozessoren, soweit verfügbar.

Implementierungen, die in einer heterogenen Umgebung verwendet werden können (verschiedene Hostplattformen).

Einfache Einbindung in Programmiersprachen und Bibliotheken und Plattformunabhängigkeit

Zuverlässige Kommunikation: Nutzer/Programmierer muss sich nicht um Kommunikationsfehler kümmern

API

Point-to-point communication,

Datatypes,

Collective operations,

Process groups,

Communication contexts,

Process topologies,

Environmental management and inquiry,

The Info object,

Process creation and management,

One-sided communication,

External interfaces,

Parallel file I/O,

Operationen

Communicator

Kommunikationswelt mit einer Gruppe aus Prozessen die gemeinsam Nachrichten austauschen können

Nachrichten können nur innerhalb der Kommunikationswelt ausgetauscht werden

MPI_COMM_WORLD ist die Standardwelt

Rank (Rang)

Einheitliche Prozessnummer innerhalb einer Kommunikationswelt

Werden vom System bei der Initialisierung vergeben und werden fortlaufend ab 0 nummeriert

Rank IDs werden bei der Kommunikation zur Identifikation von Empfänger und Sender verwendet (Kommunikationsendpunkte)

Rank IDs dienen zur Programmdifferenzierung (if rank==0 then do this else do that)

Point-to-Point Kommunikation

Kommunikation zwischen zwei Prozessen

Quellprozess sendet eine Nachricht (Typ, Daten) an einen Zielprozess unter Angabe der Rank ID

Kommunikation kann nur innerhalb eines Communicators stattfinden

MPI.send(dest:number,message:{type:string,content:string})

Damit der Zielprozess die Nachricht empfangen kann muss er einen Handler für den entsprechenden Nachrichtentyp einrichten:

MPI.recv(type:string,callback:function (message))

Broadcast Kommunikation

Ein Quellprozess kann eine Nachricht an alle Prozesse innerhalb eines Communicators senden

MPI.broadcast(message:{type:string,content:string})

RPC

Remote Procedure Call Interface

Ähnlich MPI

Klienten-Server Architektur

Es gibt drei Operationen:

getreq → Server; Auf eine Anfrage warten

putrep → Server: Eine Annfrage beantworten

trans → Klient: Eine Anfrage senden und auf Antwort warten

LUA API (CSP)

Die Kommmunikation findet über das IP-UDP/TCP Protokoll statt.

Daten werden serialisiert und es können beliebige Daten übertragen werden (inkl. seitenfreier Funktionen)

Rpc(options?:{}) → rpc

Erzeugt eine RPC Instanz (für Klient und Server)

rpc:getreq(ip:string,port:number,callback:function (req) → rep)

Server Handlerfunktion (putrep wird implizit mit dem Rückgabewert des Callbackhandlers ausgeführt)

rpc:trans(ip_string,port:number,request:\) → reply:\

Klienten Transaktion

Beispiel

// Server
require('Csp')
local rpc = Rpc({verbose=2})
rpc:getreq('127.0.0.1',12345,function (req)
  if req.cmd=='iabs' then
    return {
     result=math.sqrt(math.pow(req.x,2)+
                      math.pow(req.y,2)),
     stat='OK'
    }
  else return {stat='EINVALID'} end
end)
loop.start()

// Client
require('Csp')
local rpc = Rpc({verbose=2})
local stat,reply = rpc:trans('127.0.0.1',12345,
                             {cmd='iabs',x=1,y=2})
print(reply)

Tupelräume

Tupel-Räume stellen ein assoziiertes Shared-Memory-Modell dar, wobei die gemeinsam genutzten Daten als Objekte mit einer Reihe von Operationen betrachtet werden, die den Zugriff der Datenobjekte unterstützen

Tupel sind in Räumen organisiert, die als abstrakte Berechnungsumgebungen betrachtet werden können.

Ein Tupelraum verbindet verschiedene Programme, die verteilt werden können, wenn der Tupel-Space oder zumindest sein operativer Zugriff verteilt ist.

Oder: Mobile Rechner als Tupel Verteiler!

Das Tupelraum Organisations- und Zugangsmodell bietet generative Kommunikation, d.h. Datenobjekte können in einem Raum durch Prozesse mit einer Lebensdauer über das Ende des Erzeugungsprozesses hinaus gespeichert werden.

Ein bekanntes Tupelraum-Organisations- und Koordinationsparadigma ist Linda [GEL85].

Abbildung 11-2. Ein Schnappschuss eines Tupelraumes mit Tupeln und

Kommunikation von Sensorknoten über Tupelräume ist eine Koordionierungssprache.

Abbildung 11-3. Direkter Nachrichtenaustausch (a), z.B. durch Signale, im Vergleich zu generativer Kommunikation (b) und virtuelle verteilte Räume (c) durch mobile Prozesse (Sensorknoten)

Tupelräume - Datenmodell

Die Daten sind mit Tupeln organisiert.

Ein Tupel ist eine lose gekoppelte Verbindung einer beliebigen Anzahl von Werten beliebiger Art /Typ/

Ein Tupel ist ein Wert und sobald es in einem Tupelraum gespeichert ist, ist es persistent.

Tupeltypen ähneln den Datenstrukturtypen, sie sind jedoch dynamisch und können zur Laufzeit ohne statische Beschränkungen erstellt werden.

Auf die Elemente von Tupeln kann nicht direkt zugegriffen werden, was üblicherweise Mustererkennung und musterbasierte Dekomposition erfordert, im Gegensatz zu Datenstrukturtypen, die einen benannten Zugriff auf Feldelemente bieten, obwohl die Behandlung von Tupeln als Arrays oder Listen diese Beschränkung lösen kann.

Ein Tupel mit n Feldern heißt n-stellig und wird in der Notation <v₁, v₂, ..> angegeben.

Beispiele von Tupel

<'SENSOR',1000>
<'SENSOR2',[10,100,2]>
<1,3,5,7,11>
<'SLEEPMODE',True,2500.34>
<0,'OFF'>
<1,'ON'>

Formal werden Tupel als Vektoren durch die folgende Generierungsregel mit Werten v, Ausdrücken ε und Variablen x definiert, die als tatsächliche Parameter betrachtet werden (d.h. Variablen x, die mit Wertsemantik verwendet werden):

image-placeholder
(11-3)

Tupelwerte erfordern einen Mustervergleich basierend auf dem Vorlagenmuster mit der folgenden Generierungsregel, bestehend aus tatsächlichen (v, ε, x) und formalen Parametern (x?, Variablen, die mit Referenzsemantik verwendet werden):

image-placeholder
(11-4)

Ein Suchmuster kann ein Wildcard (⊥) anstelle von formalen Parametern verwenden.

Jedes Tupel t hat eine Typsignatur Sig (t) = St = <T₁; T₂; ...; Tn>, ein Tupel mit der gleichen Stelligkeit wie t, das den Typ jedes Tupelfeldes angibt.

Ein Tupel kann nur durch seine Verknüpfung mit Templates p angesprochen werden.

Tupel Räume - Datenmodell

Üblicherweise wird das erste Feld eines Tupels als symbolischer Schlüssel behandelt, der eine Tupelunterklasse identifiziert, indem Textzeichenfolgen oder aufgezählte symbolische Konstantenwerte verwendet werden.

Mustersuche

Sei t = <d₁, d₂, .., dn> ein Tupel, p = <dt₁, dt₂, .., dtm> eine Vorlage; dann wird t durch p abgedeckt (bezeichnet durch match (t, p) = true), wenn die folgenden Bedingungen gelten: (i) m = n. (ii) ∀ dti = di oder dti = ⊥, 1 ≤ i ≤ n. Bedingung (1) prüft, ob t und p die gleiche Stelligkeit haben, während (2) prüft, ob jedes Nicht-Wildcard-Feld von p gleich ist dem entsprechenden Feld von t.

Mustersuche

Tupelräume - Operationale Semantik

Es gibt eine Reihe von Operationen, die von Prozessen angewendet werden können, bestehend aus

einer Reihe reiner Datenzugriffsoperationen, die Tupel als passive Datenobjekte behandeln,

und Operationen, die Tupel als eine Art von aktiven Rechenobjekten behandeln (genauer gesagt, zu berechnende Daten).

RPC-Semantik (Remote Procedure Call).

out(t)

Die Ausführung der Ausgabeoperation fügt das Tupel t in den Tupelraum ein. Mehrere Kopien desselben Tupelwerts können eingefügt werden, indem die Ausgabeoperation iterativ angewendet wird. Die gleichen Tupel können nach dem Einfügen in den Tupelraum nicht unterschieden werden.

Beispiel: out("Sensor",1,100); out("Sensor",2,121);

inp(p)

Die Ausführung der Eingabeoperation entfernt ein Tupel t aus dem Tupelraum, der der Mustervorlage p entspricht. Wenn kein passendes Tupel gefunden wird führt das zu einer Blockierung des aufrufenden Prozesses bis ein passendes Tupel eingestellt wird.

Beispiel: inp("Sensor",1,s1?); inp("Sensor",i?,s?);

rd(p)

Die Ausführung der Leseoperation gibt eine Kopie eines Tupels t zurück, dass der Vorlage p entspricht, entfernt sie jedoch nicht. Wenn kein passendes Tupel gefunden wird führt das zu einer Blockierung des aufrufenden Prozesses bis ein passendes Tupel eingestellt wird.

Beispiele: rd("Sensor",1,s1?); rd("Sensor",i?,s?);

inp?(p), rd?(p)

Nichtblockierende Version von inp/rd. Wird kein passendes Tupel gefunden wird die Operation ergebnislos terminiert.

Beispiel: res:=inp?('SENSOR',a?,b?);

inpw?(tmo,p), rdw?(tmo,p)

Teilblockierende Version von inp/rd, Wird einer Zeit von tmo kein passendes Tupel gefunden wird die Operation abgebrochen.

Beispiel: res:=inpw?(1000,'SENSOR',a?,b?);

Die Verwendung von zeitlich unbegrenzt blockierenden Operationen kann unter Betrachtung der Lebendigkeit von Agenten nachteilig sein. Daher sollte immer eine zeitliche Begrenzung und anschließende Abfrage des Operationsstatus erfolgen (abgebrochen?)

test(t), testandset(p,function (t)→t)

Nicht blockierender Test eines Tupels und atomare Veränderung eines Tupels, dass der Vorlage p entspricht. Das zweite Argument ist eine Abbildungsfunktion. Das Ergebnistupel ersetzt das ursprüngliche.

Markierungen

Tupel sind persistent und können für immer in einem Tupelraum verbleiben!

Daher ist die Verwendung von Markierungen häufig sinnvoll.

Eine Markierung ist ein Tupel mit einer Lebenszeit τ

Nach Ablauf der Lebenszeit wird das Tupel - sofern es nicht entfernt wurde - durch einen Garbagecollector entfernt.

image-placeholder
(11-5)

mark(tmo,t)

Ausgabe eines Tupels t mit einer Lebenszeit τ (im Tupelraum).

Tupelräume - Synchronisationsmodell

Es gibt Produzenten- (Generator) und Verbraucherprozesse.

Ein Produzent erzeugt ein Tupel, das von einem Konsumentenprozess entfernt werden kann.

Die Tupelausgabeoperation endet unmittelbar (asynchron), alternativ nachdem das Tupel im Tupelraum gespeichert wurde (synchron).

Ein Verbraucher-Prozess wird blockiert, wenn die Anfrage nicht bearbeitet werden kann, wenn im Tupel-Bereich tatsächlich kein passendes Tupel vorhanden ist.

Nachdem ein übereinstimmendes Tupel im Tupelraum gespeichert wurde, wird es sofort einen der wartenden Verbraucherprozesse zugewiesen.

Daher ist die Eingabeoperation immer synchron. Einzige Ausnahme sind die nicht permanent blockierenden Versionen, die das Warten auf eine obere Zeitgrenze begrenzen (Timeout).

Es gibt keine anfängliche zeitliche Anordnung von Erzeuger- und Verbraucheroperationen.

Tupelräume - Beispiele von Operationen in Lua

out({'SENSOR',10,20});
out({'SENSOR',9,23{);
out({'PI',3,14{);
out({'DATA',{1,2,3,4}});
result = inp({'SENSOR',nil,nil});
>> { 'SENSOR', 9, 23 }
result = inp({'SENSOR',nil,nil});
>> { 'SENSOR', 10, 20 }
inp({'SENSOR',nil,nil});
>> nil
rd({nil,nil})
>> { 'DATA', { 1, 2, 3, 4 } }
rd({nil,nil,nil,nil},100)
>> nil -- Timeout

Sicherheit und Lebendigkeit

Ein Algorithmus, z.B. die Wahl eines Leaders in einer Prozessgruppe, gelte als sicher wenn maximal ein Leader unter allen Umständen gewählt wird. Dies ist auch der Fall wenn einzelne Prozesse der Prozessgruppe fehlerhaft sind (nicht erreichbar sind oder terminiert sind).

Ein Algorithmus, z.B. die Wahl eines Leaders in einer Prozessgruppe, gelte als lebendig wenn irgendwann mindestens ein Leader unter allen Umständen gewählt wird.

Robustheit und Fehler

Angenommen eine Prozessgruppe bestehe aus N Prozessen die in einem Netzwerk verteilt sind.

Die Netzwerkknoten sind miteinander verbunden.

Nun wird aufgrund einer technischen Störung das Netzwerk partitioniert (z.B. in zwei getrennte Bereiche geteilt).

Der verteilte Algorithmus wird in jeder der Partitionen unabhängig arbeiten. Dann ist das verteilte System zwar noch lebendig (es werden unabhängig zwei Leader in den Gruppenpartitionen gewählt), aber nicht mehr sicher !!!!

Die Invariante des Algorithmus ist verletzt worden durch Ausfall/Störung!

Abbildung 11-4. Leaderelection: Eine ursprünglich zusammenhängende Gruppe wird durch Netzwerkpartitionierung (Störung der Kommunikation) zweigeteilt und es werden jetzt zwei Leader gewählt!

Mutualer Ausschluss

Verteilter Algorithmus nach Lamport

LA1: Um einen kritischen Bereich zu erlangen (Mutex Acquire), sendet ein Prozess eine zeitgestempelte Anforderung an jeden anderen Prozess im System und fügt die Anforderung auch in seiner lokalen Queue Q hinzu.

LA2: Wenn ein Prozess eine Anforderung empfängt, wird sie in Q platziert. Wenn sich der Prozess nicht in seinem CS befindet, sendet er eine zeitgestempelte Bestätigung an den Absender. Andernfalls wird das Senden der Bestätigung bis zum Verlassen des CS verzögert (Mutex Release).

LA3: Ein Prozess tritt in seinen CS ein, wenn (1) seine Anfrage vor allen anderen Anfragen (d.h. der Zeitstempel seiner eigenen Anfrage ist kleiner als die Zeitstempel aller anderen Anfragen) in seinem lokalen Q angeordnet ist und (2) Es hat die Antworten von jedem anderen Prozess als Antwort auf seine aktuelle Anfrage erhalten.

LA4: Um die CS zu verlassen, löscht ein Prozess (1) die Anfrage von seiner lokalen Warteschlange Q und (2) sendet eine zeitgestempelte Freigabenachricht an alle anderen Prozesse.

LA5: Wenn ein Prozess eine Freigabenachricht erhält, entfernt er die entsprechende Anforderung aus seiner lokalen Warteschlange Q.

Verteilter Algorithmus nach Ricart–Agrawala’

Verbesserte Version

RA1: Jeder Prozess, der den Eintritt in seinen CS anfordert (Mutex Acquire), sendet eine zeitgestempelte Anfrage an jeden anderen Prozess im System.

RA2: Ein Prozess, der eine Anforderung empfängt, sendet eine Bestätigung an den Absender zurück, nur wenn

(1) der Prozess nicht an dem Eintritt in seinen CS interessiert ist (Mutex Acquire) oder

(2) der Prozess versucht, seine CS zu erlangen, aber sein Zeitstempel größer ist als der des Absenders.

Wenn sich der Prozess bereits in seinem CS befindet (besitzt den Lock) oder sein Zeitstempel kleiner als der des Absenders ist, puffert er alle Anforderungen bis zum Verlassen des CS.

RA3: Ein Prozess tritt in seine CS ein, wenn er von jedem der verbleibenden (n-1) Prozesse eine Bestätigung erhält.

RA4: Nach dem Verlassen seiner CS muss ein Prozess eine Rückmeldung an jede der ausstehenden Anfragen senden, bevor er eine neue Anfrage macht oder andere Aktionen ausführt.

Token Algorithmen

Eine andere Klasse verteilter mutualer Ausschlussalgorithmen verwendet das Konzept eines expliziten variablen Tokens, das als eine Erlaubnis für den Eintritt in die CS dient (Mutex Acquire) und von einem anfordernden Prozess durch das Prozesssystem weitergereicht werden kann.

Immer wenn ein Prozess in seinen CS eintreten möchte, muss er den Token erwerben. Der erste bekannte Algorithmus, der zu dieser Klasse gehört, ist auf Suzuki und Kasami zurückzuführen.

Da es nur ein Token gibt ist der mutuale Ausschluss (Sicherheit) garantiert. Die Lebendigkeit aber nicht unbedingt (Verlust des Tokens).

Abbildung 11-5. Prozess 3 hält den Token und Prozesse 1 und 4 fordern ihn (über 6 ) an; schließlich erhält ihn 4

Verteilter Konsens

Ein verteilter Konsensalgorithmus hat das Ziel in einer Gruppe von Prozessen oder Agenten eine gemeinsame Entscheidung zu treffen

Zentrale Eigenschaften:

Zustimmung/Übereinstimmung

Terminierung; Lebendigkeit und Deadlockfreiheit

Gültigkeit; Robustheit gegenüber Störungen wie fehlerhaften Nachrichten oder Ausfälle von Gruppenteilnehmern

Beim Konsens kann ein Master-Slave Konzept oder ein Gruppenkonzept mit Leader/Commander und Workern verwendet werden.

Beim Master-Slave Konzept kommunizieren nur Slaves mit dem Master

Bei Gruppenkonzept (i.A. mit einem Leader) kommunizieren auch alle Gruppenteilnehmer untereinander

Durch Störung (Fehler oder Absicht) kann es zu fehlerhaften bis hin zu fehlgeschlagenen Konsens kommen.

Bedingungen für Interaktive Konsistenz:

IC1: Jeder Worker empfängt die gleiche Anweisung vom Leader!

IC2: Wenn der Leader fehlerfrei arbeitet, dann empfängt jeder fehlerfreie Worker die Anweisung die der Leader sendete!

Byzantinisches Generalproblem

Beispiel: In einer Gruppe aus drei Prozessen/Agenten ist einer fehlerhaft bzw. versendet fehlerhafte Nachrichten (durch Störung oder Absicht) mit Anweisungen (schließlich ein Konsensergebnis) 11-7

Abbildung 11-6. Byzantinisches Generalproblem: (a) Leader 0 ist fehlerfrei, Worker 2 ist fehlerhaft (b) Leader 0 ist fehlerhaft, Worker 1 und 2 sind

Jeder Worker der Nachrichten empfängt ordnet diese nach direkten und indirekten (von Nachbarn)

Fall (a): Prozess 2 versendet fehlerhafte Nachricht mit Anweisung 0, Prozess 1 empfängt eine direkte Nachricht mit Anweisung 1 und eine indirekte mit (falschen) Inhalt Anweisung 0

Bedingung IC1 ist erfüllt. Unter Annahme von Bedingung IC2 wird Worker 1 die direkte Anweisung 1 von Prozess 0 (Commander) auswählen → Konsens wurde gefunden

Fall (b): Prozess 0 (Leader) versendet an Prozess 1 richtige Nachricht mit Anweisung 1 und falsche Nachricht mit Anweisung 0 an Prozess 1

Würde Prozess 1 wieder zur Erfüllung von IC2 eine Entscheidung treffen (Anweisung 1 auswählen), dann wäre IC1 verletzt. Wie auch immer Prozess 1 entscheidet ist entweder IC1 oder IC2 verletzt → Unentscheidbarkeit → Kein Konsens möglich

Das nicht-signierte Nachrichtenmodell erfüllt die Bedingungen:

Nachrichten werden während der Übertragung nicht verändert (aber keine harte Bedingung).

Nachrichten können verloren gehen, aber die Abwesenheit von Nachrichten kann erkannt werden.

Wenn eine Nachricht empfangen wird (oder ihre Abwesenheit erkannt wird), kennt der Empfänger die Identität des Absenders (oder des vermeintlichen Absenders bei Verlust).

Algorithmen zur Lösung des Konsensproblems müssen m fehlerhafte Prozesse annehmen (bzw. fehlerhafte Nachrichten)

Der OM(m) Algorithmus

Ein Algorithmus der einen Konsens erreicht bei Erfüllung der Bedingungen IC1 und IC2 mit bis zu m fehlerhaften Prozesse bei insgesamt n ≥ 3m+1 Prozessen mit nicht signierten ("mündlichen") Nachrichten.

Leader i sendet einen Wert v ∈ {0, 1} an jeden Worker j ≠ i. ii. Jeder Worker j akzeptiert den Wert von i als Befehl vom Leader i.

Leader i sendet einen Wert v ∈ {0, 1} an jeden Worker j ≠ i.

Wenn m > 0, dann beginnt jeder Worker j, der einen Wert vom Leader erhält, eine neue Phase, indem er ihn mit OM(m-1) an die verbleibenden Worker sendet.

In dieser Phase fungiert j als Leader.

Jeder Arbeiter erhält somit (n-1) Werte: (a) einen Wert, der direkt von dem Leader i von OM (m) empfangen wird und (b) (n-2) Werte, die indirekt von den (n-2) Workern erhalten werden, die aus ihrem Broadcast OM(m-1) resultieren.

Wird ein Wert nicht empfangen wird er durch einen Standardwert ersetzt.

Jeder Worker wählt die Mehrheit der (n-1) Werte, die er erhält, als Anweisung vom Leader i.

Algorithmus OM(m)

Abbildung 11-7. Eine Illustration von OM(1) mit vier Prozessen und einem fehlerhaften Prozess: die Nachrichten auf der oberen Ebene spiegeln die Eröffnungsnachrichten von OM(1) wider und die auf der unteren Ebene spiegeln die OM(0)-Meldungen wider, die von den Mitteilungen der oberen Ebene ausgelöst werden. (a) Prozess 3 ist fehlerhaft. (b) Prozess 0 (Leader) ist

Der Paxos Algorithmus

Paxos ist ein Algorithmus zur Implementierung von fehlertoleranten Konsensfindungen.

Er läuft auf einem vollständig verbundenen Netzwerk von n Prozessen und toleriert bis zu m Ausfälle, wobei n ≥ 2m+1 ist.

Prozesse können abstürzen und Nachrichten können verloren gehen, byzantinische Ausfälle (absichtliche Verfälschung) sind jedoch zumindest in der aktuellen Version ausgeschlossen.

Der Algorithmus löst das Konsensproblem bei Vorhandensein dieser Fehler auf einem asynchronen System von Prozessen.

Obwohl die Konsensbedingungen Zustimmung, Gültigkeit und Terminierung sind, garantiert Paxos in erster Linie die Übereinstimmung und Gültigkeit und nicht die Beendigung - es ermöglicht die Möglichkeit der Beendigung nur dann, wenn es ein ausreichend langes Intervall gibt, in dem kein Prozess das Protokoll neu startet.

Ein Prozess kann drei verschiedene Rollen wahrnehmen:

Antragsteller,

Akzeptor und

Lerner.

Abbildung 11-8. Typische Rollenverteilung beim Paxos Algorithmus

Die Antragsteller reichen die vorgeschlagenen Werte im Namen eines Initiators ein,

die Akzeptoren entscheiden über die Kandidatenwerte für die endgültige Entscheidung und

die Lernenden sammeln diese Informationen von den Akzeptoren und melden die endgültige Entscheidung dem Initiator zurück.

Ein Vorschlag, der von einem Antragsteller gesendet wird, ist ein Tupel (v, n), wobei v ein Wert und n eine Sequenznummer ist.

Wenn es nur einen Akzeptor gibt, der entscheidet, welcher Wert als Konsenswert gewählt wird, dann wäre diese Situation zu einfach. Was passiert, wenn der Akzeptor abstürzt? Um damit umzugehen, gibt es mehrere Akzeptoren.

Ein Vorschlag muss von mindestens einem Akzeptor bestätigt werden, bevor er für die endgültige Entscheidung in Frage kommt.

Die Sequenznummer wird verwendet, um zwischen aufeinander folgenden Versuchen der Protokollanwendung zu unterscheiden.

Nach Empfang eines Vorschlags mit einer größeren Sequenznummer von einem gegebenen Prozess, verwerfen Akzeptoren die Vorschläge mit niedrigeren Sequenznummern.

Schließlich akzeptiert ein Akzeptor die Entscheidung der Mehrheit.

Phasen des Paxos Algorithmus

Die Vorbereitungsphase

Jeder Antragsteller sendet einen Vorschlag (v, n) an jeden Akzeptor

Wenn n die größte Sequenznummer eines von einem Akzeptor empfangenen Vorschlags ist, dann sendet er ein ack (n, ⊥, ⊥) an seinen Vorschlager

Hat der Akzeptor einen Vorschlag mit einer Sequenznummer n' < n und einem vorgeschlagenen Wert v akzeptiert, antwortet er mit ack(n, v, n').

Aufforderung zur Annahme eines Eingabewertes

Wenn ein Antragsteller ack(n, ⊥, ⊥) von einer Mehrheit von Akzeptoren empfängt, sendet er an alle Akzeptoren accept(v, n) und fordert sie auf, diesen Wert zu akzeptieren.

Wenn ein Akzeptor in Phase 1 einen ack(n, v, n') an den Antragsteller zurücksendet, muss der Antragsteller den Wert v mit der höchsten Sequenznummer in seiner Anfrage an die Akzeptoren einbeziehen.

Ein Akzeptor akzeptiert einen Vorschlag (v, n), sofern er nicht bereits zugesagt hat, Vorschläge mit einer Sequenznummer größer als n zu berücksichtigen.

Die endgültige Entscheidung

Wenn eine Mehrheit der Akzeptoren einen vorgeschlagenen Wert akzeptiert, wird dies der endgültige Entscheidungswert. Die Akzeptoren senden den akzeptierten Wert an die Lernenden, wodurch sie feststellen können, ob ein Vorschlag von einer Mehrheit von Akzeptoren akzeptiert wurde.

Zusammenfassung

Zuverlässige und sichere Synchronisation in asynchronen Systemen mit Fehlern ist theoretisch nicht möglich!

Referenzen

Bücher

P\. S. Pacheco, An introduction to parallel programming. Elsevier, MK, 2011.

T\. Bräunl, Parallel Image Processing. Springer Berlin, 2001.

T\. Rauber and G. Rünger, Parallele und verteilte Programmierung. Springer Berlin, 2007.

G\. R. Andrews, Foundations of Multithreaded, Parallel, and Distributed Programming. Addison-Wesley, Pearson, 2000.

K\. Hwang, G. C. Fox, and J. J. Dongarra, Distributed and Cloud Computing: From Parallel Processing to the Internet of Things. Elsevier B.V., 2012.

S\. Ghosh, Distributed Systems - An Algorithmic Approach. Chapman & Hall/CRC, 2015.

D\. Talia, P. Trunfio, and F. Marozzo, Data Analysis in the Cloud. Elsevier Ltd, 2016.

S\. GUPTA, R. K. GUPTA, N. D. DUTT, and A. NICOLAU, SPARK: A Parallelizing Approach to the High-Level Synthesis of Digital Circuits. Kluwer Academic Publishers, 2004.

James E. Smith and R. Nair, Virtual Machines - Versatile Platforms for Systems and Processes. Elsevier Inc., 2005.

R\. Zurawski, Ed., Embedded systems handbook : Embedded systems design and verification. CRC Press, 2009.

D\. Padua et al., Encyclopedia of Parallel Computing

Videos

Dining Philosophers, https://www.youtube.com/watch?v=fg-NiDlcoS8

Artikel

Communications of the ACM, Vol 64, No. 3, 2021

Roberto Ierusalimschy, Luiz Henrique de Figueiredo, Waldemar Celes, The Implementation of Lua 5.0.0