FFT, FMM, and Multigrid on the Road to Exascale: performance challenges and opportunities

Abstract

FFT, FMM, and multigrid methods are widely used fast and highly scalable solvers for elliptic PDEs. However, emerging large-scale computing systems are introducing challenges in comparison to current petascale computers. Recent efforts (Dongarra et al. 2011) have identified several constraints in the design of exascale software that includes massive concurrency, resilience management, exploiting the high performance of heterogeneous systems, energy efficiency, and utilizing the deeper and more complex memory hierarchy expected at exascale. In this paper, we perform a model-based comparison of the FFT, FMM, and multigrid methods in the context of these projected constraints. In addition, we use performance models to offer predictions about the expected performance on upcoming exascale system configurations based on current technology trends.

References in corpus (1)

• Fast Multipole Method as a Matrix-Free Hierarchical Low-Rank Approximation

Cited by in corpus (6)

• Hybrid multigrid methods for high-order discontinuous Galerkin discretizations
• High-order arbitrary Lagrangian-Eulerian discontinuous Galerkin methods for the incompressible Navier-Stokes equations
• FLUPS: a Fourier-based Library of Unbounded Poisson Solvers
• Quantifying the Performance Benefits of Partitioned Communication in MPI
• Mass-Zero constrained molecular dynamics for electrostatic interactions
• A multigrid reduction framework for domains with symmetries