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

[tiridifilm/istockphoto.com]

Materialien

1. Die Vorlesungsinhalte (Skript, Folien) werden auf http://edu-9.de unter der Rubrik Lehre zusammengestellt und angeboten

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

3. Die Videos sind über http://edu-9.de verlinkt und sind auf http://ag-0.de verfügbar (opencast Server)

4. 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.

5. Es wird noch einen online Chat geben.

6. 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:

1. Mündliche Prüfung (über mindestens die Hälfte der Modulblöcke)

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

3. Die Bearbeitung einer experimentellen Arbeit (Lua)

Literatur

Vorlesungsskript und Folien

Die Inhalte der Vorlesung werden sukzessive bereitgestellt

Literatur

Software

Verwendete Software (Vorlesung und Übung):

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 parfib.lua

Software

Verwendete Software (Vorlesung und Übung):

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 (Effizienz, Blockierung, Skalierung, Ressourcenbedarf)

4. Praktische Kenntnisse der Programmierung von PS und VS anhand von Programmierübungen mit Lua und lvm (LuaJit)

5. Erkenntnisse von 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

Inhalte

1. Parallele und Verteilte Systeme
2. Sequenzielle und Parallele Datenverarbeitung
3. Funktionale, Sequenzielle, und Parallele Komposition
4. Prozessmodelle, Petri-Netze
5. Kommunizierende Prozesse, Synchronisation und Kommunikation (Primitiven)
6. Virtuelle Maschinen
7. Praktische Parallele Programmierung mit Lua und threads.lua/parallel.lua
8. Parallelisierung: Methoden und Algorithmen
9. Netzwerke und Nachrichrenaustausch
10. Plattformen und Architekturen: Multiprozessor, Cluster, GPU
11. 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!

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:

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!

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ß

Parallele und Verteilung Programmierung mit Lua