<abstract xml:lang="en" xmlns="http://www.w3.org/1999/xhtml"><p>Efficient iterative solution of large linear systems on grid computers is a complex problem. The induced heterogeneity and volatile nature of the aggregated computational resources present numerous algorithmic challenges. This paper describes a case study regarding iterative solution of large sparse linear systems on grid computers within the software constraints of the grid middleware GridSolve and within the algorithmic constraints of preconditioned Conjugate Gradient (CG) type methods. We identify the various bottlenecks induced by the middleware and the iterative algorithm. We consider the standard CG algorithm of Hestenes and Stiefel, and as an alternative the Chronopoulos/Gear variant, a formulation that is potentially better suited for grid computing since it requires only one synchronisation point per iteration, instead of two for standard CG. In addition, we improve the computation-to-communication ratio by maximising the work in the preconditioner. In addition to these algorithmic improvements, we also try to minimise the communication overhead within the communication model currently used by the GridSolve middleware. We present numerical experiments on 3D bubbly flow problems using heterogeneous computing hardware that show lower computing times and better speed-up for the Chronopoulos/Gear variant of conjugate gradients. Finally, we suggest extensions to both the iterative algorithm and the middleware for improving granularity.</p></abstract>

Efficient iterative solution of large linear systems on grid computers is a complex problem. The induced heterogeneity and volatile nature of the aggregated computational resources present numerous algorithmic challenges. This paper describes a case study regarding iterative solution of large sparse linear systems on grid computers within the software constraints of the grid middleware GridSolve and within the algorithmic constraints of preconditioned Conjugate Gradient (CG) type methods. We identify the various bottlenecks induced by the middleware and the iterative algorithm. We consider the standard CG algorithm of Hestenes and Stiefel, and as an alternative the Chronopoulos/Gear variant, a formulation that is potentially better suited for grid computing since it requires only one synchronisation point per iteration, instead of two for standard CG. In addition, we improve the computation-to-communication ratio by maximising the work in the preconditioner. In addition to these algorithmic improvements, we also try to minimise the communication overhead within the communication model currently used by the GridSolve middleware. We present numerical experiments on 3D bubbly flow problems using heterogeneous computing hardware that show lower computing times and better speed-up for the Chronopoulos/Gear variant of conjugate gradients. Finally, we suggest extensions to both the iterative algorithm and the middleware for improving granularity.

Two implementations of the preconditioned conjugate gradient method on heterogeneous computing grids

Delft Institute of Applied Mathematics, Delft University of Technology, Mekelweg 4, 2628 CD, Delft, The Netherlands

International Journal of Applied Mathematics and Computer Science

Efficient iterative solution of large linear systems on grid computers is a complex problem. The induced heterogeneity and volatile nature of the aggregated...

Two implementations of the preconditioned conjugate gradient method on heterogeneous computing grids

Published Online: Mar 25, 2010

Page range: 109 - 121

DOI: https://doi.org/10.2478/v10006-010-0008-4

Keywords
grid computing, large sparse linear systems, iterative methods, conjugate gradient methods, Chronopoulos/Gear CG, GridSolve middleware, bubbly flows

This content is open access.

Two implementations of the preconditioned conjugate gradient method on heterogeneous computing grids

Published Online: Mar 25, 2010

Page range: 109 - 121

DOI: https://doi.org/10.2478/v10006-010-0008-4

Keywordsgrid computing, large sparse linear systems, iterative methods, conjugate gradient methods, Chronopoulos/Gear CG, GridSolve middleware, bubbly flows

This content is open access.

Keywords
grid computing, large sparse linear systems, iterative methods, conjugate gradient methods, Chronopoulos/Gear CG, GridSolve middleware, bubbly flows