（计算机科学与技术专业论文）前瞻多线程编译优化技术的研究与实现.pdf

里堕型堂堇查盔兰堑壅篁堕兰垡丝苎摘要f 高性能通用微处理器是计算机系统中的核心部件，使用范围从个人电脑覆盖到超级并行计算机。对于当前软件中占主要部分的串行程序而言，微处理器主要依靠开发程序的指令级并行( i l p ) 来提高性能。随着片上集成度的不断提高，在单个芯片上集成1 0亿个晶体管的时代即将来临。在这种情况下，再增加动态指令窗口的体积和发射宽度将无助于高主频的实现，难以开发更高的i l p ，获得整体性能的提升。j前瞻多线程结构( s m a ) 结合了前瞻性执行机制和多线程执行机制，以整个线程为步长进行前瞻性执行，多个线程并行执行，并且共享处理器硬件资源。已有的研究表明该结构能够发出程序中混合并行性，达到较高的资源利用率，是一种很有前途的新体系结构。本文在全面深入地研究了国际上提出的多种多线程结构及其相关编译优化技术的基础上，结合前瞻多线程结构s m a 的执行机制，研究了针对s m a 结构的编译优化技术，实现了一个面向s m a 结构的编译优化框架s m a r c o f 。f 主要的工作与创新点包括：1 研究了s m a 结构各种主要程序结构的适应性和性能优化特性，确定了s m a 模型的关键性能要素：现场间负载不均衡、线程间控制前瞻失效与线程间数据前瞻失效。2 为s m a 前瞻执行优化设计了一组启发式优化规则，包括线程优化划分策略、现场间负载均衡策略以及类d e e 优化的前瞻执行映射策略。3 针对多线程模式下访存负荷加重的问题，为s m a 模型设计了软硬件协同预取机制，并为s m a 模型设计了c a c h ef i l t e r 来消减无效预取。4 研究了基于动态轮廓信息的软硬件联合持续优化机制，并在d l x 模拟器的基础上设计并实现了一个完整的指令级模拟平台和基于上述优化规则的编译框架s m a r c o f 。基于s p e c 代码的模拟表明该方式能够有效的挖掘系统的潜力，实现深度的指令级并行和线程级并行开发。综合来说，s m a 结构是一个很有潜力的方向，而基于反馈信息的持续优化方式配合正确的启发式优化规则能够很好的挖掘s m a 结构的潜力，将体系结构优势转化为现实的执行性能。值得在这个方面做进一步的研究。、关键词：前瞻多线程结构、编译优化、预取、动态执行轮廓、反馈优化p 一一一一，里堕型堂垫垄盔堂堑窒生堕兰垡迨塞a b s t r a c th i g h - p e r f o r m a n c e ，g e n e r a l p u r p o s em i c r o p r o c e s s o r ss e r v ea sc o m p u t ee n g i n e sf o rc o m p u t e r sr a n g i n gf r o mp e r s o n a lc o m p u t e r st os u p e r c o m p u t e r s s e q u e n t i a lp r o g r a m sc o n s t i t u t eam a j o rp o r t i o no fr e a l w o r l ds o f t w a r et h a tr u no nt h ec o m p u t e r s s t a t e o f - t h e a r tm i c r o p r o c e s s o r se x p l o i ti n s t r u c t i o nl e v e lp a r a l l e l i s m ( i l p ) t oa c h i e v eh i g hp e r f o r m a n c eo na p p l i c a t i o n sb ys e a r c h i n gf o ri n d e p e n d e n ti n s t r u c t i o n si nad y n a m i cw i n d o wo fi n s t r u c t i o n sa n de x e c u t i n gt h e mo naw i d e i s s u ep i p e l i n e i n c r e a s i n gt h ew i n d o ws i z ea n dt h ei s s u ew i d t ht oe x t r a c tm o r ei l pm a yh i n d e rf r o ma c h i e v i n gh i g hc l o c ks p e e d ，l i m i t i n go v e r - a l lp e r f o r m a n c e ，e s p e c i a l l yf o rt h ef o r t h c o m i n gb i l l i o n - t r a n s i s t o rp e r - c h i pe r a t h es p e c u l a t i v em u l t i t h r e a d i n ga r c h i t e c t u r e ( s m a ) e m p l o y sad e - c e n t r a l i z e do r g a n i z a t i o nt oc o n s t r u c tm u l t i p l es m a l lw i n d o w sa n dm a n yn a r r o w i s s u ee x e c u t i o nu n i t st oe x p l o i tm a s s i v ei l p s e q u e n t i a lp r o g r a m sa r ep a r t i t i o n e di n t oc o d ef r a g m e n t sc a l l e dt h r e a d s ，w h i c ha r es p e c u l a t i v e l ye x e c u t e di np a r a l l e l p r e v i o u sr e s e a r c hs h o w e dt h es m aa r c h i t e c t u r ec o u l da c h i e v es u b s t a n t i a lp e r f o r m a n c eb o o s ta n de f f i c i e n tr e s o u r c eu t i l i z a t i o n c o m p i l e ro p t i m i z a t i o nh o l d sav e r yi m p o r t a n tp o s i t i o ni ns m ar e s e a r c h t h e r ea r et h r e ek e yf a c t o r sb a f f l et h es m ap r o c e s s o r ：c o n t e x tl o a di m b a l a n c e ，i n t e r t h r e a dc o n t r o ld e p e n d e n c ea n di n t e r - t h r e a dd a t ad e p e n d e n c e t om a i n t a i np e r f o r m a n c eb o o s t t h es m ac o m p i l e rm u s te l i m i n a t et h o s ef a c t o r st h o r o u g h l y t h ew o r ko f t h i sp a p e ri n c l u d e ：1t h ep a p e rt h o r o u g h l yi n v e s t i g a t e se x e c u t i o nb e h a v i o ro fv a r i o u sa p p l i c a t i o n so ns m aa r c h i t e c t u r e k e yp e r f o r m a n c ef a c t o r sa r ea l s op r e s e n t e d 2as e to fh e u r i s t i cr u l e si sp r e s e n t e dt oa c c e l e r a t es p e c u l a t i v ee x e c u t i o no fs m at h r e a d s r u l e si n c l u d eo p t i m i z e dt h r e a dp a r t i t i o ns t r a t e g y , c o n t e x t sl o a db a l a n c es t r a t e g ya n dd e e l i k et h r e a dm a p p i n gs t r a t e g y 3t h o r o u g h l yr e v i e w e dm e m o r yb a n d w i d t hr e q u i r e m e n to fs m ap r o c e s s o ra n dd i f f e r e n c eo fv a r i o u si n s t r u c t i o nf e t c hp o l i c i e s t oi m p r o v ec a c h ep e r f o r m a n c eu n d e rs m am o d e l ，t h ep a p e ri n t r o d u c e sh a r d w a r e s o f t w a r ec o o p e r a t i v eo p t i m i z a t i o n o nt h es o f t w a r es i d e ，c o m p i l e ri n s e r t sp r e f e t c hi n s t r u c t i o n se x p l i c i t l y ；o nt h eh a r d w a r es i d e ，a ns m ac a c h ef i l t e ri sa d d e dt oc u td o w nu n n e c e s s a r yp r e f e t c h 4g u i d e db yf c e d b a c k b a s e do p t i m i z a t i o ns t r a t e g y , t h ep a p e rp r e s e n t sad y n a m i cp r o f i l eb a s e dc o n t i n u o u so p t i m i z a t i o nf r a m e w o r k s m a r c o f b a s e do nt h ed l xs i m u l a t o r ,s m a r c o fi sm o d i f i e dw i t hs m as p e c i f i ce x t e n s i o na n dh e u r i s t i co p t i m i z i n gr u l e s s i m u l a t i o no fs p e cc o d es h o w st h a ia b o v er u l e sc o u l de x p l o i th y b r i dp a r a l l e l i s me f f e c t i v e l yw i t hr a t h e rl o wo v e r h e a d 国防科学技术大学研究生院学位论文c o n c l u s i v e l y , t h es m aa r c h i t e c t u r ei sap r o m i s i n gw a yt oi m p l e m e n th i g hp e r f o r m a n c ep r o c e s s o r ；t h ec o n t i n u o u so p t i m i z a t i o nf r a m e w o r ks m a r c o fc a nu t i l i z ea y n a m i ce x e c u t i o np r o f i l e sa n dh e u r i s t i cr u l e st oe l i m i n a t es m ap e r f o r m a n c eh i n d r a n c ee f f e c t i v e l y p r e l i m i n a r yw o r kd i s c u s s e di nt h i st h e s i ss h o w e de n c o u r a g i n gp e r f o r m a n c eb o o s tp o t e n t i a la n da p p l i c a t i o nc o m p a t i b i l i t yo fs m a r c o ff u t u r ei m p r o v e m e n tc o u l db ee x p e c t e d k e yw o r d s ：s m a ，c o m p i l e ro p t i m i z a t i o n ，p r e f e t c h ，d y n a m i ce x e c u t i o np r o f i l e ，f e e d b a c k - b a s e do p t i m i z a t i o n国防科学技术大学研究生院学位论文图表索引图1 1超标量处理器结构一图1 2 线程级并行示意图图2 1 多线程技术的发展图2 2e a r t h 系统结构图示图2 _ 3t h r e a d c 编译环境图示一图2 4s m t 结构图示图2 5m u l t i s c a l a r 结构图示一图2 , 6s p s m 的指令执行踪迹图2 7s p 、e e 、d e e 执行模型图2 8基于s c m p 结构的p o w e r 4 芯片封装图2 9t r a c ec a c h e 的概念原理图2 10t r a c e 处理器结构一图3 1s m a 原理结构模型图3 2 线程划分示意图图3 3d oa l l 循环示例代码图3 4 各线程代码执行示例图一图3 5d oa c r o s s 类型代码示例图3 6 线程代码的执行示例图一图3 7 函数调用代码示例图3 8 多线程代码及线程间相关性一图4 1s m a 编译器与体系结构的接口图示图4 2 线程的执行周期图示一图4 3“短线程一低资源利用率”示意图图4 4 不均衡的现场负载图示图4 5 控制前瞻失效示意图图4 6 基于寄存器数据相关的前瞻失败图4 7 基于存储器数据相关导致的前瞻失败一图4 8 程序的编译优化执行周期图4 9 基于反馈信息的编译优化流程图4 1 0s m a 编译器组成结构图5 ，l 带循环展开的线程划分图5 2 针对控制相关的优化图5 3前瞻多指令流执行模式下的数据相关_ o 趣jm坦h”挎加烈巧勰汐如如勉”弘”弛强加叭钙铝的”国防科学技术大学研究生院学位论文图5 4 针对数据相关的优化图5 5 线程体积优化图示图5 6 “d o w h i l e ”类型循环代码图5 7 经循环转换的代码与执行图示图5 8 基于d e e 模型的代码调度图5 9 基准程序在不同线程配置下的u p i c图5 1 0 反馈优化次数与u i p c 对照图6 1 带宽计算图示图6 2s m a 取值单元与c a c h e 结构图6 3 线程划分对c a c h e 失效率的影响图6 4 循环分块优化- 图6 5函数调用融合对c a c h e 的影响图6 6 针对访存优化的代码布局调整图6 7 预取模式下的执行周期图6 8s m a 预取优化图示图6 9s m ac a c h ef i l t e r 机制说明图6 1 0s m a 指令执行流程图一图6 11s m a 访存优化结果图6 1 2s m a c a c h ef i l t e r 加速比对照图7 1s m a - d l x s i m 模拟平台结构图7 2 基于p r o f i l e 的程序优化图7 3a t o m 编译器的二进制目标格式观舛弱跖印配勰加孔陀佗弛为引跎黔跖髂国防科学技术大学研究生院学位论文数据表索引表1 1表1 2表3 1表3 2表51表5 2表5 3表5 4表表表表51，232 0 0 0 年美国半导体工业联合会发布的v l s i 发展预测表理想模型下的i l p 线程结束指令的形式与说明s m a 与其他多线程微处理器体系结构的比较一s m a 模拟器配置列表一多线程划分优化与体积优化结果基准程序在不同线程配置下的u p i c 反馈优化次数与u i p c 对照反馈优化次数与系统效率若干参数对照访存单元基本配置表基准程序模拟执行结果s m ac a c h ef i l t e r 执行性能评估0o拍鳃如”矾酡为舳跎国防科学技术大学研究生院学位论文第1 章绪论近二十年来，微处理器性能借助微电子工艺和体系结构模型的进步获得飞速的发展，平均每年增长3 0 。伴随着性能的提高，微处理器的应用在各个领域取得了巨大的成功，产生了良好的经济和社会效益。应用的深入要求微处理器提供更高的性能，从而推动了微处理器体系结构研究的不断深入。随着多媒体、网络、大型数据库、高性能计算、人工智能等应用的普及和进一步发展，对计算性能的要求势必越来越高，使得对微处理器性能提高的追求热情不减。微处理器性能的提高主要依靠两条途径：一是半导体工艺的进步，二是处理器体系结构的发展。就当前的技术现状和储备，在下一个十年，半导体工艺技术仍将继续推动处理器的时钟频率和集成度稳步提高。到2 0 1 0 年，高性能处理器在单芯片上将集成1 0 亿只晶体管( 表1 1 ) 1 。但是，如何有效利用这些数目巨大的晶体管，实现更高的性能仍然是微处理器体系结构研究面临的一个巨大的挑战 2 1 。表1 12 0 0 0 年美国半导体工业联合会发布的v l s i 发展预测表d r a mm i c r o p r o c e s s o r年份工艺面积集成度面积晶体管时钟i o 引脚( um 1( n l m )( gb i t s c m 2 )( i l l m )( m c r l l )( g h z )i 9 9 9o i 81 3 l0 23 1 01 9 71 2 57 6 82 0 0 2o 1 31 4 10 5 43 2 55 3 22 4 91 0 2 42 0 0 50 1 01 4 71 4 63 7 21 3 l4 1 51 0 2 42 0 0 80 0 71 9 l2 9 77 1 33 2 47 11 2 8 02 0 1 10 0 52 0 58 9 98 1 77 9 91 11 4 0 82 0 1 40 0 3 52 6 81 8 19 3 71 ，9 7 01 4 91 4 7 2由此可见，研究满足未来需求的高性能微处理器实现面临着两个方面的重要考验：首先是采取什么样的形式来组织丰富的硬件资源，使之具备充裕的性能潜力；其次是采取什么样的配套技术，使得这样的潜力能够转化为现实的执行性能。本课题的工作在一种新型的微处理器体系结构前瞻多线程体系结构的基础上，深入研究了面向该结构的相关编译优化技术，根据基于反馈的编译优化原理，实现了一个基于动态轮廓信息的持续优化框架原型。1 1 研究背景1 1 1 超标量结构的概况与局限现代高性能通用微处理器大都采用超标量结构( s u p e r s c a l a r ) ，在单个周期内并行执国防科学技术大学研究生院学位论文行多条指令来开发指令级并行( i n s t r u c t i o nl e v e lp a r a l l e l i s m ，i l p ) 。如图1 1 所示，典型的超标量结构需要维系一个大的指令窗口，引入寄存器重命名机制来消除指令间的伪相关通过复杂的硬件来识别出窗口中独立的指令，提交给功能单元执行b “1 5 1 。v l s i 工艺的不断进步导致了单芯片集成度不断提高，在单个芯片上集成1 0 亿晶体管已经成为现实。对于处理器体系结构设计人员而言，采用什么样的策略来充分利用这样充裕的硬件资源成为一个极大的挑战。但是，超标量技术的进一步发展很困难，估计纯粹的超标量技术的性能潜力将在下一代微处理器中耗尽。li指令删b=浮点功能单元1 分支酮jl介取指单元吲淼i 浮点寄存器瞄高c 二纠整数功能单元速互c 二纠访存功能单元t 丁i 介1ll 整数寄存器高联s - 指令映射表l q 重排序缓冲b ：=数据c a c h ec a c h e图1 1 超标量处理器结构对于超标量技术而言，实现更高的性能意味着更宽的发射宽度、更高的主频以及更深的流水线设计。但是超标量结构集中式的组织方式从根本上限制了这些要求。无论是乱序超标量结构中的寄存器重命名技术以及指令窗口唤醒，选择逻辑的设计，还是顺序乱序超标量技术中共同的寄存器旁路逻辑的设计，都要求分布式设计来打破集中控制瓶颈。其中寄存器旁路逻辑设计一般采用数据前传( d a t af o r w a r d i n g ) 技术，即为了提高指令执行性能，直接将一条指令的执行结果传递给所有等待其结果的指令。完全的数据前传通路的延迟是与其规模成平方关系增长，这个延迟的根源则在于布线延迟的飞速增长( 相对于处理器周期时间而言) 。事实上，已经有工业界的报告指出，在0 1 8 1 1 以下的工艺水平上设计高性能的超标量处理器，寄存器旁路逻辑设计是主要的障碍之一t 6 1 。因此，设计满足未来高性能计算要求的处理器必须摆脱超标量结构的限制，采用新的微结构来更好的利用丰富的晶体管资源。1 1 2i l p 的潜力和限制指令级并行i l p 是一种普遍存在于各类程序中的细粒度并行性。正是由于这种通用性，现今的微处理器基本上都是以开发i l p 作为其主要性能提高手段。另一方面，i l p同各种粗粒度的并行性是互补的，未来的高性能处理机都将是由多个i l p 处理器构成的国防科学技术大学研究生院学位论文复合系统。要研究程序中的指令级并行潜力，必须建立理想的处理器模型。常用的理想处理器模型有两个：o r a c l e 模型：假定完全正确的分支预测，分支开销为0 ，分支不影响代码正确执行：b y p a s s i n g 模型：程序沿着分支的两条路径同时执行下去，即旁路了分支，分支开销也是0 ，同样不影响代码正确执行。对理想处理器模型的研究表明，程序中存在着大量的i l p ( 表1 2 ) 盯“8 1 1 9 1 0 实验研究的对象包括数值计算程序和非数值计算程序。结果表明数值计算程序中的i l p 是十分巨大的，而在非数值计算程序中，i l p 的潜力也很大。表1 2 理想模型下的i l p研究b e n c h m a r k 类型平均i p c备注r i s e m a n通用程序2 5 6 5n i c o t a u科学计算1 2 1 3v l i w 模型k u m a r科学计算5 0 0 - 3 5 0 0f o r t r a n 程序b u t l e rs p e c m a r k s7 3 1 7 5 7 8 2a u s t i ns p e c m a r k s6 6 3 7 6 8 6 8 5 3 5 0l a ms p e c m a r l ( s1 5 8 2 6包括一些非s p e c 代码值得注意的是，i l p 实际上与编译技术、机器结构、程序特性和数据结构都密切相关。对i l p 的开发受到三方面条件的制约：程序中固有的i l p 、处理器硬件可支持的i l p 以及编译优化工具可以开发出的i l p 。根据木桶原理，最终可得到的并行度将等于上面三者中最小的一个。而在各种实际因素的制约下，最终得到的结果依然远小于这个理论上限。指令级并行的开发存在许多限制，主要体现在以下三个方面：1开发的时机：编译时的静态提取和运行时的动态提取各有所长。怎样将两者的优点有机地结合起来，是目前i l p 研究中的热点。2开发的范围：由于串行程序中分支指令的影响。少数几个顺序的基本块内部的i l p 很小。深度的i l p 挖掘需要处理器解决程序中大量存在的控n 数据相关性和不确定性，建立个巨大的指令窗口。研究表明，基于单指令流很难建立高效的窗口，可行的替代方案包括从多条指令流来构造一个复杂的窗口，或者建立多个简单的窗口来共同发射指令。这些方式都能够突破基本块的限制，是目前研究的重点之一。3开发的机制：依赖硬件动态提取i l p 必然提高控制和数据通路的复杂度。随着国防科学技术大学研究生院学位论文v l s l 工艺特性的变化，芯片布线延迟变得越来越重要，过于复杂的控制机制事实上无法高效实现，反而会降低主频，导致性能下降。因此研究适合未来v l s i特性具有规模可伸缩性的控制机制十分重要。在针对超标量技术的替代方案中，超长指令字( v l i w ) 技术、多线程( m u l t i t h r e a d i n g )技术以及单芯片多处理器( s i n g l ec h i pm u l t i p r o c e s s o r , s c m p ) 技术都表现出可观的性能提升和良好的应用前景。尤其是多线程技术，结合了控制流技术和数据流技术的优点，具有在多个层次开发指令级并行以及良好的延迟隐藏特性，是未来通用高性能微处理器结构的一个选择1 1 0 1 t l l l 。1 2 多线程结构与线程级并行超标量结构的主要局限是在单个线程( 或者指令流) 内部开发指令并行，这也是采用集中式设计的一个主要原因。因此，突破超标量结构局限的自然选择就是将应用程序划分为多路指令流来开发i l p ，从而实现更具有规模可伸缩性的分布式组织结构。许多研究项目都提出了这样的分布式结构设计：将应用程序按照一定的规则进行划分，分布到多套功能部件组( 现场) 来执行。这样的指令流划分，在本文中统一称为线程。一个线程可以是个或多个基本块、一个函数调用、一个循环体或者一个循环等等，不同的线程模型有不同的线程定义和划分策略。在这样的划分基础上开发出的并行性，称为线程级并行( t h r e a dl e v e lp a r a l l e l i s m ，t l p ) 。早期的多线程概念来自数据流技术的研究，主要目的是利用多个线程交替切换来隐藏长延迟操作，如多处理机系统中的远程访存操作。这方面的典型系统有h e p 、+ t 、j - m a c h i n e 等。后续的研究逐渐将数据流模型和冯诺伊曼模型有机的结合起来，形成新的多线程计算模型，如图1 2 所示。在这种模型下，每个线程内部指令的执行是按照控制流驱动的方式执行，以降低通讯开销，提高执行效率。线程作为执行调度的基本单位，多个线程按数据流驱动的方式并发( 并行) 地执行，以达到相互隐藏长延迟操作和提高并行度的效果。这方面的典型包括s i n g l ec h i pm u l t i p r o c e s s o r 结构、s i m u l t a n e o u sm u l t i t h r e a d i n g 、s p s m 、m u l t i s c a l a r 等“i - t 1 0与指令级并行i l p 不同，线程级并行t l p 属于中粒度并行性，隐式地存在于程序中。因为没有通行的划分标准，评估应用程序的t l p 很困难。最常见的是基于循环和指令踪迹( t r a c e ) 的t l p 开发。因为线程级并行来自多路指令流，所以研究t l p 必然与分支预测执行( p r e d i c t e de x e c u t i o n ) 、控制流前瞻( c o n t r o lf l o ws p e c u l a t i o n ) 以及数据前瞻( 1 3 a t as p e c u l a t i o n ) 等技术关联1 4 10国防科学技术大学研究生院学位论文图1 2 线程级并行示意图t l p 的开发是一个编译器和体系结构紧密协同的过程。一个基本的多线程编译环境通常包括以下几个方面的基本内容：l线程的定义与划分算法，负责从单线程程序中拆分出多个线程。2 线程内部优化算法，根据单个现场的内部实现方式，负责线程内部的指令级并行开发。3 线程间优化策略，根据多个现场的组织结构，协调多个线程的并发执行，包括线程调度和线程同步策略。4 多线程优化的评估策略，量化地考核多线程系统的整体性能、效率、复杂度等因素。线程级并行属于中粒度并行中的一种，基于“t l p + i l p ”的混合并行开发模式已经成为新一代高性能微处理器结构研究的热点。1 3 延迟隐藏技术在现代计算机系统中，强劲的处理器性能并不一定能够保证相应的系统性能。因为v l s i 工艺的差异，当处理器速度发展遵循摩尔定理增长1 0 倍时，存储器( d r a m ) 速度获得的增长只有2 倍。即使引入了复杂的层次存储体系( 寄存器堆一l 1c a c h e - - l 2c a c h e 主存) ，存储系统依然成为系统性能瓶颈15 1 。解决存储器速度差异的基本方式有两种：消减和隐藏。对于消减策略而言，有硬件和软件两方面的手段来实现。硬件实现包括新的v l s i 工艺、更加灵活的c a c h e 映射方式，甚至采用全新的体系结构设计( p r o c e s s o r - i n m e m o r y ) 等等。软件优化包括使用编译优化技术尽可能减少不必要的内存访问和处理器间通讯等。无论采用多么先进的消减策略，应用程序的计算模型决定了始终存在不可消减的通讯和同步。因此，在许多情况国防科学技术大学研究生院学位论文下，只能引入延迟隐藏机制。在多线程结构中，一般是多指令流共享功能单元。当单线程内的某条指令遇到长延时操作时，如c a c h e 失效，其他线程中的指令依然可以发射，分配到空闲的功能单元执行。多线程技术作为一种通用的延迟隐藏技术，可以提高处理器资源的利用率，从而提高整体性能。预取( p r e f e t c h ) 是另外一种常用的延迟隐藏技术。静态预取由编译器完成，是在静态预测延迟的基础上添加预取指令。动态预取一般与c a c h e 实现策略相关，如t r a c ec a c h e技术中t r a c e 的动态构建与调整就是非常明显的动态预取。另外，预取技术作为一个独立的执行加速技术，在多线程系统中依然可以起到提高单线程执行性能的作用。在可以预见的未来，“处理器存储器”速度差异不但不会缓解，反而有加剧的趋势。延迟隐藏技术的研究将成为高性能微处理器体系结构研究中的一个重要组成部分。考虑到延迟的多样性，未来的解决方案中必定是多种策略的组合。1 4 本文的工作多线程结构是目前体系结构研究中的热点，本文的工作以一种新的多线程结构一前瞻多线程体系结构( s p e c u l a t i v em u l t i t h r e a d e d a r c h i t e c t u r e ，简称s m a ) 为基础，对面向该结构的编译优化若干关键技术进行了深入研究。前瞻多线程体系结构是在前瞻性执行超标量技术和多线程技术的基础上结合了二者的优点而发展起来的。在s m a 中，编译器把串行程序分成一组可以并行的( 且具有相关性的) 线程，送到多个不同的现场执行。线程作为处理器前瞻性调度的基本单位，所有线程共享物理处理器的功能单元阵列，多个前瞻性线程可以并行地执行。s m a 有机地结合了静态编译技术和动态调度技术，编译器可以充分发挥它擅长的全局优化，将并行性信息( 通过线程的划分和线程内、线程间指令调度) 传递给硬件，硬件再发挥它的动态调度优势，动态地调度线程和指令执行，完成局部指令级并行优化。我们对基于s m a 模型的编译优化技术进行了深入的研究，设计并实现了一组机制来充分挖掘这一结构的潜能。概括地说，我们的研究主要集中在以下四个方面：1全面深入地研究了国际上提出的多种多线程结构及其相关编译优化技术，总结分析了它们的特点。2结合前瞻多线程结构s m a 的执行机制，研究了它对各种主要程序结构的适应性和性能优化特性，并比较分析了它的性能要素。3为s m a 结构设计一组启发式优化规则，包括以下几个方面的内容：线程划分，研究了以基本块为单位的线程划分策略，包括基本的线程内优化策略和寄存器掩码生成算法：线程体积优化，针对现场资源容量进行线程划分、融合国防科学技术大学研究生院学位论文操作，保证多个线程的负载平衡：前瞻优化，将线程树按照前瞻模型映射到环形组织的现场单元上，以保证最优的整体执行性能；访存优化，基于编译指导信息的协作式预取机制的设计，实现符合多线程特点的c a c h e 优化。4研究了基于动态轮廓( p r o f i l e ) 信息的软硬件联合持续优化机制，并在d l x 模拟器的基础上设计并实现了一个完整的指令级模拟平台。基于该平台的基准程序模拟表明该模式能够很好的挖掘体系结构的潜力，实现深度的t l p + i l p 开发。1 5 本文的结构本文是对我们的研究工作的总结，全文分为八章。第二章讨论多线程技术的现状和发展，深入分析了若干有影响的多线程结构研究，尤其是相关的体系结构与编译技术的协同机制。第三章介绍本文工作的基础一前瞻多线程计算模型，介绍其原理，描述其基本执行机制。本章还分析了s m a 模型对各种类型应用程序的性能特性，指出了s m a 结构的性能要素和优化起点。第四章介绍针对前瞻多线程体系结构的编译优化技术，包括编译器与体系结构的接1 2 1 ，在s m a 执行模式下的性能要素，以及s m a 编译优化的实现技术路线基于反馈的渐进优化策略以及在该方式下的结构组成。第五章与第六章是s m a 处理器编译优化策略的详细说明，包括两个部分：第五章着重介绍针对前瞻执行机制的优化算法，包括线程划分优化、体积优化和面向前瞻执行的优化技术。第六章介绍多线程结构下的访存优化策略，主要内容包括软硬件联合预取机制的设计以及s m ac a c h ef i l t e r 的设计方式。这一部分还包括主要的模拟数据，量化说明编译优化框架对s m a 性能潜力的开发程度。第七章的核心内容是整个s m a 指令级模拟框架的设计与实现，包括动态轮廓信息的采集、更新与融合机制，以及在动态轮廓信息指导下的持续执行优化。第八章总结全文，并指出我们未来的研究方向。本文的最后列出了参考文献，并附录s m a d l x s i m 模拟平台的使用手册与程序清单。国防科学技术大学研究生院学位论文第2 章相关研究现状多线程技术的起源可以分为两大类别：基于数据流模型与基于控制流模型。经过近3 0 年的研究，两个方向上均有众多的成果，如图2 1 所示。一般来讲，基于数据流模型的多线程偏向于构造多处理机系统，研究重点在延迟隐藏与粗、中粒度并行性开发。基于控制流模型的多线程结构偏向于开发多路指令流中的中、细粒度并行性。目前多数活跃的多线程技术研究属于基于控制流模型一类，侧重利用多线程、前瞻技术等改造传统体系结构模型，在保持软件兼容性的前提下获得性能提升“7 川钔 1 9 1 。o t h e r s ：m u l t t a j a r ( i 刃唧g m t ( 1 鳓，t c a l w f f e锹m a c h i a ed j 9 a 9 m z ”图2 1 多线程技术的发展本章分为四个部分：2 1 至2 4 节介绍了4 个成熟的多线程模型，对这些模型的特点进行了比较分析。这些模型属于多线程技术研究领域有代表性的工作，对本文工作的基础前瞻多线程结构s m a 有很大的启发作用。2 5 节介绍了多个体系结构研究热点，包括前瞻技术、单芯片多处理器技术、t r a c e 技术等。这些方面的研究内容同样给我们的研究工作带来许多有益的启迪和参考。最后是本章内容的小结。2 1e a r t h 系统e a r t h ( e f f i c i e n ta r c h i t e c t u r ef o rr u n n i n gt h r e a d s ) 系统的设计初衷是实现一个有效的并行计算机系统，该系统能够屏蔽并行程序中常见的通讯和同步开销，实现灵活高国防科学技术大学研究生院学位论文效的延迟隐藏2 0 “2 。e a r t h 系统属于较早从数据流方向演变过来的多线程系统。在e a r t h 系统中，线程为一串顺序执行的指令，是系统中调度的最小单位。系统在运行态检查就绪线程的启动条件( 数据或者控制相关) ，一旦条件被满足，该线程就启动执行。为了保证程序的正确语义，e a r t h 系统中引入了复杂的同步机制，称为点火规则( f i r i n gr u l e s ) 。与传统的多现场( m u l t i c o n t e x t ) 机器不同，线程一旦启动，就执行至结束，中途不会被挂起或撤消。这种模式称为非阻塞( n o n b l o c k i n g ) 模式，目前的多线程模型大都采用该模式。如图2 2 所示，一个e a r t h 结点包含一个执行单元( e x e c u t i n gu n i t ，e u ) 和一个同步单元( s y n c h r o n i z a t i o nu n i t ，s u ) ，由两个队列( 就绪队列和事件队列) 将它们联结。执行单元e u 每次取出就绪队列中的头线程，称为活跃线程。执行过程中产生的消息放入事件队列中。同步单元s u 处理就绪队列中的消息，加上来自网络的远程p e 单元的同步消息，判断线程的启动条件，加入新的线程到就绪队列中。s u 和e u 单元共享本地主存，通过两个队列来互相通讯，同时通过互联网络与远程p e 单元通讯。图2 2e a r t h 系统结构图示在e a r t h 系统中，个线程处于就绪状态说明该线程所需的数据和控制条件都已满足。存在数据相关的线程之间是一个“生产者一消费者”关系，s u 单元负责在运行时判断何时控制条件为真，所需数据可用，并将该就绪线程放到就绪队列中的适当位置。e a r t h 的同步机制与传统数据流系统不同之处主要是以下几点：e a r t h 系统中传递的是信号( s i g n a l s ) ，而不是数据，来激发线程；同步信号分为两种：控制相关同步和数据相关同步；同步信号在线程执行过程中就可以发出，不需要等到线程提交后。为了适应类数据流的执行模式，e a r t h 系统引入了一个扩展的并行c 语言版本：国防科学技术大学研究生院学位论文t h r e a d c ，扩展了对多线程底层的支持，如线程创建、线程同步、线程通讯、线程迁移等。与之对应的还有一个完善的运行时系统e a r t h m a n n a 来支持多线程原语，完成t h r e a d c 代码到硬件系统的映射( 图2 3 ) 。ce a r t h c图2 3t h r e a d c 编译环境图示作为早期的多线程研究项目，e a r t h 系统更多的关注于多处理机环境下的延迟隐藏技术和粗、中粒度并行性的开发。e a r t h 系统全面地涵盖了多线程处理器设计、多线程编译器、多线程程序设计语言以及多线程操作系统等各个方面，为后续的其他多线程结构研究带来许多有益的启发。2 2s m t 结构w a s h i n g t o n 大学的同时多线程( s i m u l t a n e o u sm u l t i t h r e a d i n g ，简称s m t ) 项目是超标量多线程结构的典型代表( 图2 4 ) 。在s m t 结构中，处理器中每个周期可以从多个激活的线程中取出多条指令同时发射到多个功能部件上并行执行。由于每个线程可以独占使用全部资源，所以单线程性能并未受到影响。而其他可以同时发射指令的线程的存在，使得单个线程剩余的未利用发射带宽不至于浪费，多个线程之间并行执行又可以互相屏蔽互锁和长延迟操作引起的阻塞。按照s m t 中的术语，即可以同时消除垂直浪费( v e r t i c a lw a s t e ) 和水平浪费( h o r i z o n t a lw a s t e ) ，达到充分利用资源，提高效率和性能的作用2 2 1 2 3 1 2 4 11 2 5 1 。国防科学技术大学研究生院学位论文图2 4s m t 结构图示s m t 中的线程都是独立的，线程之间不存在控制相关性；若线程间存在数据相关性，编译器在线程内插入显式的同步指令( 或生成新的线程) 来处理。所以，s m t 中多个线程的执行也是独立的，它们之间最多只存在父线程和子线程关系。从图2 4 可以看到，s m t 处理器是在超标量结构上直接扩充得到的。主要扩充的硬件机制包括：多个程序计数器，硬件现场( c o n t e x t ) 。每个线程一个独立的返回栈( r e t u r ns t a c k ) ，用于预测过程返回地址。每个线程一套指令回退( r e t i r e m e n t ) 、指令队列清洗( f l u s h ) 、陷入( t r a p ) 机制。每个分支目标缓冲区项扩充个线程标识( i d ) 域。t l b 项的t a g 中含线程标识( i d ) 或处理器标识( i d ) 。更大的寄存器文件，以支持所有线程的逻辑寄存器和重命名寄存器，流水线增加两级以适应增大寄存器后寄存器读写时间的延长。s m t 的性能模拟指出，利用多线程加速单个应用需要依赖高性能的多线程并行编译器的支持。但由于s m t 中线程间的同步和通讯都是显式的，也就是说线程间所有的数据相关都转化成显式的同步( 指令) 操作。这种独立的线程并行性在通用程序中的潜力还有待进一步的研究来量化。如果扩充了高效的同步机制，允许线程间保持隐式的数据相关( 指令之间通过寄存器直接相关) ，有可能实现更大程度的并行性开发。里堕型堂堇查丕兰堕窒竺堕兰垡迨塞2 3m u l t i s c a l a r 结构由w i s c o n s i n 大学提出的m u l t i s c a l a r