Verteilte und Parallele Programmierung

Überblick

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

Begleitet von Übungen um obige Techniken konkret anzuwenden

Vorlesung: 2 SWS mit Grundlagen und Live Programming
Übung: 2 SWS mit Programmierung und angewandter Vertiefung
Voraussetzungen: Grundlegende Programmierfähigkeiten, Grundkenntnisse in Rechnerarchitektur und Netzwerken

Zielgruppen des Kurses

Informatiker
Systemingenieure (Systems Engineering)
Produktionstechniker und Logistiker
Elektrotechniker

figscicomm [tiridifilm/istockphoto.com]

Materialien

Die Vorlesungsinhalte (Skript, Folien) werden auf http://edu-9.de unter der Rubrik Lehre zusammengestellt und angeboten
Weitere Materialien (Tutorials, Übungen, Software) werden ebenfalls auf http://edu-9.de bereitgestellt
Die Videos sind über http://edu-9.de verlinkt und sind auf http://ag-0.de verfügbar (opencast Server)
Interkation der Teilnehmer findet über einen Wiki statt! (dokuwiki). Dieser ist über http://ag-0.de erreichbar und in den jeweiligen Veranstaltungsseiten auf http://edu-9.de verlinkt.
Es wird noch einen online Chat geben.
Alle weiteren Hinweise und Einführungen (z.B. in Software) nur noch auf dem Wiki!!!

Leistungen

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

Mündliche Prüfung (über mindestens die Hälfte der Modulblöcke)
Schriftliche Ausarbeitung zu einer Fragestellung zu dem Thema (Review/Survey)
Die Bearbeitung einer experimentellen Arbeit (Lua)

Literatur

Vorlesungsskript und Folien: Die Inhalte der Vorlesung werden sukzessive bereitgestellt

Concurrent Programming: Algorithms, Principles, and Foundations: Michel Raynal, Springer 2013, ISBN 978-3-642-320626-2

figraynal

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

figbraunl

Literatur

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

figpacheco

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

figluatut

Software

Verwendete Software (Vorlesung und Übung):

threads.lua/parallel.lua

edu-9.de

Programmierung in Lua
Bibliothek für Parallele und Verteilte Systeme
Einfach zu Erlernen
Benötigt die Lua VM lvm

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

lvm

edu-9.de

LuaJit VM mit Multithreading
Ausführung von der Kommandozeile
Wird auch für Live Programming genutzt
Einsatz auf verschiedenen Hostplattformen : PC, Smartphone, Embedded PC, Server, ..
Einsatz auf Betriebssystemen: Windows, Linux, Solaris, MacOS, Android

> lvm parfib.lua

Software

Verwendete Software (Vorlesung und Übung):

pipe

pipe2.sourceforge.net

GUI basierte Simulation und Analyse von Petri Netzen
Modellierung von parallelen Systemen mit Diagrammen

figpipe

Ziele

Verständnis der Grundprinzipien und Architekturen verteilter (VS) und paralleler Systeme (PS) und Fähigkeit zum Transfer auf technische Systeme
Verständnis und Fähigkeit der programmatischen Anwendung von Synchronisation und Kommunikation in VS und PS
Verständnis der Probleme und dem Betrieb von parallelen Systemen im Vergleich zu sequenziellen Systemen (Effizienz, Blockierung, Skalierung, Ressourcenbedarf)
Praktische Kenntnisse der Programmierung von PS und VS anhand von Programmierübungen mit Lua und lvm (LuaJit)
Erkenntnisse von Grenzen und Möglichkeiten der Parallelisierung und Verteilung und die Fähigkeit effiziente Systeme zu entwickeln → Virtuelle Maschinen!
Vorbereitung für Methoden und zukunftige Trends im Cloud Computing und Internet der Dinge

Inhalte

Parallele und Verteilte Systeme
Sequenzielle und Parallele Datenverarbeitung
Funktionale, Sequenzielle, und Parallele Komposition
Prozessmodelle, Petri-Netze
Kommunizierende Prozesse, Synchronisation und Kommunikation (Primitiven)
Virtuelle Maschinen
Praktische Parallele Programmierung mit Lua und threads.lua/parallel.lua
Parallelisierung: Methoden und Algorithmen
Netzwerke und Nachrichrenaustausch
Plattformen und Architekturen: Multiprozessor, Cluster, GPU
Praktische Verteilte Programmierung mit Lua und parallel.lua

Virtuelle Maschinen

Die Verwendung von virtuellen Maschinen nimmt in der Datenverarbeitung immer mehr zu (Skriptsprachen)
Ein Schwerpunkt liegt in der Parallelisierung in und mit virtuellen Maschinen
Vor allem Parallelität auf Kontrollpfadebene und kommunizierende Systeme sollen betrachtet werden!

Parallele Prozesse und Kommunikationlocal 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.')

Parallele Prozesse und Kommunikation
1 2 3 4 5 6 7 8 9 10 11 12 13 14	`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.')`

Virtuelle Maschinen und Interpreter

Just-in-Time Compiler

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

Direkte Ausführung des Quelltextes (die Nutzereingabe und bereits geschriebene Skripte) (Parse → Execute)
Virtuelle Maschine und Übersetzung des Quelltextes in eine Zwischenrepräsentation die von einer virtuellen Maschine ausgeführt werden kann → Bytecode
Virtuelle Maschine mit Bytecode Übersetzung, Ausführung des Bytecodes, und ausgewählter Übersetzung des Bytecodes in nativen Maschinencode → JIT Compiler!

Beispiele

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)

Parallele und Verteilung 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
Kontrollpfadparallelität benötigt i.A. Kommunikation und das Konzept der Blockierung!
Formales Ausführungsmodell: Communicating Sequential Processes (CSP)
Programmfluß = Kontrollfluß + Datenfluß