ABSTRACT
This paper presents a finding and a technique on program behavior prediction. The finding is that surprisingly strong statistical correlations exist among the behaviors of different program components (e.g., loops) and among different types of program level behaviors (e.g., loop trip-counts versus data values). Furthermore, the correlations can be beneficially exploited: They help resolve the proactivity-adaptivity dilemma faced by existing program behavior predictions, making it possible to gain the strengths of both approaches--the large scope and earliness of offline-profiling--based predictions, and the cross-input adaptivity of runtime sampling-based predictions.
The main technique contributed by this paper centers on a new concept, seminal behaviors. Enlightened by the existence of strong correlations among program behaviors, we propose a regression based framework to automatically identify a small set of behaviors that can lead to accurate prediction of other behaviors in a program. We call these seminal behaviors. By applying statistical learning techniques, the framework constructs predictive models that map from seminal behaviors to other behaviors, enabling proactive and cross-input adaptive prediction of program behaviors. The prediction helps a commercial compiler, the IBM XL C compiler, generate code that runs up to 45% faster (5%-13% on average), demonstrating the large potential of correlation-based techniques for program optimizations.
- A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools. Addison Wesley, 2nd edition, August 2006. Google ScholarDigital Library
- R. Allen and K. Kennedy. Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann Publishers, 2001. Google ScholarDigital Library
- M. Annavaram, R. Rakvic, M. Polito, J. Bouguet, R. Hankins, and B. Davies. The fuzzy correlation between code and performance predictability. In Proceedings of the 37th Annual IEEE/ACM International Symposium on Microarchitecture, pages 407--420, 2004. Google ScholarDigital Library
- M. Arnold, S. Fink, D. Grove, M. Hind, and P.F. Sweeney. Adaptive optimization in the Jalapeno JVM. In Proceedings of ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications, Minneapolis, MN, October 2000. Google ScholarDigital Library
- M. Arnold, A. Welc, and V.T. Rajan. Improving virtual machine performance using a cross-run profile repository. In the Conference on Object-Oriented Systems, Languages, and Applications, 2005. Google ScholarDigital Library
- P. Berube and J. N. Amaral. Additional inputs for SPEC CPU2000. http://www.cs.ualberta.ca/~Eberube/compiler/fdo/inputs.shtml.Google Scholar
- W. Chen, S. Bhansali, T. M. Chilimbi, X. Gao, and W. Chuang. Profile-guided proactive garbage collection for locality optimization. In Proceedings of PLDI, 2006. Google ScholarDigital Library
- B. Childers, J. Davidson, and M. L. Soffa. Continuous compilation: A new approach to aggressive and adaptive code transformation. In Proceedings of NSF Next Generation Software Workshop, 2003. Google ScholarDigital Library
- P. Chuang, H. Chen, G. Hoflehner, D. Lavery, and W. Hsu. Dynamic profile driven code version selection. In Proceedings of the 11th Annual Workshop on the Interaction between Compilers and Computer Architecture, 2007.Google Scholar
- T. Hastie, R. Tibshirani, and J. Friedman. The elements of statistical learning. Springer, 2001.Google ScholarCross Ref
- J. Lau, M. Arnold, M. Hind, and B. Calder. Online performance auditing: Using hot optimizations without getting burned. In Proceedings of PLDI, 2006. Google ScholarDigital Library
- H. Leather, E. Bonilla, and M. O'Boyle. Automatic feature generation for machine learning based optimizing compilation. In Proceedings of the International Symposium on Code Generation and Optimization (CGO), 2009. Google ScholarDigital Library
- X. Li, M. J. Garzaran, and D. Padua. A dynamically tuned sorting library. In Proceedings of the International Symposium on Code Generation and Optimization, 2004. Google ScholarDigital Library
- F. Mao and X. Shen. Cross--input learning and discriminative prediction in evolvable virtual machine. In Proceedings of the International Symposium on Code Generation and Optimization(CGO), 2009. Google ScholarDigital Library
- T. Sherwood, E. Perelman, G. Hamerly, and B. Calder. Automatically characterizing large scale program behavior. In Proceedings of International Conference on Architectural Support for Programming Languages and Operating Systems, pages 45--57, 2002. Google ScholarDigital Library
- M. Voss and R. Eigenmann. High-level adaptive program optimization with ADAPT. In Proceedings of ACM Symposium on Principles and Practice of Parallel Programming, pages 93--102, Snowbird, Utah, June 2001. Google ScholarDigital Library
- C. Wang and Z. Li. Parametric analysis for adaptive computation offloading. In Proceedings of ACM SIGPLAN Conference on Programming Languages Design and Implementation, pages 119--130, 2004. Google ScholarDigital Library
- R. W. Wisniewski, P. F. Sweeney, K. Sudeep, M. Hauswirth, E. Duesterwald, C. Cascaval, and R. Azimi. Performance and environment monitoring for whole-system characterization and optimization. In PAC2 Conference on Power/Performance Interaction with Architecture, Circuits, and Compilers, 2004.Google Scholar
Index Terms
- Exploiting statistical correlations for proactive prediction of program behaviors
Recommendations
Exploiting inter-sequence correlations for program behavior prediction
OOPSLA '12Prediction of program dynamic behaviors is fundamental to program optimizations, resource management, and architecture reconfigurations. Most existing predictors are based on locality of program behaviors, subject to some inherent limitations. In this ...
Exploiting inter-sequence correlations for program behavior prediction
OOPSLA '12: Proceedings of the ACM international conference on Object oriented programming systems languages and applicationsPrediction of program dynamic behaviors is fundamental to program optimizations, resource management, and architecture reconfigurations. Most existing predictors are based on locality of program behaviors, subject to some inherent limitations. In this ...
Introducing entropies for representing program behavior and branch predictor performance
ExpCS '07: Proceedings of the 2007 workshop on Experimental computer sciencePredictors are inherent components of state-of-the-art microprocessors. Branch predictors are discussed actively from diverse perspectives. Performance of a branch predictor largely depends on the dynamic behavior of the executing program. Nevertheless, ...
Comments