（计算机应用技术专业论文）一种两级代码缓存框架设计与测评.pdf

北京工商大学硕士学位论文 摘要 为了解决指令集兼容问题，以及提高程序的执行速度，研究人员开发了跨指 令集虚拟机系统、动态二进制翻译系统、动态二进制优化系统以及一些模拟器系 统。代码缓存管理是上述系统设计和实现中的关键环节之一，对系统性能具有重 要影响。 本文以程序的局部性原理为指导，通过设计高效的代码缓存来提高上述系统 的运行速度，重点研究代码缓存的索引存储结构和热点替换算法。 本文的研究内容及主要贡献有以下四点： 1 提出了新的两级代码缓存框架的索引和存储方法( c - c c f - u i ， g e n e r a t i o n a lc o d ec a c h ef r a m e w o r k - u n i t e di n d e x i n g ) 。原来的两级 代码缓存框架( 6 c c f ，g e n e r a t i o n a lc o d ec a c h ef r a m e w o r k ) 将整个代 码缓存空间分成不连续的三部分，替换一个热点需修改两个索引表，并 在内存中移动热点两次。本文采统一索引的方法，将热点属于哪一级代 码缓存与热点的存储位置分离，消除了替换热点时内存移动的开销，并 减少了查找索引表的开销。实验表明，g c c f u i 框架查找索引表和替换 热点的时间比g c c f 框架平均减少了9 0 7 。 2 实现了一个代码缓存性能评测模拟器，用于评测代码缓存管理框架使用 各种替换算法( f i f o 、l f u 、l r u ) 时的性能； 3 评测了g c c f u i 框架分别采用f i f o 、l f u 、l r u 替换算法时的性能，发 现g c c f - u i 框架两级都采用f i f o 替换算法时性能最好； 4 将c - c c f - u i 与单级代码缓存框架进行了性能比较。在相同条件下， g c c f u i 框架的热点命中率明显高于单级代码缓存框架。 本文提出的g c c f - u i 框架，可以应用于跨指令集虚拟机系统、动态二进制 优化系统、动态二进制翻译系统和一些模拟器的设计当中，以重复利用翻译后或 优化过的代码，减少重新翻译或优化代码的代价，特别是减少查找索引表和替换 热点的时间，提高各种系统的执行速度。 关键词：代码缓存；统一索引；替换算法；性能测评 一种两级代码缓存框架设 ，与测评 a b s t r a c t t oa d d r e s st h ei n s t r u c t i o ns e tc o m p a t i b i l i t yp r o b l e m sa n dt oi m p r o v e t h es p e e do ft h ea p p li c a t i o n s ，v i r t u a lm a c h i n es y s t e m s ，d y n a m i cb i n a r y t r a n s l a t i o ns y s t e m s ，d y n a m i cb i n a r y o p t i m i z a t i o ns y s t e m sa n dal o to f s i m u l a t o r sa r ed e v e l o p e d c o d ec a c h em a n a g e m e n ti sas i g n i f i c a n tp a r to f t h e s es y s t e m s ，a n dh a sa ni m p o r t a n ti m p a c to nt h e i rp e r f o r m a n c e t h i sp a p e ri st r y i n gt oi m p r o v et h es p e e do ft h e s es y s t e m sb yd e s i g n i n g a ne f f i c i e n tc a c h ec o d eb a s e do nt h ep r i n c i p l eo fl o c a l i t y t h i sp a p e r f o c u s e so nt h ei n d e x i n ga n ds t o r a g es t r u c t u r eo fc o d ec a c h ea n dh o tt r a c e r e p l a c e m e n ta l g o r it h m s t h ec o n t e n t sa n dc o n t r i b u t i o n so ft h isp a p e ra r ea sf o ll o w e d ： 1 p r o p o s ean e wf r a m e w o r kn a m e dg e n e r a t io n a lc o d ec a c h e f r a m e w o r k u n i t e di n d e x ( g c c f u i ) t h eo r i g i n a lg e n e r a t i o n a lc o d e c a c h ef r a m e w o r k ( g c c f ) d i v i d e st h ee n t i r ec o d ec a c h ei n t ot h r e ep a r t s ， t w oi n d e xt a b l e sm u s tb em o d i f i e da n dt h eh o tt r a c e m u s tb em o v e d t w i c ei nm e m o r yi no r d e rt or e p l a c eah o tt r a c e w ep r o p o s eg c c f - u 1 w h i c hu s e s au n i f i e di n d e x i n g ，a n dm a k et h eh o tt r a c es t o r a g el o c a t i o n i r r e l e v a n tw i t hw h i c hg e n e r a t i o nc o d ec a c h ei tb e l o n g s g c c f u i e li m i n a t e st h em o v e m e n to v e r h e a dw h e nh o tt r a c e sa r er e p l a c e d ，a n d r e d u c et h et i m eo v e r h e a do fs e a r c h i n gt h ei n d e xt a b l e e x p e r i m e n t s s h o wt h a t ，r e g a r d i n gt h et i m eo v e r h e a do fs e a r c h i n gi n d e xt a b l ea n d r e p l a c i n gh o tt r a c e s ，g c c f u id e c r e a s e s9 0 7p e r c e n to na v e r a g e c o m p a r e dw i t hg c c f 2 d e s i g nac o d ec a c h ee m u l a t o rt oe v a l u a t et h ep e r f o r m a n c eo f g e n e r a t io n a lc o d ec a c h ef r a m e w o r k ： 3 e v a l u a t et h ep e r f o r m a n c eo fg c c f u 1w h e nitu s e sf i f o ，l f ua n d l r ua sr e p l a c e m e n ta l g o r it h m s ，a n df i f og e t sb e s tp e r f o r m a n c e ： 4 c o m p a r et h ep e r f o r m a n c eo fg c c f u 1w i t hs i n g l ec o d ec a c h e 北京工商人学硕士学位论文 f r a m e w o r k ，a n df i n dt h a tt h eh i tr a t eo fg c c f u ii n c r e a s e so b v i o u s l y t h ep r o p o s e dg c c f u if r a m e w o r kc a nb ea p p l i e dt ov i r t u a lm a c h i n e s y s t e m s ，d y n a m i cb i n a r yo p t i m i z a t i o ns y s t e m s ，d y n a m i cb i n a r yt r a n s l a t i o n s y s t e m sa n dan u m b e ro fs i m u l a t o r s ，t or e u s et h et r a n s l a t e do ro p t i m i z e d c o d e s ，t or e d u c et h eo v e r h e a do fo p ti m i z i n go rt r a n s l a t i n gt h e s ec o d e s r e p e a t e d l y ，e s p e c i a l l yt or e d u c et h et i m eo v e r h e a do fs e a r c h i n gi n d e x t a b l ea n dr e p l a c i n gh o tt r a c e s ，a n di m p r o v et h es p e e do ft h o s es y s t e m s k e yw o r d s ：c o d ec a c h e ：u nit e din d e x in g ；r e pia c e m e n taig o rit h m ： p e r f o r m a n c ee v alu a t io n n i 北京工商大学学位论文原创性声明 本人郑重声明：所呈交的学位论文是本人在导师指导下进行的研究工作所 取得的研究成果。除了文中已经注明引用的内容外，论文中不包含其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明。本声明的法律后果完全由本人承担。 学位论文作者签名：溢里至 日期：亍年厂月“日 北京工商大学学位论文授权使用声明 本人完全了解北京工商大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属北京工商大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以采用影印、缩印或其它复 制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 学位论文电子版同意提交后，可于口当年口一年口二年后在学校图 书馆网站上发布，供校内师生浏览。 学位论文作者签名： 导师签名：遣丝笙日期泗粤年垆伽 北京工商大学硕士学位论文 第1 章绪论 1 1 论文的研究背景和意义 信息革命的浪潮方兴未艾。当今的世界，是一个知识膨胀、信息爆炸的世界； 当今的时代，是一个一日千里、日新月异的时代。人们需求的不断增长、事物复 杂度的不断提高，这对利用计算机技术处理复杂问题既提供了机遇，又提出了挑 战。 在计算机体系结构和编译系统领域中，有两个问题长期得不到彻底解决：一 个是指令集兼容问题【1 】【2 】【3 】【4 】【5 1 1 6 7 1 引，另一个是程序的执行速度问题 【1 6 1 【1 7 l 【1 8 1 1 1 9 】【冽【2 1 】【2 2 1 。代码缓存是解决上述两个问题的一种有效手段，通过重复利 用已经翻译过或优化过的代码来加快系统的执行速度。 本文中代码缓存的主系统是中科院计算所先进微系统组开发的跨指令集软 硬件协同设计虚拟化平 4 4 1 ，软件部分是一个动态翻译系统，硬件部分为自定 义m i p s 指令集的超标量核心，通过协同设计实现对x 8 6 指令集的兼容。本文的 研究重点是设计一个高效的代码缓存【3 6 1 1 3 7 】【3 8 1 1 3 9 j 【4 0 j ，加快整个虚拟化平台的运行 速度。 1 1 1 指令集兼容问题 因为x 8 6 指令集占据了桌面市场和中低端服务器市场的绝大部分份额，文 献【3 】甚至得出了“不支持x 8 6 指令集的处理器注定会失败，不管它运行速度多 快”的结论。新的体系结构的设计者们不得不面对兼容x 8 6 指令集的问题。从 理论上说，r i s c 和v l i w 体系结构比c i s c 体系结构要优越得多，也更利于编 译器产生高效的二进制代码【4 2 】，但是要想得到市场的认可，必须解决兼容x 8 6 指令集的问题。 目前解决兼容x 8 6 程序问题主要有三种方、法【1 】： 1 二进制翻译 二进制翻译( b i n a r yt r a n s l a t i o n ) 是一种直接翻译二进制可执行程序的技 术，目标是在不修改、不重新编译原来的二进制程序的前提下在目标指令集 一种两级代码缓存框架设计与测评 上运行原指令集的程序。二进制翻译可分为解释执行、静态二进制翻译和动 态二进制翻译三种： 1 ) 解释执行 解释执行是指对原指令集代码中的每条指令进行解释执行，通常需要使 用- d , 段指令解释原来指令集的一条指令，系统不保存也不缓存解释过的指 令，也不进行任何优化。解释器相对容易开发，比较容易与老的体系结构兼 容，但效率很差【4 l 【6 】。解释执行系统不使用代码缓存，无法利用已经解释过 的代码，因此速度非常慢。 如开源的虚拟机b o c h s 。b o c h s 通过解释执行的方式执行x 8 6 程序，可 以运行在x 8 6 、m i p s 等多种平台上，并提供了很好的调试接口。但是因为 b o c h s 采用解释执行的方式，速度非常慢，因此只适合在研究中使用，无法 商业化【2 9 1 。 2 ) 静态翻译 静态翻译是在原指令集代码执行之前对其进行翻译，将原指令集的二进 制可执行程序文件a 完全翻译成目标指令集上的二进制可执行程序文件b ， 然后在目标机上执行程序b 。一次翻译的结果可以多次使用。静态翻译器有 足够的时间进行完整有效的优化，效率较高【5 3 1 。然而，静态翻译器可能无法 完整地翻译一个程序【5 1 1 ，因而需要依赖解释器的支持1 5 0 i ；而且静态翻译器需 要终端用户的参与【4 9 1 ，这给用户造成了很大不便。静态翻译系统也不需要使 用代码缓存，因为它具有充足的时间进行的离线翻译和优化工作。 如中科院计算所开发的b i t r a n l l 】和d e c 公司开发的f x l 3 2 9 】【1 0 】【1 1 】。 b i t r a n 翻译器是一个纯静态的二进制翻译器，其设计目标是将 x 8 6 l i n u x 下的e l f 格式的可执行文件翻译到低级c 程序，然后用g c c 做后 端，翻译到目标机( m i p s ) 上的可执行文件。这个过程可以表示为从( x 8 6 ， l i n u x ，e l f ) 至i j ( m i p s ，l i n u x ，e l f ) 的转换1 1 1 。 d e c 公司1 9 9 6 年研发的f x1 3 2 系统是一个轮廓信息指导的 ( p r o f i l e d i r e c t e d ) 二进制翻译器，目的是为了能将运行在x 8 6 w i n n t 系统下 的应用程序运行在a l p h a w i n n t 下。它结合静态翻译和动态解释，具有正确， 高效而且透明的特点。f x1 3 2 系统能够正确翻译w i n n t 下的l o t u s 、e x c e l 、 2 北京工商大学硕士学位论文 w o r d 等实用程序，且使翻译后的代码在a l p h a5 0 0 上运行与p e n t i u m2 0 0 性 能相当，真正达到了实用【9 j 【l o l 【1 1 l 。 3 ) 动态翻译 动态翻译则在程序运行时对执行到的指令段进行翻译，克服了静态翻译 的一些缺点，如可以解决大部分实际情况中的代码自修改问题，而这对于静 态翻译是不可能解决的1 4 1 。动态翻译可以利用执行时得到的动态信息来发掘 静态编译器所不能发现的优化机会。动态翻译器对用户可以做到完全透明， 无需用户干预。动态翻译系统的关键是平衡执行速度与系统代价，必须把翻 译代价降低到一定程度才能满足用户的需要，因此需要使用代码缓存重复使 用翻译过的代码，提高系统的执行速度。 在二进制翻译的各种技术中，动态二进制翻译技术相对其他两种技术具 有明显优势，因此得到了越来越多的研究，产生了很多动态二进制翻译系统， 如中科院计算所开发的d i g i t a l b d d g c l l l ，i n t e l 开发的认一3 2e x e c u t i o n l a y e r 1 4 1 ，i b m 开发的d a i s y 1 2 l 等。 d i g i t a l b r i d g e 动态翻译系统能够使x 8 6 程序可以直接通过该系统运行在 m i p s 机器上。其运行模式是：由d i g i t a l b f i d g e 加载x 8 6 程序及其关联的动态 链接库，通过解释执行x 8 6 代码，或者对达到一定热度的x 8 6 代码进行翻 译和优化，生成m i p s 机器代码后执行，从而提高程序的执行效率。整个 d i g i t a l b d d g e 系统包括翻译器都无需用户干预【1 1 。 i n t e l 的i a - 3 2e x e c u t i o nl a y e r ，它是一种两阶段的动态翻译系统，能够 使x 8 6 程序运行在i t a n i u m 机器上，从而使i t a n i u m 体系结构占有更大的市 场份额【1 4 1 。i b m 的d a i s y 能够使x 8 6 程序运行在采用v l i w 指令集的 p o w e r p c 机器上1 12 1 。 动态翻译技术解放了新体系结构的设计者，是他们能够专注于提高处理 器的性能，也使新的处理器能够在市场上具有更强的竞争力。 2 跨指令集虚拟机 跨指令集虚拟机的目标是虚拟出一个完整的体系结构，模拟整个源机器 平台的硬件，不仅包括模拟源机器平台的指令，而且需要模拟内存管理单元， 外设等等，能够在二进制翻译系统的支持下启动源机器的整个操作系统，然 3 一种两级代码缓存框架设计与测评 后在这个操作系统之上执行所有的源机器的系统程序和应用程序 【2 3 】【驯【矧【2 6 1 1 2 7 1 2 8 l 【2 9 1 。跨指令集虚拟机系统的关键是提高执行速度，因此也需 要使用代码缓存重复使用翻译过的代码，提高系统的执行速度。 如开源虚拟机q e m u l 4 5 】和t r a n s m e t a 公司开发的c o d em o r p h i n g i 刈1 3 1 1 。 q e m u 是一个用c 语言开发的开源的虚拟机，通过解释和翻译相结合 的方式执行，可以在x 8 6 、p o w e r p c 、a r m 、s p a r c 、a l p h a 和m i p s 的c p u 上模拟出x 8 6 、p o w e r p c 、a r m 和s p a r c 等各种机器，具有非常好的可移植 性和较快的速度【4 5 1 。 c r u s o e 是t r a n s m e t a 公司在2 0 0 0 年开发的v l i w 指令集芯片，具有 高性能、低功耗的特性，适合在嵌入式和移动计算领域应用。c r u s o e 通过 c o d em o r p h i n g 技术解决兼容x 8 6 指令的问题。c o d em o r p h i n g 是一个二进 制翻译软件，常驻在系统r o m 中，开机时会被载入内存，然后该软件动态 地将x 8 6 指令翻译成删指令执行，然后交由c r u s o e 芯片执行【3 0 1 1 3 1 1 。 3 硬件支持 从理论上来说，可以在一个c p u 上同时支持两种指令集。但是将两种 体系结构集成在一块芯片上需要大量硬件资源，与通过软件解决指令集兼容 问题相比代价要大得多。但是也有一些通过硬件解决指令集兼容问题的例 子。 h t e lx 8 6 体系8 0 3 8 6 以后的c p u 同时支持实模式和保护模式两种不同 的体系结构。实模式寻址采用和8 0 8 6 相同的1 6 位段和偏移量，最大寻址空 间1 m b ，最大分段6 4 k b ，在某一时刻只能运行单任务。保护模式寻址采用 3 2 位段和偏移量，最大寻址空间4 g b ，最大分段4 g b ，可以支持多任务、 虚拟内存和特权级。可以通过设置系统寄存器c r 0 的p e 位选择使用保护模 式和实模式，进行两种指令集之间的切换1 4 3 】。 1 9 9 2 年，m m 的研究人员提出了一种能够使c i s c 程序迁移到更高性能 平台上的体系结构框架。这种体系结构框架同时支持两种指令集，能够在两 种指令集之间无缝切换。它的工作原理是这样的( 以c i s c 和r i s c 两种指 令集为例) ：先通过r i s c 指令集的翻译软件将c i s c 指令集程序a 静态翻译 成r i s c 指令集程序b ，并且得到相关信息c ，因为不是所有的c i s c 指令都 4 北京工商大学硕士学位论文 能翻译成r i s c 指令，如s m c 指令。然后执行b 程序，遇到无法处理的指 令时，c p u 会从r i s c 模式切换到c i s c 模式，然后利用相关信息c 执行相 应的c i s c 指令，执行完后再返回到r i s c 模式执行1 3 2 】。， 通过软硬件结合的方式解决指令集兼容问题为体系结构设计者提供了 新的思路，但是这种方式需要很大的硬件资源开销，故很少有可以商用的产 品。 4 j a v a 虚拟机 j a v a 语言的一个非常重要的特点就是平台无关性。j a v a 虚拟机是实现这 一特点的关键。j a v a 虚拟机有自己定义的虚拟的硬件，如处理器、堆栈、寄 存器等，还具有相应的指令系统，在实际执行时通过j a v a 虚拟机将j a v a 指 令解释成本地指令执行，从而实现平台无关性【3 3 】【卅【3 5 1 。j a v a 程序的执行因 为要经历从源程序到j a v a 中间码再到本地指令两个过程，速度有很大损失， 因此也需要使用代码缓存重复使用翻译过的代码，提高系统的执行速度。 1 1 2 程序的执行速度阿题 编译器在产生二进制代码时，因为是静态编译，得不到程序运行时的信息， 故不能针对程序的执行特性进行相关优化。动态二进制优化技术则充分利用程序 运行时的各种统计信息，采用消除冗余代码、循环展开、分支预测等技术优化二 进制代码，以加快程序的执行速度【1 6 1 1 1 7 】【1 8 l 【1 9 】【2 0 1 1 2 1 l 【2 2 1 。动态二进制优化系统是在 运行时优化二进制代码，因此也必须使用代码缓存重复使用优化过的代码，以提 高系统的执行速度。 d y n a m o 是h ph e w l e t t p a c k a r d 实验室开发的针对p a - r i s c 程序的二进制优 化系统，平均加速比在7 左右，能在软件开发商不参与的情况下透明地提高程 序的运行速度，充分发挥机器的性能【1 8 】1 1 9 1 。d y n a m or i o 是d y n a m o 的x 8 6 版本， 能对x 8 6 程序进行动态优化。m o j o 是m i c r o s o f t 开发的针对x 8 6 程序的二进制 优化系统，支持多线程和动态链接库【2 0 1 。 为了解决指令集兼容问题和提高程序的执行速度，研究人员开发了上述各种 各样的系统，但是，性能问题仍然制约着上述系统的应用和推广。因为运行上述 系统需要复杂的翻译或者优化工作，比直接执行二进制代码在速度上有很大损 5 一种两级代码缓存框架设计与测评 失。为了开发出在市场上具有竞争力的产品，必须将各种翻译和优化系统的开销 降低到一定水平，提高系统的运行速度。 目前，提高这些系统性能的一种重要技术是代码缓存技术f 3 6 j 【3 7 1 【3 8 j 【3 9 】。代 码缓存技术是指在内存中开辟一块专门的区域，用于缓存翻译过的或者优化过的 代码，因为根据程序的局部性原理，这些代码很可能会被再次执行，这样再次执 行这些代码时，可以从代码缓存中得到已经翻译过的或者优化过的代码直接执 行，减少了重新翻译或者优化的代价。代码缓存管理是上述系统设计的关键环节 之一，对系统的性能有着重要影响。 本文以程序的局部性原理为指导，通过设计高效的代码缓存来提高系统的运 行速度，重点研究代码缓存索引存储结构和热点替换算法。 1 2 本文主要贡献与创新点 本文的研究内容及主要贡献有以下四点： 1 提出了新的两级代码缓存框架的索引和存储方法( g c c f - u i ， g e n e r a t i o n a lc o d ec a c h ef r a m e w o r k u n i t e di n d e x i n g ) 。原来的两级 代码缓存框架( g c c f ，g e n e r a t i o n a lc o d ec a c h ef r a m e w o r k ) 将整个代 码缓存空间分成不连续的三部分，替换一个热点需修改两个索引表，并 在内存中移动热点两次。本文采统一索引的方法，将热点属于哪一级与 热点的存储位置分离，消除了替换热点时内存移动的开销，并减少了查 找索引表的开销。实验表明，g c c f - u i 框架查找索引表和替换热点的时 间比g c c f 框架平均减少了9 0 7 。 2 实现了一个代码缓存性能评测模拟器，用于评测代码缓存管理框架使用 各种替换算法( f i f o 、l f u 、l r u ) 时的性能； 3 评测了g c c f - u i 框架分别采用f i f o 、l f u 、l r u 替换算法时的性能，发 现g c c f - u i 框架两级都采用f i f o 替换算法时性能最好； 4 将g c c f - u i 与单级代码缓存框架性能进行了比较。在相同条件下， g c c f - u i 框架的热点命中率明显高于单级代码缓存框架。 6 北京工商大学硕士学位论文 1 3 论文结构 第1 章概述了本文的研究背景、主要工作和创新点；第2 章对代码缓存管理 进行了综述；第3 章详细介绍了新的两级代码缓存框架设计和性能评测；第4 章简要介绍了代码缓存性能测评指标和测评方案；第5 章详细介绍了代码缓存性 能测评模拟器的设计和实现；第6 章详细讨论了代码缓存性能测评结果；第7 章对本文工作进行了总结，并对代码缓存管理进行了展望。 7 一种两级代码缓存框架设计与测评 第2 章代码缓存管理综述 目前，提高跨指令集虚拟机系统、动态二进制翻译系统和动态二进制优化系 统性能的两种重要技术就是采用动态翻译技术【1 2 1 1 1 3 1 1 1 4 】【1 5 l 和动态优化技术 1 1 6 1 1 1 7 】1 1 8 】1 1 9 1 【驯【2 1 】【勿。动态翻译技术即把原指令先翻译成本地指令，存放到代码缓 存中，然后执行这些翻译过后的本地指令，从而加快程序的执行速度。动态优化 技术则是把原来的二进制指令先进行优化，然后存放到代码缓存中，再执行这些 优化过后的二进制指令，从而加快程序的执行速度。由此产生了一个新的研究领 域代码缓存管理i 蚓【3 7 l i 粥1 1 3 9 1 1 4 0 1 。 2 1 代码缓存管理的研究背景与现状 提高跨指令集虚拟机系统、动态二进制翻译系统和动态二进制优化系统性能 的两种重要技术就是采用动态翻译技术和动态优化技术。这些翻译后或优化过的 指令会被放到一块代码缓存中，因为根据程序的局部性原理，这些指令很可能会 被再次执行。如果这些指令被再次执行，则直接执行已经存放在代码缓存中的已 经翻译好或优化过的指令即可j 这样就可以避免重复翻译或优化这些指令的代 价，从而加快程序的执行速度。 图2 - 1代码缓存在跨指令集虚拟机系统、动态二进制翻译、动态二进制优化系统中的地位 由图2 - 1 可见，代码缓存管理在跨指令集虚拟机系统、动态二进制翻译系统 和动态二进制优化系统中起着重要作用。因为有效的代码缓存设计有利于减少热 8 北京工商大学硕士学位论文 点重复翻译和优化的代价，加快程序的执行速度，因此，如何设计一个有效的代 码缓存管理系统，便成为上述系统设计的一个关键的问题。 但是这个研究点长期没有得到研究人员的重视。因为在2 0 0 2 年之前，研究 人员大都采用s p e c 4 1 l 测试程序作为测试样本，得出了代码缓存管理在跨指令集 虚拟机系统、动态二进制翻译系统和动态二进制优化系统设计中并不是很重要的 观点。因此热点替换算法大都采用全部刷新【1 1 9 】( n s h ) 方法或者无限扩展 代码缓存( u n b o u n d e dc a c h e ) 的方法【2 。 全部刷新方法，即当代码缓存占满时，如果有新的热点加入，就全部刷新整 个代码缓存。或者如果系统检测到程序的执行阶段发生了变化，也可以主动刷新 整个代码缓存。全部刷新方法有效地利用了程序执行的阶段性特征，当一个程序 从一个阶段向下一个阶段过渡时，代码缓存中的代码是陈旧的，因此全部刷新代 码缓存有利于充分利用代码缓存空间。全部刷新方法的好处是代码缓存管理的代 价比较小，但是一个主要缺点是程序执行的阶段性不易分析和预测，刷新整个代 码缓存有可能将将来会用到的有用的热点也替换出去，降低了热点的命中率，影 响了程序的执行速度【嚣】【矧。 无限扩展代码缓存方法，是指代码缓存的大小可以动态调整，根据热点的数 量和大小的增加而增加。这种方法的好处是代码缓存管理简单，不需要替换热点， 热点的命中率比较高，d y n a m or i o 默认采用无限扩展代码缓存的办法m 。但是， 研究发现，因为s p e c2 0 0 0 测试程序都小于5m b ，所以即使采用无限扩展代码 缓存算法，所需的代码缓存大小的平均值仅为7 3 6k b 。但是当采用w i n d o w s 下 大型交互性程序作为测试程序时，热点数量急剧增加，所需要的代码缓存大小也 急剧增大。因为w i n d o w s 程序都有1 0m b 或1 0 0m b 之大，如果采用无限扩展 代码缓存算法，所需的代码缓存大小的平均值1 6 1 3 9k b ，极大地浪费了内存资 源【2 1 l 。 因此如果我们的目标是兼容w i n d o w s 下大型交互性程序，并加快它们的运 行速度时，代码缓存管理就需要深入分析和研究。 代码缓存管理的研究主要包括以下几个方面： 1 替换算法 因为代码缓存空间是有限的，当产生的热点超过代码缓存的容量时，必 9 一种两级代码缓存框架设计与测评 须选择代码缓存中部分或全部热点替换出去。目前主要有l r a ( l e a s t r e c e n t l ya c c e s s e d ) 、l f a ( l e a s tf r e q u e n t l ya c c e s s e d ) 、l r c ( l e a s tr e c e n t l y c r e a t e d ) 、l e ( l a r g e s te l e m e n t ) 、b f e ( b e s tf i te l e m e n t ) 和f l u s h 六种算法。 1 ) l e a s tr e c e n t l ya c c e s s e d 算法 简写为u 认，也就是l r u 算法一最近最少使用算法。当需要替换热 点时，u 认算法选取最近一段时间使用次数最少的热点替换出去，如果空间 还不够，则将该热点随后的热点也替换出去，直到得到一块大小合适的连续 空间。该算法充分利用了热点的时间局部性，但是也会使许多“无辜的热 点受到影响，并且该算法会产生空间碎片。 2 ) l e a s tf r e q u e n t l ya c c e s s e d 算法 简写为l f a ，也就是l f u 算法一最不经常使用算法。当需要替换热 点时，l f a 算法选取访问频率最少的热点替换出去，如果空间还不够，则将 该热点随后的热点替换出去，直到得到一块大小合适的连续空间。该算法也 会使许多“无辜的一热点受到影响，并且该算法对新产生的热点不利，因为 经常会发生新产生的热点还未取得较高的访问次数时就被替换出去了。 3 ) l e a s tr e c e n t l yc r e a t e d 算法 简写为l r c ，也就是f i f o 算法。当需要替换热点时，l r c 算法选取产 生时间最久的那个热点替换出去，如果空间不够，则将该热点随后的热点替 换出去，直到得到一块大小合适的连续空间。该算法避免了空间碎片问题。 4 ) l a r g e s te l e m e n t 算法 简写为l e 。当需要替换热点时，l e 算法选取代码缓存中最大的那个热 点替换出去。该算法有利于减少替换次数，但是没有利用热点的时间局部性， 并且该算法为了快速找到最大的热点，需要维护一个按热点大小排序的线性 序列，增加了代码缓存管理的开销。 5 ) b e s tf i te l e m e n t 算法 简写为b f e 。当需要替换热点时，b f e 算法选取代码缓存中大小最合适 的那个热点替换出去，也即比新热点占用空间大的所有热点中占用空间最少 的那个。该算法也需要维护一个按热点大小排序的线性序列，增加了代码缓 存管理的开销。 6 ) f l u s h 1 0 北京工商人学硬学位论文 该算法将热点从代码缓存的低地址到高地址依次存放，当。个新热点凼 代码缓存大小限制无法存入到代码缓存中去时，就将整个代码缓存中所有的 热点都清空而将新热点作为整个代码缓存的第一个热点。浚算法是一个管 理代价非常小的算法，但是对代码缓存热点命中率有不利的影响，并导致代 码重生率增大。文献 1 8 1 表明，采用f l u s h 算法时，代码重生率的平均值为 6 1 5 。 文献 1 8 1 以s p e c2 0 0 0 为测试程序，测试了单级代码缓存采用各种替换 算法时的性能，得出了l r c 替换算法是在l r a 、l f a 、l r c 、l e 、b f e 和 f l u s h ? 、种算法中最好的替换算法。如图2 - 2 所示。 ：砸 旺到日 围2 - 2 不同代码缓存大小下六种替换算法m is sr a t e 柱状图 由图2 2 可见，在各种代码缓存人小f ，热点命中宰最好的算法是l r c 和l r a 算法，两者都基于时问局部性的。热点命中率域差的是l e 和b f e ， 两者都仅仅考虑热点的大小而没有考虑时问局部性。l r c 、l r a 算法性能相 对较好，但足l r a 算法容易产生空问碎片，而l r c 算法不易产生宅间碎片， 故l r c 算法是一个相对较好的替换算法，也即本文提到的f i f o 算法是单级 代码缓存框架中性能最好的算法。 2 替换粘度 当必须从代鹳缓存中特换出热点时，可以进挥次只替换能够容纳新热 点的内存空问，也可以选择成块地替换出热点，甚至可以刷新整个代码缓存 空旧。文献p s i 对热点臂换粒度进行了深入研究，发现把整个代码缓存空间 平均分成81 6 个单；c ( u n i n 时性能展好。因为此时既能充分利j 目程序的局 一种两级代码缓存框架设计与测评 部性，又能利用程序执行的阶段性特征。如图2 3 所示。 譬 c 0 占 宝 葺 墨 图2 - 3 采用各种替换粒度的相对代价柱状图 3 热点的索引和存储组织结构 良好的热点索引和存储结构有利于提高代码缓存的使用效率，加快程序 的执行速度。 2 0 0 3 年，k i mh a z e l w o o d 在体系结构顶级国际学术会议m i c r o 上发表论文， 第一次使用w i n d o w s 下大型交互性程序( 如w o r d 、e x c e l 等) 作为测试程序， 发现代码缓存管理对动态优化系统的性能有很大的影响。在实验中，k i m h a z e l w o o d 发现了一个重要的统计规律：经常执行的热点分为两类：生命周期 短的( 少于执行时间的2 0 ) 和生命周期长的( 多于执行时间的8 0 ) ，而在 中间的热点则很少。据此，k i mh a z e l w o o d 提出了两级代码缓存框架( g c c f ) ， 将整个的代码缓存分成两级三部分：n u r s e r y 代码缓存、p r o b a t i o n 代码缓存和 p e r s i s t e n t 代码缓存，目的是将生命周期长的热点逐渐转移到p e r s i s t e n t 代码缓 存中去，在n u r s e r y 代码缓存中存储生命周期短的热点( 如图2 4 所示) 。实验 表明，g c c f 框架取得了很好的性能【3 7 1 。 1 2 北京工商大学硕士学位论文 p e r s i s t e n l n u r s e r yc a c h e ? ! 耋曩耋l 氨三 皇i 托霉j ； 图2 - 4 两级代码缓存框架( g c c f ) 示意图 2 2 代码缓存管理存在的问题 目前，关于代码缓存的替换算法和替换粒度已经有了很好的研究成果，以 s p e c 作为测试程序的性能分析工作也做得非常深入和细致。 但是，目前的跨指令集虚拟机系统、动态二进制优化系统和动态二进制优化 系统的应用领域逐渐转向w i n d o w s 下大型交互性程序，因为w i n d o w s 下大型交 互性程序的执行特性与s p e c 很不相同，故代码缓存管理需要针对w i n d o w s 下 大型交互性程序的执行特性进行重新设计。 代码缓存管理目前存在的问题： 1 缺少w i n d o w s 下大型交互性程序的标准测试程序； 2 g c c f 框架存在移动热点次数过多的问题： 3 g c c f 框架存在查找索引表次数过多的问题： 4 g c c f 框架每一级代码缓存中仅使用了f i f o 替换算法，没有测评采用 其他算法如l f u 、l r u 时该框架的性能； 5 g c c f 框架没有将两级代码缓存框架与传统的单级代码缓存框架进行完 整的性能比较。 本文以程序的局部性原理为指导，设计了新的两级代码缓存框架索引和存储 结构，解决上面提到的问题2 和问题3 ，设计并实现了一个代码缓存性能模拟器， 对单级和两级代码缓存进行了详细地性能评测。 种两级代码缓存框架设计与测评 2 3 代码缓存管理的几个基本概念 动态代码翻译技术的翻译是以b l o c k 为单位的。一个b l o c k 是以一条转移指 令的目标地址开始到另一条转移指令结束的段指令。这些以b l o c k 为单位的翻 译代码就存储在代码缓存中。 但是，研究发现，有些b l o c k 之问的执行顺序足同定的，如图2 - 5 ： 图2 - 5 执行肠序固定的b l o c k 组成热点 这样就可以把这些执行顺序固定的b l o c k 组合成个热点o m c e ) ，从而省 去了执行完每个b l o c k 后都要查索引表的代价。 为了查找这些热点，需要为每个热点建立索引信息，这些索引信息存放在热 点索引表中。如图2 - 6 所示： 索引表代码缓存 索引键值索引指针 褰 热点4键值1指针1 执自7 键值2指针2 热点1 键值3指针3 键值4指针4 热点3 键值5指针5 热点8 键值6指针6 热点9 键值n指针n 图26 代码缓存结构图 咀后每次执行一条转移指令时，都会到索引表中查找浚转移指令的目标地 址，如果该目标地址对应的键值在索引表中，则根据索引指针找到柏应热点执行。 虚拟机指令的执行流程如图2 7 所不： 北京工商大学硕士学位论文 图2 7 虚拟机指令执行流程图 图2 7 中h t d t ( h o tt r a c ed e s c r i p t o rt a b l e ) 是热点索引表，用于记录待执行 的指令和翻译好的本地指令之间的映射关系信息，它被用来将待执行指令的 s p c ( s o u r c ep r o g r a mc o u n t e r ) 转换成对应的t p c ( t a r g e tp r o g r a mc o u n t e r ) ，如果 s p c 对应一个已经被翻译的热点的开头，就能在h t d t 中命中。 文献【3 8 】表明，替换如果以u n i t 为单位，能取得很好的性能。一个u n i t 中含有若干个热点。以u n i t 为单位进行替换有利于减少记录统计数据 ( b o o k k e e p i n g ) 的代价。 2 4 小结 本章对代码缓存管理进行了综述，简要介绍了代码缓存管理的研究背景和现 状，详细介绍了几种常用的热点替换算法，并阐述了代码缓存管理的几个基本概 念。 一种两级代码缓存框架设计与测评 第3 章新的两级代码缓存框架( g c c f - ui ) 设计 本章从分析w i n d o w s 下大型交互性程序执行特性入手，提出了一种新的两 级代码缓存框架索引和存储方法，设计了新