PD Stefan Bosse - VPP - Modul I: Metriken und Verhalten von Parallelen Programmen

Verteilte und Parallele Programmierung

Mit Virtuellen Maschinen

PD Stefan Bosse

Universität Bremen - FB Mathematik und Informatik

1 / 84

PD Stefan Bosse - VPP - Modul I: Metriken und Verhalten von Parallelen Programmen

Metriken und Verhalten von Parallelen Programmen

Wie können parallele und nebenläufige Prozesse quantitativ erfasst werden?

Was kann schief gehen?

Was begrenzt die Parallelisierung?

2 / 84

PD Stefan Bosse - VPP - Modul I: Metriken und Verhalten von Parallelen Programmen

Zustands-Raum Diagramme

Für die Visualisierung und Analyse von nebenläufigen Prozessen und Aktionen

Zustands-Raum Diagramme beschreiben die möglichen Zustands-Entwicklungen - das Verhalten - von parallelen Programmen.

3 / 84

PD Stefan Bosse - VPP - Modul I: Metriken und Verhalten von Parallelen Programmen

  • Computer sind endliche Zustandsautomaten. Der Zustandsübergang wird durch die Programminstruktionen hervorgerufen.

  • Der Zustand S eines parallelen Programms welches aus N Prozessen Pi besteht setzt sich zusammen aus folgenden Tupeln:

    • Globale Variablen des Programms:
    • Lokale Variablen und Instruktionszeiger von Prozess 1:
    • Lokale Variablen und Instruktionszeiger von Prozess 2: usw.
  • Die Berechnung ändert globale und lokale Variablen (Datenfluss) sowie Instruktionszeiger (Kontrollfluss) und führt zu einer Zustandsänderung comp: sisj.

4 / 84

PD Stefan Bosse - VPP - Modul I: Metriken und Verhalten von Parallelen Programmen

Nebenläufige Programmierung: Zustands-Raum Diagramme

  • Wesentliche Zustandsänderung ist die Änderung von lokalen und globalen Speicher.

  • Variablen sind Bestandteil von Ausdrücken und erlauben zwei Operationen: {read,write}

var x: read(x) ⇔ RHS value(x) → ε (value(x))
write(x,v) ⇔ LHS reference(x) → x := v
5 / 84

PD Stefan Bosse - VPP - Modul I: Metriken und Verhalten von Parallelen Programmen

Beschreibung eines parallelen Programms auf Programmierebene

  • Der Zugriff auf globale und somit geteilte Variablen muss atomar sein, d.h. immer nur ein Prozess kann den Wert einer Variable lesen oder einen neuen Wert schreiben.

  • Der parallele Zugriff auf eine geteilte Ressource muss aufgelöst werden (Konflikt): i.A. mutualer Ausschluss durch Sequenzialisierung der parallelen Zugriffe!

6 / 84

PD Stefan Bosse - VPP - Modul I: Metriken und Verhalten von Parallelen Programmen

Nebenläufige Programmierung: Zustands-Raum Diagramme

  • Beispiel
write(X,v1) || write(X,v2) || x3:=read(X) →
write(X,v1); read(X,x3); write(X,v2) |
x3=read(X); write(X,v2); write(X,v2) | ..
  • Algebraisch ausgedrückt ergibt sich die Transformation:

(WRITE(x,v1)p1)(WRITE(x,v2)p2) (WRITE(x,v1)(WRITE(x,v2)(p1p2)))|(WRITE(x,v2)(WRITE(x,v1)(p1p2)))| ..

  • Es gibt eine Menge von möglichen Entwicklungen des parallelen Systems!
7 / 84

PD Stefan Bosse - VPP - Modul I: Metriken und Verhalten von Parallelen Programmen

Nebenläufige Programmierung: Zustands-Raum Diagramme

  • Instruktionen von Prozessen werden sequenziell ausgeführt. Instruktionen können auf Prozess-lokale und Programm-globale Variablen zugreifen.
  • Definition eines parallelen Programms: globale Variablen (V) und Prozesse mit lokalen Variablen (v)
var V1,V2,...
process p1(a1,a2,...) process p2(a1,a2,...)
var v1,v2,.... var v1,v2,....
Vi := ε(ai,vi,Vi) Vi := ε(ai,vi,Vi)
vi := ε(ai,vi,Vi) vi := ε(ai,vi,Vi)
end end
8 / 84

PD Stefan Bosse - VPP - Modul I: Metriken und Verhalten von Parallelen Programmen

Nebenläufige Programmierung: Zustands-Raum Diagramme

  • Bei einem sequenziellen Programm ist das Ergebnis einer Berechnung (d.h. die Werte aller Variablen) deterministisch allein durch die Anweisungssequenz und die Eingabedaten gegeben, und kann beliebig oft wiederholt werden - immer mit dem gleichen Ergebnis → Reihenfolge aller Anweisungen der Berechnung vorgegeben und fest

  • Bei einem parallelen Programm können mehrere Anweisungen verschiedener Prozesse gleichzeitig ausgeführt werden bzw. konkurrieren.

  • Die Reihenfolge parallel ausgeführter Anweisungen von einzelnen Prozessen kann hingegen undeterministisch = zufällig sein!!

  • Jeder der Prozesse kann als nächster den Zustand des Programms ändern.

  • Ein Zustands-Raum Diagramm beschreibt die Änderung des Programmzustandes als sequenzielle Auswertung aller möglichen Prozessaktivitäten.

9 / 84

PD Stefan Bosse - VPP - Modul I: Metriken und Verhalten von Parallelen Programmen

Nebenläufige Programmierung: Zustands-Raum Diagramme

  • Das Diagramm ist ein gerichteter Graph, dessen Knoten den aktuellen Programmzustand sS beschreiben, und dessen Kanten die möglichen Zustandsübergänge beschreiben.

  • Es gibt einen ausgewiesen Startzustand (Initialisierung) und einen oder mehrere Endzustände.

  • Gibt es mehrere Endzustände liegt wohl möglich ein Entwurfsfehler vor, da das Programm unterschiedliche Endergebnisse liefern kann.

10 / 84

PD Stefan Bosse - VPP - Modul I: Metriken und Verhalten von Parallelen Programmen

Algorithmus: Entwicklung des Zustands-Raum Diagramms

  • Parallelen Programms welches aus N Prozessen P={p1,p2,..,pN} besteht.
  1. Initialisiere den Startzustand sx=s0 und erzeuge Wurzel-Knoten s0 im Diagramm.

  2. Aktueller Zustand: sx. Setze P*:=P mit P={p1,p2,..,pN} als Prozessliste und S*={}

  3. Wähle (entferne) einen beliebigen Prozess px aus der Prozessliste P* und setze P*:= {pn| pnP* ∧ pnpx}

11 / 84

PD Stefan Bosse - VPP - Modul I: Metriken und Verhalten von Parallelen Programmen

Nebenläufige Programmierung: Zustands-Raum Diagramme

  1. Evaluiere die nächste Instruktion ix,n von px und berechne die Wirkung auf lokale und globale Variablen sowie den Instruktionszeiger Ix,n.

  2. Erzeuge einen neuen Zustandsknoten sj/=x , füge ihn zur Liste S*:=S* ∪ {sj} hinzu und verbinde ihn mittels einer Kante tx→j mit dem aktuellen Ausgangszustand sx

  3. Wiederhole Schritt 3 bis 5 für alle anderen verbleibenden Prozesse pP bis P*={}

  4. Setze S**:=S*. Für jeden Knoten sxS** wiederhole die Schritte 2 bis 6. Iteriere Schritt 7 bis alle Prozesse terminiert sind oder keine Zustandsänderung mehr auftritt.

12 / 84

PD Stefan Bosse - VPP - Modul I: Metriken und Verhalten von Parallelen Programmen

Nebenläufige Programmierung: Zustands-Raum Diagramme

Beispiel

Sequenzielles Programm Paralleles Programm
for i := 1 to 3 do i1 process p1
for i := 1 to 3 do i1
end
process p2
for j := 1 to 3 do i2
end
13 / 84

PD Stefan Bosse - VPP - Modul I: Metriken und Verhalten von Parallelen Programmen

Nebenläufige Programmierung: Zustands-Raum Diagramme