From b0f979856da06910d023cc6ad09c33507c5b7909 Mon Sep 17 00:00:00 2001 From: Wolfgang Bangerth Date: Tue, 7 Jan 2020 15:43:06 -0700 Subject: [PATCH] Update documentation of class Partitioner. --- include/deal.II/base/partitioner.h | 179 ++++++++++++++++++++--------- 1 file changed, 126 insertions(+), 53 deletions(-) diff --git a/include/deal.II/base/partitioner.h b/include/deal.II/base/partitioner.h index aa0b30c08d..644805c7fd 100644 --- a/include/deal.II/base/partitioner.h +++ b/include/deal.II/base/partitioner.h @@ -44,25 +44,81 @@ namespace Utilities * fact, any linear data structure) among processors using MPI. * * The partitioner stores the global vector size and the locally owned - * range as a half-open interval [@p lower, @p upper). Furthermore, it - * includes a structure for the point-to-point communication patterns. It - * allows the inclusion of ghost indices (i.e. indices that a current - * processor needs to have access to, but are owned by another process) - * through an IndexSet. In addition, it also stores the other processors' - * ghost indices belonging to the current processor (see import_targets()), - * which are the indices where other processors might require information - * from. In a sense, these import indices form the dual of the ghost - * indices. This information is gathered once when constructing the - * partitioner, which obviates subsequent global communication steps when - * exchanging data. + * range as a half-open interval [@p lower, @p upper) on each process. + * Furthermore, it includes a structure for the point-to-point communication + * patterns. It allows the inclusion of ghost indices (i.e. indices that a + * current processor needs to have access to, but are owned by another + * process) through an IndexSet. In addition, it also stores the other + * processors' ghost indices belonging to the current processor (see + * import_targets()), which are the indices where other processors might + * require information from. In a sense, these import indices form the dual + * of the ghost indices. This information is gathered once when constructing + * the partitioner, which obviates subsequent global communication steps + * when exchanging data. * * The figure below gives an example of index space $[0,74)$ being split - * into four processes. + * into four parts that are each owned by one MPI process: * @image html partitioner.png - * Here process 0 will import 5 DoFs from process 1 (first pair of import - * targets), which corresponds to the first 3 elements of its import - * indices. Whereas process 2 will import 3 DoFs from process 0, which - * corresponds to the first two elements of its import indices. + * The first row (above the thick black line) shows which process owns which + * elements. Below it, the next four lines indicate which elements of + * the overall array each processor wants to know about -- this is + * generally a superset of the locally owned elements, with the difference + * being what are called "ghost elements". + * + * To understand the remaining pieces of the figure (and this class), + * remember that in MPI, you can't just ask another process for data. + * (That's not quite true: There are mechanisms in newer MPI standards + * for this, but as a general rule it's true.) Rather, if you need + * information, you need to send another process a message, the other + * process needs to expect the message and respond as appropriate with + * a message of its own. In practice, it is therefore easier and faster + * if each process will *already* know what it will be asked and, at + * the appropriate time, just send that data. The remaining lines of + * information set up this kind of scheme. + * + * To this end, note that process 0 will want to know about five + * elements it does not own itself: those with indices 20, 21 (owned + * by process 1); and 40, 41, 43 (owned by process 2). Similar information + * can be obtained from the following lines. To satisfy this need for + * knowledge, it would therefore be quite useful if process 1 stored + * that, at the appropriate time, it will have to send elements 20, 21 + * to process 0. Similarly, if you go through lines 2-4 below the thick + * black line, you will see that process 0 should know that it will need + * to send elements 1, 2, 13, 18, 19 to process 1; 18, 19 to process 2; + * and elements 1, 2, 13 to process 3. These are called "import indices" + * because other processes will want to import them. Instead of storing + * these indices as a set, it is often useful to use half-open index + * sets instead, and so the import indices listed above form the following + * collection of sets: `[1,3)`, `[13,14)`, `[18,20)`, `[18,20)`, + * `[1,3)`, `[13,14)`. This is how the import indices are shown + * in the figure above. We now only have to know which of these + * half-open sets are to be sent to whom. This is done in the line + * above it where we list the "import targets" (i.e., the target + * processes for an import operations): Process 1 will receive 5 + * elements (which are comprised of the first three half-open + * target index sets), process 2 will receive 2 indices + * (the fourth half-open interval), and process 3 will receive + * 3 indices (the remaining two half-open intervals). This information + * is encoded as the pairs `{1,5}`, `{2,2}`, `{3,3}` as the import + * targets. Similar considerations can be made for what processes + * 1, 2, and 3 will have to send out. + * + * Finally, when receiving information, it is useful to know how + * many indices each process will receive from whom since then one + * can already pre-allocate buffers of the right size. This is listed + * in the last line under "ghost targets": Process 0 will receive + * two elements from process 1 (namely those with indices 20, 21), + * and three from process 2 (namely those with indices 40, 41, 43). + * This is encoded as pairs `{1,2}` and `{2,3}`. Again, similar + * considerations can be made for what processes 1, 2, and 3 + * should expect, and what is then shown in their respective columns. + * + * The main purpose of this class is to set up these data structures + * knowing only which process owns which elements, and for which + * additional ghost elements each process needs knowledge. + * + * + *

Local and global numbering

* * The partitioner includes a mechanism for converting global to local and * local to global indices. Internally, this class stores vector elements @@ -71,15 +127,23 @@ namespace Utilities * consecutively in [@p local_size, @p local_size + @p n_ghost_indices). * The ghost indices are sorted according to their global index. * + * *

Parallel data exchange

* - * This class handles the main ghost data exchange of - * LinearAlgebra::distributed::Vector through four functions: + * This class also handles the ghost data exchange for partitioned + * arrays of objects -- i.e., if a separate class stores the + * locally owned elements on each process, then this class + * facilitates the importation of those elements that are locally + * needed as ghosts but stored elsewhere. An example of where this class + * is used is the LinearAlgebra::distributed::Vector class. + * + * The data exchange happens through four functions: *