Avoiding communication in sparse matrix computations
Authors:
- 1 April 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2008 IEEE International Symposium on Parallel and Distributed Processing
- No. 15302075,p. 1-12
Abstract
The performance of sparse iterative solvers is typically limited by sparse matrix-vector multiplication, which is itself limited by memory system and network performance. As the gap between computation and communication speed continues to widen, these traditional sparse methods will suffer. In this paper we focus on an alternative building block for sparse iterative solvers, the "matrix powers kernel" [x, Ax, A2x, ..., Akx], and show that by organizing computations around this kernel, we can achieve near-minimal communication costs. We consider communication very broadly as both network communication in parallel code and memory hierarchy access in sequential code. In particular, we introduce a parallel algorithm for which the number of messages (total latency cost) is independent of the power k, and a sequential algorithm, that reduces both the number and volume of accesses, so that it is independent of k in both latency and bandwidth costs. This is part of a larger project to develop "communication-avoiding Krylov subspace methods," which also addresses the numerical issues associated with these methods. Our algorithms work for general sparse matrices that "partition well". We introduce parallel performance models of matrices arising from 2D and 3D problems and show predicted speedups over a conventional algorithm of up to 7times on a petaflop-scale machine and up to 22times on computation across the grid. Analogous sequential performance models of the same problems predict speedups over a conventional algorithm of up to 10times on an out-of-core implementation, and up to 2.5times when we use our ideas to reduce off-chip latency and bandwidth to DRAM. Finally, we validate the model on an out-of-core sequential implementation and measured a speedup of over 3times, which is close to the predicted speedup.Keywords
This publication has 12 references indexed in Scilit:
- Optimization of sparse matrix-vector multiplication on emerging multicore platforms2007
- Implicit and explicit optimizations for stencil computations2006
- Impact of modern memory subsystems on cache optimizations for stencil computations2005
- OSKI: A library of automatically tuned sparse matrix kernelsJournal of Physics: Conference Series, 2005
- Latency lags bandwithCommunications of the ACM, 2004
- Using time skewing to eliminate idle time due to memory bandwidth and network limitations2002
- Rescheduling for Locality in Sparse Matrix Computations2001
- New tiling techniques to improve cache temporal locality1999
- s-step iterative methods for symmetric linear systemsJournal of Computational and Applied Mathematics, 1989
- Practical Use of Polynomial Preconditionings for the Conjugate Gradient MethodSIAM Journal on Scientific and Statistical Computing, 1985