Verteilte und Parallele Programmierung

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 d_i ⊃ D 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: ST₁: a=x+y; ST₂: b=a+1; → b(a) → ST₂(ST₁)
  • 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

Rechenzeit

• Die Rechenzeit t_tot für die Ausführung einer Pipeline T₁…T_M 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.

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

Rechenzeit

• Längste Bearbeitungszeit eines Subtasks bestimmt Bearbeitungszeit des Tasks τ_i!
• T_i ist der i-te Task in der horizontalen Pipeline,
• d_j die Teildatenmenge eines Subtasks T_i,i(d_j) eines Tasks T_i,
• t_comp ist die Rechenzeit,
• t_comm die Intertaskkommunikationszeit,
• t_in und t_out die Zeit zum Datentransfer in und aus der Pipeline, und
• t_d(D_i,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 D_i 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

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

• Die sog. Skalierung bei der Parallelisierung ist i.A. nicht linear:

• 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 C_i,j nicht voneinander abhängen.

• Datenabhängigkeit des Problems: Die Berechnung eines C_i,j Wertes hängt außerhalb der FOR-k-Schleife von keinem anderen Wert C_n,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 C_i,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.

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

3. 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 C_i,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