Email this article A Dynamic-Static Combined Code Layout Reorganization Approach for Dynamic Binary Translation
Abstract
Dynamic binary translation (DBT) has attracted much attention as a powerful technique for the runtime adaptation of software among different ISAs. It offers unprecedented flexibility in the control and modification of a program during the runtime. However, its inherent high overhead has perplexed researchers for many years. In order to reduce the overhead of DBT, this paper presents a dynamic-static combined approach to reorganize the layout of software cache. Under this approach, we first employ an emulating execution to collect the profile information and the translated target code. Especially, the path of execution flow will be tracked. In the static phase, based on the profile information collected in the previous stage, we first use the method of code replicating to build the traces, and then reorganize the layout of the target code by putting the hottest traces at the top of the software cache. Because of exact prediction and improved locality, the execution stream will concentrate on a small area with less control transfer. This approach can greatly reduce the overhead of DBT on the condition that the program runs repeatedly. Experimental results on executing the SPEC 2000 benchmarks show that our approach can reduce more than 30% run time on average.
Keywords
References
[1] Jinpyo Kim, Wei-Chung Hsu, Pen-Chung Yew, “COBRA: An Adaptive Runtime Binary Optimization Framework for Multithreaded Applications”, International Conference on Parallel Processing (ICPP), 2007, pp: 25-33.
[2] L. Baraz, T. Devor, O. Etzion, et al, “IA-32 Execution Layer: a two-phase dynamic translator designed to support IA-32 applications on Itanium-based systems.” In 36th International Symposium on Microarchitecture, 2003, pp: 191-201.
[3] HP ARIES Dynamic Binary Translator, http://h21007.www2.hp.com.
[4] LUK, C.-K., COHN, R., MUTH, R., et al, “Pin: building customized program analysis tools with dynamic instrumentation”. In PLDI ’05 (New York, NY, USA, 2005), pp. 190–200.
[5] V. Bala, E. Duesterwald, and S. Banerjia, “Dynamo: A transparent runtime optimization system”. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’00), June 2000.
[6] Nethercote, N., Seward, J. Valgrind: a framework for heavyweight dynamic binary instrumentation. In PLDI ’07 (New York, NY, USA, 2007), pp. 89–100.
[7] Swaroop Sridhar, Jonathan S. Shapiro, Prashanth P. Bungale, et al, “HDTrans: An Open Source, Low-Level Dynamic Instrumentation System”, In VEE '06: Proceedings of the 2nd international conference on Virtual execution environments (2006), pp. 175-185.
[8] B. Cmelik and D. Keppel, “Shade: A fast instruction-set simulator for execution profiling”, In Proceedings of the 1994 ACM SIGMETRICS Conference on the Measurement and Modeling of Computer Systems (1994), pp. 128–137.
http://dx.doi.org/10.1145/183018.183032
[9] Fabrice Bellard. “QEMU: a Fast and Portable Dynamic Translator”, Proceedings of the USENIX Annual Technical Conference, 2005, pp.41-46.
[10] K Ebcioglu, E R Altman, “DAISY: Dynamic Compilation for 100% Architectural Compatibility”, 24th Annual International Symposium on Computer Architecture (ISCA'97), pp: 26-37.
[11] J. Lu, H. Chen, P.-C. Yew, et.al, “Design and implementation of a lightweight dynamic optimization system,” The Journal of Instruction-Level Parallelism, vol. 6, 2004.
[12] Youfeng Wu, Mauricio Breternitz, Justin Quek, Orna Etzion, Jesse Fang. “The Accuracy of Initial Prediction in Two-Phase Dynamic Binary Translators”. Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization. pp:227-238.
[13] A. Chernoff and R. Hookway, “DIGITAL FX!32 - Running 32-Bit x86 Applications on Alpha NT,” USENIX Association. Berkeley CA: Proceedings of the USENIX Windows NT Workshop, August 1997.
[14] Chaohao Xu, Jianhui Li, Tao Bao, Yun Wang, “Metadata driven memory optimizations in dynamic binary translator”, Proceedings of the 3rd international conference on Virtual execution environments. San Diego, California, USA. Pages: 148 – 157, 2007.
[15] GNU Compiler Collection Internals.
[16] K. Hazelwood and M. D. Smith. “Managing bounded code cache in dynamic binary optimization systems”, Transaction on Code Generation and Optimization, 3:263-294, 2006.
http://dx.doi.org/10.1145/1162690.1162692
[17] K. Hazelwood and J. E. Smith, “Exploring Code Cache Eviction Granularities in Dynamic Optimization Systems”, Proceeding of the International Symposium on Code Generation and Optimization, pages 89-99, 2004.
[18] A. Guha, K. Hazelwood and Mary Lou Soffa, “Reducing Exit Stub Memory Consumption in Code Caches”, High Performance Embedded Architecture and Compilers, Second International Conference, pages 87-101, 2007.
[19] D. L. Bruening and S. Amarasinghe, “Maintaining Consistency and Bounding Capacity of Software Code Caches”, Proceedings of the International Symposium on Code Generation and Optimization, pages74-85, 2005.
http://dx.doi.org/10.1109/CGO.2005.19
[20] D. L. Bruening and V. Kiriansky, “Process-Shared and Persistent Code Caches”, Proceedings of the 4th International Conference on Virtual Execution Environment, pages 61-70, 2008.
[21] D. L. Bruening, “Efficient, Transparent, and Comprehensive Runtime Code Manipulation”, Ph.D thesis, Massachusetts Institute of Technology (2004).
[22] Apala Guba, Kim Hazewood and Mary Lou Soffa, “DBT Path Selection for Holistic Memory Efficiency and Perfomance”, VEE’10 March 17-19, 2010, Pittsburgh, Pennsylvania, USA.
[23] David Hiniker, Kim Hazelwood, Michael D. Smith, “Harvard UniversityImproving Region Selection in Dynamic Optimization Systems”, Proceedings of the 38th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO’05).
[24] Duane Merrill, Kim Hazelwood, “Trace Fragment Selection within Method-based JVMs”, VEE’08, March 5-7, 2008, Seattle, Washington, USA.
[25] D. Bruening, T. Garnett, S. Amarasinghe. “An infrastructure for adaptive dynamic optimization”, In International Symposium on Code Generation and Optimization, pages 265-275, San Francisco, California, 2003.
[26] Andreas Krall, “Improving Semi-static Branch Prediction by Code Replication”, SIGPLAN 94-6/94 Orlando, Florida USA.
[27] Yunchao He, Chen Kai, Jinghui Gu, et.al, “A New Approach to Reorganize Code Layout of Software Cache in Dynamic Binary Translator”, (PAAP2010). Accepted.
[28] Haipeng Deng, Kai Chen, Bo Liu, et al, “Efficient Online Trace Building Using Code Replication”, GCC 2010, Accepted.
[29] Yindong Yang, Haibing Guan, Erzhou Zhu, Hongbo Yang, Bo Liu, CrossBit: A Multi-Sources and Multi-Targets DBT, CLOUD COMPUTING 2010, November 21-26, 2010 - Lisbon, Portugal, accepted.
[30] Jinghui Gu,Chao Xu,Ling Lin,Juyu Zheng,Kai Chen,Haibing Guan, The Implementation of Static-integrated Optimization Framework for Dynamic Binary Translation, ITCS2009, Kiev, Ukraine, 25-26 July, 2009.
[31] Huihui Shi, Yi Wang, Haibing Guan, Alei Liang,"An Intermediate Level Optimization Framework for DBT", ACM SIGPLAN notice, vol 42(5),2007.5:3~9.
Full Text: PDF