Scaling Structured Multigrid to 500K+ Cores Through Coarse-Grid Redistribution

DOI10.1137/17M1146440zbMATH Open1391.65122arXiv1803.02481WikidataQ129489648 ScholiaQ129489648MaRDI QIDQ3174783FDOQ3174783

Andrew Reisner, Luke Olson, J. D. Moulton

Publication date: 18 July 2018

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Abstract: The efficient solution of sparse, linear systems resulting from the discretization of partial differential equations is crucial to the performance of many physics-based simulations. The algorithmic optimality of multilevel approaches for common discretizations makes them a good candidate for an efficient parallel solver. Yet, modern architectures for high-performance computing systems continue to challenge the parallel scalability of multilevel solvers. While algebraic multigrid methods are robust for solving a variety of problems, the increasing importance of data locality and cost of data movement in modern architectures motivates the need to carefully exploit structure in the problem. Robust logically structured variational multigrid methods, such as Black Box Multigrid (BoxMG), maintain structure throughout the multigrid hierarchy. This avoids indirection and increased coarse-grid communication costs typical in parallel algebraic multigrid. Nevertheless, the parallel scalability of structured multigrid is challenged by coarse-grid problems where the overhead in communication dominates computation. In this paper, an algorithm is introduced for redistributing coarse-grid problems through incremental agglomeration. Guided by a predictive performance model, this algorithm provides robust redistribution decisions for structured multilevel solvers. A two-dimensional diffusion problem is used to demonstrate the significant gain in performance of this algorithm over the previous approach that used agglomeration to one processor. In addition, the parallel scalability of this approach is demonstrated on two large-scale computing systems, with solves on up to 500K+ cores.

Full work available at URL: https://arxiv.org/abs/1803.02481

zbMATH Keywords

scalabilitymultigridstructureparallelstencil

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Parallel numerical computation (65Y05) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Multigrid Tutorial, Second Edition
• Black box multigrid
• Matrix-dependent prolongations and restrictions in a blackbox multigrid solver
• An optimal robust equidistribution method for two-dimensional grid adaptation based on Monge-Kantorovich optimization
• The black box multigrid numerical homogenization algorithm
• Designing broadcasting algorithms in the postal model for message-passing systems
• Black box multigrid for nonsymmetric problems
• A massively parallel geometric multigrid solver on hierarchically distributed grids
• The Multi-Grid Method for the Diffusion Equation with Strongly Discontinuous Coefficients
• Fast and robust solvers for pressure-correction in bubbly flow problems
• Black Box Multigrid with coarsening by a factor of three
• Scalable algebraic multigrid on 3500 processors
• Towards Textbook Efficiency for Parallel Multigrid
• Reducing parallel communication in algebraic multigrid through sparsification
• A MODEL AND IMPLEMENTATION OF MULTIGRID FOR MASSIVELY PARALLEL COMPUTERS

Cited In (3)

• On the Recursive Structure of Multigrid Cycles
• The effect of approximate coarsest-level solves on the convergence of multigrid V-cycle methods
• Monolithic multigrid for implicit Runge-Kutta discretizations of incompressible fluid flow

Uses Software

• PFLOTRAN

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Semicoarsening Multigrid on Distributed Memory Machines 👍 👎
• Scalable implementation of the parallel multigrid method on massively parallel computers 👍 👎
• Multiple coarse grid acceleration for multiscale multigrid computation 👍 👎
• Scalable algebraic multigrid on 3500 processors 👍 👎
• An efficient coarse-grained parallel algorithm for global-local multiscale computations on massively parallel systems 👍 👎
• Multiscale extensions for enhancing coarse grid computations 👍 👎

This page was built for publication: Scaling Structured Multigrid to 500K+ Cores Through Coarse-Grid Redistribution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3174783)