From 0f3528cd5735dc8aad0e503b65303c437f9f1206 Mon Sep 17 00:00:00 2001 From: Wolfgang Bangerth Date: Fri, 26 Sep 2014 18:39:29 -0500 Subject: [PATCH] Provide better documentation on ghosted vectors. This includes a discussion of what ghosted vectors are and what their semantics are. --- doc/doxygen/headers/distributed.h | 74 ++++++++-------- doc/doxygen/headers/glossary.h | 86 +++++++++++++++++-- doc/news/changes.h | 6 ++ include/deal.II/lac/parallel_vector.h | 14 ++- include/deal.II/lac/petsc_parallel_vector.h | 23 ++++- include/deal.II/lac/petsc_vector_base.h | 4 +- .../lac/trilinos_parallel_block_vector.h | 4 +- include/deal.II/lac/trilinos_vector.h | 53 +++++++++--- include/deal.II/lac/trilinos_vector_base.h | 2 + 9 files changed, 204 insertions(+), 62 deletions(-) diff --git a/doc/doxygen/headers/distributed.h b/doc/doxygen/headers/distributed.h index 1a8a7d46da..9b9e9a1149 100644 --- a/doc/doxygen/headers/distributed.h +++ b/doc/doxygen/headers/distributed.h @@ -235,34 +235,40 @@ * information is provided by the * DoFTools::extract_locally_relevant_dofs() function. * - *
Vectors with Ghost-elements
- * + * + *
Vectors with ghost elements
+ * * A typical parallel application is dealing with two different kinds * of parallel vectors: vectors with ghost elements (also called - * ghosted vectors) and vectors without ghost elements. Of course - * these might be different flavours (BlockVector, Vector; using - * Trilinos or PETSc, etc.). - * - * In vectors without ghost elements knowledge about a single entry i - * in the vector is only known to a single processor. They are - * constructed with an IndexSet reflecting the - * locally_owned_dofs(). There is no overlap in the IndexSets. - * Ghosted vectors are typically created using locally_active or - * locally_relevant IndexSets and contain elements on processors that - * are owned by a different processor. - * - * One important aspect is that we forbid any modification of ghosted - * vectors. This is because it would create subtle bugs if elements - * are edited on one processor but do not immediately transfer to the - * ghosted entries on the other processors. - * - * The usage is typically split up in the following way: ghosted - * vectors are used for data output, postprocessing, error estimation, - * input in integration. Vectors without ghost entries are used in all + * ghosted vectors) and vectors without ghost elements. (Both + * kinds can typically be represented by the same data type, but there + * are of course different vector types that can each represent both flavors: + * for example TrilinosWrappers::MPI::Vector, PETScWrappers::Vector, and + * BlockVector objects built on these). + * You can find a discussion of what distinguishes these kinds of vectors + * in the @ref GlossGhostedVector "glossary entry on ghosted vectors". + * + * From a usage point of view, ghosted vectors are typically used for + * data output, postprocessing, error estimation, input in + * integration. This is because in these operations, one typically + * needs access not only to @ref GlossLocallyOwnedDofs "locally owned dofs" + * but also to @ref GlossLocallyActiveDofs "locally active dofs" + * and sometimes to @ref GlossLocallyRelevantDofs "locally relevant dofs", + * and their values may not be stored in non-ghosted vectors on the + * processor that needs them. The operations listed above also only + * require read-only access to vectors, and ghosted vectors are therefore + * usable in these contexts. + * + * On the other hand, vectors without ghost entries are used in all * other places like assembling, solving, or any other form of - * manipulation. You can copy between vectors with and without ghost + * manipulation. These are typically write-only operations and + * therefore need not have read access to vector elements that may be + * owned by another processor. + * + * You can copy between vectors with and without ghost * elements (you can see this in step-40 and step-32) using operator=. * + * *
Sparsity patterns
* * At the time of writing this, the only class equipped to deal with the @@ -383,17 +389,17 @@ namespace parallel { - /** - * A namespace for class and - * functions that support %parallel - * computing on %distributed memory - * machines. See the @ref - * distributed module for an - * overview of the facilities this - * namespace offers. - * - * @ingroup distributed - */ + /** + * A namespace for class and + * functions that support %parallel + * computing on %distributed memory + * machines. See the @ref + * distributed module for an + * overview of the facilities this + * namespace offers. + * + * @ingroup distributed + */ namespace distributed { } diff --git a/doc/doxygen/headers/glossary.h b/doc/doxygen/headers/glossary.h index 0d8b4e53a1..5e68507356 100644 --- a/doc/doxygen/headers/glossary.h +++ b/doc/doxygen/headers/glossary.h @@ -549,10 +549,6 @@ * This argument is required for vectors and matrices starting with the 7.3 * release. * - * In olde releases we also proposed fake add/set operations. Those were the - * cause of many bugs and deadlocks, so the usage of VectorOperation is now - * required. - * * In short, you need to call compress() in the following cases (and only in * those cases, though calling compress() in other cases just costs some * performance): @@ -573,6 +569,11 @@ * calls to compress(). * * + * @note Compressing is an operation that only applies to vectors whose + * elements are uniquely owned by one and only one processor in a parallel + * MPI universe. It does not apply to + * @ref GlossGhostedVector "vectors with ghost elements". + * * *
@anchor GlossDoF Degree of freedom
* @@ -895,6 +896,77 @@ * dealii::Triangulation class. * * + *
@anchor GlossGhostedVector Ghosted vectors
+ *
+ * In parallel computations, vectors come in two general kinds: + * without and with ghost elements. Vectors without ghost + * elements uniquely partition the vector elements between + * processors: each vector entry has exactly one processor that + * owns it, and this is the only processor that stores the value + * of this entry. In other words, if processor zero stores elements + * 0...49 of a vector and processor one stores elements 50...99, + * then processor one is out of luck accessing element 42 of this + * vector: it is not stored here and the value can not be assessed. + * This will result in an assertion. + * + * On the other hand, there are many situations where one needs to + * know vector elements that aren't locally owned, for example to + * evaluate the solution on a locally owned cell (see + * @ref GlossLocallyOwnedCell) for which one of the degrees of freedom + * is at an interface to a cell that we do not own locally (which, + * in this case must then be a @ref GlossGhostCell "ghost cell") + * and for which the neighboring cell may be the owner -- in other + * words, the degree of freedom is not a + * @ref GlossLocallyOwnedDof "locally owned" but instead only a + * @ref GlossLocallyActiveDof "locally active DoFs". The values of such + * degrees of freedom are typically stored on the machine that owns the + * degree of freedom and, consequently, would not be accessible on the + * current machine. + * + * Because one often needs these values anyway, there is a second kind of + * vector, often called "ghosted vector". Ghosted vectors store some elements + * on each processor for which that processor is not the owner. + * For such vectors, you can read those elements that the + * processor you are currently on stores but you cannot write into them + * because to make this work would require propagating the new value to + * all other processors that have a copy of this value (the list of + * such processors may be something which the current processor does not + * know and has no way of finding out efficiently). Since you cannot + * write into ghosted vectors, the only way to initialize such a vector + * is by assignment from a non-ghosted vector. This implies having to + * import those elements we locally want to store from other processors. + * + * The way ghosted vectors are actually stored is different between the + * various implementations of parallel vectors. For PETSc (and the corresponding + * PETScWrappers::MPI::Vector class), ghosted vectors store the same + * elements as non-ghosted ones would, plus some additional elements + * that are owned by other processors. In other words, for each element + * there is a clear owner among all of the processors and those elements + * that the current processor stores but does not own (i.e., the + * "ghost elements") are simply mirror images of a master value somewhere + * else -- thus, the name "ghost". This is also the case for the + * parallel::distributed::Vector class. + * + * On the other hand, in Trilinos (and consequently in + * TrilinosWrappers::MPI::Vector), a ghosted vector is simply a view + * of the parallel vector where the element distributions overlap. The + * 'ghosted' Trilinos vector in itself has no idea of which entries + * are ghosted and which are locally owned. In fact, a ghosted vector + * may not even store all of the elements a non-ghosted vector would + * store on the current processor. Consequently, for Trilinos vectors, + * there is no notion of an 'owner' of vector elements in the way we + * have it in the the non-ghost case view (or in the PETSc case) and + * the name "ghost element" may be misleading since in this view, + * every element we have available locally may or may not be stored + * somewhere else as well, but even if it is, the local element is not + * a mirror value of a master location as there is no owner of each + * element. + * + * @note The @ref distributed documentation module provides a brief + * overview of where the different kinds of vectors are typically + * used. + *
+ * *
@anchor hp_paper %hp paper
*
The "hp paper" is a paper by W. Bangerth and O. Kayser-Herold, titled * "Data Structures and Requirements for hp Finite Element Software", that @@ -1000,7 +1072,7 @@ Article{BK07, *
Every object that makes up a Triangulation (cells, faces, * edges, etc.), is associated with a unique number (of type * types::manifol_id) that is used to identify which manifold object - * is responsible to generate new points when the mesh is refined. + * is responsible to generate new points when the mesh is refined. * * By default, all manifold indicators of a mesh are set to * numbers::invalid_manifold_id. A typical piece of code that sets the @@ -1010,8 +1082,8 @@ Article{BK07, * * @code * for (typename Triangulation::active_cell_iterator cell = - * triangulation.begin_active(); - * cell != triangulation.end(); ++cell) + * triangulation.begin_active(); + * cell != triangulation.end(); ++cell) * if (cell->center()[0] < 0) * cell->set_manifold_id (42); * @endcode diff --git a/doc/news/changes.h b/doc/news/changes.h index 4bb5c9fc1b..6f95dfb1a6 100644 --- a/doc/news/changes.h +++ b/doc/news/changes.h @@ -117,6 +117,12 @@ inconvenience this causes. (Denis Davydov, Wolfgang Bangerth, 2014/09/28) +
  • New: The glossary now contains an extensive entry on ghosted and + non-ghosted vectors (see @ref GlossGhostedVector +
    + (Wolfgang Bangerth, 2014/09/27) +
    • +
  • New: Made MappingQ aware of Manifold. Now we can use high order mappings that actually follow the geometry also on the interior of codimension diff --git a/include/deal.II/lac/parallel_vector.h b/include/deal.II/lac/parallel_vector.h index 043ba413f9..416d615f1d 100644 --- a/include/deal.II/lac/parallel_vector.h +++ b/include/deal.II/lac/parallel_vector.h @@ -82,7 +82,9 @@ namespace parallel * communicator), and retained until the partitioning is changed * again. This allows for efficient parallel communication of indices. In * particular, it stores the communication pattern, rather than having - * to compute it again for every communication. + * to compute it again for every communication. (For more information on + * ghost vectors, see also the + * @ref GlossGhostedVector "glossary entry on vectors with ghost elements".) * - Besides the usual global access operator () it is also possible to * access vector entries in the local index space with the function @p * local_element(). Locally owned indices are placed first, [0, @@ -97,6 +99,7 @@ namespace parallel * Note that the @p insert mode of @p compress() does not set the * elements included in ghost entries but simply discards them, assuming * that the owning processor has set them to the desired value already. + * (See also the @ref GlossCompress "glossary entry on compress".) * - The update_ghost_values() function imports the data from * the owning processor to the ghost indices in order to provide read * access to the data associated with ghosts. @@ -196,6 +199,8 @@ namespace parallel * called once for a given layout. Use the constructor with * Vector argument to create additional vectors with the same * parallel layout. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ Vector (const IndexSet &local_range, const IndexSet &ghost_indices, @@ -252,6 +257,8 @@ namespace parallel * called once for a given layout. Use the @p reinit function with * Vector argument to create additional vectors with the same * parallel layout. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ void reinit (const IndexSet &local_range, const IndexSet &ghost_indices, @@ -363,7 +370,6 @@ namespace parallel * i.e., whenever a non-zero ghost element is found, it is compared to * the value on the owning processor and an exception is thrown if these * elements do not agree. - * */ void compress (::dealii::VectorOperation::values operation); @@ -389,6 +395,8 @@ namespace parallel * inner product will always ignore ghost elements in order to avoid * counting the ghost data more than once. To allow writing to ghost * elements again, call zero_out_ghosts(). + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ void update_ghost_values () const; @@ -475,6 +483,8 @@ namespace parallel * read-access to ghost elements is prohibited whereas write access is * still possible (to those entries specified as ghosts during * initialization), not that there are no ghost elements at all. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ bool has_ghost_elements() const; diff --git a/include/deal.II/lac/petsc_parallel_vector.h b/include/deal.II/lac/petsc_parallel_vector.h index 18414d2c44..5c5461d8c9 100644 --- a/include/deal.II/lac/petsc_parallel_vector.h +++ b/include/deal.II/lac/petsc_parallel_vector.h @@ -1,6 +1,6 @@ // --------------------------------------------------------------------- // -// Copyright (C) 2004 - 2013 by the deal.II authors +// Copyright (C) 2004 - 2014 by the deal.II authors // // This file is part of the deal.II library. // @@ -61,6 +61,7 @@ namespace PETScWrappers * functions). Only the functions creating a vector of specific type differ, * and are implemented in this particular class. * + * *

    Parallel communication model

    * * The parallel functionality of PETSc is built on top of the Message Passing @@ -150,6 +151,8 @@ namespace PETScWrappers * operations at the same time, for example by placing zero additions if * necessary. * + * @see @ref GlossGhostedVector "vectors with ghost elements" + * * @ingroup PETScWrappers * @ingroup Vectors * @author Wolfgang Bangerth, 2004 @@ -270,6 +273,8 @@ namespace PETScWrappers * * @note This operation always creates a ghosted * vector. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ explicit Vector (const MPI_Comm &communicator, const IndexSet &local, @@ -295,6 +300,8 @@ namespace PETScWrappers * * @note This operation always creates a ghosted * vector. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ Vector (const IndexSet &local, const IndexSet &ghost, @@ -302,14 +309,15 @@ namespace PETScWrappers /** * Constructs a new parallel PETSc - * vector from an Indexset. This creates a non + * vector from an IndexSet. This creates a non * ghosted vector. */ explicit Vector (const MPI_Comm &communicator, const IndexSet &local) DEAL_II_DEPRECATED; + /** * Constructs a new parallel PETSc - * vector from an Indexset. This creates a non + * vector from an IndexSet. This creates a non * ghosted vector. */ explicit Vector (const IndexSet &local, @@ -442,14 +450,18 @@ namespace PETScWrappers * Reinit as a ghosted vector. See * constructor with same signature * for more details. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ void reinit (const MPI_Comm &communicator, const IndexSet &local, const IndexSet &ghost) DEAL_II_DEPRECATED; /** * Reinit as a vector without ghost elements. See - * constructor with same signature + * the constructor with same signature * for more detais. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ void reinit (const IndexSet &local, const IndexSet &ghost, @@ -462,10 +474,13 @@ namespace PETScWrappers */ void reinit (const MPI_Comm &communicator, const IndexSet &local) DEAL_II_DEPRECATED; + /** * Reinit as a vector without ghost elements. See * constructor with same signature * for more detais. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ void reinit (const IndexSet &local, const MPI_Comm &communicator); diff --git a/include/deal.II/lac/petsc_vector_base.h b/include/deal.II/lac/petsc_vector_base.h index a1afef3896..efb6b08201 100644 --- a/include/deal.II/lac/petsc_vector_base.h +++ b/include/deal.II/lac/petsc_vector_base.h @@ -1,6 +1,6 @@ // --------------------------------------------------------------------- // -// Copyright (C) 2004 - 2013 by the deal.II authors +// Copyright (C) 2004 - 2014 by the deal.II authors // // This file is part of the deal.II library. // @@ -423,6 +423,8 @@ namespace PETScWrappers /** * Return if the vector contains ghost * elements. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ bool has_ghost_elements() const; diff --git a/include/deal.II/lac/trilinos_parallel_block_vector.h b/include/deal.II/lac/trilinos_parallel_block_vector.h index b30e68450f..46585b3039 100644 --- a/include/deal.II/lac/trilinos_parallel_block_vector.h +++ b/include/deal.II/lac/trilinos_parallel_block_vector.h @@ -1,6 +1,6 @@ // --------------------------------------------------------------------- // -// Copyright (C) 2008 - 2013 by the deal.II authors +// Copyright (C) 2008 - 2014 by the deal.II authors // // This file is part of the deal.II library. // @@ -293,6 +293,8 @@ namespace TrilinosWrappers /** * Returns if this Vector contains ghost elements. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ bool has_ghost_elements() const; diff --git a/include/deal.II/lac/trilinos_vector.h b/include/deal.II/lac/trilinos_vector.h index 2247b9c742..6e3b20a4eb 100644 --- a/include/deal.II/lac/trilinos_vector.h +++ b/include/deal.II/lac/trilinos_vector.h @@ -1,6 +1,6 @@ // --------------------------------------------------------------------- // -// Copyright (C) 2008 - 2013 by the deal.II authors +// Copyright (C) 2008 - 2014 by the deal.II authors // // This file is part of the deal.II library. // @@ -120,18 +120,19 @@ namespace TrilinosWrappers * One particular case, where an MPI message may be generated * unexpectedly is discussed below. * + * *

    Accessing individual elements of a vector

    * - * Trilinos does allow read access to individual elements of a vector, - * but in the distributed case only to elements that are stored - * locally. We implement this through calls like - * d=vec(i). However, if you access an element outside the - * locally stored range, an exception is generated. + * Trilinos does of course allow read access to individual + * elements of a vector, but in the distributed case only to + * elements that are stored locally. We implement this through + * calls like d=vec(i). However, if you access an element + * outside the locally stored range, an exception is generated. * * In contrast to read access, Trilinos (and the respective deal.II * wrapper classes) allow to write (or add) to individual elements of * vectors, even if they are stored on a different process. You can do - * this writing by writing into or adding to elements using the syntax + * this by writing into or adding to elements using the syntax * vec(i)=d or vec(i)+=d, * or similar operations. There is one catch, however, that may lead to * very confusing error messages: Trilinos requires application programs @@ -193,19 +194,23 @@ namespace TrilinosWrappers * Parallel vectors come in two kinds: without and with ghost elements. * Vectors without ghost elements uniquely partition the vector elements * between processors: each vector entry has exactly one processor that - * owns it. For such vectors, you can read those elements that you are - * owned by the processor you are currently on, and you can write into + * owns it. For such vectors, you can read those elements that + * the processor you are currently on owns, and you can write into * any element whether you own it or not: if you don't own it, the * value written or added to a vector element will be shipped to the * processor that owns this vector element the next time you call * compress(), as described above. * - * What we call a 'ghosted' vector is simply a view of the + * What we call a 'ghosted' vector (see + * @ref GlossGhostedVector "vectors with ghost elements") + * is simply a view of the * parallel vector where the element distributions overlap. The 'ghosted' * Trilinos vector in itself has no idea of which entries are ghosted and - * which are locally owned. In particular, there is no notion of - * an 'owner' of vector selement in the way we have it in the - * the non-ghost case view. + * which are locally owned. In fact, a ghosted vector + * may not even store all of the elements a non-ghosted vector would + * store on the current processor. Consequently, for Trilinos vectors, + * there is no notion of an 'owner' of vector elements in the way we + * have it in the the non-ghost case view. * * This explains why we do not allow writing into ghosted vectors on the * Trilinos side: Who would be responsible for taking care of the @@ -385,6 +390,8 @@ namespace TrilinosWrappers * subdivides elements among processors or not, the resulting vector * may or may not have ghost elements. See the general documentation of * this class for more information. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ explicit Vector (const Epetra_Map ¶llel_partitioning); @@ -398,6 +405,8 @@ namespace TrilinosWrappers * subdivides elements among processors or not, the resulting vector * may or may not have ghost elements. See the general documentation of * this class for more information. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ Vector (const Epetra_Map ¶llel_partitioning, const VectorBase &v); @@ -410,6 +419,8 @@ namespace TrilinosWrappers * subdivides elements among processors or not, the resulting vector * may or may not have ghost elements. See the general documentation of * this class for more information. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ template void reinit (const Epetra_Map ¶llel_partitioner, @@ -423,6 +434,8 @@ namespace TrilinosWrappers * subdivides elements among processors or not, the resulting vector * may or may not have ghost elements. See the general documentation of * this class for more information. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ void reinit (const Epetra_Map ¶llel_partitioning, const bool fast = false); @@ -435,6 +448,8 @@ namespace TrilinosWrappers * subdivides elements among processors or not, the resulting vector * may or may not have ghost elements. See the general documentation of * this class for more information. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ template Vector (const Epetra_Map ¶llel_partitioning, @@ -454,6 +469,8 @@ namespace TrilinosWrappers * subdivides elements among processors or not, the resulting vector * may or may not have ghost elements. See the general documentation of * this class for more information. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ explicit Vector (const IndexSet ¶llel_partitioning, const MPI_Comm &communicator = MPI_COMM_WORLD); @@ -465,6 +482,8 @@ namespace TrilinosWrappers * subdivides elements among processors or not, the resulting vector * may or may not have ghost elements. See the general documentation of * this class for more information. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ Vector (const IndexSet &local, const IndexSet &ghost, @@ -480,6 +499,8 @@ namespace TrilinosWrappers * subdivides elements among processors or not, the resulting vector * may or may not have ghost elements. See the general documentation of * this class for more information. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ Vector (const IndexSet ¶llel_partitioning, const VectorBase &v, @@ -493,6 +514,8 @@ namespace TrilinosWrappers * subdivides elements among processors or not, the resulting vector * may or may not have ghost elements. See the general documentation of * this class for more information. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ template Vector (const IndexSet ¶llel_partitioning, @@ -510,6 +533,8 @@ namespace TrilinosWrappers * subdivides elements among processors or not, the resulting vector * may or may not have ghost elements. See the general documentation of * this class for more information. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ void reinit (const IndexSet ¶llel_partitioning, const MPI_Comm &communicator = MPI_COMM_WORLD, @@ -537,6 +562,8 @@ namespace TrilinosWrappers * subdivides elements among processors or not, the resulting vector * may or may not have ghost elements. See the general documentation of * this class for more information. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ void reinit (const IndexSet &locally_owned_entries, const IndexSet &ghost_entries, diff --git a/include/deal.II/lac/trilinos_vector_base.h b/include/deal.II/lac/trilinos_vector_base.h index ba77c644bf..dd8fc22fc9 100644 --- a/include/deal.II/lac/trilinos_vector_base.h +++ b/include/deal.II/lac/trilinos_vector_base.h @@ -420,6 +420,8 @@ namespace TrilinosWrappers /** * Return if the vector contains ghost elements. This answer is true if * there are ghost elements on at least one process. + * + * @see @ref GlossGhostedVector "vectors with ghost elements" */ bool has_ghost_elements() const; -- 2.39.5