Title: Hiding global communication latency in the GMRES algorithm on massively parallel computers
Authors: Ghysels, Pieter ×
Ashby, Tom J.
Meerbergen, Karl
Vanroose, Wim #
Issue Date: Jan-2013
Publisher: SIAM
Series Title: SIAM Journal on Scientific Computing vol:35 issue:1 pages:C38-C71
Abstract: In the Generalized Minimal Residual Method (GMRES), the global all-to-all communication re-
quired in each iteration for orthogonalization and normalization of the Krylov base vectors is becoming a perfor-
mance bottleneck on massively parallel machines. Long latencies, system noise and load imbalance cause these
global reductions to become very costly global synchronizations. In this work, we propose the use of non-blocking
or asynchronous global reductions to hide these global communication latencies by overlapping them with other
communications and calculations. A pipelined variation of GMRES is presented in which the result of a global
reduction is only used one or more iterations after the communication phase has started. This way, global synchro-
nization is relaxed and scalability is much improved at the expense of some extra computations. The numerical
instabilities that inevitably arise due to the typical monomial basis by powering the matrix are reduced and often
annihilated by using Newton or Chebyshev bases instead. Our parallel experiments on a medium sized cluster
show significant speedups of the pipelined solvers compared to standard GMRES. An analytical model is used to
extrapolate the performance to future exascale systems.
ISSN: 1064-8275
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Numerical Analysis and Applied Mathematics Section
× corresponding author
# (joint) last author

Files in This Item:

There are no files associated with this item.

Request a copy


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science