I've always heard that easy parallelization was one of the advantages of DG methods, but I don't really see why any of those reasons don't also apply to continuous Galerkin.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ I don't think so, but it might enhance the question if you linked to or described some of those supposed reasons. $\endgroup$– Bill BarthCommented Mar 13, 2014 at 16:46
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
One reason DG methods may receive more attention as a parallel method is that it is readily seen that the method is inherently local to an element. The coupling in DG methods is weak, as it only occurs through adjacent edges (or faces in 3d). So, for triangles or quads DG will communicate to three or four processers at most, respectively. Whereas CG methods will include element corners, thus the valence of an element's corner becomes important. Depending on the mesh generator used, this valence can be eight processers (possibly higher). So the cost of assembling the time derivative can be considered "higher" for CG methods. This is paricularly of concern for spectral methods, where the volume of information to be communicated can be quite large (and latency hiding can become more difficult as the size of each partition shrinks).
But this extra cost for CG to assemble it's time derivative could be compensated for by a different load balancing strategy. Different mesh partitioning strategies (I'm most farmiliar with METIS) allow the user to balance the load through various metrics, e.g., ensuring each partitiom has approximately the same number of elements or limiting the amount of communication between partitions. I feel a reason the colloquisium of DG being readily parallelizable is that a naive splitting of the problem into equal pieces can give a very efficient parallel implementation, even presenting super linear speedup in certain cases due to cache effects (see for example Baggag et. al. or Altmann et. al.). Whereas CG may require a more clever partitioning method. So it may be the case that changing spacial discretizations from DG to CG, say, would require one to also reconsider how to divide the mesh into subproblems.
answered Mar 14, 2014 at 2:06
$\begingroup$
$\endgroup$
From my many years writing FEM software, I believe that the statement that DG schemes are better suited to parallelization than CG schemes is apocryphal. It is frequently used in introductions of DG papers as a justification for DG methods, but I have never seen it substantiated with a reference that actually investigated the question. It is similar to every NSF proposal on a number theory project referencing "cryptography" as an area of broader impact, a statement that in this generality is also never substantiated.
In fact, I believe that with the one exception of explicit time stepping schemes and, possibly, problems where you have to invert a mass matrix, DG schemes are no better or worse than CG schemes if one investigated the cost of communication involved in either. I do mean this to be in a practical sense: sure, one may have to communicate less data, but I would imagine the difference in wallclock time to be negligible to all the other operations programs do on this data.
Of course, I would be delighted if anyone took up the challenge to prove me wrong!
answered Mar 14, 2014 at 0:22
$\begingroup$
$\endgroup$
Just as it is the case with most general statements about numerical schemes, the answer depends on the exact circumstances you're looking at. First of all, the advantages of DG concerning parallelization mainly pay off in case of explicit time-integration schemes because of
- The cell-local mass matrix of DG schemes (so you don't have to apply the inverse of the mass matrix globally)
- A favorable ratio of CPU-local work (volume integrals) to communication related work (edge integrals), especially for higher orders
While these statements apply to generic DG discretizations, real HPC applications (say, using several thousand processors) require some more effort concerning the parallelization strategy in order maintain a good scaling. This paper shows, for example, how one can achieve almost perfect scaling up to one cell per processor. This is certainly something you cannot expect from a continuous FEM, but as mentioned before, implicit schemes are totally different thing.
$\begingroup$
$\endgroup$
1
When assembling a stiffness matrix, the data stored in an element in continuous (nodal) FEM has to be communicated to all its nodal neighbours. In contrast, DGFEM requires the element data to be communicated to all its face neighbours. In 1D nodal and face neighbours are identical, but in 3D the difference can be quite large: For a regular hexahedral mesh, there are 26 nodal neighbours but only 6 face neighbours. For irregular meshes with many high-valence vertices, the situation gets worse for CG, while it stays the same for DG.
-
$\begingroup$ True, but is what you say of any practical concern? In other words, if you measured the time for communicating these elements in a real FEM program and compared it to the time necessary to compute the matrix entries, would it matter? $\endgroup$ Commented Mar 14, 2014 at 0:16
$\begingroup$
$\endgroup$
DG for hyperbolic PDE can be used as a replacement for finite volume schemes. In finite volume as in finite difference, when you increase the order of the scheme, your stencil increases. This makes parallelization more difficult, since for each scheme order, you have different stencil. At partition boundaries, you must ensure that all required cells from the neigbouring partition for the particular order of the scheme are available. But with DG, no matter what order the scheme is, each cell communicates only with its face neighbours. So compared between finite volume/difference and DG, one can say the DG is easier to parallelize.
