6.1.3 Givens rotation on a parallel computer

Denote by $g(k,s)$ the Givens rotation of rows $k-1$ and $k$ in column $s$ .

The following data dependencies occur :

Figure 6.1: Static data dependencies in the Givens rotation

We transform the static data dependency in Fig. 6.1 by means of markers $\ast$ into a dynamic data flow chart with an arbitrary number of processors.

Let $m(k,s)$ the number of markers for process $g(k,s)$.

$m(k,s) = 2$ $\Longrightarrow$ process $g(k,s)$ starts.

Initial values :

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

On a shared memory computer, we achieve the flow chart in Fig. 6.2

Figure 6.2: Flow chart on a shared memory computer : Givens rotation

The markers $m(k-1,s)$ and  $m(k+1,s+1)$ are incremented after process $g(k,s)$ has finished.

If the processors have only access on a part of the distributed memory then we have to investigate the data dependencies between the processors. Here, a rowise distribution of blocks of matrix $A$ is preferred, see Fig. 6.3.

Figure 6.3: Flow chart on a distributed memory computer: Givens rotation

Remark : A similar distribution of rows can also be uses in the Gauß elimination.