=========================================== Zweidimensionale Organisation von Prozessen =========================================== Die Partitionierung eines Problems auf einzelne Prozesse und deren Kommunikationsbeziehungen kann als Graph repräsentiert werden, wobei die Prozesse die Knoten und die Kommunikationsbeziehungen die Kanten repräsentieren. Der Graph ist normalerweise ungerichtet, weil zumindest die zugrundeliegenden Kommunikationsarchitekturen und das Protokoll bidirektional sind. Da die Bandbreiten und Latenzzeiten zwischen einzelnen rechnenden Knoten nicht überall gleich sind, ist es sinnvoll, die Aufteilung der Prozesse auf Knoten so zu organisieren, dass die Kanten möglichst weitgehend auf günstigere Kommunikationsverbindungen gelegt werden. Bei Infiniband spielt die Organisation kaum eine Rolle, es sei denn, es liegt eine Zwei-Ebenen-Architektur vor wie beispielsweise bei _SuperMUC_ in München. Bei MP-Systemen mit gemeinsamen Speicher ist es günstiger, wenn miteinander kommunizierende Prozesse auf Kernen des gleichen Prozessors laufen, da diese typischerweise einen Cache gemeinsam nutzen können und somit der Umweg über den langsamen Hauptspeicher vermieden wird. Manche Cluster-Systeme (wie beispielsweise Titan) sind in einem dreidimensionalen Torus organisiert, bei dem die Nachbarschaft eine wichtige Rolle spielt. MPI bietet die Möglichkeit, beliebige Kommunikationsgraphen zu deklarieren. Zusätzlich unterstützt bzw. vereinfacht MPI die Deklarationen $n$-dimensionaler Gitterstrukturen, die in jeder Dimension mit oder ohne Ringstrukturen konfiguriert werden können. Entsprechend sind im eindimensionalen einfache Ketten oder Ringe möglich und im zweidimensionalen Fall Matrizen, Zylinder oder Tori. Dies eröffnet MPI die Möglichkeit, eine geeignete Zuordnung von Prozessen auf Prozessoren vorzunehmen. Ferner lassen sich über entsprechende MPI-Funktionen die Kommunikationsnachbarn eines Prozesses ermitteln. Grundsätzlich ist eine Kommunikation abseits des vorgegebenen Kommunikationsgraphen möglich. Nur bietet diese möglicherweise höhere Latenzzeiten und/oder niedrigere Bandbreiten. In unserem Kontext ist zunächst die Organisation der Prozesse in einem zweidimensionalen Gitter interessant. Dies könnte so erfolgen: ---- CODE (type=cpp) ---------------------------------------------------------- int dims[2] = {0, 0}; int periods[2] = {false, false}; MPI_Dims_create(nof_processes, 2, dims); MPI_Comm grid; MPI_Cart_create(MPI_COMM_WORLD, 2, // number of dimensions dims, // actual dimensions periods, // both dimensions are non-periodical true, // reorder is permitted &grid // newly created communication domain ); MPI_Comm_rank(MPI_COMM_WORLD, &rank); // update rank (could have changed) ------------------------------------------------------------------------------- In dem Array `dims` geben wir die gewünschte Dimensionierung vor. Wenn wir hier 0 angeben, überlassen wir die Dimensionierung MPI. Alternativ könnten wir hier auch bereits Teiler von `nof_processes` angeben. `MPI_Dims_create` führt nun die zweidimensionale Dimensionierung durch. Dabei wird das Array `dims` überschrieben. `MPI_Dims_create` sucht nach einer möglichst guten Verteilung auf Basis der zur Verfügung stehenden Teiler von `nof_processes`. Sollte `nof_processes` prim sein, würde dabei eine sehr ungünstige Aufteilung $1 \times nof_processes$ entstehen. Mit `MPI_Cart_create` erzeugen wir eine neue Kommunikationsdomäne mit dem Prozessen aus dem ersten Parameter, hier `MPI_COMM_WORLD`. Mit `periods` wird festgelegt, ob die jeweilige Dimension ringförmig anzulegen ist. Bei dem Jacobi-Verfahren benötigen wir das nicht, entsprechend setzen wir hier beide Werte auf `false`. Wenn eine Umordnung zulässig ist (fünfter Parameter), dann kann sich der `rank` jeder der Prozesse auch innerhalb von `MPI_COMM_WORLD` verändern. Dies erlaubt MPI die Umorganisation aller Prozesse auf der zur Verfügung stehenden Netzwerkstruktur, die die Kommunikationstopologie möglichst gut unterstützt. Wenn eine Umordnung zugelassen wird, muss anschließend der `rank` erneut abgerufen werden, da dieser sich verändert haben könnte. Aufgabe ======= Analog zu den vorherigen zeilenweisen operierenden Scatter- und Gather-Operationen lohnt es sich, dies auch zwei-dimensional blockweise bei Matrizen durchzuführen. Es gibt hier allerdings keine MPI-Operationen, die dies unmittelbar stützen, da sowohl `MPI_Scatterv` als auch `MPI_Gatherv` zwar unterschiedliche Quantitäten pro Prozess zulassen, jedoch auf einheitliche Typen bestehen. Das ist bei einer zweidimensionalen Matrixaufteilung jedoch nicht mehr der Fall, da wir dort bis zu vier verschiedene Typen haben können: Regulärer Fall, rechter Rand, unterer Rand, linke untere Ecke. Entsprechend lohnt es sich, Scatter- und Gather-Operationen für Matrizen selbst zu entwickeln, die allerdings auf der Seite des Root-Prozesses alle Kommunikationsoperationen mit Hilfe der nicht-blockierenden Operationen parallelisieren sollte. Ebenso ist zu beachten, dass der Root-Prozess auch immer einen Teilblock an sich selbst verteilt bzw. wieder zurückkopiert -- hierfür wird keine Kommunikation benötigt, sondern nur eine reguläre Matrix-Kopieroperation (`hpc::matvec::copy`). Entwickeln Sie die Funktionen `scatter_by_block` und `gather_by_block` mit den folgenden Signaturen: ---- CODE (type=cpp) ---------------------------------------------------------- template typename std::enable_if< hpc::matvec::IsGeMatrix::value && hpc::matvec::IsGeMatrix::value && std::is_same::value, int>::type scatter_by_block(const MA& A, MB& B, int root, MPI_Comm grid, int dims[2], int coords[2]) { /* ... */ } template typename std::enable_if< hpc::matvec::IsGeMatrix::value && hpc::matvec::IsGeMatrix::value && std::is_same::value, int>::type gather_by_block(const MA& A, MB& B, int root, MPI_Comm grid, int dims[2], int coords[2]) { /* ... */ } ------------------------------------------------------------------------------- Vorlage ======= Zum Testen steht eine Vorlage zur Verfügung: :import:session22/scatter-gather4.cpp :navigate: up -> doc:index back -> doc:session22/page06 next -> doc:session22/page08