Avoiding communication in geometric multigrid

Talk overview • Coarse grid solver (“bottom solver”) often the bottleneck in geometric multigrid methods due to high cost of global communication • Replacing classical solver with communication-avoiding variant can asymptotically reduce global communication • Implementation, evaluation, and optimization of a communication-avoiding formulation of the Krylov solver routine (CA-BICGSTAB) as a high-performance, distributed-memory bottom solve routine for geometric multigrid • Bottom solver speedups: 4.2x in miniGMG benchmark, up to 2.5x in real applications • First use of communication-avoiding Krylov subspace methods for improving multigrid bottom solve performance 2 Geometric multigrid 3 • Numerical simulations in a wide array of scientific disciplines require solving elliptic/parabolic PDEs on a hierarchy of adaptively refined meshes • Geometric multigrid (GMG) is a good choice for many problems • Krylov subspace methods commonly used for bottom solve routines – Only require approximate solve, matrix-free representation – GMG + Krylov method available as solver option in many available software packages (e.g., BoxLib, Chombo, PETSc, hypre) • Consists of a series of V-cycles (“U-cycles”) – When further coarsening becomes infeasible, solve distributed coarse grid problem – Other options: agglomerate and solve local coarse grid problem, switch to algebraic, etc. bottom-solve Krylov subspace methods • Iterative methods based on projection onto expanding subspaces • In iteratio