======================================
Grenzen und Umfang eines MPI-Datentyps
======================================

Wenn wir nicht den glücklichen Umstand haben, dass die Matrix
in `row major` mit `A.incCol == 1` vorliegt, wenn diese in
`row major` zu übertragen ist, dann ist es prinzipiell möglich,
den Datentyp einer Matrix in zwei Schritten zu erzeugen:

 * Vektor-Datentyp für eine Zeile bestimmen
 * Matrix als Vektor von Vektoren ansehen

Dabei ist jedoch zunächst unklar, wie MPI komplexe Datentypen
zu einem Vektor aneinanderreiht. Bei unmittelbar im Speicher
hintereinander liegenden Datentypen ist dies klar. Im Falle
einer `col major`-Matrix mit `A.incRow == 1` liegen die
Zeilen nicht konsekutiv hintereinander im Speicher, sondern
überlappen sich mit einem Versatz.

Um zu verstehen, wie MPI diese Dinge betrachtet, sollten
wir zur Definition eines Datentyps als Tupelsequenz zurückkehren:
$T = \left\{ (bt_1, o_1), (bt_2, o_2), \dots, (bt_n, o_n) \right\}$,

 * Für jeden Datentyp $T$ sein der Umfang $\mbox{extent}(T)$ definiert.
   Bei den elementaren Datentypen entspricht dies dem Wert,
   den `sizeof` liefern würde. Beispielsweise ist
   $\mbox{extent}(\mbox{MPI_DOUBLE}) = 8$.

 * Der _lower bound_ $\mbox{lb}$ ist definiert als
   $\mbox{lb}(T) = \min\limits_{1 \le i \le n} \left\{ o_i \right\}$.

 * Analog gibt es den _upper bound_ $\mbox{ub}$, der jedoch den
   Umfang mit berücksichtigt:
   $\mbox{ub}(T) = \max\limits_{1 \le i \le n} \left\{ o_i + \mbox{extent}(bt_i) \right\} + \epsilon$.
   Hierbei dient $\epsilon$ der Aufrundung auf die nächste
   Alignment-Kante.

 * Dann lässt sich $\mbox{extent}$ allgemein definieren:
   $\mbox{extent}(T) = \mbox{ub}(T) - \mbox{lb}(T)$.

Angenommen, wir hätten eine $2 \times 3$-Matrix in _col major_.
Der Datentyp $R$ für die erste Zeile würde dann so aussehen:
$R = \left\{ (DOUBLE, 0), (DOUBLE, 16), (DOUBLE, 32) \right\}$. Dann
ist $\mbox{lb}(R) = 0$, $\mbox{ub}(R) = 40$ und
$\mbox{extent}(R) = \mbox{ub}(R) - \mbox{lb}(R) = 40$.
Würden wir jetzt zwei solche Zeilen zu einem Vektor kombinieren,
wäre das erste absolute Offset des zweiten Zeilenvektors 40,
obwohl dieser bei 8 beginnt.

Die MPI-Bibliothek erlaubt es, von der voreingestellten
Berechnung mit Hilfe der Funktion
`MPI_Type_create_resized` abzuweichen:

---- CODE (type=cpp) ----------------------------------------------------------
int MPI_Type_create_resized(MPI_Datatype oldtype, MPI_Aint lb,
                            MPI_Aint extent, MPI_Datatype* newtype);
-------------------------------------------------------------------------------

Hierbei spezifiziert `lb` die neue untere Grenze $\mbox{lb}(T)$ und
`extent` den Umfang $\mbox{extent}(T)$, der in Bytes zu spezifizieren ist.
Daraus ergibt sich dann implizit auch $\mbox{ub}(T)$. Es ist dabei zulässig,
den Umfang zu wählen, dass zwei "konsekutiv" folgende Objekte sich
überlappen. Im obigen Beispiel der _col major_-Matrix wäre es
entsprechend sinnvoll, dem Umfang auf 8 Bytes zu setzen, da
`&A(0, 0)` und `&A(1, 0)` nur 8 Bytes voneinander entfernt sind.

Im Trivialfall, dass alle Elemente eines Vektors unmittelbar
hintereinander liegen, kann auch `MPI_Type_contiguous`
verwendet werden:

---- CODE (type=cpp) ----------------------------------------------------------
int MPI_Type_contiguous(int count, MPI_Datatype oldtype,
                        MPI_Datatype* newtype);
-------------------------------------------------------------------------------

Aufgabe
=======

 * Entwickeln Sie eine Funktion `get_row_type`, die den
   MPI-Datentyp für die Zeile einer Matrix liefert, wobei
   mit Hilfe der Funktion `MPI_Type_create_resized` der
   Umfang so konfiguriert wird, dass der gleiche Datentyp
   für aufeinanderfolgende Zeilen einer beliebigen Matrix
   verwendet werden kann. `lb` kann dabei unverändert auf 0
   bleiben.

 * Entwickeln Sie darauf aufbauend `get_type` für Matrizen,
   wobei im Falle einer Matrix mit `A.incCol != 1` die
   Funktion `get_row_type` verwendet wird, um den MPI-Datentyp
   als Vektor von Zeilen zu konstruieren.

 * Vergleichen Sie den Umfang des von Ihnen konstruierten
   Matrix-Typs mit der Größe der Matrix:

   ---- CODE (type=cpp) -------------------------------------------------------
   GeMatrix<double> A(m, n);
   MPI_Datatype datatype_A = get_type(A);

   MPI_Aint true_extent; MPI_Aint true_lb;
   MPI_Type_get_true_extent(datatype_A, &true_lb, &true_extent);

   MPI_Aint extent; MPI_Aint lb;
   MPI_Type_get_extent(datatype_A, &lb, &extent);

   auto size = sizeof(double) * A.numRows * A.numCols;

   assert(extent == size && true_extent == size);
   ----------------------------------------------------------------------------

   `MPI_Type_get_extent` liefert den möglicherweise
   manipulierten Umfang, `MPI_Type_get_true_extent` liefert
   diesen ohne die Manipulationen durch
   `MPI_Type_create_resized`.

 * Schreiben Sie darauf aufbauend ein kleines Testprogramm mit
   zwei Prozessen für Matrizen analog zum vorherigen Testprogramm
   mit Vektoren.

   Überprüfen Sie sicherheitshalber, dass der Umfang der
   gesamten Matrix korrekt ist:

   Testen Sie Ihr Programm dabei mit unterschiedlichen
   Konfigurationen. Beispielsweise die Übertragung einer
   _row major_-Matrix in eine _col major_-Matrix oder
   umgekehrt.

:navigate: up    -> doc:index
           back  -> doc:session21/page04
           next  -> doc:session21/page06