TY - JOUR
T1 - FFT, FMM, and multigrid on the road to exascale
T2 - Performance challenges and opportunities
AU - Ibeid, Huda
AU - Olson, Luke
AU - Gropp, William
N1 - Funding Information:
The authors would like to thank Prof. David Keyes (KAUST) for many insightful discussions. This material is based in part upon work supported by the Department of Energy, National Nuclear Security Administration, under Award Number DE-NA0002374.
Funding Information:
The authors would like to thank Prof. David Keyes (KAUST) for many insightful discussions. This material is based in part upon work supported by the Department of Energy , National Nuclear Security Administration , under Award Number DE-NA0002374 . Huda Ibeid is a postdoctoral researcher at the University of Illinois at Urbana-Champaign. She received her B.Sc. degree in Computer Engineering from the University of Jordan and her Ph.D. degree in Computer Science from the King Abdullah University of Science and Technology (KAUST) in 2016. Her research interests include fast algorithms for particle-based simulations, fast solvers for large-scale linear systems, the design of parallel numerical algorithms, and performance modeling. Luke Olson is a professor in the Department of Computer Science at the University of Illinois at Urbana-Champaign. He received his Ph.D. is in applied mathematics from the University of Colorado at Boulder in 2003 and his research interests include sparse matrix computations, multigrid methods, finite elements methods, and parallel numerical algorithms. William Gropp is a director and chief scientist of the National Center for Supercomputing Applications and holds the Thomas M. Siebel Chair in the Department of Computer Science at the University of Illinois in Urbana-Champaign. He received his Ph.D. in Computer Science from Stanford University in 1982. He was on the faculty of the Computer Science Department of Yale University from 1982 to 1990 and from 1990 to 2007, and he was a member of the Mathematics and Computer Science Division at Argonne National Laboratory. His research interests are in parallel computing, software for scientific computing, and numerical methods for partial differential equations. He is a fellow of ACM, IEEE, and SIAM and a member of the National Academy of Engineering.
Publisher Copyright:
© 2019 Elsevier Inc.
PY - 2020/2
Y1 - 2020/2
N2 - 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 include 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.
AB - 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 include 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.
KW - Exascale
KW - Fast Fourier transform
KW - Fast multipole method
KW - Multigrid
KW - Performance modeling
UR - http://www.scopus.com/inward/record.url?scp=85074439422&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85074439422&partnerID=8YFLogxK
U2 - 10.1016/j.jpdc.2019.09.014
DO - 10.1016/j.jpdc.2019.09.014
M3 - Article
AN - SCOPUS:85074439422
VL - 136
SP - 63
EP - 74
JO - Journal of Parallel and Distributed Computing
JF - Journal of Parallel and Distributed Computing
SN - 0743-7315
ER -