3
$\begingroup$

I see things like this deal.II example, (ctrl + f for "superMUC") which seems to show some pretty impressive scaling (nearly twice as fast for twice as many CPU cores for a wide range of cores). I'm aware of some other software that manages this as well--especially if one uses GPUs. In the example at hand, Poisson's equation is solved subject to homogeneous Dirchlet boundary conditions using matrix free methods and a multigrid preconditioner.

My question is: In the context of state of the art implementation of finite element methods, is there any need for improvement or deviation from the above, even across the broader class of PDEs one might be interested in? The tutorial seems to suggest that nonlinear or time-dependent PDEs make the deal.II approach even more attractive rather than less, which makes sense given the nature of matrix free methods. Are there then, for example, PDEs or boundary conditions above for which matrix free solvers are not practical? Or at least perhaps problems for which matrix free ideal preconditioners are not known?

Is there any room for additional research here? That is, if one had an idea for parallelism which could be applied "on top of" domain decomposition and the above scheme while also being able to guarantee scaling up to another $2N$ processors, where $N$ is some limit above which the above does not scale? Or is it the case that any such research would be met with "What's the matter? Just apply existing methods with $2N$ processors."

$\endgroup$
2
  • $\begingroup$ Usually, your fine linear scaling breaks down as soon as your equations are time dependent. Then, every node has to do communication with other nodes which will not scale linearly. $\endgroup$
    – MPIchael
    Commented Apr 24, 2023 at 7:26
  • $\begingroup$ @MPIchael No, this is not a good argument. For stationary problems, you also need to communicate. In fact, time dependent problems can scale even better if you use an explicit time stepping method and you can hide communication of the previous time step's state behind the work necessary to update to the current time step's state. $\endgroup$ Commented Apr 24, 2023 at 16:57

1 Answer 1

13
$\begingroup$

There are multiple questions in the post, so let me address these separately:

Scaling: Every parallel program is composed of sequential and parallel tasks, and Amdahl's law then guarantees that there is a limit to how well a program scales. Martin Kronbichler's group (which wrote the linked to step-37) has spent an enormous amount of time finding the sequential parts of the program and reducing the time spent there and/or parallelizing them as well. As a consequence, they can show good scaling up to 300k processes in some cases. But experience shows that every time you go from $N$ to $2N$ processes, you will find another part of the code that now is the bottleneck, and you will need to address that to make a program scale further. Experience also shows that for finite element methods, this can actually be done (and Martin's group is among the best in doing so) and I have no particular reason to believe that they can't also go to 1M processes and more -- but it's going to take a good amount of time and access to some of the largest machines in the world to make that happen.

There are also components of the parallel parts of the program that can be bottlenecks. For example, every finite element code needs to do dot products between vectors (in fact, many!) and that requires a reduction operation where the local parts of the dot product are summed up over all processes. This is done in a tree reduction algorithm which has $\log(P)$ complexity -- and you can actually see that factor if you get access to a machine that is just large enough. There is very little you can do about that if you just use existing algorithms -- which is why people are starting to implement and use communication-hiding Krylov subspace methods and similar.

Speed: At the end of the day, scalability does not matter -- speed does. What is a dog slow code good for that you can scale to large machines, if there is another code that can solve the same problem in 1/10th the time on 1/100th the number of processes? As a consequence, working on speed is also an important area, and there, too, like finding the sequential bottlenecks, more work always needs to be done. This is why people port their stuff from CPUs to GPUs, for example: Not because they hope for better scalability, but because they want faster execution.

Equations: You also ask about whether there are equations where the matrix-free approach of step-37 is not appropriate or simply does not work. At the end, the only equations we know how to solve efficiently are elliptic problems such as the Laplace equations, and ones for which we can devise good preconditioners by solving elliptic equations (e.g., for the Stokes equations). That's because for these we know how to build multigrid methods as preconditioners -- the only known class of optimal preconditioner. But for all other equations that we want to solve implicitly, we are in a decent amount of trouble -- so take your favorite non-standard equation (say, a pattern-forming equation, or the high-frequency case of the Helmholtz equation, or the linearization of some random nonlinear equation) and we no longer know how to build good preconditioners, let alone in a matrix-free way. So there is still a lot of work left in this area regarding making things scale well to large problems.

The only other category of problems where we know we can scale well is for explicit time discretizations of hyperbolic problems -- say for high-speed flow. In those cases, we do not have to solve a linear system in each step (typically the largest component of finite element solvers by run-time), and codes for this kind of problem have also been shown to scale to very large machines. For these kinds of problems, you're back to just finding the sequential bottlenecks of problems. At the same time, if you have been listening to the talks of David Keyes over the past 20 years, you will have heard that these problems can often be solved faster with implicit time stepping methods -- where each time step is vastly slower, but you can take vastly larger time steps. In those cases, you're typically back to the question of how to find efficient and scalable solvers for the linear systems, and that is not always entirely clear: More research is certainly necessary.

Summary: I think we will still have plenty to do regarding scalability and speed of finite element codes. If you ask Martin, at any given time he can probably give you a list of ten places in his code base (including deal.II) that he knows are or will be bottlenecks and that need to be addressed. My perspective is more on the solver side, and I can always give you ten examples of problems for which we currently don't have good solvers and preconditioners. We're not going to run out of things to research for a good long while :-)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.