Cache-optimized and low-overhead implementations of additive Schwarz methods for high-order FEM multigrid computations

Abstract

This contribution presents data-locality optimizations of the additive Schwarz method (ASM) based on the fast-diagonalization method defined on overlapping cell-centric and vertex-star patches in the context of high-order matrix-free finite-element computations on modern CPU-based hardware. The developments are guided by detailed performance models of the ASM in the context of Chebyshev iterations when used as smoothers for p-multigrid. The proposed efficient implementation of ASM adopts concepts known from cell-loop infrastructures for efficient operator evaluation, in particular, the storage of information per geometric entity and the cache-friendly interleaving of cell loops and vector updates as a means to increase data locality. We use the latter concept for both applying the weights required by ASM and performing the vector updates required by the Chebyshev iteration, which are memory-bound operations with non-negligible costs in comparison to efficient operator evaluation. Furthermore, the solution of a scalar Poisson problem on a highly anisotropic and an unstructured mesh with p-multigrid using the developed smoothers indicates that efficient implementations of the additive Schwarz method can outperform optimized point-Jacobi preconditioners already for simple problems despite being more than twice as expensive per iteration. Even though ASM introduces additional communication steps per smoother application, the reduced number of iterations can lead to improved parallel scalability for intermediate problem sizes. At the scaling limit, the results are inconclusive due to these two opposing effects.