Article

Evaluating Indirect Branch Handling Mechanisms in Software Dynamic Translation Systems

Authors:

Jason D. Hiser,

Daniel Williams,

Jack W. Davidson,

Bruce R. ChildersAuthors Info & Claims

CGO '07: Proceedings of the International Symposium on Code Generation and Optimization

Pages 61 - 73

https://doi.org/10.1109/CGO.2007.10

Published: 11 March 2007 Publication History

Abstract

Software Dynamic Translation (SDT) systems are used for program instrumentation, dynamic optimization, security, intrusion detection, and many other uses. As noted by many researchers, a major source of SDT overhead is the execution of code which is needed to translate an indirect branch's target address into the address of the translated destination block. This paper discusses the sources of indirect branch (IB) overhead in SDT systems and evaluates several techniques for overhead reduction. Measurements using SPEC CPU2000 show that the appropriate choice and configuration of IB translation mechanisms can significantly reduce the IB handling overhead. In addition, cross-architecture evaluation of IB handling mechanisms reveals that the most efficient implementation and configuration can be highly dependent on the implementation of the underlying architecture.

References

[1]

{1} Vasanth Bala, Evelyn Duesterwald, and Sanjeev Banerjia. Dynamo: A transparent dynamic optimization system. In PLDI '00: Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation, pages 1-12, New York, NY, USA, June 2000. ACM Press.

Digital Library

[2]

{2} Derek Bruening. Efficient, Transparent, and Comprehensive Runtime Code Manipulation. PhD thesis, MIT, 2004.

Digital Library

[3]

{3} Derek Bruening and Saman Amarasinghe. Maintaining consistency and bounding capacity of software code caches. In CGO '05: Proceedings of the International Symposium on Code Generation and Optimization, pages 74-85, Washington, DC, USA, 2005. IEEE Computer Society.

Digital Library

[4]

{4} Derek Bruening, Timothy Garnett, and Saman Amarasinghe. An infrastructure for adaptive dynamic optimization. In CGO '03: Proceedings of the International Symposium on Code Generation and Optimization, pages 265-275, March 2003.

Digital Library

[5]

{5} Wen-Ke Chen, Sorin Lerner, Ronnie Chaiken, and David Gillies. Mojo: A dynamic optimization system. In Proceedings of the ACM Workshop on Feedback-Directed and Dynamic Optimization FDDO-3, December 2000.

[6]

{6} Bob Cmelik and David Keppel. Shade: A fast instruction-set simulator for execution profiling. In SIGMETRICS '94: Proceedings of the 1994 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, pages 128-137, New York, NY, USA, May 1994. ACM Press.

Digital Library

[7]

{7} Apple Computers. Apple website on rosetta, 2006.

[8]

{8} Advanced Micro Devices. AMD website on opterons, 2006.

[9]

{9} David R. Ditzel. Transmeta's Crusoe: Cool chips for mobile computing. In IEEE, editor, Hot Chips 12: Stanford University, Stanford, California, August 13-15, 2000, 1109 Spring Street, Suite 300, Silver Spring, MD 20910, USA, 2000. IEEE Computer Society Press.

[10]

{10} Evelyn Duesterwald and Vasanth Bala. Software profiling for hot path prediction: less is more. In ASPLOS-IX: Proceedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 202- 211, New York, NY, USA, 2000. ACM Press.

Digital Library

[11]

{11} Kemal Ebcioglu and Erik Altman. DAISY: Dynamic compilation for 100% architectural compatibility. In ISCA '97: Proceedings of the 24th Annual International Symposium on Computer Architecture, pages 26-37, New York, NY, USA, 1997. ACM Press.

Digital Library

[12]

{12} Kim Hazelwood and James E. Smith. Exploring code cache eviction granularities in dynamic optimization systems. In CGO '04: Proceedings of the International Symposium on Code Generation and Optimization, page 89, Washington, DC, USA, 2004. IEEE Computer Society.

Digital Library

[13]

{13} Kim Hazelwood and Michael D. Smith. Generational cache management of code traces in dynamic optimization systems. In MICRO 36: Proceedings of the 36th Annual IEEE/ACM International Symposium on Microarchitecture, page 169-179, Washington, DC, USA, 2003. IEEE Computer Society.

Digital Library

[14]

{14} David Hiniker, Kim Hazelwood, and Michael D. Smith. Improving region selection in dynamic optimization systems. In MICRO 38: Proceedings of the 38th Annual IEEE/ACM International Symposium on Microarchitecture, pages 141-154, Washington, DC, USA, 2005. IEEE Computer Society.

Digital Library

[15]

{15} Intel. IA-32 Intel Architecture Optimization Reference Manual, 2005.

[16]

{16} Ho-Seop Kim and James E. Smith. Hardware support for control transfers in code caches. In MICRO 36: Proceedings of the 36th Annual IEEE/ACM International Symposium on Microarchitecture, page 253, Washington, DC, USA, 2003. IEEE Computer Society.

Digital Library

[17]

{17} Vladimir Kiriansky, Derek Bruening, and Saman Amarasinghe. Secure execution via program shepherding. In 11th USENIX Security Symposium, August 2002.

Digital Library

[18]

{18} Naveen Kumar, Bruce R. Childers, Daniel Williams, Jack W. Davidson, and Mary Lou Soffa. Compile-time planning for overhead reduction in software dynamic translators. International Journal of Parallel Programming, 33(2):103-114, 2005.

Digital Library

[19]

{19} Transitive Corporation Ltd. Transitive website, 2006.

[20]

{20} Chi-Keung Luk, Robert Cohn, Robert Muth, Harish Patil, Artur Klauser, Geoff Lowney, Steven Wallace, Vijay Janapa Reddi, and Kim Hazelwood. Pin: building customized program analysis tools with dynamic instrumentation. In PLDI '05: Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 190- 200, New York, NY, USA, 2005. ACM Press.

Digital Library

[21]

{21} Kevin Scott and Jack Davidson. Strata: A software dynamic translation infrastructure. In IEEE Workshop on Binary Translation , September 2001.

[22]

{22} Kevin Scott and Jack W. Davidson. Safe virtual execution using software dynamic translation. In Proceedings of the 18th Annual Computer Security Applications Conference, pages 209- 218, Las Vegas, NV, December 2002.

Digital Library

[23]

{23} Kevin Scott, N. Kumar, Bruce Childers, Jack W. Davidson, and Mary Lou Soffa. Overhead reduction techniques for software dynamic translation. In Proceedings of the 18th International Parallel and Distributed Processing Symposium, page 200. IEEE Computer Society, 2004.

[24]

{24} Kevin Scott, Naven Kumar, Siva Velusamy, Bruce Childers, Jack W. Davidson, and Mary Lou Soffa. Retargetable and reconfigurable software dynamic translation. In CGO '03: Proceedings of the International Symposium on Code Generation and Optimization, pages 36-47, Washington, DC, USA, 2003. IEEE Computer Society.

Digital Library

[25]

{25} Robert Sedgewick. Algorithms. Addison-Wesley, 1983.

Digital Library

[26]

{26} Jim Smith and Ravi Nair. Virtual Machines: Versatile Platforms for Systems and Processes. Morgan Kaufmann, 2005.

Digital Library

[27]

{27} Swaroop Sridhar, Jonathan S. Shapiro, and Prashanth P. Bungale. Hdtrans: A low-overhead dynamic translator. In Proceedings of the 2005 Workshop on Binary Instrumentation and Applications. IEEE Computer Society, September 2005.

[28]

{28} Standard Performance Evaluation Corporation. SPEC CPU2000 Benchmarks. http://www.specbench.org/osg/ cpu2000.

[29]

{29} Sun Microsystems. UltraSPARC-IIi User's Manual, 1997. User's Manual.

[30]

{30} David Ung and Cristina Cifuentes. Machine-adaptable dynamic binary translation. In Proceedings of the ACM Workshop on Dynamic Optimization Dynamo '00, 2000.

Digital Library

[31]

{31} Shukang Zhou, Bruce R. Childers, and Mary Lou Soffa. Planning for code buffer management in distributed virtual execution environments. In VEE '05: Proceedings of the 1st ACM/USENIX International Conference on Virtual Execution Environments, pages 100-109, New York, NY, USA, 2005. ACM Press.

Digital Library

Cited By

Gopan DOhmann PMelski DKim TWang CKim TWu D(2017)VertxProceedings of the 2017 Workshop on Forming an Ecosystem Around Software Transformation10.1145/3141235.3141237(1-7)Online publication date: 3-Nov-2017
https://dl.acm.org/doi/10.1145/3141235.3141237
D'Antras AGorgovan CGarside JLuján M(2017)Low overhead dynamic binary translation on ARMACM SIGPLAN Notices10.1145/3140587.306237152:6(333-346)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3140587.3062371
D'Antras AGorgovan CGarside JLuján MCohen AVechev M(2017)Low overhead dynamic binary translation on ARMProceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3062341.3062371(333-346)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3062341.3062371
Show More Cited By

Index Terms

Evaluating Indirect Branch Handling Mechanisms in Software Dynamic Translation Systems
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Translator writing systems and compiler generators

Recommendations

Evaluating indirect branch handling mechanisms in software dynamic translation systems

Software Dynamic Translation (SDT) is used for instrumentation, optimization, security, and many other uses. A major source of SDT overhead is the execution of code to translate an indirect branch's target address into the translated destination block's ...
Evaluating indirect strategies for Chinese-Spanish statistical machine translation: extended abstract
IJCAI '13: Proceedings of the Twenty-Third international joint conference on Artificial Intelligence

Although, Chinese and Spanish are two of the most spoken languages in the world, not much research has been done in machine translation for this language pair. This paper focuses on investigating the state-of-the-art of Chinese-to-Spanish statistical ...
Handling Translation Divergences: Combining Statistical and Symbolic Techniques in Generation-Heavy Machine Translation
AMTA '02: Proceedings of the 5th Conference of the Association for Machine Translation in the Americas on Machine Translation: From Research to Real Users

This paper describes a novel approach to handling translation divergences in a Generation-Heavy Hybrid Machine Translation (GHMT) system. The translation divergence problem is usually reserved for Transfer and Interlingual MT because it requires a large ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CGO '07: Proceedings of the International Symposium on Code Generation and Optimization

March 2007

346 pages

ISBN:0769527647

Sponsors

Publisher

IEEE Computer Society

United States

Publication History

Published: 11 March 2007

Check for updates

Qualifiers

Article

Conference

CGO07

Sponsor:

CGO07: 5th Annual IEEE / ACM International Symposium on Code Generation and Optimization

March 11 - 14, 2007

Acceptance Rates

CGO '07 Paper Acceptance Rate 27 of 84 submissions, 32%;

Overall Acceptance Rate 312 of 1,061 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
385
Total Downloads

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

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gopan DOhmann PMelski DKim TWang CKim TWu D(2017)VertxProceedings of the 2017 Workshop on Forming an Ecosystem Around Software Transformation10.1145/3141235.3141237(1-7)Online publication date: 3-Nov-2017
https://dl.acm.org/doi/10.1145/3141235.3141237
D'Antras AGorgovan CGarside JLuján M(2017)Low overhead dynamic binary translation on ARMACM SIGPLAN Notices10.1145/3140587.306237152:6(333-346)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3140587.3062371
D'Antras AGorgovan CGarside JLuján MCohen AVechev M(2017)Low overhead dynamic binary translation on ARMProceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3062341.3062371(333-346)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3062341.3062371
Chachmon NRichins DCohn RChristensson MCui WReddi V(2016)Simulation and Analysis Engine for Scale-Out WorkloadsProceedings of the 2016 International Conference on Supercomputing10.1145/2925426.2926293(1-13)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1145/2925426.2926293
d'Antras AGorgovan CGarside JLuján M(2016)Optimizing Indirect Branches in Dynamic Binary TranslatorsACM Transactions on Architecture and Code Optimization10.1145/286657313:1(1-25)Online publication date: 5-Apr-2016
https://dl.acm.org/doi/10.1145/2866573
McFarlin DZilles CPrvulovic M(2015)Bungee jumpsProceedings of the 48th International Symposium on Microarchitecture10.1145/2830772.2830781(370-382)Online publication date: 5-Dec-2015
https://dl.acm.org/doi/10.1145/2830772.2830781
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
Jia NYang CWang JTong DWang K(2013)SPIREACM SIGPLAN Notices10.1145/2517326.245151648:7(1-12)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1145/2517326.2451516
Branković AStavrou KGibert EGonzález AFranke HHeinecke APalem KUpfal E(2013)Performance analysis and predictability of the software layer in dynamic binary translators/optimizersProceedings of the ACM International Conference on Computing Frontiers10.1145/2482767.2482786(1-10)Online publication date: 14-May-2013
https://dl.acm.org/doi/10.1145/2482767.2482786
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