Asynchronous Stabilisation and Assembly Techniques for Additive Multigrid

Abstract

Multigrid solvers are among the best solvers in the world, but once
applied in the real world there are issues they must overcome. Many multigrid
phases exhibit low concurrency. Mesh and matrix assembly are challenging to
parallelise and introduce algorithmic latency. Dynamically adaptive codes exacerbate
these issues. Multigrid codes require the computation of a cascade of matrices and
dynamic adaptivity means these matrices are recomputed throughout the solve.
Existing methods to compute the matrices are expensive and delay the solve. Non-
trivial material parameters further increase the cost of accurate equation integration.
We propose to assemble all matrix equations as stencils in a delayed element-wise
fashion. Early multigrid iterations use cheap geometric approximations and more
accurate updated stencil integrations are computed in parallel with the multigrid
cycles. New stencil integrations are evaluated lazily and asynchronously fed to the
solver once they become available. They do not delay multigrid iterations. We
deploy stencil integrations as parallel tasks that are picked up by cores that would
otherwise be idle. Coarse grid solves in multiplicative multigrid also exhibit limited
concurrency. Small coarse mesh sizes correspond to small computational workload
and require costly synchronisation steps. This acts as a bottleneck and delays
solver iterations. Additive multigrid avoids this restriction, but becomes unstable
for non-trivial material parameters as additive coarse grid levels tend to overcorrect.
This leads to oscillations. We propose a new additive variant, adAFAC-x, with a
stabilisation parameter that damps coarse grid corrections to remove oscillations.
Per-level we solve an additional equation that produces an auxiliary correction.
The auxiliary correction can be computed additively to the rest of the solve and
uses ideas similar to smoothed aggregation multigrid to anticipate overcorrections.
Pipelining techniques allow adAFAC-x to be written using single-touch semantics
on a dynamically adaptive mesh.