Two implementations of the preconditioned conjugate gradient method on heterogeneous computing grids
Two implementations of the preconditioned conjugate gradient method on heterogeneous computing grids
复制标题
预条件共轭梯度法在异构计算网格上的两种实现
DOI：
10.2478/v10006-010-0008-4
复制
发表时间：
2010
影响因子：
2.8
通讯作者：
M. Gijzen
中科院分区：
文献类型：
--
作者：
T. Collignon;M. Gijzen
预条件共轭梯度法在异构计算网格上的两种实现大型线性方程组在网格计算机上的有效迭代求解是一个复杂的问题。聚合的计算资源的诱导的异质性和易失性的性质提出了许多算法的挑战。本文介绍了一个案例研究网格计算机上的大型稀疏线性系统的迭代求解网格中间件GridSolve的软件约束和预处理共轭梯度（CG）型方法的算法约束内。我们确定的中间件和迭代算法引起的各种瓶颈。我们认为标准CG算法的Hestenes和Stiefel，作为替代的Chronopoulos/齿轮的变体，一个配方，是潜在的更好地适合网格计算，因为它只需要一个同步点，而不是两个标准CG。此外，我们通过最大化预处理器中的工作来提高计算与通信的比率。除了这些算法的改进，我们还试图最大限度地减少GridSolve中间件目前使用的通信模型内的通信开销。我们提出了使用异构计算硬件的3D泡状流问题的数值实验，显示较低的计算时间和更好的速度为Chronopoulos/齿轮变体的共轭梯度。最后，我们建议扩展的迭代算法和中间件，以提高粒度。
Two implementations of the preconditioned conjugate gradient method on heterogeneous computing grids 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.