Speedup of distributed iterative solvers of large sparse systems of linear equations

Zuberek, W.M., and Perera, T.D.P.

WSEAS Transactions on Mathematics, vol.4, no.3, pp.281-288, 2005.

Abstract:

Many applications of computational methods in science and engineering require the solution of large sparse systems of linear equations. For such systems, iterative methods are often more attractive than direct methods because of their small (and constant) memory requirements. Moreover, the performance of iterative solvers can easily be improved by using distributed systems. For distributed applications, a common performance characteristic is the speedup, usually defined as the ratio of the execution time of an application on a single processor to the execution time of the same workload on a system composed of P processors. This paper estimates the speedup of distributed linear iterative solvers, analyzes the influence of different communication schemes on the speedup, and compares the estimates with the measurements of real distributed programs.

Keywords:

Distributed computing, speedup, computation-to-communication ratio, sparse systems of linear equations, iterative methods.

References:

• G.W. Althaus, E. Spedicato, Algorithms for large scale linear algebraic systems: applications in science and engineering; Kluwer Academic Publ. 1998.
• O. Axelsson, Iterative solution methods; Cambridge University Press 1994.
• R. Barrett, M.W. Berry, T.F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, H. van der Vorst, Templates for the solution of linear systems: building blocks for iterative methods; SIAM 1993.
• F. Berman, G. Fox, T. Hey, Grid computing: making the global infrastructure a reality; J. Wiley 2003.
• J.J. Dongarra, I.S. Duff, D.C. Sorenson, H.A. van der Horst, Numerical linear algebra for high-performance computers; SIAM 1998.
• L. Erlander, "Distributed computing: an introduction"; Extreme Tech, April 4, 2002.
• V.K. Garg, Principles of distributed systems; Kluwer Academic Publ. 1998.
• G.H. Golub, C.F. van Loan, Matrix computations; The Johns Hopkins Univ. Press 1983.
• A. Greenbaum, Iterative methods for solving linear systems (Frontiers in Applied Mathematics 17); SIAM 1997.
• W. Gropp, E. Lusk, A. Skjellum, Using MPI: portable parallel programming with the message-passing interface (2-nd ed.); MIT Press 1999.
• W. Hackbusch, Iterative solution of large sparse systems of equations (Applied Mathematical Sciences 95); Springer-Verlag 1995.
• S. Hamilton, "Taking Moore's law into the next century"; IEEE Computer Magazine, vol.32, no.1, 1999, pp.43-48.
• R. Merritt, "Intel, clusters on the rise in `Top 500 Supercomputer' list"; EE Times Online, November 18, 2003.
• Y. Saad, Iterative methods for sparse linear systems (2-nd ed.); SIAM 2003.
• R.A. Saleh, K.A. Gallivan, M-C. Chang, I.N. Hajj, D. Smart, T.N. Trick, "Parallel circuit simulation on supercomputers"; Proceedings of the IEEE, vol.77, no.12, 1989, pp.1915-1931.
• M.R. Steed, M.J. Clement, "Performance prediction of PVM programs"; Proc. 10-th Int. Parallel Processing Symposium (IPPS), 1996, pp.803-807.
• J.A. Stankovic, "Distributed computing"; in Distributed computing systems, IEEE CS Press 1994.
• H. van der Vorst, "Iterative methods for linear systems and implementation on parallel computers"; in Iterative methods in scientific computing; R.H. Chan, T.F. Chan, and G.H. Golub (eds.), Springer-Verlag 19999, pp.1-44.
• B. Wilkinson, Computer Architecture -- Design and Performance (2-nd ed.); Prentice Hall 1996.
• "www.beowulf.org" is Beowulf home page.
• "www.climateprediction.net" is ClimatePrediction home page.
• "setiathome.ssl.berkeley.edu" is SETI@home home page.

Available in pdf.