======================================================
Zweidimensionale Partitionierung beim Jacobi-Verfahren
======================================================

Wenn das Jacobi-Verfahren zweidimensional partitioniert werden soll,
müssen wir jeweils mit den unmittelbaren Nachbarn kommunizieren.
Bei einem mehrdimensionalen Gitter nennt uns MPI unsere Nachbarn:

---- CODE (type=cpp) ----------------------------------------------------------
// get the process numbers of our neighbors
int left, right, upper, lower;
MPI_Cart_shift(grid, 0, 1, &upper, &lower);
MPI_Cart_shift(grid, 1, 1, &left, &right);
-------------------------------------------------------------------------------

Die Funktion `MPI_Cart_shift` liefert die Nachbarn in einer der
Dimensionen. Der zweite Parameter ist die Dimension, der dritte
Parameter der Abstand (hier 1 für den unmittelbaren Nachbarn). Die
Prozessnummern der so definierten Nachbarn werden in den beiden
folgenden Variablen abgelegt. Wenn in einer Richtung kein Nachbar
existiert (z.B. am Rande einer Matrix), wird `MPI_PROC_NULL`
zurückgeliefert.

In jedem Iterationsschritt ist dann mit jedem der vier
Nachbarn beidseitig zu kommunizieren, wobei jeweils eine
Zeile bzw. Spalte auszutauschen ist. Insgesamt sind dies
acht Ein- und Ausgabe-Operationen. Die Latenzzeiten würden sich
sehr ungünstig addieren, wenn alle acht Operationen sequentiell
hintereinander ausgeführt werden. Sinnvoller ist es, diese
zu parallelisieren. Es bietet sich hier sogar an, die
Kommunikation und die Berechnung zu parallelisieren. Dies
geht mit folgendem Verfahren:

Gegeben seien die Matrizen $A$ und $B$, wobei $A$ den Stand
aus dem letzten Iterationsschritt hält und in $B$ der
nächste zu berechnende Stand abgelegt wird. Im weiteren wird
vom äußeren Rand gesprochen, wenn die Bereiche betrachtet
werden, die wir von unseren Nachbarn beziehen. Der innere
Rand ist derjenige, den wir an unsere Nachbarn weitergeben.
Dann könnte ein Iterationsschritt so aussehen:

 * Berechne den inneren Rand von $B$ in Abhängigkeit von $A$.
 * Initiiere folgende asynchronen Ein- und Ausgabe-Operationen:
    - Übertrage den inneren Rand an unsere vier Nachbarn.
    - Erhalte den äußeren Rand von unseren vier Nachbarn.
      (Anmerkung: Die Eckfelder lassen sich hier ignorieren,
      da sie nicht benötigt werden.)
 * Berechne den Teil innerhalb des inneren Rands von $B$.
 * Warte darauf, dass alle zuvor initiierten Ein- und
   Ausgabe-Operationen abgeschlossen sind.

Aufgabe
=======

Implementieren Sie das Jacobi-Verfahren mit
zweidimensionaler Partitionierung in der beschriebenen Weise.

Am Ende können Sie auch gerne Ihre Lösung wieder zu
einem tar-Archiv zusammenpacken und mit `submit` einreichen:

---- CODE (type=sh) -----------------------------------------------------------
submit hpc session22 session22.tar
-------------------------------------------------------------------------------

:navigate: up    -> doc:index
           back  -> doc:session22/page10
           next  -> doc:session22/page12