Dynamic Binary Translation Algorithm Based on Characteristic of Transfer Instructions

Abstract

Abstract:

Abstract： The traditional dynamic binary translator(DBT) deals with different kinds of transfer instructions in the same way, which leads to great performance loss of DBT. This paper proposed a novel DBT algorithm composed of directmapping and transfertypeinheriting mechanism to efficiently handle transfer translation，based on the distinctive characteristics between innerfunction and outerfunction transfers. Innerfunction transfers were exactly mapped to the same type of transfers in the source machine, which not only reduced the transfers induced by conditional branches, but also avoids memory synchronizations. Outerfunction transfers were dealt with differently to pass function callreturn attributes from source code to translation code, thus improving the hit rate of the target machine branch predictor. The experiment results from EEMBC(embedded microprocessor benchmark consortium) show that the instructions executed in translation code of transfers has been reduced by 58.9%, the branch predictor hit rate has been increased by 80.7%, and the overall DBT performance has been improved by 12.3%.

Key words: dynamic binary translation (DBT), transfer instructions, direct mapping, branch predictor

CLC Number:

LI Zhanhui1,MENG Jianyi2,CHEN Zhijian1,YAN Xiaolang1,2. Dynamic Binary Translation Algorithm Based on Characteristic of Transfer Instructions[J]. Journal of Shanghai Jiaotong University, 2015, 49(02): 173-177.

References

［1］Altman E R, Kaeli D, Sheffer Y. Welcome to the opportunities of binary translation［J］. Computer, 2000, 33(3): 4045.

［2］李剑慧，马湘宁，朱传琪. 动态二进制翻译与优化技术研究［J］. 计算机研究与发展, 2007，44(1): 161168.

LI Jianhui, MA Xiangning, ZHU Chuanqi. Dynamic binary translation and optimization［J］. Journal of Computer Research and Development, 2007, 44(1): 161168.

［3］Jia N, Yang C, Wang J, et al. SPIRE: Improving dynamic binary translation through SPCIndexed indirect branch redirecting［C］∥Proc of the 9th ACM SIGPLAN/SIGOPS Int Conf on Virtual Execution Environments. New York: ACM, 2013: 112.

［4］Brankovic＇ A, Stavrou K, Gibert E, et al. Performance analysis and predictability of the software layer in dynamic binary translators/optimizers［C］∥Proc of the ACM Int Conf on Computing Frontiers. New York: ACM, 2013: 110.

［5］Bellard F. Qemu, a fast and portable dynamic translator［C］∥USENIX Annual Technical Conf. California: FREENIX Track, 2005: 4146.

［6］Hong D Y, Hsu C C, Yew P C, et al. HQemu: A multithreaded and retargetable dynamic binary translator on multicores［C］∥Proc of the 10th Int Symp on Code Generation and Optimization. New York: ACM, 2012: 104113.

［7］WHU Weiwu, WANG Jian, GAO Xiang, et al. GODSON3: A scalable multicore RISC processor with X86 emulation［J］. IEEE MICRO, 2009, 29(2): 1729.

［8］Hsu C C, Liu P, Wang C M, et al. LnQ: Building high performance dynamic binary translators with existing compiler backends［C］∥Int Conf on Parallel Processing. Piscataway, NJ: IEEE, 2011: 226234.

［9］Ottoni G, Hartin T, Weaver C, et al. Harmonia: A transparent, efficient, and harmonious dynamic binary translator targeting the Intel architecture［C］∥Proc of the 8th ACM Int Conf on Computing Frontiers. New York: ACM, 2011: 110.

［10］Chen X H, Shen L, Wang Z Y, et al. Binary compatibility for embedded systems using greedy subgraph mapping［J］. Science China Information Sciences, 2014, 57: 07210610721062.

［11］Chen W, Wang Z Y, Zheng Z, et al. TransARM: An efficient instruction set architecture emulator［J］. Chinese Journal of Electronics, 2011, 20(1): 610.

［12］贾宁，杨春，佟冬，等. 动态翻译系统中的间接转移关联预测算法［J］. 计算机研究与发展, 2014，51(3): 661671.

JIA Ning, YANG Chun, TONG Dong, et al. Corrected software prediction for indirect branch in dynamic binary translation systems［J］. Journal of Computer Research and Development, 20014，51(3): 661671.

［13］Sun T T, Yang Y D, Yang H B, et al. Return instruction analysis and optimization in dynamic binary translation［C］∥The 4th Int Conf on Frontier of Computer Science and Technology. Piscataway, NJ: IEEE, 2009: 435440.

［14］Kim H S, Smith J E. Hardware support for control transfers in code caches［C］∥Proc of the 36th Annual IEEE/ACM Int Symp on Micro Architecture. Piscataway, NJ: IEEE, 2003: 253264.

［15］Hangzhou CSKY Microsystem Corporation. CK810 Introduction［EB/OL］.(20120101) ［20140120］. http://www.csky.com/prodeuct.php.

［16］Luk C K, Cohn R, Muth R, et al. Pin: Building customized program analysis tools with dynamic instrumentation［J］. ACM SIGPLAN Notices, 2005, 40(6): 190200.

[1]	YANG Zhen,FU Zhuang,GUAN Enguang,XU Jiannan,TIAN Shihe,ZHENG Hui. The Kinematic Analysis and Structure Optimization of MLattice Modular Robot [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1153-1159.
[2]	ZHAO Jun1,YU Haidong2. Dynamic Analysis of TwoLink Flexible Manipulators Based on the Absolute Nodal Coordinate Formulation [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1160-1165.
[3]	ZHAO Ziren1,DU Shichang1,HUANG Delin1,REN Fei2,LIANG Xinguang2. Modelling and Bottleneck Analysis of Product Quality in Transient Phase of MultiStage Manufacturing Systems Based on Markovian Chains [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1166-1173.
[4]	HUANG Xuangui. Algorithm for Relatively Small Planted Clique with Small Edge Probability [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1202-1206.
[5]	LUO Jingjinga,YU Haidonga,ZHAO Chunzhanga,b,WANG Haoa,b. Study on Motion Stability of Variable CrossSection Flexible Beams Based on the Absolute Nodal Coordinate Formulation [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1174-1180.
[6]	WANG Yibo1,HUANG Yixiang1,LI Bingchu1,LING Xiao1 ZHAO Shuai1,LIU Chengliang1,ZHANG Daqing2. An Improved Modal Simulation Method for Switched Reluctance Motor Based on Static PreComputation [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1181-1188.
[7]	ZHOU Binghai,LI Ming. Scheduling Method of Manufacturing Cells with Robot Restricted Processing [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1214-1219.
[8]	CHEN Jinping1,ZHANG Shusheng1,HE Weiping1,WANG Mingwei1,HUANG Hui2. Feasible Change Path Search and Optimization Method Based on Driving Parameter Modeling [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1220-1227.
[9]	ZHOU Penghui,MA Hongzhan,CHEN Dongping,CHEN Mengyue,CHU Xuening. Identification of Product Redesign Modules Based on Fuzzy Random Failure Mode and Effects Analysis [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1189-1195.
[10]	PENG Cheng,ZHU Jianyun,CHEN Li. Mode Transition for a Hybrid Electric Vehicle Based on Model Reference Control [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1196-1201.
[11]	LIU Wei,YANG Chao . A Study on Injection Mould Part Quotation Model Based on Back Propagation Neural Network [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1207-1213.
[12]	CHEN Suting，WANG Zhuo，WANG Qi. Aerial Scene Classification Based on Nonlinear Scale Space [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1228-1234.
[13]	CHEN Ning,HE Xiaobin,GUI Weihua,YANG Chunhua. Research on Image Encryption System Based on Chaotic Discrete Sequence [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1273-1280.
[14]	LIU Kaia，ZHANG Liminb，ZHOU Lijuna. Design of Random Restricted Boltzmann Machine Group [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1235-1240.
[15]	ZHU Xinyao1，SONG Baowei2,XU Gang1,YANG Songlin1. Research on Landing Strategy and Influencing Factors of an Autonomous Underwater Vehicle with Supporting Mechanism [J]. Journal of Shanghai Jiaotong University, 2017, 51(10): 1241-1251.