Verteilte und Parallele Programmierung

PD Stefan Bosse
Universität Bremen, FB Mathematik & Informatik
SS 2020
Version 2020-06-10

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 S1,S2,.. zugeordnet.

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

figprodaconfluss

Abb. 1. Programm-, Kontroll-, und Datenflussgraphen

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

  1. Parallelität auf Bitebene (jegliche funktionale Operation)
  2. 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. 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 = i1 to i2 do
 2:   for j = j1 to j2 do 
 3:     ..
 4:     IB(i,j,x(i,j),x(i+1,j),..,);
 5:   end
 6: end
 7:  ----------------------------------------
 8:   IB(i1,j1,x(i1,j1),x(i1+1,j1),..) ‖
 9:   IB(i1+1,j1,x(i1+1,j1),x(i1+2,j1),..) ‖
10:   IB(i1+n,ij+m,x(i1+n,ij+m),x(i1+n+1,j1+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 ISb(ISb-1(ISb-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

figimgconv

Abb. 2. Algorithmus: Transformation von Farb- in Grauwertbilder [2]

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

figimgmean

Abb. 3. Komplexitätsreduktion durch Separation der Operatoren: (1) Alle Zeilenoperationen werden parallel ausgeführt (2) Alle Spaltenoperationen werden parallel ausgeführt

figimgmeanalg

Abb. 4. Algorithmus: Parallele Nachbarschaftsberechnung

Parallelisierungsmethoden

Basisblock Optimierer und Scheduler

  • Nebenläufigkeits- und Datenabhängigkeitsanalyse

  • Ziele: Reduktion von Zeitschritten, Minimierung der Latenz, Parallelisierung

  1. Basisblöcke sind Bereiche im Programmflussgraphen, die nur einen Kontrollzugang am Kopf und nur einen Kontrollausgang am Ende haben, und keine weiteren Seiteneingänge.
  2. 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)
  3. Es werden Datenabhängigkeitsgraphen für jeden Major-Block erstellt.
  4. 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

fignodejs-eventloop

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

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