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

Tijmen P. Collignon ; Martin B. Van Gijzen

International Journal of Applied Mathematics and Computer Science, Tome 20 (2010), p. 109-121 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 2010-01-01

Zbl 1300.65097

EUDML-ID : urn:eudml:doc:207967

Bibliographie

[000] Anderson, D. P., Cobb, J., Korpela, E., Lebofsky, M. and Werthimer, D. (2002). SETI@home: An experiment in public-resource computing, Communications of the ACM 45(11): 56-61.

[001] Axelsson, O. (1994). Iterative Solution Methods, Cambridge University Press, New York, NY. | Zbl 0795.65014

[002] Beck, M., Arnold, D., Bassi, A., Berman, F., Casanova, H., Dongarra, J., Moore, T., Obertelli, G., Plank, J., Swany, M., Vadhiyar, S. and Wolski, R. (2002). Middleware for the use of storage in communication, Parallel Computing 28(12): 1773-1787. | Zbl 1043.68019

[003] Bisseling, R. H. (2004). Parallel Scientific Computation: A Structured Approach Using BSP and MPI, Oxford University Press, New York, NY. | Zbl 1059.65133

[004] Boghosian, B., Coveney, P., Dong, S., Finn, L., Jha, S., Karniadakis, G. and Karonis, N. (2006). Nektar, SPICE and Vortonics: Using federated grids for large scale scientific applications, Workshop on Challenges of Large Applications in Distributed Environments (CLADE)/15th International Symposium on High Performance Distributed Computing (HPDC-15), Paris, France, pp. 34-42.

[005] Brady, T., Guidolin, M. and Lastovetsky, A. (2008). Experiments with SmartGridSolve: Achieving higher performance by improving the GridRPC model, 9th IEEE/ACM International Conference on Grid Computing, Tsukuba, Japan, pp. 49-56.

[006] Brady, T., Konstantinov, E. and Lastovetsky, A. (2006). SmartNetSolve: High level programming system for high performance Grid computing, Proceedings of the 20th International Parallel and Distributed Processing Symposium (IPDPS 2006), Rhodes Island, Greece, (on CD-ROM).

[007] Brakkee, E., Vuik, C. and Wesseling, P. (1997). Domain decomposition for the incompressible Navier-Stokes equations: Solving subdomain problems accurately and inaccurately, in R. Glowinski, J. Périaux and Z-C. Shi and O. Widlund (Eds), Domain Decomposition Methods in Sciences and Engineering, John Wiley & Sons, Chichester, pp. 443-451. | Zbl 0915.76063

[008] Caron, E., Del-Fabbro, B., Desprez, F., Jeannot, E. and Nicod, J.-M. (2005). Managing data persistence in network enabled servers, Scientific Programming 13(4): 333-354.

[009] Caron, E. and Desprez, F. (2006). DIET: A scalable toolbox to build network enabled servers on the grid, International Journal of High Performance Computing Applications 20(3): 335-352.

[010] Chronopoulos, A. T. and Gear, C. W. (1989). S-step iterative methods for symmetric linear systems, Journal of Computational and Applied Mathematics 25(2): 153-168. | Zbl 0669.65021

[011] Collignon, T. P. and van Gijzen, M. B. (2007). Implementing the conjugate gradient method on a grid computer, Proceedings of the International Multiconference on Computer Science and Information Technology, Wisła, Poland, Vol. 2, pp. 527-540.

[012] Collignon, T. P. and van Gijzen, M. B. (2008). Solving large sparse linear systems efficiently on Grid computers using an asynchronous iterative method as a preconditioner, Technical report DUT 08-08, Delft University of Technology, Delft. | Zbl 1216.65040

[013] Collignon, T. P. and van Gijzen, M. B. (2010). Parallel scientific computing on loosely coupled networks of computers, in B. Koren and C. Vuik (Eds), Advanced Computational Methods in Science and Engineering, Lecture Notes in Computational Science and Engineering, Vol. 71, Springer, Berlin, pp.79-106. | Zbl 1187.68029

[014] Desprez, F. and Jeannot, E. (2004). Improving the GridRPC model with data persistence and redistribution, ISPDC '04: Proceedings of the 3rd International Symposium on Parallel and Distributed Computing/3rd International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Networks (ISPDC/HeteroPar'04), Cork, Ireland, pp. 193-200.

[015] Dong, S., Karniadakis, G. E. and Karonis, N. T. (2005). Crosssite computations on the TeraGrid, Computing in Science and Engineering 7(5): 14-23.

[016] Dongarra, J., Li, Y., Shi, Z., Fike, D., Seymour, K. and YarKhan, A. (2007). Homepage of NetSolve/GridSolve, http://icl.cs.utk.edu/netsolve/.

[017] Dongarra, J. J., Duff, I. S., Sorensen, D. C. and van der Vorst, H. A. (1998). Numerical Linear Algebra for High Performance Computers, Society for Industrial and Applied Mathematics, Philadelphia, PA. | Zbl 0914.65014

[018] Foster, I. and Kesselman, C. (2004). The Grid: Blueprint for a New Computing Infrastructure, 2nd Edn., Morgan Kaufman Publishers, San Fransisco, CA.

[019] Hestenes, M. R. and Stiefel, E. (1952). Methods of conjugate gradients for solving linear systems, Journal of Research of National Bureau Standards 49(6): 409-436. | Zbl 0048.09901

[020] Karonis, N. T., Toonen, B. and Foster, I. (2003). MPICHG2: A grid-enabled implementation of the message passing interface, Journal of Parallel and Distributed Computing 63(5): 551-563. | Zbl 1059.68526

[021] Lastovetsky, A., Zuo, X. and Zhao, P. (2005). A non-intrusive and incremental approach to enabling direct communications in RPC-based grid programming systems, Technical report, UCD School of Computer Science and Informatics, Dublin, http://www.csi.ucd.ie/content/non-intrusive-and-incremental-approach-enabling-direct-communications-rpc-based-grid-program.

[022] Lee, C., Nakada, H. and Tanimura, Y. (2007). GridRPC Working Group, http://forge.ogf.org/sf/projects/gridrpc-wg/.

[023] Mercier, G. (2006). MPICH-Madeleine. An MPI implementation for heterogeneous clusters of clusters, http://runtime.futurs.inria.fr/mpi/.

[024] Mirghani, B., Tryby, M., Baessler, D., Karonis, N., Ranhthan, R. and Mahinthakumar, K. (2005). Development and performance analysis of a simulation-optimization framework on TeraGrid Linux clusters, 6th LCI International Conference on Linux Clusters: The HPC Revolution 2005, Chapel Hill, NC, USA.

[025] Mittal, R. and Iaccarino, G. (2005). Immersed boundary methods, Annual Review of Fluid Mechanics 37: 239-261. | Zbl 1117.76049

[026] Peskin, C. (2002). The immersed boundary method, Acta Numerica 11: 479-517. | Zbl 1123.74309

[027] Sato, M., Boku, T. and Takahashi, D. (2003). OmniRPC: A Grid RPC system for parallel programming in cluster and Grid environment, CCGRID '03: Proceedings of the 3rd International Symposium on Cluster Computing and the Grid, Tokyo, Japan, pp. 206-213.

[028] Seinstra, F. J. and Verstoep, K. (2007). DAS-3: The distributed ASCI supercomputer 3, http://www.cs.vu.nl/das3/.

[029] Seymour, K., Nakada, H., Matsuoka, S., Dongarra, J., Lee, C. and Casanova, H. (2002). Overview of GridRPC: A remote procedure call API for grid computing, GRID '02: Proceedings of the 3rd International Workshop on Grid Computing, Baltimore, MD, USA, pp. 274-278. | Zbl 1024.68846

[030] Seymour, K., YarKhan, A., Agrawal, S. and Dongarra, J. (2005). NetSolve: Grid enabling scientific computing environments, in L. Grandinetti (Ed.), Grid Computing and New Frontiers of High Performance Processing, Elsevier, New York, NY.

[031] Tanaka, Y., Nakada, H., Sekiguchi, S., Suzumura, T. and Matsuoka, S. (2003). Ninf-G: A reference implementation of RPC-based programming middleware for Grid computing, Journal of Grid Computing 1(1): 41-51.

[032] Tang, J. M. and Vuik, C. (2007a). On deflation and singular symmetric positive semi-definite matrices, Journal of Computational and Applied Mathematics 206(2): 603-614. Tang, J. and Vuik, C. (2007b). Efficient deflation methods applied to 3-D bubbly flow problems, Electronic Transactions on Numerical Analysis 26: 330-349. | Zbl 1125.65028

[033] van der Pijl, S., Segal, A., Vuik, C. and Wesseling, P. (2005). A mass-conserving level-set method for modelling of multi-phase flows, International Journal for Numerical Methods in Fluids 47: 339-361. | Zbl 1065.76160

[034] van Kan, J. (1986). A second-order accurate pressure correction scheme for viscous incompressible flow, SIAM Journal on Scientific and Statistical Computing 7(3): 870-891. | Zbl 0594.76023

[035] Vastenhouw, B. and Bisseling, R. H. (2005). A two-dimensional data distribution method for parallel sparse matrix-vector multiplication, SIAM Review 47(1): 67-95. | Zbl 1083.65044

[036] Whaley, R. C. and Petitet, A. (2005). Minimizing development and maintenance costs in supporting persistently optimized BLAS, Software: Practice and Experience 35(2): 101-121.

[037] Wyrzykowski, R., Meyer, N., Olas, T., Kuczynski, L., Ludwiczak, B., Czaplewski, C. and Oldziej, S. (2009). Metacomputations on the CLUSTERIX grid, in B. Kågström, E. Elmroth, J. Dongarra and J. Wasniewski (Eds), Applied Parallel Computing: State of the Art in Scientific Computing. 8th International Workshop, PARA 2006, Umeå, Sweden, June 18-21, 2006, Revised Selected Papers, Lecture Notes in Computer Science, Vol. 4699, Springer, Berlin/Heidelberg, pp. 489-500.

[038] Wyrzykowski, R., Meyer, N. and Stroinski, M. (2005). Concept and implementation of CLUSTERIX: National cluster of linux systems, 6th LCI International Conference on Linux Clusters: The HPC Revolution 2005, Chapel Hill, NC, USA.

[039] YarKhan, A., Seymour, K., Sagi, K., Shi, Z. and Dongarra, J. (2006). Recent developments in GridSolve, International Journal of High Performance Computing Applications (IJHPCA) 20(1): 131-141.

[040] Zheng, Y., Bassi, A., Beck, M., Plank, J. S. and Wolski, R. (2004). Internet Backplane Protocol: C API 1.4, Technical report, Department of Computer Science, University of Tennessee, Knoxville, TN.

[041] Zuo, X. and Lastovetsky, A. (2007). Experiments with a software component enabling NetSolve with direct communications in a non-intrusive and incremental way, Proceedings of the 21st International Parallel and Distributed Processing Symposium (IPDPS 2007), Long Beach, CA, USA.