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

　摘 要:基于热路径的动态优化技术是动态二进制翻译器中提高软件运行效率的一种有效方法。如何利用基本块中已有的有限历史运行信息来识别热路径并提高它的预测命中率,同时保持计算开销没有增加是研究的重点。已有的热路径识别算法中基于模型进行预测的方法非常少,算法实现比较复杂。基于隐马尔可夫模型提出一种改进的热路径预测算法。由于状态转移序列惟一,该算法实现简单,可以提高热路径的命中率,在一定程度上改善动态二进制翻译器的性能。最后通过实验对所提出算法的有效性进行验证。
　　关键词:动态二进制翻译;动态优化;热路径;隐马尔可夫模型
　　　　
　　algorithm for hot paths prediction using hidden markov model
　　
　　liu kui1, li shi-ying1, li rui1,2, li ren-fa1
　　( of computer & communication, hunan university, changsha 410082, china; of computer, national university of defense technology, changsha 410073, china)
　　abstract:method of hot paths-based dynamic optimization is effective for improving the operational efficiency of the software in dynamic binary translator. this study focused on how to identify the hot paths by using the existing limited amount of previous operational information of basic blocks,and to enhance the hit rate of the prediction,with no increase of computational cost at the same had been few methods based on models among exsiting hot paths prediction algorithms,which need complicated paper proposed an improved hot paths prediction algorithm based on hidden markov the sequence of state transition was unique,this algorithm was easy to implement,and could improve the hit rate of hot paths as well as the performance of the dynamic binary experimental results verified the efficiency of our algorithm.
　　key words:dynamic binary translation; dynamic optimization; hot path; hidden markov model(hmm)
　　0 引言
　　动态二进制翻译技术是一种即时编译技术,它在程序的运行过程中将针对源体系结构编译生成的二进制代码(源机器码)动态翻译为可以在目的体系结构上运行的代码(目标码),此过程对用户来说是透明的。整个动态翻译过程分为两个阶段,即产生本地代码的翻译阶段和执行阶段。在代码的执行阶段,动态优化器会进行一定的优化。大多数的程序将大部分的时间花费在很小的一部分代码段上,识别并优化这一部分代码将从本质上改善软件的整体性能。
　　频繁执行的代码块称之为热块。代码块就是一个控制转移(如一个分支、调用或跳转指令)结束的指令序列,代码块也称为基本块[1]。当一个代码块变热时,其周围的一些代码块也将变热,由这些热块组成的执行序列称之为热路径。一个热路径就是一个指令序列。热路径是研究人员在设计dynamo[2]系统时提出来的概念,热路径的优化技术是目前动态二进制翻译器主要采用的技术。常见的热路径识别方法主要有分别基于基本块、边和路径的识别方法。这三种方法的预测准确度递增,但是复杂度也随之增加,尤其是基于路径的预测,随着程序的运行,负载急剧增长反而会降低软件的运行效率[3,4]。
　　热路径的产生一定与循环执行有关,因此预测主要针对循环进行,只有热路径优化带来的收益大于开销时才能从整体上提高系统的效率。因此,在热路径的优化过程中既要尽量提高热路径的预测准确率,同时又要控制预测过程的开销,并且优化越早启动越好。已有的热路径预测算法出于计算复杂度的考虑都没有基于模型进行预测,如spanning tree算法[5]、bit tracing算法[3]、net算法[3]、编码算法[6],大多只是计算路径的执行次数,并取执行次数最多的作为热路径,研究的重点是如何更方便、更高效地记录热路径以及更新路径计数器的方法,尤其是当候选热路径的执行次数近似或者执行均衡时,更是很难作出合理的选择。本文基于隐马尔可夫模型(hmm),提出了改进的热路径预测算法,该算法实现简单,在预测延迟不明显增加的情况下,提高了热路径的命中率,从而减少了热路径在cache中的替入替出消耗,一定程度上提升了软件在动态二进制翻译器上的运行效率。
　　1 总体思路
　　本文的总体思想是以程序的基本块为单位,将程序的流程构造成一个满足隐马尔可夫模型(hmm)[7]的有向图,并以图中自上至下的每层为一个状态,每层中的一个代码块可视为一个观察值,热路径即为模型的一个观察序列,程序的流转变为状态的转移,同时,任何时刻每个状态的转移只与前一个状态相关,而与时间以及其他状态无关。很显然,此时基于块的热路径预测过程满足马尔可夫性,是一个马尔可夫过程,即马尔可夫链;而且一个状态中有多个观察值,通过扩展后(详见1.2节),一个观察序列不能直接确定状态的转移序列,因此该过程又是一个隐马尔可夫过程。依据hmm的估算方法,一旦循环程序段的入口代码块的计数器counter达到阈值trigger时,就启动基于该模型的热路径预测,并选取候选热路径candihp中估算概率最大的路径作为热路径。总体思路如图1所示。

　1.1 隐马可夫模型介绍
　　如果一个过程的“将来”仅依赖于“现在”而不依赖“过去”,则此过程具有马尔可夫性,或称此过程为马尔可夫过程。设s是一个由有限个状态组成的集合s={1,2,3,…,n-1,n},随机序列x在t和s时刻所在的状态分别为qt、qs(qt,qs∈s)。若有p(qt=j|qt-1=i,qt-2=k,…)=p(qt=j|qt-1=i),或者p(qt=j|qt-1=i)=p(qs=j|qs-1=i),则随机序列x构成一个一阶马尔可夫链。令aij=p(qt=j|qt-1=i)(1≤i,j≤n),则对于所有的i, j有下面的关系成立:nj=1aij=1(aij≥0)。
　一阶马尔可夫模型可以描述为一个二元组λ(s,a)。s是状态的集合,而a是所有状态转移概率aij组成的一个n行n列的矩阵,其中每一个元素aij表示从状态i转移到j的概率,可表示为a=[aij],aij=p(qt+1=j|qt=i)(1≤i, j≤n)。一阶马尔可夫模型的状态与观察序列一一对应,因此根据观察序列能直接推断出状态转移序列。隐马尔可夫模型是对马尔可夫模型的一种扩展,观察序列不能确定状态的转移。隐马尔可夫模型λ可以表示为一个五元组 λ=(s,v,a,b,π)。s和a与一阶马尔可夫模型一样分别表示一组状态的集合和状态转移矩阵;v是一组输出符号组成的集合,v={v1,v2,v3,…,vm};b是输出符号的概率分布,b={bj(vk)},其中bj(vk)表示在状态j时输出符号vk的概率,bj(k)=p(vk|j)(1≤k≤m,1≤j≤n);π是初始状态概率分布,π={πi},πi=p(q1=i)(1≤i≤n),表示初始时刻选择某个状态i时的概率。
　　
　　hmm的状态是不确定或不可见的,只有通过观察序列的随机过程才能表现出来。观察到的观察序列与状态不是一一对应的,而是通过一组概率分布相联系。hmm是一个双重随机过程(图2),有两个组成部分:马尔可夫链和一般随机过程。前者描述状态的转移,用转移概率描述;后者描述状态与观察序列间的关系,用观察值概率描述。
　　
　　基于模型λ,若给定状态转移序列q={q1,q2,q3,…,qt},则产生观察序列o={o1,o2,o3,…,ot}的概率p(o|λ)为[7]
　　p(o|λ)=qp(o,q|λ)=
　　q1,q2,…,qtπq1bq1(o1)aq1q2bq2(o2),…,aqt-1qtbqt(ot)
　　1.2 基于程序的图解及扩展
　　动态二进制翻译器的热路径优化针对的是频繁执行的代码块序列,主要是程序中循环执行的代码段。图3是一种典型的循环代码段,其中包括结构化程序中常见的顺序、选择和循环三种结构。图4为该程序段基于基本块的图解。由图4可以发现,程序中任何时刻基本块的转移仅与前一基本块有关,而与其他基本块以及时间无关。图中基本块旁边的数字表示在启动热路径预测时代码块的执行次数,由程序运行时的profile获取。
　　
　　通过对图4的扩展,可使其满足隐马尔可夫性。首先将循环中的内循环合并成一个块,本文以代码块较少、循环次数较少的常见内循环为例进行介绍,当然,当内循环较复杂时可多次调用本算法。将图中的每个块视为hmm中一个输出或者是观察值,也即模型λ中集合v的元素,v={a,b,c,d,e,f,g,h,i,j,k}。并使得自顶向下处于同一层次的代码块属于一个状态,如图5所示,也即模型λ中的状态集合s,其中s={q1,q2,q3,q4,q5}。通过对图5的再次扩展,可使其转换成以代码块为单位的图6,也就是使得程序段的每条执行路径在每个状态qi(1≤i≤5)都有输出。
　　
　　基于模型λ的概率估算只在循环入口代码块a的执行次数达到优化触发器的值trigger时才启动预测,本例为了方便计算设trigger=100。候选热块candibb是基本块的计数器count大于阈值basecount的块,一般basecount=trigger×40%[8],可表示为candibb={x|x∈bbset•count(x)>basecount}。bbset指循环内的所有基本块,此处即为集合v。由候选热块组成的执行路径称为候选热路径, candihp={a,x,y|x,y∈candibb•a→x∧x→y∧y→a}。
　　
　　至此,热路径的预测即可通过模型λ进行,图6中的路径adhjk表示hmm的一个输出,也即观察序列oi(1≤i≤m),m为循环内路径总数,并且是一条候选热路径。热路径的预测就是基于模型λ预测其中输出序列oi出现概率p(oi|λ)最大的序列过程。
　　
　　2 基于hmm的建模
　　经过分析,此时热路径的预测变成如下问题的求解过程。
　　已知:a)模型λ=(s,v,a,b,π);b)候选热路径为oi=(o1,o2,…,oi,…,o5)。其中oi∈v。
　　求解:候选热路径中p(oi|λ)值最大的路径,也即求解oi中出现概率最大的观察序列。
　　其中:状态集合s={1,2,3,4,5},qi(1≤i≤5)表示某一个状态;观察值集合为v={a,b,c,d,e,f,g,h,i,j,k}。状态转移矩阵a如下所示,经过扩展后,程序的执行可视为自上至下的执行过程,因此只存在(q1,q2,q3,q4,q5)的状态转移序列,其他出现的概率均为0。
　　a=01000
　　00100
　　00010
　　00001
　　10000
　　b表示各代码块的执行概率分布,b={bj(vk)}。其中:bj(vk)=count/trigger,如bq2(b)=40/100,即为q2状态下出现b的概率;π是初始状态概率分布,π={πi}且πi=p(q1=i),本处很显然π1=1,π1=0(2≤i≤5)。
　　3 算法及复杂度分析
　　1)给定λ以及状态转移序列q=(q1,q2,q3,…,qt),则观察序列oi=(o1,o2,o3,…,ot)的出现概率为p(oi|q,q,λ)=bq1(o1)bq2(o2)bq3(o3),…,bqt(ot);给定λ,则状态转移序列q=(q1,q2,q3,…,qt)的出现概率为p(q|λ)=πq1aq1q2aq2q3,…,aqt-1qt。因此oi和q的联合概率p(oi,q|λ)=p(oi|q,λ)[7]。
　　2)给定λ,若考虑所有的状态转移序列,则p(oi|λ)=qp(o,q|λ)=qp(o|q,λ)p(q|λ)。
　　展开后得到
　　p(oi|λ)=q1,q2,…,qtπq1
　　bq1(o1)aq1q2bq2(o2)aq2q3,aqt-1qtbqt(ot)
　　
　　由于只存在q=(q1,q2,q3,…,qt)转移序列,其他情况的状态转移计算结果为0,无须纳入计算,即π1=1,πi=0(2≤i≤5)。此时计算变成:
　　p(oi|λ)=bq1(o1)aq1q2bq2(o2)aq2q3…aqt-1qtbqt(ot)
　　整理后即为
　　p(oi|λ)=bq1(o1)bq2(o2)…bqt(ot)aq1q2aq2q3…aqt-1qt
　　
　　则计算p(oi|λ)共需要进行2(t-1)次乘法,整个算法需要计算n×2(t-1)次乘法(n为候选热路径数)。

　本例对于每条候选热路径只需计算8次乘法运算,候选热路径数3条,则总的计算次数为24次。通过计算获得候选热路径的最大可能执行概率,选取该候选热路径作为热路径。
　　在本例中
　　p(oi|λ)=bq1(o1)aq1q2bq2(o2)aq2q3bq3(o3)aq3q4bq4(o4)aq4q5bq5(o5)
候选热路径有{abeii,abejk,adhjk}。
　　通过计算可以得到p(abeii|λ)=100/100×50/100×50/100×20/100×20/100=0.01;同理可计算得p(abejk|λ)=0.06; p(adhjk|λ)=0.0448(由于bj(vk)的基数都是trigger,计算时可直接使用基本块的执行次数count进行计算,本处为了更直观,仍使用比值计算)。
　　
　　p(abejk|λ)>p(adhjk|λ)>p(abeii|λ),那么最热的热路径为abejk。
　　
　　若采用传统的热路径执行次数判断法,则c{abeii}=20;c{abejk}=30;c{adhjk}=35。
　　
　　c{adhjk}>c{abejk}>c{abeii},因为路径adhjk的执行次数最多,所以最热的路径为adhjk。
　　
　　由以上复杂度分析可知,尽管思路完全不同,基于隐马尔可夫模型的计算,其计算过程并不复杂,而且实现非常简单。
　　4 实验结果与分析
　　为了评价热路径预测算法的有效性,下面分别给出了预测命中率、噪声比、预测延迟的定义。假设启动预测后,候选热路径pi的执行次数为f(pi)(1≤i≤n),则所有候选热路径的执行次数约为ni=1 f(pi)+n×trigger,热路径的预测命中率为
　　
　　hitrate(p)=f(p)/(ni=1f(pi)+n×trigger)
　　其中:p表示预测出的热路径。
　　噪声比是指将非热路径作为热路径的概率,可表示为
　　noise=(ni=1f(pi)-f(p))/(ni=1f(pi)+n×trigger)
　　其中:n为候选热路径数。
　　预测延迟predelay是指启动热路径预测前所有路径执行的次数与程序段总的执行次数的比值,可表示为
　　perdelay=mi=1f(pi(t))/t
　　
　　其中:f(pi(t))表示t时刻启动预测前路径i的执行次数;m表示路径总数;t是程序段总的执行次数。预测延迟越大,则热路径的丢失机会成本[3]越高,同时运行时的负载也将越高。
　　预测的重点就是如何提高命中率hitrate(p),并保持低的预测延迟和噪声比noise。本算法的实现在skyeye[9]上进行。skyeye是国内一款开源的虚拟机,目标是模拟常见的嵌入式计算机系统,可在skyeye上运行linux、μclinux等多种嵌入式操作系统和各种系统软件。skyeye的动态二进制翻译模块(dbct)对运行在其上的操作系统进行加速,该模块的实现基于qemu。
　　下面是在skyeye的linux系统上运行系统性能测试工具nbench benchmark suite的结果,并针对上面介绍的三个指标进行分析。表1给出了benchmark程序中的绝对热路径数(a-hotpaths)与相对热路径数(r-hotpaths)占路径总数比例的情况。其中绝对热路径是指在循环内执行次数远远多于其他分支的路径;相对热路径是指循环内平均执行的路径。大多数情况下循环内绝对热路径要比相对热路径多,可以发现其中assignment和huffman程序中相对热路径的数目较多。同时,从表1可以了解到huffman程序绝对路径与相对路径数相似,assignment程序的相对热路径比绝对热路径稍多,idea程序两者相差较大。这三个程序具有一定的代表性,因此下面就采用这三个程序对本文所提出的算法性能进行分析。
　　表1 路径情况
　　
　　benchmarkpathsa-hotpaths/%r-hotpaths/%
　　numeric sort7002.429 1.571
　　string sort7502.800 1.600
　　bitfield 713 2.104 1.543
　　fp emulation8271.693 0.967
　　fourier6972.296 1.578
　　assignment 7622.887 3.281
　　idea 7632.752 1.180
　　huffman7392.0301.894
　　
　　图7给出了所提出算法下huffman、idea和assignment程序的预测延迟与命中率的关系图。由图可以看出,由于huffman的路径数较少,在盲测时的命中率稍高;同时由于idea的绝对热路径与相对热路径占用比例相差较大,idea的命中率总体呈上升趋势。
　　
　　图8给出了上述三个程序的噪声比与预测延迟的关系图。由图可以看出,与图7相对应,idea的噪声比明显要小;同时由于assignment的相对路径较多,整体噪声比较大。结合图7和8可以发现,若在预测延迟的20%处启动预测,将在hitrate与noise之间达到一个较好的平衡。
　　
　　预测命中率的计算相对比较复杂,并且预测的目的是通过提高命中率来减少热路径重复翻译产生的开销,从而提高程序的运行效率,减少程序的运行时间,因此本文直接针对程序的运行时间进行分析,运行时间越少自然命中率越高,算法更优越。图9给出了所提出的算法与基于路径数预测方法以及本地的运行时间比较。从图中可以发现,利用基于hmm模型的热路径算法程序运行时间有不同程度的减少,其中相对热路径较多的assignment等程序减少明显。由于显示的需要,本文以代码块较少的简单程序作为实例进行分析。如果程序更加复杂,如大型系统程序,该算法的效果将更加显著。当然,如果直接在本地运行,速度差别仍然较大。以上实验结果和分析表明,本算法在保持预测延迟不明显增加的情况下可以提高热路径的命中率,从而提升软件的总体运行效率。
　　
　　5 结束语
　　热路径是程序在某一个时间频繁执行的代码块的集合,识别并优化热路径能显著改善程序在动态二进制翻译器上的运行性能。热路径预测的目标是如何利用有限的已有运行信息预测出未来将要频繁执行的路径,预测算法要尽量简单,容易实现,并且只有预测带来的效益大于开销时,预测才有意义。本文运用隐马尔可夫模型提出了改进的基于块的热路径预测算法,该算法的优越性主要体现在热路径的预测基于预测模型,尤其当候选热路径执行次数近似时,热路径的选择更具有效性。该算法实现简单,提高了热路径的命中率,降低了热路径在cache中替入替出的消耗,从而能够提高软件在虚拟机中的运行速率。下一步工作将针对热路径的阶段变化情况进行研究。
　　参考文献:
　　[1]
　　scott k,kumar ad reduction techniques for software dynamic translation[c]//proc of the 18th international parallel and distributed processing symposium.2004.
　　
　　[2]ebcioglu c binary translation and optimization[j].ieee trans on computers,2001,50(6):529-548.
　　[3]duesterwald e,bala re profiling for hot path prediction:less is more[c|//proc of the 9th international conference on architectural support for programming languages and operating york:acm press,2000:202-211.
　　
　　[4]ball t,mataga p,sagiy profiling versus path profiling:the showdown[c]//proc of the 25th acm sigplan-sigact symposium on principles of programming york:acm press,1998:134-148.
　　
　　[5]ball t,larus j ent path profiling[c]//proc of the 29th annual acm/ieee international symposium on gton dc:ieee computer society,1996:46-57.
　　
　　[6]史辉辉,管海兵,梁阿磊.动态二进制翻译中热路径优化的软件实现[j].计算机工程,2007,33(23):78-83.
　　[7]rabiner l r.a tutorial on hidden markov models and selected applications in speech recognition[j].proceedings of ieee,1989,77(2):257-286.
　　
　　[8]ung d,cifuentes zing hot paths in a dynamic binary tanslalor[c]//proc of acm sigarch computer architecture york:acm press,2001:55-65.
　　
　　[9]chen yu,ren jie,zhu hui,et c binary translation and optimization in a whole-system emulator-skyeye[c]//proc of international conference on parallel gton dc:ieee computer society,2006:327-336.