6.1.3 Givensrotation auf dem Parallelrechner

Bezeichne $g(k,s)$ die Givensrotation der Zeilen $k-1$ und $k$ und der Spalte $s$ .

Hierbei tritt folgende Datenabhängigkeit auf :

  

Abbildung 6.1: Statische Datenabhängigkeit Givensrotation

Die statische Datenabhängigkeit von Bild 6.1 wandeln wir durch sogenannte Marker $\ast$ in ein dynamisches Datenflußkonzept um, miteiner beliebigen Anzahl von Prozessoren.

Sei in $m(k,s)$ die Anzahl der Marken für den Prozeß $g(k,s)$.

$m(k,s) = 2$ $\Longrightarrow$ Prozeß $g(k,s)$ startet.

Anfangswerte :

$m(n,1) := 2$
$m(k,1) := 1$	$k<n$
$m(k,s) := 0$	$s>1$

Bei gemeinsamem Speicher ergibt sich der Datenfluß in Bild 6.2

  

Abbildung 6.2: Datenfluß bei gemeinsamem Speicher : Givensrotation

Nach Abschluß von Prozeß $g(k,s)$ werden $m(k-1,s)$ und  $m(k+1,s+1)$ jeweils um $1$ erhöht.

Haben die Prozessoren jedoch nur Zugriff zu ihrem Teil des verteilten Speichers, müssen noch die Abhängigkeiten zwischen den Prozessoren untersucht werden. Hierbei bietet sich eine blockzeilenweise Aufteilung der Matrix $A$ an, was in Bild 6.3 dokumentiert wird.

  

Abbildung 6.3: Datenfluß bei verteiltem Speicher : Givensrotation

Bemerkung : Eine analoge Aufteilung der Zeilen ist auch beim Gaußalgorithmus denkbar.