Search

Geometric multigrid solvers within adaptive mesh refinement (AMR) applications often reach a point where further coarsening of the grid becomes impractical as individual sub domain sizes approach unity. At this point the most common solution is to use a bottom solver, such as BiCGStab, to reduce the residual by a fixed factor at the coarsest level. Each iteration of BiCGStab requires multiple global reductions (MPI collectives). As the number of BiCGStab iterations required for convergence grows with problem size, and the time for each collective operation increases with machine scale, bottom solves in large-scale applications can constitute a significant fraction of the overall multigrid solve time. In this paper, we implement, evaluate, and optimize a communication-avoiding s-step formulation of BiCGStab (CABiCGStab for short) as a high-performance, distributed-memory bottom solver for geometric multigrid solvers. This is the first time s-step Krylov subspace methods have been leveraged to improve multigrid bottom solver performance. We use a synthetic benchmark for detailed analysis and integrate the best implementation into BoxLib in order to evaluate the benefit of a s-step Krylov subspace method on the multigrid solves found in the applications LMC and Nyx on up to 32,768 cores on the Cray XE6 at NERSC. Overall, we see bottom solver improvements of up to 4.2x on synthetic problems and up to 2.7x in real applications. This results in as much as a 1.5x improvement in solver performance in real applications. © 2014 IEEE.

Krylov subspace methods are iterative methods for solving large, sparse linear systems and eigenvalue problems in a variety of scientific domains. On modern computer architectures, communication, or movement of data, takes much longer than the equivalent amount of computation. Classical formulations of Krylov subspace methods require data movement in each iteration, creating a performance bottleneck, and thus increasing runtime. This motivated s-step, or communicationavoiding, Krylov subspace methods, which only perform data movement every O(s) iterations. We present new communication-avoiding Krylov subspace methods, CA-BICG and CA-BICGSTAB. We are the first to provide derivations of these methods. For both sequential and parallel implementations, our methods reduce data movement by a factor of O(s) versus the classical algorithms. We implement various polynomial bases and perform convergence experiments to enable comparison with the classical algorithm. We discuss recent results in improving both numerical behavior and performance in communication-avoiding Krylov subspace methods. [ABSTRACT FROM AUTHOR]