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 (2010)

  • Volume: 20, Issue: 1, page 109-121
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Tijmen P. Collignon, and Martin B. Van Gijzen. "Two implementations of the preconditioned conjugate gradient method on heterogeneous computing grids." International Journal of Applied Mathematics and Computer Science 20.1 (2010): 109-121. <http://eudml.org/doc/207967>.

@article{TijmenP2010,
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.},
author = {Tijmen P. Collignon, Martin B. Van Gijzen},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {grid computing; large sparse linear systems; iterative methods; conjugate gradient methods; Chronopoulos/Gear CG; GridSolve middleware; bubbly flows},
language = {eng},
number = {1},
pages = {109-121},
title = {Two implementations of the preconditioned conjugate gradient method on heterogeneous computing grids},
url = {http://eudml.org/doc/207967},
volume = {20},
year = {2010},
}

TY - JOUR
AU - Tijmen P. Collignon
AU - Martin B. Van Gijzen
TI - Two implementations of the preconditioned conjugate gradient method on heterogeneous computing grids
JO - International Journal of Applied Mathematics and Computer Science
PY - 2010
VL - 20
IS - 1
SP - 109
EP - 121
AB - 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.
LA - eng
KW - grid computing; large sparse linear systems; iterative methods; conjugate gradient methods; Chronopoulos/Gear CG; GridSolve middleware; bubbly flows
UR - http://eudml.org/doc/207967
ER -

References

top
  1. 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. 
  2. Axelsson, O. (1994). Iterative Solution Methods, Cambridge University Press, New York, NY. Zbl0795.65014
  3. 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. Zbl1043.68019
  4. Bisseling, R. H. (2004). Parallel Scientific Computation: A Structured Approach Using BSP and MPI, Oxford University Press, New York, NY. Zbl1059.65133
  5. 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. 
  6. 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. 
  7. 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). 
  8. 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. Zbl0915.76063
  9. 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. 
  10. 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. 
  11. 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. Zbl0669.65021
  12. 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. 
  13. 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. Zbl1216.65040
  14. 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. Zbl1187.68029
  15. 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. 
  16. Dong, S., Karniadakis, G. E. and Karonis, N. T. (2005). Crosssite computations on the TeraGrid, Computing in Science and Engineering 7(5): 14-23. 
  17. Dongarra, J., Li, Y., Shi, Z., Fike, D., Seymour, K. and YarKhan, A. (2007). Homepage of NetSolve/GridSolve, http://icl.cs.utk.edu/netsolve/. 
  18. 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. Zbl0914.65014
  19. Foster, I. and Kesselman, C. (2004). The Grid: Blueprint for a New Computing Infrastructure, 2nd Edn., Morgan Kaufman Publishers, San Fransisco, CA. 
  20. 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. Zbl0048.09901
  21. 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. Zbl1059.68526
  22. 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. 
  23. Lee, C., Nakada, H. and Tanimura, Y. (2007). GridRPC Working Group, http://forge.ogf.org/sf/projects/gridrpc-wg/. 
  24. Mercier, G. (2006). MPICH-Madeleine. An MPI implementation for heterogeneous clusters of clusters, http://runtime.futurs.inria.fr/mpi/. 
  25. 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. 
  26. Mittal, R. and Iaccarino, G. (2005). Immersed boundary methods, Annual Review of Fluid Mechanics 37: 239-261. Zbl1117.76049
  27. Peskin, C. (2002). The immersed boundary method, Acta Numerica 11: 479-517. Zbl1123.74309
  28. 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. 
  29. Seinstra, F. J. and Verstoep, K. (2007). DAS-3: The distributed ASCI supercomputer 3, http://www.cs.vu.nl/das3/. 
  30. 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. Zbl1024.68846
  31. 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. 
  32. 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. 
  33. 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. Zbl1125.65028
  34. 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. Zbl1065.76160
  35. 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. Zbl0594.76023
  36. 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. Zbl1083.65044
  37. 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. 
  38. 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. 
  39. 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. 
  40. 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. 
  41. 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. 
  42. 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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.