5.1.2 Der parallelisierte CG

Wählt man in Algorithmus 5.1 $\;C=I$ erhält man den klassischen CG. Betrachtet man die darin enthaltenen Operationen und vergleicht sie mit den Ausführungen in Abschnitt 4.3.1, so kann man folgende Parallelisierungsstrategie aufbauen, wobei die Anzahl der notwendigen Kommunikationen möglichst klein gehalten werden soll.

  $\mbox{$\bullet$}$

Die Matrix $K$ muß als ${\ensuremath{\color{green} {\sf K}} }$ (4.1) verteilt (Typ-II) gespeichert werden, da im anderen Fall Einschränkungen an die Matrixstruktur erfolgen müssen.

$\Longrightarrow$

Vektoren $\underline{s}$, $\underline{u}$ $\rightarrow$ $\underline{{\ensuremath{\color{red} \mathfrak{s} } }}$, $\underline{{\ensuremath{\color{red} \mathfrak{u} } }}$ sind akkumuliert (Typ-I)
$\Longrightarrow$ Matrix-mal-Vektor liefert Typ-II Vektor, ohne daß Kommunikation notwendig ist (4.8).

$\Longrightarrow$

Vektoren $\underline{v}$, $\underline{r}$, $\underline{f}$ $\rightarrow$ $\underline{{\ensuremath{\color{green} {\sf v}} }}$, $\underline{{\ensuremath{\color{green} {\sf r}} }}$, $\underline{{\ensuremath{\color{green} {\sf f}} }}$ sind verteilt gespeichert (Typ-II) und werden im Verlauf der Iteration nicht akkumuliert.

$\Longrightarrow$

Wählt man auch $\underline{w}$ $\rightarrow$ akkumuliert, so lassen sich alle DAXPY-Operationen ohne Kommunikation durchführen.

  $\mbox{$\bullet$}$

Da in den beiden Skalarprodukte der CG-Schleife unterschiedliche Vektortypen verwendet werden, können diese Operationen mit sehr geringem Kommunikationsaufwand ausgeführt werden (4.7).

!!

Die Zuweisung $\underline{{\ensuremath{\color{red} \mathfrak{w} } }}\,:=\,\underline{{\ensuremath{\color{green} {\sf r}} }}$ beinhaltet eine Vektortypumwandlung mittels Akkumulation (4.5) und damit eine Kommunikation über die zu mehreren Prozessen gehörenden Daten.

 
Der resultierende parallele CG-Algorithmus 5.2 erfordert pro Iteration 2  ALL/SMALL>_REDUCE-Operationen mit einer reellen Zahl und eine Vektorakkumulation.

Man kann auch über andere Ansätze zu Algorithmus 5.2 gelangen, so sind z.B. die verteilt gespeicherten Vektoren $\underline{{\ensuremath{\color{green} {\sf f}} }}$, $\underline{{\ensuremath{\color{green} {\sf r}} }}$ und $\underline{{\ensuremath{\color{green} {\sf v}} }}$ identisch mit den funktionalen Größen im CG-Algorithmus (``Energie``). Eine Einteilung der Vektoren in funktionale Größen und Funktionswerte liefert einen guten Ansatz für die Zuordnung der 2 Vektortypen.

Bemerkung : Es gibt cg-Varianten, in denen beide Skalarprodukte und damit die entsprechende Kommunikationen zusammengefaßt werden können. Dadurch spart man eine Startup-Zeit ein. Jedoch sind diese Varianten unter Umständen instabil.

Zur Vorkonditionierungsproblematik siehe Abschnitt 5.8.