More Web Proxy on the site http://driver.im/

research-article

An input-centric paradigm for program dynamic optimizations

Authors:

Xipeng ShenAuthors Info & Claims

OOPSLA '10: Proceedings of the ACM international conference on Object oriented programming systems languages and applications

Pages 125 - 139

https://doi.org/10.1145/1869459.1869471

Published: 17 October 2010 Publication History

Abstract

Accurately 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 program inputs, a deciding factor for program behaviors.

Triggered by the strong and predictive correlations between program inputs and behaviors that recent studies have uncovered, this work proposes to include program inputs into the focus of program behavior analysis, cultivating a new paradigm named input-centric program behavior analysis. This new approach consists of three components, forming a three-layer pyramid. At the base is program input characterization, a component for resolving the complexity in program raw inputs and the extraction of important features. In the middle is input-behavior modeling, a component for recognizing and modeling the correlations between characterized input features and program behaviors. These two components constitute input-centric program behavior analysis, which (ideally) is able to predict the large-scope behaviors of a program's execution as soon as the execution starts. The top layer of the pyramid is input-centric adaptation, which capitalizes on the novel opportunities that the first two components create to facilitate proactive adaptation for program optimizations.

By centering on program inputs, the new approach resolves a proactivity-adaptivity dilemma inherent in previous techniques. Its benefits are demonstrated through proactive dynamic optimizations and version selection, yielding significant performance improvement on a set of Java and C programs.

References

[1]

}}A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools. Addison Wesley, 2nd edition, August 2006.

Digital Library

[2]

}}R. Allen and K. Kennedy. Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann Publishers, 2001.

Digital Library

[3]

}}M. Arnold, S. Fink, D. Grove, M. Hind, and P. Sweeney. Adaptive optimization in the Jalapeno JVM. In Proceedings of ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications, pages 47--65, Minneapolis, MN, October 2000.

Digital Library

[4]

}}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.

Digital Library

[5]

}}M. Arnold, A. Welc, and V. Rajan. Improving virtual machine performance using a cross-run profile repository. In the Conference on Object-Oriented Systems, Languages, and Applications, pages 297--311, 2005.

Digital Library

[6]

}}P. Berube and J. N. Amaral. Benchmark design for robust profile-directed optimization. In Standard Performance Evaluation Corporation (SPEC) Workshop, 2007.

[7]

}}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.

Digital Library

[8]

}}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.

Digital Library

[9]

}}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.

Digital Library

[10]

}}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.

[11]

}}J. Dean and C. Chambers. Towards better inlining decisions using inlining trials. In Proceedings of ACM Conference on Lisp and Functional Programming, pages 273--282, 1994.

Digital Library

[12]

}}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.

Digital Library

[13]

}}M. Ernst, J. Perkins, P. Guo, S. McCamant, M. T. C. Pacheco, and C. Xiao. The daikon system for dynamic detection of likely invariants. Science of Computer Programming, 69:35-- 45, 2007.

Digital Library

[14]

}}M. Frigo and S. G. Johnson. The design and implementation of FFTW3. Proceedings of the IEEE, 93(2):216--231, 2005.

[15]

}}B. Grant, M. Philipose, M. Mock, C. Chambers, and S. J. Eggers. An evaluation of staged run-time optimizations in DyC. In Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 293--304, Atlanta, Georgia, May 1999.

Digital Library

[16]

}}N. Grcevski, A. Kilstra, K. Stoodley, M. Stoodley, and V. Sundaresan. Java just-in-time compiler and virtual machine improvements for server and middleware applications. In Proceedings of the 3rd Virtual Machine Research and Technology Symposium (VM), May 2004.

Digital Library

[17]

}}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.

Digital Library

[18]

}}T. Hastie, R. Tibshirani, and J. Friedman. The elements of statistical learning. Springer, 2001.

[19]

}}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.

Digital Library

[20]

}}Y. Jiang, X. Shen, J. Chen, and R. Tripathi. Analysis and approximation of optimal co-scheduling on chip multiprocessors. In Proceedings of the International Conference on Parallel Architecture and Compilation Techniques (PACT), pages 220--229, October 2008.

Digital Library

[21]

}}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.

Digital Library

[22]

}}T. P. Kistler and M. Franz. Continuous program optimization: a case study. ACM Transactions on Programming Languages and Systems, 25(4):500--548, 2003.

Digital Library

[23]

}}C. Lattner. Macroscopic Data Structure Analysis and Optimization. PhD thesis, Computer Science Dept., Univ. of Illinois at Urbana-Champaign, May 2005.

Digital Library

[24]

}}J. Lau, M. Arnold, M. Hind, and B. Calder. Online performance auditing: Using hot optimizations without getting burned. In Proceedings of PLDI, pages 239--251, 2006.

Digital Library

[25]

}}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.

Digital Library

[26]

}}M. Lipasti and J. Shen. Exceeding the dataflow limit via value prediction. In Proceedings of the International Symposium on Microarchitecture (MICRO-29), pages 226--237, 1996.

Digital Library

[27]

}}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.

Digital Library

[28]

}}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.

Digital Library

[29]

}}R. Marlet, C. Consel, and P. Boinot. Efficient incremental run-time specialization for free. In Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 281--292, Atlanta, GA, May 1999.

Digital Library

[30]

}}M. A. Namjoshi and P. A. Kulkarni. Novel online profiling for virtual machines. In Proceedings of the International Conference on Virtual Execution Environments (VEE), pages 133--144, 2010.

Digital Library

[31]

}}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.

Digital Library

[32]

}}M. Polettto, W. Hsieh, D. R. Engler, and M. F. Kaashoek. 'C and tcc: A language and compiler for dynamic code generation. ACM Transactions on Programming Languages and Systems, 21(2):324--369, March 1999.

Digital Library

[33]

}}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.

[34]

}}X. Shen and F. Mao. Modeling relations between inputs and dynamic behavior for general programs. In Proceedings of the Workshop on Languages and Compilers for Parallel Computing, 2007.

[35]

}}X. Shen, Y. Zhong, and C. Ding. Locality phase prediction. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems, pages 165--176, 2004.

Digital Library

[36]

}}T. Sherwood, S. Sair, and B. Calder. Phase tracking and prediction. In Proceedings of International Symposium on Computer Architecture, pages 336--349, San Diego, CA, June 2003.

Digital Library

[37]

}}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.

Digital Library

[38]

}}A. Snavely and D. Tullsen. Symbiotic jobscheduling for a simultaneous multithreading processor. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems, pages 66--76, 2000.

Digital Library

[39]

}}S. Soman, C. Krintz, and D. F. Bacon. Dynamic selection of application-specific garbage collectors. In Proceedings of the International Symposium on Memory Management, pages 49--60, 2004.

Digital Library

[40]

}}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.

Digital Library

[41]

}}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.

Digital Library

[42]

}}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.

Digital Library

[43]

}}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.

Digital Library

[44]

}}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.

[45]

}}T. Yeh and Y. N. Patt. A comparison of dynamic branch predictors that use two levels of branch history. In Proceedings of the 20th Annual International Symposium on Computer Architecture, pages 257--266, May 1993.

Digital Library

[46]

}}C. Zhang and M. Hirzel. Online phase-adaptive data layout selection. In Proceedings of the European Conference on Object-Oriented Programming, pages 309--334, 2008.

Digital Library

[47]

}}Y. Zhong, X. Shen, and C. Ding. Program locality analysis using reuse distance. ACM Transactions on Programming Languages and Systems, 31(6), 2009.

Digital Library

Cited By

Li XAgrawal G(2021)Shrinking Sample Search Algorithm for Automatic Tuning of GPU Kernels2021 IEEE 28th International Conference on High Performance Computing, Data, and Analytics (HiPC)10.1109/HiPC53243.2021.00040(262-271)Online publication date: Dec-2021
https://doi.org/10.1109/HiPC53243.2021.00040
Rankin YThomas JJoseph N(2020)Intersectionality in HCIInteractions10.1145/341649827:5(68-71)Online publication date: 1-Sep-2020
https://dl.acm.org/doi/10.1145/3416498
Bellini RStrohmayer A(2020)Intersections of transformationInteractions10.1145/341446627:5(76-78)Online publication date: 1-Sep-2020
https://dl.acm.org/doi/10.1145/3414466
Show More Cited By

Index Terms

An input-centric paradigm for program dynamic optimizations
1. Software and its engineering
  1. Software notations and tools
    1. Compilers

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 applications

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 ...
An input-centric paradigm for program dynamic optimizations
OOPSLA '10

Accurately 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 ...
An input centric paradigm for program dynamic optimizations and lifetime evolvement

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

OOPSLA '10: Proceedings of the ACM international conference on Object oriented programming systems languages and applications

October 2010

984 pages

ISBN:9781450302036

DOI:10.1145/1869459

General Chairs:
William R. Cook
University of Texas at Austin
,
Siobhán Clarke
Trinity College Dublin
,
Program Chairs:
Martin Rinard
MIT
,
Kevin J. Sullivan
University of Virginia
,
Daniel H. Steinberg
Dim Sum Thinking Inc.

ACM SIGPLAN Notices Volume 45, Issue 10
OOPSLA '10
October 2010
957 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1932682
Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 October 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPLASH '10

Sponsor:

SIGPLAN

SPLASH '10: Systems Programming Languages and Applications: Software for Humanity

October 17 - 21, 2010

Nevada, Reno/Tahoe, USA

Acceptance Rates

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

62
Total Citations
View Citations
401
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li XAgrawal G(2021)Shrinking Sample Search Algorithm for Automatic Tuning of GPU Kernels2021 IEEE 28th International Conference on High Performance Computing, Data, and Analytics (HiPC)10.1109/HiPC53243.2021.00040(262-271)Online publication date: Dec-2021
https://doi.org/10.1109/HiPC53243.2021.00040
Rankin YThomas JJoseph N(2020)Intersectionality in HCIInteractions10.1145/341649827:5(68-71)Online publication date: 1-Sep-2020
https://dl.acm.org/doi/10.1145/3416498
Bellini RStrohmayer A(2020)Intersections of transformationInteractions10.1145/341446627:5(76-78)Online publication date: 1-Sep-2020
https://dl.acm.org/doi/10.1145/3414466
Park JKwon YPark YJeon D(2019)Microarchitecture-Aware Code Generation for Deep Learning on Single-ISA Heterogeneous Multi-Core Mobile ProcessorsIEEE Access10.1109/ACCESS.2019.29105597(52371-52378)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2910559
Zhang YYang MBaghdadi RKamil SShun JAmarasinghe S(2018)GraphIt: a high-performance graph DSLProceedings of the ACM on Programming Languages10.1145/32764912:OOPSLA(1-30)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276491
Zhao YLi JLiao CShen X(2018)Bridging the gap between deep learning and sparse matrix format selectionACM SIGPLAN Notices10.1145/3200691.317849553:1(94-108)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3200691.3178495
Zhao YLi JLiao CShen XKrall AGross T(2018)Bridging the gap between deep learning and sparse matrix format selectionProceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3178487.3178495(94-108)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3178487.3178495
Zhao YZhou WShen XYiu G(2018)Overhead-Conscious Format Selection for SpMV-Based Applications2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2018.00104(950-959)Online publication date: May-2018
https://doi.org/10.1109/IPDPS.2018.00104
Jantz MRobinson FKulkarni P(2016)Impact of Intrinsic Profiling Limitations on Effectiveness of Adaptive OptimizationsACM Transactions on Architecture and Code Optimization10.1145/300866113:4(1-26)Online publication date: 12-Dec-2016
https://dl.acm.org/doi/10.1145/3008661
Merrifield TTaheri H(2016)Performance Implications of Extended Page Tables on Virtualized x86 ProcessorsACM SIGPLAN Notices10.1145/3007611.289225851:7(25-35)Online publication date: 25-Mar-2016
https://dl.acm.org/doi/10.1145/3007611.2892258
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents