Examples of PDE computations using parallelism in both space and time

Question

In the numerical solution of initial boundary value PDEs, it is very common to employ parallelism in space. It is much less common to employ some form of parallelism in the time discretization, and that parallelism is usually much more limited. I'm aware of an increasing number of codes and published works demonstrating temporal parallelism, but none of them include spatial parallelism.

Are there examples of implementations that include parallelism in both space and time? I'm interested in both publications and available codes.

I just found this preprint, combining Parareal with spatial domain decomposition for incompressible Navier-Stokes on 2048 processors: http://icsweb.inf.unisi.ch/preprints/preprints/file201203.pdf — David Ketcheson, Jul 04 '12 at 20:46

Matthew Emmett · Accepted Answer · 2012-08-23T02:53:43.567

The PFASST (Parallel Full Approximation Scheme in Space and Time) and PEPC (Pretty Efficient Parallel Coulomb) algorithms have recently been used together to achieve parallelism in both space and time.

PFASST does the time parallelism, PEPC does the space parallelism. The results of this were recently presented at the DD21 conference, and we have prepared a submission for SC12 describing the combination of PFASST+PEPC.

A "small" problem consisting of 4 million particles (PEPC is a parallel N-body solver) was shown to scale well up to 8192 cores on JUGENE using only PEPC (ie, only parallel in space). Beyond this, communication costs became significant and the parallel efficiency began to degrade. The addition of PFASST allows this fixed sized problem to be run on 262,144 cores (ie, we filled up JUGENE) by using 32 "time" processors (each of which consists of 8192 "spatial" cores).

Although the parallel efficiency of time-parallel algorithms isn't 100%, we were able to obtain speedups of about 6.5x using 32 PFASST processors with this PFASST+PEPC configuration.

Here is a link to a preprint: A massively space-time parallel N-body solver

Matt that sounds pretty neat, please update with a link to the draft when you're ready. — Aron Ahmadia, Jul 01 '12 at 07:49
Awesome, just what I was looking for. And nice work, by the way. — David Ketcheson, Jul 01 '12 at 09:39
Thanks! I'll try to post a link soon. BTW, I have also successfully used a PETSc DA to distribute the spatial domain of a shallow-water solver inside of PyPFASST. — Matthew Emmett, Jul 01 '12 at 14:36

score 4 · Answer 2 · answered Jun 30 '12 at 23:40

4

There are also space-time DG and continuous Galerkin methods. After choice of quadrature, space-time DG with a structured grid in the time direction is equivalent to an implicit Runge-Kutta method. The space-time DG method, however, allows for different step sizes in different parts of the domain, a case that is difficult to analyze for implicit RK methods. Space-time multigrid methods can also be applied in this context.

answered Jun 30 '12 at 23:40

Jed Brown

25,650
3
72
130

I don't understand how this is time-parallel. Can you point to an example or explain more? – David Ketcheson Jul 01 '12 at 09:40
When you make the domain larger, you get to decompose into more domains of a given size. Space-time methods add the time dimension to the domain, thus increasing parallelism. Note that there are huge computational benefits to doing several related things at once so for maximum performance with modest sized time slabs, you might still decompose only in space and vectorize locally in the time dimension. – Jed Brown Jul 01 '12 at 21:09

score 2 · Answer 3 · answered Jul 01 '12 at 08:44

Once you consider space-time parallelsim, the subdomain is space-time over multiple time levels. A method called waveform relaxation exploits space-time subdomains but parallelize only in space (no partition in time dimension). So a cartesian of the space partition and time partition gives a kind of space-time parallelism. You can find a paper on such a cartesian method here. As Jed Brown mentioned in his answer, space-time method not only gives more flexible parallelsim but also adaptivity for discretization. On the latter topic, you can google works of Schwab, see also their project. For the work exploiting both parallelism and adaptivity, you can watch at R. Haynes' homepage.

score 1 · Answer 4 · answered Jun 30 '12 at 22:38

1

Have a look at the Parareal algorithm and its related work like spectral deferred correction (a simple Google search turns up quite a lot of material). The basic idea is to use a coarse "mesh" in time and do a rough time stepping, but then go back over it and perform corrections on a finer time scale. It seems to be used mostly in fluid simulations, but I'm in the area of electromagnetics, so I can't really say much more about it. The only reason I know about it is because I attended a seminar on the deferred correction approach and it seemed very interesting that any kind of parallelization could be done in time.

answered Jun 30 '12 at 22:38

Victor Liu

4,480
18
28

I know of those, but can you point to a case where they are used in conjunction with spatial parallelism? – David Ketcheson Jul 01 '12 at 09:38
To be clear, deferred or defect correction schemes by themselves don't have anything to do with Parareal and/or time-parallel schemes. – Matthew Emmett Jul 01 '12 at 16:37

score 1 · Answer 5 · answered Jul 01 '12 at 13:01

The multiple shooting method used in optimal control is designed in such a way that the sub-problems on each shooting interval can be solved in parallel. I don't know of papers that couple this with spatial parallelism (there are not that many optimal control problems that have been solved in the past where the equation is a time-dependent spatial PDE) but it would be obvious how to do parallelism in both space and time.

Examples of PDE computations using parallelism in both space and time

5 Answers5

Linked