（微电子学与固体电子学专业论文）微处理器中分支处理技术的开发与研究.pdf

摘要 摘要 现代微处理器普遍采用流水线、超级流水线、超标量流水线等技术来提高指 令并行度，但指令流中的分支指令往往造成流水线效率损失，影响其性能的发挥。 论文研究内容基于企业研发的一款双核通信处理s o c 芯片中3 2 位嵌入式精简 指令集微处理器，本人在项目中负责此微处理器中流水线优化工作和分支处理单 元的设计。本文所设计的分支处理单元采用了一种分支折叠和分支预测技术并用 的分支处理策略，它能有效解决分支指令给流水线造成的阻塞。分支折叠能够将 部分分支指令在调入指令执行阶段之前清除出指令流水线；基于条件码的静态分 支预测方法有效地利用了体系结构中指令集特点，在实现低分支处理机制复杂度 的同时也能获得较高的分支预测效率。本文在完成了此微处理器中分支处理单元 各模块的设计之后，建立了相关验证环境，仔细编写验证计划和测试程序，进行 了高覆盖率的系统功能验证，逐步检验各个模块功能及系统工作。采用0 1 8u l n 标 准单元库的后端设计即将结束，准备流片，主频达到2 6 6 m h z 。 对研究结果进行了总结表明，所设计的分支处理单元能切实有效地提高微处 理器中流水线效率。 关键词：流水线分支处理分支折叠分支预测 a b s t r a c t i i i a b s t r a c t m o d e m m i c r o p r o c e s s o r sc o m m o n l yu s cp i p e l i n et e c h n o l o g y , s u p e rp i p e l i n e t e c h n o l o g y , a n ds u p e r s c a l a rt e c h n o l o g yt oi m p r o v et h ep a r a l l e l i s mo fi n s t r u c t i o n s e x e c u t i o n b u tt h eb r a n c h e si nt h ei n s t r u c t i o ns t r e a mc a nm a k et h es t a l l si nt h e i n s t r u c t i o np i p e l i n ew h i c hc a nd e c r e a s et h ep e r f o r m a n c eo ft h em i c r o p r o c e s s o r t h i st h e s i sm a i n l yt a l k sa b o u tt h ed e s i g no fa ne m b e d d e dr i s c m i c r o p r o c e s s o rc o r e i nt h ec o r p o r a t i o np r o j e c to fac o m m u n i c a t i o ns o c ih a dt h ec h a n c et op a r t i c i p a t ei n t h eo p t i m i z i n gw o r ko ft h ep i p e l i n ei nt h i sm i c r o p r o c e s s o r m yr e s e a r c hw o r kf o c u s e d o nt h ed e s i g na n dr e s e a r c ho ft h eb r a n c hp r o c e s s i n gu n i tw h i c hi n c l u d e st w o m e c h a n i s m sf o rr e d u c i n gt h ei m p a c to fb r a n c hi n s t r u c t i o n si nt h ed e s i g n e dp i p e l i n e ： b r a n c hf o l d i n ga n db r a n c hp r e d i c t i o n t h eb r a n c hf o l d i n gm e c h a n i s mc a nf o l dc e r t a i n b r a n c h e so u to ft h ei n s t r u c t i o np i p e l i n e s t a t i cb r a n c hp r e d i c t i o nm e c h a n i s mu s et h e c o m p i l e ro ra s s e m b l yl a n g u a g ep r o g r a m m i n gt os e tab i tt ot h ec o n d i t i o n a lb r a n c h i n s t r u c t i o nw h i c hh e l p ss p e c i f yw h e t h e rt h eb r a n c hi sp r e d i c t e dt ob et a k e no rn o tt a k e n t oa c h i e v eh i g hp i p e l i n ee f f i c i e n c yw i t hl o wc o m p l e x i t yo ft h eb r a n c hp r o c e s s i n g m e c h a n i s m s a f t e rt h ep i p e l i n ef i x i n ga n dt h em o d u l e sd e s i g no ft h eb r a n c hp r o c e s s i n g u n i ti nt h em i c r o p r o c e s s o r , t e s tb e n c ha n dv e r i f i c a t i o np l a nw i t hs e v e r a lt e s tp r o c e d u r e s w e r eb u i l tu pf o rt h ep r o c e s s o r c o m p r e h e n s i v ef u n c t i o n a lv e r i f i c a t i o nf o rt h eb r a n c h p r o c e s s i n gu n i tw a sf i n i s h e dt oe n s u r et h ef e a s i b i l i t yo ft h eb r a n c hs t r a t e g i e s t h e b a c k e n dd e s i g no ft h ew h o l e c h i pw i mt h eo 18u mc e l ll i b r a r yw i l lb ef i n i s h e dw i t ht h e s t a r to ft h ew a f e r 姗t h em i c r o p r o c e s s o rw i l lh a v et h ep r o c e s s i n gf i e q u e n c yo f 2 6 6 m h z t h er e s e a r c hr e s u l t si n d i c a t et h a to u rs t r a t e g i e sc a ne f f e c t i v e l yi m p r o v et h ee f f i c i e n c y o ft h ep i p e l i n ei nt h em i c r o p r o c e s s o r k e y w o r d ：p i p e l i n e b r a n c hp r o c e s s i n gb r a n c hf o l d i n gb r a n c hp r e d i c t i o n 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：易叠塑一 日 期：互堕盗! 叠望旦 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印、或其它复制手段保存论文。( 保密论文 在解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签名：星盔至亟 翩躲邈 日期： 第一章绪论 第一章绪论 1 1 课题研究背景 信息化社会的发展对计算机性能要求在不断提高，微处理器的开发技术在不 断进步。为提高指令在处理器中的执行效率，人们不断开发指令的并行性。首先 提出指令处理的流水线( p i p e l i n e ) 结构，使得指令可以在流水线中重叠并行地执行。 一条指令的执行被分割成离散的阶段。相对来说，一条指令并没有占用整个执行 单元资源。如图1 1 ，一条指令a 完成解码后，就从解码阶段( s t a g e 2 ) 退出进入下 一阶段，而下一条指令b 紧接着进入解码阶段，这增加了指令流吞吐量 ( t h r o u g h p u t ) 。例如，一条浮点运算指令在执行阶段通常需要耗费3 个时钟周期 来完成，而使用流水线后在不存在流水线阻塞的情况下能获得每个时钟周期一条 指令的吞吐量。 i s t a g e1 i s t a g e2 i s t a g e3 i i 广 i 广1i 广 l ( ；l o c k 0 i | i n s t r u c t i o n a 一 一 i i j i c l o c k1 ： i i c l o c k 2 i l l c l o c k 3 i l il ： ： 图1 1 指令的流水线处理 现代微处理器在采用流水线结构的基础上，还采用超标量( s u p e r s c a l e ) 结构 或超长指令字( v l i w ) 技术来提高指令发射和执行的并行性 1 】。超标量流水线技术 是一种通过并行执行多条标量指令来提高处理器性能的计算机实现技术；超长指 令字技术采用多个独立的功能部件，将多个操作组合成一条长指令或者将不存在 相关性的操作封装成一条长指令，然后将这条长指令放入指令流，组成长指令的 多个操作同时进入不同的功能部件执行。超标量或超长指令字每个周期发射多条 指令到多个功能部件上执行，从而提高了每个时钟周期执行的指令数 3 0 1 。 不断加深加宽的流水线结构提高了处理器的硬件资源利用率，大大提高了处 2 微处理器中分支处理技术的开发与研究 理器的运行效率。但是系统程序中的指令并不总是顺序执行的，分支指令( b r a n c h ) 的存在使得系统程序的执行方向经常发生改变，这往往存在于程序中的循环过程 中。微处理器在取到一条分支指令时，并不能立即确定该分支指令是否发生转移， 也称之为跳转。只有在该分支指令经过执行后才能知道其是否发生跳转以及发生 跳转的目标地址，因此取指令阶段需要等待分支指令执行结果来开始，可见分支 指令的存在将会造成流水线的停顿，导致流水线断流而造成效益损失。这表明， 一遇到分支指令，整个指令流水线就被打乱一次，稍后才能恢复到正常。显然， 这影响机器的运行速度。统计表明典型的定点程序中平均每六、七条指令中就存 在一条分支转移指令 2 】，这就意味着在两发射结构中每四拍就有一条分支指令。 如果等分支指令的目标地址确定后再进行后面的取指，意味着每取四拍指令就得 等五、六拍甚至更多才能继续后面的取指，按照常用的顺序取指令方式无疑会造 成流水线经常性的停顿、排空，造成处理器性能大大下降。 无条件分支指令对程序执行速度影响很小，而条件分支指令伴随着各种控制 相关和数据相关，对程序执行速度的影响很大。当处理器的性能不太高时，分支 指令对系统的影响可能还不是很明显。但随着人们不断地追求计算机性能的提高， 处理器的设计越来越复杂，流水线越来越深，指令发射宽度越来越大，这种影响 也就变得越来越大，甚至成为制约系统性能的瓶颈。如何使得分支指令对系统性 能的影响尽可能的小，就变得格外重要。我们必须采取相应的分支处理技术来解 决这类问题。 在没有分支处理机制的结构中，必须在流水线完成其译码操作之后暂停流水 线直到分支结果得出后才能确定分支预测的正确方向，所带来的性能损失是很大 的。要减小流水线处理分支所产生的暂停时钟周期数，可以采用两种途径： ( 1 ) 在流水线中尽早判断出分支转移是否成功；( 2 ) 尽早计算出分支转移成功时的程 序计数器( p c ) 值，即分支跳转的目标地址，以快速取得下一条指令，保持流水 线饱和 3 】。目前常用的分支处理技术就是分支预测( b r a n c hp r e d i c t i o n ) ，其一般 分为静态分支预测和动态分支预测。对于前述第一种途径就可以采用分支预测的 方法，取到分支指令就给它一个预测结果，即在分支指令还没有执行之前就预测 其跳转与否，对于分支成功时的p c 值可以根据分支预测的结果或者分支的历史信 息通过相关算法来给出。但是如果预测失误率太大，对系统性能造成的影响也是 很大的，因此，如何采用更有效的方法来预测分支指令的执行结果，将预测失误 率减小是一项很重要的工作。 此外在具体应用中还存在延迟分支( d e l a y e db r a n c h ) 、循环缓冲器( l o o p b u f f e r s ) 、预取分支转移目标( p r e f e t c hb r a n c ht a r g e t ) 、分支折叠( b r a n c hf o l d i n g ) 、 多个指令流( m u l t i p l ei n s t r u c t i o ns t r e a m s ) 等分支处理技术【4 ，它们可以和分支预测 技术一起配合来实现流水线效率的最大化。 第一章绪论 3 1 2 课题研究的主要内容 本课题为一款双核通信处理s o c 芯片中3 2 位嵌入式r i s c 微处理器核心( s 微处 理器) 设计的一部分。课题研究的内容主要为针对s 微处理器流水线的优化制定分 支处理策略，设计实现分支指令处理单元( b r a n c hp r o c e s s i n gu n i t ，b p u ) ，并对 其功能实现进行验证。 分支处理技术的开发研究是b p u 设计的主要工作。首先要按照整个微处理器 的设计要求来确定分支处理策略，项目中我们提出了一种将分支指令折叠技术与 分支预测技术相结合的分支处理策略，负责分支指令在b p u 分支处理部件中的分 配、译码、预测和修改。设计的过程中针对流水线对分支处理策略进行优化，涉 及软硬件等各个方面。 在完成了分支处理单元中各个功能模块的设计之后，项目组自行搭建有针对 性的验证平台，为验证工作制定验证环境，仔细编写测试计划，在提供的仿真器 上，综合相关分支处理策略对设计方案进行全面系统的功能测试验证。 1 3 论文结构 本文重点讲述了s 微处理器中分支处理单元( b p u ) 的设计与验证过程，详细 阐述了其中所使用的分支处理策略和具体实现方法分析，共分为五章： 第一章介绍课题研究背景，课题研究内容，目的和意义以及论文组织结构。 第二章概述各种分支指令处理方法的理论基础和实现原理，让读者对当今计 算机技术中常见的分支指令处理技术特别是分支预测技术有了详细 而全面认识。 第三章讲述工程实践中设计实现的微处理器结构组成及自行制定的流水线 特点；详细阐述了微处理器中分支指令处理部件采用的一种分支折叠 与分支预测相结合的分支处理策略；根据整个微处理器设计要求规划 分支处理单元结构，明确划分功能模块，详细阐述了应对各种分支指 令的分支处理策略的具体实现。 第四章在为系统搭建的验证平台上，仔细编写验证计划和测试程序，在提供 的仿真器上，综合相关分支处理策略对设计方案进行全面系统的功能 测试验证，并得出可行性结论。 第五章对本论文的工作进行了总结，并对未来工作做出展望。 4微处理器中分支处理技术的开发与研究 1 4 论文研究成果与意义 1 4 1 课题研究的主要成果 本文重点研究了r i s c 微处理器中分支折叠与分支预测相结合的分支处理机 制，是当代计算机发展中流水线优化技术的一次尝试。设计实现了包括多个功能 模块的分支处理单元( b p u ) ，有针对地搭建了此处理器分支处理部件的验证环 境，完成了高覆盖率的验证分析和改进优化，最终完成的系统验证测试结果表明s 微处理器中分支处理单元功能和性能参数指标符合设计要求并能正确运行。 1 4 2 课题研究的主要意义 对于我本人来说，这次课题研究是我对计算机科学和微电子集成电路领域的 一次深入的研究实践。通过系统地学习总结国内外相关领域研究成果，有效地在 具体工程实践中实现设计思路，从而实现了科学理论与工程实践相结合，通过研 究实践进一步巩固所学到的理论知识。 以分支指令处理技术为核心的分支处理单元的设计，是整个s 微处理器项目研 发中的关键部分。这次全新的分支处理策略在r i s c 微处理器中的实现，为未来更 高性能的微处理器设计奠定了一定基础。 第二章分支处理技术 5 第二章分支处理技术 在处理器设计中必须采用合理分支处理技术有效地处理指令流水线中的分 支指令以提高其性能。解决分支指令给流水线造成效率损失的分支处理技术有很 多，下面总结分析了几种常见的方案。 2 1 延迟分支 延迟分支( d e l a y e db r a n c h ) 是一种能有效减小微处理器流水线中分支转移指 令造成效益损失的技术。根据分支指令要直到下面一条指令之后才产生影响，即 有两周期的延迟的特点，我们可以利用编译器在其后安排一条有用的指令来替代 仅为延迟的空操作( n o p ) ，就是说原来的n o p 现在可以是有意义的指令。这样当 被分派的指令执行完毕后，分支的目标地址也计算出来了，这样既保持了程序的 原语义，又缩短了指令执行周期。当然为了保证正确性，这些填入的指令必须是 不依赖于这条分支指令的，对于条件分支指令来说，能与之重排交换的指令是没 有数据相关或控制相关，不能修改其条件的指令。这样的话通常允许的延迟周期 只能是一个时钟周期，因为通常很难找到足够多适合的指令来填多于两个以上的 位置。应用方面，延迟分支技术被i b m 8 0 1 所采用 5 】。随着超标量机器的开发，延 迟分支策略较少使用了。原因在于，多条指令需要在延迟槽中执行，会引起几个 指令相关性的问题。 2 2 循环缓冲器 循环缓冲器( l o o pb u f f e r s ) 是流水线取指令阶段维护的一种小但极高速的缓冲 存储器。含有多条最近取来的指令。若一条分支指令即将发生跳转，硬件首先检 查跳转的目标是否在此缓存中，若是，则直接可从缓存取得。循环缓冲器有几点 好处： 1 由于采用了预取，循环缓冲器含有某些排序在当前指令取地址之前的指令， 于是顺序取来的指令都可能被使用而不需要通常的存储器访问时间。 2 若一条分支指令跳转的目标地址恰好在此分支指令之前的少数几个位置 上，则目标已在缓冲器中。这对于相当普遍的i f - t h e n 和i f - t h e n e l s e 语句特别有 6 微处理器中分支处理技术的开发与研究 用。 3 这一策略特别适用于处理程序中的循环和重复，因此命名为循环器。如 果循环缓冲器足够大，足以容纳循环内的所有指令，则这些指令只需要在 第一次循环时从存储器取来，后面的重复过程不需要再取指令。 从原理上讲，循环缓冲器类似于指令c a c h e 。与c a c h e 的不同点在于，循环缓冲 器只保留顺序指令，因而容量小，成本较低。使用循环缓冲器的机器，有c d c 的 一些机器( s t a r l0 0 ，6 6 0 0 ，7 6 0 0 ) 和c ra y _ l 6 】。 2 3 多个指令流 一个简单的流水线之所以蒙受分支指令带来的惩罚，在于它在取下一条指令 时必须做个二选一的选择，而且选择可能是错误的。一个强制的方法是复制流 水线的初始部分，并允许流水线同时取这两条指令，使用两个指令流。这种方法 称为多个指令流( m u l t i p l ei n s t r u c t i o ns t r e a m s ) ，有几个问题： 1 使用多个流水线，会对寄存器和存储器访问有竞争延时； 2 在原先的分支预测判别还没解决之前，可能又有另外的分支指令进入流水 线( 不管是哪一路) ，这样又需要添加指令流。 尽管有这些缺点，这个策略也能有效改善处理器性能。使用两个或者多个指 令流的处理器有i b m 3 7 0 18 6 和i b m 3 0 3 3 机 7 】。 2 4 预取分支转移目标 在识别出一个条件分支指令时，除了取此分支指令之后的指令外，分支跳转 目标地址的指令也同时被取来，即预取分支目标( p r e f c t c hb r a n c ht a r g e t ) 。这个目 标地址的指令被保存直到此分支指令被执行。如果分支转移确实发生，那么此目 标指令已经被取来了。i b m 3 6 1 9 1 使用了这种方法【8 】。 2 5 分支折叠 a t & tc r i s p 处理器是第一种使用分支折叠( b r a n c hf o l d i n g ) 技术来将分支指 令执行时间减为零的 9 】。c 融s p 处理器使用一个指令解码缓存，每一条不跳转指 令都被转化成指令解码缓存中的一行微码。缓存中每一个条目包括指向执行下一 第二章分支处理技术 条微码指令的地址，无条件跳转指令只是简单地被折叠到上一条微码对应的指令 地址。 分支折叠中不跳转指令的清除( r e m o v a lo f f a l l t h r o u g hb r a n c h e s ) ，就是当分支 指令不跳转或者预测为不跳转时用顺序下一条指令直接代替分支指令的方案，分 支直接从指令序列中被清除出流水线。这种技术非常自由，在整个流水线过程中 仿佛分支指令没有出现过。 下面我们重点讨论分支预测技术。 2 6 分支预测 目前微处理器对分支指令的处理普遍采用分支预测的方法，即当分支指令被 取到流水线时就预测其是否发生转移。当分支方向预测正确时，流水线效率没有 损失；而预测错误时，流水线中有多个功能段被浪费，使流水线吞吐率下降百分 比为：d = p q ( k 一1 ) 1 一p q ( k 一1 ) ，其中p 是条件分支指令在程序中所占比例，q 是分支成功率，k 是流水线功能段数。据统计，一般程序中，条件分支指令占2 0 ， 分支成功率为6 0 ，流水线有8 级时，吞吐率将下降4 6 1 0 。因此对分支指令预测 的精度会直接影响到微处理器的性能，如果分支预测执行的准确度能够做到足够 高，对于系统性能的提高是大有益处的。同延迟转移( d e l a y e d b r a n c h ) 策略相比， 分支预测在采用深流水和多发射机制的处理器中优势更加明显。从上个世纪8 0 年 代开始，分支预测技术就逐渐成为体系结构方面专家研究的热点问题之一。 在应用程序中，分支转移很多，而且也很复杂，但是我们还是可以从中找到 规律，发现一些有针对性的预测策略，从而提高系统的性能。分支预测主要是在 深度流水线中，用来预测分支指令的执行路径，以减少指令断流对处理器速度的 影响。我们主要需要预测：分支跳转或者不跳转，如果跳转的话，跳转目标地址 是多少。分支预测方法一般分为两类：静态分支预测的和动态分支预钡l j 1 1 。 2 6 1 静态分支预测 静态分支预测结构比较简单，由于不需要太多的硬件支持，实现起来花费的 代价比较d 、 1 3 】。静态预测通常采用的方法有硬件固定实现的分支预测：预测分支 总是发生跳转不发生跳转( t a k e n n o tt a k e n ) 【1 2 】。 分析程序行为的研究表明，分支指令倾向于发生跳转，分支成功率高于 5 0 4 ，因此预测分支跳转总是发生的方法要比预测分支跳转总是不发生的方法 精度高。一旦分支指令发生跳转，这同时需要预测分支目标地址，以便从分支目 微处理器中分支处理技术的开发与研究 标处取指令。而预测绝不发生跳转的方法则直接顺序取下一条指令。上述两种方 法都要求在预测错误的情况下清除所有在分支指令之后已经执行的指令记录。 预测总是发生跳转的方法有两个明显的缺点：首先，上面说到的，它需要额 外的硬件资源来计算分支目标地址；而且在一个分页的机器中，由分支目标预取 要比顺序路径预取下一条指令更可能造成缺页，旦预测错误，将不需要的指令 调入指令缓存而造成对缓存的占用浪费。 因此，在实际的设计中，预测总是不跳转的方法使用得更为广泛。如果你预 测分支不跳转，那么所取的下一指令可由分支指令顺序下一地址取得，这条指令 一般都与分支指令在同一缓存阵列上，这就减少了缓存的占用浪费。 软件方面可通过编译器优化来实现预测。一种方法就是在分支指令中增加一 位操作码给硬件来预测这条分支跳转还是不跳转。编译器可以在编译程序时根据 收集的信息对这一位操作码进行设置，依据分支指令的操作码进行判定，对某些 条件分支指令的操作码将总是发生分支，对另外的总是不发牛 2 5 。这种预测结构 是在对源代码进行编译之前或之中来决定分支预测的方向。这种静态分支预测的 方法使用了在编译过程中编译器用到的信息。编译器可能利用的信息有以下三种： 指示程序设计者嵌入的信息，明确告诉编译器做什么；基于程序结构的启发式信 息 2 9 】；从程序的轨迹获得的轮廓信息。此外还有根据程序制导信息、剖视文件 ( p r o f i l e ) 、程序结构获取分支偏向性进行预钡l j 1 4 】。 静态分支预测实现起来比较方便，功耗也小，主要是因为静态分支预测不必 增加硬件结构，但是这种预测方式的预测精度比较低，而且对不同的程序及不同 的输入数据集，它的预测失效率变化很大。利用硬件实现的静态分支预测，我们 通常只能预测指令是倾向于跳转还是倾向于不跳转，对所有的分支都提供同样的 结果，因此无法适应程序运行中的状态变化，这对于某些分支( 如循环终止分支) 来说，准确度还比较高，但对于其它一些，诸如带有数据相关性条件的分支，静 态预测的准确度就不够了。软件编译实现的预测方案中，编译器也没有能力那么 准确地预测分支如何执行，有些分支容易预测，但有些很难，静态分支预测的预 测失效率很大。实际使用中静态分支预测往往结合其它分支处理技术一起处理分 支指令，如文中将阐述的s 微处理器采用的是分支折叠与分支预测结合机制。此 外还有静态分支预测结合动态分支预测一起来使用的方案，如h p 系列的p a 8 0 0 0 和p a 8 7 0 0 1 5 】。 2 6 2 动态分支预测 动态分支预测技术虽然需要增加一些硬件支持，但是它能够利用运行时的信 第二章分支处理技术 9 息，记录下每条分支指令的历史信息。这是一个很大的区别，因为研究发现，一 条分支指令的跳转与否在很大程度上依赖于该分支及相邻分支在历史上的转移情 况，即表明分支转移的可能性在很大程度上依赖于以前的运行结果 1 6 】。动态预测 基于程序执行过程中的转移历史信息预测当前指令的分支转移方向，由处理器中 的专用部件来实现预测功能。动态分支预测结构就是采用分支目标缓冲( b t b ) 试图 发掘这种特性，保存每条分支的历史信息。这些信息可以在程序执行过程中动态 地更新。理想状态下，b t b 表应该保存所有的分支指令，但由于存储空间的限制， 通常采用一定的映射函数将分支地址映射到某一项 4 】。这也就产生了多种算法。 先简单地来看动态分支预测策略，它试图通过记录分支指令特别是条件分支 指令在程序中的历史位来改善预测的准确度。每个条件分支指令可有与之相关联 的一位或者几位，它们反映此指令的最近历史，称为发生不发生开关 2 7 】，指挥 处理器在下次遇到此指令时产生具体的判定。一般，这些位保存在一个暂时的高 速存储装置中。一种可能是，这些位与任何己在c a c h e 中的条件分支指令相关联， 当这种指令由c a c h e 替换出时其历史位也相应丢失；另一种可能是维护一个小型 历史表，在这个表项中有最近执行的分支指令的一位或几个相关位，处理器能像 对待c a c h e 一样地访问这种关联表，或者通过使用分支指令地址的低序位来访问 表项 1 7 】。 分支历史信息以单个位记录的，只是当前分支指令最后一次执行是否发生跳 转。这时只需追踪这最后一次执行的结果，猜测此分支指令按照它上次同样的方 式执行。 如前所述我们建立一个分支历史关联表来实现这个功能，它含有n 个条目 ( e n t r y ) ，也称为项。平均每个项分配1 位数据，如图2 1 。每当我们执行一条分 支指令时，我们用分支指令地址低序位来访问历史表 1 3 】，并选择其中一个项来 判断分支跳转与否。当分支指令实际执行结束后，我们在相应的位置更新历史位， 记录下分支跳转还是不跳转。 图2 1 一位分支预测器 结 1 0 微处理器中分支处理技术的开发与研究 判定过程用一位饱和计数器来实现，有限状态机表示如图2 2 。 图2 2 一位分支预测器状态转化图 这种结构称为一位预测器，它只有一位数据与每个分支指令相关联。一位预 测器占用相对较小的芯片面积，运行速度也快，但它存在着局限：首先，不同分 支指令之间的冲突，即如果两条频繁执行的分支指令同时映射到同一条目项，那 么就存在冲突，在这两条分支指令执行结果不同的情况下，却会预测为相同。这 降低了预测率( 但若执行结果相同的话，这反而提升了性能) 。最重要的是，一位 预测器在面对如下情况：如果一条分支指令经常都是不发生跳转而中间偶尔次 跳转，即卜外心n n 删，如循环指令，可看到由于历史位的两次更新造成了 两次预测的错误，一次是进入循环时，一次是退出循环时( t t t t t n t t t t t 情况类似) 。 一种提高预测精度的方法就是采用两位历史数据预测，即两位预测器，如图 2 3 。这两位历史位能记录相关分支指令的最后两次执行情况或是记录其它样式的 状态。 分 地 访 图2 3 两位分支预测器 相应的两位历史关联表条目是通过两位饱和计数器来实现，而不是一位历史 表采用的一位，如果计数器值为1 0 或者1 1 ，那么此时预测分支指令跳转；如果 计数器值为0 0 或者0 l ，那么此时预测分支指令不跳转。分支指令最终执行完毕 后，历史表将进行更新，计数器实现更新的方式是：分支指令实际跳转，相应的 计数器值增加；分支指令实际不跳转，相应计数器值减少。判定过程用有限状态 第二章分支处理技术 机表示，如图2 4 。 跳榭 赢翮鳖 竺卜磊 跳转 赢赢p 预测不跳转l 二 ( 0 1 ) k 一 j 跳转 预测跳转 ( 1 0 ) 不跳转 预测不跳转 ( 0 0 ) ；跳转 图2 4 两位分支预测状态转化图 于是，算法只有连续两次失误才更改预测判定。在遇上前面所述循环时预测 器状态虽然由o o 变为0 l ，但下次仍然预测不跳转，只会发生一次判断错误。 两位的预测结构可以扩展至t 1 n 位，但研究表明，在n 2 时，两位预测模式与n 位 预测模式的预测精度基本相同【1 0 】。采用二位饱和计数器预测方案的处理器有： m i p s 的r 1 0 0 0 0 、a l p h a 的2 1 0 6 4 、2 11 6 4 和s u n 的u l t r a s p a c e l 。 2 6 3 两级分支预测 动态转移预测方法通常具有更高的正确率，替换预测策略时不需要修改指令 系统和已经存在的可执行程序。现在的研究成果表明静态预测的平均准确性为 6 8 ，而动态预测的准确性能达到9 0 或更高 1 3 】，当然，动态预测的控制逻辑 也更为复杂，算法也很多。 动态分支预测的关键是对分支历史信息的处理算法，前述的动态分支预测器 采用的是n 位饱和计数器( 典型的是一位和两位饱和计数器方式) 。但简单地基于 历史位预测的方法，无论一位还是两位饱和计数器算法，都存在映射到同一历史 表条目的冲突情况，而且两种方案都存在一个根本的局限就是，只考虑当前的分 支指令情况，仅是利用单个分支最近的分支行为来预测其将来的行为，这在包含 很多循环控制分支的高密度浮点算法的科学计算程序中比较有效。但是实际中分 支指令之间存在着许多的数据相关和控制相关，简单地基于历史位预测的方法对 不同分支指令之间的相关性并未予以充分考虑，这样在整数算法占优的程序中预 测精度受到限制。 1 2 微处理器中分支处理技术的开发与研究 为获取更高的预测准确度，产生了多级分支预测技术。我们不仅仅考虑要预 测的那条分支指令的历史信息，而且利用邻近相关的分支指令的执行信息来更准 确地预测当前指令的执行结果 2 1 】。 1 9 9 1 年密歇根大学的t s ey uy e h 和y s l en p a t 教授发表论文首次提出两级自适 应分支预测技术 18 】。 两级预测机制的基本原理就是根据每个分支指令最新的k 次跳转或不跳转的 结果来预测此分支指令当前是否发生跳转，如图2 5 。 第一级是一个k 位的移位寄存器，称为分支历史寄存器( b r a n e hh i s t o r yr e g i s t e r , b h r ) ，其中每一位代表一次程序执行的历史信息，如果这一位为0 ，表示该分支 指令这一次不跳转，为坝f j 表示该分支指令这一次发生跳转，b h r 由指令指针所指 向的地址来进行索引。如果所有的k 位b h r 项索引一个模式历史表( p a t t e nh i s t o r y t a b l e ，p h t ) ，那么该p h t 就叫做全局模式历史表( g l o b a lp a t t e nh i s t o r yt a b l e ， g p h t ) ，这个p h t 就是第二级了。最基本的两级分支预测器是使用一个k 位的单个 全局分支历史寄存器索引两位的p h t ，更新函数可以由两位饱和计数器构成，因此 p h t 共需要，置项，其中每项里面存放着一个值s ，得到这个值s 后，通过一个函数 f u n e a ( s ) 对这个值进行计算，然后跟据计算的结果就可以预测这次分支指令是否跳 转了。这两位饱和计数器四种状态之间的转换如两位历史位预测方法那样，当分 支指令执行后实际发生跳转，饱和计数器加1 ；当不发生跳转时，饱和计数器就向 减1 的方向变化。由强转移变化到强不转移，当中要经过弱转移和弱不转移两个状 态。当两位饱和计数器处于强转移或强不转移时，只有连续两次预测错误时才会 改变预测方向，避免了一位分支预测机制对于循环有两次预测错误的情况。 分支历史寄存器表( k 位) 图2 5 两级分支预测器 当这个分支指令被真正执行后，把第一级中先前那个k 位寄存器向左移一 位，然后在最右边空出来的那一位上根据是否跳转( t a k e n ) 填入1 或0 ，再通过 第二章分支处理技术1 3 一个函数f u n e b ( s ，t a k e n ) 计算出新的s 值存替换先前那个p a t t e r n 表项中的s 。这其 实是一个类似于人工智能中不断训练学习的方式，所有的学习训练策略，即函数 f u n c a 0 及f u n e b 0 都可由设计者自行制定。因为分支预测是根据程序执行时候的 动态信息，所以也属于动态预测算法。在程序开始执行的时候，分支预测表为空。 随着程序的执行，分支预测表慢慢被填满，这时候就能够提供相应的分支预测信 息。 这种方法在预测方面有更为全面的考虑，能够预测相关的分支指令，其它预 测方法是做不到的。但是同样存在历史信息项相同时的冲突现象，如在同一排中 4 次跳转的所有分支指令将映射到同样的预测目标( 这有时也是十分有利的) ；而 且在做精确预测时也要耗费更多的时间。 两级自适应分支预测精确度可达到9 7 ，对有多个分支指令，可以有多个k 位 寄存器，每个k 位寄存器为一个分支指令服务，但由于p a t t e r n 表较大，所以可以让 多个k 位寄存器共享一个p a t t e r n 表；也可以采用多个p a t t e r n 表，每个p a t t e r n 表为一条 分支指令服务，这都可以提高预测精度 2 8 1 。 随着研究的深入，不断产生新的算法，1 9 9 3 年s c o t tm e f a r l i n g 提出g s h a r e 方案 ( 全称为g l o b a lh i s t o r yw i t hi n d e xs h a r i n g ) 2 6 1 ，这是一种经典的全局历史记录表预 测方法。该方法被后来的诸多c p u 所采用，成为用单预测器预测分支的经典方案。 g sha re 方法用分支指令的地址作为区分不同分支的重要标志，将n 位地址的高m 位与历史记录表的m 位异或，然后再拼成新的n 位地址去查寻分支模式历史表来决 定分支转移方向。这种算法更加综合考虑了分支指令相关历史记录，预测效率更 高。 为了进一步提高预测成功率，s c o t tm e f a r l i n g 之后又提出了一种崭新的预测思 想，将不同的预测器组合起来，如动态分支预测与静态分支预测结合，利用它们 不同的特点，再结合其它分支处理技术共同进行分支转移预测，这种思想后来被 称为混合预测( h y b 订dp r e d i c t i o n ) 2 0 】。实际应用中看到的各种预测机制中有很多都 是属于混合预测器的范畴 31 】。 2 6 4 分支目标地址计算 仅仅预测分支指令跳转或者不跳转是不够的。如果一条分支指令跳转，我们 还需要预测它跳转的目标地址。我们采用分支目标地址缓冲器( b r a n c ht a r g e t b u f f e r , b t b ) 来完成地址的预测，达到判定一经做出，就能立即开始取指令，实 现高效率。 分支目标地址缓冲器是一个和流水线取指令阶段相关联的小型高速缓冲存储 1 4 微处理器中分支处理技术的开发与研究 器。这个表项由三个元素组成：( 1 ) 分支指令索引位；( 2 ) 记录这条指令使用状 况的历史位；( 3 ) 有关它的目标地址信息。在大多数的建议和实现中，此索引位 为目标指令地址( 分支目标地址c a c h e 技术b t a c ) ；另一种可能是，此索引位为 实际的目标指令( 分支目标指令c a c h e 技术b t i c ) 。保存目标地址可使表的规模 较小，但与保存目标指令相比却要花费较多的取指令时间，这点需要权衡折中考 虑。 b t b 具体功能实现如图2 6 。其在使用中作为c a c h e 对待，每次预取触发一 次历史表的查找。 分支预 测历史 位 图2 6b t b 结构 流水线取指令单元将当前分支指令地址与b t b 中存储的指令地址( 假设为 b t a c 方案) 相比较。如果未发现匹配的，则下一顺序地址( p c + 4 ) 用于取；如 果其中有匹配的，则依据指令状态进行预测，若预测此分支指令跳转，那么b t b 中目标地址部分就用于新指令的取( b t bt a r g e t ) ；若预测不跳转，下一顺序地址用 于取( p c + 4 ) ，如图2 7 。当此分支指令最终执行完成，执行阶段将其结果通知 b t b ，b t b 将根据正确的预测信息和目标地址进行更新，指令状态被修改以反映 正确或不正确的预测。若预测不正确，则选择逻辑重定向到正确地址为下次取。 当碰到的一个条件分支指令不在表中时，则它被添入到表中，而现有的一个表项 被删除，这一般使用类似于c a c h e 相关替换算法来实现。 鉴于b t b 与c a c h e 的相似性，我们可以利用尺寸调节、地址存储设置等方法 来提高指令地址命中率。通常都是将b t b 与分支预测器相结合，但其中分支指令 的方向预测和分支目标地址预测是分开执行的，这两部分的尺寸也不相同，有些 预测方案则直接将这两部分合并以节省空间。 第二章分支处理技术1 5 1 3 t bb i a n c hp 砧1 t a l g c lp c 1 1 i ll a k e nb t l 3t a r g e t l l i tn o tt a k e np c “ l n l s sl a k e np c 钳 l n i s s n o tt a k e np c + 4 图2 7 分支目标地址 小结 以上我们主要了解了分支指令对流水线性能的影响，探讨了分支处理技术特 别是几种分支预测方案的实现原理以及分支目标地址计算机制。分支处理技术的 研究工作随着现代处理器对性能要求的不断提升显得越来越重要。 第三章s 微处理器中的分支指令处理 1 7 第三章s 微处理器中的分支指令处理 通过第二章对主要分支处理技术的理论基础和实现原理加以分析，本章结合 实际微处理器设计项目讨论其中分支处理策略的制定和分支处理单元机制的设 计。 3 1s 微处理器简介 企业研发的s 微处理器应用于的一款双核通信处理器s o c 芯片，整个芯片包含 这个嵌入式的微处理器内核和个通信处理器内核。本节主要概述s 微处理器的基 本组成单元划分和参数设置。 s 微处理器内核是整个芯片的处理核心，其为一低功耗、精减指令集计算机 ( r e d u c e di n s t r u c t i o ns e tc o m p u t e r ，r i s c ) 系列微处理器并实现了3 2 位p o w e r p c 体系结构，定义了2 0 0 多条指令。大部分指令在一个单一的周期内执行