（计算机系统结构专业论文）多核结构上的线程级推测关键技术研究.pdf

摘要 摘要 进入2 1 世纪以来，随着半导体工艺技术的发展，微处理器芯片体系结构由 于受到功耗与设计复杂度等问题的限制开始进入多核时代，但是传统的串行程 序模型与串行地址空间模型并没有发生实质性变化，并行的多核结构模型与串 行的计算理论模型之间发生了矛盾。线程级推测技术的提出为缓解这一矛盾， 使用多核结构加速串行程序提供了可能。目前，有关该技术的研究仍然停留在 学术研究阶段，距离应用还有较大的距离，仍有许多关键技术有待深入研究。 因此“多核结构上的线程级推测关键技术研究”对于探索在多核微处理器芯片 上加速传统串行应用的有效方法具有重要的学术意义和实际应用价值。 本文围绕线程级推测的若干关键技术问题开展了深入系统的研究，主要涉 及线程级推测并行性的定位与分析、线程级推测程序的表示与变换、支持线程 级推测的单芯片多处理器( c h i pm u l t i p r o c e s s o r ，c m p ) 结构模型三个方面。( 1 ) 在线程级推测并行性的定位与分析的研究中，本文提出了判定“特定应用程序 是否适合推测执行”的准则，以及分析、定位应用程序中线程级推测并行性的 理论与方法，并设计实现了针对线程级推测的剖析工具。( 2 ) 在线程级推测程序 的表示与变换的研究中，本文为实现循环结构和子程序结构的线程级推测执行， 设计实现了基本的运行时系统，完成了循环结构和子程序结构的线程化执行， 简化了线程级推测程序的设计，并通过扩充系统调用的方法避免了对编译器的 大幅度改动。( 3 ) 在支持线程级推测的c m p 结构模型的研究中，本文考察了在c m p 结构上实现线程级推测所需的硬件支持，提出了一种线程级推测硬件体系结构 模型。( 4 ) 搭建了多核芯片结构的行为级模拟实验平台，开展了软硬件协同的性 能分析与优化工作。通过大量的实验，完成了对多核芯片基本设计空间的搜索， 获得了对线程级推测技术中的若干关键问题的新认识。 本文选取s p e cc p u2 0 0 0 中的程序作为研究对象。通过对应用程序中固有 的线程级推测并行性的研究，我们发现：( 1 ) 程序中存在着大量的返回值可预测 的子程序结构，这些子程序结构平均占据了超过5 0 的运行时间，简单的 l a s t v a l u e 函数返回值预测方案已经足以取得令人满意的预测成功率。( 2 ) 程序 中粒度较小的循环结构较粒度较大的循环结构多，循环展开合并技术对于控制 推测线程的粒度是必要的。( 3 ) 无论是循环结构还是子程序结构，访存数据依赖 摘要 都是普遍存在的，在推测执行的过程中适当地插入同步与通信对于提高线程级 推测的性能具有重要意义。( 4 ) 由于受到应用本身并行特性的限制，基于4 发射 超标量内核的线程级推测技术所能有效利用的处理器内核数目小于4 。 通过搭建具体的行为级模拟平台、开展软硬件协同的性能分析与优化，我 们还发现：( 1 ) 单一总线互连网络很难承担线程级推测执行过程中的数据通信负 载，按照功能分裂总线的多总线互连方案可以在一定程度上缓解该问题，但是 当处理器数目大于4 时；多总线互连方案将成为系统性能瓶颈。( 2 ) 使用复杂的 宽发射处理器内核( 发射宽度大于2 ) 构造线程级推测系统是不必要的，但是乱序 发射技术是必须的。( 3 ) 线程级推测的性能很大程度依赖于编译技术，优化的线 程划分方案与适当的同步通信机制是影响线程级推测性能的两个关键因素。 关键词：多处理器芯片体系结构线程级推测多线程程序设计程序剖析 编译优化性能评价 a b s t r a c t a b s t r a c t e n t e r i n gt h e2 1s tc e n t u r y ，w i t ht h ed e v e l o p m e n to fi n t e g r a t e dc i r c u i tt e c h n o l o g i e s ， t h ep r o c e s s o ra r c h i t e c t u r eh a v es t e p p e di n t oat i m eo fm u l t i c o r es i n c et h ec o n s t r a i n t o fp o 、v e rc o n s u m p t i o na n dd e s i g nc o m p l e x i t y h o w e v e r ， t h et r a d i t i o n a ls e r i a l p r o g r 锄m i n gm o d e la n dl i n e a ra d d r e s ss p a c em o d e lh a v en oe s s e n t i a lc h a n g e ，ag 印 a p p e a r e d b e t w e e nt h e p a r a l l e l a r c h i t e c t u r ea n dt l l es e r i a l c o m p u t i n gm o d e l t h r e a d - l e v e ls p e c u l a t i o n ( t l s ) w a sp r o p o s e dt on 1 1 t h i sg a pa n dm a d ei tp o s s i b l et o s p e e d u pt h et r a d i t i o ns e r i a lp r o g r a mv i am u l t i c o r ep r o c e s s o r b u tn o w ，t l sw a ss t i l i i nt h es t a g eo fa c a d e m i cr e s e a r c ha n ds t i l lh a v eal o n gd i s t a n c et op r a c t i c a lu s e ，a n d t h e r ea r eal o to fp i v o t a lq u e s t i o n sn e e dt 0a n s w e r ，s o “s t u d yo nt h ek e yt e c h n o l o g i e s o ft h r e a d l e v e ls p e c u l a t i o no nm u l t i c o r ep l a t f o n n ”w a ss e l e c t e da st h et i t l eo ft h i s d i s s e r t a t i o n i nt h i sd i s s e r t a t i o n ，w eh a v es t u d i e dt h r e ef i a c e t so ft l s ：a n a l y s i sa n dl o c a t i n go f t l sp a r a l l e l i s m ，t l sp r o g r a m m i n ga n dc o d et r a n s f o r m a t i o n ，a n dt l sa r c h i t e c t u r e s u p p o r tf o rc h i pm u l t i - p r o c e s s o r ( c m p ) ( 1 ) i nt h ei n v e s t i g a t i o no ft l sp a r a l l e l i s m s l o c a t i o na n da n a l y s i s ，w ep r o p o s e ds e v e r a lc r i t e r i o n so f j u d g i n gw h e t h e rap r o g r 锄i s s u i t a b l ef o rt l s ，m e t h o da n dt h e o r yo fh o wt o1 0 c a t et l sp a r a l l e l i s mi nas p e c i f i e d p r o g r 锄，a n dw ea l s od e s i g n e da n di m p l e m e n t e d as u i to fp r o 丘l i n gt o o l sf o rt l s ；( 2 ) i nt h er e s e a r c ho ft l s p r o g r a m m i n ga n dc o d et r a n s f o r m a t i o n ，w eh a v ei m p l e m e n t e d ab a s er u n - t i m es y s t e mf o rs p e c u l a t i v ee x e c u t i o no fl o o p sa n ds u b r o u t i n e s ，w h i c h m a k e st h es p e c u l a t i v ee x e c u t i o no fl o o p sa n ds u b r o u t i n er o b o t i c i z e dp a r t l ya n d s i m p l m e dt h ep r o g r a m m i n go ft l s 黟e a t l y ；( 3 ) i nt h ea r c h i t e c t u r er e s e a r c ho fc m p w i t ht l s s u p p o r t ，w ec h e c k e dt h en e c e s s a r yh a r d w a r es u p p o nf o rt l s ，a n dp r o p o s e d ab a l s et l sa r c h i t e c t u r e ( 4 ) w eh a v ea l s oi m p l e m e n t e dab e h a v i o r _ l e v e ls i m u l a t i o n p l a t f o 肌f o rm u l t i c o r ep r o c e s s o r i n v e s t i g a t e dt h ep e r f o m a n c eo p t i m i z a t i o no fb o t h h a r d w a r ea 1 1 ds o r w a r e ，a n da c h i e v e dd e s i g ns p a c es e a r c h i n go fm u l t i c o r ep r o c e s s o r ， a c q u i r e dn e wc o g n i t i o no fs e v e r a lt l sp i v o t a lq u e s t i o n t h i sd i s s e r t a t i o ns e l e c t sp r o g r 锄so fs p e cc p u2 0 0 0a sc a s es t u d i e s o no n e i i i a b s t r a c t 一一 h a n d ，t h ei n v e s t i g a t i o no ft l sp a r a l l e l i s m s1 0 c a t i o na na n a l y s i ss h o w st h a t ：( 1 ) t h e r e a l o to fs u b r o u t i n e si nt h ep r o g r 锄，w h o s er e t u mv a l u e2 u r ep r e d i c t a b l e ，a n dt h e yt a k e a ne x e c u t i o nt i m eo fe x c e e d5 0 ，a n dt h es i m p l el a s t v a l u er e t u mv a l u ep r e d i c t i o n s c h e m ei sg o o de n o u g h ( 2 ) l o o p s ，、v h o s eg r a n u l a r i t yi st o os m a l l ，i sm o r et h a nt h a t o n e s ，w h o s eg r a n u i a r i t yi st o ob i g ，a n dl o o pc h u n k i n gi sn e c e s s a 巧t oc o n t r o lt h e g r a n u l a r i t yo ft l st h r e a d s ( 3 ) d a t ad e p e n d e n c e sa r eu b i q u i t o u sf o rb o t h l o o p s t r u c t u r ea j l ds u b r o u t i n es t r u c t u r e ，a n dt h es y n c h r o n i z a t i o nm e c h a n i s m i sn e c e s s a m ( 4 ) f o rt h el a c ko ft l sp a r a l l e l i s mi np r o g r a m ，t h en u m b e ro fp r o c e s s o r st h a tt l s c a n e 脑c t i v e l yu t i l i z ei ss m a l l e rt h a n4 o nt h eo t h e rh a n d ，t h eb e h a v i o rs i m u l a t i o ns h o wt h a t ( 1 ) s i n g l eb u sc o n n e c t i o n c a nn o tb e a rt h ew e i 曲to ft h ec o m m u n i c a t i o nd u r i n g s p e c u l a t i v ee x e c u t i o n ，b u s s p l i t t i n gc a na l l e v i a t et h i sq u e s t i o n ，b u tw h e nt h en u m b e ro fp r o c e s s o re x c e e d4 ， m u l t i b u sc o 肌e c t i o nw i l lb e c o m et h eb o t t i e n e c ko ft h es y s t e m ( 2 ) c o m p l e xa n d w l d e 。l s s u es u p e r s c a l a rc o r ei sn o tn e c e s s a r yf o r b u i l d i n gac m pc h i pw i t ht l s s u p p o n ，b u to u t o r d e ri s s u et e c h n o l o g yi sn e c e s s a 拶( 3 ) c o m p i l i n go p t i m i z a t i o ni s m o r e s i g n i f i c a n t t h a n c o m p l e xh a r d 、v a r ee f 五) r t ， t h r e a d p a r t i t i o nm o d e la n d s y n c h r o n i z a t i o ns u p p o r r ta r et h em o s ti m p o r t a n tf a c t o r sf o rt l s k e yw o r d s ： m u l t i c o r e p r o c e s s o ra r c h i t e c t u r e ，t h r e a d l e v e l s p e c u l a t i o n( t l s ) ， m u l t i - t h r e a d p r o g r a m m i n g ，p r o g r a mp r o n l i n g ，c o m p i l i n go p t i m i z e ， p e r f o m l a n c ee v a l u a t i o n i v 目录 图片目录 图1 1 说明线程级推测技术的例子3 图2 1m u l t i s c a l a r 体系结构图一1 0 图2 2m u l t i s c a l a r 执行模型示意图1 2 图2 3h y d r a 微体系结构图1 4 图2 4h y d r a 对一级数据c a c h e 的扩展1 4 图2 5l 2 写缓存结构图1 5 图2 6s t a m p e d e 方案基本硬件结构图1 8 图2 7s t a m p e d ec a c h e 一致性协议状态转换图2 0 图2 8 说明多级推测的例子2 2 图3 1 循环结构的推测执行过程2 7 图3 2 子程序结构的推测执行过程2 9 图3 3 生产距离与消费距离示意图3 0 图3 4 剖析工作总体框架图3 3 图3 5c a l ll i s t 数据结构示意图3 5 图3 6l a s tw r i t eh a s hl i s t 数据结构示意图与代码片段3 6 图3 7p i s a 体系结构虚地址空间分布示意图3 7 图3 8 推测执行时间计算示意图3 7 图3 9p r o l o o p 中循环结构的标识示意图一3 8 图3 1oi t e r a t i o nl i s t 数据结构示意图3 9 图3 1 lp r o l o o p 中l a s tw r i t eh a s hl i s t 数据结构示意图4 0 图3 1 2p r o l o o p 中对堆栈段数据访问拦截的例子。4 0 v i i i 目录 图3 1 3 不同返回值类型的函数的运行时间比例4 2 图3 1 4l a s t v a l u e 与s t r i d e 方案的返回值预测成功率4 3 图3 1 5 不同静态长度子程序结构的运行时间分布4 4 图3 1 6 子程序结构访存数据依赖分布4 4 图3 1 7 无限内核与2 内核对子程序结构的加速4 5 图3 18 循环展开粒度分布图4 7 图3 1 9 循环展开间的数据依赖分布4 7 图3 2 0 系统加速比j 4 8 图4 1 子程序结构的另一种推测执行模型5 2 图4 2 两种子程序执行模型的对比5 3 图4 3 子程序调用的表示与程序变换举例5 5 图4 4s pc a l l 处理流程图5 8 图4 5f o r 型循环的表示与变换6 0 图4 6s pf o 刚s pw h i l e 处理流程图6 l 图4 7 任务池示意图6 2 图5 1 基本结构模型示意图6 5 图5 2 推测读过程示意图6 7 图5 3 推测写过程示意图6 8 图5 4 函数返回值预测器数据结构图7 1 图5 5c a c h e 行结构示意图7 3 图5 6 推测读详细流程示意图7 4 图5 7 推测写详细流程示意图7 5 图6 1s pc a l l 系统库函数一级c a c h e 行为8 0 图6 2n c o r e = 4 时s pf o r 执行代价随测试规模的变化关系图8 2 目录 图6 3n c o r e = 4 ，n = 1 0 k 时代价随任务数的变化关系图8 3 图6 4n c o r e = 4 时系统加速比随测试规模的变化关系图8 3 图6 5n c o r e = 4 ，n = l o k 时加速比随任务数的变化关系图8 3 图6 6l 2c a c h e 总线占用率与内核数目的关系8 5 图6 7 总线分裂后的总线占用率与内核数目的关系图8 6 图6 8 进一步将数据总线分裂后总线占用率与内核数目的关系8 6 图6 9 处理器内核配置对系统加速比的影响8 7 图6 1 0 测试代码( v 1 。0 ) 8 8 图6 1 1 线程粒度对性能的影响8 9 图6 1 2c a c h e 行大小为8 字节时线程粒度与加速比的关系9 l 图6 1 3c a c h e 行大小为1 6 字节时线程粒度与加速比的关系9 1 图6 1 4c a c h e 行大小为3 2 字节时线程粒度与加速比的关系9 l 图6 1 5 经过优化的测试代码( v 1 1 ) 9 2 图6 1 6v1 1 版本测试代码的性能9 3 图6 1 7 经过再次优化的测试代码( v 1 2 ) 9 4 图6 18v1 2 版本测试代码的性能9 4 x 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除己特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均己在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 却私炙 作者签名：潍 作者签名：鏊l 坚 2 0 0 7 年7 月2 5 日 竹移i ， 第1 章绪论 1 1 研究背景 第l 章绪论 进入2 1 世纪以来，传统的超标量处理器体系结构受到了多方面的严重挑战 ( a s a n o v i c ，2 0 0 6 ，h e r u l e s s y ，2 0 0 3 ) 。一方面，芯片功耗不断增加，已经接近或达到 可以控制的极限( m u d g e ，2 0 0 1 ，g o n z a l e z ，1 9 9 7 ) ：另一方面，越来越复杂的芯片结 构给芯片的设计与验证带来了巨大的困难( a l l a n ，2 0 0 2 ，h a m i l t o n ，1 9 9 9 ， g r o h o s k i ，19 9 8 ) ，芯片的开发研制周期越来越长，处理器的发展进入高投入低产 出的低速发展阶段( p a n ，1 9 9 7 ，p a n ，1 9 9 6 ) 。然而，半导体技术却仍然按照摩尔定律 的速度发展着，不断地为处理器体系结构的研究提供大量的片上晶体管资源 ( k o z y r a l ( i s ，1 9 9 8 ，h o r o w i t z ，1 9 9 9 ) 。如何有效地将丰富的片上晶体管资源转化为计 算资源逐渐成为了摆在处理器体系结构研究者面前的一个重要问题。目前，单 芯片多处理器( c h i pm u l t i p r o c e s s o r ，c m p ) 技术因为能有效控制芯片功耗，降低设 计验证复杂性等方面的优势( o l u k o t u n ，2 0 0 5 ) ，已经被工业界所普遍采用。例如 i b m 在其p o w e r4 、p o w e r5 芯片中就已经采用了c m p 结构( c l a b e s ，2 0 0 4 ， d i e f e n d o r f f ，1 9 9 9 ) ，i n t e l 也已经在其最新一代的处理器产品中采用了c m p 结构 ( m e n d e l s o n ，2 0 0 6 ) 。c m p 结构已经成为从高端到低端各种应用领域处理器体系结 构发展的必然选择。 然而，c m p 结构是工艺技术驱动的产物，而并非应用驱动的产物。工艺技 术方面，为了解决前述处理器体系结构研究中所面临的问题，c m p 结构是不得 已的选择；而应用方面，传统的图灵机串行程序模型与冯诺依曼的串行地址 空间结构并没有发生实质性的变化，程序的设计仍然遵循传统的设计方法，这 就出现了物理上并行的结构设计与理论上串行的程序设计和执行模型之间的不 相匹配问题，这正是目前多核处理器技术所面临的最为严重的问题之一，并且， 随着半导体工艺的不断进步，该问题还将变得越来越严重。迫切的应用需求， 决定了使用多核结构加速串行程序执行的必要性。 技术的进步往往是平滑渐进的，c m p 结构也不例外。c m p 结构可以看作是 在单芯片上构造的对称多处理机( s m p ) 系统，因此可以沿用传统的并行程序设计 第l 章绪论 的方法解决加速传统串行程序的问题。但是众所周知，因为锁与同步机制的使 用，使得传统的并行程序设计与调试变得异常复杂( h e r l i h y ，1 9 9 3 ) ，过去；由于多 处理器结构仅仅应用于高性能计算的领域，该问题还能够被容忍和接受，但是 随着c m p 结构的普及，越来越多的应用都有了使用多核结构获取性能加速的需 求，传统并行程序设计方法难于掌握与设计调试困难的弊端变得越来越严重， 并逐渐超出人们的容忍限度。另一方面，现实中存在着大量遗留的串行算法与 串行代码，传统的并行程序设计方法对于加速它们则是无能为力的。最后，c m p 结构提供了s m p 结构所不能比拟的处理器间互连带宽( l iz h a 0 ，2 0 0 7 ， c h i s h t i ，2 0 0 5 ) ，传统的并行程序设计方法不能充分利用该互连带宽。由于传统的 s m p 结构采用板级互连结构，一次通信往往需要几十甚至上百个时钟周期，传 统的并行程序设计方法不得不花费大量的精力用于减少数据通信，而这种努力 往往是以牺牲对并行性的开发利用作为代价的。如果仍然沿用传统的思路与方 法设计并行程序势必会导致对片上互连网络带宽的浪费。 为了解决前述并行物理结构与串行理论模型之间的矛盾，学术界提出了线 程级推测( t h r e a dl e v e ls p e c u l a t i o n ，t l s ) 技术。该技术将传统串行程序划分成可 以并行执行的线程，通过在多核处理器上并行执行多个线程的方法加速传统串 行程序，线程问的数据相关与控制相关则在程序执行期间动态地捕获与解决。 图1 1 是说明线程级推测技术的一个典型例子，由于不同的循环展开对数组h a s h 的访问可能存在数据相关，因此该循环要么不能被静态并行，要么在人工并行 或是编译器自动并行时加入保守的同步，限制了大部分循环之间的可并行性。 事实上，邻近的循环展开间存在真正数据依赖的概率并不高，并行地执行邻近 的循环展开在大多数情况下并不会发生错误。正是出于这一点考虑，线程级推 测技术使用推测的方法加速该代码，并在运行时动态侦测是否发生了错误的数 据引用，一旦检测到错误的数据引用，则通过重新执行线程的方法恢复错误。 例如，图中线程1 与线程4 之间发生了错误的数据引用，因此当该错误被发现 后，线程4 将丢弃其运行结果并重新开始执行以纠正该错误。 线程级推测技术具有相对于传统方法更加灵活的应用空间，通过在推测执 行的并行代码中插入同步通信的方法，线程级推测可以兼容传统的并行程序设 计方法，熟悉并行程序设计的程序员仍然可以方便地编写代码。另一方面，与 传统并行程序设计方法只能在算法级开发粗粒度并行不同，线程级推测技术可 以使用自动并行工具在源代码级、中间代码级、甚至二进制代码级自动地产生 2 第1 章绪论 1 2 论文目标与研究内容 本文的研究工作旨在分析线程级推测的技术潜力，研究“定位、分析线程 级推测并行性”的理论与方法、推测执行的运行时系统支持以及c m p 结构上实 现线程级推测所需的硬件支持等。在充分调研国内外线程级推测技术的基础上， 我们从应用程序特征分析入手，针对应用程序中固有的线程级推测并行性，提 出了一套分析与定位线程级推测并行性的方法与理论；并在此基础上设计实现 了软硬件相结合的线程级推测系统解决方案，建立了一个基本的线程级推测软 硬件研究平台，开展了对平台相关的线程级并行特性的研究工作。我们希望通 该研究回答以下4 个关键问题： 。 1 如何判断特定的应用是否适合使用线程级推测进行加速，以及如何定位程序 中适于推测执行的代码。 线程级推测与其它任何技术一样都存在着一定的适用范围，对于一个给定 的应用，如何判断该应用是否适合使用线程级推测技术进行加速至今仍然没有 形成完整的理论和方法。本文根据线程级推测的基本原理，针对影响线程级推 测性能的若干关键衡量指标，以s p e cc p u2 0 0 0 中的部分程序作为研究对象， 展开对该问题的详细研究。希望通过该研究建立起一套判定特定应用是否适合 使用线程级推测技术进行加速的方法，并回答如何定位线程级推测热点( 程序中 适合使用线程级推测技术进行加速的部分) 的问题。 2 目前普遍采用的总线式的处理器互连网络对c m p 规模的限制情况。 目前，由于总线结构的互连具有设计实现简单的优势，而被大多数商用c m p 处理器所采用，但是随着半导体技术的不断进步，片上集成的处理器内核数目 将会不断增加，互连总线的负担也将会变得越来越重，直至最终成为系统的性 能瓶颈，然而目前我们还没有看到针对该问题的定量分析。本文的研究将计划 采用模拟的方法，定量的考察处理数目与互连总线负载的关系，以及随着处理 器数目的增加系统整体性能的变化情况，希望通过该研究回答总线互连结构对 c m p 规模限制的问题。 3 顺序( i n o r d e r ) 发射与乱序( o u t o r d e r ) 发射处理器内核对于线程级推测性能的 影响。 c m p 结构的出现标志着从发掘指令级并行( i n s t m c t i o nl e v e lp a r a l l e l i s m ，i l p ) 向发掘线程级并行( t h r i e a dl e v e ip a r a l l e l i s m ，t l p ) 的转变。但是， “是否可以因 4 第1 章绪论 此放松发掘i l p 的努力”，“是否有必要仍然沿用复杂的乱序发射的处理器内 核来构造c m p 结构等问题仍然有待学术界给出明确的回答。本文的研究通过 模拟的方法，对单个处理器内核的设计空间进行搜索，给出单核复杂度对于线 程级推测性能的影响情况。 4 编译技术对线程级推测性能的影响。 性能的提高需要软件与硬件的协同努力，但对于特定的系统方案，软硬件 对于性能的贡献却是不相同的。线程级推测技术的性能究竟在多大程度上依赖 于编译技术是另一个需要学术界回答的问题。本文的研究工作，在确定底层硬 件满足若干基本约束( 详细内容见本文第5 章) 的前提下，通过逐步增加编译优化 的力度，考察编译技术对系统整体性能的影响情况。 1 3 研究步骤和实验方案 为了回答1 2 节中提出的4 个线程级推测技术中存在的问题，我们采用自上 而下的方法开展具体的研究工作。 我们首先展开对应用程序固有并行特性的研究与分析，即研究“定位、分 析应用程序中固有线程级推测并行特性 的方法与理论。通过设计具有针对性 的应用程序剖析工具，我们定量地分析了推测执行过程中直接影响性能的几个 关键指标，主要包括粒度、子程序结构的返回值预测成功率、访存数据依赖特 征等。该研究的结果对于指导编译器定位适合推测执行的代码片断，指导线程 的划分与优化都有着十分重要的意义。 其次，为了开展线程级推测性能的研究工作，我们设计实现了软硬件结合 的模拟实验平台。软件上，我们设计了针对子程序与循环结构推测执行的系统 库函数、研究了推测执行程序的表示与变换方法；硬件上我们扩充了c m p 结构， 加入了必要的线程级推测支持，实现了线程级推测的基本功能，为软件提供了 必要的支持，搭建了可配置、易扩展的实验平台。 最后，我们在上述软硬件结合的模拟实验平台上开展具体的研究，并选取 s p e cc p u2 0 0 0 中部分程序作为测试用例，展开对1 2 节中4 个关键问题的研究。 为了避免不必要的重复劳动，加快研究进度，研究中所使用的应用程序剖 析工具与线程级推测模拟器均在学术界目前广泛采用的模拟工具的基础上扩 充、修改完成。此外，为了回避对编译器的大范围改动，我们保持原有处理器 第1 章绪论 内核指令级体系结构不变，所有对新特性的支持都以系统调用的形式与上层软 件接口，同时，为了保证模拟的精确，我们为所有扩充的系统调用加入了相应， 的延迟模型。 1 4 论文的写作安排 论文全文共分7 章，各章节将按如下方式组织： 本章为绪论，介绍选题的背景与意义、论文的研究内容与目标以及研究方 法与步骤。 第二章，通过对学术界最有影响的几个技术方案的分析与比较，介绍线程 级推测技术的发展与现状，以及我们对相关研究工作的认识与评价。 第三章，根据线程级推测技术的基本原理，选取s p e cc p u2 0 0 0 中的部分 程序作为研究对象，针对子程序结构与循环结构开展对应用程序中固有线程级 推测并行特性的研究，并介绍相关的实验方法与实验数据。 第四章，介绍软硬件相结合的系统方案中的软件方案，即线程级推测技术 的程序表示与变换方法，及其与底层硬件平台的接口。 第五章，介绍我们提出的硬件系统结构，主要包括推测缓冲机制、错误侦 测机制以及回退机制等，这些都是实现线程级推测的必要元素。 第六章，以特定的应用程序作为测试用例，在第三第四章中所搭建的实验 平台上展开对线程级推测技术的详细性能分析，针对4 个关键问题设计相应实 验，并给出定量的回答。 第七章，介绍研究所取得的重要成果与结论、目前工作中所发现的问题及 其预计的解决办法。 本文的最后还列出相关的参考文献。 6 第2 章相关的研究工作分析 第2 章相关的研究工作分析 本章首先简要介绍线程级推测技术的发展概况，然后按照时间的大致顺序 依次介绍不同时期最具代表性的几个典型的线程级推测方案，最后通过与相关 研究工作的比较，给出本文研究工作的具体定位。 在展开讨论之前，为了准确方便地描述问题，我们首先明确若干概念与名 词。 推测度( s p e c u l a t i 仰d e g r e e ，s p d ) ：推测度是指推测执行的线程在串行程序 序中的相对位置。推测度越高说明其在串行程序序中的位置越靠后，反之则越 靠前。有时候，我们也使用年长与年幼来描述线程间的相对推测度。线程a 较 线程b 年幼是指线程a 的推测度较线程b 高：线程a 较线程b 年长是指线程a 的推测度较线程b 低。在实际执行过程中，线程一般与具体的处理器内核是对 应的，因此，有时候推测度的概念也被用于处理器内核，这时候推测度反映了 不同内核上推测执行的线程之间的相对顺序。由于串行程序序的存在，推测执 行的过程中只有一个线程处于非推测状态，其推测度最低，我们通常称之为头 线程，负责执行头线程的处理器我们通常称之为头处理器。 数据相关的分类：根据引起数据相关的数据对象的不同我们可以将相关分 为寄存器相关与存储器相关，顾名思义，二者分别是指由于对寄存器与存储器 的读写所产生的相关。寄存器相关可以在编译阶段被编译器所捕获，因此对于 寄存器相关的分析与处理相对简单。部分存储器相关( 例如对全局变量的访问) 也可以被编译器在编译阶段所捕获，对于这一类的存储器相关我们称之为显式 存储器相关或确定存储器相关：还有部分的存储器相关( 复杂的指针操作) 不能 在编译阶段被编译器所捕获，对于这一类的存储器相关我们称之为隐式存储器 相关或不确定存储器相关。此外，相关有时候也被称之为依赖，除具有显示附 加说明的情况外，本文对二者并不做显式的区分。 2 1 线程级推测技术发展概况 线程级推测技术在上世纪9 0 年代早期开始萌芽，通常以1 9 9 5 年威斯康星 大学s o h i 教授领导的研究小组发表m u l t i s c a l a r 技术方案( g o p a l ，1 9 9 8 ， 7 第2 章相关的研究工作分析 v i j a y k u m a r ，1 9 9 7 ，j a c o b s o n ，1 9 9 7 ，v i j a y k u m a r ，1 9 9 7 ，v i j a y k u m a r ，1 9 9 6 ，s o h i ，1 9 9 5 ) 作 为该技术的正式提出。尽管早期的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 的提出却 引领了处理器体系结构的研究由开发i l p 向开发t l p 的转变，也带动了学术界 许多其他研究小组开展发掘t l p 的研究，这其中包括明尼苏达大学的a g a s s i z 小组，伊利诺斯大学的i a c o m a 小组等。 1 9 9 9 年，斯坦福大学的研究小组发表了h y d r a 技术方案( p r a b h u ，2 0 0 5 ， h a m m o n d ，2 0 0 0 ，o l u k o t u n ，1 9 9 9 ，h 锄m o n d ，1 9 9 8 ，n a y f e h ，1 9 9 6 ) ，该技术方案将4 个高性能的m i p s 处理器内核集成于单一芯片之上，处理器之间采用共享二级 c a c h e 的方法进行通信，并摒弃了寄存器级的通信机制，这使得该方案回避了 m u l t i s c a l a r 方案设计复杂、验证困难的问题。此外，h y d r a 采用软硬件相结合的 方法实现线程的推测机制，这也在一定程度上简化了硬件系统的设计。正是由 于上述技术改进，使得h y d r a 能够逐渐取代m u l t i s c a l a r 方案成为线程级推测技 术的典型代表。 几乎与h y d r a 同时，2 0 0 0 年卡内基梅隆大学的研究小组提出了s t a m p e d e 方案( s t e f m ，2 0 0 5 ，s t e f j m ，2 0 0 0 ，z h a i ，2 0 0 2 ，s t e f ，19 9 7 a ，s t e f f a n ，19 9 7 b ) ，该方案 首次明确提出了线程级推测的概念。但是，不同于h y d r a 实施全系统设计的研 究方法，s t a m p e d e 方案针对普遍意义上的c m p 硬件体系结构，专注于相关编 译技术与操作系统支持方面的研究。 2 0 0 4 年，l a n c eh a m m o n d ( 2 0 0 4 a ，2 0 0 4 b ) 等人提出了t c c ( t r a n s a c t i o n m e m o r yc o h e r e n c ea n dc o n s i s t e n c y ) 方案，该方案借用t r a n s a c t i o nm e m o 巧的思 想实现了线程级推测。t r a n s a c t i o nm e m o 巧( h e r l i h y ，1 9 9 3 ) 技术的设计初衷是为了 将程序员从复杂繁琐的并行程序设计中解放出来的，l a i l c eh a m m o n d 等人借用 了其思想精髓，将其应用于线程级推测技术，从而简化了线程级推测系统软硬 件设计的复杂度，但与此同时也对并行编译技术提出了更高的要求。 时至今日，有关线程级推测的研究仍然是学术界的一个重要研究热点，但 是随着对该技术认识的不断深化，越来越多的研究者意识到线程级推测技术的 8 第2