浅析基于隐马尔可夫模型的热路径预测算法研究

《浅析基于隐马尔可夫模型的热路径预测算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浅析基于隐马尔可夫模型的热路径预测算法研究摘要:基于热路径的动态优化技术是动态二进制翻译器中提高软件运行效率的一种有效方法。如何利用基本块中已有的有限历史运行信息来识别热路径并提高它的预测命中率,同时保持计算开销没有增加是研究的重点。已有的热路径识别算法中基于模型进行预测的方法非常少,算法实现比较复杂。基于隐马尔可夫模型提出一种改进的热路径预测算法。由于状态转移序列惟一,该算法实现简单,可以提高热路径的命中率,在一定程度上改善动态二进制翻译器的性能。最后通过实验对所提出算法的有效性进行验证。　　关键词:动态二进制

2、翻译;动态优化;热路径;隐马尔可夫模型　　　　　AlgorithmforhotpathspredictionusinghiddenMarkovmodel　　　　LIUKui1,LIShi-ying1,LIRui1,2,LIRen-fa1　　(ofComputer&Communication,HunanUniversity,Changsha10082,China;ofComputer,NationalUniversityofDefenseTechnology,Changsha10073,China)　　A

3、bstract:Methodofhotpaths-baseddynamicoptimizationiseffectiveforimprovingtheoperationalefficiencyofthesoftwareindynamicbinarytranslator.Thisstudyfocusedonhowtoidentifythehotpathsbyusingtheexistinglimitedamountofpreviousoperationalinformationofbasicblocks,andt

4、oenhancethehitrateoftheprediction,withnoincreaseofcomputationalcostatthesamehadbeenfewmethodsbasedonmodelsamongexsitinghotpathspredictionalgorithms,whichneedcomplicatedpaperproposedanimprovedhotpathspredictionalgorithmbasedonhiddenMarkovthesequenceofstatetran

5、sitionwasunique,thisalgorithmwaseasytoimplement,andcouldimprovethehitrateofhotpathsaswellastheperformanceofthedynamicbinaryexperimentalresultsverifiedtheefficiencyofouralgorithm.　　Keywords:dynamicbinarytranslation;dynamicoptimization;hotpath;hiddenMarkovmodel

6、(HMM)　　0引言　　动态二进制翻译技术是一种即时编译技术,它在程序的运行过程中将针对源体系结构编译生成的二进制代码(源机器码)动态翻译为可以在目的体系结构上运行的代码(目标码),此过程对用户来说是透明的。整个动态翻译过程分为两个阶段,即产生本地代码的翻译阶段和执行阶段。在代码的执行阶段,动态优化器会进行一定的优化。大多数的程序将大部分的时间花费在很小的一部分代码段上,识别并优化这一部分代码将从本质上改善软件的整体性能。　　频繁执行的代码块称之为热块。代码块就是一个控制转移(如一个分支、调用或跳转指令)结束的指

7、令序列,代码块也称为基本块[1]。当一个代码块变热时,其周围的一些代码块也将变热,由这些热块组成的执行序列称之为热路径。一个热路径就是一个指令序列。热路径是研究人员在设计dynamo[2]系统时提出来的概念,热路径的优化技术是目前动态二进制翻译器主要采用的技术。常见的热路径识别方法主要有分别基于基本块、边和路径的识别方法。这三种方法的预测准确度递增,但是复杂度也随之增加,尤其是基于路径的预测,随着程序的运行,负载急剧增长反而会降低软件的运行效率[3,4]。　　热路径的产生一定与循环执行有关,因此预测主要针对循环进

8、行,只有热路径优化带来的收益大于开销时才能从整体上提高系统的效率。因此,在热路径的优化过程中既要尽量提高热路径的预测准确率,同时又要控制预测过程的开销,并且优化越早启动越好。已有的热路径预测算法出于计算复杂度的考虑都没有基于模型进行预测,如spanningtree算法[5]、bittracing算法[3]、NET算法[3]、编码算法[6],大多只是计算路径的执行次数,并取