PD Stefan Bosse - VPP - Modul F: Parallelisierung von Algorithmen und Programmen

Verteilte und Parallele Programmierung

Mit Virtuellen Maschinen

PD Stefan Bosse

Universität Bremen - FB Mathematik und Informatik

1 / 40

PD Stefan Bosse - VPP - Modul F: Parallelisierung von Algorithmen und Programmen

Parallelisierung von Algorithmen und Programmen

Wie können Algorithmen und Programmen parallelisiert werden?

Wann ist Kontrollpfadparallelität sinnvoll?

Was unterscheidet Datenpfad- von Kontrollpfadparallelität?

Unterschied zwischen Koroutinen, Threads, und Prozessen

Asynchrone vs. Synchrone Verarbeitung

2 / 40

PD Stefan Bosse - VPP - Modul F: Parallelisierung von Algorithmen und Programmen

Parallelisierungsmethoden

Sequenzielle Schleifen und Abrollung

  • Schleifen stellen eine reine Sequenz von elementaren Prozessen dar (parametrisierbare Replikate): I=i1→i2→ ...

  • Das Abrollen von Schleifen ist eine der gängigsten Parallelisierungsmethoden bei der Schleifen durch Replikation der Schleifeninstruktionen (Schleifenkörper) in eine sequenzielle und parallelisierbare Anweisungssequenz

    • teilweise (partitioniert)
    • oder vollständig transformiert werden.

  • Dabei wird der Schleifenkörper B(I,p) in Abhängigkeit von der Iterationsvariable p parametrisiert

  • Kontrollpfaparallelität durch Partitionierung: Jede Instanz oder eine Menege von B(pi) kann einem separaten Prozess Pi zugeordnet werden
3 / 40

PD Stefan Bosse - VPP - Modul F: Parallelisierung von Algorithmen und Programmen

Parallelisierungsmethoden

for i = i1 to i2 do
  for j = j1 to j2 do 
    ..
    IB(i,j,x(i,j),x(i+1,j),..,);
  end
end
──────────────────────────
IB(i1,j1,x(i1,j1),x(i1+1,j1),..) ||
IB(i1+1,j1,x(i1+1,j1),x(i1+2,j1),..) ||
IB(i1+n,ij+m,x(i1+n,ij+m),x(i1+n+1,j1+m),..) ||
..

Schleifenparallelität und mögliche Parallelisierung (von Datenabhängigkeit verschiedener Instanzen Bi begrenzt)

4 / 40

PD Stefan Bosse - VPP - Modul F: Parallelisierung von Algorithmen und Programmen

Parallelisierungsmethoden

  • Zu beachten sind Datenabhängigkeiten zwischen einzelnen Anweisungsiterationen und Kosten durch die Abrollung (Overhead)

  • Beispiel: Abrollbar aber nicht parallelisierbar durch Datenabhängikeit ISb(ISb-1(ISb-2(..)) !

X := 1;
for i = a to b do
  IS: X := X*i;
end
5 / 40

PD Stefan Bosse - VPP - Modul F: Parallelisierung von Algorithmen und Programmen

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 → Datenpfadparallelität.

  • Anstelle der iterativen Berechnung mittels Schleifen definiert man deklarativ die Berechnung eines Pixels (Punktoperator) oder eines Bereiches des Bildes (Lokaloperator):

6 / 40

PD Stefan Bosse - VPP - Modul F: Parallelisierung von Algorithmen und Programmen

Parallelisierungsmethoden

img' = F(img):: = { f(x)|x ∈ img }
──────────────────────────
procedure F (img: vector of type):
begin
  return f(img)
end

Deklarative Beschreibung von Vektoroperationen

7 / 40

PD Stefan Bosse - VPP - Modul F: Parallelisierung von Algorithmen und Programmen

Parallelisierungsmethoden

Beispiel Punktoperator