Verteilte und Parallele Programmierung

Mit Virtuellen Maschinen

PD Stefan Bosse

Universität Bremen - FB Mathematik und Informatik

1 / 27

PD Stefan Bosse - VPP - Überblick ::

Überblick

2 / 27

PD Stefan Bosse - VPP - Überblick :: Schwerpunkte in diesem Kurs

Schwerpunkte in diesem Kurs

Parallelisierung primär auf Kontrollpfadebene!

  • Grundlagen von parallelen und verteilten Systemen

  • Konzepte der parallelen und verteilten Programmierung

  • Praktische Relevanz und Anwendung

  • Plattformen und Technologien, Virtualisierung

  • Netzwerke, Nachrichten, und Protokolle (MPI,..)

3 / 27

PD Stefan Bosse - VPP - Überblick :: Schwerpunkte in diesem Kurs

Begleitet von Übungen um obige Techniken konkret anzuwenden

Vorlesung
2 SWS mit Grundlagen und Live Programming
→ Synchroner Livestream + Chat
→ Tutorial Videos
Übung
1 SWS mit Programmierung und angewandter Vertiefung → Digitale Notebooks mit Online Hilfe Funktion und Einreichungssystem
Voraussetzungen
Grundlegende Programmierfähigkeiten, Grundkenntnisse in Rechnerarchitektur und Netzwerken
4 / 27

PD Stefan Bosse - VPP - Überblick :: Zielgruppen des Kurses

Zielgruppen des Kurses

  • Informatiker, Wirtschaftsinformatiker
  • Systemingenieure (Systems Engineering)
  • Produktionstechniker und Logistiker
  • Elektrotechniker

tiridifilm/istockphoto.com

5 / 27

PD Stefan Bosse - VPP - Überblick :: Materialien

Materialien

  1. Die Vorlesungsinhalte (Skript, Folien) werden auf http://edu-9.de unter der Rubrik Lehre zusammengestellt und angeboten. Achtung: Kürzel vpp3k beachten!

  2. Weitere Materialien (Tutorials, Übungen, Software) werden ebenfalls auf http://edu-9.de bereitgestellt

  3. Es gibt einige Videos und sind über http://edu-9.de erreichbar

  4. Es gibt eine Mailing Liste (ZfN) über die aktuelle Informationen versendet werden (Updates, Ankündigungen). Eine Anmeldung ist nicht erforderlich.

6 / 27

PD Stefan Bosse - VPP - Überblick :: Leistungen

Leistungen

Folgende Möglichkeiten einer Prüfungsleistung stehen zur Auswahl:

  1. Mündliche Prüfung

  2. Schriftliche Ausarbeitung zu einer Fragestellung zu dem Thema (Review/Survey)

  3. Die Bearbeitung einer experimentellen Arbeit (Lua) mit kleiner schriftlicher Arbeit (Dokumentation)

7 / 27

PD Stefan Bosse - VPP - Überblick :: Literatur

Literatur

Vorlesungsskript und Folien
Die Inhalte der Vorlesung werden sukzessive bereitgestellt (HTML, PDF, EPUB Format)
Concurrent Programming: Algorithms, Principles, and Foundations
Michel Raynal, Springer 2013, ISBN 978-3-642-320626-2

Parallel Image Processing
T. Bräunl, Springer Berlin, 2001




8 / 27

PD Stefan Bosse - VPP - Überblick :: Literatur

Literatur

An introduction to Parallel Programming
P. S. Pacheco, Elsevier, MK, 2011.

Lua Scripting Language
Tutorial Points, K. K. Panigrahi, 2016.


9 / 27

PD Stefan Bosse - VPP - Überblick :: Software

Software

LuaJit

  • LuaJit Virtual Machine ⇒ Kernelkomponente von Michael Pall (luajit.org)
  • Integrierte Bytecode und native code just-in-time Compiler
  • Parallele Ausführung in Threads möglich durch Kapselung (keine globalen Variablen)
  • Mittlere Performanz im Vergleich zu Google V8/nodejs, hohe Performanz im Vergleich zu Python

Fengari VM

  • JavaScript Implementierung von Lua (C)
  • Kann mit jedem Web Browser und mit Node Webkit (nw.js) ausgeführt werden
  • Parallele Ausführung in Web Workern möglich, ggfs. mit Shared Memory
  • Niedrige Performanz (aber vergleichbar mit Python VM)
10 / 27

PD Stefan Bosse - VPP - Überblick :: Software

Software

lvm

edu-9.de

  • LuaJit VM mit Multithreading
  • Ausführung von der Kommandozeile
  • Wird auch für Live Programming und mit Digitalen Notebooks genutzt
  • Einsatz auf verschiedenen Hostplattformen : PC, Smartphone, Embedded PC, Server, ..
  • Einsatz auf Betriebssystemen: Windows, Linux, Solaris, MacOS, Android
> lvm parfib.lua
Thread [fe5af458:4] released
Thread [fe5afa00:5] released
{ 
  1 = 9227465,
  2 = 24157817,
  3 = 63245986,
  4 = 165580141,
  5 = 14930352,
  6 = 39088169,
  7 = 102334155,
  8 = 267914296,
}
686478381
Time 6235 ms
Ausführung Kommandozeile
11 / 27

PD Stefan Bosse - VPP - Überblick :: Software (Optional)

Software (Optional)

LuaOS Web IDE

  • Beinhaltet ein kleines LuaOS und die Fengari Lua VM
  • Multithreading durch Verwendung von Web Workern
  • Schnittstelle zu externen lvm Instanzen vie weblvm REST API

VNetOS Web IDE

  • Beinhaltet das LuaOS und die Fengari Lua VM
  • Aufbau von virtuellen Netzwerken
  • Einbindung von externen lvm Instanzen möglich

12 / 27

PD Stefan Bosse - VPP - Überblick :: Software (Bilbiotheken)

Software (Bilbiotheken)

parallel.lua (In lvm bereits integriert)

edu-9.de

  • Programmierung in Lua
  • Bibliothek für parallele und verteilte Systeme
  • Einfach zu Erlernen
  • Benötigt die LuaJit VM lvm 
require('parallel')
local function worker (id,set)
  local results = T{}
  for i = 1,#set do
    results:push(fib(set[i]))
  end
  return results
local data = {34,35,36,37,38,39,40,41}
local p = Parallel:new(data,options)
p:time():
  map(worker):
  reduce(sum):
  apply(print):
  time()
Programmcode
13 / 27

PD Stefan Bosse - VPP - Überblick :: Software (Bilbiotheken)

Software (Bilbiotheken)

csp.lua (In lvm bereits integriert)

edu-9.de

  • Programmierung in Lua
  • Bibliothek für Konkurrierende Parallele Programmierung mit Shared Memory
  • API entspricht erweiterten CCSP Modell
  • Einfach zu Erlernen
  • Benötigt die Lua VM lvm (integriert)
require('Csp')
Par({
  function (pid) 
    local x=ch1.read();
    ch2.write(fib(x))
  end,
  function (pid)
    Seq({
      function () .. end,
      function () .. end
    }) 
  end
  function (pid)  Seq({..}) end
},{ ch1:Channel(1), ch2:Channel(1))
Programmcode
14 / 27

PD Stefan Bosse - VPP - Überblick :: Software

Software

rpc.lua

edu-9.de

  • Programmierung in Lua
  • Bibliothek für Remote Procedure Call Kommunikation
  • Aufbau von verteilten Systemen
  • Einfach zu Erlernen
  • Benötigt die Lua VM lvm
local rpc = Rpc({verbose=2})
rpc:getreq('127.0.0.1',12345,function (req)
  print(req)
  return {
   result=req.x+req.y,
   stat='OK'
  }
end)
local stat,reply = 
  rpc:trans('127.0.0.1',12345,
            {x=1,y=2})
print(reply)
Programmcode
15 / 27

PD Stefan Bosse - VPP - Überblick :: Konzept

Konzept

16 / 27

PD Stefan Bosse - VPP - Überblick :: Ziele

Ziele

  1. Verständnis der Grundprinzipien und Architekturen verteilter (VS) und paralleler Systeme (PS) und Fähigkeit zum Transfer auf technische Systeme;
  2. Verständnis und Fähigkeit der programmatischen Anwendung von Synchronisation und Kommunikation in VS und PS;
  3. Verständnis der Probleme und dem Betrieb von parallelen Systemen im Vergleich zu sequenziellen Systemen bezüglich Effizienz, Blockierung, Skalierung, Ressourcenbedarf sowie Fehler wie Verklemmung (Deadlocks);
  4. Praktische Kenntnisse der Programmierung von PS und VS anhand von Programmierübungen mit Lua und (p)lvm (LuaJit);
  5. Erkenntnisse der Grenzen und Möglichkeiten der Parallelisierung und Verteilung und die Fähigkeit effiziente Systeme zu entwickeln → Virtuelle Maschinen!
  6. Vorbereitung für Methoden und zukunftige Trends im Cloud Computing und Internet der Dinge (praktisch: Raspberry PI).
17 / 27

PD Stefan Bosse - VPP - Überblick :: Inhalte

Inhalte

  1. Parallele und Verteilte Systeme, Zelluläre Automaten
  2. Sequenzielle und Parallele Datenverarbeitung
  3. Funktionale, Sequenzielle, und Parallele Komposition
  4. Prozessmodelle, Kontroll- und Datenpfade, Petri-Netze
  5. Kommunizierende Prozesse, Synchronisation und Kommunikation (Primitiven)
  6. Virtuelle Maschinen: Architekturen, Programmverarbeitung, Speichermanagement
  7. Praktische Parallele Programmierung mit Lua und csp.lua/parallel.lua
  8. Praktische Verteilte Programmierung mit Lua und rpc.lua/parallel.lua
  9. Verteilung und Parallelisierung: Methoden und Algorithmen
  10. Netzwerke und Nachrichrenaustausch
  11. Plattformen und Architekturen: Multiprozessor, Cluster, Cloud, IoT, GPU
  12. Gruppenkommunikation, Konsens, Distributed Shared Memory...
18 / 27

PD Stefan Bosse - VPP - Überblick :: Virtuelle Maschinen

Virtuelle Maschinen

  • Die Verwendung von virtuellen Maschinen nimmt in der Datenverarbeitung immer mehr zu (Skriptverarbeitung und Abstraktion)
  • Ein Schwerpunkt liegt in der Parallelisierung in und mit virtuellen Maschinen
  • Vor allem Parallelität auf Kontrollpfadebene und kommunizierende Systeme sollen betrachtet werden!
local s = {Semaphore(1),Semaphore(1),Semaphore(1)}
local b = Barrier(3)
Par({
  function () b:await(); for i = 1,10 do
    s[1]:down(); s[2].down(); eat(); s[2]:up(); s[1]:up(); think() 
  end end,
  function () b:await(); for i = 1,10 do
    s[2]:down(); s[3]:down(); eat(); s[3]:up(); s[2]:up(); think() 
  end end,
  function () b:await(); for i = 1,10 do
    s[3]:down(); s[1]:down(); eat(); s[1]:up(); s[3]:up(); think()
  end end
})
print('Done.')
19 / 27

PD Stefan Bosse - VPP - Überblick :: Virtuelle Maschinen und Interpreter

Virtuelle Maschinen und Interpreter

Interpreter Zyklus: Editieren → Übersetzen → Ausführen

20 / 27

PD Stefan Bosse - VPP - Überblick :: Just-in-Time Compiler

Just-in-Time Compiler

Interpreter können im wesentlichen auf drei Arten (Architekturklassen) implementiert werden:

  1. Direkte Ausführung des Quelltextes (die Nutzereingabe und bereits geschriebene Skripte) (Parse → Execute)

  2. Virtuelle Maschine und Übersetzung des Quelltextes in eine Zwischenrepräsentation die von einer virtuellen Maschine ausgeführt werden kann → Bytecode

  3. Virtuelle Maschine mit Bytecode Übersetzung, Ausführung des Bytecodes, und ausgewählter Übersetzung des Bytecodes in nativen Maschinencode → JIT Compiler!

21 / 27

PD Stefan Bosse - VPP - Überblick :: Just-in-Time Compiler

Virtuelle Maschine: Virtualisierung ≡ Abstraktion und Automatisches Speichermanagement

Beispiele

  • BASIC: Klasse 1
  • Python: Klasse 2 (Bytecode)
  • JavaScript: Klasse 2 (Spidermonkey, WEB Browser) und Klasse 3 (Google Chrome/V8, nodejs)
  • OCaML: Klasse 2 (und native Codeerzeugung mit Compiler)
  • Lua: Klasse 2 (Lua) und Klasse 3 (LuaJit/lvm)

Parallelisierung der Datenverarbeitung von VM schwierig, Verteilung hingegen ist prinzipiell moglich.

22 / 27

PD Stefan Bosse - VPP - Überblick :: Abstraktion

Abstraktion

Was kann durch eine VM abstrahiert oder virtualisert werden?

  • CPU×
  • Speicher×
  • IO×
  • Kommunikation×
  • Parallelisierung×
  • Konfiguration×
  • Hardware×
  • ...×
  • No search results.
23 / 27

PD Stefan Bosse - VPP - Überblick :: Programmiersprachen

Programmiersprachen

Welche Programmiersprachen werden häufig verwendet?

  • JAVA×
  • C++×
  • Python×
  • No search results.

Welche parallelen Programmiersprachen sind bekannt?

  • OCCAM×
  • GO×
  • ??Finde es heraus×
  • No search results.
24 / 27

PD Stefan Bosse - VPP - Überblick :: Parallele und Verteilte Programmierung mit Lua

Parallele und Verteilte Programmierung mit Lua

  • In diesem Kurs soll die Programmierung mit der Skriptsprache Lua erfolgen und mit der virtuellen Maschine lvm ausgeführt

  • Der Lua Quelltext wird durch einen Übersetzer in Bytecode übersetzt der von lvm direkt ausgeführt wird.

    • Besonderheit: Der Bytecode wird direkt während des Parservorgangs erzeugt (kein AST-IR)

  • Die LuaJit VM (lvm) unterstützt parallele Datenverarbeitung und das Konzept der Prozessblockierung

    • Prozesse
    • Threads
    • Coroutinen (Fibers)
25 / 27

PD Stefan Bosse - VPP - Überblick :: Parallele und Verteilte Programmierung mit Lua

  • Kontrollpfadparallelität benötigt i.A. Kommunikation und das Konzept der Blockierung des Prozessflusses!

  • Formales Ausführungsmodell: Communicating Sequential Processes (CSP)

CSP ist eine von Tony Hoare an der Universität Oxford entwickelte Prozessalgebra zur Beschreibung von Interaktion zwischen kommunizierenden Prozessen

  • Programmfluss = Kontrollfluss + Datenfluss

  • Parallele und Verteilte Datenverarbeitung: Übergang vom Shared Memory (SM) zum Distributed (Shared) Memory (DSM) Modell!

26 / 27

PD Stefan Bosse - VPP - Überblick :: Parallele und Verteilte Programmierung mit Lua

Parallele und Verteilte Programmierung mit Lua

(benötigt lvm weblvm.lua)

27 / 27