Methods of inference and learning for performance modeling of parallel applications

ABSTRACT

Increasing system and algorithmic complexity combined with a growing number of tunable application parameters pose significant challenges for analytical performance modeling. We propose a series of robust techniques to address these challenges. In particular, we apply statistical techniques such as clustering, association, and correlation analysis, to understand the application parameter space better. We construct and compare two classes of effective predictive models: piecewise polynomial regression and artifical neural networks. We compare these techniques with theoretical analyses and experimental results. Overall, both regression and neural networks are accurate with median error rates ranging from 2.2 to 10.5 percent. The comparable accuracy of these models suggest differentiating features will arise from ease of use, transparency, and computational efficiency.

REFERENCES

• 1: A. Petit, R. Whaley, J. Dongarra, and A. Cleary. HPL - A portable implementation of the high-performance LINPACK benchmark for distributed-memory computers.
• 2: Peter N. Brown , Robert D. Falgout , Jim E. Jones, Semicoarsening Multigrid on Distributed Memory Machines, SIAM Journal on Scientific Computing, v.21 n.5, p.1823-1834, April 2000 [doi>10.1137/S1064827598339141]
• 3: L. Carrington, A. Snavely, X. Gao, and N. Wolter. A performance prediction framework for scientific applications. In Proceedings International Conference on Computational Science Workshop on Performance Modeling and Analysis (PMA03), June 2003.
• 4: L. Carrington, N. Wolter, A. Snavely, and C. Lee. Applying an automatic framework to produce accurate blind performance predictions of full-scale HPC applications. In Department of Defense Users Group Conference, June 2004.
• 5: R. Caruana, S. Lawrence, and C. Giles. Overfitting in neural nets: backpropagation, conjugate gradient, and early stopping. In Neural Information Processing Systems (NIPS), November 2002.
• 6: Robert D. Falgout , Ulrike Meier Yang, hypre: A Library of High Performance Preconditioners, Proceedings of the International Conference on Computational Science-Part III, p.632-641, April 21-24, 2002
• 7: Frank E. Harrell, Jr., Regression Modeling Strategies, Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 8: E. Ipek, B. de Supinski, M. Schulz, and S. McKee. An approach to performance prediction for parallel applications. Proceedings of Euro-Par, Springer LNCS, 3648, August 2005.
• 9: Engin Ïpek , Sally A. McKee , Rich Caruana , Bronis R. de Supinski , Martin Schulz, Efficiently exploring architectural design spaces via predictive modeling, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 10: P. Joseph, K. Vaswani, and M.J. Thazhuthaveetil. Construction and use of linear regression models for processor performance analysis. In Proceedings of the 12th Symposium on High Performance Computer Architecture, Austin, Texas, February 2006.
• 11: 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]
• 12: B. Lee and D. Brooks. Accurate and efficient regression modeling for microarchitectural regression models. In Proceedings International Symposium on High-Performance Computer Architecture (HPCA-13), February 2007.
• 13: 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
• 14: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 15: M. Riedmiller and H. Braun. A direct adaptive method for faster backpropagation learning: The RPROP algorithm. In Proceedings IEEE International Conference on Neural Networks, May 1993.
• 16: C. Stone. Comment: Generalized additive models. Statistical Science, 1:312--314, 1986.
• 17: 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]
• 18: Joshua J. Yi , David J. Lilja , Douglas M. Hawkins, Improving Computer Architecture Simulation Methodology by Adding Statistical Rigor, IEEE Transactions on Computers, v.54 n.11, p.1360-1373, November 2005 [doi>10.1109/TC.2005.184]
• 19: A. Zell and et. al. SNNS: Stuttgart neural network simulator, user manual, version 4.2. In User Manual, Version 4.2, University of Stuttgart.

INDEX TERMS

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

General Terms:
Experimentation, Measurement, Performance

Keywords:
neural networks, numerical methods, performance prediction, regression, statistics