（计算机系统结构专业论文）分片式处理器上激进执行模型分析.pdf

摘要 随着大规模集成电路技术的发展，可用的片上资源越来越多，如何把丰富 的晶体管资源转化为实际的计算能力，是当前体系结构研究中面临的基本问题。 传统的超标量和超长指令字结构，由于采用集中式、全局控制结构以及广播式 数据通路，导致功耗、线延迟和设计复杂度等诸多问题，很难进一步扩展，因 此一种结构模块化、分布化、层次化的分片式处理器体系结构应运而生。分片 式处理器通过资源分布和资源复制策略代替传统集中式控制结构，用点到点片 上数据传输网络取代广播式数据通路，可扩展性大大增强。但在顺序执行模型 下，受编译技术和应用本身的限制，很难充分发掘应用的指令级并行性。因此， 我们提出分片式处理器上基于指令块的激进执行模型。本文针对影响分片式处 理器激进执行模型有效性的几个方面进行了分析和实验验证，为激进执行模型 的实践提供了理论指导。 本文采用理论分析和实验验证相结合的方法，一方面在理论上分析了各种 因素对于分片式处理器激进执行模型的影响，另一方面对这些影响因素建立有 效的实验评价方案和实验环境，进行实验验证。 本文的研究内容和成果包括以下几个方面：( 1 ) 从控制流的角度，分析了 控制相关对于激进执行模型的影响，提出了块级预测技术，设计了一种基于传 统分支预测器的块级分支预测器；并且针对块间的控制相关，提出了自己的实 验评价方案，评价了控制相关对于分片式处理器上激进执行模型有效性的影响。 实验结果表明，由于块级预测具有较高的预测精度，适合深度推测，因而控制 相关对于激进执行模型有效性影响较小。( 2 ) 从数据流的角度，分析了数据相 关对于激进执行模型的影响，提出了块间的数据f o r w a r d i n g 和值预测技术，并 给出了块间数据依赖深度概念。实验表明大部分应用都具有较高的依赖深度， 并且可以通过数据流推测技术进一步减少数据相关造成的等待时延，因而数据 相关对于分片式处理器激进执行模型有效性影响较小。( 3 ) 针对结构相关对于 激进执行模型的影响，分别对各种可能的结构相关因素；进行了分析和实验。 结果表明，结构相关对于分片式处理器激进执行模型几乎没有影响，并且有利 于把更多的片上资源转转化为芯片的计算能力。 本文的实验结果表明，在分片式处理器上引入激进执行模型是完全可行的， 可以通过控制流推测、数据流推测等技术克服块间的控制、数据相关，进一步 扩大分片式处理器的指令发射窗口，发掘应用的指令级并行性。 关键词：分片式处理器激进执行模型控制相关数据相关结构相关 a b s t r a c t w i t ht h ed e v e l o p m e n to fv l s ia n df u r t h e rr i c h e ra v a i l a b l eo n - c h i pr e s o u r c e s ，a n e w c h a l l e n g ei nt h er e s e a r c hf i e l do fc o m p u t e ra r c h i t e c t u r ei sh o wt ot r a n s f o r mt h e i n c r e m e n to fr e s o u r c e si n t oa c t u a lp r o m o t i o no fc o m p u t i n gp o w e r h o w e v e r , t h e t r a d i t i o n a la r c h i t e c t u r es u c ha ss u p e r s c a l a ra n dv l i wi sh a r dt os c a l e ，d u et o i n c r e a s i n gw i r ed e l a ya n dd e s i g nc o m p l e x i t yc a u s e db yt h ei n t r i n s i cc h a r a c t e r i s t i c s ， l i k ec e n t r a l i z e dg l o b a lc o n t r o l ，d a t ap a t hb a s e do nb r o a d c a s t i n g ，e t c t i l e dp r o c e s s o r a r c h i t e c t u r e ( t p a ) i sp r o p o s e da sap o t e n tr e s p o n s et ot h e s ep r o b l e m s i nt h et p a m o d e l ，i n s t e a do ft h et r a d i t i o n a lc e n t r a l i z e dg l o b a lc o n t r o l ，t h ep o l i c yo fr e s o u r c e d i s t r i b u t i n ga n dd u p l i c a t i n gi sa d o p t e d ，a n dr a t h e rt h a nb r o a d c a s t i n gd a t ap a t h ， p o i n t t o - p o i n td a t at r a n s f e rn e t w o r ki si n t r o d u c e d ，w h i c he v i d e n t l yi m p r o v e st h e s c a l a b i l i t yo fp r o c e s s o r n e v e r t h e l e s s ，i nt h es e q u e n t i a le x e c u t i o nm o d e lo nt p a ，d u e t oc o n s t r a i n t so fc o m p i l i n gt e c h n o l o g ya n dt h ea p p l i c a t i o nc h a r a c t e r i s t i c s ，i ti sq u i t e d i f f i c u l tt of u l l ye x p l o i tt h ei l po fa p p l i c a t i o n s s ow ep r o p o s e da na g g r e s s i v e e x e c u t i o nm o d e lf o rt p a i nt h i st h e s i s ，w ea n a l y z ea n de v a l u a t et h ef a c t o r sa f f e c t t h ee f f e c t i v e n e s so ft h ea g g r e s s i v ee x e c u t i o nm o d e lo nt p ai nam e t h o do f c o m b i n i n gt h e o r e t i c a la n a l y s i sa n de x p e r i m e n t a lv e r i f i c a t i o n ，a n dp r e s e n ts o m e i m p o r t a n ti n s t r u c t i o n sf o rt h ed e s i g no fa g g r e s s i v ee x e c u t i o nm o d e lo nt p a t h er e s e a r c hc o n t e n ta n da c h i e v e m e n ti n c l u d e ：( 1 ) f o rt h ei m p a c to fc o n t r o l d e p e n d e n c y o n a g g r e s s i v ee x e c u t i o nm o d e l ，ip r o p o s e t h eb r a n c hp r e d i c t i o n t e c h n i q u ea tb l o c kl e v e l ，a n dd e s i g np r e d i c t o rb a s e do nt r a d i t i o n a lb r a n c hp r e d i c t i o n f o ri t e x p e r i m e n t ss h o wt h a tc o n t r o ld e p e n d e n c yh a sl i t t l ee f f e c to nt h ea g g r e s s i v e e x e c u t i o nm o d e l ，a n dm o s ta p p l i c a t i o n sa c h i e v eh i g h p r e c i s i o ni nb l o c k - l e v e l p r e d i c t i o n ( 2 ) f o rt h ei m p a c to fd a t ad e p e n d e n c yo na g g r e s s i v ee x e c u t i o nm o d e l ，i p r o p o s et h ei n t e r - b l o c kd a t af o r w a r d i n ga n dv a l u e - p r e d i c t i o nt e c h n i q u e ，a n dd e f m e t h ec o n c e p to fd e p e n d e n c yd e p t h e x p e r i m e n t sd e m o n s t r a t et h a td a t ad e p e n d e n c y a l s os h o wl i t t l e i m p a c tt ot h em o d e l ，e i t h e r ( 3 ) f o rt h ei m p a c to fs t r u c t u r e d e p e n d e n c yo nt h ea g g r e s s i v ee x e c u t i o nm o d e l ，ie v a l u a t e da l lp o t e n t i a lf a c t o r si n s t r u c t u r e ，e s p e c i a l l yt h et o p o l o g yo fn e t w o r k a n da g a i n ，t h er e s u l t ss h o wt h a t s t r u c t u r e d e p e n d e n c yh a sa l m o s tn oi m p a c to n t h em o d e la n de v e np r o m o t e s e x p l o i t i n gi l p 、i mo p t i m i z a t i o n i ns u m m a r y , t h i st h e s i sd e m o n s t r a t e st h a tt h ea g g r e s s i v ee x e c u t i o nm o d e li s f e a s i b l et oe n h a n c et h et i l e dp r o c e s s o ra r c h i t e c t u r e ，i n c r e a s i n gt h es i z eo fi n s t r u c t i o n l i i s s u ew i n d o wa n df u r t h e re x p l o i t i n gt h ei n s t r u c t i o nl e v e lp a r a l l e l i s m ，t h r o u g h m u l t i p l et e c h n i q u e st oe l i m i n a t et h ec o n t r o ld e p e n d e n c y , d a t ad e p e n d e n c ya n d s t r u c t u r ed e p e n d e n c ya m o n gb l o c k s k e y w o r d ：t i l e dp r o c e s s o ra r c h i t e c t u r e ，a g g r e s s i v e e x e c u t i o nm o d e l ，c o n t r o l d e p e n d e n c bd a t ad e p e n d e n c y ，s t r u c t u r a ld e p e n d e n c y i i i 图目录 图目录 图1 ，1m u l t i s c a l a r 结构示意图5 图1 2r a w 处理器结构示意图6 图2 1t p a p i 处理器整体结构1 2 图2 2 全局控制模块内部结构1 3 图2 3 寄存器，数据c a c h e 数据传输示意图1 4 图2 4t p a p i 执行单元结构1 5 图2 5t p a p i 指令集1 8 图2 6 数据流执行模型示意图1 9 图2 7t p a - p i 顺序执行模型2 0 图2 8t p a p i 激进执行模型2 1 图3 1 块级预测器整体构造2 5 图3 2 基于全局历史的预测器2 6 图3 3 基于局部历史的预测器2 6 图3 4 锦标赛预测器2 7 图3 5 块转移目标预测2 8 图4 。lt p a - p i 指令块形成示意图3 3 图4 2 一定深度下预测性能变化3 5 图4 3 预测深度分布3 6 图4 4 不同应用期望预测深度3 7 图4 5 改进前后期望深度变化3 9 图5 1 偶久p i 上数据相关示意图4 0 图5 2 指令块内部静态指令分布4 4 图5 3 指令依赖距离分布示意图4 5 图5 4 依赖深度示意图4 6 图5 5 加入值预测后依赖深度变化4 7 图6 1t p a p i 处理器取指流水过程5 0 图6 2t p a p i 内部路由结点结构5 l 图6 3 四种点到点网络拓扑结构5 2 图6 4 不同网络拓扑延迟分析5 3 v i i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名： 签字日期： , 7 , t o 尹r 罗 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 玉开口保密( 年) 作者签名： 蚪 签字日期： 婴2 ：! l 导师签名： 签字日期：竺掣 第1 章绪论 1 1 课题研究背景 第1 章绪论 自摩尔定律提出以来，半导体工业和大规模集成电路就一直飞速地发展着， 芯片的集成度以每1 8 个月翻一番的速度递增，芯片的体系结构也日新月异，各 种深度流水高主频的芯片频频问世。在这个过程中，体系结构界一直在探索着 如何能把日益增多的片上资源转化为计算能力，从而加速应用的处理速度、发 掘程序的并行性( m a r kh o r o w i t zc ta l ，1 9 9 9 ) ( c h r i s t o f o r o sk o z y r a k i s ，1 9 9 8 ) 。 对体系结构的研究，发掘应用的并行性，主要分为三个方面：指令级并行 性、数据级并行性和线程级并行性。其中指令级并行性包括通过流水线技术实 现指令之间的重叠，通过多发射或超长指令字技术实现空间重复，以及通过乱 序执行技术充分发挥流水线的效率。数据级并行性主要使一条指令完成对多个 数据的相同操作，主要包括向量处理技术及单指令流多数据流技术( s i m d ) 。 在线程级并行性方面，主要包括同时多线程技术( s m t ) 和片上多核( c m p ) 技术( j l h e r m e s s ye ta l ，2 0 0 3 ) ( k r s t ea s a n o v i ce ta l ，2 0 0 6 ) 。 指令级并行性的开发，是发掘应用并行性的主要思路，主要包括超标量( 超 流水线) 以及超长指令字技术。超标量技术利用硬件资源发掘指令级并行性， 技术发展十分成熟，是目前微处理器技术的主流。目前大多数r i s c 处理器如 m i p s 、a l p h a 和s p a r c 等都采用超标量技术，而代表个人p c 处理器主流的 i n t e l 、a m d 处理器i a 体系结构( c i s c ) ，也采用超标量技术。另一种开发指 令级并行性的方法是超长指令字技术( v l i w ) ，这是一种基于软硬件协同的方 法。由软件编译技术发掘应用的并行性，而硬件仅仅提供并行计算资源，不负 责发掘并行性。v l i w 技术广泛应用于d s p 领域( j l h e n n e s s ye ta l ，2 0 0 3 ) 。 数据级并行性的开发，主要包括向量处理技术和s i m d 技术，前者主要用 于高性能计算机系统领域。数据级并行性的开发对应用的特性要求很高，非常 适合如图形图像处理等专门领域的应用，而对通用的桌面应用适用性较差。如 目前出现的流媒体处理器，大多是针对某些特殊应用领域而开发。在通用处理 器上，往往可以集成某些数据级并行模块，加速专门应用，如p 4 的s s e 2 媒体 加速部件等( k r s t ea s a n o v i ee ta l ，2 0 0 6 ) 。 线程级并行性的开发，主要包括多线程应用的s m t 技术和多进程的c m p 技术，结合软硬件的协同开发，如编译技术、线程级推测、t m 等，可以用于 加速应用，开发线程级并行性( k r s t ea s a n o v i ce ta l ，2 0 0 6 ) ( f p l l a c ke ta l ，19 9 9 ) 。 第1 章绪论 上述提及的各种开发应用并行性的方法，都存在着各种各样的不足或弊病。 特别是随着大规模集成电路的进一步发展，片上资源进一步增多，它们已经很 难把大量的片上资源转换为计算能力。代表指令级并行性开发主流技术的超标 量技术，虽然研究表明应用的i l p 能够达到4 1 0 ，但目前能够发掘的并行性只 能达到2 4 ，而且很难进一步开发。一方面，由于目前的超标量体系结构基本 上采用深度流水技术，而目前的处理器流水线深度已经相当高，如i n t e l 微处理 器的流水线深度达到2 0 - 3 0 级，已经接近极限；另一方面，由于线延迟的增加， 扇入扇出系数的膨胀，基于广播的数据通路也很难满足高主频要求( d m a t z k e ， 1 9 9 7 ) ；再者，集中式控制结构也导致处理器芯片逻辑的过于复杂，难于扩展。 而数据级并行性的开发，由于其受应用本身的影响巨大，很难适用于一般的应 用，开发潜力有限( va g a r w a le ta l ，2 0 0 0 ) ( b r a d f o r dm b e c k m a n ne ta l ，2 0 0 4 ) 。线 程级并行性开发采用软件协同技术，软件方面包括线程的切割划分等，很难达 到很好的性能要求，而且线程级并行性存在着串行程序移植困难、对于细粒度 并行性开发开销大等缺点。 总之，大规模集成电路的发展以及传统开发应用并行性技术的不足，要求 能够开发出能更好地发掘应用并行性的新技术的出现，即新型体系结构的产生。 分片式处理器就是满足这一状况而开发的新式体系结构，主要为了更有效地发 掘应用的指令级并行性，一方面克服超标量处理器线延迟增加、扩展性难、集 中控制难于设计等不足，同时吸收线程级并行开发技术软硬件协同开发的优点 a g a r w a le ta l ，2 0 0 0 ) 。分片式处理器一般采用资源分片和资源复制策略代替传 统超标量集中式控制结构，设计复杂度大大降低；利用点到点片上数据传输网 络取代超标量处理器上广播式数据通路，避免了长线延迟的存在，可扩展性大 大增强；并且通过软硬件协同开发的方式发掘应用的并行性，提供了统一的编 程模型。t p a - p i 处理器是基于德克萨斯奥斯汀大学提出的t r i p s 体系结构开发 的一种典型的分片式处理器，其设计思路主要包括以下方面：首先通过编译技 术，应用被切割成一系列的指令块，在块内采用数据流驱动执行，而块间采用 控制流的方式执行；然后，根据编译阶段优化调度等，这些指令块被取到执行 单元阵列上执行；指令执行结束，数据被送到相关指令的指令槽，驱动下一条 指令的执行，数据的传输通过专门的点到点网络进行，克服了长线延迟的缺点； 块与块之间采用控制流方式，可以通过块级的预测技术，进一步提高应用的并 行性，扩大发射窗口；指令单元、寄存器以及指令和数据c a c h e 均采用阵列分 布方式，便于扩展：整个处理器核由大量简单的执行单元构成，但执行单元之 间无需流水，克服了集中控制的缺点，便于设计实现f n r a n g a n a t h a ne ta l ， 2 0 0 2 ) ( d b u r g e re ta l ，2 0 0 4 ) 。 2 第1 章绪论 t p a p i 处理器顺序执行模型是个指令块执行完成提交之后才开始下一 个指令块的取指工作，这种方式很难充分利用处理器的处理能力，对指令级并 行性的开发效果也不好。在顺序执行模型下，一方面，虽然硬件提供了足以多 个块同时处理的能力，但由于执行模型的限制，只有很少的一部分得以利用； 另一方面，发射窗1 3 仅仅是一个指令块的大小，受编译技术的限制，所能达到 的发射窗口很小，应用的并行性难以被有效开发。实际上，如果能够把应用执 行路径上多个指令块提前取指到硬件资源上执行，无论是硬件资源利用率还是 应用的并行性的发掘都可以大大提高。实验表明，在目前的硬件资源条件下( 目 前t p a p i 处理器提供同时8 个块的执行硬件资源) ，在执行路径上8 0 有效指 令块被预取执行时，有效发射窗口可以提高4 倍以上。因此，采用顺序执行模 型的分片式处理器难以充分利用硬件资源发掘应用的并行性，对并行性的开发 和资源利用率都较差，寻找一种好的执行模型变得十分必要。而前述众多的分 片式处理器和传统的超标量结构采用的基于控制流推测和数据流推测技术的激 进执行模型，这种执行模型能否被有效引入到分片式处理器及可能存在的问题， 是体系结构界必需研究的课题。 1 。2 本文的相关工作 1 2 1 分片式处理器结构及其激进执行模型 1 2 1 1t r i p s 处理器 t r i p s 是u t - a u s t i n 大学提出的一种新型体系结构，整个处理器采用显式 数据流图的执行模型：在指令当中指定数据的目标地址，从而驱动相关指令的 执行，这类似于传统的数据流处理器。但这些指令被划分成一个个的指令块， 块之间的依赖关系的解析是通过寄存器和存储器相关决定的，这又类似于传统 的控制流机器的实现( d b u r g e re ta l ，2 0 0 4 ) ( 董立平等，2 0 0 6 ) 。 t r i p s 处理器核是一个单元阵列结构，拥有一个称为g t i l e 的全局控制器， 控制着整个处理器的取指、预测、提交和刷新。第一排还有4 个称为r t i l e 的 阵列单元，是四个独立的寄存器组，每组8 个寄存器，因此每个线程在其上可 以使用3 2 个寄存器进行重命名：全局控制器下4 个单元称为d t i l e ，即数据 c a c h e ，t r i p s 的指令和数据c a c h e 是分开的，以提高访问速度；右下角的4 木4 阵列称为e - t i l e ，是执行单元阵列。所有这些阵列单元是通过一些独立的片上网 络连接在一起。包括数据传输网络，进行操作数的传输；取指网络，完成取指 到执行单元；刷新、提交网络，报告完成网络等等( va g a r w a le ta l ，2 0 0 0 ) ( 9 b u r g e re ta l ，2 0 0 4 ) 。 第1 章绪论 t r i p s 处理器采用激进执行模型，即通过块级预测机制，提前预取和处理 执行路径上的指令块，使得处理器核上同时处理的指令块数达到8 ，发射窗口 大大提高，能够很好地发掘应用的并行性，硬件资源利用率也较高。t r i p s 处 理器上块级预测是通过g t i l e 中的预测器进行的，这是一种基于a l p h a 2 1 2 6 4 锦 标赛预测器的块级预测器，与传统的预测器有着明显的区别。整个处理器核执 行过程中，同时处理的多个指令块除了第一个块之外，其它的都处于预测态执 行，即通过块级预测器预测后预取指执行的( r k e s s l e re ta l ，1 9 9 9 ) 。 t r i p s 是一种细粒度的资源分片结构，通过资源分片和资源重复，芯片设 计的复杂度大大降低，处理器的可扩展性也得以提高。t r i p s 是利用软硬件协 同开发应用指令级并行性的典型结构，利用编译策略把应用编译成能够映射到 硬件结构上的指令块，指令块内部指令的位置和通信都由编译器来完成。相比 之下，硬件的功能就要少一些，但这也是降低设计复杂度的新思路。并且，t r i p s 的指令间通信方式也很有特点，那就是指令块内部采用显式的数据流驱动方式， 而指令块之间则形成一种对于存储器或者寄存器的相关性。因此，可以说t r i p s 结构是把传统的数据流机器和控制流结构相结合较好的方式。 1 2 1 2m u l t i s c a l a r 处理器 m u l t i s c a l a r 处理器体系结构是威斯康星大学针对超标量处理器在进一步发 掘指令级并行性存在困难而提出的一种新型体系结构。针对超标量处理器集中 式结构以及纯粹使用硬件资源发掘并行性存在着众多的缺陷：首先，由于分支 指令的大量存在平均每5 条指令中即存在一条分支跳转指令，而分支预测 不能达到理想精度的前提下，发射窗口无效的部分比例很高；其次，采用集中 式结构条件下，由于每一条指令都要与所有指令间进行相关检测，使得发射的 复杂度很高，很难进一步扩大发射窗口；再者，对于存储器相关，l o a d 和s t o r e 不可以被重定序，任何一条未被进行地址解析的l o a d 、s t o r e 指令都将导致整 个处理器的阻塞，降低了效率。于是，一种基于软硬件协同开发指令级并行性 的新型体系结构m u l t i s c a l a r 被提了出来，整个处理器结构如图1 1 所示： 4 第l 章绪论 图1 1m u l t i s c a l a r 结构示意图 m u l t i s c a l a r 是一种软硬件协同的体系结构模型。软件方面，编译器把程序切 割成大的指令块，并把块的边界做好标记，以便硬件识别；每一个指令块叫做 一个任务，每个任务有一个任务头，头中包含标记信息，还有寄存器操作的 f o r w a r d i n g 位和停止位；当寄存器的值产生且f o r w a r d i n g 位被设置的时候，该 值被f o r w a r d i n g 出去；碰到停止位，就表示块的执行完成。硬件方面，首先有 多个超标量处理单元，进行块的执行；然后有一个称为顺序器的装置，负责块 之间相关性的检测，块级的预测机制以及块的提交和刷新等；另外，还有一个 成为a r b ( 地址解析缓存) 的结构，用于缓存预测执行下解析出l o a d 、s t o r e 指令地址及值。注意到m u l t i s c a l a r 对于寄存器相关和存储器相关的处理是不同 的，前者采用f o r w a r d i n g 技术，数据未到达则等待，而后者采用激进方式执行， 即不管任务之间的依赖与否都不等待，但一旦检测到存在相关性才进行违例处 理( g u r i n d a rs s o h ie ta l ，19 9 5 ) 。与t r i p s 类似，m u l t i s c a l a r 也是一种资源分片 结构，但相比前者，资源分片的粒度较高；并且它们都采用软件进行指令块划 分和块级推测技术，使处理器上能够同时处理多个指令块，从而提高发射窗口， 发掘应用并行性，因此m u l t i s c a l a r 也是一种激进的块执行模型。 m u l t i s c a l a r 处理器的结构和执行模型表明：由于每一个处理单元存在独立的 发射窗口，整个处理器核的发射窗口则可以达到极高的水平；而对于每一个处 理单元来说，它发射的指令数不是很多，因此发射的复杂度大大降低；由于采 用很激进的执行模型处理存储器相关，使得避免了因为l o a d s t o r e 操作而使整 个处理器阻塞的可能性。相对于v l i w 体系结构，m u l t i s c a l a r 克服了过于依赖 软件优化带来的不足。m u l t i s c a l a r 本身与c m p 结构极为相似，但由于多个处理 单元集成于一个片上，通信延迟降低，对于开发细粒度的并行性更有效。 第1 章绪论 1 2 1 3r a w 处理器 m i t 的r a w 处理器是最早提出分片结构的一种新型体系结构，其针对目前 处理器频率增加、集成电路飞速发展导致单周期信号传输距离下降的问题，提 出了静态动态网络概念。该思想对于我们研究分片式处理器数据通路有着很好 的借鉴意义。r a w 处理器整体结构如图1 2 所示( m b t a y l o re ta l ，2 0 0 4 ) 。 图1 2r a w 处理器结构示意图 r a w 处理器由1 6 个相同的用于运算处理的分片单元( t i l e ) 构成，每个分 片单元类似m i p s 处理器单指令发射内部处理计算流水线和动静态网络构成。 每个分片单元可以作为具有独立程序计数器的处理器工作，当指令或数据缓存 发生错误时，则可从配置在外的主存获取数据。分片单元间的通信必需借助寄 存器，所有布线设计均短于分片单元的单边长度。因此，即使是根据应用的要 求或晶体管数目的提高，而增加集成的分片单元数也不会降低处理器的工作频 率。从图可见，如果单位不限距离的延迟为1 个时钟周期的时候，最远距离间 的通信大概需要6 个周期的延迟。分片单元的运算流水线由八级流水构成，每 条流水线都采用单指令发射的简单结构。尽管一个分片单元每个周期只能发射 一条指令，但1 6 个单元一共可以发射1 6 条指令，从而达到较高的峰值性能。 另外，在流水线的数据通路上，还设立了专门的通信机构，从而大大地降低了 分片单元间的通信延迟似b t a y l o r , 2 0 0 2 ) 。 脚处理器也是一种资源分片结构，它的分片粒度比t r i p s 和m u l t i s c a l a r 更高，并且与上述两种资源分片结构相比，r a w 更多依赖于硬件发掘应用的并 行性。r a w 的激进执行模型更多类似于传统的超标量处理器上的激进执行方 式，本文下一节将详细介绍。 6 第1 章绪论 1 2 2 传统超标量处理器上激进执行 激进执行模型在传统的超标量处理器上得以广泛采用。一方面通过控制流 推测技术，克服指令间控制相关，进行指令预取和乱序发射；另一方面，通过 值预测等技术克服指令间数据相关，加速指令推进。本节将着重介绍传统超标 量处理器上控制流推测和数据流推测技术。 1 2 2 1 控制流推测技术 控制流推测技术，即分支预测一直是提高通用处理器性能的重要方法。分 支预测的本质是克服指令的控制相关，提高指令并行度，从而使处理器的性能 得到提高。分析表明，在深度流水的超标量处理器上，分支预测的准确率还会 极大地影响取指带宽的利用率。在5 发射1 0 级流水条件下，预测准确率为9 0 时，带宽会浪费4 7 ；而当预测准确率提高到9 6 时，带宽浪费可降低至2 6 。 分支预测技术对于传统的超标量处理器性能十分关键，因而很多小组对其进行 了大量的研究。这些研究工作对于寻找块级的预测机制也有很大的帮助。 早期的处理器上采用静态分支预测技术，最简单的静态分支预测技术莫过 于总是预测跳转或者不跳转，这种预测机制优点是预测开销小、速度快，但预 测精度很差，而且受应用影响很大。一般来说，预测精度为4 0 6 0 。针对简 单分支预测的不足，有人提出改进方案：如果分支地址是正增加，就预测不跳 转，否则预测跳转，这种算法对单循环很有效，但性能还是不好，这两种机制 的共同优点在于硬件开销很小，所以在半导体工业发展的初期，芯片集成度还 不是很高的时候，曾经被广泛使用，比如i b m 3 6 0 3 7 0 ( d w a n d e r s o n ，1 9 6 7 ) 。 现在的应用程序大概5 7 条指令当中就有一条分支指令，这种预测精度根本无 法满足处理器高性能的需求，因此在现代通用处理器上已经消失，但在某些嵌 入式处理器上还在使用。 在静态分支预测之后，学术界开始在编译器上开展了基于分支的剖析研究。 即先运行一遍程序，把运行过程中分支跳转信息记录下来，然后把这些信息告 诉编译器，进行重新编译，并在程序当中记录这些信息以便进行分支预测，这 样就在静态分支预测的基础上提高了分支预测精度。但由于程序当中能够记录 的信息有限，这种方式也不能达到很好的性能( j a f i s h e r , 1 9 9 2 ) 。基于剖析的 思路作为体系结构研究过程当中的一种很有生命力的思维方式，其研究适用度 是很广的，虽然仅就分支预测方面来说，其性能或许不是太佳，但把这种思路 用于指导处理器执行，采用软硬件结合的方式，对于提高资源的利用率以及降 低处理器的功耗等等，都会带来意想不到的结果。 为了进一步提高预测准确率，学术界开始提出动态的分支预测技术。其中 第1 章绪论 最简单的就是动态i 位分支预测，基本思想就是本次预测的结果与上次产生的 结果相同。后来又产生了两位分支预测器，即分支预测的结果一次错误不能改 变下次预测结果，而只有两次才能够改变预测模式( j ，e s m i t he ta l ，1 9 8 1 ) 。 动态分支预测器是现代高性能处理器预测器的最主要的方式。对于其性能 的提高特经历了很长的发展历程。如最早并不是采用基于历史的分支预测器， 这种忽略了不同分支之间的相关性，从而产生了两级分支预测技术。对于动态 分支预测过程中可能产生的分支别名问题的研究，又促使了g - s h a r e 预测器的产 生。随着分支预测研究的深入，学术界认识到分支预测的本质是机器学习问题， 而机器学习已经在模式识别、自动控制等领域进行过大量研究，其中神经网络 是目前机器学习的有效方法。罗格斯大学的d a n i e l a j i m e n e z 最先在2 0 0 1 年的 h p c a 会议上将神经网络引入分支预测领域。研究表明，对于4 k 的硬件开销， 采用s p e cc p u 2 0 0 0 基准测试程序，神经网络分支预测器误预测率要比g - s h a r e 降低2 6 ，比组合分支预测降低了1 2 。将神经网络引入分支预测领域，使得 分支预测研究又开始活跃，许多新的分支预测机制被提趋( d a n i e la j i m e n e ze t a l ，2 0 0 2 ) 。 控制流推测技术的发展一直伴随着处理器的发展，分支预测对于处理器性 能的提高起着重要作用。当预测精度达到一定高度的时候，分支预测精度就很 难提高，这是由于某些应用特性未被发现，如分支相关、别名等。每当发现一 个瓶颈，分支预测技术都将得到一次提升。然而随着不同应用被开发出来，各 种新的预测行为也产生了，如近年出现的块执行模型，需要我们对块级的分支 预测技术进行一定的研究。 1 2 2 2 数据流推测技术 数据流推测技术即值预测技术在传统的超标量处理器上也得以广泛的研 究。值预测技术是为了克服指令间的数据相关性，包括寄存器相关和存储器相 关，主要利用的是程序当中寄存器或存储器数据的局部性。 值预测的概念最早由l i p a s t i 等人提出，并且提出了一种称为l a s t v a l u e 的 值预测技术，即采用先前出现的历史值作为后续的预测值的方式。这种简单的 值预测思路是否成功，取决于数据局部性和再现率。在l i p a s t i 等人的设计当中， 值预测单元包括一个分类历史表和一个值预测表，利用当前指令的p c 值索引 值预测表，就可以得到当前的预测值；但对每一个值，是否采用预测值还需要 利用p c 索引历史分类表决定。即该预测单元把寄存器和存贮器历史进行分类， 只有部分地址采用值预测机制。l i p a s t i 等人的研究结果表明，寄存器值的再现 率往往比较高，值预测效果较好；在p o w e r p c 上采用该机制以后，处理器性能 获得4 5 0 2 3 的提高( m l i p a s t ie ta l ，1 9 9 6 ) 。 、 8 第1 章绪论 随着值预测技术的进一步研究，人们逐渐发现某些寄存器值虽然采用上述 l a s t - v a l u e 无法进行有效预测，但其值的变化具有一定规律，如线性增长规律等。 这与程序设计当中循环控制变量等变化规律很类似。为此，有人提出了基于先 前两个历史值的s t r i d e v a l u e 机制。l a s t - v a l u e 可以看作s t r i d e v a l u e 两个历史值相 等的特殊情况，而对于前述满足一定增长规律的寄存器值变化，s t r i d e v a l u e 也 能较好地把握，因而性能得到一定的提高。 前述的l a s t v a l u e 和s t r i d e v a l u e 预测技术都局限于寄存器值，而对于存储器 的值预测，有人认为可以用最近s t o r e 的值预测将来要l o a d 的值。y i a n n a k i s 等 人对数据相关推测( d a t ad e p e n d e n c es p e c u l a t i o n ) 和数据相关链压缩( d a t a d e p e n d e n c ec o l l a p s i n g ) 两种技术的性能潜能进行了分析，将两种技术结合使用 可以将性能提高2 0 - , - 6 6 ，这其中数据相关链压缩技术的贡献占了性能提升的 主要部分f t g a b b a ye ta 1 1 9 9 6 ) 。 1 3 本文的研究工作 在分片式处理器结构上，程序被划分成一个个大小有限的指令块，并且受 编译技术的制约，指令块中有效指令较少。因此，采用顺序执行模型时，整个 分片式处理器的发射窗口较小，对应用并行性的发掘和硬件资源的利用率都较 差。如何有效地把硬件资源转换为芯片有效的计算能力，进一步发掘应用的指 令级并行性，提高处理器计算能力，成为急需解决的问题。 上一节讲到，在传统超标量处理器上，通过控制流推测技术和数据流推测 技术，指令受控制相关和数据相关所需等待的时间减少，并行度大大提高，因 而可以较好地发掘应用的指令级并行性。在近年出现的众多资源分片结构当中， 也引入了激进执行方式，即通过控制流或者数据流推测技术克服指令( 指令块) 问控制相关和数据相关，进一步扩大处理器发射窗口，发掘应用的并行性，处 理器性能得以提高。因此，在分片式处理器上引入激进执行模型，扩大发射窗 口、充分利用硬件资源发掘应用的并行性变得十分必要。本文以分片式处理器 t p a p i 为例，分析分片式处理器激进执行模型面临的问题和影响因素，对分片 式处理器引入激进执行模型有效性进行讨论。 在t p a p i 处理器上，指令块内部采用数据流驱动执行方式，但不同的指令 块之间却采用控制流驱动方式，不同的指令块之间存在着控制相关和数据相关。 控制相关和结构相关的存在，极大