Premium
A stochastic performance model for pipelined Krylov methods
Author(s) -
Morgan Hannah,
Knepley Matthew G.,
Sanan Patrick,
Scott L. Ridgway
Publication year - 2016
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.3820
Subject(s) - speedup , latency (audio) , computation , computer science , parallel computing , multiplication (music) , sparse matrix , matrix multiplication , algorithm , noise (video) , mathematics , artificial intelligence , telecommunications , physics , combinatorics , quantum mechanics , image (mathematics) , quantum , gaussian
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.