Cross-Platform Performance Prediction of Parallel Applications Using Partial Execution

ABSTRACT

Performance prediction across platforms is increasingly important as developers can choose from a wide range of execution platforms. The main challenge remains to perform accurate predictions at a low-cost across different architectures. In this paper, we derive an affordable method approaching cross-platform performance translation based on relative performance between two platforms. We argue that relative performance can be observed without running a parallel application in full. We show that it suffices to observe very short partial executions of an application since most parallel codes are iterative and behave predictably manner after a minimal startup period. This novel prediction approach is observation-based. It does not require program modeling, code analysis, or architectural simulation. Our performance results using real platforms and production codes demonstrate that prediction derived from partial executions can yield high accuracy at a low cost. We also assess the limitations of our model and identify future research directions on observationbased performance prediction.

REFERENCES

• 1: Vikram Adve , Rizos Sakellariou, Application Representations for Multiparadigm Performance Modeling of Large-Scale Parallel Scientific Codes, International Journal of High Performance Computing Applications, v.14 n.4, p.304-316, November 2000 [doi>10.1177/109434200001400403]
• 2: Brian Armstrong , Rudolf Eigenmann, Performance Forecasting: Towards a Methodology for Characterizing Large Computational Applications, Proceedings of the 1998 International Conference on Parallel Processing, p.518, August 10-14, 1998
• 3: Rajive Bagrodia , Ewa Deeljman , Steven Docy , Thomas Phan, Performance prediction of large parallel applications using parallel simulations, Proceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming, p.151-162, May 04-06, 1999, Atlanta, Georgia, United States
• 4: [4] D. H. Bailey and A. Snavely. Performance modeling: Understanding the present and predicting the future. In Euro-Par Conference, August 2005.
• 5: Robert H. Bell, Jr. , Lizy K. John, Improved automatic testcase synthesis for performance model validation, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088164]
• 6: Julien Bourgeois , François Spies, Performance Prediction of an NAS Benchmark Program with ChronosMix Environment, Proceedings from the 6th International Euro-Par Conference on Parallel Processing, p.208-216, August 29-September 01, 2000
• 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: Mark J. Clement , Michael J. Quinn, Automated performance prediction for scalable parallel computing, Parallel Computing, v.23 n.10, p.1405-1420, Oct. 1997 [doi>10.1016/S0167-8191(97)00066-5]
• 9: David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 19-22, 1993, San Diego, California, United States
• 10: [10] W. Dick and M. Heath. Whole system simulation of solid propellant rockets. In Proceedings of the 38th AIAA/ASME/SAE/ASEE Joint Propulsion Conference and Exhibit, Indianapolis, IN, July 2002.
• 11: [11] DOE Office of Science. Database and File Systems Working Group Summary, SLAC Data Management Workshop, 2003.
• 12: Evelyn Duesterwald , Calin Cascaval , Sandhya Dwarkadas, Characterizing and Predicting Program Behavior and its Variability, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.220, September 27-October 01, 2003
• 13: Marcio Faerman , Alan Su , Richard Wolski , Francine Berman, Adaptive performance prediction for distributed data-intensive applications, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.36-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331568]
• 14: Mark R. Fahey , Jeff Candy, GYRO: A 5-D Gyrokinetic-Maxwell Solver, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.26, November 06-12, 2004 [doi>10.1109/SC.2004.27]
• 15: Thomas Fahringer , Hans P. Zima, A static parameter based performance prediction tool for parallel programs, Proceedings of the 7th international conference on Supercomputing, p.207-219, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.165971]
• 16: Stephen A. Jarvis , Daniel P. Spooner , Helene N. Lim Choi Keung , Graham R. Nudd , Junwei Cao , Subhash Saini, Performance Prediction and Its Use in Parallel and Distributed Computing Systems, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.276.1, April 22-26, 2003
• 17: W. M. Jones , L. W. Pang , W. B. Ligon , D. Stanzione, Bandwidth-aware co-allocating meta-schedulers for mini-grid architectures, Proceedings of the 2004 IEEE International Conference on Cluster Computing, p.45-54, September 20-23, 2004
• 18: 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]
• 19: Darren J. Kerbyson , Adolfy Hoisie , Harvey J. Wasserman, A Comparison between the Earth Simulator and AlphaServer Systems Using Predictive Application Performance Models, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.64.2, April 22-26, 2003
• 20: Walter B. Ligon III, Research Directions in Parallel I/O for Clusters, Proceedings of the IEEE International Conference on Cluster Computing, p.436, September 23-26, 2002
• 21: Chu-Cheow Lim , Yoke-Hean Low , Boon-Ping Gan , Wentong Cai, Implementation Lessons of Performance Prediction Tool for Parallel Conservative Simulation (Research Note), Proceedings from the 6th International Euro-Par Conference on Parallel Processing, p.189-193, August 29-September 01, 2000
• 22: Wei Liu , Michael C. Huang, EXPERT: expedited simulation exploiting program behavior repetition, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006228]
• 23: Xiaosong Ma , Marianne Winslett , Jonghyun Lee , Shengke Yu, Improving MPI-IO Output Performance with Active Buffering Plus Threads, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.68.2, April 22-26, 2003
• 24: 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
• 25: Ahuva W. Mu'alem , Dror G. Feitelson, Utilization, Predictability, Workloads, and User Runtime Estimates in Scheduling the IBM SP2 with Backfilling, IEEE Transactions on Parallel and Distributed Systems, v.12 n.6, p.529-543, June 2001 [doi>10.1109/71.932708]
• 26: Ralf Reussner , Gunnar Hunzelmann, Achieving Performance Portability with SKaMPI for High-Performance MPI Programs, Proceedings of the International Conference on Computational Science-Part II, p.841-850, May 28-30, 2001
• 27: Hongzhang Shan , Leonid Oliker , Rupak Biswas, Job Superscheduler Architecture and Performance in Computational Grid Environments, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.44, November 15-21, 2003
• 28: Jens Simon , Jens-Michael Wierum, Accurate Performance Prediction for Assively Parallel Systems and Its Applications, Proceedings of the Second International Euro-Par Conference on Parallel Processing-Volume II, p.675-688, August 26-29, 1996
• 29: [29] C. Smith. Open source metascheduling for virtual organizations with the community scheduler framework (CSF). Technical whitepaper, http://www.platform.com/resources/whitepapers/.
• 30: Warren Smith , Ian T. Foster , Valerie E. Taylor, Predicting Application Run Times Using Historical Information, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.122-142, March 30, 1998
• 31: 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
• 32: [32] Supercluster.org. SILVER design specification. http://www.supercluster.org/silver/specoverview.shtml.
• 33: Valerie Taylor , Xingfu Wu , Rick Stevens, Prophesy: an infrastructure for performance analysis and modeling of parallel and grid applications, ACM SIGMETRICS Performance Evaluation Review, v.30 n.4, March 2003 [doi>10.1145/773056.773060]
• 34: Arjan J. C. van Gemund, Symbolic Performance Modeling of Parallel Systems, IEEE Transactions on Parallel and Distributed Systems, v.14 n.2, p.154-165, February 2003 [doi>10.1109/TPDS.2003.1178879]
• 35: Jeffrey S. Vetter , Frank Mueller, Communication characteristics of large-scale scientific applications for contemporary cluster architectures, Journal of Parallel and Distributed Computing, v.63 n.9, p.853-865, September 2003 [doi>10.1016/S0743-7315(03)00104-7]
• 36: Alan S. Wagner , Halsur V. Sreekantaswamy , Samuel T. Chanson, Performance Models for the Processor Farm Paradigm, IEEE Transactions on Parallel and Distributed Systems, v.8 n.5, p.475-489, May 1997 [doi>10.1109/71.598275]
• 37: Xiaodong Zhang , Zhichen Xu, Multiprocessor scalability predictions through detailed program execution analysis, Proceedings of the 9th international conference on Supercomputing, p.97-106, July 03-07, 1995, Barcelona, Spain [doi>10.1145/224538.224549]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Partial evaluation

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory