Performance prediction based on inherent program similarity

ABSTRACT

A key challenge in benchmarking is to predict the performance of an application of interest on a number of platforms in order to determine which platform yields the best performance. This paper proposes an approach for doing this. We measure a number of microarchitecture-independent characteristics from the application of interest, and relate these characteristics to the characteristics of the programs from a previously profiled benchmark suite. Based on the similarity of the application of interest with programs in the benchmark suite, we make a performance prediction of the application of interest. We propose and evaluate three approaches (normalization, principal components analysis and genetic algorithm) to transform the raw data set of microarchitecture-independent characteristics into a benchmark space in which the relative distance is a measure for the relative performance differences. We evaluate our approach using all of the SPEC CPU2000 benchmarks and real hardware performance numbers from the SPEC website. Our framework estimates per-benchmark machine ranks with a 0.89 average and a 0.80 worst case rank correlation coefficient.

REFERENCES

• 1: Murali Annavaram , Ryan Rakvic , Marzia Polito , Jean-Yves Bouguet , Richard A. Hankins , Bob Davies, The Fuzzy Correlation between Code and Performance Predictability, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.93-104, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.34]
• 2: I-Cheng K. Chen , John T. Coffey , Trevor N. Mudge, Analysis of branch prediction via data compression, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.128-137, October 01-04, 1996, Cambridge, Massachusetts, United States
• 3: T. Conte. Insight, not (random) numbers. Keynote talk at the 2005 International Symposium on Performance Analysis of Systems and Software (ISPASS), Mar. 2005.
• 4: L. Eeckhout, J. Sampson, and B. Calder. Exploiting program microarchitecture independent characteristics and phase behavior for reduced benchmark suite simulation. In Proceedings of the 2005 IEEE International Symposium on Workload Characterization (IISWC), pages 2--12, Oct. 2005.
• 5: L. Eeckhout, H. Vandierendonck, and K. De Bosschere. Quantifying the impact of input data sets on program behavior and its applications. Journal of Instruction-Level Parallelism, 5, Feb. 2003. http://www.jilp.org/vol5.
• 6: Manoj Franklin , Gurindar S. Sohi, Register traffic analysis for streamlining inter-operation communication in fine-grain parallel processors, Proceedings of the 25th annual international symposium on Microarchitecture, p.236-245, December 01-04, 1992, Portland, Oregon, United States
• 7: R. A. Johnson , D. W. Wichern, Applied multivariate statistical analysis, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 8: Tejas S. Karkhanis , James E. Smith, A First-Order Superscalar Processor Model, Proceedings of the 31st annual international symposium on Computer architecture, p.338, June 19-23, 2004, München, Germany
• 9: J. Lau, J. Sampson, E. Perelman, G. Hamerly, and B. Calder. The strong correlation between code signatures and performance. In Proceedings of the International Symposium on Performance Analysis of Systems and Software (ISPASS), Mar. 2005.
• 10: J. Lau , S. Schoemackers , B. Calder, Structures for phase classification, Proceedings of the 2004 IEEE International Symposium on Performance Analysis of Systems and Software, p.57-67, March 10-12, 2004
• 11: A. Phansalkar and L. K. John. Performance prediction using program similarity. In Proceedings of the 2006 SPEC Benchmark Workshop, Jan. 2006.
• 12: A. Phansalkar, A. Joshi, L. Eeckhout, and L. K. John. Measuring program similarity: Experiments with SPEC CPU benchmark suites. In Proceedings of the 2005 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS'05), pages 10--20, Mar. 2005.
• 13: Rafael H. Saavedra , Alan J. Smith, Analysis of benchmark characteristics and benchmark performance prediction, ACM Transactions on Computer Systems (TOCS), v.14 n.4, p.344-384, Nov. 1996 [doi>10.1145/235543.235545]
• 14: Timothy Sherwood , Erez Perelman , Greg Hamerly , Brad Calder, Automatically characterizing large scale program behavior, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 15: A. Srivastava and A. Eustace. ATOM: A system for building customized program analysis tools. Technical Report 94/2, Western Research Lab, Compaq, Mar. 1994.
• 16: H. Vandierendonck and K. De Bosschere. Many benchmarks stress the same bottlenecks. In Proceedings of the Seventh Workshop on Computer Architecture Evaluation using Commercial Workloads (CAECW), pages 57--64, Feb. 2004.
• 17: Joshua J. Yi , David J. Lilja , Douglas M. Hawkins, A Statistically Rigorous Approach for Improving Simulation Methodology, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.281, February 08-12, 2003
• 18: Yutao Zhong , Steven G. Dropsho , Chen Ding, Miss Rate Prediction across All Program Inputs, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.79, September 27-October 01, 2003

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

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

General Terms:
Experimentation, Measurement, Performance

Keywords:
inherent program behavior, performance modeling, workload characterization