（计算机系统结构专业论文）一种适用于mips指令系统的分支预测方法.pdf

干l i j 遗j hj 。m i p s 指令系统的分芷顺测玎以、：论卫摘唼 论文摘要 本文基0 二对近年米国内外分支预测方法的分析，提出了一种剀实适用于 m h 指令系统的混合分支颅测方案。 小文提出的混合预测方案由永远预测分支成功转移的预测方案和作者提出 的( ；一s h a r e 改进型分支预测方案共同组成。伪了简化预测器的复杂度，充分利 用了指令分类的思想，针对m i p s 指令集中的l ik e l y 类分支指令和其他分支指令 分别采取不i 亓j 的预测方法进行处理。对于l jk e ly 类指令，选用永远预测分支成 助转移的预测方案；而刈r 非l ik e ly 类指令，! j ! 【j 采用( ；s h a r e 改进型方案进行 分支预测。) 一， 本文提出的g s h a r e 改进型分支预测方案与经典g s h a r e 方案相比，引入 操作系统的状态位信息来取代分支历史的一部分，与全局历史记录。起参与进行 分支预测。对于l i n u x 操作系统而言，作者采用的是程序计数器p c 地址的最高 位地址p c 3 l 。通过在支持m f p s 指令系统的芯片模拟器上+ 进行的模拟发现，在真 实的操作系统中，g s h a r e 改进方案在同等的硬件复杂度下，和g s h a r e 方案 分支预测的命中率相比总体有所提高。同时，由于g s h a r e 改进方案利用了操 作系统提供的有效信息，因此和同复杂度的g s h a r e 方案相比，少需要位的 历史记录。 天键词：分支预测，混合j ：5 l 洲，全局历史掀洲 种适川jm i p s 指令系统的，盘】j 6 1 删7 j 泣a b s t c a c t ab r a n c hp r e d i c t i o ns c h e m e d e s i g n e df o r m i p si n s t r u c t i o ns e t f e n gl e i ( c o m p u t e ra r c h i t e c t u r e ) d i r e c t e db y t a n g z h i m i n f h r o u g ha n a l y z i n gt h em e t h o d so fb r a n c hp r e d i c t i o np r o p o s e dl n r e c e n ty e a r s 1 b r i n g f o r w a r da h y b r i d b r a n c h p r e d i c t i o n s c h e m ew h i c h a d a p t s w e l lt om i p s i n s t r u c t i o ns e t t h i s h y b r i d b r a n c h p r e d i c t i o n s c h e m ei sm a d eu po ft w o s i n g l ep r e d i c t i o n m e t h o d s o n ei st h em e t h o dw h i c hp r e d i c t st h eb r a n c hi sa l w a y st r u e ，t h eo t h e ri st h e m e t h o dn a m e di m p r o v e dg s h a r e t o s i m p l i f y t h e c o m p l e x i t yo ft h es c h e m e ，i c l a s s i f yt h em 1 p sb r a n c hi n s t r u c t i o n si n t ot w oc a t e g o r i e s ，n a m e l yl i k e l yi n s t r u c t i o n s a n dn o n e l i k e l yi n s t r u c t i o n s 1u s et h ef i r s tm e t h o dt op r e d i c tt h el i k e l yi n s t r u c t i o n s a n dt h es e c o n dt op r e d i c to t h e r s t h ei m p r o v e dg s h a r es c h e m ei s p r o p o s e db yt h ea u t h o rf r o mg - s h a r es c h e m e t h en e wm e t h o dt a k e ss o m eb i t sw h i c hr e f l e c tt h ei n f o r m a t i o no ft h e o p e r a t i n g s y s t e m t os u b s t i t u t es o m e p a r to f t h eb r a n c hh i s t o r yr e c o r d sw i t ht h e s eb i t sa n ds o m e o t h e rp a n so f g l o b a lh i s t o r yr e c o r d s ，i tc a np r e d i c tt h eb e h a v i o ro fb r a n c hi n s t r u c t i o n s l i k ew h a tg s h a r es c h e m ed o e si n l i n u x ，it a k et h eh i g h e s tb i to fp c ( p r o g r a m c o u n t e r ) ，p c 31 ，t op u ti ti n t or e a l i t y a f t e rs i m u l a t i o n so nt h ecs i m u l a t o r ，w ef i n dt h e n e wm e t h o dh a sb e t t e rp e r f o r m a n c et h a ng s h a r ei f lt h es a m eh a r d w a r ec o m p l e x i t y t a k i n gu s eo f t h ee f f e c t i v ei n f o r m a t i o np r o v i d e db yt h eo s ，t h eb r a n c hh i s t o r yr e c o r d o ft h ei m p r o v e dg s h a r es c h e m en e e d so n eb i tl e s st h a nt h a ti nt h e o r i g i n a lm e t h o d k e y w o r d s ：b r a n c hp r e d i c t i o n ，h y b r i db r a n c hp r e d i c t i o n ，g l o b a lh i s t o r yp r e d i c t i o n 独创性声明 本人声明我所呈交的论文是我个人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论义 l ，1 i 包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对木 义所做的任何贡献均已在论文中作了明确的说明并表卅了谢意。 作者签名： 握彬 日期：秒。r b 关于论文使用授权的说明 巾幽科学院计算技术研究所有杖保留送交论文的复印件，允许论文被 查阅和借阅：并町以公布沦文的全部或部分内容，可以采用影印、缩印或 j c 它复制手段保存该论文。 化行虢讼侈繇澎办h 剃：矽”叫 第一章分支转移预测技术的现状 仃系统中，分支 ：往是山程序中的循环引起的。而要处理分支，就需要 定的时m j l ：销，当处理器的性能1 i 太高时，分支处理对系统的影响可能迩4 i 是很 明盟。但随着对处理器性能要求的越来越高，处理器的设计越来越复杂，流水线 深度越来越深，这种影响也就变得越来越丈，甚至成为制约系统性能的瓶颈。如 何使得分支处理对系统性能的影响尽可能的小，就变得格外重要。对分支进行猜 测执行无疑是个比较好的办法，如果分支猜测执行的准确度能够做到足够高， 对于系统性能的提高是大有益处的。因此，从上个世纪8 0 年代开始，分支预测 技术就逐渐成为体系结构方面专家研究的热点问题之一。 1 1 分支预测的基本原理 在应用程序中，分支转移很多，而且也很复杂，但是我们还是可以从中找 到规律，发现些有针对性的预测策略，从而提高系统的性能。 在一些多重循环比较常见的应用程序中，我们会发现：在多重循环罩，分支 转移总是有很强的偏向性，也就是况分支总是经过多次同向的执行，才会偶尔转 向另外一个方向，然后很快又会转回到原来方向。因此我们就可以采用两位：进 制计数器，来记录分支所处的状态，直到分支连续出现两次预测失误时才改变分 支的预测方向。关于两位计数器的状态机洋见图l 。 跳# - 跳转 图17 - q 位计数器状念机 不跳转 ：黧璧登芝! ! ! i 煎室薹篓娄曼生量窭蛭翟邑 这秘瑟谴鼷濒方法，对子上述磷缀强德匈性麴分支，不论怒镳向蹴转、成偏 两一i 麟转鹩，都寄撼封鹣散黎，强会导数镤尔熬预潮键谟。在实际的程序中，授 多溺镶环砉器能产躐毳锻灌魏国馈鹊分支，铡如下馥的校序段： 幽( a ) h n i 】( a ( 鍪 在趣净羧中，当蠹溪环执行时，分支语訇蘑楚舅8 转嫩功，囊到罐耀姥寒。 出予外辍环数狡行，国疆环黪薅攻被巍罩亍。这对强鬃慕爨只翁位的谢。数器，则 l 蟊j 二静次懿转失液，强就裁会凝凝此次分支为不蹴转，扶嚣产生预测错误。如 禁采臻簿谶鼹经魄秘二逡麓诗数嚣计数，数然技态机出1 1 变为l o ，但仍然判断 分支搿转，预测滚然楚正确数。 还有，我们帮躲邋，纛序褒撬行过程中憝青局部健原瑗的。也就砖说，从时 阕上谫，蠲戳执嚣遮筑伐礤，往往会狠姨渡饕赣弧行。瓿空间上讲，溺褥瓶行进 瓣代秘煎嘏邻代鹳锭菠 夔会被缀妖撬符。围髋嫩避的分支静历受貉鬃，对于将爱 遽行鹣分支走穗，往往罴寄潜在影嫡懿。针对这两种不黼的褥部程愿溅，就产查 了葶垂掰革个分支翁历史话录寒鞭溅分支瓣鲻帮预测滚，氍巅麓竣避遴魏篱全筠分 支绥浆溪溺戆全援羧浏方法。这蕊张慰憋实簿生靛蹩f 瓣要贪爨鼹涎绥农遥瘟崽 錾艇掰摹孛黪镪。 其实分支恣畜臻多其链憝将点，院皴：缓多分支掰辫癸比较熬缨裂 主筑楚 个不变，舅令以潮定麓d e l t a 蕊发生变饨。裂燃这蛰点，鼓霹以搜用分支 静续聚逡来焱溺下一次分支靛方囱【 3 。 扶f 一节 ：始，穆洋镪分缨分支鞭测黝方法浆发嶷趋势黝些骢型方法的提 出缀潮鞭具体惑懋。 2 分支颈溺菠零麓发蒺趋势 分支联测授术疆早窿凌在8 0 每代韧，耳始时主要巢搿静态颈滚方法。所；辫 熊静态颡渊蠢法藏怒嚣先矮过对程序的，次葚至多次扫描，褥整呵耩搿盼信 感然艨铡嬲这冀端感髂为颥瓣黪蔽攒，封程葶中懿分支趱 j ：壤测，这释疗法黪 釉点楚：由1 尹捌鞭缪巍撬 亍之藩藏童篷行了分援，毽梵颈灏鹋准撩率选较赢。怒跫 l 二破翟葶羧 亍之潦餮述铃颈搬撩+ 因此效率l 芝袋慑。所以透常甭传为单独鹩分 第一章分支4 侈颅跳技术的蚍状 支颅测办法进行使用。 i i 赴于静态预测方法的效率比较低，【天】此从8 0 年代中期”始，动态颅测 力法的训究就逐渐为人们所重视。 较t ，提出的比较简单实用的动态预测方法是采用单层i 进制计i 数器进行分 支坝测，i - 要冉两位状态l l 和多位状念机的预测方法。但足配用比较广泛的还是 心何状态机方法。两位状态机方法实际上是针对多蕈循环提出的，针对多重循环 ； ，的转移通常具有很强的偏向性，偶尔。次的分支方向改变，并小意i 味着分支的 偏向发生变化。因此这种方法对于多重循环具有不错的效果，但是从刘整个程序 的预测结果来看，还是远远不能让人满意的。 进入卜世纪九十年代，随着对计算机性能要求的不断提高，分支预测成功 牢的，蜀低，越来越成为影响系统性能的瓶颈之+ 。而尢论是静态预测方法还是丽 位状念机方法虽然有各自的优点，但是也有着明显的不足。因此，世界上众多系 统结构方面的专家认识到研究高效准确的分支预测方法的重要性，j r 始动手研究 各种高性能的预测方法。其中很多思想都源自1 9 9 1 年t s e y u 、，e h 和y a l en p a t t 教授提出的两层自适应思想，包括g s h a r e ，b i m o d e y a g s 等等。 随着对分支预测准确率要求的迸。步提高，预测机制也逐渐的复杂起来，月 始慢慢偏向于充分利用静态和动态方法各自的优点进行混合预测，不过这类方法 对编译和预处理要求比较高，阗此准确率很高，但效率稍低。 1 3 最近十年来国外科学家的一些研究成果 1 9 9 1 年密歇根大学的t s e y u y e h 和y a l e n p a r t 教授提出了两层自适应动念分 支预测( t w o l e v e la d a p t i v et r a i n i n gb r a n c hp r e d i c t i o n ) 思想，丌创了非简单? 值动念预测的先河 1 3 【1 4 j 【1 5 。他们的t 要思想是：动态的将程序。 j 执行过的 分支的结果记录到分支历史记录表中，琏r 分支历史记录对当前的分支进行预 测，分支历史 己录表在程序执j 亍的过程中动态的修改。所谓两层是指在这种预测 器t 。，有历个记求表， 一个是分支历史记录表( b h t ) ，一个是分支模式记录表 ( b p t ) 。当遇到新的分支需要进i j 预测时，首先通过食寻分支历史i 已录表蛮h j “10 u 转移棚匹配的分支模式，然后通过杏、7 分支模工表刘当前指令进行预测。 从9 0 年代初到现以! ，多数转移预测方法都是以此为琏础的。 1 9 9 1 年t s e y uy e h 和y a l en p a r t 提出这利思想的u 候，提出的控制分支模 农修改的- f i 动机非常复杂，f 司叫也彳i 女，实现，阕此1 9 9 2 年他们分析了川t 和 f lf n 各种组合方j ( b h t 和b p t f 一绀i t ! ；j 构分别可以是企曲的( g ) 。也就足所 仃的分支公川个农：组棚迮的( s ) ，也就址桀 炎分支公n 个辰项；i l l4 受棚 连的( p ) ，i ! j 何个分艾1 2 1 已4 j i t 个7 is ) j ! 。b i i t 和b p t 符采川这一种连垃力。， ：塑盟型堕爨燮童塑篓是一一 耋銎黧篓塞憾嚣麓翼三嚣塞篱嚣熹翥箍0 絮蠢鬟羹杰熬窖嚣霎 燃煮煞墨篓黧茎罢纛篓薯鬈翼鬻! 景黧淼茹丢： 篓慧慧挈薯挲焉鬟黧釜。豢纛裔篡蒜f 渺”“ 这丸转 键合之中。对予一般程黟耨茸，攮一鞭小锚酬j n 擞避。 龇a l p a # 巷b t 碡 p a 协m 婚s 抽半 # 静谴 f g p h t i 8 0 缸赫产“e m h 蝌o “t 抽沁 g p h ? ? 躐2 i s e 。掩y e h 秘y a l e n 。p a t t 提出敬缀合方式串熬三携g a g ，g a p 鞍p a g 虽然在两争y 酞黎y a l en p a r t 撬璧l 嚣g 斡缀台孛，毽a p 靛分支控躐敲鬃 羧好，瞧对予程穿戈其楚大浚褪乎藤交，幽予b h t 是骞令，瓣鼗对予不黪翁分 支缀西缒会遇到稳越豹历史滋录，霆憩翻转移的实鞲方囱帮截然秘反，露薅造域 不裔中靛翅热，胰藤瓣低g a p 蕊预测成功翠。遗魏，魏褥蜮少这秘不瓣转移之 潮煞滚命中，搜继稍瑟避穗 嚣l 匏历交记录# i 虿戳区分露袈，麓戏为娶终斑熬蒙襄 滴题。 1 9 9 3 年s c o t tm cf a d i n g 针对这难题瓣出了蔫名鳇g - - s h a r e 方案f 9 3 ( 全 稼为g l o b a l h i s t o r y w i t h i n d e x s h a r i n g ，谨览鲻3 ) ，该艿禁设历寒鹩潢多c p u 瓒 采鲻，贼为碟零预瓣器逑行分支预 ； 经典宵察。纯稠分支指令的地址作为区分 不鬻分支瓣委簧瓣豢，将n 蕴憋礁的高m 像! j _ | ：7 j 史记录表的1 1 1 位辫或，然：= ；弭t 与剩f 滟m n 经愁楚：拱或藩瓣n 镪遗璇去镬b p t 。b p t 采糟的是标准的两位状 态辘褛遂，程f 一嚣，酶其j 枣= 鼹g - - s h a r e 矗豢避行奔绍。嵌践酲 j j ，肘r 段 第一帝分盘转移f 5 l 洲拙术的现状 的j 、vj h ，这种预测器得到的结果已经l 】j 以令人满意了。为了进一步提高预测成功 ：红，s c o t t m cf a r l i n g 提出了一种崭新的预1 1 思想，将小嗣的预测器组合起束，利 川他们不同的特 ，共同进行转移预测，这种思想后米被称为混合预测( h y b r i d p r e d i c t i o n ) 。实际j ： j 面看到的各种j | i ! 测器钉很多都是槿于混合预测器的范畴。 图3g s h a r e 转移预测方案示意图 从1 9 9 4 年丌始，基于两层自适应动态分支预测的混合仿真模型层出不穷， 但山r 他们大多数是通过对特定程序的分析 1 6 ，选择预测器来提高命中率，而 且大多结构复杂，只是为了研究而提出的，因此刑实际的应用作用并不大。下面 将介绍几个比较有影响的预测器。 1 9 9 4 年，p o y u n gc h a n g 等提出了通过刈分支指令进行分炎，米提高分支预 测命中率的方法 1 。他们将指令通过程序测试进行分析，将指令分成易j ：预测 的和不易预测的两大类，用一个比较简单的预测器对于比较容易预测的分支进行 预测，同时对f f i 妤预测的分支用复杂的于贞测器进行予贞测，由于这利- 方法具自+ 针 对程序的特点，斟而， ：不太实用。但是这种思想，对作者设计的分支预测器还足 起了 定的帮助作用，作者就是通过一种分类思想，实现了控制复杂度的控制。 1 9 9 5 年p oy u n gc h a n g 等提h 了比较。典用的混合型分支预测器 2 ，用嘶种 双层自适应动态分支预测器来共同实现分支预测，通过两个阴位汁数器进行 数，需要预测的时候采刖计数器值大的用i 刈应的转移琐测器的结果进行坝测，川 时也求没有选p 的预测器的分支预测方向，如粜两个i i 数器的值川川则选择原水 的颅测器不变。如果分支颅测足成功的i l ( ，! ! | | 叫数器加1 ，f r 则4 成1 ，加剑最多 为：j 减剑坡小为0 。这种力法的 体实现汁见蚓4 。山j ：采川了两j 。；f j 辽越坝 ：丝业些竖丝堕丝型堕鲨 测器作为基础，因此混合预测器是较易实现的，l 叫时由：产采用了两个颅测器，使 得命中率也有一一定的提高。但是它所付出的代价就是控制的硬件逻辑要比原来多 倍片有，控制复杂度也大大增加，冈此需要慎重考虑。不过这j 少l 绎是 种、m i f 内混合预测器了。 t ； i n d e x 7 b r a n c hh b 【0 r yt b l e 图41 9 9 5 年p o y u n gc h a n g 的混合型转移预测器 1 9 9 6 年p o y u n gc h a n g 等为了减少上面提出的混合转移预测器的硬件丌销， 提出一种新的方法 5 ，不再利用两个双层自适应动态转移预测器进行混合预测， 而是采用一个简单的分支预测器负责捕捉那些比较容易预测的转移，而对于不太 好预测的转移，采用两层自适应动态分支预测器来进行预测。当采用简单的转移 预测器进行预测时，两层分支预测器中的p h t 不进行任何修改。这是一种更易于 实用，同时命中率很高逻辑消耗较少的方法，因此我认为采用这种思想同时进 行一些变化，就可以应用到我们支持m i p s 指令系统的模拟器中。简单的分支预 测器兀丁以采用永远预测分支是成功的方法，同时复杂的预测器可以采用g s h a r e 思想。这样的命中率会比g s h a r e 提高不少，但逻辑上要稍稍复杂一些。 1 9 9 7 年c h i h c h i e hl e e 等提出了b i m o d e 预测器 1 0 ，这是对混合分支预 测器又一改良，目的是为了进一步提高分支预测的命中率，结构详见图5 。 b j m o d e 预测器在普通的混合分支预测器的基础上加入了一个小的c a c h e ，这个 o a c h e 用来记录当前转移最近应用了哪个预测器，由于对预测器的选择，达到了 针列每条分支指令的程度，因此命中率又有所提高。但是增加c a c h e 本身，僦碟 来了很大的复杂度，比如，c a c h e 的容量应该有多人，究竟陔如何进行c a c h e 替 换等等，因此无论是在控制通路上，还是存硬件逻辑【：都要付出很大的代价。我 认为这种乃+ 法，预测准确牢虽商，f i 【j 14 ：填删。 第争分支转移顺测技术的虮状 p r e d i c t i o n 图5b i ，m o d e 预测器 在同一年e r i c s p a r n g c 等提出了a g r e e p r e d i c to f 1 2 ，他们的思想是， 在指令c a c h e 或分支目的地址缓存( b t b ) 中为每一个分支都加上个偏向位， 偏向位中保存的是这条指令最常见的分支方向。两位计数器不是用来预测分支方 向的，而是用来决定是否按照偏向位来转移的。当分支的实际结果与偏向位t 致 时，计数器加l ，否则减l ，最多加到： ，最小减为0 ，具体结构详见图6 。这种 方法相当于把两个预测器综合起来运用，巧妙的减少了一螳逻辑，但是对所有转 移指令都要增加一个偏向位，控制垌 实现越来会比较复杂。 ：! ! 蓬墨主! i 登鲞妻墨鎏墼竺量塑塑查婆一 秘蛾# 瞬6e r i cs p a m g l c 等挺融瓣a g m e 预灞器 也是在这一年，威额康璧大学的y i a n n a k i ss a z e i d e s 等为了迸一步提商分 支预测的性能，掇出了一种转移预测的新的思路，使用结粜值来送行转移预丽 【i l 。谴将所有基于德的转移预溯器分成了两类，类是计算型的预测嚣，这类 预溅器主要有两种，瓣皇次豹德遴行预测的鬣运值预测法( 1 a s tv a l u e p r e d i c t o r ) ，臻等长蓑德遴行 葵溺豁多长颓溺法 2 ： p h l h iin d e x = ( p c o x o o o 0 0 3 c 0 ) 2 ： ( f f f in d e x ：( o h r e g 0 x o 0 0 0 0 0 0 7 ) 2 4 ) ： f ) h l h jin d e x ：p h t _ h i in d e x 4 g h in d e x ： f j hl j n d e x 2 p h t h jjn d e x p h t 一】o in d e x ： n ：i i ) ( 指与分支控制模块中，有个很关键的部分就是下一拍p c 计数器值的 汁并。这个汁算实际l ：比较复杂，但这也是分支预测和整个系统控制的关键，凶 笙：堂堑旦坚! 堕_ 旦全童! 堑盟二l 垄璺塑竖丑垄 此要比较洋细的解说一下。程序计数器p c 的地址会有以下几种可能出现的情况： , l l n i 常的取指结果也就是p c + 4 表示程序将向着正常的方向进行。 分支转移的地址b r a n c h a d d r ，当猜测分支是成功的时候，p c 中要放的是 b r a n c h a d d r = 当前p c - k o f f s e c 。 例外地址e x c e p t i o n a d d r ，例外地址早面义有很多种情况，可能是真l f 的 例外地址，也可能是与例外一起处理的分支取消的地址。如果是分支取 消的地址的话，若原来预测的是转移，则由c o m m i l b u s 送回来的该指令 的p c + 8 ，若原来分支预测的是不转移，则p c 中就直接写入c o 1 n i l b u s 总线送回的o f f s e t 域的值。 了解了这些，就可以清楚的掌握p c 的取值情况，下面的附图1 5 可以做更好 的谠明。 c o m m i t b u s 图1 5 程序计数器i 】c 地址的形成 一壁擅卫士坚翼! 塑竺墨篓堕笙生堡型查耍+ 一 一 铁籍中，我们可以看出p e 计数器地垃粒打入是由敷擐和分支控制部传控制 的，同时可以穰清楚黪蓿到作者爨设计敬分支颡测方法中，分支预测失败时( 无 论缀来簇测的是转穆也好不转移也罢) ，郡是靼倒外地址一起处理的t 只不过在 腰柬预测成功时选取的是c o m m i t h u s ，v a l u e h + 8 ，而在开始预测分支不转移时 选取e o m m it h u s o f f s e t 的路线。 2 4 2 2 务相关总线与分支预测有关的数据结构 在我所修改的模拟器中，与分支预测柏关的总线主要有i r b u s ，d e c h u s ， c o m m it b u s 三条。 ir b u s 楚联系取指部件和译码部件的总线。在i r b u s 数据缀构中与分支预测 相关的主要有： 8 l t lv a li d ：总线有效位 鼢& p c ：程序诗数器篷 w o r do f f s e t ： f f o f ) i n s ： b i t lb d ： b y t e9 h t i n d e x ： b i t lp r e d i c l i o n ： 其中v a ii d 是总线的有效信号。p c 避程序计擞嚣的值，i n s t 是3 2 位的 f i p s 指令，b d 表示是否延迟槽指令，o f f s e t 表示如果预测失败时的转移修f 地址， p h t in d e x 畦录当前猜测指令的分支索g l ，以便猜测失败时修改分支模式表的定 位。p r e d l e t i o n 表示当前措令猜测执行的分支方向。 d e c b u s 的任务主要是将分支控制信息稻译码部件筲到的译码信息送给处理 核心豁嘏二。与分支颓测有关翡结构主要有： 8 l t lv a li d ： 总线舂效位 b y t e o p ；指令款内邦鹳 8 s r c l ：第源操作数 b f t rs r c 2 ： 第二源操作数 w 0 r d p c w o i do f f s e t b i 1 1 b d ： b y t ep h t j n d e x ： 8 l7 l 、i p r e d i c t io n 笙= 童堡旦! ：丛! 堕塑全墨堕堕尘些塑型互型l 一 i ) e c b u s 主要是将ir b u s 发送过束的p c ，b d to f f s e t ，p h i i n d e x ，p r e d l c t i o n 等棚关信号，l 传到处理核心部件，因此也要增加相应的结构。o p t s r c l ，s r c 2 为泽l - j ，h 果，v a l id 是总线有效位。 c o m m jt b u s 是结果总线，由于分支控制的取消是通过与例外处理类似的方式 实现的，因此与分支控制相关的结构主要包括： b i t lv a l jd ：总线有效位 b y t eo 口：当前指令的操作 b i t le x ：例外位，表示出现分支预测失败或例外 b i t 6e x c o d e ：例外代码 b 】1 、1b d ： b y t ep h t _ i n d e x ： w o r dv a l u e ：结果的低3 2 位 w o r dv a l u eh ：结果的高3 2 位 w o r do f f s e t ： b i t l p r e d i c t i o n ： 当例外位e x 置起，同时e x c o d e 为全l 时，表示当前所处理的分支预测失败。 若此时p r e d i c t i o n 为0 ，o f f s e t 中包含的是所需要恢复的p c 值，若此时 p r e d ic t jo n 为1 v a l u e h 中包含的是所需恢复的p c 值，p h t in d e x 中包含的 是需要调整的分支模式表表项的索引。p r e d i c t j o n 域是指分支的预测方向。 对于其他总线，由于处理核一心部件在处理分支转移指令时，在发射时已经把 他们变成了算术指令执行，因此这些总线的信号在实现分支转移方案时没有受到 任何影响。 ：壁堕旦三竺堡! 堂竺垂竺堕坌生堡型空堑一一一 第三章相关实验结果和数据分析 为了验证作者提出的方案的可行性和f f 确性，以及和模拟器原有预测方法做 性能上的比较，作者特意选定了该模拟器1 2 l 版本作为测试的基础平台，通过 对浚模拟器的改造，在原有的基础上，增加了预测分支是不转移的处理机制，实 现了混合预测模型，以及g - - s h a r e 方法和g s h a r e 改进方法。所有针对分支预 测所做的实验，都是在p c 机上i n d o w s2 0 0 0 操作系统下进行的。通过在w i n d o w s 坏境下运行模拟器i 2 l 版本，测试设计的分支预测机制在应用程序中的成功率 和对系统性能的影响。主要选取的应用程序包括l i n u x 2 4 启动程序以及规模相 对较大的g c c 。 3 1 支持m i p s 指令系统的o p u 模拟器介绍 我所采用的芯片模拟器是以时钟周期作为模拟单位设计而成的c p u 模拟器， 它仿真c p u 在真实环境中运行时的状态。可以记录每个周期内各个寄存器，存储 部件和总线的值和变化情况，很准确的反映c p u 在真实环境中的运行。该模拟器 以c 语言编写，整个假想c p u 的功能完全能由此模拟器模拟。 浚c 模拟器共有两套版本，一套是在l in u x 环境下设计的，另一套是在 w i n d o w s 环境中设计的，依靠串口作为输入输出设备，模拟整个c p u 的运行过程。 我采用的是在w i n d o w s 环境中的版本，版本号为l 2 l 。 我采用的模拟器1 2 l 版本是一个相对而占比较稳定，经过比较完备的测试， 正确系数较大的版本。在分支控制机制方面，仍然采用的是永远猜测分支正确的 分支预测方法，即对所有分支，一律认为其转移是成功的，一旦发现不成功，则 全部取消重来。该版本中没有一j r 始就预测分支不进行转移的部分。 本文的作者就是在这一基础上，对整个分支控制机制进行了改造，实现了遇 到转移指令可以向任意方向预测的机制，并且在其e 实现了整体的混合预测方 案，以及针对m p s 指令系统中非ii k e iy 类指令的g s h a r e 方案和g s h a r e 改进方案。基本完成了分支预测机制的设计，并且在模拟器上通过了g c c 这样的 规模较大的程序的验证。 3 2 实验所选择的分支预测方案 为了测试分支预测机制对转移成功率的影响，我选川了一种主：要的分支预测 方法，可分为两大类。第一类是永远猜测分支转移成功的预测方法，简记为，r ， 笫三章相关实验结果和数捌分析 这是模拟器中现在采用的分支预测方法。咒 类包括两种方法，都是由作者来实 现的。这两种方法采用的部是混合预测的思想，只小过对于非l i k e l y 类指令的预 测方法不同。其中包括标准的g - - s h a r e 分史预测方法和作者设计的g - - s h a r e 改 进方法，简记i g s 方案。 同时，为了测试不司参数设置对分支预测器性能的影响，在g s h a r e 方案 和1 g s 方案中可以根据参数的没定生成不同的试验方案。为了方便起见，我们 将在下面的叙述中使用如下的简记方法，g s h a r e ( x ，y ) 表示分支模式表索引 共有x + y 位，其中全局历史记录选取x 位，剩下的y 位为低位地址( 不包括最 低两位的0 ) 。i g s ( x ，y ) 表示分支模式表索引共x + v + 1 位，其中全局历史记 录选取x 位，操作系统状态位选取l 位，剩卜的y 位为低位地址( 不包括最低两 位的0 ) 。 由于设计从一开始就考虑了实用性的问题，因此采用的测试方案也并不是很 复杂，以最终能够实现为目的。一共有以下几种方案：2 5 6 项模式表的g s h a r e ( 5 ，3 ) 和g - - s i _ a r e ( 4 ，4 ) ，g s h a r e ( 3 ，5 ) ，6 一s h a r e ( 2 ，6 ) 以及1 0 2 4 项模式表的g s h a r e ( 5 ，5 ) ，g s h a r e ( 4 ，6 ) ，g s h a r e ( 3 ，7 ) ，g s h a r e ( 2 ，8 ) 。2 5 6 项模式表的i g s ( 3 ，4 ) ，i g s ( 2 ，5 ) ，i g s ( 1 ，6 ) ，i g s ( 4 ，3 ) ， 1 0 2 4 项的i g s ( 4 ，5 ) ，i g s ( 3 ，6 ) ，i g s ( 2 ，7 ) ，以及现有的方法t 。 需要说明的是，由于g c c 程序规模较大，在进行g c c 性能提升测试时，作者 只选用了自己的设计的i g s ( 3 ，4 ) 版和g s h a r e ( 4 ，4 ) 以及模拟器的标准实现 作了比较。 3 3 测试数据和结果分析 3 3 1 分支预测方法对命中率的影响 为了比较准确的测试得到各种分支预测方法在较大规模程序中的命中率，我 们选取l i n u x 2 4 核心启动程序作为基准测试程序。通过成功启动ijn u x 时的结 果，来评判各种方法的优劣。下面的表l 就是从1in u x 2 4 ( 8 兆虚盘) 腑动榭序 中得到的非l i k e ly 类分支预测成功的数目和命中率结果。 二登垩! ! 主竺堡! 堂竺墨竺竺坌垄堕型互垄一 预测方法 g - s h a r e ( 5 ，3 ) g - s h a r e ( 4 ，4 ) o - s h a r e ( 3 ，5 ) g - s h a r e ( 2 ，6 ) g - s h a r e ( 6 ，4 ) g - s h a r e ( 5 ，5 ) g - s h a r e ( 4 ，6 ) g s “警包掩砧 簿j l 绱耱鹾1 i 蕊( 2 ，8 ； i p , s 锟s $ 梦 l g s ( 5 ，4 ) i 黔1 4 ，i 勘、 嚣隧： 表1 刁i 同分支预测方案在l i n u x 2 4 启动中的结果 猜测分支 总次数 2 2 2 7 0 4 2 2 2 8 0 4 2 2 2 4 5 3 2 2 2 4 7 9 2 2 2 2 3 0 2 2 2 5 6 5 2 2 2 5 2 8 2 2 2 6 2 8 2 2 2 5 3 4 2 2 2 3 0 9 2 2 2 4 5 8 2 2 2 2 3 0 2 2 2 0 7 8 2 2 2 3 1 2 2 2 2 7 0 1 2 2 2 3 1 8 2 2 2 5 5 5 2 2 2 2 9 5 猜测成功 的分支次 数 12 4 3 1 8 1 8 2 4 5 9 1 8 2 1 1 3 1 8 5 8 7 l 1 8 4 2 3 l 1 8 5 9 3 3 1 8 8 1 5 5 1 8 8 6 7 8 1 9 0 1 6 0 1 8 8 3 4 7 1 8 2 0 4 2 1 8 3 5 0 l 1 8 4 8 9 5 1 8 5 7 2 6 1 8 6 5 1 8 1 8 9 3 7 2 1 9 0 4 1 0 1 8 8 3 0 0 猜测失败的 分支次数 9 8 3 8 6 4 0 3 4 5 4 0 3 4 0 3 6 6 0 8 3 7 9 9 9 3 6 6 3 3 3 4 3 7 3 3 3 9 5 0 3 2 3 7 4 3 3 9 6 2 4 0 4 1 6 3 8 7 2 9 3 7 】8 3 3 6 5 8 6 3 6 1 8 3 3 2 9 4 6 3 2 1 4 5 3 2 9 4 6 孽测成功执行周期 警 5 5 8 2 8 1 8 9 8 1 8 7 8 3 5 4 8 2 9 0 8 3 5 4 8 4 5 5 8 4 7 5 8 5 4 5 8 4 7 2 8 1 8 3 8 2 5 7 8 3 2 6 8 3 5 4 8 3 7 5 8 5 1 8 8 5 5 6 8 4 7 0 2 9 3 3 2 6 8 如 2 6 8n 2 6 6 力 2 6 8 妇 2 6 6h 2 6 5 力 2 6 5 力 2 6 4 力 2 6 5 力 2 6 8 万 2 6 7 力 2 6 6 力 2 6 6 力 2 6 6 力 2 6 4 l j 2 6 4 力 2 6 5 力 注：冈为测试结果只精确剑万周期而检测起s h e l l 的结果是以# 的输出为评介点的 内而具体执行周期数有一定的误筹，从而导致猜洲分支总数的统计有一定的误筹。 通过上面的这张表格的数据，我们可以清楚的看到，我们现有模拟器的所 饺用的永远预测为真的方法的命中率只有5 5 庄右，这和我们所知道的在应用 程序中，分支倾向于转移的次数比不转移的次数略高是吻合的。正是由于这一点， 改进我们模拟器的分支控制机制，使他可以自主选择预测执行哪个方向，而不是 总走单一的方向是十分重要和必要的。 从上面的表1 中的数据中我们还可以看到，g s h a r e 方法虽然比较简单，m 是在实际应用中对提高分支预测的命中率效果还是很明显的。h f j 使只是采用简t n 的g s h a r e 方案，命中率都可以比永远预测分支为转移的方案提高2 0 以j j 。 从表中我们还可以看到，对于一般的应用程序而言，并刁i 是地址位选用的越长， 预测效果越好。g - - s h a r e 方案在同等复杂度下，测试中表现的最好的方案并不是 地址位最长的方案，而分别是g - - s h a r e ( 3 ，7 ) 和g - s h a r e ( 3 ，5 ) 。这两午l f 】方 案和其他方案比较起来，地址位比较氏，f l l 还保持了足够的令局历殳f 内信息。这 从 个角度说l 如令岗历史记? r n t 预测巾足f h 一 i ：篮的，j 亡j0 魁扛“1 坝测器舰模f ：够 第二章相关实验结果和数制分析 大的情况下，历史记录是不可或缺的。 从另外一方面看，由于g - - s h a r e 思想本身采用的是全局表和历史记录相异 或的方法，具有一定的不确定性。囚此对于一般程序而言，采用的全局历史记录 艮，命中率不一定会提高。比如，在表中g s h a r e ( 6 ，2 ) 和g s h a r e ( 5 ，3 ) 相比，虽然采用了更多的全局历史记录和p c 的高位地址相异或，但结果并没有 提高，反而下降。这从另一个角度说明对于g - - s h a r e 方案而占，如何配置历史 记录和地址位的比例是很有考究的。这同时也说明全局历史记录的高位，也就是 和当前分支比较远的结果应用到分支的控制中，虽然占用了相应的资源，但并不 一定能够有效提高分支预测的成功率，越远的历史记录对于分支转移的影响会越 小，也就越会失去其作用。正是由于发现了这一点，作者提出了g s h a r e 改进方 案，利用操作系统的中比较明确的信息位取代作用不大的高位历史记录，帮助进 行分支预测。 我们还可以从表中看到，对于经典g - - s h a r e 方法和改进的g s h a r e 方法而 言，f t g t f i 的预测峰值是基本相当的，而且在规模不是很大的情况下，可以发现该 测试程序中，改进g - - s h a r e 的峰值比经典g - - s h a r e 还要高一些。对于这个测试 程序而言，在2 5 6 项的情况下，两者的峰值基本相当，大约为8 3 5 ：在1 0 2 4 项模式表的情况下，峰值命中率最高的是i g s ( 3 ，6 ) ，达到了8 5 5 6 ，这是传统 标准g s h a r e 方法在同样复杂度的情况下任何组合都没有达到的。 采用作者前述思想实现的i g s 方案，在硬件规模不是很大的情况下，在预 测成功率上比同等复杂度的g - - s h a r e 方案预测率的峰值上有一定提高的同时， 在命中率较高的几种情况中，平均性能和g - - s h a r e 方案比起来，相对较好，也 就是况，选用不同的比较接近的i g s 方案，所可能带来的损失比选用不同的g s h a r e 方案要小一些，这一点可以从表l 中发现。对于上述测试程序，在i g s 方案中，无论是2 5 6 项还是1 0 2 4 项方案，处于较高命中率水平的方案比g s h a r e 都要多一些，在2 5 6 项模式下，有3 种i g s 方案命中率在8 2 以上，在1 0 2 4 模 式下，有2 种方案在8 5 以上，而经典g - - s h a r e 方案都只有一种。虽然说改进