Verteilte und Parallele Programmierung

Parallelisierung

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.
Programmfluss: Der Programmfluss setzt sich kombiniert aus Daten- und Kontrollfluss zusammen.

Parallelisierungsklassen

Programmanweisungen werden Zuständen S₁,S₂,.. zugeordnet.
Einfache Anweisungen (Berechnungen) werden jeweils einem Zustand, komplexe Anweisungen i.A. mehreren Unterzuständen zugeordnet.

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

Parallelisierungsklassen

Zur Ausnutzung der Datenparallelität wurden sequentielle Programmiersprachen zu datenparallelen Programmiersprachen erweitert. Diese verwenden wie sequentielle Programmiersprachen einen Kontrollfluss, 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.
Beispiel für eine deklarative Vektoranweisung und die dazugehörige imperative Anweisungssequenz in Schleifenform (Fortran 90):

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

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

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

Datenparallelität benötigt i.A. keine weitere Synchronisation

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 Programmier- und Ausführungsmodell (z.B. pthreads)
Instruktionsparallelität benötigt i.A. Synchronisation zwischen den einzelnen Prozessen

Parallelisierungsklassen

Möglichkeiten der Parallelisierung

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

Parallelisierungsmethoden

Abrollung von Schleifen

Das Abrollen von Schleifen ist eine der gängigsten Parallelisierungsmethoden bei der Schleifen durch Replikation der Schleifeninstruktionen (Schleifenkörper) in eine paralellisierbare Anweisungssequenz
- teilweise
- oder vollständig transformiert werden.

Definition 1. (Schleifenparallelität )

 1: for i = i₁ to i₂ do
 2:   for j = j₁ to j₂ do 
 3:     ..
 4:     IB(i,j,x(i,j),x(i+1,j),..,);
 5:   end
 6: end
 7:  ----------------------------------------
 8:   IB(i₁,j₁,x(i₁,j₁),x(i₁+1,j₁),..) ‖
 9:   IB(i₁+1,j₁,x(i₁+1,j₁),x(i₁+2,j₁),..) ‖
10:   IB(i₁+n,ij+m,x(i₁+n,ij+m),x(i₁+n+1,j₁+m),..) ‖
11:   ..

Parallelisierungsmethoden

Zu Beachten sind Datenabhängigkeiten zwischen einzelnen Anweisungsiterationen und Kosten durch die Abrollung (Overhead)
Beispiel: Nicht abrollbar und parallelisierbar durch Datenabhängikeit IS_b(IS_b-1(IS_b-2(..)) !

1: X := 1;
2: for i = a to b do
3:   IS: X := X*i;
4: end

Parallelisierungsmethoden

Deklarative Beschreibung von Vektoroperationen

In der Bildverarbeitung werden Vektoroperationen (und Matrixoperationen) sehr häufig verwendet. Dabei werden häufig die gleichen Operationen auf alle Pixel eines Bildes (Feldelemente) angewendet.
Anstelle der iterativen Berechnung mittels Schleifen definiert man deklarativ die Berechnung eines Pixels (Punktoperator) oder eines Bereiches des Bildes (Lokaloperator):

Definition 2.

$img' = F(img):: = \{ f(x)|x \in img\}$

1: procedure F (img: vector of type):
2: begin
3:   return f(img)
4: end

Parallelisierungsmethoden

Beispiel Punktoperator

Parallelisierungsmethoden

JavaScript und Lua

JavaScript (und andere funktionalen Programmiersprachen) arbeiten intensiv mit Listen und Arrays
Listen und Arrays lassen sich mittels eines Abbildungsoperators und einer Elementfunktion (Punktoperator) transformieren (map-and-reduce)

Parallelisierungsmethoden

Lokaloperatoren

Lokale Operatoren sind rechenintensiver als Punktoperatoren. Um ein neues Pixel zu berechnen wird der alte Wert des Pixels sowie die alten räumlich benachbarten Werte der Pixel innerhalb einer definierten maximalen Entfernung verwendet.
Für eine 3x3-Nachbarschaftsberechnung werden zum Beispiel Neun Datenwerte für jedes Pixel benötigt.
Für die Berechnung lokaler Operatoren wird eine bestimmte Anzahl von parallelen Datenaustauschvorgängen benötigt → Kommunikation.
Wenn jedes Pixel auf einem anderen Prozessor gespeichert wird ist Kommunikation teuer!

Parallelisierungsmethoden

Beispiel Lokaloperator

Parallelisierungsmethoden

Basisblock Optimierer und Scheduler

Nebenläuﬁgkeits- und Datenabhängigkeitsanalyse
Ziele: Reduktion von Zeitschritten, Minimierung der Latenz, Parallelisierung

Basisblöcke sind Bereiche im Programmﬂussgraphen, die nur einen Kontrollzugang am Kopf und nur einen Kontrollausgang am Ende haben, und keine weiteren Seiteneingänge.
Ein Basisblock der nur aus Datenanweisungen besteht ist ein Major-Block. Dieser wird in elementare Minor-Blöcke zerlegt, die wenigstens eine Anweisung enthalten (bei einem gebunden Block der ganze Block)
Es werden Datenabhängigkeitsgraphen für jeden Major-Block erstellt.
Nicht abhängige Anweisungen werden durch einen Scheduler mit ASAP-Verhalten in einen gebundenen Block (paralleler Prozess) zusammengefasst.

Funktionale Programmierung

Determinismus macht paralleles Auswerten der Argumente und Parallelisierung bei Rekursion möglich
Parameter von Funktionen sind datenunabhängig → Parallele Evaluierung der Funktionsargumente bei der Funktionsapplikation
Funktionsaufrufe sind gänzlich oder partiell datenunabhängig → Parallelisierung der Funktionsaufrufe (Endrekursion, Kopfrekursion bringt kein Vorteil)

Probleme:
- Argumente haben teils kein ausreichendes Potential (Ausdrücke zu einfach und zu flach)
- Große Rekursionstiefen können zu einer zu feinen Aufteilung führen → nicht gut auf Prozessoren aufzuteilen

Asynchrone Ereignisverarbeitung

Neben der Parallelisierung der reinen Datenverarbeitung (Berechnung) kann auch eine Partitionierung von Ein- und Ausgabe bzw. der Ereignisverarbeitung erfolgen
Bekanntes Beispiel: Geräteinterrupts mit einfachen Foreground-Background System mit zwei Prozessen:
- P1: Hohe Priorität (Ereignisverarbeitung → Interrupthandler → Foreground Prozess)
- P2: Niedrige Priorität (Berechnung → Hauptprogramm → Background Prozess) mit Preemption durch Ereignisverarbeitung
Ein- und Ausgabeoperationen eines Programms können synchron (blockierend) oder asynchron (im Hintergrund verarbeitet und nicht blockierend) ausgeführt werden.

Asynchrone Ereignisverarbeitung

Beispiel Lua

Synchrone Operationen liefern das Ergebnis in einer Datenanweisung zurück die solange blockiert wird bis das Ereignis eintritt(Ergebnisdaten verfügbar sind). Dabei werden zwei aufeinander folgende Operationen sequenziell ausgeführt, und eine folgende Berechnung (nicht ereignisabhängig) erste nach den Ereignissen ausgeführt:

x = IO1(arg1,arg2,..);
y = IO2(arg1,arg2,..);
z = f(x,y);

Asynchrone Ereignisverarbeitung

Bei der asynchronen (nebenläufigen) Ausführung von ereignisabhängigen Operationen wird das Ergebnis über eine Callback Funktion verarbeitet. Die IO Operation blockiert nicht. Vorteil: Folgende Berechnungen können unmittelbar ausgeführt werden.

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

Asynchrone Ereignisverarbeitung

Asynchrone Ereignisverarbeitung

Synchronisation

Asynchrone Ereignisverarbeitung mit preemptiven 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:

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