（微电子学与固体电子学专业论文）一种基于双模结构的分支预测器研究.pdf

摘要摘要当今世界的主流计算机大多采用超标量、深度流水的技术，控制也越来越复杂，一条指令的预测失误很可能会导致几个甚至几十周期的处理器中断，从而降低处理器的性能。因此如何用尽量小的代价获得令人满意的预测成功率，成为计算机体系结构研究的一个重要领域。目前分支预测研究的重点是动态分支预测技术，采用学科交叉的观点，提出新的预测算法。算法的研究主要包括分支历史信息的处理，分支指令地址的映射，状态转换等。还要考虑硬件开销，实现的复杂性问题。本文基于对近年来国内外分支预测方法的研究分析，提出了一种对动态两级自适应分支预测进行改进的新方法，即基于双模结构的双模预测器。程序中的很多指令是相关的，我们可以根据其它转移指令的结果来预测当前转移指令的结果，这种存在于转移指令之间的相关称为转移间相关。也可以根据局部转移历史( 如转移指令自身以前的转移结果) 来预测一条转移指令的结果，这种存在于单一指令的多个转移结果之间的相关称为转移内相关。双模预测器能同时根据指令转移间相关和转移内相关进行转移预测，从而获得更高的预测精度。在分析双模预测器结构的同时，本文还对其性能进行了测试。数据表明，与传统的静态分支预测方法相比，双模预测器的地址和方向命中率有了很大的提高。关键词：分支预测转移间相关转移内相关双模预测器a b s t r a c ta b s t r a c tb e c a u s eo fs u p e r s c a l a ra n ds u p e rp i p e l i n i n gt e c h n i q u e s ，w h i c ha r eu s e di nm o s to ft h ep o p u l a rc o m p u t e r s ，ab r a n c hm i s p r e d i c t i o nm a yc a u s es e v e r a lt od o z e n so fc y c l e s s t a l l t h u s ，h o wt og e tt h es a t i s f y i n gp r e d i c t i o nh a sb e c o m ea ni m p o r t a n tf i e l di nc o m p u t e ra r c h i t e c t u r er e s e a r c h n o w a d a y s ，t h er e s e a r c ho nb r a n c hp r e d i c t i o nf o c u s e so nt h ed y n a m i cb r a n c hp r e d i c t i o n 。m a n yn e wp r e d i c t i o na l g o r i t h m sh a v eb e e nr a i s e db a s e do nt h em e r g eo fd i f f e r e n ts u b j e c t t h er e s e a r c ho nb r a n c hp r e d i c t i o ni n c l u d e st h eu s eo fh i s t o r yi n f o r m a t i o n ，b r a n c hi n s t r u c t i o na d d r e s sm a p p i n ga n ds t a t et r a n s i t i o n t h eh a r d w a r es p e n d i n ga n dt h ec o m p l e x i t yo fi m p l e m e n t a t i o nm u s tb ec o n s i d e r e d t 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 di nr e c e n ty e a r s ，t h i sp a p e rb r i n g sf o r w a r dan e wm e t h o dt oi m p r o v et h et 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 o r , w h i c hi sc a l l e dt h et w o - p a t t e r np r e d i c t o rb a s i n go nat w o - p a t t e ms t r u c t u r e m a n yb r a n c h e si nt h ep r o g r a m sa r ec o r r e l a t e d w ec a np r e d i c tt h eo u t c o m eo fab r a n c hb a s e do nt h eo u t c o m e so fo t h e rb r a n c h e s ，t h i sk i n do fc o r r e l a t i o nb e t w e e nb r a n c h e si sc a l l e di n t e r - b r a n c hc o r r e l a t i o n a n dw ec a np r e d i c tt h eo u t c o m e so fab r a n c hb a s e do nt h el o c a lb r a n c hh i s t o r y ，i e t h ep r e v i o u so u t c o m e so ft h eb r a n c hi t s e l f ；t h i sk i n do fc o r r e l a t i o nb e t w e e nt h er e s u l t so fas i n g l eb r a n c hi sc a l l e di n t r a - b r a n c hc o r r e l a t i o n t h et w o p a t t e r np r e d i c t o rm a k e sp r e d i c t i o n sb a s e do nb o t hi n t e r - b r a n c hc o r r e l a t i o na n di n t r a - b r a n c hc o r r e l a t i o ns i m u l t a n e o u s l ya n dt h e nc a na c h i e v eh i g h e rb r a n c hp r e d i c t i o na c c u r a c y b e s i d e sa n a l y z eo ft h es t r u c t u r e ，t h i sp a p e rt e s t si t sp e r f o r m a n c e a n dt h ed a t ei n d i c a t e st h a tt h ep e r f o r m a n c eo ft h et w o p a t t e r np r e d i c t o ri sb e t t e rt h a nt h et r a d i t i o n a ls t a t i cp r e d i c t o r s k e y w o r d s ：b r a n c hp r e d i c t i o ni n t e r - b r a n c hc o r r e l a t i o ni n t r a b r a n c hc o r r e l a t i o nt w o - p a t t e r np r e d i c t o r西安电子科技大学学位论文独创性( 或创新性) 声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谓十中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切的法律责任。本人签名：榉日期沙夕g i _ 西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。本人签名：二阻出色名日期迎! 塞：叫导师签名：第一章绪论第一章绪论流水线结构提高了微处理器的硬件资源利用率，因此大大提高了c p u 运行效率，但是程序中的指令并不总是顺序执行，转移指令的存在使得程序的执行方向经常发生改变。微处理器在取到一条分支指令时，并不能立即确定该分支指令是否转移，只有该分支指令执行完毕才能知道是否发生跳转以及跳转的地址，因此分支指令的存在将会造成流水线的停顿。目前微处理器对分支指令的处理采用了分支预测的方法，即当分支指令被取到流水线时就预测其是否发生转移，因此分支指令预测的精度会直接影响到微处理器的性能。1 1 分支预测的基本原理在应用程序中，分支转移很多，而且也很复杂，但是我们还是可以从中找到规律，发现一些有针对性的预测策略，从而提高系统的性能。在一些多重循环比较常见的应用程序中，我们会发现：在多重循环里，分支转移总是有很强的偏向性，也就是说分支总是经过多次同向的执行，才会偶尔转向另外一个方向，然后很快又会转回到原来方向。因此我们可以采用两位二进制计数器，来记录分支所处的状态，直到分支连续出现两次预测失误时才改变分支的预测方向。两位预测方法，对于有很强偏向性的分支，不论是偏向跳转、或是偏向不跳转的，都有很好的效果，只会导致偶尔的预测错误。在实际的程序中，很多的循环都能产生有很强偏向性的分支，例如下面的程序段：d o ( a )( 1 )d o ( b )( 2 )u n t i l ( b )( 3 )u n t i l ( a )( 4 )在程序段中，当内循环执行时，分支语句( 3 ) 总是跳转成功，直到循环结束。由于外循环的执行，内循环将再次被执行。这时如果采用只有一位的计数器，则由于前一次跳转失败，因此就会判断此次分支为不跳转，从而产生预测错误。如果采用前述两位饱和二进制计数器，虽然状态机由li 变为1 0 ，但仍然判断分支跳转，预测依然是正确的。2一种基于双模结构的分支预测器研究还有我们知道，程序在执行过程中是有局部性原理的，也就是说，从时间上讲，刚刚执行过的代码，往往很快被重新执行。从空间上讲，刚刚执行过的代码的相邻代码往往也会被很快执行。因此最近的分支的历史结果，对于将要进行的分支走向，往往是有潜在影响的。针对这两种不同的局部性原理，就产生了利用单个分支的历史记录来预测分支的局部预测法和利用最近遇到的全局分支结果预测的全局预测方法。这两种思想实际上就是本文后面要介绍的两级自适应思想的特例。1 2 近十年国外的一些研究成果1 9 9 1 年密歇根大学的t s e y uy e h 和y a l en p a t 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 ) 思想，开创了非简单二值动态预测的先河【2 】。他们的主要思想是：动态的将程序中执行过的分支的结果记录到分支历史记录表中，基于分支历史记录对当前的分支进行预测，分支历史记录表在程序执行中的过程中动态的修改。所谓两级是指在这种预测中，有两个记录表，一个是分支历史记录表( b h t ) ，一个是分支模式记录表( b p t ) 。当遇到新的分支需要进行预测时，首先通过查找分支历史记录表查出与当前转移相匹配的分支模式，然后通过查寻分支模式表对当前指令进行预测。从9 0 年代初到现在，多数转移预测方法都是以此为基础的。1 9 9 1 年t s e y uy e h 和y a l en p a t t 提出这种思想的时候，提出的控制分支模式表修改的自动机非常复杂，同时也不好实现，因此1 9 9 2 年他们分析了b h t 和b p t的各种组合方式( b h t 和b p t 的组织结构分别是全局的( 曲，也就是所有的分支公用一个表；组相连的( s ) ，也就是某一类分支公用一个表项：直接相连的( p ) ，即每个分支占用一个表项。b h t 和b p t 各采用这三种连接方式，共九种组合情况) ，指出在所有方案中，采用直接相连的方法，虽然准确率很高，但是硬件消耗过大。同时通过分析得出g a p 方式( 也就是转移历史表所有转移公用一个，针对每一种模式各有各的模式表) 在这九种组合之中，对于一般程序而言，是一种不错的折衷选择。虽然在t s e y uy e h 和y a l en p a r t 提出的9 种组合中，g a p 的分支控制效果最好，但对于程序尤其是大段程序而言，由于b h t 只有一个，因此对于不同的分支很可能会遇到相同的历史记录，而他们转移的实际方向却截然相反，因而造成不命中的增加，从而降低g a p 的预测成功率。因此，如何减少这种不同转移之间的误命中，使他们面对相同的历史记录时可以区分开来，就成为要解决的重要问题。19 9 3 年s c o t tm c f a r l i n g 针对这一难题提出了著名的g s h a r e 方案1 3 1 ( 全称为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 ，详见图3 3 ) 。该方案被后来的诸多c p u 所采用，第一章绪论3成为用单项预测器进行分支预测的经典方案。使用分支指令的地址作为区分不同分支的重要因素，将n 位地址的高m 位与历史记录表的m 位异或，然后再与剩下的n m 位地址拼成新的n 位地址去查b p t 。b p t 采用的是标准的两位状态机模型，在后面将具体对g s h a r e 方案进行介绍。实践证明，对于一般的应用，这种预测器得到的结果已经可以令人满意了。为了进一步提高预测成功率，s c o t tm c f a r l i n g 提出了一种新的预测思想，将不同的预测器组合起来，利用它们不同的特点，共同进行转移预测，这种思想后来被称为混合预测( h y b r i dp r e d i c t i o n ) 。从1 9 9 4 年开始，基于两级自适应动态分支预测的混合仿真模型层出不穷，但由于它们大多数是通过对特定的程序的分析【4 】，选择预测器来提高命中率，而且大多结构复杂，只是为了研究而提出的，因此对实际的应用作用并不大。1 9 9 4 年，p o y u n gc h a n g 等提出了通过对分支指令进行分类，来提高分支预测命中率的方法【5 j ，他们将指令通过程序测试进行分析，将指令分成易于预测的和不易于预测的两大类，用一个比较简单的预测器对于比较容易预测的分支进行预测，同时对于不好预测的分支用复杂的预测器进行预测，由于这种方法具有针对程序的特点，因而并不太实用。但是这种思想，对作者设计的分支预测器还是起了一定的帮助作用，作者就是通过一种分类思想，实现了对复杂度的控制。1 9 9 5 年p o y u n gc h a n g 等提出了比较实用的混合型分支预测器1 6 1 ，用两种两级自适应动态分支预测器来共同实现分支预测，通过两个两位计数器进行计数，需要预测的时候采用计数器值大的所对应的转移预测器的结果进行预测，同时记录没有选中的预测器的分支预测方向，如果两个计数器的值相同则选择原来的预测器不变。如果分支预测是成功的话，则计数器加1 ，否则减l ，加到最大为3 ，减到最小为0 。这种方法的具体实现见图1 1 。b r a n c hi纮襽1 l i匕r a n c hi s t o r ya b l er e dt i o n1 19 9 5 年p o y u n gh a n g 的混合型转移预测器于采用了两级自适应预测器作为基础，因此混合预测器是较易实现的，同4一种基于双模结构的分支预溅器研究时由于采用了两个预测器，使得命中率也有一定的提高。但是它所付出的代价就是控制的硬件逻辑要比原来多出一倍左右，控制复杂度也大大增加，因此需要慎重考虑。不过这至少已经是一种可行的混合预测器了。1 9 9 7 年c h i h c h i e hl e e 等提出了b i m o d e 预测器悼j ，这是对混合分支预测器又一改良，目的是为了进一步提高分支预测的命中率，结构详见图3 5 。b i m o d e 预测器在普通的混合分支预测器的基础上加入了一个小的c a c h e ，这个c a c h e 用米记录当前转移最近应用了哪个预测器，由于对预测器的选择，达到了针对每条分支指令的程度，因此命中率又有所提高。但是增加c a c h e 本身，就带来了很大的复杂度，比如，c a c h e 的容量应该有多大，究竟该如何进行c a c h e 替换等等，因此无论是在控制通路上，还是在硬件逻辑上都要付出很大的代价。我认为这种方法，预测准确率虽高，但并不实用。在同一年e r i cs p a r n g l c 等提出 a g r e e p r e d i c t o r 9 1 ，他们的思想是，在指令c a c h e或分支目标地址缓存( b t b ) 中为每一个分支都加上个偏向位，偏向位中保存的是这条指令最常见的分支方向。两位计数器不是用来预测分支方向的，而是用来决定是否按照偏向位来转移的。当分支的实际结果与偏向位一致时，计数器加1 ，否则减l ，最多加到3 ，最小减为0 ，具体结构详见图3 4 。这种方法相当于把两个预测器综合起来运用，巧妙的减少了一些逻辑，但是对所有转移指令都要增加一个偏向位，控制和实现起来会比较复杂。也是在这一年，威斯康星大学的y i a n n a k i ss a z e i d e s 等为了进一步提高分支预测的性能，提出了一种转移预测的新的思路，使用结果值柬进行转移预测弘饿。他将所有基于值的转移预测器分成了两类，一类是计算型的预测器，这类预测器主要有两种，用上一次的值进行预测的最近值预测法( 1 a s tv a l u ep r e d i c t o r ) 和用等长差值进行预测的步长预测法( s t r i d ep r e d i c t o r ) 。另一类是依赖上下文进行预测。这种思想虽然很新颖，但是进行值的预测本身就是一件很复杂的事情，和转移控制再结合起来，其复杂度更是可想而知。依据值进行预测的方法无论是控制还是应用都非常复杂，需要记录的信息很多，因此不实用，迄今为止，没有一个成熟的c p u采用这种方法进行预测。1 9 9 8 年a 。n e d e n 等人提出 y a g s 转移预测方案【l1 1 ，这种方法主要是针对g s h a r e 和i a g r e e 方法进行的改进，目的是为了减小可能遇到的地址冲突。他们提出把所有的p h t 分成两层，第一层是普通的p h t ，第二层分成两块c a c h e ，一块是转移成功表( t a k e n ) ，另块是不成功表( n o tt a k e n ) ，分别负责存储特殊情况指令地址的例子，首先在第一层p h t 进行选择，针对在第一层p h t 的选择结果，在相反的第二层p h t 中进行查找。比如在第一层p h t 中查出应该预测为真，则在第二层n o tt a k e nc a c h e 中去查找，是不是有这条指令的地址，如果有，并且预测当前应该为n o tt a k e n ，则预测为n o tt a k e n ，否则按照第一层的结果进行预测。当分支结果出来之后，第一章绪论分别对顶测表进行修改。在第二层表中，为了准确性，采用了a g r e e 预测器的方法，就是引入偏向位，来帮助提高预测的正确性。这种方法，没有对固定程序的针对性，因此有一定实用价值，但实现起来很麻烦，硬件消耗很大，而且控制起来相当复杂，造成这种方法没有得到广泛应用同样在1 9 9 8 年，k a r e ld r i e s e 。等人提出了c a s c a d e d 预测器【l2 。这种预测器正如其名字一样，是一种层叠结构。在总体结构上和两级自适应方法有很多相似的地方。只不过更新的方法不同，它通过第一层的预测器把分支指令动态的分组，只有当预测器预测失败的时候，第二层的预测器才开始对这种分支做预测，为了防止硬件上的浪费，第一层的预测器就像是一个滤镜，把简单的转移滤出来自己处理，只有真正需要依赖于历史记录的分支，才由第二层预测器来进行预测。从1 9 9 9 年开始至u 2 0 0 0 年，国际上对于转移控制的研究开始向针对特殊程序优化预测器方面倾斜，主要是提高特殊程序尤其是s p e c 的预测命中率方面。这对于实际的转移控制收效如何就不得而知了，不过由于其极具针对性，因此s p e c 的结果都有一些不同程度的提高。但是现有的任何主流c p i 都没有至少是公开表示自己是采用的这个时期的预测器。1 9 9 9 年，t i m o t h yh h e i l 等提出f l j v a l u e 预测器和普通预测器来进行混合预测i l 引。但是他们对预测器的选择则是在对s p e c 程序进行分析之后，根据得出的规律来设置的，因此实用性值得商榷。而且他们设计的预测器比上面提到的每一种预测器都要复杂的多，实现起来非常复杂。2 0 0 0 年，d a n i e la j i m e n e z 提出了一种基于神经网络( p e r c e p t r o n s ) 的动态预测方法，他提出给每一个转移提供一个权值，根据计算出的权值，来进行转移预测i l4 1 。采用这种方法，首先要采用一系列数学公式来对当前的转移计算权值，这种方法即使真的能够提高转移预测的正确率，他的复杂度也不是一个实用c p u 所能够接受的，因此不可能用于实用，也就是研究研究罢了。进入2 1 世纪体系结构方面的专家们己经认识到只盲目的提高转移的命中率，而不去理睬硬件复杂度，以及延迟等方面的因素是不可能对实际应用有任何帮助的，因此开始务实的研究深亚微米情况下转移控制应该如何进行，最新的研究成果是d a n e la j i m e n e z 于2 0 0 0 年术提出的关于g s h a r e 模型在深亚微米环境下的延迟结果【l5 1 ，值得庆幸的是，如果我们采用不大于l k b 的硬件规模，在深亚微米环境下，性能是不会有太大变化的。不过如果采用2 k b 以上的规模，预测性能就要下降到普通情况的一半左右、甚至更低。以上是最近国际上对转移预测方面的一些主要研究成果。1 3 分支预测技术的发展趋势分支预测技术最早出现在8 0 年代初，开始时主要采用静态预测方法。所谓静6一种基于双模结构的分支预测器研究态分支预测方法就是首先通过对程序的一次甚至多次扫描，得到一些可利用的信息，然后利用这些信息作为预测的依据，对程序中的分支进行预测，这种方法的特点是：由于对程序在执行之前就进行了分析，因此预测的准确率比较高。但是由于在程序执行之前要进行预扫描，因此效率比较低。所以，通常不作为单独的分支预测方法进行使用。正是由于静态预测方法的效率比较低，因此从8 0 年代中期开始，动态预测方法的研究就逐渐为人们所重视。较早提出的比较简单实用的动态预测方法是采用单层二进制计数器进行分支预测，主要有两位状态机和多位状态机的预测方法。但是应用比较广泛的还是两位状态机方法。两位状态机方法实际上是针对多重循环提出的，针对多重循环中的转移通常具有很强的偏向性，偶尔一次的分支方向改变，并不意味着分支的偏向发生变化。因此这种方法对于多重循环具有不错的效果，但是从对整个程序的预测结果来看，还是远远不能让人满意的。进入2 0 世纪九十年代，随着对计算机性能要求的不断提高，分支预测成功率的降低越来越成为影响系统性能的瓶颈之一。而无论是静态预测方法还是两位状态机方法虽然有各自的优点，但是也有着明显的不足。因此，世界上众多系统结构方面的专家认识到研究高效准确的分支预测方法的重要性，开始动手研究各种高性能的预测方法。其中很多思想都源自1 9 9 1 年t s e y uy e h 和y a l en p a r 教授提出的两级自适应思想，包括g s h a r e ，b i m o d e ，y a g s 等等。随着对分支预测准确率要求的进步提高，预测机制也逐渐的复杂起来，开始慢慢偏向于充分利用静态和动态方法各自的优点进行混合预测，不过这类方法对编译和预处理要求比较高，因此准确率很高，但效率稍低。1 4 课题研究的主要内容，来源和意义本课题研究的主要内容包括以下几个方面：一对分支预测机制相关技术资料的搜集、整理和研究，特别是近十年国际上对分支预测研究的最新成果。二研究流水线结构，指令在流水线中的执行路径，以及指令的控制相关问题。三在动态两级自适应分支预测基础上提出双模预测器模型，并对其性能进行测试。四分析研究双模预测器在流水线中的应用结构。本课题的来源：网络处理器设计( 国防科技预研项目) 。课题研究的意义：一从个人方面讲，这次课题使本人系统研究了国内外有关分支预测机制的理论第一章绪论7成果，以及集成电路设计时需要考虑的实际问题，促使本人把理论学习与工程实践结合起来，在工程实践中进一步巩固基础知识。二从课题研究角度来讲，这是实验室网络处理器项目研制中重要的一部分，是整个项目顺利完成的基础。1 5 本论文的结构本文是我们研究工作的总结，总分为六章：第一章：课题研究的主要内容和学术界相关的研究工作。第二章：流水线的结构，以及指令在流水线中的执行路径。第三章：动态分支预测技术和几种新的分支预测算法。第四章：两级自适应分支预测结构改进和性能测试。第五章：流水线中的双模预测器结构。第六章：对本文进行总结，并对未来的工作进行了展望。第二章流水线处理器研究9第二章流水线处理器研究2 1 流水线基本概念流水线是提高系统吞吐率的一项强大的实现技术，能够使多条指令重叠操作，已成为现代处理器设计中最为关键的部分。流水线处理器把一条指令的执行分成几个步骤，或称为级。每一级在一个时钟周期内完成。在每个时钟周期，处理器启动执行一条指令。如果处理器的流水线有m 级，则同时重叠执行的指令总条数将为m ，每条指令处在不同的执行阶段。如果分级分得好的话，那么每级都没有时间上的浪费。流水线处理器在这种理想的情况下，与非流水线处理器的性能加速比为：s=篙筹=医cpine=小(2-11c p it)xpxr c p ln p 、。其中，i 为一个程序被执行的总的指令条数。它在流水线处理器和非流水线处理器中是相等的。c p i 是每条指令总体平均所需的时钟周期数。c p i n p 是非流水线处理器的c p i ，c p i d 是流水线处理器的c p i 。因为流水线处理器把一条指令的执行时间理想的分为m 级，有m 条指令在同时( 重叠) 执行，则c p i p = c p i n p m 。但不是说流水线级数分得越多处理器的性能越好，实际情况往往要受很多条件的限制。流水线处理器性能提高的关键在于每个时钟周期处理器都能启动一条指令的执行。这意味着流水线每级中的执行部件要有能力在每个时钟周期接受一条新的指令。在流水线处理器设计中，一个时钟周期要能容下所有类型的功能部件中所需时间最长的部件的执行时间。若流水线级数为m ，总共执行n 条指令，则所需总的时钟周期为( m + n 一1 ) n 。则流水线处理器平均每条指令所需的准确的时钟周期数为：c l p ，| p = ( m + n - ( 2 2 )流水线处理器设计中有两个应考虑的问题：一个是缩短单条指令的执行时间，另一个是提高流水线处理器的吞吐率。流水线技术的好处在于它既能把指令间的操作并行性充分发挥出来，同时又不对用户编程提出新的要求，即它对用户来讲是“透明的 。1 0一种基于双模结构的分支预测器研究2 2 流水线指令执行路径本节主要讨论流水线处理器的数据路径，图2 1 给出流水线处理器的组成结构。执行指令的过程分为5 部分，可重叠执行的指令为5 条。每一级所使用的名字及其要完成的动作如下【l6 】：i f ( i n s t r u c t i o nf e t c h ) 取指令；i d ( i n s t r u c t i o nd e c o d e ) 指令译码并读寄存器操作数；e x e ( e x e c u t i o n ) 执行；m e m ( m e m o r ya c c e s s ) 存储器访问；w b ( w r i t eb a c k ) 写回。图2 1 把单周期处理器的指令执行分为5 级如图中的箭头方向所示，指令执行时从左移向右通过电路。但有两处从右向左的例外：一处是w b 级，它把运算结果写回中间靠左位置的寄存器堆中；另一处是i f 级，它把经过计算的下一条指令的地址写入程序计数器p c 中。下一条指令地址的计算方法有两种，一种是当前p c 加l ，另一种是当前p c 加字地址偏移量，偏移量在指令中定义出。流水线处理器的最大特点是每一个时钟周期取出一条指令来执行。所有的指第二章流水线处理器研究令按取出的先后次序通过图2l 中的从左至右的数据路径。按照指令类型的不同，每种指令在执行过程中可能会用到数据路径的不同部分。当处理器从存储器取出一条指令并把它送到i d 级去译码时，下条指令也正在从存储器中取出。如果先取出的指令没有被保存，则它后面正在被取出的指令会对它造成影响。也就是说，我们必顽要使用寄存器来保存从存储器取出的指令。推而广之，我们必须要在流水线的各级之间安排一组寄存器用以保存当前时钟周期运算出的结果，以便为下一个周期使用( 我们只能用触发器寄存器，它把时钟上升沿时数据输入端的信息打入寄存器中：而不能使用锁存器，因为锁存器的输出在时钟高电平时跟随输入的变化而变化) 称这些寄存器为流水线寄存器。幽2 2 流水线第一级一一取指令级取指段需要大的取指宽度，因为取指段能够维持的吞吐率直接影响到整个流水线的吞吐率，后续几个流水段的吞吐率取决于取指的吞吐率，并且不可能超过它。在第一级( 取指令级) ( 图22 ) 处理器使用p c 的内容访问指令存储器，取出指令，并在该级结束时，把指令打入1 r 寄存器。下一条指令的地址也在这一级计算出，并把它打入p c 寄存器。新的p c 的计算有两种情况：程序不发生转移时，新的p c 地址由当前p c 值加1 得到，即指向下一条顺序的指令：发生转移时情况1 2一种基于双模结构的分支预测器研究在后面几章讨论。2 2 。2 译码图2 3 流水线第二级指令译码级指令译码段对从c a c h e 取出但还没有分派到功能部件的指令进行译码，这主要包括指令的识别、指令类型的确定以及指令间相关性的检测。指令译码的复杂度受两个因素的影响：i s a ( 指令集体系结构) 和并行流水线的宽度。对于典型的r i s c 指令集，指令是定长的且格式简单，因此译码操作比较简洁，无需确定每条指令的起止字节。相对较少的指令格式和寻址方式使得指令类型的辨别相对容易，只需对很少的几个字段进行译码就可以确定指令类型和格式，其它字段的意义也可以很快确定。指令译码级( 图2 3 ) 有两件事要做：第一件是数据路径要完成的工作，主要是从寄存器堆中读寄存器操作数和对指令中的立即数部分进行符号扩展；第二件工作由控制部件完成。控制部件根据指令操作码o p c o d e ，产生所有的控制信号。2 2 3 执行指令执行段是超标量流水线的核心。当前超标量设计的趋势是向着大规模并第二章流水线处理器研究行和多条流水线的方向发展，即配置了越来越专用化的功能部件。功能部件的专用化趋势使得功能部件在设计时可以进行更加有针对性的优化，对特定类型的指令执行效率更高。目前超标量处理器一般都有多个功能部件，包括整数部件、浮点部件、单独的分支部件以及l o a d s t o r e 部件。整数部件除了执行整数a l u 指令以外，还用来计算存储器地址、处理分支以及l o a d s t o r e 指令。分支部件主要是修改p c ，l o a d s t o r e 则直接和数据c a c h e 相连。其他一些专用部件诸如图形图像处理部件也相继出现。图2 4 流水线第三级执行级指令执行段资源的并行性是由空间并行性和时间并行性共同决定的。设置多个功能部件是一种空间并行性的体现方式，而同样的并行程度可以通过将功能部件流水化来实现，这是时间并行性的一种体现方式。一种基于双模结构的分支预测器研究2 2 4 存储器访问图2 5 流水线第四级存储器访问级存储器访问级( 图2 5 ) 专为l o a d s t o r e 指令而设，两条指令均使用流水线寄存器输出作为访问存储器的地址。s t o r e 指令把内容写入存储器。l o a d 指令读存储器，并把读出的数据写入下一个流水线寄存器。2 2 5 写回写回级( 图2 6 ) 把指令结果写回到寄存器堆。要写入的数据来源有两个，一个是存储器数据；另一个是流水线寄存器的内容，即指令的计算结果。第二章流水线处理器研究图2 6 流水线第五级写回级2 3 流水线的相关问题在流水线的体系结构中，关键的性能屏蔽是存在流水线断流。相关是流水线的主要障碍，它使得指令流中下一条指令无法在紧接着的时钟周期内执行，相关将会降低流水线可能获得的理想性能。执行各种不同指令时，流水线上各功能段进行的操作有所不同，表2 1 列出了算术逻辑指令、取数存数指令、转移分支指令在流水线各功能段上进行的操作【1 7 】。1 6一种基于双模结构的分支预测器研究表2 1 不同类型指令中各流水段所进行的操作拷拿。j a l ul o a d s t o i 乇eb r a n c h流水段i f取指取指取指l d译码，读寄存器译码，读寄存器译码，读寄存器计算转移目标地址。设置条e x执行计算访存有效地址件码若条件成立。将转移目标地m e( 空操作)访问存储器( 读或写)址送p c结果弓回寄存器将读出的数据写入寄存w b( 空操作)堆器堆相关有三种情况，分别是结构相关，数据相关和控制相关。下面简要介绍下几种相关的产生原因和一些解决方法。2 3 1 流水线的结构相关某些指令组合在流水线重叠执行过程中，如果硬件资源满足不了指令重叠执行的要求，便会产生资源冲突，则称该流水线有结构相关。结构相关产生的原因是，当有多条指令进入流水线后在同一个时钟周期内争用同一个功能部件而发生了资源冲突。解决结构相关的方法是：( 1 ) 让流水线中的一部分指令执行，而另一部分指令被延迟执行。( 2 ) 如果指令和数据在同一个存储器，可使用双端口存储器，其中一个端口存取数据，另一个端口用于指令。( 3 ) 设置两个存储器，其中一个作为数据存储器，另一个作为指令存储器。2 3 2 流水线的数据相关当指令在流水线中重叠执行时，流水线可能改变指令读写操作数的顺序，使得读写操作顺序不同于它们非流水实现的顺序，从而导致数据供求关系上的冲突，成为数据相关。解决数据相关的方法是：( 1 ) 通过编译器禁止产生具有相关性的五条指令序列，从而避免数据相关。例如，编译器可以在两个相关指令之间插入几条没有相关性的指令来消除数据相关。如果没有这种指令可以插入，编译器可以插入一定数量的n o p 指令，即“什么都不做 的空指令。但是这样做是以牺牲流水线效率为代价的。第二章流水线处理器研究1 7( 2 ) 前传技术，前传技术是将某一指令的操作结果尽快传递给它的后续指令，而不必等到该指令完全执行完毕的一种技术。即把结果直接送到需要它的功能部件，或者说把一个结果从一个功能部件的输出直接送到另一个功能部件的输入。2 3 3 流水线的控制相关流水线的控制相关是因为程序执行转移类指令而引起的相关。转移类指令如无条件转移、条件转移、子程序调用、中断等，它们属于分支指令，执行中可能改变程序的方向，从而造成流水线断流。控制相关决定了跟分支指令有关的指令的执行顺序，即分支指令只能在该执行的时候才能执行。程序中除了第一个基本块的第一条指令之外，均控制相关于某条或某些分支指令，通常情况下，这些控制相关是必须保留的。一个控制相关的最简单例子是程序语句“t h e n ”部分对于“i f ”分支的相关，如下面例子所示：i fp 1s l ：) ：i fp 2s 2 ：)s 1 控制相关于p l ，s 2 控制相关于p 2 而不是p 1 。控制相关会带来两方面的限制：( 1 ) 控制相关于一个分支的指令不能被移到分支之前执行。如i f t h e n 程序中，t h e n 后面的语句不能移至i f 之前执行。( 2 ) 没有控制相关于一个分支的指令不能移至该分支指令之后从而受这个分支控制，如i f t h e n 程序中，i f 前的指令不能移至t h e n 部分中执行。控制相关可以通过以下两个方面得到保证。( 1 ) 指令按顺序执行，这使得分支指令之前的指令只能在该分支指令之前执行。( 2 ) 对控制或分支冲突进行检测，保证控制相关于一个分支的指令在分支转移方向没有确定之前不会被执行。数据相关影响到的仅仅是本条指令附近少数几条指令，所以称为局部相关。而控制相关影响的范围要大得多，它会引起程序执行方向的改变，使流水线损失更多的性能，所以称为全局相关。有关控制相关的解决方法在第4 章将详细介绍。一种基于双模结构的分支预测器研究2 4 小结本章主要研究了流水线的数据执行路径，具体给出了五级流水线中指令执行时各流水段的操作以及指令执行时的各种相关问题。流水线处理器性能的主要障碍是指令相关引起的流水线停顿。其中，控制相关引起的分支开销是最主要的部分。动态分支预测能够减少这一部分的开销，只有当分支预测失误时才会带来分支开销。当分支预测正确时，流水线没有停顿。然而，当检测到预测失误时，必须清空流水线。控制相关和分支预测我们将在第4 章讨论。第三章动态分支预测技术分析1 9第三章动态分支预测技术分析3 1 引言动态分支预测依赖于分支的动态行为，它使用硬件对分支结果进行预测，在程序执行中，分支指令在历史上的转移状态会影响预测结果。最简单的动态分支预测结构是分支预测缓冲( b p b ，b r a n c hp r e d i c t i o nb u f f e r ) in s 或者分支历史表( b h t ，b r a n c hh i s t o r yt a b l e ) 。分支预测缓冲是一块小的内存区域，利用分支指令的低位地址进行索引，同时包含一位最近分支成功或失败的信息。分支历史表是保存分支执行历史信息的一块内存区域，把最近几次分支转移的结果保存在分支历史表( b h t ) 中，通过合理的运用这些历史信息，可以对当前或是将来的分支方向做出预测。一般来讲，分支历史信息越多，可以得到的分支预测准确率越高1 1 9 】，当然这也需要采用适当的分支历史信息处理算法。在目前的分支预测机制中，可以把分支预测缓冲( b p b ) 和分支历史表( b h t ) 结合，也可以单独使用。近几年来，随着对微处理器性能要求的不断提高，原有的分支预测技术的准确率已经不能很好地满足要求，国际上出现了一些新的分支预测算法，试图获得更好的预测性能。例如：基于人工神经元网络的条件分支预测算法【2 0 l 、基于稚尔函数的分支预测算法【2 l 】、基于傅立叶变换的分支预测算法【2 2 1 、采用机器学习的w m l 分支预测算法等【z 引。3 2 典型的动态分支预测技术研究发现一条分支指令的转移与否在很大程度上是依赖于分支历史上的转移不转移结果。动态分支预测结构试图发掘这种特性，合理利用分支历史信息，采用不同的算法进行分支预测。3 2 1 一位两位动态分支预测机制一位预测机制用图3 1 所示的状态转换图进行预测。用转移的地址索引一个位元素的数组，找到用于该转移的预测。如果该位是l ，预测转移发生( t a k e n ) ；否则，预测转移不发生( n ot a k e n ) 。当该转移被提交时，按转移的实际方向对该位更新。一种基于双模结构的分支预测器研究转移成移不成功图3 1 一位转移预测状态转换图一位预测机制在循环迭代不结束的情况下可以正确地预测循环分支。在嵌套循环中，一位预测机制会在内循环中造成两次错误的预测：一次在循环结束时，预测循环分支成功但是事实却是循环结束，一次在第一次执行循环语句，预测循环分支失败但实际成功。这样的两次预测错误在两位预测机制中可以避免。两位预测机制必须在失效两次之后才会改变预测结果。它的状态转换如图3 2 所示。图3 2 两位饱和计数预测两位的预测结构可以扩展到1 1 位。研究表明，n 2 ，两位预测器与r l 位预测器的性能十分接近，因此2 位预测器使用最为广泛。2 位预测器对于浮点密集型程序中存在大量循环的程序精度很高，比1 位预测器性能更好，但对于定点计算中大量存在的相关转移指令，其性能不佳。3 2 2g s h a r e g s e l e c t 分支预测方式g s h a r e g s e l e c t 转移预测结构由m c f a r l i n g 提出【2 4 1 ，结构如图3 3 。两种预测器技术利用分支地址和历史位的关系产生h a s h 函数。第三章动态分支预测技术分析2 l图3 ，3g s h a r e g s e l e c t 预测结构m c f a r l i n g 使用了表3 1 说明两种类型的预测器的索引方式：表3 1g s h a r e 和g s e l e c t 的索弓分支地址b h rg s e l e c t4 4g s h a r e8 80 0 0 0 0 0 0 00 0 0 0 0 0 0l0 0 0 0 0 0 0l0 0 0 0 0 0 010 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 01 1l l1 1 l l0 0 0 0 0 0 0 01 1 1 1 0 0 0 0l l l i l l l l1 l1 11 11 l10 0 0 0 0 0 01 1 1 1 0 0 0 00 1 1 1 1 1 1 1 1根据这个表，我们可以看出，g s e l e c t4 4 技术将分支地址