PD Stefan Bosse - VPP - Modul F: Parallelisierung von Algorithmen und Programmen
Mit Virtuellen Maschinen
PD Stefan Bosse
Universität Bremen - FB Mathematik und Informatik
PD Stefan Bosse - VPP - Modul F: 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
PD Stefan Bosse - VPP - Modul F: Parallelisierung von Algorithmen und Programmen
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
Dabei wird der Schleifenkörper B(I,p) in Abhängigkeit von der Iterationsvariable p parametrisiert
PD Stefan Bosse - VPP - Modul F: Parallelisierung von Algorithmen und Programmen
for i = i1 to i2 do for j = j1 to j2 do .. IB(i,j,x(i,j),x(i+1,j),..,); endend──────────────────────────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)
PD Stefan Bosse - VPP - Modul F: Parallelisierung von Algorithmen und Programmen
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
PD Stefan Bosse - VPP - Modul F: Parallelisierung von Algorithmen und Programmen
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):
PD Stefan Bosse - VPP - Modul F: Parallelisierung von Algorithmen und Programmen
img' = F(img):: = { f(x)|x ∈ img }──────────────────────────procedure F (img: vector of type):begin return f(img)end
Deklarative Beschreibung von Vektoroperationen
PD Stefan Bosse - VPP - Modul F: Parallelisierung von Algorithmen und Programmen