Verteilte und Parallele Programmierung

Mit Virtuellen Maschinen

PD Stefan Bosse

Universität Bremen - FB Mathematik und Informatik

1 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung ::

Einführung in die verteilte und parallele Datenverarbeitung

Was unterscheidet verteilte und parallele Datenverarbeitung?

Welche Eigenschaften besitzen verteilte gegenüber parallelen Systemen?

2 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Performanz

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
3 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Performanz

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
4 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Performanz

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

5 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Performanz

Weicker, R. P. (1984) Analyse der prozentualen Verteilung von verschiedenen Anweisungen in verschiedenen Programmiersprachen

6 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Performanz

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

Ergebnisse:

7 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Terminologie

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
8 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Verteilte vs. Parallele Systeme

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
9 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Verteilte vs. Parallele Systeme

Verteilte vs. Parallele Systeme

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

10 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Verteilte vs. Parallele Systeme

Verteilte vs. Parallele Systeme

1 Taxonomie von verteilten und parallelen Systemen

11 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Verteilter Speicher

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

12 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Geteilter Speicher

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



13 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Speichermodell und Speicherarchitekturen

Speichermodell und Speicherarchitekturen

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

14 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Speicherhierarchie

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:

S(M)=s1(m1)→s2(m2)→..→sk(mk)

15 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Speicherhierarchie

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)

16 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Verteilte Systeme

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?
17 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Verteilte Systeme

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?
18 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Parallele Systeme

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)

19 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Parallele Systeme

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

20 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Parallele Systeme

Parallele Systeme

  • 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)

21 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Parallele Systeme

Parallele Systeme

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!
22 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Parallele Systeme

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

23 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Parallele Systeme

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

24 / 37

PD Stefan Bosse - VPP - Einführung in die verteilte und parallele Datenverarbeitung :: Konkurrenz (Wettbewerb)

Konkurrenz (Wettbewerb)

  • Es gibt eine oder mehrere geteilte Ressourcen ℝ={R1,R2,..}, 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!
25 / 37

PD Stefan Bosse - VPP - Sequenzielle Programmierung mit Lua :: Konkurrenz (Wettbewerb)

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

26 / 37

PD Stefan Bosse - VPP - Sequenzielle Programmierung mit Lua :: Lua :: Daten und Variablen

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 von lokalen Variablen und Verwendung in Anweisungen und Ausdrücken

27 / 37

PD Stefan Bosse - VPP - Sequenzielle Programmierung mit Lua :: Lua :: Daten und Variablen

Beispiele Variablen und Ausdrücke

28 / 37

PD Stefan Bosse - VPP - Sequenzielle Programmierung mit Lua :: Lua :: Funktionen

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,..)

Funktionsdefinition und Anwendung

29 / 37

PD Stefan Bosse - VPP - Sequenzielle Programmierung mit Lua :: Lua :: Funktionen

Lua :: Funktionen

  • 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)
30 / 37

PD Stefan Bosse - VPP - Sequenzielle Programmierung mit Lua :: Lua :: Funktionen

Beispiele Funktionen

31 / 37

PD Stefan Bosse - VPP - Sequenzielle Programmierung mit Lua :: Lua :: Datenstrukturen

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 = ε
32 / 37

PD Stefan Bosse - VPP - Sequenzielle Programmierung mit Lua :: Lua :: Datenstrukturen

Lua :: Datenstrukturen

  • 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"]

Lua Äquivalenz Array und Datenstruktur

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

Lua Datenobjekte

33 / 37

PD Stefan Bosse - VPP - Sequenzielle Programmierung mit Lua :: Lua :: Objekte

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.

34 / 37

PD Stefan Bosse - VPP - Sequenzielle Programmierung mit Lua :: Lua :: Objekte

Lua :: Objekte

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

Lua Objektklassen mit Definition einer Konstruktorfunktion, Objektinstanziierung, und Methodenanwendung

35 / 37

PD Stefan Bosse - VPP - Sequenzielle Programmierung mit Lua :: Lua :: Objekte

Lua :: Objekte

36 / 37

PD Stefan Bosse - VPP - Sequenzielle Programmierung mit Lua :: Zusammenfassung

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.
37 / 37