Stefan Bosse - VPP - Modul F 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?

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Zustands-Raum Diagramme

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.

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Zustands-Raum Diagramme

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

• Der Zustand S eines parallelen Programms welches aus N Prozessen P_i 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: s_i → s_j.

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Nebenläufige Programmierung: Zustands-Raum Diagramme

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Nebenläufige Programmierung: Zustands-Raum Diagramme

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!

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Nebenläufige Programmierung: Zustands-Raum Diagramme

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:

$$\frac{\begin{gathered} (WRITE(x,{v_1}) \to {p_1})\parallel \hfill \\ (WRITE(x,{v_2}) \to {p_2}) \hfill \ \end{gathered} }{\begin{gathered} (WRITE(x,{v_1}) \to (WRITE(x,{v_2}) \to ({p_1}\parallel {p_2})))| \hfill \\ (WRITE(x,{v_2}) \to (WRITE(x,{v_1}) \to ({p_1}\parallel {p_2})))| \hfill \ .. \hfill \\ \end{gathered} }$$

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Nebenläufige Programmierung: Zustands-Raum Diagramme

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Nebenläufige Programmierung: Zustands-Raum Diagramme

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.

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Nebenläufige Programmierung: Zustands-Raum Diagramme

Nebenläufige Programmierung: Zustands-Raum Diagramme

• Das Diagramm ist ein gerichteter Graph, dessen Knoten den aktuellen Programmzustand s ∈ S 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.

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Nebenläufige Programmierung: Zustands-Raum Diagramme

Algorithmus: Entwicklung des Zustands-Raum Diagramms

• Parallelen Programms welches aus N Prozessen P={p₁,p₂,..,p_N} besteht.

1. Initialisiere den Startzustand s_x=s₀ und erzeuge Wurzel-Knoten s₀ im Diagramm.

2. Aktueller Zustand: s_x. Setze P*:=P mit P={p₁,p₂,..,p_N} als Prozessliste und S*={}

3. Wähle (entferne) einen beliebigen Prozess p_x aus der Prozessliste P* und setze P*:= {p_n| p_n ∈ P* ∧ p_n ∉ p_x}

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Nebenläufige Programmierung: Zustands-Raum Diagramme

Nebenläufige Programmierung: Zustands-Raum Diagramme

4. Evaluiere die nächste Instruktion i_x,n von p_x und berechne die Wirkung auf lokale und globale Variablen sowie den Instruktionszeiger I_x,n.

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

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

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Nebenläufige Programmierung: Zustands-Raum Diagramme

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Nebenläufige Programmierung: Zustands-Raum Diagramme

Nebenläufige Programmierung: Zustands-Raum Diagramme

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Globale Ressourcen und Synchronisation

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.

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Globale Ressourcen und Synchronisation

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|

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Globale Ressourcen und Synchronisation

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| ??

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Globale Ressourcen und Synchronisation

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Globale Ressourcen und Synchronisation

Globale Ressourcen und Synchronisation

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Globale Ressourcen und Synchronisation

Experiment

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Globale Ressourcen und Synchronisation

Globale Ressourcen und Synchronisation

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

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={p₁,p₂,...} auf einer Semaphore S angewendet werden können:

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Globale Ressourcen und Synchronisation

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Globale Ressourcen und Synchronisation

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 i₁,i₂,i₃, ... ein, und ein UP(S) gibt ihn wieder frei:

semaphore S(1)
... down(S) |i1,i2,i3,..,in)| up(S) ...

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Globale Ressourcen und Synchronisation

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Globale Ressourcen und Synchronisation

Globale Ressourcen und Synchronisation

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Eigenschaften von Parallelen Systemen

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.

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Eigenschaften von Parallelen Systemen

Eigenschaften von Parallelen Systemen

Eigenschaft (Liveness) Lebendigkeit → Starvation Freiheit

• Starvation Freiheit bedeutet dass ein Prozess p_i 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).

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Eigenschaften von Parallelen Systemen

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!

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Eigenschaften von Parallelen Systemen

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.

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Eigenschaften von Parallelen Systemen

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.

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Eigenschaften von Parallelen Systemen

Eigenschaften von Parallelen Systemen

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Eigenschaften von Parallelen Systemen

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.

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Eigenschaften von Parallelen Systemen

Eigenschaften von Parallelen Systemen

Deadlocksituation zweier Prozesse die wechselseitig gesperrte Ressourcen anfordern

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Eigenschaften von Parallelen Systemen

Experiment

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Parallelität

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Parallelität

Parallelität

Räumliche Parallelität

Die Datenmenge D kann in Teilmengen d_i ⊃ D 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 ⇒ D₁ ⇒ Objekterkennung ⇒ D₂

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Datenabhängigkeit

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: ST₁: a=x+y; ST₂: b=a+1; → b(a) → ST₂(ST₁)

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Datenabhängigkeit

Datenabhängigkeit

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Rechenzeit

Rechenzeit

• Die Rechenzeit t_tot für die Ausführung einer Pipeline T₁...T_M 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.

$$\begin{gathered} {t_{tot}} = \sum\limits_{i = 1}^m {{\tau _i} + \sum\limits_{i = 1}^{m - 1} {{t_d}({D_{i,i + 1}}} ) + {t_{in}} + {t_{out}}} \hfill \\ {\tau _i} = \max \{ {t_{comp}}({T_{i,j}}({d_j}))|1 \leqslant j \leqslant {n_i}\} + {t_{comm}}({T_i}) \hfill \\ \end{gathered}$$

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Rechenzeit

Rechenzeit

• Längste Bearbeitungszeit eines Subtasks bestimmt Bearbeitungszeit des Tasks τ_i!
• T_i ist der i-te Task in der horizontalen Pipeline,
• d_j die Teildatenmenge eines Subtasks T_i,i(d_j) eines Tasks T_i,
• t_comp ist die Rechenzeit,
• t_comm die Intertaskkommunikationszeit,
• t_in und t_out die Zeit zum Datentransfer in und aus der Pipeline, und
• t_d(D_i,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 D_i können daher von unterschiedlicher Größe und Art sein.

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Klassifikation von parallelen Algorithmen

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.

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Klassifikation von parallelen Algorithmen

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.

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Klassifikation von parallelen Algorithmen

Klassifikation von parallelen Algorithmen

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

• Weiterhin Klassifikation nach:
  • Eingabedatenabhängigkeit
  • Ergebnisabhängigkeit

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Speed-up

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) = \frac{Performanz(N)}{Performanz(1)}, S_t(n) = \frac{Rechnenzeit(1)}{Rechenzeit(N)}$$

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Speed-up

Speed-up

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

$${0}<{S}{\left({N}\right)}<{N}$$

• Kommunikation ist weitere Randbedingung bei der parallelen Datenverarbeitung.

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Kosten und Laufzeit

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Kosten und Laufzeit

Kosten und Laufzeit

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

• Datenabhängigkeit des Problems: Die Berechnung eines C_i,j Wertes hängt außerhalb der FOR-k-Schleife von keinem anderen Wert C_n,m mit n ≠ i und m ≠ j ab.

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Kosten und Laufzeit

Kosten und Laufzeit

• Mögliche Partitionierungen der drei For-Schleifen auf N parallel arbeitenden Verarbeitungseinheiten (VE):

1. Jede VE berechnet einen C_i,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.

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Kosten und Laufzeit

Kosten und Laufzeit

3. 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 C_i,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.

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Kosten und Laufzeit

Kosten und Laufzeit

Mögliche Partitionierungen der Matrixmultiplikation

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Kosten und Laufzeit

Kosten und Laufzeit

Kosten und Laufzeitanalyse der verschiedenen Parititionierungen

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Kommunikation

Kommunikation

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

Kommunikation Fall 1

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Kommunikation

Kommunikation

Kommunikation Fall 2

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Kommunikation

Kommunikation

Kommunikation Fall 3

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Kommunikation

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Kommunikation

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Kommunikation

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 A_1,j-Element besitzen werden dieses nach rechts verschieben.

• Alle VEs die ein B_i,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.

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Kommunikation

Kommunikation

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Kommunikation

Kommunikation

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

• Die Kosten betragen Θ(n³), 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 3n² VEs.

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

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Kommunikation

Kommunikation

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

  • Dazu werden die Matrizen A, B und C überlagert, d.h. VE_1,1 ⇒ {A_1,1,B_1,1,C_1,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 Θ(n³)!

Stefan Bosse - VPP - Modul F Metriken und Verhalten von Parallelen Programmen :: Kommunikation

Kommunikation