Kai Tian
Xipeng Shen
Abstract
Dynamic program optimizations are critical for the efficiency of applications in managed programming languages and scripting languages. Recent studies have shown that exploitation of program inputs may enhance the effectiveness of dynamic optimizations significantly. However, current solutions for enabling the exploitation require either programmers' annotations or intensive offline profiling, impairing the practical adoption of the techniques.
This current work examines the basic feasibility of transparent integration of input-consciousness into dynamic program optimizations, particularly in managed execution environments. It uses transparent learning across production runs as the basic vehicle, and investigates the implications of cross-run learning on each main component of input-conscious dynamic optimizations. It proposes several techniques to address some key challenges for the transparent integration, including randomized inspection-instrumentation for cross-user data collection, a sparsity-tolerant algorithm for input characterization, and selective prediction for efficiency protection. These techniques make it possible to automatically recognize the relations between the inputs to a program and the appropriate ways to optimize it. The whole process happens transparently across production runs; no need for offline profiling or programmer intervention. Experiments on a number of Java programs demonstrate the effectiveness of the techniques in enabling input-consciousness for dynamic optimizations, revealing the feasibility and potential benefits of the new optimization paradigm in some basic settings.
- Java Grande benchmark. http://www2.epcc.ed.ac.uk/javagrande/.Google Scholar
- Spec jvm98. http://www.spec.org/jvm98/.Google Scholar
- M. Arnold, M. Hind, and B. G. Ryder. Online feedback-directed optimization of Java. In Proceedings of ACM Conference on Object-Oriented Programming Systems, Languages and Applications, pages 111--129, 2002. Google ScholarDigital Library
- M. Arnold, A. Welc, and V. Rajan. Improving virtual machine performance using a cross-run profile repository. In the Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 297--311, 2005. Google ScholarDigital Library
- J. Bilmes, K. Asanovic, C.-W. Chin, and J. Demmel. Optimizing matrix multiply using PHiPAC: A portable, high-performance, ANSI C coding methodology. In Proceedings of the ACM International Conference on Supercomputing, pages 340--347, 1997. Google ScholarDigital Library
- S. M. Blackburn et al. The DaCapo benchmarks: Java benchmarking development and analysis. In Proceedings of ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications, October 2006. Google ScholarDigital Library
- M. D. Bond, K. E. Coons, and K. S. McKinley. Pacer: Proportional detection of data races. In Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation, 2010. Google ScholarDigital Library
- J. Cavazos and M. O'Boyle. Method-specific dynamic compilation using logistic regression. In Proceedings of ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications, 2006. Google ScholarDigital Library
- W. Chen, S. Bhansali, T. M. Chilimbi, X. Gao, and W. Chuang. Profile-guided proactive garbage collection for locality optimization. In Proceedings of PLDI, pages 332--340, 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. Diniz and M. Rinard. Dynamic feedback: an effective technique for adaptive computing. In Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 71--84, Las Vegas, May 1997. Google ScholarDigital Library
- M. Frigo and S. G. Johnson. The design and implementation of FFTW3. Proceedings of the IEEE, 93(2):216--231, 2005.Google ScholarCross Ref
- A. Gal, B. Eich, M. Shaver, D. Anderson, et al. Trace-based just-in-time type specialization for dynamic languages. In Proceedings of the ACM SIGPLAN Conference On Programming Language Design and Implementation, 2009. Google ScholarDigital Library
- A. Georges, D. Buytaert, and L. Eeckhout. Statistically rigorous Java performance evaluation. In Proceedings of ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications, 2007. Google ScholarDigital Library
- D. Gu and C. Verbrugge. Phase-based adaptive recompilation in a JVM. In Proceedings of the International Symposium on Code Generation and Optimization, pages 24--34, 2008. Google ScholarDigital Library
- T. Hastie, R. Tibshirani, and J. Friedman. The elements of statistical learning. Springer, 2001.Google ScholarCross Ref
- X. Huang, S. M. Blackburn, K. S. McKinley, J. E. Moss, Z. Wang, and P. Cheng. The garbage collection advantage: improving program locality. In the Conference on Object-Oriented Programming, Systems, Languages, and Applications, 2004. Google ScholarDigital Library
- E.-J. Im, K. Yelick, and R. Vuduc. Sparsity: Optimization framework for sparse matrix kernels. Int. J. High Perform. Comput. Appl., 18(1):135--158, 2004. Google ScholarDigital Library
- Y. Jiang, E. Zhang, K. Tian, F. Mao, M. Geathers, X. Shen, and Y. Gao. Exploiting statistical correlations for proactive prediction of program behaviors. In Proceedings of the International Symposium on Code Generation and Optimization (CGO), pages 248--256, 2010. Google ScholarDigital Library
- G. Jin, A. V. Thakur, B. Liblit, and S. Lu. Instrumentation and sampling strategies for cooperative concurrency bug isolation. In Proceedings of ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications, 2010. Google ScholarDigital Library
- T. P. Kistler and M. Franz. Continuous program optimization: a case study. ACM Transactions on Programming Languages and Systems, 25(4):500--548, 2003. 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, pages 111--124, 2004. Google ScholarDigital Library
- B. Liblit, A. Aiken, A. X. Zheng, and M. I. Jordan. Bug isolation via remote program sampling. In Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation, 2003. 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), pages 92--101, 2009. Google ScholarDigital Library
- F. Mao, E. Zhang, and X. Shen. Influence of program inputs on the selection of garbage collectors. In Proceedings of the International Conference on Virtual Execution Environments (VEE), pages 91--100, 2009. Google ScholarDigital Library
- M. Paleczny, C. Vic, and C. Click. The Java Hotspot(TM) server compiler. In USENIX Java Virtual Machine Research and Technology Symposium, pages 1--12, 2001. Google ScholarDigital Library
- M. Puschel, J. Moura, J. Johnson, D. Padua, M. Veloso, B. Singer, J. Xiong, F. Franchetti, A. Gacic, Y. Voronenko, K. Chen, R. Johnson, and N. Rizzolo. SPIRAL: code generation for DSP transforms. Proceedings of the IEEE, 93(2):232--275, 2005.Google ScholarCross Ref
- J. Singer, G. Brown, I. Watson, and J. Cavazos. Intelligent selection of application-specific garbage collectors. In Proceedings of the International Symposium on Memory Management, pages 91--102, 2007. Google ScholarDigital Library
- A. Srivastava and J. Thiagarajan. Effectively prioritizing tests in development environment. In Proceedings of International Symposium on Software Testing and Analysis, 2002. Google ScholarDigital Library
- N. Thomas, G. Tanase, O. Tkachyshyn, J. Perdue, N. M. Amato, and L. Rauchwerger. A framework for adaptive algorithm selection in STAPL. In Proceedings of the Tenth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 277--288, 2005. Google ScholarDigital Library
- K. Tian, Y. Jiang, E. Zhang, and X. Shen. An input-centric paradigm for program dynamic optimizations. In the Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), 2010. 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
- B. Wagner. Collaborative compilation. PhD thesis, Computer Science Dept., MIT, 2006.Google Scholar
- 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. C. Whaley, A. Petitet, and J. Dongarra. Automated empirical optimizations of software and the ATLAS project. Parallel Computing, 27(1--2):3--35, 2001.Google Scholar
- 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
- X. Zhuang, S. Kim, M. Serrano, and J. Choi. Perfdiff: a framework for performance difference analysis in a virtual machine environment. In Proceedings of the International Symposium on Code Generation and Optimization, 2008. Google ScholarDigital Library
Index Terms
- A step towards transparent integration of input-consciousness into dynamic program optimizations
Recommendations
A step towards transparent integration of input-consciousness into dynamic program optimizations
OOPSLA '11: Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applicationsDynamic program optimizations are critical for the efficiency of applications in managed programming languages and scripting languages. Recent studies have shown that exploitation of program inputs may enhance the effectiveness of dynamic optimizations ...
An input-centric paradigm for program dynamic optimizations
OOPSLA '10Accurately predicting program behaviors (e.g., locality, dependency, method calling frequency) is fundamental for program optimizations and runtime adaptations. Despite decades of remarkable progress, prior studies have not systematically exploited ...
Do computer programs have to be as dumb as they are?: input-centric dynamic program optimizations
VMIL '13: Proceedings of the 7th ACM workshop on Virtual machines and intermediate languagesLooking around this world, we see that a fledgling can fly faster and faster, a pupil can calculate quicker and quicker, and a graduate student can write papers better and better. But since the birth of computers, it has been the case that after the ...
Comments