Estimation of the speedup of distributed applications

Zuberek, W.M.

Proc. Int. Conf. on Advances in the Internet, Processing, Systems, and Interdisciplinary Research (IPSI'04); Studenica Monastery, Serbia, 4-5 June 2004.

Abstract:

Speedup is one of the main performance characteristics of distributed applications. It is defined as the ratio of application's execution time on a single processor to the execution time, of the same workload, on a system composed on N processors. This paper analyzes, in very general terms, the speedup that can be achieved in distributed environments and shows why some applications scale very well with the number of processors while others have strict limitations on the speedup that can be achieved in distributed environments. The existence of such limitations simply means that a straightforward distribution of a (sequential) workload is not a satisfactory approach, and new algorithms are needed to use distributed environments in a more satisfactory way.

Keywords:

Distributed systems, speedup estimation, computation-to-communication ratio, iterative methods, state space generation, SETI@home.

References:

• S.C. Allmaier and G. Horton, "Parallel shared-memory state-space exploration in stochastic modeling"; in Solving Irregularly Structured Problems in Parallel (Lecture Notes in Computer Science 1253); pp.207-218, Springer-Verlag 1997.
• S.C. Allmaier, S. Dalibor, and D. Kreische, "Parallel graph generation algorithms for shared and distributed memory machines"; in Parallel Computing: Fundamentals, Applications and New Directions (Advances in Parallel Computing 12); pp.581-588, Elsevier, North-Holland 1997.
• O. Axelsson, Iterative solution methods; Cambridge University Press 1994.
• R.H. Chan, T.F. Chan, and G.H. Golub (eds.), Iterative methods in scientific computing; Springer-Verlag 1997.
• G. Couloris, J. Dollimore, T. Kindberg, Distributed systems: concepts and design (2-nd ed.); Addison-Wesley 1994.
• L. Erlander, "Distributed computing: an introduction"; Extreme Tech, April 4, 2002.
• V.K. Garg, Principles of distributed systems; Kluwer Academic Publ. 1998.
• A. Greenbaum, Iterative methods for solving linear systems (Frontiers in Applied Mathematics 17); SIAM 1997.
• A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Manchek, and V. Sunderam, {\em {PVM}: Parallel Virtual Machine. {a} users' guide and tutorial}. \newblock MIT Press 1994. \bibitem {SCSE} E. Korpela, D. Werthimer, D. Ansrson, J. Cobb, and M. Lebofsky, "SETI@home: massively distributed computing for SETI"; Computing in Science and Engineering, vol.3, no.1, pp.78-83, 2001.
• P. Marenzoni, S. Caselli, and G. Conte, "Analysis of large GSPN models: a distributed solution tool"; Proc. IEEE Int. Workshop on Petri Nets and Performance Models (PNPM'97), pp.122-131, 1997.
• I. Rada, "Distributed generation of state space for timed Petri nets"; M.Sc. Thesis, Department of Computer Science, Memorial University of Newfoundland, St.John's, Canada 2000.
• I. Rada and W.M. Zuberek, "Distributed generation of state space for timed Petri nets"; Proc. High Performance Computing Symposium 2001, Seattle, WA, pp.219-227, 2001.
• M.R. Steed and M.J. Clement, "Performance prediction of PVM programs"; Proc. 10-th Int. Parallel Processing Symposium (IPPS-96), pp.803-807, 1996.
• J.A. Stankovic, "Distributed computing"; in Distributed computing systems, IEEE CS Press 1994.
• T.L. Sterling, How to build a Beowulf: a guide to the implementation and application of a PC clusters; MIT Press 1999.
• B. Wilkinson, Computer architecture - design and performance (2-nd ed.); Prentice Hall 1996.
• Beowulf home page is "www.beowulf.org".
• SETI@home home page is "setiathome.ssl.berkeley.edu".

Available in pdf and postscript.