（计算机科学与技术专业论文）多路径trace处理器.pdf

摘要 据估计，未来半导体技术仍将保持持续稳定的发展势头，可以预期未来的芯片上将 集成巨大数目的晶体管。当前如何利用这些晶体管实现更高性能的处理器是体系结构 研究的热点，也是面临的挑战。 前瞻执行是提高处理器性能的一条途径。本文分析高性能处理器大量应用前瞻技术 带来的问题。特别是深度前瞻技术在长流水线机器中的应用，使系统复杂性上升前瞻 错误的开销增大。针对前瞻技术的不足，本课题提出并研究了“多路径t r a c e 处理器” ( m p t p ) 模型。 i v i p t p 模型对低可预测性分支采取分支两个方向同时执行，减少前瞻错误的开销；对 高可预测性分支采取单路径前瞻执行，实现太指令窗口。m p t p 处理器以t r a c e 处理器为 基础，重复设置多个超标量处理单元，把指令流的多条t r a c e 发送到处理单元同时执行。 本文分析了m p t p 模型的设计思想，研究了m p t p 的执行机制，给出了m p t p 的结 构设计，并通过模拟实验验证m p t p 的关键技术。总结起来，m p t p 的关键技术有： 1 基于分支可预测性的多路径执行m p e b p 机制。m p e b p 评估分支的可预测性， 然后根据评估结果决定分支的执行模式。置信度阀值是评估分支可预测性的关键，不同 的阀值影响路径的派生和资源的使用。 2 基于分支目标提取的t r a c e 预构_ t p b t p 机制。t p b t p 机制从直接分支指令中 提取目标地址，弥补分支预测和分支目标缓存的不足，加速指令读取，实现t r a c e 预构。 3 多路径执行的控制机制。多路径的执行控制将路径中的分支方向编码为路径标识， 辨别不同t r a c e 之闻的路径隶属关系，以此为基础，实施多条t r a c e 执行时的数据和控制 信息的正确传播。 4 t r a c e 的执行控制机制。t r a c e 的执行开发程序的控制无关性，粗细两种粒度的 控制无关性相结合实现指令窗口的层次式管理。指令窗口的层次式管理降低了复杂性。 本文采用处理器体系结构研究广泛认可的s i m p l e s e a l a r 模拟器验证m p t p 的设计思 想。本文根据m p t p 模型对模拟器进行了必要的扩充。模拟器以s p e ( 鼽c 9 5 程序进行基 准测试。 模拟实验表明，在资源约束的条件下，m p e b p 机制对错误预测的分支有较高的覆盖 率t p b t p 机制有效提高了指令的读取速度，m p t p 处理器的整体性能有显著的提高。 总的来说，m p t p 处理器模型是实现宽指令发射的一种有潜力的模型。 本论文的主要研究成果：独创性地提出并研究了多路径t r a c e 处理器m p t p 的结 构和实现机制。 。查竖墨盟堑塞堡型：苎真：曼堕壅目塑垦：墅q ! ：壁塑曼鲎隧主墨童苎翼塾：。 第i 页 ：；= ：；：= ；= ：= 些娑鳖些堡坠彗鲨鹜：= ：；：= = ；：= 美缝溜：擞侮器缮撩，t r a c ee 鑫瓣，t r a c e 处理夔，雾蹊轻橇好tt r a c e 鞭橡，努童疆裂 置俯度 垦堕型堂垫查盔兰堑壅生堕兰堡鲨塞 a b s t r a c t a c c o r d i n gt oe s t i m a t i o n ，s e m i c o n d u c t o rt e c h n o l o g yw i l l c o n t i n u et h e d e v e l o p m e n t p r o g r e s si nt h ef u t u r e i ti sd e t e r m i n e dt h a th u g ea m o u n t so ft r a n s i s t o r sw i l lb ei n t e g r a t e do na c h i p h o wt om a k et h e s eh u g ea m o u n t so ft r a n s i s t o r st oh i g h e rp e r f o r m a n c er e m a i n sab i g c h a l l e n g e s p e c u l a t i v ee x e c u t i o ni saw a yt oh i g h e rp e r f o r m a n c e t h i sd i s s e r t a t i o na n a l y z e st h e i n s u f f i c i e n c yo fs p e c u l a t i v em e c h a n i s m si n a d v a n c e dp r o c e s s o ri m p l e m e n t a t i o n ，i nal o n g - p i p e l i n em a c h i n e ，s p e c u l a t i v e e x e c u t i o ni n c r e a s e s m i s s p e c u l a t i o n p e n a l t i e s ，a n dm a k e s p r o c e s s o r sm u c hc o m p l e x t od e a lw i t ht h ei n s u f f i c i e n c yo fs p e c u l a t i v ee x e c u t i o n ，w ep r o p o s e m u l t i p a t ht r a c ep r o c e s s o r s ( m p t p ) i nm p t eb r a n c h e sw i t ll e s s p r e d i c t a b i l i t yw i l l e x e c u t eb o t hd i r e c t i o n st om i n i m i z e m i s p r e d i c t i o np e n a l t i e s ，w h i l eb r a n c h e sw i t hh i g hp r e d i c t a b i l i t yw i l le x e c u t eo n l yt h ep r e d i c t e d p a t h t oe x p a n di n s t r u c t i o nw i n d o w b a s e do nt r a c ep r o c e s s o r s ，m p t pd u p l i c a t e sm u l t i p l e s u p e r s c a l a rp r o c e s s o r sa sp r o c e s s i n ge l e m e n t s ( p z ) ，a n de x e c u t e si n s t r u c t i o nt r a c e si np e s t h i sd i s s e r t a t i o ni l l u s t r a t e st h ep r i n c i p l e s ，s t r u c t u r e sa n dc o n t r o lm e c h a n i s m so fm p t pi n d e t a i l s w em a k ee v a l u a t i o no fm p t pm o d e lb ys i m u l a t i o n t h ek e yt e c h n o l o g yo fm p t p i n c l u d e s ： f i r s t ，m u l t i - p a t he x e c u t i o nb a s e do nb r a n c hp r e d i c t a b i l i t ym e c h a n i s m ( m p e b p ) i s p r o p o s e d m p e b pm e c h a n i s me v a l u a t e sb r a n c hp r e d i c t i o nc o n f i d e n c e ，a n dt h ee v a l u a t i o no u t p u t d e t e r m i n e sb r a n c he x e c u t i o nb e h a v i o lad i f f e r e n tc o n f i d e n c et h r e s h o l d w i 】la f f e c t p a t h d i v e r g e n c ea n dr e s o u r c e su s a g e w es t u d yt h er e l a t i o n s h i pb e t w e e nc o n f i d e n c et h r e s h o l da n d t h e c o v e r a g eo fm i s p r e d i c t i o nb r a n c h e sb ys i m u l a t i o n s e c o n d ，t r a c ep m c o n s t m c t i o nb a s e do nb r a n c ht a r g e tp r o f i l i n gm e c h a n i s m ( t p b t p ) i s p r o p o s e d t p b t pm e c h a n i s me v a l u a t e sb r a n c ht a r g e tf r o mad i r e c tb r a n c hi na d v a n c e ，s ot o m a k eu pt h ei n s u f f i c i e n c yo f b r a n c hp r e d i c t o ra n db r a n c ht a r g e tb u f f e r , a n dc o n s t r u c t si n s t r u c t i o n t r a c e sb e f o r ep r o g r a me x e c u t i o n t h i r d m u l t i p l ep a t h sc o n t r o lm e c h a n i s mi sd e v e l o p e d m u l t i - p a t he x e c u t i o n i sc o n t r o l l e d t h r o u g ht r a c ei d e n t i f i e r , w h i c hi sg e n e r a t e db yc o d i n gb r a n c hd i r e c t i o n si nap a t h t r a c ei d e n t i f i e r b e n e f i t sp r o p a g a t i o no fd a t aa n dc o n t r o lw i t h i nm u l t i p l et r a c e s f o u r t h ，s p e c u l a t i v et r a c ee x e c u t i o nm e c h a n i s mi sd e v e l o p e d t r a c e e x e c u t i o ne x p l o i t s c o n t r o li n d e p e n d e n c e c o a r s eg r a i ni n d e p e n d e n c ei n c o r p o r a t i n gw i t hf i n eg r a i ni n d e p e n d e n c e l e a d st oh i e r a r c h i c a li n s t r u c t i o nw i n d o w , w h i c hr e d u c e si n s t r u c t i o nw i n d o wc o m p l e x i t y w en s es i m p l e s c a l a rs i m u l a t o r ，w h i c hi sd e v e l o p e db yu n i v e r s i t yo fw i s c o n s i n - m a d i s o n ， t oe v a l u a t eo u rm o d e l s i m p l e s c a l a ri saw e l l k n o w nm i c r o - a r c h i t e c t u r es i m u l a t o r w er e w r o t ei c t of i to u rd e s i g n s p e c i n t 9 5b e n c h m a r ks u i t ei su s e dt ov a l i d a t em p t p 第j j i 页 国防科学技术大学研究生院学位论文 w i t hr e s t r i c t e dr e s o u r c e s ，o u rs i r e u l a t i o ni n d i c a t e st h a tm p e b pm e c h a n i s mh a sw e l l c o v e r e dm o s to ft h em i s p r e d i c t e db r a n c h e s ，a n dt p b t pc a ni m p r o v ei n s t r u c t i o nf e t c hr a t e e m c i e n t l y t a k i n go n ew i t ha n o t h e r , t h em p t p m o d e li sag o o dc a n d i d a t ef o ri m p l e m e n t i n gn e x t g e n e r a t i o nm i c r o a r c h i t e c t u r e n l i sd i s s e r t a t i o nm a k e st w om a i nc o n t r i b u t i o n s ：f i r s t ，an o v e lp r o c e s s o rm i c r o a r c h i t e c t u r e m p t pi sf u l l yd e v e l o p e d s e c o n d ，p e r f o r m a n c ee v a l u a t i o no f m p t pi ss t u d i e d k e y w o r d s ：m i c r oa r c h i t e c t u r e ，t r a c ec a c h e ，t r a c ep r o c e s s o r s ，m u l t i p l ep a t he x e c u t i o n ， t r a c ep r e c o n s t r u c t i o n ，b r a n c hp r e d i c t i o nc o n f i d e n c e 国防科学技术大学研究生院学位论文 第一章绪论 微处理器在其三十年的发展过程中，性能以每年3 0 的速度增长。伴随着性能的提 高，微处理器的应用在各个领域取得了巨大的成功和发展，产生了良好的经济效益和社 会效益。应用的深入和发展要求微处理器提供更高的性能，从而推动了微处理器体系结 构的研究不断深入。 微处理器性能的提高主要依靠两条途径：一是半导体工艺的进步，二是处理器体系 结构的发展。就当前的技术现状和储备【i l ，在下一个十年，半导体工艺技术仍将继续推动 处理器的时钟频率和集成度稳步提高。根据摩尔定律预计，到2 0 1 0 年，高性能处理器在 单片上将集成1 0 亿只晶体管。但是，如何有效利用这些数目巨大的晶体管实现更高的性 能仍然是微处理器体系结构研究面临的一个巨大的挑战。 本课题1 在广泛深入地了解当前处理器体系结构研究现状的基础上，分析当前处理器 体系结构研究中的不足，展开对多路径前瞻执行机制的研究，提出了“多路径t m c e 处理 器”( m p t p ) 模型，给出了m p t p 的设计，并通过模拟实验验证m p t p 的设计思想。 1 1研究背景及目标 1 3 。1处理器体系结构研究的机遇和挑战 根据美国半导体工业协会( s i a ：s e m i c o n d u c t o ri n d u s t r ya s s o c i a t i o n ) 1 9 9 8 年的修订 报告，预计2 0 1 0 年左右，单片存储器的容量将达到2 5 6 g b i t s ，商用逻辑电路的晶体管 数目将达到1 8 0 m c m 2 ，届时将出现单片集成l o 亿只晶体管的处理器。 对体系结构的设计师来说，有了这些数目巨大的晶体管是实现更高性能的机会，同 时，如何合理有效地利用这些晶体管达到更高的性能又是次挑战。 首先，超标量处理器的实现复杂。当前，主流处理器大多采用超标量结构，实行指 令的动态调度1 2 “。超标量处理器的动态指令调度机制越来越复杂，指令发射带宽每提高 一倍，调度单元的芯片版图就会翻一番【6 i 。而且，超标量处理器的指令窗口、取指令执 行部件及其运行机制效率均会很低，当处理器的指令流出峰值带宽增加时，关键路径上 执行的指令数并不成比例增加。即增加了指令带宽却没有得到足够的性能。 其次，常规超标量处理器没有能力从串行程序中提取出足够的并行性。由于超标量 处理器的结构局限，使之无法有效地处理程序中的控制相关和数据相关，从而无法区分 本课题的研究得到“九五”国防颈研项目。b s o i ”及湖南省院士基金的赍助 第1 页 国防科学技术大学研究生院学位论文 指令级并行性( i l p ：i n s t r u c t i o n - l e v e lp a r a l l e l i s m ) 。超标量处理器在开发更高层次的指令 级并行性上，面临巨大的困难和挑战。 1 1 2指令级并行性前景 通用程序中蕴含大量的指令级并行性。l a m 7 1 ，a u s t i n s l 和p a n 嘲等人的研究表明：在 通用的非并行化设计的程序中包含了大量内在的并行性。如果指令窗口能够容纳1 k 条指 令，则程序每个时钟周期能够发射的指令数目( 即i p c ：i n s t r u c t i o n sp e rc y c l e ) 大约在1 0 到1 0 0 之间，即理想条件下，每个时钟周期可以并行执行1 0 到1 0 0 条指令。追求更高的 指令级并行性是先进处理器实现单周期多指令发射的原动力。 然而，由于控制和数据相关以及资源约束等原因，处理器体系结构能否从普通的串 行程序中提取出更多的并行性仍然是面临的一个挑战【7 】。当前，微处理器的i p c 总体水平 还没有达到每个时钟周期两条指令，因此，有很大的发展空间。 指令级并行性技术以扩大指令窗口为手段，在一个大指令窗口中灵活调度指令，使 处理器能够在单位时间完成更多指令的并行处理，从而实现加速程序的执行，得到更高 性能的目的。无论是基于硬件的还是软件的方法，扩大指令窗口都是开发更高性能处理 器的基础。 1 1 3主要的处理器结构 当前微处理器体系结构研究的核心问题是支持多控制流，包括直接的或间接的对多 控制流的支持。同时对多控制流的支持将实现更大的指令窗口就可以发射更多可并行 执行的指令，避免了通过正确预测一系列分支指令来扩大单个指令窗口的困难。 超标量处理器i o 重复设置多个流水线功能部件，通过单周期多条指令发射来加速指 令执行。随着发射带宽的增加，动态调度的复杂性问题越来越突出，限制了其规模的进 一步扩大。在大指令窗口中，超标量的动态指令调度机制已越来越力不从心。 单芯片多处理器1 1 1 , 1 2 1 利用芯片的可用资源集成多个简单处理器，通过对称多处理模式 ( s m p ) ，以单个芯片内的低互连延迟解决共享数据访问时间长的矛盾，同时，多个处理 器自主控制，有实现分布处理的能力。但单芯片多处理器对细粒度的并行性无能为力。 同时多线程【”】( s m t ：s i r e u j t a n e o u s m u l t i t h r e a d i n g ) 和前瞻多线程1 1 町( s m a ：s p e c u l a t i v e m u l t i t h r e a d i n ga r c h i t e c t u r e ) 通过支持多个控制线程来增大指令窗口，强调对硬件资源的 有效利用，能够在经济可行的情况下做更宽的超标量实现。但要看到，对每个线程而言 多线程并不能使其主要依赖关系的关键路径缩短，因此，对计算结果起主导作用的延迟 并没有得到隐藏，而且上下文切换还可能增加关键路径上的延迟。除此之外，多线程结 构还存在与当前处理器结构的二迸制兼容问题。 第2 页 国防科学技术大学研究生院学位论文 超长指令字l i s ( v l i w ：v e r yl o n gi n s t r u c t i o nw o r d ) 结构，以及e p i c t ” ( e x p l i c i t l y p a r a l l e l i n s t r u c t i o nc o m p u t i n g ) 结构被认为是静态调度的超标量，在简化处理器实现的复杂性方 面向前走了一大步。在处理媒体类型数据方面，超长指令字结构的处理能力已得到广泛 认同。但就当前的技术发展来看，由于优化编译器技术及程序固有控制流的不确定性， 超长指令字结构的性能潜能还不得而知。此外超长指令字还必须解决与当前的处理器、 以及不同代次的超长指令字处理器间的代码兼容性问题。 t r a n s m e t a 。公司的c r u s o e t m 处理器采用v l l w 的执行内核结合c o d em o r p h i f 技术 用软件实现x 8 6 指令集的二迸制代码兼容印】，在性能上还不能与同一代的超标量处理器 相比。i n t e l 。公司与h p 。合作开发的i a 6 4 ( 1 8 】结构处理器，采用e p i c 结构，虽己历时多年， 仍没有商用的产品面市j 超长指令字和多线程结构被认为是取代超标量结构的比较有潜力的下一代处理器实 现技术。但就现在的发展情况来看，这两种结构还缺乏高效的二进制代码兼容解决方案， 难以展示结构本身的性能潜力。 1 1 4二进制代码兼容 当前，二迸制代码兼容问题已经是涉及到处理器能否有生命力的主要问题。解决二 迸制代码兼容问题已经是处理器必须实现的目标之一。 计算机发展的早期，各种指令集的结构呈现百花齐放的局面，由于当时的数据交换 技术并不发达，指令集结构并没有对计算机技术的发展形成太大的阻碍。八十年代束九 十年代初，还出现了支持不同指令集的多种r i s c 处理器，如a l p h a2 1 x 6 4 系列、m i p sr 系列、p a r j s c 系列、p o w e r p c 系列、s p a r c 系列的处理器。尽管这些处理器都曾试图 在i n t e l 占领的通用处理器市场上一争高下，但由于市场的强大惯性和指令级的不兼容， 都没能撼动x 8 6 及其兼容处理器的市场主导地位，只有a m d 。公司的k 系列处理器，凭 借对x 8 6 的良好兼容性，占据了通用处理器市场的一席之地，并呈现日益壮大的发展趋 势。 进入九十年代，互连网技术大肆兴起，各种软件在互连网上迅速传播，以i n t e l 。的x 8 6 指令集编写的程序更成了互连网上各种应用程序的主流。即便是i n t e l o 公司，在认识到x 8 6 指令集的局限性后也无法全力开拓一种新的结构，首先在以超标量结构实现的p e n t i u m p r o 内核中兼容x 8 6 的c i s c 指令集【1 9 1 ，然后，又在以v l i w 实现的下一代处理器中，设 计了一个支持x 8 6 指令运行的模块i 。同样，t r a n s m e t a 公司开发的c r u s o e 处理器采用了 v l l w 的执行内核来执行x 8 6 指令，是软件实现二进制代码兼容的一个典型。 总之，随着各种应用软件的发展和积累，二进制代码兼容问题已经成为当前处理器 设计时必须要解决的一个主要问题。 第3 页 国防科学技术大学研究生院学位论文 1 1 5 深度前瞻的障碍 前瞻技术是实现太指令窗口、获取更高i l p 的有效途径深度前瞻是进一步扩大指 令窗口的必由之路。但是，深度前瞻带来了一系列问题： 首先是指令流的高速提供问题。在前瞻处理器中，分支预测的失误使读出的指令成 为无用指令。控制流的变化使取指部件不能提供全部的取指带宽，因为指令在c a c h e 中 按照程序顺序排放，指令流的控制转移指令如分支、跳转、子程序调用、以及返回指 令等导致读出的指令块的剩余部分成为无用指令。此外，指令c a c h e 不命中还导致取指 部件等待，在读出指令之前，无法向执行部件提供指令。 其次，前瞻失败的代价越来越大。当前，微处理器为了达到更高的主频，不断细分 流水线。s u n 公司推出的u l t r a s p a r c i i i 处理器的流水线长达2 3 级唧，i n t e l 最新发布的 p e n t i u m4 内核的指令执行流水线就己多达2 0 级，其分支预测错误的代价为1 9 个时钟周 期，如果指令在t r a c ec a c h e 中不命中，则其分支错误预测的代价还要增加。尽管当前实 用的分支预测器己经能够达到9 5 的预测准确率，但要进一步提高分支预测的准确率非 常困难。 再次，存储器的访问速度相比执行部件的执行速度有越来越慢的趋势。半导体存储 器件的性能每年提高大约7 ，远跟不上处理器性能提高的速度，随着c a c h e 进一步扩容 和半导体的纳米效应，未来的处理器对c a c h e 的访问也不可能在一个时钟周期完成，a l p h a t 2 1 处理器访问一级指令c a c h e 需要两个时钟周期就是一个例子。存储器访问周期的增加， 导致前瞻错误的代价进一步增加。 深度的前瞻执行在提高性能的同时，当前瞻失败时，也产生了相反的效果。如果考 虑分支预测的不命中率的累积效应，深度前瞻执行的指令正确递交的概率变得很小，使 前瞻失去了价值。 1 2论文的工作 在深入分析和研究处理器体系结构的研究和发展现状的基础之上，结合半导体技术 的发展前景，本文创新地提出了“多路径t r a c e 处理器”( t p ：m u l t i - p a t ht r a c e p r o c e s s o r s ) 模型。m p t p 以t r a c e 处理器为基础，通过开发控制无关性实现前瞻执行，对 低可预测性分支采取分支两个方向同时执行的机制，减少前瞻失败的代价，开发更高的 指令级并行性。归纳起来，m p t p 的主要特点有： 1 保持与超标量结构的完全二进制代码兼容。m p t p 以多个逻辑连续的指令基本块 构成t r a c e ，作为处理器执行的基本单位。t r a c e 是连续的指令流，因此，无需修改处理 器指令集，也不必加入新的指令来控制t r a c e 的执行。 2 采用层次式的指令窗口管理，有效地扩大了指令窗口，内在地支持前瞻执行，降 第4 页 国防科学技术大学研究生院学位论文 低了大指令窗口的复杂性。m p t p 处理器开发程序的控制无关性，将指令流转换为控制无 关的t r a c e ，从而，将大指令窗口的管理变成了对多条t r a c e 的管理，用简单的、层次式 的机制实现了大指令窗口。 3 m p t p 对低可预测性分支采取分支两个方向同时执行方式，减少前瞻错误的代价。 m p t p 利用晶体管资源丰富的特点，重复设置多个简单的超标量处理器，对程序中的低可 预测性分支，同时执行分支两个方向的指令，减少前瞻错误的开销。 4 m p t p 实现基于分支目标提取的t r a c e 预构机制，减少指令流访问的等待延迟。 为了在程序执行前预先得到指令流t r a c e ，m p t p 根据分支预测器的输出和低可预测性分 支的评估结果，预先构造指令流t r a c e ，对目标地址不明确的分支指令通过指令块的扫描 发现分支并提取分支的目标地址，加速指令块的预取，支持t r a c e 的预构。 概括地说，本文的研究工作与创新主要有四个方面： 1 独创地提出了“多路径t r a c e 处理器”m p t p 模型，深入研究了m p t p 的关键技 术，给出了m p t p 的结构设计，并作实验研究。 2 针对t r a c e 预构的阻塞问题，创新地提出了基于分支目标提取的t r a c e 预构 t p b t p 机制，研究了t p b t p 的实现方法，给出t p b t p 的结构设计，并实验研 究t p b t p 的可行性和有效性。 3 为了有效控制多条路径执行的资源消耗，提出了基于分支可预测性的多路径执行 m 口e b p 机制，深入研究了分支可预测性的评估方法、基于分支可预测性的 路径派生机制、以及以t r a c e 为处理单位的多路径执行控制机制，并实验研究。 4 扩充s i m p l e s c a l a r 模拟器采用s p e c i n t 9 5 程序作为测试集，用模拟实验评价m p t p 及各项关键技术的可行性及性能，证明了m p t p 的可行性和有效性。 1 3论文结构 本文是对我们的研究工作的全面总结，全文共分为九章。 本章介绍当前微处理器体系结构研究面临的机遇和挑战，分析前瞻技术的不足。然 后，介绍了本文的工作和论文的结构。 第二章介绍与本论文紧密相关的处理器体系结构研究现状。内容包括处理器前瞻技 术研究的现状，多路径执行，t r a c ec a c h e 机制，前瞻t r a c e 处理器，t r a c e 预构机制等。 第三章详细阐述m p t p 的设计原则，给出了处理器的结构设计。本章分析m p t p 的 关键技术，比较前瞻t r a c e 处理器与m p t p 的异同。 第四章研究m p e b p 机制。首先介绍分支预测置信度的评估方法，然后通过模拟实验 研究了置信度阀值对路径派生的影响，以及置信度阀值与错误分支预测的覆盖率间的关 系并分析实验的结果。本章还给出了资源约束条件下m p t p 的性能评价。 第5 页 里堕型堂垫查盔堂堑塞生堕堂垡丝奎 第五章给出t r a c e 预处理器t p p 的设计及结构，并重点研究了t p b t p 机制。t p p 以 消除指令读取瓶颈，开发控制无关性，实现t r a c e 构造为目标。t p b t p 机制是t p p 实现 的关键。本章分析动态指令流的分支特征，介绍t p b t p 的工作流程，给出t p b t p 的模 拟实验结果，并作出分析和评价。 第六章主要介绍多条路径的标识、控制、及执行机制。路径的标识从路径中包含的 分支指令的方向编码而来，它是控制路径、t r a c e 及指令正确执行的关键。多路径控制管 理处理器的资源分配，实现正确的程序执行逻辑。 第七章介绍m p t p 的t r a c e 执行机制。t r a c e 执行以开发程序的指令级并行性为主要 目标，提取指令流的控制无关信息，以指令流的控制无关结构实现指令窗口的层次式管 理。t r a c e 执行机制研究t r a c e 在处理单元中执行时，处理单元内部的控制逻辑及与外部 执行的t r a c e 交换数据和控制信息的机制。 第八章介绍本文采用的模拟方法及实验环境。模拟器采用处理器体系结构研究广泛 认可的s i m p l e s c a l a r 模拟器，本章简要介绍模拟器的结构及运行过程。测试程序采用 s p e c i n t 9 5 整数测试集。 第九章是全文的总结，及对下一步工作的展望。 第6 页 国防科学技术大学研究生院学位论文 第二章相关研究现状 本章简要介绍前瞻技术的研究现状，然后分析其不足。前瞻执行在分支没有输出结 果之前就执行分支之后的指令。这是一种不同于程序逻辑的执行方法，因此，前瞻技术 必须解决由此带来的问题。前瞻执行的两个主要的问题是如何获得指令和何时执行指令。 高带宽指令读取机制解决前瞻的指令供应问题，前瞻执行的发射机制解决指令的数据相 关和指令的就绪发射问题。 多路径执行是一种特殊形态的前瞻机制。多路径执行是解决控制流预测错误的一种 手段，它不依赖于分支执行方向的预测，而是沿着分支的两个方向同时执行，是一种特 殊形式的前瞻执行。 本章还介绍与m p t p 处理器模型紧密相关的t r a c ec a c h e 、t r a c e 处理器、t r a c e 预构机 制的研究现状。t r a c ec a c h e 是一种新颖的指令c a c h e ，它保存指令流的轨迹，即程序的逻 辑顺序。t r a c e 处理器模型是以t r a c ec a c h e 为基础的一种新型i l p 处理器。t r a c e 预构是支持 指令预取的一种模式。 2 1前瞻执行技术 当前，计算机仍然采用冯诺伊曼的存储程序式结构。在这种计算模式下，程序顺 序存放在存储器中，当程序执行时首先从存储器读出一条指令，经过译码、执行，然 后将执行结果写回存储器。一般而言，程序中包括计算操作和数据通讯，程序执行则受 到控制结构的约束。提高程序执行速度的基本思想是利用多个硬件资源将多条计算操作 和数据通讯同时进行。 前瞻执行是提高程序执行速度的一种方法。所谓前瞻执行是指将指令的执行提前到与 它控制相关的分支指令输出结果之前进行。深度前瞻是指跨越多条分支的前瞻执行。前瞻 深度即前瞻执行跨越的基本块数目。本节的前瞻执行是指沿着单路径执行的前瞻执行。 程序前瞻执行时，在多条连续的分支的预测输出基础上，构造一条较长的预测指令 路径前瞻执行就沿着这条预测路径的指令进行。但是，当这条预测的路径有分支预测 错误时预测错误的分支之后的指令就要取消，这就是前瞻失败。前瞻失败之后必须恢 复正常的状态，因此，前瞻执行是有负作用的。 根据存储程序式结构的计算模式，前瞻执行必须要解决的两个主要问题是：第一， 如何使处理单元获得指令? 第二如何使获得的指令尽早发射? 其中，第一个问题的实 质是实现高带宽指令读取。 第7 页 国防科学技术大学研究生院学位论文 2 1 1高带宽指令读取 在前瞻执行处理器中，存储系统必须提供足够的指令读取带宽，支持前瞻执行对大 量指令的消耗，因为采用前瞻方式执行指令，每个时钟并行执行的指令数目将大量增加， 如果存储系统不能提供高带宽的指令读取，将导致执行部件的等待。 高带宽指令读取向执行部件高速提供指令。高速提供指令的主要阻碍有： 1 c a c h e 不命中导致取指令部件等待，在指令读出来之前，无法向处理器提供指令， 2 分支预测的失误使读出的指令成为无用指令， 3 控制流的变化使取指部件不能提供全部的指令宽度，这是因为指令c a c h e 以物理 顺序排列，控制转移指令，如条件分支，跳转，子程序调用及返回指令等导致读出的指 令块的剩余部分成为无用指令。 p a t e l ( 2 0 l 研究了s p e c 血9 5 基准测试程序的分支之间指令条数和跳转分支的指令条数分 布，如表2 1 。从表中得到的结论是：如果分支导致的取指浪费不能解决，取指的带宽将 不会超过平均上限，即每个时钟1 0 5 2 条指令。如果不能实现有效的跨分支指令读取，则 前瞻执行不可能开发出更高的指令级并行性。 表2 1 执行分支间的指令数目统计 程序平均分支间指令数转移分支的指令数 c o m d t e s s 9 1 5 1 3 0 7 g c c 5 3 48 4 6 g o 6 2 l9 1 1 1 t d e r 15 5 91 9 1 4 1 i5 5 48 4 1 m 8 8 k s i m4 2 45 7 8 p e r l 6 0 6 9 1 3 v o r t e x 6 5 71 1 0 5 平均值 7 3 41 0 5 2 概括起来，高带宽指令读取技术大致分为两种：基于硬件的指令预取技术和基于编 译的指令预取技术。 基于硬件的高带宽指令读取与分支预测技术紧密相关。在执行部件的指令请求之前 进行的指令读取又称为指令预取。基于硬件支持的预取技术口“2 5 1 通过分支预测得到目标地 址，访问存储器获得指令块，实现同时从多个基本块中提取指令级并行性。 分支预测主要解决两个子问题：第一，预测分支的方向；第二对于跳转分支给出 分支目标路径的起始地址。分支的执行方向一般根据分支历史进行预测。分支目标的预 第3 页 国防科学技术大学研究生院学位论文 测一般是采用分支目标缓冲区b t b 2 s l ，在b t b 中记录分支的转移目标地址。 由于单分支预测方法 2 7 - 2 9 i 每个时钟只能预测一条分支指令的输出，不能满足深度前瞻 处理器的指令读取部件在单周期读取多个指令块的要求，而基本块的平均指令条数限制 了取指部件能够在单周期读出的有效指令数目，多分支预测技术口唧0 5 , 2 2 , 3 1 , 2 4 3 2 3 埘1 应运而 生，它实现单周期多个分支的预测，以协助单周期多个基本块的读取。 高带宽指令读取的另一种技术基于编译器支持的预取从增加取指令的长度，减 少跳转分支的数目出发，将指令重新排序，构造大的基本块。它最初是用于增大优化编 译器的代码视野，特别对于v l l w 机器，对有可能同时执行的一组基本块简化为单个单元 4 ”，这样取指令的有效指令数相应增加，同时减少了分支错误预测的次数。 不论是基于硬件的指令预取还是基于软件的指令预取，其总的目标都是实现向前瞻 执行部件的高速指令发送。 2 1 2前瞻执行的指令发射 在多个执行部件重复设置的情况下，前瞻执行的指令发射主要受到数据相关的制约。 数据相关分为寄存器相关和存储器相关两个方面。前瞻执行的寄存器相关主要有两种解 决办法，第一种解决办法依靠寄存器重命名表来消解寄存器访问冲突，第二种办法是重 复设置多个寄存器文件，分别记录多个前瞻版本的状态。此外，数据旁路是加快寄存器 相关时的数据传输的一种手段。最近的研究中，l i p a s f i t 4 3 i 等人提出了“值局部性”的思想， 研究利用值的局部性来解决寄存器相关问题，采用类似分支预测的机制记录计算指令的 值，并根据值变化的模式预测下一次该计算指令的值，从而达到加速指令发射的目的。 前瞻执行的另外一个问题是存储器访问相关的问题。受访问地址计算的延迟和地址 访问的冲突影响，存储器不能立即提供访问的内容，也会导致执行部件的等待。数据前瞻 是提前访存指令的执行到可能与它具有数据相关的访存指令的执行之前执行，这样访存 指令可以乱序地执行处理器不会因为访存指令的阻塞而长时间地阻塞处理器发射其他 指令执行。数据前瞻技术要求访存控制器在访存指令的存储地址计算出来之前就能处理 这个访存指令，若访存指令前瞻执行错误，还需要进行恢复工作。 m u l t i s c a l a r 处理器中采用的a r b 4 4 】访存单元就是一个利用数据前瞻技术的访存控制 器。在a r b 中，任意一条访存指令只要译码完成就可以发射。s v c t 4 q 改进a r b 的集中控 制机制，采用分布式的控制。s v c 类似于一个私有的一级c a c h e 组织，属于层次式组织的 处理单元，以类似于c a c h e 一致性的监听机制来维护s v c 的一致性。值预测技术开发所谓 的“值局部性”，提出装入值的预测_ i o a dv a l u ep r e d i c t i o n ( l 、厂p 机制1 4 3 】) ，采用类似 于分支预测的机制，记录存储器访问的地址及值，预测下一次的访问地址和数据相关。 当数据相关问题解决之后，如果有空闲的执行部件，指令就可以发射了。跨分支的 乱序执行是前瞻发射指令的一种方式。乱序执行机制下，指令窗口中的指令，只要操作 第9 页 国防科学技术大学研究生院学位论文 数就绪就可以发射，而不必按照程序顺序发射。 由于指令的前瞻发射可能产生正常执行的情况下不会出现的例外，针对前瞻执行的 指令执行不安全的问题，无异常指令技术扩充一组同原有指令系统相对应的无异常指令系 统来支持前瞻执行。编译将不安全的前瞻执行指令变换成相应的无异常指令。从而编译 可以移动不安全的前瞻执行指令。硬件遇到无异常指令即知道这是一条不安全的前瞻性 执行指令，需要按照无异常指令的语意进行特殊的处理。 执行前推技术m 】( b o o s t i n g ) 是一种采用指令标记来区分不同类型前瞻执行的技术。 它允许编译处理任何一种前瞻执行( 包括非法的和不安全的前瞻执行) ，编译把每条前瞻 执行指令按特定的标记方式标记出来，这些标记还标明了指令源自哪个基本块。硬件可 以识别这些标记，并利用硬件资源支持这些前瞻执行指令的执行。硬件对执行前推的支 持程度越大，可得到的前瞻执行深度也越深，硬件开销也越大。 从上面的介绍可以看出：前瞻执行的同时也带来了前瞻实现的代价。前瞻机制中大 量采用预测的思想，随着前瞻的深度越来越深，前瞻机制要记录越来越多的处理机状态 版本，增加了系统复杂性，还加重了前瞻恢复的负担。 2 1 3前瞻执行技术的小结 通用程序中蕴涵大量i l p 。研究证实：在l k 条容量的指令窗口中，理想条件下，每个 时钟能够并行执行的指令数目大约在1 0 n 1 0 0 条