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:

// 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:

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:

submit hpc session22 session22.tar