Analyzing the Effect of Local Rounding Error Propagation on the Maximal Attainable Accuracy of the Pipelined Conjugate Gradient Method

Siegfried Cools 1 Emrullah Fatih Yetkin 2 Emmanuel Agullo 3 Luc Giraud 2 Wim Vanroose 1
1 Universiteit Antwerpen [Antwerpen]
2 HiePACS - High-End Parallel Algorithms for Challenging Numerical Simulations
LaBRI - Laboratoire Bordelais de Recherche en Informatique, Inria Bordeaux - Sud-Ouest
3 LaBRI - Laboratoire Bordelais de Recherche en Informatique
Abstract : Pipelined Krylov subspace methods typically offer improved strong scaling on parallel HPC hardware compared to standard Krylov subspace methods for large and sparse linear systems. In pipelined methods the traditional synchronization bottleneck is mitigated by overlapping time-consuming global communications with useful computations. However, to achieve this communication-hiding strategy, pipelined methods introduce additional recurrence relations for a number of auxiliary variables that are required to update the approximate solution. This paper aims at studying the influence of local rounding errors that are introduced by the additional recurrences in the pipelined Conjugate Gradient (CG) method. Specifically, we analyze the impact of local round-off effects on the attainable accuracy of the pipelined CG algorithm and compare it to the traditional CG method. Furthermore, we estimate the gap between the true residual and the recursively computed residual used in the algorithm. Based on this estimate we suggest an automated residual replacement strategy to reduce the loss of attainable accuracy on the final iterative solution. The resulting pipelined CG method with residual replacement improves the maximal attainable accuracy of pipelined CG while maintaining the efficient parallel performance of the pipelined method. This conclusion is substantiated by numerical results for a variety of benchmark problems.
Keywords : maximal attainable accuracy conjugate gradients rounding errors pipelin-global communication parallelization latency hiding
Document type :
Journal articles
Complete list of metadatas

Cited literature [46 references]  Display  Hide  Download
https://hal.inria.fr/hal-01753411
Contributor : Luc Giraud <>
Submitted on : Friday, March 30, 2018 - 1:00:11 PM
Last modification on : Thursday, May 9, 2019 - 11:58:04 AM

File

simax_2018_pipelinedAccuracy.p...
Files produced by the author(s)

Identifiers

Collections

CNRS | UNIV-BORDEAUX | INSMI | LABRI | INRIA | TDS-MACS

Citation

Siegfried Cools, Emrullah Fatih Yetkin, Emmanuel Agullo, Luc Giraud, Wim Vanroose. Analyzing the Effect of Local Rounding Error Propagation on the Maximal Attainable Accuracy of the Pipelined Conjugate Gradient Method. SIAM Journal on Matrix Analysis and Applications, Society for Industrial and Applied Mathematics, 2018, 39 (1), pp.426 - 450. ⟨10.1137/17M1117872⟩. ⟨hal-01753411⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

247

Files downloads

234

 

 

Contact

archive-ouverte@inria.fr

 

</div