FFT, FMM, and multigrid on the road to exascale: Performance challenges and opportunities

Research output: Contribution to journalArticle

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 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.

Original languageEnglish (US)
Pages (from-to)63-74
Number of pages12
JournalJournal of Parallel and Distributed Computing
Volume136
DOIs
StatePublished - Feb 2020

Fingerprint

Multigrid Method
Fast Fourier transforms
Memory Hierarchy
Elliptic PDE
Heterogeneous Systems
Resilience
Performance Model
Concurrency
Energy Efficiency
Energy efficiency
High Performance
Model-based
Data storage equipment
Configuration
Software
Computing
Prediction
Trends
Context
Design

Keywords

  • Exascale
  • Fast Fourier transform
  • Fast multipole method
  • Multigrid
  • Performance modeling

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Cite this

@article{9bee372881974556acf3ec37da6a671c,
title = "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 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.",
keywords = "Exascale, Fast Fourier transform, Fast multipole method, Multigrid, Performance modeling",
author = "Huda Ibeid and Luke Olson and William Gropp",
year = "2020",
month = "2",
doi = "10.1016/j.jpdc.2019.09.014",
language = "English (US)",
volume = "136",
pages = "63--74",
journal = "Journal of Parallel and Distributed Computing",
issn = "0743-7315",
publisher = "Academic Press Inc.",

}

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

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 -