（计算机科学与技术专业论文）指令级并行性开发关键技术的研究与实现.pdf

国防科学技术大学研究生院学位论文，、捅要f七十多年以来，微处理器的性能已经有了巨大的提高，但是由于新应用的产生，人们对于微处理器性能的要求也越来越高。目前微处理器基本上都是以超标量技术为基础进行设计的，但这一技术已经很难进一步大幅度地提高性能。据估计，下个世纪初，微处理器将完成结构换型。因此研究新的适合于微处理器的体系结构技术迫在眉睫，是国际上研究的热点，也具有极大的科研、经济和社会意义。i 当前，在微处理器体系结构研究中，为了充分提高微处理器的处理性能，主要采用了指令级并行技术( 1 l p ) ，指令级并行性的开发程度对发挥微处理器的硬件特性，提高程序运行性能至为关键。开发更多i l p 的关键是：如何自动识别程序中的所有相关关系，并将能够并行执行的成分( 指令) 挖掘出来。在目标代码中可以区别两类数据相关，一类是寄存器数据相关，一类是存储器数据相关。对于对寄存器指令数据相关的分析相对简单，它可以直接通过对指令序列进行数据流分析得到。而对于存储器访问指令而言，其相关性分析则相对复杂得多，关键问题是必须解决存储器访问地址的别名问题( a l i a s i n gp r o b l e m ) ，即必须判断出对存储器的两次访问是否针对同一个地址单元，然后在此基础上进行存储器访问的数据相关性分析。与常用的基于数据流图的方法不同，我们提出了一种通过寄存器队列检测指令间寄存器数据相关的算法。该算法利用寄存器队列分析指令间的数据相关，能够分析出指令间的所有寄存器相关，其特点是：数据流驱动；算法简单、实现效率高：并行成分的表示直观。该算法的执行效率远远高于经典的基于图的相关性分析算法。当前大多数指令调度算法只判断出寄存器指令的数据相关，而忽略了存储器指令数据相关。它们大多数是在分析时将存储器作为一个数据单元，进而假设任何两次对存储器的访问之间都存在数据相关。我们通过一种值预测及传播算法检测存储器指令数据相关。这种方法有助于提高与存储器访问相关的指令的执行效率。模拟结果表明，该算法能够获得8 7 的加瓣睇1关键词：指令级并性，数据相关性分析，寄存器队列，符号值传播、vv 7l ，7第1 页国防科学技术大学研究生院学位论文a b s t r a c ti nt w e n t yy e a r s ，t h ep e r f o r m a n c eo fm i c r o p r o c e s s o rh a sr e a c h e dv e r yh i g h ，b u tn e wa p p l i c a t i o n sn e e dm o r ea n dm o r ec o m p u t i n gp o w e r n o w a d a y s ，a l lo ft h em i c r o p r o c e s s o rd e s i g n sa r cb a s e do nt h es u p e r - s c a l a rt e c h n o l o g y ，w h i c hh a sl i t t l er o o mf o ri m p r o v i n gp e r f o r m a n c em o r e i nt h en e a rf u t u r e ，t h ea r c h i t e c t u r ea n do r g a n i z a t i o no fm i c r o p r o c e s s o rw i l lc h a n g eg r e a t l y i t st h et i m et or e s e a r c hn e wa r c h i t e c t u r ef o rm i c r o p r o c e s s o rd e s i g n t h i sk i n do fr e s e a r c h i n gw o r ki sv e r yh o ta n di m p o r t a n t o n eo ft h ek e ye l e m e n t st oa c h i e v i n gh i g h e rp e r f o r m a n c ei nm i c r o p r o c e s s o r si se x e c u t i n gm o r ei n s t r u c t i o n sp e rc y c l e h o w e v e r ，d e p e n d e n c i e sa m o n gi n s t r u c t i o n s ，v a r y i n gl a t e n c i e so fc e r t a i ni n s t r u c t i o n s ，a n de x e c u t i o nr e s o u r c e sc o n s t r a i n t s ，l i m i tt h i sp a r a l l e l i s mc o n s i d e r a b l y i no r d e rt oe 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 ，p r o c e s s o rs h o u l de m p l o yd a t ad e p e n d e n c ea n a l y s i st oi d e n t i f yi n d e p e n d e n ti n s t r u c t i o n st h a tc a ne x e c u t ei np a r a l l e l t h e r ea r et w ot y p e so fd a t ad e p e n d e n c i e sb e t w e e ni n s t r u c t i o n s ，r e g i s t e ra n dm e m o r yd e p e n d e n c i e s i nb o t hc a s e sw ec a nd e r i v ed a t ad e p e n d e n c e sf r o mr e a c h i n gd e f i n i t i o n sa n du s e si n f o r m a t i o no b t a i n e db yd a t af l o wa n a l y s i s a ts c h e d u l et i m et r u er e g i s t e rd e p e n d e n c i e sa r ek n o w n ，s or e g i s t e ra n a l y s i sd o e sn o ti n v o l v ea n yc o m p l i c a t i o n b u tf o rm e m o r yd e p e n d e n c i e sw eh a v et od e a lw i t ht h ep r o b l e mo f a l i a s i n g ( a d d r e s s e sa r ec o m p u t e dd u r i n ge x e c u t i o n ) i nt h i sp a p e rw ep r o p o s ean e ws i m p l ea p p r o a c hf o ra n a l y z i n gd a t ad e p e n d e n c eo nd l xc o d eu s i n gr e g i s t e rq u e u e s f o re a c hr e g i s t e rw ec r e a t eaq u e u ea n dt h ei n d e xo fq u e u ei t e mm e a l q saf u n c t i o no fe x e c u t i n gt i m e t h ei t e mi nt h eq u e u ei se i t h e rn u l lo ra ni n s t r u c t i o nw h o s eo p e r a n di sk e p ti nt h i sr e g i s t e r i fo n ei t e ms t a n d sf o ra ni n s t r u c t i o n ，i t si n d e xh a ss o m er e l a t i o nw i t hi t se a r l i e s te x e c u t i o nt i m e w ea l s od i s c u s san e wa p p r o a c hf o rs o l v i n gt h ep r o b l e mo fm e m o r yd e p e n d e n c i e s o u ra n a l y s i sm a i n l yc o n c e r n st h ed e t e r m i n a t i o no fm e m o r ya d d r e s s w eu s ea i la d d r e s ss y m b o l i cv a l u ep r o p a g a t i o na l g o r i t h mt od e r i v ep o s s i b l ea d d r e s ss e tt h a tm i g h tb ea c c e s s e db yam e m o r yi n s t r u c t i o n s i m u l a t i o nr e s u l t ss h o wt h a tt h i st w om e t h o d sc a nd e t e c td a t ad e p e n d e n c en o to n l ye x a c t l yb u ta l s oe f f i c i e n t l y k e y w o r d ：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 ，d a t ad e p e n d e n c ea n a l y s i s ，r e g i s t e rq u e u e ，s y m b o l i cv a l u ep r o p a g a t i o n 第1 i 页国防科学技术大学研究生院学位论文第一章绪论1 1 研究背景自从第个微处理器4 0 0 4 在1 9 7 1 年诞生以来，微处理器已经走过了将近三十年的发展历程。在这三十年间，推动微处理器性能不断提高的因素主要有两个：工艺技术的飞速进步和体系结构技术的不断发展。工艺技术的每一次进步都为体系结构的研究提出了新的课题，开辟了新的领域；体系结构的发展又在半导体工艺发展的基础上进一步提高了微处理器的性能。这两个因素一直相互影响、相互促进。人们对提高微处理器计算性能的追求是永无止境的，尤其是随着多媒体、网络、大型数据库、高性能科学计算、人工智能等应用的普及和进一步发展，对微处理器计算性能的要求也势必越来越高。人们一方面努力提高微处理器的工艺水平，另一方面不断寻找新的微处理器体系结构技术，以满足日益紧迫的性能压力。也正因为如此，在这三十年间，微处理器的性能取得了平均每年超过3 0 的飞速发展。著名的摩尔定律表明，随着集成电路技术的迅猛发展，芯片上的集成度和性能每三年就要翻两番。按照摩尔定律推算，2 0 0 6 年微处理器将达到以下的工艺水平：芯片大小1 4英寸，线宽0 1 微米，集成3 5 亿个晶体管，主频4 ，0 0 0 m h z ，其性能将达到2 0 ，0 0 0 m i p s 。照此速度发展下去，到2 0 1 0 年左右，芯片上集成的晶体管数目将超过十亿个。因此，体系结构的研究又遇到了新的课题：如何有效利用数目如此众多的晶体管? 如何去设计与超大规模芯片相适应的微处理器体系结构?国际上，针对与超大规模芯片相适应的微处理器计算机体系结构的研究方兴未艾，主要集中在以下几个方面：超标量处理器( s u p e r s c a l a rp r o c e s s o r )超长指令字处理器( v l i wp r o c e s s o r )多线程处理器( m u l t i t h r e a d e dp r o c e s s o r ，m t p )在现有的高性能微处理器设计中，超标量结构与v l l w 结构正被或者即将被广泛使用，但它们的发展都遇到了难以逾越的障碍。超标量结构是一种通过在一个时钟周期内同时发射多条标量指令到多个功能部件以提高处理器性能的计算机体系结构技术。虽然超标量中某些技术可以追朔到c d c6 6 0 0m 删和i b m3 6 0 9 1t 2 t o m a s u l 0 6 7 1 但真正商用的超标量微处理器是8 0 年代末出现的。第一个商用超标量微处理器是i n t e l 公司于1 9 8 9 年9 月推出的i 9 6 0 c a 。如今，超标量技术无论从理论上还是从实践上都已经十分完善，正处在完全成熟和应用阶段。市场上几乎所有的商用微处理器都使用了超标量技术，它们的差别只是在实现参数的权衡上。但是，现有的研究表明，超标量结构的进一步发展已经非常困难了。一般认为8 发射( 左右) 超标量是超标量结构的实际极限，也就是说，超标量处理器最多可以在一个时钟周期内同时发射8 条标量指令b 啦“瓶9 5 1 ，这是由超标量技术本身所存在的局限性和缺点所决定的。总的第1 页国防科学技术大学研究生院学位论文来说，超标量技术中存在的问题主要体现在以下四个方面：a 、超标量技术难以开发出程序中更大的i l p ：b 、超标量技术的实现复杂度随着规模( 发射带宽等) 的增加增长很快( p a l a c h a r l a 9 6 1 ；c 、超标量处理器中资源利用率极低：d 、不断增长的处理器和主存性能差对超标量处理器的性能影响很大。资源利用率低的根本原因是由于程序中所存在的数据相关、控制相关使得超标量结构的指令调度窗口往往非常低效，其中的空操作指令( h o p ) 比较多。超标量技术的局限性使得性能很难有大的提高，但在其上还可以进行许多改进和替代结构以进一步提高性能，而且这些改进对未来的结构也有参考价值。改进技术主要有：深度的前瞻性执行，如无异常指令( n o n e x c e p t i n gi n s t r u c t i o n ) 和b o o s t i n g 技术，以及针对存储器访问指令的数据前瞻等等。但总的来说，它们带来的性能提高是有限的，这是因为当把这些技术应用于超标量结构时，他们都没有完全从根本上改变超标量技术的局限性，也就不可能飞跃性地提高超标量处理器的性能。超长指令字结构( v l i w ，v e r yl o n gi n s t r u c t i o nw o r d ) 完全利用编译技术静态地开发程序中的i l p 。它最早是由美国y a l e 大学的f i s h e r 教授于1 9 8 3 年提出的，其基本思想来自于计算机的水平微程序设计原理。1 9 8 7 年推出的m u l t i f l o wt r a c e 7 是第一个商用的v l l w 处理器。由于编译可以对程序进行全局的指令分析，在一个( 虚拟的) 很大的指令窗口中调度指令，所以有可能开发出比超标量技术更大的i l p ；而且由于指令调度完全由编译完成，所以硬件设计十分简单，不会出现超标量中的实现复杂度问题，只要编译可以开发出更大的i l p ，v l l w 处理器就可以简单地靠增大处理器规模来提高性能。正是由于这两个突出的优点，v l l w 被许多人看好作为超标量的下一代替代技术。众多研究单位一直在广泛研究v l i w 技术，许多公司已经宣布将推出基于v l l w 的主流产品。而且，在媒体处理器( m e d i ap r o c e s s o r ) 领域，v l i w 技术已被广泛接受。可以说，v l i w 技术正在走向成熟，有望成为主流技术。但是，在v l i w 体系结构中，开发的是标量操作中的随机并行性，其成功与否主要取决于是否能有一个高效的编译器以承担硬件的调度功能和并行性开发功能。同时，兼容性问题也是制约v l i w 结构发展的一个重要因素，这是v l i w在推广中遇到的最大障碍。另外，资源利用率低和受存储延迟影响大的问题在v l l w 中也很严重。m t p 结构则是以线程作为执行调度的基本单位，多个线程按照数据流驱动的方式并发执行，以达到相互隐藏长延迟操作和提高并行度的效果，它依赖于高性能的多线程并行编译器的支持。多线程体系结构的优点在于它是一种通用的延迟隐藏技术，并且可以极大地提高处理器的利用率，从而提高整体性能。而且由于它独立于特定的基本体系结构，所以软件兼容性不成问题。m t p 结构也有两个缺点：一是依赖于一个高性能的多线程并行编译器，这也是所有多线程结构的共同问题；二是取指令机制、带宽、寄存器文件组织、访问延迟往往成为多线程超标量结构的性能瓶颈，会限制其实际性能的提高，并进一步限制其规模的扩充。单纯的超标量处理器的性能潜力已经不大，而在其上进行的各种改进技术虽然能使性第2 页国防科学技术大学研究生院学位论文能有所提高，但因为仍无法摆脱超标量结构的基本局限性，所以性能难以有本质上的提高。几种替代的体系结构技术则各有优缺点，有的无法满足进一步的性能要求( 如v l l w 和多线程) ，有的实现上过于复杂( 如超前瞻性执行) 。从这些研究中我们可以得到这样三点启不：要开发出程序中较大的i l p ，必须将软件编译技术和硬件动态调度技术在体系结构上更加紧密和深入地相结合；前瞻性执行是一种十分有益的提高i l p 的手段，但必须克服实现深度前瞻性执行的复杂性，这就需要开拓新的技术思路和体系结构技术：多线程技术对于解决处理器存储器瓶颈问题以及提高资源利用率是一个很好的途径，它可以作为其他结构的一个很好的补充技术。据d e c 推测，2 0 0 3 年每周期的指令发射速率将增加到3 2 条，在体系结构和编译技术方面若没有大的突破，要开发如此高的i l p 是相当困难的，因此需要编译器和系统软件在未来的体系结构中能够自动地析取并行性。另外，由于指令集兼容性的问题，向后兼容已有软件的问题也妨碍了体系结构的创新。因此，编译器、代码翻译软件的好坏越来越影响着系统性能。1 2 问题与研究l - 2 1 研究现状及本课题的研究目的从处理器结构设计的角度来说，提高系统性能的一个主要技术思路就是并行处理。抽象地说，在冯诺伊曼结构下，一个程序的执行由一组受程序控制结构制约的计算操作和数据的通讯构成。并行处理的基本观点就是采用冗余的硬件资源并行地处理多个计算操作和数据的通讯过程，从而减少总的执行时间。在这个抽象模型中，程序的执行时间同程序的计算与通讯总量、处理器周期、平均每周期处理的计算量和通讯量都有密切的关系。程序中的并行性可以有很多种分类方法：规则的和不规则的；粗粒度与细粒度；数据并行与指令并行等等。不同的程序类型具有不同的并行性，不同的体系结构侧重于开发不同的并行性。指令级并行( 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 ) 是一种普遍存在于各类程序中的细粒度并行性，现今的微处理器基本上都是以开发i l p 作为其主要性能提高手段。另一方面，i l p 同各种粗粒度的并行性是互补的，未来的高性能处理机都将是由多个i l p 处理器构成的复合系统。由此看来，对i l p 的研究十分重要和必要。本文正是探索i l p开发中的问题，并提出新的开发i l p 的体系结构技术。开发更多i l p 的关键是：如何自动识别程序中的所有相关关系，并将能够并行执行的成分( 指令) 挖掘出来。当前国内外相关的研究工作主要存在下面一些问题：当前的微处理器体系结构中大多采用动态调度策略，在一定大小的调度窗口中提取- ，、_ 、一，_ ，d l ，- _ k ，、指令序列的并行成分，并行性分析主要是基于指令流驱动模型，调度算法复杂，并且并行性表示不够直观、不够简单，从而增加了微处理器内部指令调度部件的硬件实现复杂度。第3 页国防科学技术大学研究生院学位论文已有的多数在编译阶段进行的并行性分析工作主要由并行优化编译器系统在源代码一级或中间代码一级上进行，针对目标代码的分析技术还研究的比较少。这为保证微处理器二进制代码兼容带来了很多困难。目前，存储器的性能的提高已经远远落后于处理器性能的提高，次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 访问的主动服务部件设计提供支持。本课题得到了国家自然科学基金( n o 6 0 1 7 3 0 4 0 ，6 9 9 3 3 0 3 0 ) ；国家“八六三”高技术研究发展计划资金( n o 8 6 3 s o c y 321 ) 的支持。1 2 2 研究内容本课题的研究总体技术思路是：分析已有的并行性分析技术，面向二进制代码兼容，以极大开发指令序列的并行成分，实现( 软件实现或硬件实现) 简洁、高效为目标，研究指令级并行性开发的关键技术，提出指令级并行性开发算法，以及存储器访问数据相关性分析算法，并对算法进行软件实现，通过对基准程序的测试，评估算法的效能。课题研究的主要内容有：l 、全面深入地研究各种主要i l p 技术。2 、研究基本程序块指令之间存在的并行性，设计出一种寄存器数据并行开发算法。3 、针对存储器访问指令，设计出一种存储器访问数据并行开发算法。4 、在以上两个算法基础上，进一步研究与其他技术结合的方法。在课题研究中，将采取自下而上的研究方法，在基础理论和关键技术研究的基础上，开展实现技术的研究，理论和实践相结合，以理论指导设计实现，以模拟验证关键技术。该项目的工作将分为三个阶段进行，第一阶段是研究已有的指令调度算法和相关的并行性开发算法；第二阶段开展指令级并行性开发的相关算法研究：第三阶段将以第二阶段的关键技术研究成果为基础，进行软件实现，并通过基准程序对所提出的算法进行模拟和效能验证。1 2 3 关键技术和课题研究意义面向与当前主流高性能通用微处理器指令集兼容和设计高性能的嵌入式微处理器内核，我们针对以下关键技术进行了研究：第4 页国防科学技术大学研究生院学位论文相关性检测分析技术：无论程序的执行是数据流驱动还是控制流驱动，相关性检测始终是影响i l p 开发的一个关键因素在流水线资源充分的情况下，指令间的相关主要包括寄存器指令数据相关、存储器指令数据相关和控制指令相关三部分，它们严重妨碍了程序指令级并行( i l p ) 的提高。寄存器重命名技术：寄存器重命名的目的是为了增加处理器并行流出指令条数，从而提高系统的性能。它通过增加需要使用的物理寄存器的数量和寄存器读写的带宽，从而获得较高的i p c 。寄存器重命名利用寄存器重用可以消除反相关和输出相关，并使得在乱序执行时避免不必要的停顿。存储器访问预测技术：存储器重命名的方法类似相关性预测，它在预测相关性的同时预测值。区别在于相关性预测基于对相关性的推断，而存储器重命名基于对l o a d 即将访问的值的推测。存储器重命名预测相关或一个值，该值一旦可用则马上可以被相关指令所使用。只有在该值不正确时预测失败。另一个不同是存储器重命名在一个比用于相关预测的存储集合更大的指令窗口范围内记录s t o r e 和l o a d 指令之间的相关。数据前瞻技术：提前访存指令的执行到可能与它存在数据相关的访存指令的执行之前执行，这样访存指令可以乱序地执行，处理器不会因为访存指令的阻塞而长时间地阻塞处理器发射其他指令执行。它要求访存控制器在访存指令的所有数据相关性完全确定之前就能处理这个访存指令。若访存指令前瞻执行错误，还需要进行恢复工作。符号值传播技术：为了比较精确的分析可能的存储器访问地址集合，必须有一种方法来描述和计算这些未知的值。使用符号值的概念，对每一个寄存器和每条程序语句计算可能的符号值集合( 符号值传播过程) ，然后使用符号地址信息和控制流信息来决定可能、肯定别名信息。扩大基本块技术：超标量和v l i w 处理器的编译器必须能够开发出大量的指令级并行以有效的利用并行执行硬件。但是对于大多数程序而言，基本块内的i l p 受到很大的限制，因此需要研究开发出跨越基本块边界的i l p 的方法。数据预取技术：数据预取通过提前把即将被使用的数据从存储器取入c a c h e 以减少可能的c a c h e 失效，从而提高处理器的执行性能。它与推测执行l o a d 操作的最大不同在于后者把数据直接从存储器取入寄存器中，因此寄存器数量的限制并不会像对推测执行l o a d那样对数据预取造成影响。在微处理器设计中，开发指令级并行是提高微处理器系统性能的关键技术。微处理器每个时钟周期可以处理的指令条数直接取决于程序中可以开发的并行成分。为了在每个时钟周期可以流出多条指令，编译器必须可以开发出大量的可并行执行指令。否则，当指令不满时，会造成计算资源闲置。对于这一领域的研究对于微处理器系统设计具有重要的理论意义和实用价值。开发更多i l p 的关键是识别程序中的相关性成分。但是，传统的微处理器体系结构大多采用动态调度策略，相关性分析基于指令流驱动模型，算法复杂，并且并行性表示不够直观、不够简单，从而增加了硬件实现的复杂度。而且，数据相关的分析工作大多由并行优化编译器系统在源代码一级或中间代码一级上进行，针对目标代码的分析技术还研究的第5 页国防科学技术大学研究生院学位论文比较少。由于目标代码指令的规整性，对它进行相关性分析可能可以设计出简单高效的数据相关分析算法，这对于实现与某种已有i s a 的二进制代码兼容也具有重要的现实意义。1 3 课题研究结果和论文组织1 3 1 课题研究结果经过近两年的研究，课题研究工作主要在以下两个方面取得了一定的结果：提出了一种寄存器数据相关性分析的方法，对该算法进行了形式化描述，并对其进行了模拟、测试，验证了该算法的效能。提出了一种存储器访问数据相关性分析的方法，对该算法进行了形式化描述，并对其进行了模拟、测试，验证了该算法的效能。这些初步的研究结果对我们自主进行高性能微处理器设计具有一定的借鉴作用。1 3 2 论文组织本文是对我们的研究工作的总结，全文分为六章：第一章简要介绍了本课题的背景、研究现状和研究目的、研究内容、关键技术和研究意义：第二章介绍了指令集并行技术和数据相关性分析的总体方法和分析流程；第三章主要设计了一种寄存器数据相关性分析的方法，对该算法进行了形式化描述，并对其进行了模拟、测试，验证了该算法的效能：第四章描述了种存储器数据相关性分析的方法，对其进行模拟、测试和效能验证。第五章主要结合了其他一些提高指令级并行性的关键技术，进一步研究开发i l p 的方法。最后，对研究工作进行了总结，并提出了几个需要进一步深入研究的问题。第6 页国防科学技术大学研究生院学位论文第二章指令集并行和数据相关性分析方法2 1l l p 技术未来的微处理器芯片将被设计成具有更高的时钟速率、更高的i l p 、更低的c p i 、更低的功耗和更复杂的软件支持。当前，在微处理器体系结构研究中，为了充分提高微处理器的处理性能，主要采用了指令级并行技术( i l p ) ，指令级并行性的开发程度对发挥微处理器的硬件特性，提高程序运行性能至为关键。i l p 技术是指一套处理器设计和编译技术，这些技术通过并行地执行独立的机器操作( 指令) ，如存储器读写、整数、浮点等来加速程序的执行。i l p 的大小可以采用每周期平均执行的指令数( i p c ) 来衡量，或者采用整个程序的每条指令平均执行的周期数( c p i ，c p i = i i p c ) 来衡量。对i l p 的开发受到三方面条件的制约：程序中固有的i l p ；处理器硬件可支持的i l p ：处理器体系结构和实现的组织结构可以开发出的i l p ：处理器最终得到的i l p 将等于上面三者中最小的一个。2 1 1 程序中固有的i l p要研究程序中的i l p 潜力，必须建立理想的处理器模型，常用的理想处理器模型有两个：o r a c l e 模型：假定完全正确的分支预测，分支开销为o ，分支不影响代码正确执行：b y p a s s i n g 模型：程序沿着分支的两条路径同时执行下去，即旁路了分支，分支开销也是0 ，同样不影响代码正确执行。对理想处理器模型的研究表明，程序中存在着大量的i l p ( 表1 1 ) ；。胁8 4 1 嘶8 瑚8 15 m 2 b 咖一1 l “9 2 1 。这些实验研究的对象包括数值计算程序和非数值计算程序，数值计算程序中的i l p 是十分巨大的，即使在非数值计算程序中，i l p 的潜力也很大。表2 1理想模型的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 l 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 】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 c s1 5 8 2 6包括一些非s p e c 代码第7 页国防科学技术大学研究生院学位论文值得注意的是，i l p 的大小实际上是一个与编译( 变换) 技术、机器结构、程序特性和数据结构都有密切关系的量。所以，我们得到的i l p 的理想极限值应理解为在理想状态下至少可测得的最大并行度。当然，随着v l s i 的特征线宽逐渐进入深亚微米水平，v l s i 工艺特性正在发生巨大变化，这些变化无疑会对未来处理器的设计产生深刻影响。例如集成度的极大提高使得在单个芯片内可以容纳更多的资源，但同时芯片内长线延迟的影响越来越大，布线和封装的困难以及功耗的增加会进一步加大处理器主存瓶颈。但总的来说，未来处理器硬件有能力支持大量的i l p 开发。2 1 2 目前工业界可达到的i l p虽然程序中存在大量的i l p ，v l s i 也可以充分支持大量i l p 的开发，但目前工业上可实现的i l p 却不大。图2 1 是实测的p e n t i u m 处理器( 2 发射超标量c i s c ) 运行s p e c 9 2 程序得到的c p i值8 。o 。”9 ”。图2 1p e n t i u ms p e c 9 2 测试c p i 值造成实际中i l p 小的原因是多方面的，但i l p 开发中的困难是基本的因素。2 1 3i l p 开发中的技术问题开发程序( 尤其是非数值计算程序) 中的i l p 存在一些困难和需解决的问题，概括地说，当前微处理器开发i l p 主要需要解决以下三个方面的问题：首先，何时提取i l p ? 一种方式是在编译时提取，另一种方式是在运行时动态地提取。两种方法都各有其优缺点，并独立地发展出多项技术，例如静态提取i l p 的v l i w 技术和动态提取i l p 的超标量技术。当前的许多技术都是独立地运用静态i l p 技术或动态i l p 技术，实际效果并不理想，因此我们认为完全依赖任何一种方式都不是最佳的，必须将二者有机地结合起来。这样一来，如何将二者有机地结合就成为了一个关键的问题，这也是当前i l p 技术研究的一个热点。其次，在什么范围内提取i l p 7 研究表明，由于串行程序中分支指令的影响，少数几第8 页国防科学技术大学研究生院学位论文个顺序的基本块内存在的i l p 很小，但在大量基本块中i l p 却很大，这就要求处理器建立一个巨大的指令窗口。但由于程序中控制相关性的大量存在和程序控制流向的不确定性，建立一个大的指令窗口并不容易。更进一步，指令窗口中的指令应有较大的概率被执行才能真正提高性能，我们称这样的窗口为高效的窗口。研究表明，单个指令流中很难建立高效的窗口，这就要求处理器能从多条指令流中建立一个复杂的窗口来提高窗口的效率，此项工作更加困难，也是人们研究的重点之一。最后，采用什么控制机制提取i l p ? 提取i l p 的控制机制的关键是要克服机制实现时造成的控制和数据通路的复杂度。由于随着v l s i 规模的扩大，v l s i5 1 2 艺特性发生变化，降低芯片内线延迟变得越来越重要，因此过于复杂的控制机制事实上无法高效实现，反而会降低主频，也就没有实际应用意义。例如传统的集中控制方式的指令调度机制就很难大规模高效地实现。因此研究适合未来v l s i 特性，具有规模可伸缩性的控制机制十分重要。2 2 数据相关分析方法无论程序的执行是数据流驱动还是控制流驱动，相关性检测始终是影响i l p 开发的一个关键因素。研究程序代码中的相关性，不但可以明确指令的调度，而且可以明确代码固有的并行性和可以获得的并行性。相关的两条指令不但不能同时执行，改变指令的顺序也会b 1 起问题。般来说，流水线中的相关主要分为以下三种类型：l 、结构相关：当指令在重叠执行过程中，硬件资源满足不了指令重叠执行的要求，发生资源冲突时将产生“结构相关”。2 、数据相关：当一条指令需要用到前面指令的执行结果，而这些指令均在流水线中重叠执行时，就可能引起“数据相关”。3 、控制相关：当流水线遇到分支指令和其他会改变p c 值的指令时就会发生“控制相关”。为了能够在流水线中执行指令的所有可能，而不发生结构相关，通常采用流水化功能单元或资源重复的方法。硬件代价完全可以消除这种相关。控制相关是由分支指令引起的相关，它需要根据分支指令执行的结果来确定后续指令执行的顺序。处理控制相关一般采用预测以及各种扩大基本块的方法。数据相关可能发生在一对指令对同一寄存器或存储器同一单元进行读写的时候。根据指令对寄存器的读写顺序，可以将数据相关分为如下三种类型。考虑流水线中的两条指令i 和j ，且i 在j 之前进入流水线，由此可能带来的数据相关有：( 1 ) 写后读相关( r a w ) ：j 的执行要用到i 的执行结果，但是当其在流水线中重叠执行时，j 可能在i 写入其计算结果之前就先行对保存该结果的寄存器或存储器单元进行读操作，从而可能得到错误的值。( 数据相关)( 2 ) 写后童写相关( w a w ) ：j 和i 的目的操作数一样，但是当其在流水线中重叠执行时，j 可能在i 写入其计算结果之前就先行对保存该结果的寄存器或存储器单元进行写操作，第9 页国防科学技术大学研究生院学位论文从而导致写入顺序错误，在目的寄存器或存储器单元留下错误的值。( 反相关)( 3 ) 读后写相关( w a r ) ：j 可能在i 读取某个源寄存器或存储器单元的内容之前就先对该寄存器进行写操作，导致i 后来读取到错误的值。( 输出相关) 。数据相关具有传递性，分析数据相关的主要工作是：确定指令的相关性；确定数据的计算顺序确定最大并行性。编译器可以通过重新组织代码顺序来消除由数据相关带来的暂停。在目标代码中可以区别两类数据相关，一类是寄存器数据相关，一类是存储器数据相关。对于非访存指令，操作的数据来自于寄存器。而寄存器名可以完全地标识出一个确定的寄存器，所以即使在指令未执行前( 只要指令译码完成) ，我们就能确定指令之间的相关性。也就可以前瞻性地执行指令。我们称这种相关性为单义的( u n a m b i g u o u s ) 相关性。而对于访存指令，访存指令之间是通过存储器单元发生数据相关，而由于寻址方式的多样性( 例如：间接寻址) ，使得在处理器计算出指令的访存地址之前，我们无法确定访存指令之间的数据相关性，也就无法前瞻地执行访存指令。我们称这种相关性为多义的( a m b i g u o u s ) 相关性。访存指令的顺序执行虽然保证了程序执行的正确，但由于程序中访存指令的比例比较大，当前瞻执行的深度增加时，顺序执行的访存指令必然成为性能提高的一大障碍。对于对寄存器指令数据相关的分析相对简单，它可以直接通过对指令序列进行数据流分析得到。而对于存储器访问指令而言，其相关性分析则相对复杂得多，关键问题是必须解决存储器访问地址的别名问题( a l i a s i n gp r o b l e m ) ，即必须判断出对存储器的两次访问是否针对同一个地址单元，然后在此基础上进行存储器访问的数据相关性分析。寄存器数据相关信息可以通过检测指令的寄存器操作数在解码阶段获得。而存储器访问数据相关需要计算存储器的访问地址，地址的计算必须在寄存器操作数就绪和指令被发射覆后方可进行，因此在解码阶段不能检测出存储器访问是否存在相关。7数据相关性分析的流程如图2 2 所示：z ，图2 2数据相关性分析的流程图第1 0 页国防科学技术大学研究生院学位论文与常用的基于数据流图的方法不同，我们提出了一种通过寄存器队列检测指令问寄存器相关的算法。该算法利用寄存器队列分析指令问的数据相关，能够分析出指令间的所有寄存器相关，其特点是：数据流驱动；算法简单、实现效率高；并行成分的表示直观。该算法的执行效率远远高于经典的基于图的相关性分析算法。具体的算法描述和性能分析见越。当前大多数指令调度算法只判断寄存器指令的数据相关，而忽略了存储器指令数据相关，而是将存储器作为一个数据单元，假设任何两次对存储器的访问之间都存在数据相关。我们通过一种值预测及传播算法检测存储器指令数据相关。这种方法属于静态地址多义性消除的技术，它有助于提高与访存相关的指令的执行效率。整个过程是由编译完成的，它的好处是无论如何这种分析不会造成任何副作用，因为前瞻执行的访存指令都是经过分析必定可以提前执行的指令，不会需要恢复工作。这种方法的另一个优点是它是一项相对独立的技术，不仅可以应用在超标量处理器中，也可以应用在其他结构的i l p 处理器中。具体的算法描述和性能分析见第三章。2 3 性能测试说明2 3 1 体系结构说明我们以d l x 指令集为基础，为了简化分析过程，不考虑c a c h e 访问，假设系统体系结构如图2 3 ：d l x 指令集主要有如下几类：+ n oa r g s + l o a d 重命名图2 3假设系统体系结构图r i oo p c r a n d s( r e g i s t e r , a d d r e s s )第1 i 页国防科学技术大学研究生院学位论文+ s t o r e 一+ l u i + a r i t h 一女+ m u l d i v 一+ b r a n c h00 p 一+ b r a n c hlo p + j u m p + s r c l + l a b e l + m o v e + f l o a d + f s t o r e + f a r i t h + f c o m r 眦+ t r a p 一( a d d r e s s ，r e g i s t e r )( d e s t ，1 6 一b i te x p r e s s i o n )( d e s t ，s r c l ，s r 2 c ) o r ( d e s t s r c l ，s r c 2 )o r ( d e s t ，s r c l ，1 6 一b i ti m m e d i a t e )o r ( d e s g s r c l ，16 - b i ti m m e d i a t e )s a m ea sa r i t h ( s p e c i a ls u b s e tt oh a n d l em u w d i v i d e r e mi n s t r u c t i o n sb e c a u s et h e yo p e r a t eo nf l o a t i n gp o i n tr e g i s t e r s )( 1 a b e l ) t h es o u r c er e g i s t e ri si m p l i e d( s r c l ，l a b e l )( 1 a b e l ) o r ( s r c l )( s r c l )( 1 a b e l )( d e s t ，s r c l )l i k el o a d ，f o rf l o a t i n g d o u b l el i k es t o r e ，f o rf l o a t i n g d o u b l el i k ea r i t h ，f o rf l o a t i n gp o i n tc o m p a r et w of l o a t i n gp o i n tn u m b e r s( t r a pn u m b e r )表2 2 给出了d l x 指令和它的分类表2 2d l x 指令及其分类a r i t ha d d ，a d d i ，a d d u ，a d d u i ，s u b ，s u b i ，s u b u ，s u b u i ，a n d ，a n d i ，o r ，o r i ，x o r ，x o r i ，s r a ，s r a i ，s r l ，s r l i ，s l l ，s l l i ，s l e ，s l e i ，s l e u ，s l e u i ，s e t , s l t i ，s l t u ，s l t u i ，s n e ，s n e i ，s n e u ，s n e u i ，s e q ，s e q i ，s e g u ，s e q u i ，s g e ，s g e i ，s g e u ，s g e u i ，s g t , s g