Article

Improving Region Selection in Dynamic Optimization Systems

Authors:

Michael D. SmithAuthors Info & Claims

MICRO 38: Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture

Pages 141 - 154

https://doi.org/10.1109/MICRO.2005.22

Published: 12 November 2005 Publication History

Publisher Site Get Access

Abstract

The performance of a dynamic optimization system depends heavily on the code it selects to optimize. Many current systems follow the design of HP Dynamo and select a single interprocedural path, or trace, as the unit of code optimization and code caching. Though this approach to region selection has worked well in practice, we show that it is possible to adapt this basic approach to produce regions with greater locality, less needless code duplication, and fewer profiling counters. In particular, we propose two new region-selection algorithms and evaluate them against Dynamo's selection mechanism, Next-Executing Tail (NET). Our first algorithm, Last-Executed Iteration (LEI), identifies cyclic paths of execution better than NET, improving locality of execution while reducing the size of the code cache. Our second algorithm allows overlapping traces of similar execution frequency to be combined into a single large region. This second technique can be applied to both NET and LEI, and we find that it significantly improves metrics of locality and memory overhead for each.

References

[1]

{1} B. Alpern, et al. "The Jikes Research Virtual Machine project: Building an open-source research community," IBM Systems Journal, vol. 44, no. 2, 2005.

Digital Library

[2]

{2} M. Arnold, et al. "Adaptive optimization in the Jalapeñ'o JVM," Proc. ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA 2000), October 2000.

Digital Library

[3]

{3} V. Bala, E. Duesterwald, and S. Banerjia. "Dynamo: A Transparent Runtime Optimization System," Proc. ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation, pp. 1-12, June 2000.

Digital Library

[4]

{4} V. Bala, E. Duesterwald, and S. Banerjia. "Transparent Dynamic Optimization: The Design and Implementation of Dynamo," Hewlett Packard Laboratories Technical Report HPL-1999-78, June 1999.

[5]

{5} T. Ball and J. Larus. "Programs Follow Paths," Microsoft Research Technical Report MSR-TR-99-01, January 1999.

[6]

{6} D. Bruening, T. Garnett, and S. Amarasinghe. "An Infrastructure for Adaptive Dynamic Optimization," Proc. First Annual International Symposium on Code Generation and Optimization, pp. 265-275, March 2003.

Digital Library

[7]

{7} W. Chen et al. "Mojo: A Dynamic Optimization System," Proc. 4th ACM Workshop on Feedback-Directed and Dynamic Optimization, pp. 81-90, December 2000.

[8]

{8} D. Deaver, R. Gorton, and N. Rubin. "Wiggins/Redstone: An On-line Program Specializer," Proc. IEEE Hot Chips XI, 1999.

[9]

{9} J. Dehnert et al. "The Transmeta Code Morphing(tm) Software: Using Speculation, Recovery, and Adaptive Retranslation to Address Real-Life Challenges," Proc. 2003 International Symposium on Code Generation and Optimization, pp. 15-24, March 2003.

Digital Library

[10]

{10} E. Duesterwald and V. Bala. "Software Profiling for Hot Path Prediction: Less is More," Proc. 12th International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 202-211, November 2000.

Digital Library

[11]

{11} P. Chang, S. Mahlke, and W. Hwu. "Using Profile Information to Assist Classic Code Optimizations," Software Practice and Experience, vol. 21, pp. 1301-1321, December 1991.

Digital Library

[12]

{12} M. Gschwind et al. "Dynamic and Transparent Binary Translation," IEEE Computer Magazine, vol. 33, pp. 54-59, March 2000.

Digital Library

[13]

{13} R. Hank, W. Hwu, and B. Rau. "Region-Based Compilation: An Introduction and Motivation," Proc. 28th Annual International Symposium on Microarchitecture, pp. 158-168, November 1995.

Digital Library

[14]

{14} K. Hazelwood. "Code Cache Management in Dynamic Optimization Systems," PhD thesis, Harvard University, 2004.

[15]

{15} J. Lu et al. "Design and Implementation of a Lightweight Dynamic Optimization System," Journal of Instruction-Level Parallelism, vol. 6, pp. 1-24, April 2004.

[16]

{16} C. Luk et al. "Pin: Building Customized Program Analysis Tools with Dynamic Instrumentation," Proc. ACM Programming Language Design and Implementation, pp. 190-200, June 2005.

Digital Library

[17]

{17} S. Sathaye et al. "BOA: Targeting Multi-gigahertz with Binary Translation," Proc. of the 1999 Workshop on Binary Translation, pp. 2-11, December 1999.

[18]

{18} T. Sherwood et al. "Automatically Characterizing Large Scale Program Behavior," Proc. 10th International Conference on Architectural Support for Programming Languages and Operating Systems, October 2002.

Digital Library

[19]

{19} SPEC CPU2000 benchmark suite. Standard Performance Evaluation Corporation. http://www.spec.org/osg/cpu2000/.

[20]

{20} C. Young and M. Smith. "Better Global Scheduling Using Path Profiles," Proc. 31st Annual ACM/IEEE International Symposium on Microarchitecture, pp. 115-123, November 1998.

Digital Library

Cited By

Wang WWu JGong XLi TYew P(2018)Improving Dynamically-Generated Code Performance on Dynamic Binary TranslatorsACM SIGPLAN Notices10.1145/3296975.318641353:3(17-30)Online publication date: 25-Mar-2018
https://dl.acm.org/doi/10.1145/3296975.3186413
Hong DWu JLiu YFu SHsu W(2018)Processor-Tracing Guided Region Formation in Dynamic Binary TranslationACM Transactions on Architecture and Code Optimization10.1145/328166415:4(1-25)Online publication date: 16-Nov-2018
https://dl.acm.org/doi/10.1145/3281664
Wang WWu JGong XLi TYew P(2018)Improving Dynamically-Generated Code Performance on Dynamic Binary TranslatorsProceedings of the 14th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments10.1145/3186411.3186413(17-30)Online publication date: 25-Mar-2018
https://dl.acm.org/doi/10.1145/3186411.3186413
Show More Cited By

Index Terms

Improving Region Selection in Dynamic Optimization Systems
1. Hardware
  1. Integrated circuits
2. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Code cache management in dynamic optimization systems
Exploring Code Cache Eviction Granularities in Dynamic Optimization Systems
CGO '04: Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization

Dynamic optimization systems store optimized or translatedcode in a software-managed code cache in order tomaximize reuse of transformed code. Code caches storesuperblocks that are not fixed in size, may contain linksto other superblocks, and carry a ...
Improving performance and energy consumption in region-based caching architectures

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MICRO 38: Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture

November 2005

350 pages

ISBN:0769524400

Sponsors

SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing

Publisher

IEEE Computer Society

United States

Publication History

Published: 12 November 2005

Check for updates

Qualifiers

Article

Conference

Micro-38

Sponsor:

SIGMICRO

Micro-38: The 38th Annual IEEE/ACM International Symposium on Microarchitecture

November 12 - 16, 2005

Barcelona, Spain

Acceptance Rates

MICRO 38 Paper Acceptance Rate 29 of 147 submissions, 20%;

Overall Acceptance Rate 484 of 2,242 submissions, 22%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
24
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang WWu JGong XLi TYew P(2018)Improving Dynamically-Generated Code Performance on Dynamic Binary TranslatorsACM SIGPLAN Notices10.1145/3296975.318641353:3(17-30)Online publication date: 25-Mar-2018
https://dl.acm.org/doi/10.1145/3296975.3186413
Hong DWu JLiu YFu SHsu W(2018)Processor-Tracing Guided Region Formation in Dynamic Binary TranslationACM Transactions on Architecture and Code Optimization10.1145/328166415:4(1-25)Online publication date: 16-Nov-2018
https://dl.acm.org/doi/10.1145/3281664
Wang WWu JGong XLi TYew P(2018)Improving Dynamically-Generated Code Performance on Dynamic Binary TranslatorsProceedings of the 14th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments10.1145/3186411.3186413(17-30)Online publication date: 25-Mar-2018
https://dl.acm.org/doi/10.1145/3186411.3186413
Laurenzano MZhang YChen JTang LMars J(2016)PowerChopACM SIGARCH Computer Architecture News10.1145/3007787.300115244:3(140-152)Online publication date: 18-Jun-2016
https://dl.acm.org/doi/10.1145/3007787.3001152
Laurenzano MZhang YChen JTang LMars JMin SLoh G(2016)PowerChopProceedings of the 43rd International Symposium on Computer Architecture10.1109/ISCA.2016.22(140-152)Online publication date: 18-Jun-2016
https://dl.acm.org/doi/10.1109/ISCA.2016.22
Spink TWagstaff HFranke BTopham N(2014)Efficient code generation in a region-based dynamic binary translatorACM SIGPLAN Notices10.1145/2666357.259781049:5(3-12)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2666357.2597810
Spink TWagstaff HFranke BTopham NZhang YKulkarni P(2014)Efficient code generation in a region-based dynamic binary translatorProceedings of the 2014 SIGPLAN/SIGBED conference on Languages, compilers and tools for embedded systems10.1145/2597809.2597810(3-12)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2597809.2597810
Häubl CWimmer CMössenböck H(2014)Trace transitioning and exception handling in a trace-based JIT compiler for javaACM Transactions on Architecture and Code Optimization10.1145/257967311:1(1-26)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1145/2579673
Hsu CLiu PWu JYew PHong DHsu WWang C(2013)Improving dynamic binary optimization through early-exit guided code region formationACM SIGPLAN Notices10.1145/2517326.245151948:7(23-32)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1145/2517326.2451519
Serrano MFranke HHeinecke APalem KUpfal E(2013)Trace construction using enhanced performance monitoringProceedings of the ACM International Conference on Computing Frontiers10.1145/2482767.2482811(1-10)Online publication date: 14-May-2013
https://dl.acm.org/doi/10.1145/2482767.2482811
Show More Cited By

View Options

Get Access

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