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 di ⊃ 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.
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 ttot für die Ausführung einer Pipeline T1…TM enthält:
Zeit zum Einlesen der Daten I(n),
Zeit für die Ausgabe der Daten und Ergebnisse,
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 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
Weiterhin Klassifikation nach:
Eingabedatenabhängigkeit
Ergebnisabhängigkeit
Speedup
Bei der Datenverarbeitung gibt es drei Randbedingungen:
Gesamte Rechenzeit → Zeitdimension
Gesamte Ressourcenbelegung → Flächendimension
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 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):
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.
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
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.