A stochastic performance model for pipelined Krylov methods
Authors:
- 31 March 2016
- journal article
- research article
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 28 (18) , 4532-4542
Abstract
Summary: Pipelined Krylov methods seek to ameliorate the latency due to inner products necessary for projection by overlapping it with the computation associated with sparse matrix‐vector multiplication. We clarify a folk theorem that this can only result in a speedup of 2× over the naive implementation. Examining many repeated runs, we show that stochastic noise also contributes to the latency, and we model this using an analytical probability distribution. Our analysis shows that speedups greater than 2× are possible with these algorithms. Copyright © 2016 John Wiley & Sons, Ltd.Keywords
All Related Versions
Funding Information
- National Science Foundation (OCI‐1147680)
- National Science Foundation (DMS‐0920960, DMS‐1226019)
This publication has 13 references indexed in Scilit:
- Hiding global synchronization latency in the preconditioned Conjugate Gradient algorithmParallel Computing, 2014
- Hiding Global Communication Latency in the GMRES Algorithm on Massively Parallel MachinesSIAM Journal on Scientific Computing, 2013
- Characterizing application sensitivity to OS interference using kernel-level noise injection2008
- Implementation and performance analysis of non-blocking collective operations for MPI2007
- Pipelined Mixed Precision Algorithms on FPGAs for Fast and Accurate PDE Solvers from Low Precision Components2006
- Iterative Methods for Sparse Linear Systems2003
- Electromagnetic scattering with the boundary integral method on MIMD systems1999
- Reducing the effect of global communication in GMRES(m) and CG on parallel distributed memory computersApplied Numerical Mathematics, 1995
- Probability1993
- s-step iterative methods for symmetric linear systemsJournal of Computational and Applied Mathematics, 1989