Creator:
Collignon, Tijmen P. ; Van Gijzen, Martin B.
Contributor:
Korbicz, Józef (1951- ) - red. ; Uciński, Dariusz - red.
Title:
Two implementations of the preconditioned conjugate gradient method on heterogeneous computing grids
Group publication title:
Subject and Keywords:
grid computing ; large sparse linear systems ; iterative methods ; conjugate gradient methods ; Chronopoulos/Gear CG ; GridSolve middleware ; bubbly flows
Abstract:
Efficient iterative solution of large linear systems on grid computers is a complex problem. The induced heterogeneity andvolatile nature of the aggregated computational resources present numerous algorithmic challenges. This paper describesa case study regarding iterative solution of large sparse linear systems on grid computers within the software constraintsof the grid middleware GridSolve and within the algorithmic constraints of preconditioned Conjugate Gradient (CG) typemethods. ; We identify the various bottlenecks induced by the middleware and the iterative algorithm. We consider thestandard CG algorithm of Hestenes and Stiefel, and as an alternative the Chronopoulos/Gear variant, a formulation thatis potentially better suited for grid computing since it requires only one synchronisation point per iteration, instead oftwo for standard CG. In addition, we improve the computation-to-communication ratio by maximising the work in thepreconditioner. ; In addition to these algorithmic improvements, we also try to minimise the communication overhead withinthe communication model currently used by the GridSolve middleware. We present numerical experiments on 3D bubblyflow problems using heterogeneous computing hardware that show lower computing times and better speed-up for theChronopoulos/Gear variant of conjugate gradients. Finally, we suggest extensions to both the iterative algorithm and themiddleware for improving granularity.
Publisher:
Zielona Góra: Uniwersytet Zielonogórski
Date:
Resource Type:
DOI:
Pages:
Source:
AMCS, Volume 20, Number 1 (2010) ; click here to follow the link