Reference documentation for deal.II version Git b7c4cb1 2014-07-28 23:12:52 +0200
|Table of contents|
This program does not introduce any new mathematical ideas; in fact, all it does is to do the exact same computations that step-8 already does, but it does so in a different manner: instead of using deal.II's own linear algebra classes, we build everything on top of classes deal.II provides that wrap around the linear algebra implementation of the PETSc library. And since PETSc allows to distribute matrices and vectors across several computers within an MPI network, the resulting code will even be able to solve the problem in parallel. If you don't know what PETSc is, then this would be a good time to take a quick glimpse at their homepage.
As a prerequisite of this program, you need to have PETSc installed, and if you want to run in parallel on a cluster, you also need METIS to partition meshes. The installation of deal.II together with these two additional libraries is described in the README file.
Now, for the details: as mentioned, the program does not compute anything new, so the use of finite element classes etc. is exactly the same as before. The difference to previous programs is that we have replaced almost all uses of classes
SparseMatrix by their near-equivalents
PETScWrappers::SparseMatrix (for sequential vectors and matrices, i.e. objects for which all elements are stored locally on one machine), and
PETScWrappers::MPI::SparseMatrix for versions of these classes where only a part of the matrix or vector is stored on each machine within an MPI network. These classes provide an interface that is very similar to that of the deal.II linear algebra classes, but instead of implementing this functionality themselves, they simply pass on to their corresponding PETSc functions. The wrappers are therefore only used to give PETSc a more modern, object oriented interface, and to make the use of PETSc and deal.II objects as interchangeable as possible.
While the sequential PETSc wrappers classes do not have any advantage over their deal.II counterparts, the main point of using PETSc is that it can run in parallel. We will make use of this by partitioning the domain into as many blocks (``subdomains'') as there are processes in the MPI network. At the same time, PETSc provides dummy MPI stubs that allow to run the same program on a single machine if so desired, without any changes.
Note, however, that the only data structures we parallelize are matrices and vectors. We do, in particular, not split up the
DoFHandler classes: each process still has a complete copy of these objects, and all processes have exact copies of what the other processes have. Doing so is slightly, though not much more complicated (from a user perspective, it is much more complicated under the hood) to achieve and we will show how to do this in step-40.
The techniques this program demonstrates are: how to use the PETSc wrapper classes; how to parallelize operations for jobs running on an MPI network; and how to partition the domain into subdomains to parallelize up the work. Since all this can only be demonstrated using actual code, let us go straight to the code without much further ado.
First the usual assortment of header files we have already used in previous example programs:
And here come the things that we need particularly for this example program and that weren't in step-8. First, we replace the standard output
std::cout by a new stream
pcout which is used in parallel computations for generating output only on one of the MPI processes.
We are going to query the number of processes and the number of the present process by calling the respective functions in the Utilities::MPI namespace.
Then, we are going to replace all linear algebra components that involve the (global) linear system by classes that wrap interfaces similar to our own linear algebra classes around what PETSc offers (PETSc is a library written in C, and deal.II comes with wrapper classes that provide the PETSc functionality with an interface that is similar to the interface we already had for our own linear algebra classes). In particular, we need vectors and matrices that are distributed across several processes in MPI programs (and simply map to sequential, local vectors and matrices if there is only a single process, i.e. if you are running on only one machine, and without MPI support):
Then we also need interfaces for solvers and preconditioners that PETSc provides:
And in addition, we need some algorithms for partitioning our meshes so that they can be efficiently distributed across an MPI network. The partitioning algorithm is implemented in the
GridTools class, and we need an additional include file for a function in
DoFRenumbering that allows to sort the indices associated with degrees of freedom so that they are numbered according to the subdomain they are associated with:
And this is simply C++ again:
The last step is as in all previous programs:
Now, here comes the declaration of the main class and of various other things below it. As mentioned in the introduction, almost all of this has been copied verbatim from step-8, so we only comment on the few things that are different. There is one (cosmetic) change in that we let
solve return a value, namely the number of iterations it took to converge, so that we can output this to the screen at the appropriate place. In addition, we introduce a stream-like variable
pcout, explained below:
The first variable is basically only for convenience: in parallel program, if each process outputs status information, then there quickly is a lot of clutter. Rather, we would want to only have one process output everything once, for example the one with process number zero.
ConditionalOStream does exactly this: it acts as if it were a stream, but only forwards to a real, underlying stream if a flag is set. By setting this condition to
this_mpi_process==0, we make sure that output is only generated from the first process and that we don't get the same lines of output over and over again, once per process.
With this simple trick, we make sure that we don't have to guard each and every write to
std::cout by a prefixed
The next few variables are taken verbatim from step-8:
In step-8, this would have been the place where we would have declared the member variables for the sparsity pattern, the system matrix, right hand, and solution vector. We change these declarations to use parallel PETSc objects instead (note that the fact that we use the parallel versions is denoted the fact that we use the classes from the
PETScWrappers::MPI namespace; sequential versions of these classes are in the
PETScWrappers namespace, i.e. without the
MPI part). Note also that we do not use a separate sparsity pattern, since PETSc manages that as part of its matrix data structures.
The next change is that we have to declare a variable that indicates the MPI communicator over which we are supposed to distribute our computations. Note that if this is a sequential job without support by MPI, then PETSc provides some dummy type for
MPI_Comm, so we do not have to care here whether the job is really a parallel one:
Then we have two variables that tell us where in the parallel world we are. The first of the following variables,
n_mpi_processes tells us how many MPI processes there exist in total, while the second one,
this_mpi_process, indicates which is the number of the present process within this space of processes. The latter variable will have a unique value for each process between zero and (less than)
n_mpi_processes. If this program is run on a single machine without MPI support, then their values are
The following is again taken from step-8 without change:
The first step in the actual implementation of things is the constructor of the main class. Apart from initializing the same member variables that we already had in step-8, we here initialize the MPI communicator variable we shall use with the global MPI communicator linking all processes together (in more complex applications, one could here use a communicator object that only links a subset of all processes), and call the Utilities helper functions to determine the number of processes and where the present one fits into this picture. In addition, we make sure that output is only generated by the (globally) first process. As
this_mpi_process is determined after creation of pcout, we cannot set the condition through the constructor, i.e. by
pcout(std::cout, this_mpi_process==0), but set the condition separately.
The second step is the function in which we set up the various variables for the global linear system to be solved.
Before we even start out setting up the system, there is one thing to do for a parallel program: we need to assign cells to each of the processes. We do this by splitting (
partitioning) the mesh cells into as many chunks (
subdomains) as there are processes in this MPI job (if this is a sequential job, then there is only one job and all cells will get a zero as subdomain indicator). This is done using an interface to the METIS library that does this in a very efficient way, trying to minimize the number of nodes on the interfaces between subdomains. All this is hidden behind the following call to a deal.II library function:
As for the linear system: First, we need to generate an enumeration for the degrees of freedom in our problem. Further below, we will show how we assign each cell to one of the MPI processes before we even get here. What we then need to do is to enumerate the degrees of freedom in a way so that all degrees of freedom associated with cells in subdomain zero (which resides on process zero) come before all DoFs associated with cells on subdomain one, before those on cells on process two, and so on. We need this since we have to split the global vectors for right hand side and solution, as well as the matrix into contiguous chunks of rows that live on each of the processors, and we will want to do this in a way that requires minimal communication. This is done using the following two functions, which first generates an initial ordering of all degrees of freedom, and then re-sort them according to above criterion:
While we're at it, let us also count how many degrees of freedom there exist on the present process:
Then we initialize the system matrix, solution, and right hand side vectors. Since they all need to work in parallel, we have to pass them an MPI communication object, as well as their global sizes (both dimensions are equal to the number of degrees of freedom), and also how many rows out of this global size are to be stored locally (
n_local_dofs). In addition, PETSc needs to know how to partition the columns in the chunk of the matrix that is stored locally; for square matrices, the columns should be partitioned in the same way as the rows (indicated by the second
n_local_dofs in the call) but in the case of rectangular matrices one has to partition the columns in the same way as vectors are partitioned with which the matrix is multiplied, while rows have to partitioned in the same way as destination vectors of matrix-vector multiplications:
Finally, we need to initialize the objects denoting hanging node constraints for the present grid. Note that since PETSc handles the sparsity pattern internally to the matrix, there is no need to set up an independent sparsity pattern here, and to condense it for constraints, as we have done in all other example programs.
The third step is to actually assemble the matrix and right hand side of the problem. There are some things worth mentioning before we go into detail. First, we will be assembling the system in parallel, i.e. each process will be responsible for assembling on cells that belong to this particular processor. Note that the degrees of freedom are split in a way such that all DoFs in the interior of cells and between cells belonging to the same subdomain belong to the process that
owns the cell. However, even then we sometimes need to assemble on a cell with a neighbor that belongs to a different process, and in these cases when we write the local contributions into the global matrix or right hand side vector, we actually have to transfer these entries to the other process. Fortunately, we don't have to do this by hand, PETSc does all this for us by caching these elements locally, and sending them to the other processes as necessary when we call the
compress() functions on the matrix and vector at the end of this function.
The second point is that once we have handed over matrix and vector contributions to PETSc, it is a) hard, and b) very inefficient to get them back for modifications. This is not only the fault of PETSc, it is also a consequence of the distributed nature of this program: if an entry resides on another processor, then it is necessarily expensive to get it. The consequence of this is that where we previously first assembled the matrix and right hand side as if there were no hanging node constraints and boundary values, and then eliminated these in a second step, we should now try to do that while still assembling the local systems, and before handing these entries over to PETSc. At least as far as eliminating hanging nodes is concerned, this is actually possible, though removing boundary nodes isn't that simple. deal.II provides functions to do this first part: instead of copying elements by hand into the global matrix, we use the
distribute_local_to_global functions below to take care of hanging nodes at the same time. The second step, elimination of boundary nodes, is then done in exactly the same way as in all previous example programs.
So, here is the actual implementation:
The infrastructure to assemble linear systems is the same as in all the other programs, and in particular unchanged from step-8. Note that we still use the deal.II full matrix and vector types for the local systems.
The next thing is the loop over all elements. Note that we do not have to do all the work: our job here is only to assemble the system on cells that actually belong to this MPI process, all other cells will be taken care of by other processes. This is what the if-clause immediately after the for-loop takes care of: it queries the subdomain identifier of each cell, which is a number associated with each cell that tells which process handles it. In more generality, the subdomain id is used to split a domain into several parts (we do this above, at the beginning of
setup_system), and which allows to identify which subdomain a cell is living on. In this application, we have each process handle exactly one subdomain, so we identify the terms
MPI process with each other.
Apart from this, assembling the local system is relatively uneventful if you have understood how this is done in step-8, and only becomes interesting again once we start distributing it into the global matrix and right hand sides.
TODO investigate really small values here
Now we have the local system, and need to transfer it into the global objects. However, as described in the introduction to this function, we want to avoid any operations to matrix and vector entries after handing them off to PETSc (i.e. after distributing to the global objects). Therefore, we will take care of hanging node constraints already here. This is not quite trivial since the rows and columns of constrained nodes have to be distributed to the rows and columns of those nodes to which they are constrained. This can't be done on a purely local basis (because the degrees of freedom to which hanging nodes are constrained may not be associated with the cell we are presently treating, and are therefore not represented in the local matrix and vector), but it can be done while distributing the local system to the global one. This is what the following call does, i.e. we distribute to the global objects and at the same time make sure that hanging node constraints are taken care of:
Now compress the vector and the system matrix:
The global matrix and right hand side vectors have now been formed. Note that since we took care of this already above, we do not have to condense away hanging node constraints any more.
However, we still have to apply boundary values, in the same way as we always do:
The last argument to the call just performed allows for some optimizations. It controls whether we should also delete the column corresponding to a boundary node, or keep it (and passing
true means: yes, do eliminate the column). If we do, then the resulting matrix will be symmetric again if it was before; if we don't, then it won't. The solution of the resulting system should be the same, though. The only reason why we may want to make the system symmetric again is that we would like to use the CG method, which only works with symmetric matrices. Experience tells that CG also works (and works almost as well) if we don't remove the columns associated with boundary nodes, which can be easily explained by the special structure of the non-symmetry. Since eliminating columns from dense matrices is not expensive, though, we let the function do it; not doing so is more important if the linear system is either non-symmetric anyway, or we are using the non-local version of this function (as in all the other example programs before) and want to save a few cycles during this operation.
The fourth step is to solve the linear system, with its distributed matrix and vector objects. Fortunately, PETSc offers a variety of sequential and parallel solvers, for which we have written wrappers that have almost the same interface as is used for the deal.II solvers used in all previous example programs.
First, we have to set up a convergence monitor, and assign it the accuracy to which we would like to solve the linear system. Next, an actual solver object using PETSc's CG solver which also works with parallel (distributed) vectors and matrices. And finally a preconditioner; we choose to use a block Jacobi preconditioner which works by computing an incomplete LU decomposition on each block (i.e. the chunk of matrix that is stored on each MPI process). That means that if you run the program with only one process, then you will use an ILU(0) as a preconditioner, while if it is run on many processes, then we will have a number of blocks on the diagonal and the preconditioner is the ILU(0) of each of these blocks.
Then solve the system:
The next step is to distribute hanging node constraints. This is a little tricky, since to fill in the value of a constrained node you need access to the values of the nodes to which it is constrained (for example, for a Q1 element in 2d, we need access to the two nodes on the big side of a hanging node face, to compute the value of the constrained node in the middle). Since PETSc (and, for that matter, the MPI model on which it is built) does not allow to query the value of another node in a simple way if we should need it, what we do here is to get a copy of the distributed vector where we keep all elements locally. This is simple, since the deal.II wrappers have a conversion constructor for the non-MPI vector class:
Then we distribute hanging node constraints on this local copy, i.e. we compute the values of all constrained nodes:
Then transfer everything back into the global vector. The following operation copies those elements of the localized solution that we store locally in the distributed solution, and does not touch the other ones. Since we do the same operation on all processors, we end up with a distributed vector that has all the constrained nodes fixed.
Finally return the number of iterations it took to converge, to allow for some output:
Step five is to output the results we computed in this iteration. This is actually the same as done in step-8 before, with two small differences. First, all processes call this function, but not all of them need to do the work associated with generating output. In fact, they shouldn't, since we would try to write to the same file multiple times at once. So we let only the first job do this, and all the other ones idle around during this time (or start their work for the next iteration, or simply yield their CPUs to other jobs that happen to run at the same time). The second thing is that we not only output the solution vector, but also a vector that indicates which subdomain each cell belongs to. This will make for some nice pictures of partitioned domains.
In practice, the present implementation of the output function is a major bottleneck of this program, since generating graphical output is expensive and doing so only on one process does, of course, not scale if we significantly increase the number of processes. In effect, this function will consume most of the run-time if you go to very large numbers of unknowns and processes, and real applications should limit the number of times they generate output through this function.
The solution to this is to have each process generate output data only for it's own local cells, and write them to separate files, one file per process. This would distribute the work of generating the output to all processes equally. In a second step, separate from running this program, we would then take all the output files for a given cycle and merge these parts into one single output file. This has to be done sequentially, but can be done on a different machine, and should be relatively cheap. However, the necessary functionality for this is not yet implemented in the library, and since we are too close to the next release, we do not want to do such major destabilizing changes any more. This has been fixed in the meantime, though, and a better way to do things is explained in the step-18 example program.
One point to realize is that when we want to generate output on process zero only, we need to have access to all elements of the solution vector. So we need to get a local copy of the distributed vector, which is in fact simple:
The thing to notice, however, is that we do this localization operation on all processes, not only the one that actually needs the data. This can't be avoided, however, with the communication model of MPI: MPI does not have a way to query data on another process, both sides have to initiate a communication at the same time. So even though most of the processes do not need the localized solution, we have to place the call here so that all processes execute it.
(In reality, part of this work can in fact be avoided. What we do is send the local parts of all processes to all other processes. What we would really need to do is to initiate an operation on all processes where each process simply sends its local chunk of data to process zero, since this is the only one that actually needs it, i.e. we need something like a gather operation. PETSc can do this, but for simplicity's sake we don't attempt to make use of this here. We don't, since what we do is not very expensive in the grand scheme of things: it is one vector communication among all processes , which has to be compared to the number of communications we have to do when solving the linear system, setting up the block-ILU for the preconditioner, and other operations.)
This being done, process zero goes ahead with setting up the output file as in step-8, and attaching the (localized) solution vector to the output object:. (The code to generate the output file name is stolen and slightly modified from step-5, since we expect that we can do a number of cycles greater than 10, which is the maximum of what the code in step-8 could handle.)
The only thing we do here additionally is that we also output one value per cell indicating which subdomain (i.e. MPI process) it belongs to. This requires some conversion work, since the data the library provides us with is not the one the output class expects, but this is not difficult. First, set up a vector of integers, one per cell, that is then filled by the number of subdomain each cell is in:
Then convert this integer vector into a floating point vector just as the output functions want to see:
And finally add this vector as well:
This all being done, generate the intermediate format and write it out in GMV output format:
The sixth step is to take the solution just computed, and evaluate some kind of refinement indicator to refine the mesh. The problem is basically the same as with distributing hanging node constraints: in order to compute the error indicator, we need access to all elements of the solution vector. We then compute the indicators for the cells that belong to the present process, but then we need to distribute the refinement indicators into a distributed vector so that all processes have the values of the refinement indicator for all cells. But then, in order for each process to refine its copy of the mesh, they need to have access to all refinement indicators locally, so they have to copy the global vector back into a local one. That's a little convoluted, but thinking about it quite straightforward nevertheless. So here's how we do it:
So, first part: get a local copy of the distributed solution vector. This is necessary since the error estimator needs to get at the value of neighboring cells even if they do not belong to the subdomain associated with the present MPI process:
Second part: set up a vector of error indicators for all cells and let the Kelly class compute refinement indicators for all cells belonging to the present subdomain/process. Note that the last argument of the call indicates which subdomain we are interested in. The three arguments before it are various other default arguments that one usually doesn't need (and doesn't state values for, but rather uses the defaults), but which we have to state here explicitly since we want to modify the value of a following argument (i.e. the one indicating the subdomain):
Now all processes have computed error indicators for their own cells and stored them in the respective elements of the
local_error_per_cell vector. The elements of this vector for cells not on the present process are zero. However, since all processes have a copy of a copy of the entire triangulation and need to keep these copies in sync, they need the values of refinement indicators for all cells of the triangulation. Thus, we need to distribute our results. We do this by creating a distributed vector where each process has its share, and sets the elements it has computed. We will then later generate a local sequential copy of this distributed vector to allow each process to access all elements of this vector.
So in the first step, we need to set up a parallel vector. For simplicity, every process will own a chunk with as many elements as this process owns cells, so that the first chunk of elements is stored with process zero, the next chunk with process one, and so on. It is important to remark, however, that these elements are not necessarily the ones we will write to. This is so, since the order in which cells are arranged, i.e. the order in which the elements of the vector correspond to cells, is not ordered according to the subdomain these cells belong to. In other words, if on this process we compute indicators for cells of a certain subdomain, we may write the results to more or less random elements if the distributed vector, that do not necessarily lie within the chunk of vector we own on the present process. They will subsequently have to be copied into another process's memory space then, an operation that PETSc does for us when we call the
compress function. This inefficiency could be avoided with some more code, but we refrain from it since it is not a major factor in the program's total runtime.
So here's how we do it: count how many cells belong to this process, set up a distributed vector with that many elements to be stored locally, and copy over the elements we computed locally, then compress the result. In fact, we really only copy the elements that are nonzero, so we may miss a few that we computed to zero, but this won't hurt since the original values of the vector is zero anyway.
So now we have this distributed vector out there that contains the refinement indicators for all cells. To use it, we need to obtain a local copy...
...which we can the subsequently use to finally refine the grid:
Lastly, here is the driver function. It is almost unchanged from step-8, with the exception that we replace
std::cout by the
pcout stream. Apart from this, the only other cosmetic change is that we output how many degrees of freedom there are per process, and how many iterations it took for the linear solver to converge:
So that's it, almost.
main() works the same way as most of the main functions in the other example programs, i.e. it delegates work to the
run function of a master object, and only wraps everything into some code to catch exceptions:
Here is the only real difference: PETSc requires that we initialize it at the beginning of the program, and un-initialize it at the end. The class MPI_InitFinalize takes care of that. The original code sits in between, enclosed in braces to make sure that the
elastic_problem variable goes out of scope (and is destroyed) before PETSc is closed with
PetscFinalize. (If we wouldn't use braces, the destructor of
elastic_problem would run after
PetscFinalize; since the destructor involves calls to PETSc functions, we would get strange error messages from PETSc.)
If the program above is compiled and run on a single processor machine, it should generate results that are very similar to those that we already got with step-8. However, it becomes more interesting if we run it on a multicore machine or a cluster of computers. The most basic way to run MPI programs is using a command line like
to run the step-17 executable with 32 processors.
The command line above is the appropriate way of starting the program on a multicore machine when using MPI for parallelization. On the other hand, most clusters are shared resources and have some kind of scheduling system that distributes jobs onto available processors. All of these scheduling systems have their own calling syntax - on my system, I have to use the command
qsub with a whole host of options to run a job in parallel - so that the exact command line syntax varies.
Whether directly or through a scheduler, if you run this program on 8 processors, you should get output like the following:
(This run uses a few more refinement cycles than the code available in the examples/ directory. The run also used a version of METIS from 2004 that generated different partitionings; consequently, the numbers you get today are slightly different.)
As can be seen, we can easily get to almost four million unknowns. In fact, the code's runtime with 8 processes was less than 7 minutes up to (and including) cycle 14, and 14 minutes including the second to last step. (These are numbers relevant to when the code was initially written, in 2004.) I lost the timing information for the last step, though, but you get the idea. All this is after release mode has been enabled by running
make release, and with the generation of graphical output switched off for the reasons stated in the program comments above. (See also video lecture 18.) The biggest 2d computations we did had roughly 7.1 million unknowns, and were done on 32 processes. It took about 40 minutes. Not surprisingly, the limiting factor for how far one can go is how much memory one has, since every process has to hold the entire mesh and DoFHandler objects, although matrices and vectors are split up. For the 7.1M computation, the memory consumption was about 600 bytes per unknown, which is not bad, but one has to consider that this is for every unknown, whether we store the matrix and vector entries locally or not.
Here is some output generated in the 12th cycle of the program, i.e. with roughly 300,000 unknowns:
As one would hope for, the x- (left) and y-displacements (right) shown here closely match what we already saw in step-8. As shown there and in step-22, we could as well have produced a vector plot of the displacement field, rather than plotting it as two separate scalar fields. What may be more interesting, though, is to look at the mesh and partition at this step:
Again, the mesh (left) shows the same refinement pattern as seen previously. The right panel shows the partitioning of the domain across the 8 processes, each indicated by a different color. The picture shows that the subdomains are smaller where mesh cells are small, a fact that needs to be expected given that the partitioning algorithm tries to equilibrate the number of cells in each subdomain; this equilibration is also easily identified in the output shown above, where the number of degrees per subdomain is roughly the same.
It is worth noting that if we ran the same program with a different number of processes, that we would likely get slightly different output: a different mesh, different number of unknowns and iterations to convergence. The reason for this is that while the matrix and right hand side are the same independent of the number of processes used, the preconditioner is not: it performs an ILU(0) on the chunk of the matrix of each processor separately. Thus, it's effectiveness as a preconditioner diminishes as the number of processes increases, which makes the number of iterations increase. Since a different preconditioner leads to slight changes in the computed solution, this will then lead to slightly different mesh cells tagged for refinement, and larger differences in subsequent steps. The solution will always look very similar, though.
Finally, here are some results for a 3d simulation. You can repeat these by first changing
in the main function, and then in the Makefile, change the reference to the 2d libraries to their 3d counterparts. If you then run the program in parallel, you get something similar to this (this is for a job with 16 processes):
The last step, going up to 1.5 million unknowns, takes about 55 minutes with 16 processes on 8 dual-processor machines (of the kind available in 2003). The graphical output generated by this job is rather large (cycle 5 already prints around 82 MB of GMV data), so we contend ourselves with showing output from cycle 4:
The left picture shows the partitioning of the cube into 16 processes, whereas the right one shows the x-displacement along two cutplanes through the cube.
The program keeps a complete copy of the Triangulation and DoFHandler objects on every processor. That's obviously the bottleneck for as far as parallelization goes. Internally, within deal.II, parallelizing the data structures used in hierarchic and unstructured triangulations is a very hard problem, and it took us a few more years to make this happen. The step-40 tutorial program and the Parallel computing with multiple processors using distributed memory documentation module talk about how to do these steps and what it takes from an application perspective. An obvious extension of the current program would be to use this functionality to completely distribute computations to many more processors than used here.