5.7.2.4 Der Grobgitterlöser

Das eigentliche Parallelisierungsproblem in (Multilevel- und) Mehrgitterverfahren ist das exakt zu lösende Grobgitterproblem

$$\pmb{\sum\limits_{s=1}^P} A_{s,1}^T {\ensuremath{\color{gre... ...derline{{\ensuremath{\color{green} {\sf f}} }}_{s,1} \enspace.$$ (5.10)

Folgende Lösungsansätze sind denkbar und werden verwendet :

1.

Direkter Löser - seriell

Gröbstes Gitter ist so klein, daß es ein Prozessor  $\ensuremath{\mathbb{P} } _0$ zusätzlich speichern kann.
Assemblierung  ${\ensuremath{\color{green} {\sf K}} }_1$ ( REDUCE).
Assemblierung  $\underline{{\ensuremath{\color{green} {\sf f}} }}_1$ ( REDUCE).
Prozessor  $\ensuremath{\mathbb{P} } _0$ löst ${\ensuremath{\color{red} \mathfrak{K} } }_1\cdot\underline{{\ensuremath{\color{... ...athfrak{u} } }}_1 \,=\, \underline{{\ensuremath{\color{red} \mathfrak{f} } }}_1$ .
Verteilen von $\underline{{\ensuremath{\color{red} \mathfrak{u} } }}_1$ ( SCATTER).

Diese Vorgehen ist allerdings rein sequentiell !!

2.

Direkter Löser - parallel

Auch das gröbste Gitter wird verteilt gespeichert und das Grobgittersystem direkt parallel gelöst. Im Auflösungsprozeß treten Loadinbalancen auf.

3.

Iterative Löser - parallel

Hier wird keine Assemblierung von ${\ensuremath{\color{green} {\sf K}} }_1$ und $\underline{{\ensuremath{\color{green} {\sf f}} }}_1$ benötigt, jedoch tritt in jedem Iterationsschritt mind. eine Akkumulation auf (siehe 5.1 - 5.6).

Achtung : Die evtl. beabsichtigte Symmetrie des Multigridoperators wird bei den CG-ähnlichen Verfahren zerstört. Um sie zu erhalten, muß z.B. eine lexikographisch vorwärtige Gauß-Seidel Iteration stets mit einer rückwärtigen gekoppelt werden.

Prinzipiell ergibt sich beim Grobgitterlöser durch das ungünstige Verhältnis von Arithmetik zu Kommunikation eine Verschlechterung der Parallelisierung. Dies äußert sich bei 32 und mehr Prozessoren ganz deutlich im W-Zyklus , der sehr oft auf die groben und insbesondere das gröbste Gitter zugreift.
Ein Lösungsversuch besteht in der Verteilung des Grobgitters auf weniger als $P$ Prozessoren, jedoch ist dann bei der Interpolation und Restriktion zwischen bestimmten Gittern $\ell_0$ und  $\ell_0 + 1$ Kommunikation notwendig.

Kommunikation im Grobgitterlöser !