Verteilte und Parallele Programmierung

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

Parallelisierung und Metriken


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
Räumliche Parallelität
Die Datenmenge D kann in Teilmengen diD 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‘’

Parallelität

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

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: ST1: a=x+y; ST2: b=a+1; b(a) ST2(ST1)
    • 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.

Datenabhängigkeit

figraumzeitpar


Abb. 1. Räumliche und zeitliche Datenabhängigkeit ⇔ Vertikalen und horizontale Parallelisierung

Rechenzeit

  • Die Rechenzeit ttot für die Ausführung einer Pipeline T1TM 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}
\]

als die Zeit die benötigt wird, einen Task i unter Berücksichtigung von Datenabhängigkeiten der ni Subtasks T(dj) zu bearbeiten.

Rechenzeit

  • Längste Bearbeitungszeit eines Subtasks bestimmt Bearbeitungszeit des Tasks τi!
  • Ti ist der i-te Task in der horizontalen Pipeline,
  • dj die Teildatenmenge eines Subtasks Ti,i(dj) eines Tasks Ti,
  • tcomp ist die Rechenzeit,
  • tcomm die Intertaskkommunikationszeit,
  • tin und tout die Zeit zum Datentransfer in und aus der Pipeline, und
  • td(Di,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 Di können daher von unterschiedlicher Größe und Art sein.

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

Klassifikation von parallelen Algorithmen

figpardatab


Abb. 2. Klassifikation nach Kommunikationsbedarf aufgrund Datenabhängigkeit zwischen einzelnen Tasks eines parallelen Programms
  • Weiterhin Klassifikation nach:
    • Eingabedatenabhängigkeit
    • Ergebnisabhängigkeit

Speedup

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 sN
  • 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)}
\]
  • Die sog. Skalierung bei der Parallelisierung ist i.A. nicht linear:
\[0 < S(N) < N
\]
  • Kommunikation ist weitere Randbedingung bei der parallelen Datenverarbeitung.

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
  • Partitionierung kann beliebig erfolgen, da die einzelnen Ergebniswerte Ci,j nicht voneinander abhängen.

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

Kosten und Laufzeit

  • Mögliche Partitionierungen der drei For-Schleifen auf N parallel arbeitenden Verarbeitungseinheiten (VE):
  1. Jede VE berechnet einen Ci,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.
  1. 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.

Kosten und Laufzeit

  1. 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 Ci,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.

Kosten und Laufzeit