A regression-based approach to scalability prediction

ABSTRACT

Many applied scientific domains are increasingly relying on large-scale parallel computation. Consequently, many large clusters now have thousands of processors. However, the ideal number of processors to use for these scientific applications varies with both the input variables and the machine under consideration, and predicting this processor count is rarely straightforward. Accurate prediction mechanisms would provide many benefits, including improving cluster efficiency and identifying system configuration or hardware issues that impede performance.

We explore novel regression-based approaches to predict parallel program scalability. We use several program executions on a small subset of the processors to predict execution time on larger numbers of processors. We compare three different regression-based techniques: one based on execution time only; another that uses per-processor information only; and a third one based on the global critical path. These techniques provide accurate scaling predictions, with median prediction errors between 6.2% and 17.3% for seven applications.

REFERENCES

• 1: S. R. Alam and J. S. Vetter. Hierarchical model validation of symbolic performance models of scientific applications. In Euro-Par, Aug. 2006.
• 2: Sadaf R. Alam , Jeffrey S. Vetter , Pratul K. Agarwal , Al Geist, Performance characterization of molecular dynamics techniques for biomolecular simulations, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1122983]
• 3: D. Bailey, J. Barton, T. Lasinski, and H. Simon. The NAS parallel benchmarks. RNR-91-002, NASA Ames Research Center, Aug. 1991.
• 4: Vasanth Balasundaram , Geoffrey Fox , Ken Kennedy , Ulrich Kremer, A static performance estimator to guide data partitioning decisions, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.213-223, April 21-24, 1991, Williamsburg, Virginia, United States
• 5: R. Bell, A. Malony, and S. Shende. ParaProf: A Portable, Extensible, and Scalable Tool for Parallel Performance Profile Analysis. In Proceedings of the International Conference on Parallel and Distributed Computing (Euro-Par 2003), pages 17--26, Aug. 2003.
• 6: J. Brehm, P. H. Worley, and M. Madhukar. Performance modeling for SPMD message-passing programs. Concurrency: Practice and Experience, 10(5):333--357, Apr. 1998.
• 7: S. Browne , J. Dongarra , N. Garner , K. London , P. Mucci, A scalable cross-platform infrastructure for application performance tuning using hardware counters, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.42-es, November 04-10, 2000, Dallas, Texas, United States
• 8: Bryan Buck , Jeffrey K. Hollingsworth, An API for Runtime Code Patching, International Journal of High Performance Computing Applications, v.14 n.4, p.317-329, November 2000 [doi>10.1177/109434200001400404]
• 9: Graham Carey , Joe Schmidt , Vineet Singh , Dennis Yelton, A scalable, object-oriented finite element solver for partial differential equations on multicomputers, Proceedings of the 6th international conference on Supercomputing, p.387-396, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143438]
• 10: David E. Culler , Richard M. Karp , David Patterson , Abhijit Sahay , Eunice E. Santos , Klaus Erik Schauser , Ramesh Subramonian , Thorsten von Eicken, LogP: a practical model of parallel computation, Communications of the ACM, v.39 n.11, p.78-85, Nov. 1996 [doi>10.1145/240455.240477]
• 11: Luiz A. de Rose , Daniel A. Reed, SvPablo: A Multi-Language Architecture-Independent Performance Analysis System, Proceedings of the 1999 International Conference on Parallel Processing, p.311, September 21-24, 1999
• 12: T. R. P. for Statistical Computing. http://www.r-project.org/.
• 13: John L. Gustafson, Reevaluating Amdahl's law, Communications of the ACM, v.31 n.5, p.532-533, May 1988 [doi>10.1145/42411.42415]
• 14: Jeffrey K. Hollingsworth, Critical Path Profiling of Message Passing and Shared-Memory Programs, IEEE Transactions on Parallel and Distributed Systems, v.9 n.10, p.1029-1040, October 1998 [doi>10.1109/71.730530]
• 15: E. Ipek, B. R. de Supinski, M. Schulz, and S. A. McKee. An approach to performance prediction for parallel applications. In Euro-Par, pages 196--205, Aug 2005.
• 16: D. J. Kerbyson , H. J. Alme , A. Hoisie , F. Petrini , H. J. Wasserman , M. Gittings, Predictive performance and scalability modeling of a large-scale application, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.37-37, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582071]
• 17: Jesús Labarta , Sergi Girona , Vincent Pillet , Toni Cortes , Luis Gregoris, DiP: A Parallel Program Development Environment, Proceedings of the Second International Euro-Par Conference on Parallel Processing-Volume II, p.665-674, August 26-29, 1996
• 18: Benjamin C. Lee , David M. Brooks , Bronis R. de Supinski , Martin Schulz , Karan Singh , Sally A. McKee, Methods of inference and learning for performance modeling of parallel applications, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA [doi>10.1145/1229428.1229479]
• 19: Gordon Lyon , Raghu Kacker , Arnaud Linz, A scalability test for parallel code, Software—Practice & Experience, v.25 n.12, p.1299-1314, Dec. 1995 [doi>10.1002/spe.4380251202]
• 20: Gabriel Marin , John Mellor-Crummey, Cross-architecture performance predictions for scientific applications using parameterized models, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 21: G. Marin and J. Mellor-Crummey. Application insight through performance modeling. In IEEE International Performance Computing and Communications Conference, Apr 2007.
• 22: M. Müller, H. Brunst, M. Jurenz, A. Knüpfer, M. Lieber, H. Mix, and W. Nagel. Developing Scalable Applications with Vampir, VampirServer and VampirTrace. In Proceedings of the Minisymposium on Scalability and Usability of HPC Programming Tools at PARCO 2007, to appear, Sept. 2007.
• 23: Daniel Nussbaum , Anant Agarwal, Scalability of parallel machines, Communications of the ACM, v.34 n.3, p.57-61, March 1991 [doi>10.1145/102868.102871]
• 24: Fabrizio Petrini , Darren J. Kerbyson , Scott Pakin, The Case of the Missing Supercomputer Performance: Achieving Optimal Performance on the 8,192 Processors of ASCI Q, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.55, November 15-21, 2003
• 25: V. Pillet, J. Labarta, T. Cortes, and S. Girona. PARAVER: A tool to visualise and analyze parallel code. In Proceedings of WoTUG-18: Transputer and Occam Developments, volume 44 of Transputer and Occam Engineering, pages 17--31, Apr. 1995.
• 26: Philip C. Roth , Barton P. Miller, On-line automated performance diagnosis on thousands of processes, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1122984]
• 27: M. Schulz. Extracting critical path graphs from MPI applications. In IEEE Cluster, Sep 2005.
• 28: Jaswinder Pal Singh , John L. Hennessy , Anoop Gupta, Scaling Parallel Programs for Multiprocessors: Methodology and Examples, Computer, v.26 n.7, p.42-50, July 1993 [doi>10.1109/MC.1993.274941]
• 29: Allan Snavely , Laura Carrington , Nicole Wolter , Jesus Labarta , Rosa Badia , Avi Purkayastha, A framework for performance modeling and prediction, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-17, November 16, 2002, Baltimore, Maryland
• 30: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
• 31: Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
• 32: Frederick C. Wong , Richard P. Martin , Remzi H. Arpaci-Dusseau , David E. Culler, Architectural requirements and scalability of the NAS parallel benchmarks, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.41-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331573]
• 33: Patrick H. Worley, The effect of time constraints on scaled speedup, SIAM Journal on Scientific and Statistical Computing, v.11 n.5, p.838-858, September 1990 [doi>10.1137/0911050]
• 34: Leo T. Yang , Xiaosong Ma , Frank Mueller, Cross-Platform Performance Prediction of Parallel Applications Using Partial Execution, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.40, November 12-18, 2005 [doi>10.1109/SC.2005.20]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development

General Terms:
Experimentation, Measurement

Keywords:
MPI, modeling, prediction, regression, scalability