Stefan Bosse - VPP - Modul D Parallele Programmierung ::

Parallele Programmierung

Grundlagen der parallelen Programmierung

Unterscheidung zwischen Parallelisierung im Daten- und Kontrollfluß von Programmen

Prozessmodelle und Prozesskonstruktoren

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Parallelisierungsklassen

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.

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Parallelisierungsklassen

Parallelisierungsklassen

Programmfluss

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Parallelisierungsklassen

Parallelisierungsklassen

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

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

Programm-, Kontroll-, und Datenflussgraphen

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Parallelisierungsklassen

Parallelisierungsklassen

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Parallelisierungsklassen

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Parallelisierungsklassen

Parallelisierungsklassen

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Parallelisierungsklassen

Parallelisierungsklassen

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

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Parallelisierungsklassen

Parallelisierungsklassen

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

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Parallelisierungsklassen

Parallelisierungsklassen

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)

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Parallelisierungsklassen

Parallelisierungsklassen

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Parallelisierungsklassen

Parallelisierungsklassen

Möglichkeiten der Parallelisierung

1. Vertikale Parallelität auf Bitebene (jegliche funktionale Operation)
2. Horizontale Parallelität durch Pipelining (nur Datenströme)
3. Parallelität durch mehrere Funktionseinheiten:
   • Superskalare Prozessoren
   • Very Large Instruction Word (VLIW) Prozessoren
4. Funktionsparallelität (Evaluierung der Funktionsargumente und Rekursion)
5. Vertiakle Parallelität auf Prozess- bzw. Threadebene (Kontrollpfadebene)

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Fluss und Pfadgraphen

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Daten- und Kontrollpfade

Daten- und Kontrollpfade

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

1. Datenfluss → Datenpfade
2. Kontrollfluss → Kontrollpfad → Zustandsautomat

Datenpfad

• Führt Berechnungen durch
• Kann rein funktional (speicherlos, kombinatorisch) oder speicherbasiert mir Register-Transfer Architektur sein

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Daten- und Kontrollpfade

Daten- und Kontrollpfade

Kontrollpfad

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Daten- und Kontrollpfade

Daten- und Kontrollpfade

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Daten- und Kontrollpfade

Daten- und Kontrollpfade

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Daten- und Kontrollpfade

Daten- und Kontrollpfade

• Komposition von Daten- und Kontrollfluss/pfad:
  • Sequenzielle Komposition
  • Parallele Komposition

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Funktionale Programmierung

Funktionale Programmierung

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Funktionale Komposition

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 f_i beschreibt einen Teil der Berechnung.

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Funktionale Komposition

Funktionale Komposition

• Ausdrücke bestehen aus:

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Funktionale Komposition

Funktionale Komposition

• 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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Funktionale Komposition

Funktionale Komposition

Beispiel für Funktionsdefinition und Applikation

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Funktionale Komposition von Systemen

Funktionale Komposition von Systemen

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Map&Reduce - Funktional

Map&Reduce - Funktional

l=[ν1,ν2,..]
l'=map(l,x => f(x))
l''=reduce(l',(a,b) => g(a,b))

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Map&Reduce - Lua

Map&Reduce - Lua

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Map&Reduce - Lua

Map&Reduce - Lua

┌――――――――――――――――――――――――――――――――┐
│            Data List           │
└――┬――――――――┬――――――――┬――――――――┬――┘
   │        │        │        │   
   │        │        │        │   
   ▼        ▼        ▼        ▼   
┌―――――┐  ┌―――――┐  ┌―――――┐  ┌―――――┐
│  f  │  │  f  │  │  f  │  │  f  │
└――┬――┘  └――┬――┘  └――┬――┘  └――┬――┘
   │        │        │        │   
   │ ┌――――┐ │        │ ┌――――┐ │   
   └―┤ g  ├―┘        └―┤ g  ├―┘   
     └―┬――┘            └――┬―┘     
       │                  │       
       │      ┌―――――┐     │       
       └――――――┤  g  ├―――――┘       
              └―――――┘

Datenflussgraph von Map&Reduce (vertikal) und (mögliche) Parallelisierung (horizontal)

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Map&Reduce - Lua

Map&Reduce - Lua

local options = {workers = 2, remap=true, schedule="circular", mapchunks=true}
-- Input data
local data = {34,35,36,37,38,39,40,41}
-- Worker Function
local function worker (set,id)
  -- set ist ganze Partition!
  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(function (r) 
    print(r:print()) end):
  time()

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Map&Reduce - Lua

Map&Reduce - Lua

local options = {workers = 2, remap=true, schedule="circular", mapchunks=false}
-- Input data
local data = {34,35,36,37,38,39,40,41}
-- Worker Function
local function worker (n,index,id)
  -- hier jetzt Aufruf mit einzelnen Daten,
  -- zerlegung und Zusammenfügung 
  -- einer Partition (chunk) dann in parallel mapper
  return fib(n)
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(function (r) 
    print(r:print()) end):
  time()

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Sequenzielle Komposition

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 sequenziell in exakt der angegebenen Reihenfolge ausgeführt

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Sequenzielle Komposition

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

1. Arithmetische, relationale, und boolesche Ausdrücke (in Verbindung mit 2./3.) x+1, a*(b-c)*3, x<(a+b), ...
2. Datenanweisungen: Wertzuweisungen an Variablen x := a+b
3. Kontrollanweisungen wie bedingte Verzweigungen und Sprünge (Schleifen)

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Sequenzielle Komposition

Sequenzielle Komposition

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Sequenzielle Komposition

Sequenzielle Komposition

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Das Prozeßmodell

Das Prozeßmodell

Es werden zwei Prozesstypen unterschieden:

Sequenzieller Prozeß

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

Paralleler Prozeß

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Sequenzieller Prozess

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), z.B. Verfügbarket von Eingabedaten
  • Blockiert (BLOCKED), z.B. P1(suspend)-P2(wakeup) Paare
  • Rechenbereit aber nicht rechnend (nach Ereignis) (READY)

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Sequenzieller Prozess

• Befindet sich der Prozess im Ausführungszustand RUN (also ausführend), dann werden strikt sequenziell die Instruktionen des Programs I={i₁,i₂,..,i_n} 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.

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Sequenzieller Prozess: Zeitliches Modell

Sequenzieller Prozess: Zeitliches Modell

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

$${i_1}:{t_1} \mapsto {i_2}:{t_2} \mapsto {i_3}:{t_3} \mapsto .. \mapsto {i_n}:{t_n}{\text{ mit}} \\ {t_1} < {t_2} < {t_3} < .. < {t_n} \\ T = \sum\limits_i {{t_i-t_{i-1}}} \ $$

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Sequenzieller Prozess

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 AWAIT wartet dieser auf ein Ereignis:

  • Daten sind verfügbar
  • Zeitüberschreitung
  • Geteilte Ressource ist frei
  • Synchronisation mit anderen Prozessen

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Sequenzieller Prozess

Sequenzieller Prozess

• 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

Koroutinen

• In Koroutinen (Fiber) z.B. mittels der yield Anweisung
• Der Programmfluß 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)

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Sequenzieller Prozess

Koroutinen

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Sequenzieller Prozess

Koroutinen

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Sequenzieller Prozess

Koroutinen

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

Asymmetrische Koroutinen in Lua

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Sequenzieller Prozess

Sequenzieller Prozess

Fibers

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Sequenzieller Prozess

Fibers

co1 = luv.fiber.create(function ()
           for i=1,5 do
             print("co1", i)
             luv.fiber.yield()
           end
           print("co1 finished.")
         end)
co2 = luv.fiber.create(function ()
           for i=1,5 do
             print("co2", i)
             luv.fiber.yield()
           end
           print("co2 finished.")
         end)
co1:ready()
co2:ready()
co1:join()
co2:join()
print ("Done.")

Luv Fibers: Symmetrische Koroutinen in lvm/luv

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Sequenzieller Prozess

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Parallele Prozesse

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₂ ; .. ; i_n) ⇒ p₁ ↦ p₂ ↦ .. ↦ p_n

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Parallele Komposition

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₃ ∥ ..

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Paralleler Prozess

Paralleler Prozess

Prozesskonstruktor

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Paralleler Prozess

Paralleler Prozess

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:

$$\begin{gathered} {P_1}\parallel {P_2}\parallel ..\parallel {P_n} \Rightarrow {P_1};{P_2};..;{P_n} \hfill \\ {P_1}\parallel {P_2} \Rightarrow {P_1};{P_2} \Rightarrow {P_2};{P_1}! \hfill \ \end{gathered}$$

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Paralleler Prozess: Zeitliches Modell

Paralleler Prozess: Zeitliches Modell

$$P = {P_1}\parallel {P_2}\parallel ..\parallel {P_n} \\ {P_1} = ({i_{1,1}}:{t_{1,1}};{i_{1,2}},:{t_{1,2}};..) \cdots {P_n} = ({i_{n,1}}:{t_{n,1}};{i_{n,2}}:{t_{n,1}};..),{\text{ mit}} \\ {t_{i,1}} < {t_{i,2}} < .. < {t_{i,m}}{\forall\text{Prozess mit }}m{\text{ Instr}}{\text{. und }} \\ t(P) = [{t_1},{t_2}] = [{t_{1,1}},{t_{1,q}}] \cup [{t_{2,1}},{t_{2,r}}] \cup .. \cup [{t_{n,1}},{t_{n,s}}] \\ {t_1} = \min \{ {t_{1,1}},{t_{2,1}},..,{t_{n,1}}\} \\ {t_2} = \max \{ {t_{1,q}},{t_{2,r}},..,{t_{n,s}}\} \ T=t_2-t_1 \\ $$

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Prozessflussdiagramme

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.

Beispiel eines Prozessflussdiagramms für vier Prozesse. P₁ startet P₃, und P₂ spaltet P₄ ab. (mit P_{_,i} = Instruktion(P,i))

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Paralleler Prozess

Paralleler Prozess

Prozesserzeugung und Synchronisation

• Ein neuer paralleler Prozess kann durch den entsprechenden Prozesskonstruktor erzeugt werden

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Paralleler Prozess

Forking

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

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Parallele Prozesse in Lua

Parallele Prozesse in Lua

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Lua - Ausführungsmodelle

Lua - Ausführungsmodelle

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Lua - Ausführungsmodelle

Lua - Ausführungsmodelle

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Lua - Ausführungsmodelle

Lua - Ausführungsmodelle

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Lua - Ausführungsmodelle

Lua - Ausführungsmodelle

Threadmodell und Kommunikation der Prozesse mit geteilten Objekten

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Lua - Ausführungsmodelle

Lua - Ausführungsmodelle

IO Paralellisierung

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Lua - Ausführungsmodelle

Lua - Ausführungsmodelle

docs.libuv.org/en/v1.x/design.html Asynchrone IO mit der libuv Architektur

Stefan Bosse - VPP - Modul D Parallele Programmierung :: LVM

LVM

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

Parallelisierung durch multiple VM Instanzen mit Inter-VM Kommunikation

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Asynchrone Ereignisverarbeitung

Asynchrone Ereignisverarbeitung

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Asynchrone Ereignisverarbeitung

Asynchrone Ereignisverarbeitung

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Asynchrone Ereignisverarbeitung

Asynchrone Ereignisverarbeitung

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Asynchrone Ereignisverarbeitung

Asynchrone Ereignisverarbeitung

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Asynchrone Ereignisverarbeitung

Asynchrone Ereignisverarbeitung

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:

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Asynchrone Ereignisverarbeitung

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

Verwendung einer Prädikatfunktion P zur Auflösung von Abhängigkeiten und Asynchronität / Unbekannter Ausführungsreihenfolge

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Synchronisierung von Callbacks

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

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Synchronisierung von Callbacks

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

Deasync Wrapper für asynchrone Funktionen

Stefan Bosse - VPP - Modul D Parallele Programmierung :: Zusammenfassung

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 terminert

Prozessblockierung ist wesentliche Eigenschaft von synchronisierenden Prozessen