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

Beispiel und mögliche Entwicklung des Programmzustands (lokale Var. i,j)

14 / 84

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

Globale Ressourcen und Synchronisation

Globale Ressourcen

  • In dem bisherigen Programmiermmodell gibt es nur globale Variablen als globale geteilte Ressourcen, die konkurrierend von Prozessen gelesen und beschrieben werden können.

  • Die globalen Variablen dienen dem Datenaustausch = Kommunikation zwischen den Prozessen (Shared Memory Model!).

    • Shared Memory dient aber nur dem Datenaustausch, es bietet keine höhere Synchronisation zwischen Prozessen
    • Bei nachrichtenbasierter Kommunikation (und auch Channels/Queues) ist das anders.
15 / 84

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

Globale Ressourcen und Synchronisation

Atomare Aktionen

  • Atomare Operationen, Schreibweise |A| werden in einem Schritt ausgeführt und können nicht durch andere Prozesse unterbrochen werden (keine Interferenz).
  • Einzelne Lese- und Schreibe-Operationen mit globalen Variablen sind atomar. Nebenläufigkeit wird durch Sequenzialisierung aufgelöst.
t1: |X := v|
16 / 84

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

Globale Ressourcen und Synchronisation

Nicht atomare Aktionen und Synchronisation

Zusammengesetzte Ausdrücke können aus mehreren Berechnungsschritten bestehen, so ist z. B. X := X + 1 als Ganzes nicht mehr atomar!

t1: |temp=X|
t2: |X:=temp+1|
|X:=X+1| ??
17 / 84

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

Globale Ressourcen und Synchronisation

Beispiel einer unzureichend geschützten nicht atomaren Aktion

var X := 1
INCR(X) DECR(X)
process p1 process p2
var t:=0 var t:=0
t := X t := X
X := t + 1 X := t - 1
end end
18 / 84

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

Globale Ressourcen und Synchronisation

Zustands-Raum Diagramm mit unterschiedlichen Endergebnissen (X=0,-1,1)

19 / 84

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

Experiment

20 / 84

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

Globale Ressourcen und Synchronisation

Nicht atomare Aktionen (Sequenz von Aktionen) mit globalen Ressourcen müssen durch Mutuale Ausschlusssynchronisation geschützt werden → Schutz von kritischen CodebereichenDatenkonsistenz!

Semaphore

  • Eine Semaphore S ist ein Zähler s>0 der niemals negative Werte annehmen kann.

  • Es gibt zwei atomare Operationen die von einer Menge von Prozessen P={p1,p2,...} auf einer Semaphore S angewendet werden können:

21 / 84

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

Globale Ressourcen und Synchronisation

operation down(S) ∈ p:
|if s > 0
then s := s - 1
else WAITERS+(S,p),block(p)|
operation up(S) ∈ p:
|if s = 0 and WAITERS(S) ≠ []
then pi=WAITERS-(S),unblock(pi)
else s := s + 1|

Operationen der Semaphore

22 / 84

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

Globale Ressourcen und Synchronisation

  • Eine Semaphore mit einem Startwert s=1 entspricht einer Mutex (binäre Semaphore). Ein DOWN(S) leitet einen kritischen Bereich in einer Sequenz i1,i2,i3, ... ein, und ein UP(S) gibt ihn wieder frei:
semaphore S(1)
... down(S) |i1,i2,i3,..,in)| up(S) ...
23 / 84

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

Globale Ressourcen und Synchronisation

Beispiel einer mit einer Semaphore geschützten nicht atomaren Aktion

var X := 1
semaphore S := 1
INCR(X) DECR(X)
process p1 process p2
var t:=0 var t:=0
down(S) down(S)
t := X t := X
X := t + 1 X := t - 1
up(S) up(S)
end end
24 / 84

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

Globale Ressourcen und Synchronisation

Zustands-Raum Diagramm mit einem Endergebnis (X=0)

25 / 84

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

Eigenschaften von Parallelen Systemen

Konkurrieren mehrere Prozesse um die Ressource K, so gewinnt maximal einer, die anderen verlieren den Wettbewerb. Wettbewerb

Ein solches Wettbewerbsproblem ist gekennzeichnet durch die Eigenschaften Sicherheit und Lebendigkeit.

Sicherheit bedeutet: Bedingung Anzahl der Prozesse im kritischen Bereich K muss |{ p | I(p) ∈ K}| ≤ 1 immer erfüllt sein.

26 / 84

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

Eigenschaften von Parallelen Systemen

Eigenschaft (Liveness) Lebendigkeit → Starvation Freiheit

  • Starvation Freiheit bedeutet dass ein Prozess pi der die Ressource/den kritischen Bereich anfragt maximal eine endliche Anzahl von Zeiteinheiten / Wettbewerben n ≠ ∞ durch jeden anderen Prozess umgangen werden kann (Bypass, haben den Wettbewerb gewonnen).
27 / 84

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

Eigenschaften von Parallelen Systemen

Eigenschaft Deadlock Freiheit

  • Wenn bis zu einem beliebigen Zeitpunkt t eine Reihe von Prozessen versucht haben den kritischen Bereich zu erlangen, ihn aber nicht erhalten haben, zu wird es in der Zukunft eine Zeit t' > t geben, wo sie erfolgreich sind (d.h. die Anfrage-Operation terminiert).

  • D.h. eine Anfrage der Ressource terminiert mit einem gewonnen Wettbewerb garantiert irgendwann.

    • Starvation Freiheit impliziert Deadlock Freiheit!
    • Worst case eines Deadlocks: alle Prozesse verlieren den Wettbewerb, keiner kann die Ressource mehr nutzen/zugeteilt bekommen!
28 / 84

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

Eigenschaften von Parallelen Systemen

Eigenschaft Begrenztes (Bounded) Bypass Kriterium

  • Es gibt eine Funktion f(N) für N Prozesse die die maximale Anzahl von verlorenen Wettbewerben (bei Konkurrenz) angibt.
29 / 84

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

Eigenschaften von Parallelen Systemen

Service gegen Klient Sichtweise

Der Service ist die Ressource, der kritische Bereich. Der Klient ist der Prozess, der die Ressource anfragt.

  • Aus Sicht des Service (Ressource) ist die Deadlock Freiheit wichtigstes Kriterium. Der konkurrierende Wettbewerb führt immer dazu, dass irgendein Prozess die Ressource nutzen kann → die Ressource gewinnt immer.

  • Aus Sicht des Klienten (Prozesses) ist die Starvation Freiheit wichtigstes Kriterium. Wenn immer ein Prozess die Ressource anfragt, wird er sie (eventuell) zugeteilt bekommen → der Prozess gewinnt immer.

30 / 84

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

Eigenschaften von Parallelen Systemen

  • Es gibt daher eine Hierarchie der Lebendigkeitseigenschaften (entsprechend ihrer Stärke):

1. Bounded Bypass f(N)=X ≫

2. Starvation Freiheit ≡ Endlicher Bypass f(N) ≠ ∞ ≫

3. Deadlock Freiheit

31 / 84

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

Eigenschaften von Parallelen Systemen

Deadlock

  • Tritt häufig ein wenn zwei (oder mehrere) Prozesse gegenseitig eine Ressource (Lock) beanspruchen die aber jeweils vom anderen bereits belegt ist.

    • Prozesse, die bereits Sperren halten, fordern neue Sperren an.

    • Die Anforderungen für neue Sperren werden gleichzeitig gestellt.

    • Zwei oder mehr Prozesse bilden eine kreisförmige Kette, in der jeder Prozesse auf eine Sperre wartet, die vom nächsten Prozess in der Kette gehalten wird → Dining Philosopher Problem.

32 / 84

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

Eigenschaften von Parallelen Systemen

Deadlocksituation zweier Prozesse die wechselseitig gesperrte Ressourcen anfordern

33 / 84

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

Experiment

34 / 84

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

Parallelität

  • Unterteilung in räumliche und zeitliche Parallelität

  • Parallele Datenverarbeitung bedeutet Partitionierung eines seriellen Programms in eine Vielzahl von Subprogrammen oder Tasks

  • Weitere Unterteilung beider Dimensionen in Abhängigkeit von:
    • Art der Tasks/Algorithmen
    • Ausführungsmodell der Tasks und verwendete Rechnerarchitektur
    • Art und Umfang der Wechselwirkung zwischen Tasks
    • Kontroll- und Datenfluss eines Tasks
35 / 84

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

Parallelität

Räumliche Parallelität
Die Datenmenge D kann in Teilmengen diD zerlegt werden. Die minimal erreichbare Größe der Teilmenge gibt Granularität bei der Parallelisierung wieder. Die Datenmenge D wird durch eine Verarbeitungsstufe in eine neue Datenmenge D' transformiert, die dann von nachfolgenden Verarbeitungsstufen weiter verarbeitet wird.
Beispiel : D=Bild ⇒ Glättung ⇒ D1 ⇒ Objekterkennung ⇒ D2
Zeitliche Parallelität
Zeitliche Parallelität ist vorhanden, wenn eine Folge von gleichartigen Datenmengen D(n) repitierend mit dem gleichen Algorithmus verarbeitet werden → Pipeline-Verfahren
36 / 84

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

Datenabhängigkeit

  • Räumliche und zeitliche Parallelität führen zu räumlicher und zeitlicher Datenabhängigkeit.

  • Räumliche Datenabhängigkeit findet auf Intra- und Intertaskebene statt.

    • Intrataskebene: Subtasks tauschen Daten aus → Sequenzielle Ausführung. Beispiel: ST1: a=x+y; ST2: b=a+1;b(a) → ST2(ST1)

    • Intertaskebene: Übertragung von Daten zwischen Tasks in einer Pipeline.

  • Zeitliche Datenabhängigkeit: Ergebnisse aus der Vergangenheit gehen in aktuelle Datenberechnung ein. Beispiel: Bewegungserkennung aus einer Bild-Sequenz.

37 / 84

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

Datenabhängigkeit

Räumliche und zeitliche Datenabhängigkeit ⇔ Vertikale und horizontale Parallelisierung

38 / 84

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

Rechenzeit

  • Die Rechenzeit ttot für die Ausführung einer Pipeline T1...TM enthält:

    1. Zeit zum Einlesen der Daten I(n),
    2. Zeit für die Ausgabe der Daten und Ergebnisse,
    3. Summe aller Ausführungszeiten der Tasks in der Pipeline, die sich aus Rechen- und Kommuniaktionszeiten zusammensetzten.

ttot=mi=1τi+m1i=1td(Di,i+1)+tin+toutτi=max{tcomp(Ti,j(dj))|1jni}+tcomm(Ti)

als die Zeit die benötigt wird, einen Task i unter Berücksichtigung von Datenabhängigkeiten der ni Subtasks T(dj) zu bearbeiten.

39 / 84

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

Rechenzeit

  • Längste Bearbeitungszeit eines Subtasks bestimmt Bearbeitungszeit des Tasks τi!
  • Ti ist der i-te Task in der horizontalen Pipeline,
  • dj die Teildatenmenge eines Subtasks Ti,i(dj) eines Tasks Ti,
  • tcomp ist die Rechenzeit,
  • tcomm die Intertaskkommunikationszeit,
  • tin und tout die Zeit zum Datentransfer in und aus der Pipeline, und
  • td(Di,i+1) die Datentransferzeit zwischen zwei Tasks.
  • In Vision-Systemen sind die ersten Tasks i.A. low- und mid-level Algorithmen, und die letzten Tasks high-level Algorithmen, die auf den Daten der unteren Ebenen aufbauen. Die einzelnen Datenströme Di können daher von unterschiedlicher Größe und Art sein.
40 / 84

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

Klassifikation von parallelen Algorithmen

Datenabhängigkeit

Lokal, statisch
Ausgangsdaten (≡Ergebnisse) hängen nur von eng begrenzter kurzreichweitiger Region der Eingangsdaten ab. Die Größe der Eingangsdatenregion ist unveränderlich (statisch). → Kommunikationsbedarf ist gering.
Lokal, dynamisch
Die Größe der Eingangsdaten-Region ist parametrisiert und veränderlich (dynamisch). Z.B. bei mathematischer Faltung von Bildmatrizen ändert sich Größe der Region.
41 / 84

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

Klassifikation von parallelen Algorithmen

Global, statisch
Die Ausgangsdaten hängen gänzlich vom gesamter Eingangsdatenmenge ab. Abhängigkeit hängt nur von der Größe des Bildes, aber nicht von dessen Inhalt ab. Z.B. Fouriertransformation oder Histogramm-Funktionen. → Kommunikationsbedarf ist groß.
Global, dynamisch
Ausgangsdaten hängen von variierenden Ausschnittsregion der Eingangsdaten ab. Die Berechnung ist vollständig datenabhängig. Z.B. Hough-Transformation.
42 / 84

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

Klassifikation von parallelen Algorithmen

Klassifikation nach Kommunikationsbedarf aufgrund Datenabhängigkeit zwischen einzelnen Tasks eines parallelen Programms

  • Weiterhin Klassifikation nach:
    • Eingabedatenabhängigkeit
    • Ergebnisabhängigkeit
43 / 84

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

Speed-up

Bei der Datenverarbeitung gibt es drei Randbedingungen:

  1. Gesamte Rechenzeit → Zeitdimension
  2. Gesamte Ressourcenbelegung → Flächendimension
  3. Bei der Parallelverarbeitung wird eine weitere Dimension hinzugefügt: Anzahl der Verarbeitungseinheiten N
  • Die Nutzung von Parallelität führt zu einem Performanzgewinn (Speedup) durch Vergleich sequenzielles Programm (N=1) mit parallelen Programm (N Prozessoren):

Speedup=S(N)=Performanz(N)Performanz(1),St(n)=Rechnenzeit(1)Rechenzeit(N)

44 / 84

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

Speed-up

  • Die sog. Skalierung bei der Parallelisierung ist i.A. nicht linear:

0<S(N)<N

  • Kommunikation ist weitere Randbedingung bei der parallelen Datenverarbeitung.
45 / 84

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

Kosten und Laufzeit

Beispiel: Matrixmultiplikation

FUN matmult(A:ARRAY (p,q), B: ARRAY(p,q)) -> C:ARRAY (p,r)
DEF matmult(A, B) =
FOR i = 1 to p DO
FOR j = 1 to r DO
C[i,j] <- 0;
FOR k = 1 to q DO
C[i,j] <- C[i,j] + A[i,k] * B[k,j]
END FOR k
END FOR j
END FOR i
END
46 / 84

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

Kosten und Laufzeit

  • Partitionierung kann beliebig erfolgen, da die einzelnen Ergebniswerte Ci,j nicht voneinander abhängen.

  • Datenabhängigkeit des Problems: Die Berechnung eines Ci,j Wertes hängt außerhalb der FOR-k-Schleife von keinem anderen Wert Cn,m mit ni und mj ab.

47 / 84

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

Kosten und Laufzeit

  • Mögliche Partitionierungen der drei For-Schleifen auf N parallel arbeitenden Verarbeitungseinheiten (VE):
  1. Jede VE berechnet einen Ci,j-Wert. D.h. eine VE führt die FOR-k-Schleife für ein gegebenes i und +j* durch.
    • Jede VE benötigt dazu die i-te Zeile von A und die j-te Spalte von B.
    • Keine weitere Datenabhängigkeit!
    • Es werden N=p•r VEs benötigt.
  1. Eine VE berechnet eine Ergebnisspalte, d.h. führt die FOR-k und FOR-j-Schleifen durch.
    • Jede VE benötigt A und eine Spalte von B.
    • Es werden N=p VEs benötigt.
48 / 84

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

Kosten und Laufzeit

  1. Eine VE führt eine Multiplikation und Addition innerhalb der FOR-K-Schleife durch.
    • Jede VE benötigt einen A und B-Wert.
    • Es werden N=p•r•q VEs benötigt.
    • Jeweils eine VE für einen gegebenen Ci,j-Wert führt die Zusammenführung der Zwischenwerte der FOR-k-VEs durch.
  • Zusammenführung der Ergebnisdaten in den Fällen 1&2 trivial. Im Fall 3 besteht Zusammenführung im wesentlichen in der Summation der Zwischenergebnisse.
49 / 84

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

Kosten und Laufzeit

Mögliche Partitionierungen der Matrixmultiplikation

50 / 84

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

Kosten und Laufzeit

Kosten und Laufzeitanalyse der verschiedenen Parititionierungen

51 / 84

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

Kommunikation

  • Berechnung der Kommunikation mit Einheitswerten eines Nachrichtenaustauschs: Message Passing (MP) → Aufwand eine Zelle einer Matrix zu versenden ist MP=1.

Kommunikation Fall 1

52 / 84

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

Kommunikation

Kommunikation Fall 2

53 / 84

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

Kommunikation

Kommunikation Fall 3

54 / 84

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

Kommunikation

  • Bisher konnten Matrizen ganzzahlig auf VEs verteilt werden. In der Realität ist aber p=q=r,n!

  • Bisher wurde angenommen, dass alle VEs mit jeder anderen VE Daten mit einer Distanz/Ausdehnung D=1 austauschen kann. Nur möglich mit vollständig verbundenen Netzwerktopologien unter Verwendung von Kreuzschaltern.

  • Gängige parallele und ökonomische Rechnertopologie: Maschennetz

    • Besteht aus n × n VEs.
    • Jede VE kann mit seinem direkten Nachbarn kommunizieren.
    • Eine Nachricht hat eine maximale Reichweite von (2n-1) VEs, Θ(n).
55 / 84

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

Kommunikation

  • Bisherige statische Partitionierung resultiert in zu hohen Kommunikationsaufwand in der Verteilung der Matrizen A und B sowie in der Zusammenführung der Matrix C.
    • Dynamisch veränderliche Partitionierung passt sich effizienter an Netzwerktopologie an.
    • Bei Matrixoperationen mit zwei Matrizen (n=p=q=r) ist dafür ein 2n × 2n Netz optimal geeignet.

Zweidimensionales Maschennetzwerk

56 / 84

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

Kommunikation

Dynamische Verteilung der Matrizen

  • Das 2n x 2n Netz wird in vier Quadranten der Größe n × n unterteilt.

    • Die Matrizen A und B befinden sich initial im linken unteren und rechten oberen Quadranten
    • Die Ergebnismatrix C wird schließlich im rechten unteren Quadranten zusammen- geführt.
  • Alle VEs die ein A1,j-Element besitzen werden dieses nach rechts verschieben.

  • Alle VEs die ein Bi,1-Element besitzen werden dieses nach unten verschieben.

    • Dieser Vorgang wird für weitere Zeilen (A) und Spalten (B) fortgesetzt.
    • Die einzelnen Elemente von A und B passieren die VEs im C-Quadranten. Die einzelnen C-Werte können mittels Summation berechnet werden.
57 / 84

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

Kommunikation

Dynamische und überlagerte Verteilung der Matrizen A, B, und C

58 / 84

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

Kommunikation

  • Die Laufzeit der Matrixmuliplikation auf dem Netz beträgt Θ(n), da n Verschiebungen durchgeführt werden.

  • Die Kosten betragen Θ(n3), vergleichbar mit sequenzieller Ausführung. D.h. diese Partitionierung und Architektur ist kostenoptimal.

  • Das 2n x 2n Netz wird nur in drei Quadranten genutzt. Benötigt werden daher nur 3n2 VEs.

  • Aus Sicht der Rechnerarchitektur ungünstig zu implementieren und nicht generisch, d.h. abhängig vom verwendeten Algorithmus.

59 / 84

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

Kommunikation

  • Reduktion dieses Verfahrens auf n × n Netz möglich

    • Dazu werden die Matrizen A, B und C überlagert, d.h. VE1,1 ⇒ {A1,1,B1,1,C1,1}.
  • Die Zeilenelemente von A werden dann nach vorherigen Ablaufschema gegen den Uhrzeigersinn rotiert (nur horizontal), und die Spaltenelemente von B im Uhrzeigersinn (vertikal).

  • Man erhält gleiche asymptotische Grenzwerte für die Laufzeit Θ(n) und Kosten Θ(n3)!

60 / 84

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

Kommunikation

Überlagerte Verarbeitung der Matrizen A, B, und C auf einem Maschennetzwerk

61 / 84

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

Maßzahlen für Parallele Systeme

Berechnungszeit
Die Berechnungszeit Tcomp (computation time) eines Algorithmus als Zeit, die für Rechenoperationen verwendet wird.
Kommunikationszeit
Die Kommunikationszeit Tcomm (communication time) eines Algorithmus als Zeit, die für den Daten- bzw. Nachrichtenaustausch (Sende- und Empfangsoperationen) zwischen Subprogrammen und Verarbeitungseinheiten verwendet wird.
Untätigkeitszeit
Die Untätigkeitszeit Tidle (idle time) eines Systems als Zeit, die mit Warten (auf zu empfangende oder sendende Nachrichten) verbracht wird → Prozessblockierung trägt zur Untätigskeitszeit bei!
62 / 84

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

Maßzahlen für Parallele Systeme

Es gilt (bei N Prozessen):

Ttot=Tcomp+Tcomm+Tidle1/Ni=1..nTcomp,i+Tcomm,i+Tidle,i

63 / 84

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

Maßzahlen für Parallele Systeme

Übertragungszeit
Die Übertragunszeit Tmsg (message time) ist die Zeit, die für das Übertragen einer Nachricht mit der Länge L Datenwörter zwischen zwei Prozessen oder Prozessoren benötigt wird.
  • Sie setzt sich aus einer Startzeit Ts (message startup time) und einer Transferzeit Tw für ein Datenwort zusammen.
  • Es gilt: Tmsg = Ts + LTw
  • Voraussetzung: Verbindungsnetz arbeitet konfliktfrei.
64 / 84

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

Maßzahlen für Parallele Systeme

Startzeit
Die Startzeit wird durch die Kommunikationshard- und software bestimmt, die zur Initiierung eines Datentransfers benötigt wird, z.B. Overhead des Protokollstacks bei einer Software-Implementierung.
Transferzeit
Die Transferzeit wird durch die Bandbreite des Kommunikationsmediums und zusätzlich bei Software-Implementierung durch den Protokollstack (Datenkopie) bestimmt.
65 / 84

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

Maßzahlen für Parallele Systeme

Parallelisierungsgrad P
Die maximalze Anzahl von binären Stellen (bits) pro Zeiteinheit (Taktzyklus) die von einer Datenverarbeitungsanlage verarbeitet werden kann.
  • Es gilt: P = WB
Wortlänge W
Die Wortlänge oder Wortbreite gibt die Anzahl der Bits eines Datenpfades an.
Bitslice-Länge B
Die Bitslice-Länge setzt sich zusammen aus der Anzahl von Verarbeitungseinheiten VE, die parallel ausgeführt werden können, und der Anzahl der Pipeline-Stufen einer VE.
  • Es gilt: B = NVENStages
66 / 84

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

Maßzahlen für Parallele Systeme

Illustration Parallelisierungsgrad und Beispiel

67 / 84

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

Maßzahlen für Parallele Systeme

Beschleunigung S und Kosten C
Die Beschleunigung gibt die Steigerung der Verabeitungsgeschwindigkeit bzw. die Re-duzierung der Verarbeitungszeit T an beim Übergang Anzahl Prozessoren N=1 → N>1. Die Kosten C skaliert die Verarbeitungszeit (Komplexitätsklasse) mit den Ressourcen.

S(N)=T(1)T(N),C(N)=T(N)N

68 / 84

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

Maßzahlen für Parallele Systeme

Effizienz E
Die Effizienz gibt die relative Verbesserung in der Verarbeitungsgeschwindigkeit an, da die Leistungssteigerung S mit der Anzahl der Prozessoren normiert wird.

E(N)=S(N)N, mit 1NE(N)1

69 / 84

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

Maßzahlen für Parallele Systeme

Mehraufwand R
Bezieht sich auf die Anzahl X der auszuführenden (Einheits-)Operationen des Programms:

R(N)=X(N)X(1)

Parallelindex I
Der Parallelindex gibt die Anzahl der parallelen Operationen pro Zeit-/Takteinheit an.

I(N)=X(N)T(N)

70 / 84

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

Maßzahlen für Parallele Systeme

Auslastung U
Entspricht dem normierten Parallelindex:

U(N)=I(N)N

71 / 84

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

Maßzahlen für Parallele Systeme

Beispiel zur Auslastung

Ein Einprozessorsystem benötigt für die Ausführung von 1000 Operationen genau 1000 (Takt-)Schritte. Ein Multiprozessorsystem mit 4 Prozessoren benötigt dafür 1200 Operationen, die aber insgesamt in 400 Schritten ausgeführt werden können:

X(1)=1000 und T(1)=1000, X(4)=1200 und T(4)=400
S(4)=2.5 und E(4)=0.625,I(4)=3 und U(4)=0.75

Im Mittel sind 3 Prozessoren gleichzeitig aktiv, da jeder Prozessor nur zu 75% ausgelastet ist!

72 / 84

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

Amdahl’s Gesetz

Eine kleine Zahl von sequenziellen Operationen kann den Performanzgewinn durch Parallelisierung signifikant reduzieren.

  • Sequenzieller Anteil der Berechnungszeit T eines Algorithmus in [%]: η

  • Paralleler Anteil dann: (1-η)

  • Kommunikation (Synchronisation) zwischen nebenläufig ausgeführten Tasks oder Verarbeitungseinheiten verursacht immer η>0!

    • Beispiel: Schutz einer geteilten Ressource mit einer Mutex.
    • Beispiel: Datenverteilung über eine Queue
73 / 84

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

Amdahl’s Gesetz

  • Zugriff auf geteilte Ressourcen verursacht immer η>0!

    • Beispiel: Geteilte Ressource Hauptspeicher in einer PRAM
  • Der Kommunikationsanteil ist schwer im Voraus abzuschätzen, und der genaue Wert hängt auch von temporalen Konkurrenzverhalten ab (wie häufig gibt es verlorene Wettbewerbe)!

Das Amdahlsche gesetzt gilt nur für Probleme mit fester Größe!

74 / 84

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

Amdahl’s Gesetz

  • Es gilt dann für die gesamte Berechnungszeit eines parallelen Systems:

T(N,η)=ηT(1)+(1η)T(1)N

  • Daraus lässt sich eine Obergrenze der Beschleunigung S mit zusätzlicher Abhängigkeit von η ableiten:

S(N,η)=T(1)T(N,η)N(ηN1)+1

75 / 84

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

Amdahl’s Gesetz

Beispiel

Ein Algorithmus mit einem sequenziellen Anteil von η=10% und einem parallelen Teil von 90% wird A.) mit N=10 Prozessoren, und B.) mit N=20 Prozessoren ausgeführt. Die Obergrenze der Beschleunigung S ist dann:

A.) S(10)=5.26
B.) S(20)=6.0
  • Verdopplung der Prozessoren erhöht nicht mehr signifikant die Beschleunigung!
76 / 84

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

Amdahl’s Gesetz

(Berechnung)

Beschleunigung S in Abhängigkeit von η und Anzahl der Prozessoren N

77 / 84

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

Simulation eines einfachen Systems

Simulation der Beschleunigung S in Abhängigkeit des Kommunikationsanteils η% bei N Prozessen und einem vollständigen Kommunikationsnetzwerkgraphen N:N

78 / 84

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

Gustafson's Gesetz

  • Amdahl's Gesetzt gilt bei Problemen mit fest vorgegebener Größe (also z.B. die Größe einer Matrix)

    • Für verteiltes Rechnen mit N > 1000 eine Katastrophe!
  • Aber die theoretische Begrenzung der Beschleunigung S gilt so nicht mehr für Probleme die mitwachsen

    • Einfach ausgedrückt: Die Hinzunahme von Prozessoren bei zunehmender Größe des Problems bringt i.A. einen Vorteil!
  • Es kann (min.) zwei Motivationen geben:

    • Die Rechenzeit soll effizient und wirtschaftlich reduziert werden
    • Die Rechenzeit soll beim Anwachsen des Problems (z.B. die Anzahl von WEB Seiten die eine Suchmaschine indizieren soll) nicht anwachsen (egal was es kostet, oder noch mit vertretbaren Kostenaufwand)!
79 / 84

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

Gustafson's Gesetz

Geschichte

C

In einer Konferenzdebatte von 1967 über die Verdienste von Parallelen Rechnen, IBM's Gene Amdahl argumentiert, dass ein wesentlicher Anteil der Arbeit von Computern inhärent seriell ist, sowohl aus algorithmischen als auch aus architektonischen Gründen.

Er schätzte die serielle Fraktion f auf etwa 0.25-0.45. Er behauptete, dass dies den Ansatz stark einschränken würde parallele Verarbeitung zur Reduzierung der Ausführungszeit einzusetzen.

Amdahl argumentierte, dass selbst die Verwendung von zwei Prozessoren weniger kosteneffektiv als ein serieller Prozessor. Außerdem, die Verwendung einer großen Anzahl von Prozessoren würde niemals die Ausführungszeit um mehr als 1/f reduzieren, was durch seine Schätzung ein Faktor von etwa 2-4 war.

Trotz vieler Bemühungen, einen Fehler in Amdahls Gesetz zu finden, ist Amdahls Gesetz seit über 20 Jahren die Begründung für die fortgesetzte Verwendung von seriellem Rechnern und seriellen Programmiermodellen.

80 / 84

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

Gustafson's Gesetz

  1. Die Zeit die ein Nutzer auf eine Berechnung warten will sei konstant (Einheitswert, P=1)
  2. Der Anteil der Berechnung der seriell ist sei f, und unabhängig von der Parallelisierung (Stimmt das wirklich??)
    • Der serielle Anteil kann mit zunehmender Problemgröße (relativ!) abnehmen!
  3. Der verbleibende Anteil 1-f parallelisiert ideal so dass ein serieller Prozessor P mal länger braucht um diesen zu berechnen (P: Anzahl der Prozessoren)
  4. Das Verhältnis der parallelen zur seriellen Berechnung ist dann:

S=1f+P(1f)

81 / 84

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

Gustafson's Gesetz

C Vergleich paralleler zu serieller Berechnung

82 / 84

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

Gustafson's Gesetz

C (a) Beschleunigung S möglich mit 32 Prozessoren in Abhängigkeit vom parallelen Anteil, Gustafson’s vs Amdahl’s Gesetz (b) Verschiedene Skalierungstypen und Kommunikationskosten sowie Randbedingungen[]

83 / 84

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

Zusammenfassung

Parallele Programme können sich auf unterschiedliche Weise entwickeln. Zustandsraum Diagramme verdeutlichen die möglichen Entwicklungen von parallelen Systemen.

Es gibt eine Vielzahl von metrischen Größen um parallele und verteilte Systeme messbar und vergleichbar zu machen → Beschleunigung.

Es können Fehler in parallelen Systemen durch Wettrennen und Wettbewerbe auftreten: Deadlock, Starvation

Kommunikation ist der limitierende Faktor in der Parallelisierung.

84 / 84