第4章-指令级并行PPT.ppt

《第4章-指令级并行PPT.ppt》由会员分享，可在线阅读，更多相关《第4章-指令级并行PPT.ppt（116页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、LOGO顾一禾 制作 2013 第5版2第第4章章指令级并行指令级并行主讲：主讲：顾一禾顾一禾 2 本章学习内容u指令指令级并行的基本概念并行的基本概念u指令的指令的动态调度度u动态分支分支预测技技术u多指令流出技多指令流出技术2 4.1指令级并行指令级并行u指令之指令之间存在的潜在并行性称存在的潜在并行性称为指令指令级并行并行。（。（ILP：Instruction-LevelParallelism）u只有将硬件技只有将硬件技术和和软件技件技术互相配合，互相配合，才能才能够最大限度地挖掘出程序中存在的指最大限度地挖掘出程序中存在的指令令级并行。并行。2 1.流水线处理机的实际流水线处理机的实际

2、CPIu流水流水线处理机的理机的实际CPI就是理想流水就是理想流水线的的CPI加上各加上各类停停顿的的时钟周期数：周期数：CPI流水流水线=CPI理想理想+停停顿结构冲突构冲突+停停顿数据冲突数据冲突+停停顿控制冲突控制冲突uCPI理想理想即理想即理想CPI，是衡量流水，是衡量流水线最高性最高性能的指能的指标之一。之一。2 IPC（InstructionsPerCycle）uIPC：每个：每个时钟周期内完成的指令条数。周期内完成的指令条数。uIPC是是CPI的倒数。的倒数。u提高提高IPC的途径之一是减少的途径之一是减少CPI流水流水线。2 2.基本程序块基本程序块u基本程序基本程序块：一段除

3、了入口和出口以外不：一段除了入口和出口以外不包含其他分支的一个包含其他分支的一个线性代性代码段。段。u因因为程序往往平均每程序往往平均每57条指令就会有一条指令就会有一个分支，而且指令之个分支，而且指令之间还可能存在相关，可能存在相关，所以在基本程序所以在基本程序块中能开中能开发的并行性是很的并行性是很有限的，很可能比基本有限的，很可能比基本块的大小要小很多。的大小要小很多。u为了明了明显地提高性能，必地提高性能，必须跨越多个基本跨越多个基本块开开发指令的并行性。指令的并行性。2 3.开发指令级并行常用的方法开发指令级并行常用的方法u（1）开）开发循循环级并行并行u循循环级并行（并行（Loop

4、levelparallelism）：循循环程序不同迭代之程序不同迭代之间存在的并行性。存在的并行性。u例：例：for（i=1；i500；i=i1）ai=ais；n在每一次循在每一次循环的内部，没有任何的并行性。的内部，没有任何的并行性。n每一次循每一次循环都可以与其他的循都可以与其他的循环重叠并行重叠并行执行。行。u开开发循循环级并行性是增加指令之并行性是增加指令之间并行性的最并行性的最简单和最常用的方法。和最常用的方法。2 开发循环级并行的基本技术开发循环级并行的基本技术u采用循采用循环展开技展开技术u采用向量指令和向量数据表示采用向量指令和向量数据表示2 （2 2）解决相关与流水线冲突问题

5、）解决相关与流水线冲突问题u相关相关是程序固有的一种属性，它反映了程序中是程序固有的一种属性，它反映了程序中指令之指令之间的相互依的相互依赖关系。关系。u相关的三种相关的三种类型：数据相关、名相关、控制相型：数据相关、名相关、控制相关。关。u如果两条指令相关，它如果两条指令相关，它们就不能并行就不能并行执行，或行，或只能部分重叠只能部分重叠执行。行。u由于相关的存在，使得指令流中的下一条指令由于相关的存在，使得指令流中的下一条指令不能在指定不能在指定时钟周期周期执行，就是行，就是发生了生了流水流水线冲突冲突。u相关的存在限制了指令相关的存在限制了指令级并行（并行（ILP）的开）的开发。2 u流

6、水流水线冲突的三种冲突的三种类型：型：结构冲突、数据冲突、构冲突、数据冲突、控制冲突。控制冲突。n结构冲突：由硬件构冲突：由硬件资源冲突造成。源冲突造成。n数据冲突：由数据相关和名相关造成。数据冲突：由数据相关和名相关造成。n控制冲突：由控制相关造成。控制冲突：由控制相关造成。u具体的一次相关是否会具体的一次相关是否会导致致实际冲突冲突的的发生以生以及及该冲突会冲突会带来多来多长的停的停顿，根据流水，根据流水线的属的属性而定。性而定。2 解决相关与冲突的方法解决相关与冲突的方法u保持相关，但保持相关，但避免避免发生冲突生冲突。n方法：指令方法：指令调度，包括静度，包括静态调度和度和动态调度。度

7、。u通通过代代码变换，消除相关。，消除相关。2 解决相关与冲突时需注意的问题解决相关与冲突时需注意的问题u由于相关的存在，在开由于相关的存在，在开发指令指令级并行并行时，如果，如果可能影响到程序的正确性，就必可能影响到程序的正确性，就必须注意保持程注意保持程序序顺序。序。n程序程序顺序序：由源程序确定的在完全串行方式：由源程序确定的在完全串行方式下指令的下指令的执行行顺序。序。u控制相关并不是一个必控制相关并不是一个必须严格保持的关格保持的关键属性。属性。n当存在控制相关当存在控制相关时，在，在对程序的正确性没有程序的正确性没有影响的前提下，可以不遵守控制相关的依影响的前提下，可以不遵守控制相

8、关的依赖关系，关系，执行本来不行本来不该执行的指令。行的指令。2 必须保持的最关键的两个属性必须保持的最关键的两个属性u要正确地要正确地执行程序，必行程序，必须保持的最关保持的最关键的两个的两个属性是：属性是：数据流数据流和和异常行异常行为。u保持异常行保持异常行为：无无论怎么改怎么改变指令的指令的执行行顺序，序，都不能改都不能改变程序中异常的程序中异常的发生情况。生情况。n原来程序中是怎么原来程序中是怎么发生的，改生的，改变执行行顺序后序后还是怎么是怎么发生。生。n可弱化可弱化为：指令：指令执行行顺序的改序的改变不能不能导致程致程序中序中发生新的异常。生新的异常。u如果能做到如果能做到保持保

9、持程序的数据相关和控制相关，程序的数据相关和控制相关，就能保持程序的数据流和异常行就能保持程序的数据流和异常行为。2 u例：例：DADDUR2，R3，R4BEQZR2，L1LWR1，0（R2）L1：u如果不保持关于如果不保持关于R2的数据相关，程序的的数据相关，程序的执行行结果果就会改就会改变。u如果不保持控制相关，把如果不保持控制相关，把LW指令移到指令移到BEQZ之前，之前，就有可能就有可能产生一个新的生一个新的“访存保存保护”异常（如果异常（如果R20）。）。2 u数据流数据流：指数据：指数据值从其从其产生者指令到其消生者指令到其消费者者指令的指令的实际流流动。n分支指令使得数据流具有分

10、支指令使得数据流具有动态性性，因，因为它使它使得得给定指令的数据可以有多个来源。定指令的数据可以有多个来源。n仅仅保持数据相关性是不保持数据相关性是不够的的，一条指令可，一条指令可能与多条先前的指令数据相关，程序能与多条先前的指令数据相关，程序顺序决序决定了哪条指令真正是所需数据的定了哪条指令真正是所需数据的产生者。生者。u只有再加上保持控制只有再加上保持控制顺序，才能序，才能够保持程序保持程序顺序。序。2 u例：例：DADDUR1，R2，R3BEQZR4，L1DSUBUR1，R5，R6L1：ORR7，R1，R8uOR指令中使用的指令中使用的R1值取决于取决于BEQZ指令分支的指令分支的是否成

11、功。即是否成功。即OR与与DADDU或或DSUBU指令相关。指令相关。u必必须通通过保持控制相关，避免保持控制相关，避免对数据流的修改，数据流的修改，以保以保证数据流的正确。数据流的正确。uDSUBU不能被移到不能被移到BEQZ之前。之前。2 u有有时，不遵守控制相关既不影响异常行，不遵守控制相关既不影响异常行为，也不改也不改变数据流。在数据流。在这种情况下，可以大胆种情况下，可以大胆地地进行指令行指令调度，把失度，把失败分支中的指令分支中的指令调度度到分支指令之前。到分支指令之前。2 u例：例：DADDU R1，R2，R3BEQZR12，SkipnextDSUBUR4，R5，R6DADDUR

12、5，R4，R9Skipnext：ORR7，R8，R9u如果已知如果已知R4在在Skipnext后不再被使用，而且后不再被使用，而且DSUBU指令不会指令不会产生异常，那么就可以把生异常，那么就可以把DSUBU指令移到指令移到BEQZ之前。之前。u因因为这个移个移动不会改不会改变数据流。数据流。2 开发指令的并行性的方法开发指令的并行性的方法u硬件方法：指令的硬件方法：指令的动态调度、度、动态分支分支预测、多指令流出技多指令流出技术。u软件方法：指令的静件方法：指令的静态调度、循度、循环展开技展开技术。u软硬件硬件结合方法：合方法：显式并行指令式并行指令计算算EPIC。2 4.5循环展开和指令调

13、度循环展开和指令调度u4.5.1循循环展开和指令展开和指令调度的基本方法度的基本方法u为了充分了充分发挥流水流水线的作用，必的作用，必须设法法让它它满负荷工作。因此要充分开荷工作。因此要充分开发指令之指令之间存在的并存在的并行性，找出不相关的指令序列，行性，找出不相关的指令序列，让它它们在流水在流水线上重叠并行上重叠并行执行。行。u增加指令增加指令间并行性最并行性最简单和最常用的方法和最常用的方法n开开发循循环级并行性并行性循循环的不同迭代之的不同迭代之间存存在的并行性。在的并行性。n在把循在把循环展开后，通展开后，通过重命名和指令重命名和指令调度来度来开开发更多的并行性。更多的并行性。2 编

14、译器指令调度能力的限制编译器指令调度能力的限制u编译器完成指令调度的能力受限于两个特性：编译器完成指令调度的能力受限于两个特性：n程序固有的指令级并行性；程序固有的指令级并行性；n流水线功能部件的执行延迟。流水线功能部件的执行延迟。2 浮点流水线延迟浮点流水线延迟uLoad指令的结果可以通过定向路径及时送给指令的结果可以通过定向路径及时送给store指指令，所以延迟为令，所以延迟为0，不用插入停顿。，不用插入停顿。产生结果的指令产生结果的指令使用结果的指令使用结果的指令 延迟（时钟周期数）延迟（时钟周期数）浮点计算浮点计算另一个浮点计算另一个浮点计算3浮点计算浮点计算浮点浮点store（S.D

15、）2浮点浮点load（L.D）浮点计算浮点计算1浮点浮点load（L.D）浮点浮点store（S.D）02 u例例4.6对于下面的源代于下面的源代码，转换成成MIPS汇编语言，言，在不在不进行指令行指令调度和度和进行指令行指令调度两种情况下，度两种情况下，分析其代分析其代码一次循一次循环所需的所需的执行行时间。nfor(i=1；i=1000；i+)nxi=xi+s；u解：解：u该循循环的不同迭代之的不同迭代之间不存在相关，所以多次迭不存在相关，所以多次迭代可以并行代可以并行执行。行。2 uMIPS汇编语言代言代码：u假假设R1的初的初值指向第一个元素，指向第一个元素，8（R2）指向最）指向最后

16、一个元素。后一个元素。Loop：L.DF0,0(R1)/取一个向量元素放入取一个向量元素放入F0ADD.DF4,F0,F2/加上在加上在F2中的中的标量量S.DF4,0(R1)/存存结果果DADDIUR1,R1,#8/将指将指针减减8（每个数据占（每个数据占8个字个字节）BNER1,R2,Loop/若若R1不等于不等于R2，表示尚未，表示尚未结束，束，/转移到移到Loop继续执行行其中：其中：整数寄存器整数寄存器R1：指向向量中的当前元素。：指向向量中的当前元素。（初（初值为向量中最高端元素的地址）向量中最高端元素的地址）浮点寄存器浮点寄存器F2：用于保存常数：用于保存常数s。2 不进行指令调

17、度的情况下，程序的实际执行情况不进行指令调度的情况下，程序的实际执行情况Loop:L.DF0,0（R1）1（空（空转）2ADD.D F4,F0,F23（空（空转）4（空（空转）5S.DF4,0（R1）6DADDIUR1,R1，#87（空（空转）8BNER1,R2,Loop9（空（空转）10u每个元素的操作需要每个元素的操作需要10个个时钟周期，其中周期，其中5个是空个是空转周期。周期。2 指令调度以后，程序的执行情况指令调度以后，程序的执行情况Loop:L.DF0,0（R1）（空（空转）ADD.DF4,F0,F2（空（空转）（空（空转）S.DF4,0（R1）DADDIUR1,R1,#8（空（空

18、转）BNER1,R2,Loop（空（空转）Loop:L.DF0,0（R1）DADDIUR1,R1,#8ADD.DF4,F0,F2（空（空转）BNER1,R2,LoopS.DF4,8（R1）因因为修改指修改指针R1的减的减8操作操作提前了，所以提前了，所以S.D指令中指令中变址指址指针的偏移量要从的偏移量要从0改改为8.2 指令流出指令流出时钟Loop:L.DF0,0(R1)1DADDIUR1,R1,#-82ADD.DF4,F0,F2 3（空（空转）4BNER1,Loop5S.DF4，8(R1)6u一个元素的操作一个元素的操作时间从从10个个时钟周期周期减少到减少到6个个,其中其中5个周期是有指

19、令个周期是有指令执行行的，的，1个个为空空转周期周期。2 例子中的问题及解决方案例子中的问题及解决方案u只有只有L.D、ADD.D和和S.D这3条指令是有效条指令是有效操作，占用操作，占用3个个时钟周期。而周期。而DADDIU、空空转和和BEN这3个个时钟周期都是附加的循周期都是附加的循环控制开控制开销。有效操作比例不高。有效操作比例不高。u循循环展开技展开技术n把循把循环体的代体的代码复制多次并按复制多次并按顺序排列，序排列，然后相然后相应调整循整循环的的结束条件。束条件。2 u例例4.7将例将例4.6中的循中的循环展开展开3次得到次得到4个循个循环体，体，然后然后对展开后的指令序列在不展开

20、后的指令序列在不调度和度和调度两种度两种情况下，分析代情况下，分析代码的性能。的性能。u设R1的初的初值为32的倍数，即循的倍数，即循环次数次数为4的倍的倍数。因此不需要在循数。因此不需要在循环体后面增加体后面增加补偿代代码。u方法：消除冗余的指令，并且不重复使用寄存方法：消除冗余的指令，并且不重复使用寄存器。器。2 分配寄存器（不重复使用寄存器分配寄存器（不重复使用寄存器 ）uF0、F4：用于展开后的第：用于展开后的第1个循个循环体体uF2：用于保存常数：用于保存常数uF6、F8：用于展开后的第：用于展开后的第2个循个循环体体uF10、F12：用于展开后的第：用于展开后的第3个循个循环体体u

21、F14、F16：用于展开后的第：用于展开后的第4个循个循环体体2 展开后没有调度的代码展开后没有调度的代码 指令流出时钟指令流出时钟Loop:L.DF0,0(R1)1（空转）（空转）2ADD.D F4,F0,F23（空转）（空转）4（空转）（空转）5S.DF4,0（R1）6L.DF6,-8(R1)7（空转）（空转）8ADD.D F8,F6,F29（空转）（空转）10（空转）（空转）11S.DF8,-8（R1）12L.DF10,-16(R1)13（空转）（空转）14 指令流出时钟指令流出时钟ADD.D F12,F10,F215（空转）（空转）16（空转）（空转）17S.DF12,-16(R1)1

22、8L.DF14,-24(R1)19（空转）（空转）20ADD.D F16,F14,F221（空转）（空转）22（空转）（空转）23S.DF16,-24(R1)24DADDIUR1,R1,#-3225（空转）（空转）26BNER1,R2,Loop27（空转）（空转）282 结果分析结果分析u这个循个循环每遍共使用了每遍共使用了28个个时钟周期。周期。u有有4个循个循环体，完成体，完成4个元素的操作。个元素的操作。平均每个元素使用平均每个元素使用28/4=7个个时钟周期周期u原始循原始循环的每个元素需要的每个元素需要10个个时钟周期。周期。u节省的省的时间：从减少循：从减少循环控制的开控制的开销中

23、中获得的。得的。u在整个展开后的循在整个展开后的循环中，中，实际指令只有指令只有14条，其条，其他他14个周期都是空个周期都是空转。u结论：效率并不高：效率并不高2 对指令序列进行优化调度对指令序列进行优化调度 指令流出时钟指令流出时钟Loop:L.DF0,0(R1)1L.DF6,-8(R1)2L.DF10,-16(R1)3L.DF14,-24(R1)4ADD.DF4,F0,F25ADD.DF8,F6,F26ADD.DF12,F10,F27ADD.DF16,F14,F28S.DF4,0(R1)9S.DF8,-8(R1)10DADDIUR1,R1,#-3212S.DF12,16(R1)11BNE

24、R1,R2,Loop13S.DF16,8(R1)142 结果分析结果分析u没有数据相关引起的空没有数据相关引起的空转等待。等待。整个循整个循环仅仅使用了使用了14个个时钟周期。周期。平均每个元素的操作使用平均每个元素的操作使用14/4=3.5个个时钟周期。周期。u通通过循循环展开、寄存器重命名和指令展开、寄存器重命名和指令调度，可以度，可以有效地开有效地开发出指令出指令级并行。并行。2 循环展开和指令调度时要注意的问题循环展开和指令调度时要注意的问题u保保证正确性。正确性。在循在循环展开和展开和调度度过程中尤其要注意程中尤其要注意两个地方两个地方的正确性：的正确性：循循环控制，操作数偏移量的修

25、改。控制，操作数偏移量的修改。u注意有效性。注意有效性。只有能只有能够找到不同循找到不同循环体之体之间的无关性，才能的无关性，才能有效地使用循有效地使用循环展开。展开。u使用不同的寄存器。使用不同的寄存器。（否（否则可能可能导致新的冲突）致新的冲突）u删除多余的除多余的测试指令和分支指令，并指令和分支指令，并对循循环结束代束代码和新的循和新的循环体代体代码进行相行相应的修正。的修正。2 u注意注意对存存储器数据的相关性分析器数据的相关性分析例如例如对于于load指令和指令和store指令，如果它指令，如果它们在在不同的循不同的循环迭代中迭代中访问的存的存储器地址是不同器地址是不同的，它的，它们

26、就是相互独立的，可以相互就是相互独立的，可以相互对调。u注意新的相关性注意新的相关性由于原循由于原循环不同次的迭代在展开后都到了不同次的迭代在展开后都到了同一次循同一次循环体中，因此可能体中，因此可能带来新的相关性。来新的相关性。2 u静静态调度度n依靠依靠编译器器对代代码进行静行静态调度，以减少相关度，以减少相关和冲突。和冲突。n不是在程序不是在程序执行的行的过程中、而是在程中、而是在编译期期间进行代行代码调度和度和优化。化。n通通过把相关的指令拉开距离来减少可能把相关的指令拉开距离来减少可能产生的生的停停顿。u动态调度度n在程序的在程序的执行行过程中，依靠程中，依靠专门硬件硬件对代代码进行

27、行调度，减少数据相关度，减少数据相关导致的停致的停顿。4.2指令的动态调度指令的动态调度2 指令的动态调度的指令的动态调度的特点特点u能能够处理一些在理一些在编译时情况不明的相关（比如涉情况不明的相关（比如涉及到存及到存储器器访问的相关），并的相关），并简化了化了编译器。器。u能能够使本来是面向某一流水使本来是面向某一流水线优化化编译的代的代码在在其他的流水其他的流水线（动态调度）上也能高效地度）上也能高效地执行。行。u以硬件复以硬件复杂性的性的显著增加著增加为代价代价2 4.2.1动态调度的基本思想动态调度的基本思想u到目前到目前为止我止我们所使用流水所使用流水线的最大的的最大的局限局限性：

28、性：指令必指令必须按序流出和按序流出和执行行u考考虑下面一段代下面一段代码：DIV.DF4，F0，F2SUB.DF10，F4，F6ADD.DF12，F6，F14uSUB.D指令与指令与DIV.D指令关于指令关于F4相关，相关，导致致流水流水线停停顿。uADD.D指令与流水指令与流水线中的任何指令都没有中的任何指令都没有关系，但也因此受阻。关系，但也因此受阻。2 在前面的基本流水在前面的基本流水线中中译码功能段的工作功能段的工作ID检测检测结构结构冲突冲突检测检测数据数据冲突冲突一旦一条指令受阻，其后的指令都将停顿。一旦一条指令受阻，其后的指令都将停顿。解决办法：解决办法：允许乱序执行允许乱序执

29、行 2 u为了允了允许乱序乱序执行，将行，将5段流水段流水线的的译码阶段段再分再分为两个两个阶段：段：u流出流出（Issue，IS）：指令）：指令译码，检查是否存是否存在在结构冲突。构冲突。u读操作数操作数（ReadOperands，RO）：等待数）：等待数据冲突消失，然后据冲突消失，然后读操作数。操作数。ISRO检测检测结构结构冲突冲突检测检测数据数据冲突冲突2 u在前述在前述5段流水段流水线中，中，顺序序执行行时是不会是不会发生生WAR冲突和冲突和WAW冲突的。但乱序冲突的。但乱序执行有可能行有可能发生。生。u例：例：DIV.DF10,F0,F2SUB.DF10,F4,F6ADD.DF6,

30、F8,F14存在反相关存在反相关存在输出相关存在输出相关可以通过使用寄存器重命名技术来消除相关。可以通过使用寄存器重命名技术来消除相关。2 u动态调度的流水度的流水线支持多条指令同支持多条指令同时处于于执行当中。行当中。n要求：要求：具有多个功能部件、或者流水功能部件、或者具有多个功能部件、或者流水功能部件、或者兼而有之。兼而有之。n假假设具有具有多个功能部件。多个功能部件。u指令乱序完成指令乱序完成带来的来的最大最大问题：n异常异常处理比理比较复复杂n动态调度要保持正确的异常行度要保持正确的异常行为：只有那些在程序：只有那些在程序严格按程序格按程序顺序序执行行时会会发生的异常，才能真正生的异

31、常，才能真正发生。生。2 u保持正确的异常行保持正确的异常行为：对于一条会于一条会产生异常的生异常的指令来指令来说，只有当，只有当处理机确切地知道理机确切地知道该指令将指令将被被执行后，才允行后，才允许它它产生异常。生异常。u即使保持了正确的异常行即使保持了正确的异常行为，动态调度度处理机理机仍可能仍可能发生不精确异常。生不精确异常。2 精确异常与不精确异常精确异常与不精确异常u精确异常：精确异常：发生异常生异常时，处理机的理机的现场跟跟严格按格按程序程序顺序序执行行时指令指令i的的现场相同。相同。u不精确异常：不精确异常：当当执行指令行指令i i导致致发生异常生异常时，处理机的理机的现场（状

32、（状态）与）与严格按程序格按程序顺序序执行行时指指令令i i的的现场不同。不同。u发生不精确异常的生不精确异常的原因：原因：n当当发生异常（生异常（设为指令指令i）时，流水，流水线可能已可能已经执行完行完按程序按程序顺序是位于指令序是位于指令i i之后的指令；之后的指令；n流水流水线可能可能还没完成按程序没完成按程序顺序是指令序是指令i i之前的指令。之前的指令。u不精确异常使得在异常不精确异常使得在异常处理后理后难以接着以接着继续执行行程序。程序。2 4.2.2Tomasulo算法算法u核心思想核心思想n记录和和检测指令相关，操作数一旦就指令相关，操作数一旦就绪就立即就立即执行，把行，把发生

33、生RAW冲突冲突的可能性减少到最小；的可能性减少到最小；n通通过寄存器寄存器换名来消除名来消除WAR冲突冲突和和WAW冲突冲突。u。u原因：原因：2 IBM360/91首先采用了首先采用了Tomasulo算法算法u（1）IBM360/91的的设计目目标是基于整个是基于整个360系系列的列的统一指令集和一指令集和编译器来器来实现高性能，而不高性能，而不是是设计和利用和利用专用的用的编译器来提高性能，因此器来提高性能，因此需要更多地依需要更多地依赖硬件。硬件。uIBM360体系体系结构只有构只有4个双精度浮点寄存器，个双精度浮点寄存器，限制了限制了编译器器调度的有效性。度的有效性。u360/91的

34、的访存存时间和浮点和浮点计算算时间都很都很长。（也是（也是Tomasulo算法要解决的算法要解决的问题）u寄存器寄存器换名名可以消除可以消除WAR冲突和冲突和WAW冲突。冲突。2 n考考虑以下代以下代码：DIV.DF0，F2，F4ADD.DF6，F0，F8S.DF6，0（R1）SUB.DF8，F10，F14MUL.DF6，F10，F8输出相关（输出相关（F6）导致导致WAW冲突冲突反相关（反相关（F8）导致导致WAR冲突冲突 2 u消除名相关消除名相关n引入两个引入两个临时寄存器寄存器S和和Tn把把这段代段代码改写改写为：DIV.DF0，F2，F4ADD.DS，F0，F8S.DS，0（R1）S

35、UB.DT，F10，F14MUL.DF6，F10，T两个两个F6都换名为都换名为S两个两个F8都都换名为换名为T 2 基于基于Tomasulo算法的算法的MIPS处理器浮点部件的基本结构处理器浮点部件的基本结构2 保留站（保留站（reservationstation）u每个保留站中保存一条已每个保留站中保存一条已经流出并等待到本功能部件流出并等待到本功能部件执行的指令（相关信息）。行的指令（相关信息）。包括：操作包括：操作码、操作数以及用于、操作数以及用于检测和解决冲突的信和解决冲突的信息。息。u在一条指令流出到保留站的在一条指令流出到保留站的时候，如果候，如果该指令的源操指令的源操作数已作数

36、已经在寄存器中就在寄存器中就绪，则将之取到将之取到该保留站中。保留站中。u如果操作数如果操作数还没有没有计算出来，算出来，则在在该保留站中保留站中记录将将产生生这个操作数的保留站的个操作数的保留站的标识。u浮点加法器有浮点加法器有三三个保留站：个保留站：ADD1，ADD2，ADD3u浮点乘法器有浮点乘法器有两两个保留站：个保留站：MULT1，MULT2u每个保留站都有一个每个保留站都有一个标识字段字段，唯一地，唯一地标识了了该保留保留站。站。2 公共数据总线公共数据总线CDBuCDB是是一条重要的数据通路一条重要的数据通路n所有功能部件的所有功能部件的计算算结果都是送到果都是送到CDB上，由它

37、把上，由它把这些些结果直接送到（播送到）各个需要果直接送到（播送到）各个需要该结果的地果的地方。方。n在具有多个在具有多个执行部件且采用多流出（即每个行部件且采用多流出（即每个时钟周周期流出多条指令）的流水期流出多条指令）的流水线中，需要采用多条中，需要采用多条CDB。2 load缓冲器和缓冲器和store缓冲器缓冲器u用于存放用于存放读/写存写存储器的数据或地址器的数据或地址uload缓冲器冲器的作用：的作用：n存放用于存放用于计算有效地址的分量；算有效地址的分量；n记录正在正在进行的行的load访存，等待存存，等待存储器的响器的响应；n保存已保存已经完成了的完成了的load的的结果（即从存

38、果（即从存储器取来的器取来的数据），等待数据），等待CDB传输。ustore缓冲器冲器的作用：的作用：n存放用于存放用于计算有效地址的分量；算有效地址的分量；n保存正在保存正在进行的行的store访存的目存的目标地址，地址，该store正在正在等待存等待存储数据的到达；数据的到达；n保存保存该store的地址和数据，直到存的地址和数据，直到存储部件接收。部件接收。2 u浮点寄存器浮点寄存器FPn共有共有16个浮点寄存器：个浮点寄存器：F0，F2，F4，F30。n它它们通通过一一对总线连接到功能部件，并通接到功能部件，并通过CDB连接到接到store缓冲器。冲器。u指令指令队列列n指令部件送来的

39、指令放入指令指令部件送来的指令放入指令队列列n指令指令队列中的指令按先列中的指令按先进先出的先出的顺序流出序流出u运算部件运算部件n浮点加法器完成加法和减法操作浮点加法器完成加法和减法操作n浮点乘法器完成乘法和除法操作浮点乘法器完成乘法和除法操作2 u在在Tomasulo算法中，寄存器算法中，寄存器换名是通名是通过保留站保留站和流出和流出逻辑来共同完成的。来共同完成的。n当指令流出当指令流出时，如果其操作数，如果其操作数还没有没有计算出来，算出来，则将将该指令中相指令中相应的寄存器号的寄存器号换名名为将将产生生这个个操作数的保留站的操作数的保留站的标识。n指令流出到保留站后，其操作数寄存器号或

40、者指令流出到保留站后，其操作数寄存器号或者换成了数据本身（如果成了数据本身（如果该数据已数据已经就就绪），或者），或者换成了保留站的成了保留站的标识，不再与寄存器有关系。，不再与寄存器有关系。2 Tomasulo算法的特点算法的特点u冲突冲突检测和指令和指令执行控制是分布的。行控制是分布的。u每个功能部件的保留站中的信息决定了什么每个功能部件的保留站中的信息决定了什么时候候指令可以在指令可以在该功能部件开始功能部件开始执行。行。u计算算结果通果通过CDB直接从直接从产生它的保留站生它的保留站传送到送到所有需要它的功能部件，而不用所有需要它的功能部件，而不用经过寄存器。寄存器。2 指令执行的步骤

41、指令执行的步骤u使用使用Tomasulo算法的流水算法的流水线需需3段段：u流出流出：从指令：从指令队列的列的头部取一条指令。部取一条指令。n如果如果该指令的操作所要求的保留站有空指令的操作所要求的保留站有空闲的，就把的，就把该指令送到指令送到该保留站（保留站（设为r）。）。n如果其操作数在寄存器中已如果其操作数在寄存器中已经就就绪，就将，就将这些操作数些操作数送入保留站送入保留站r。n如果其操作数如果其操作数还没有就没有就绪，就把将，就把将产生生该操作数的保操作数的保留站的留站的标识送入保留站送入保留站r。n一旦被一旦被记录的保留站完成的保留站完成计算，它将直接把数据送算，它将直接把数据送给

42、保留站保留站r。（寄存器。（寄存器换名和名和对操作数操作数进行行缓冲，消除冲，消除WAR冲突）冲突）n完成完成对目目标寄存器的寄存器的预约工作工作（消除了（消除了WAW冲突）冲突）n如果没有空如果没有空闲的保留站，指令就不能流出。的保留站，指令就不能流出。（发生了生了结构冲突）构冲突）2 u执行行n当两个操作数都就当两个操作数都就绪后，本保留站就用相后，本保留站就用相应的功的功能部件开始能部件开始执行指令行指令规定的操作。定的操作。nload和和store指令的指令的执行需要两个步行需要两个步骤：n计算有效地址（要等到基地址寄存器就算有效地址（要等到基地址寄存器就绪）n把有效地址放入把有效地址

43、放入load或或store缓冲器冲器u写写结果果n功能部件功能部件计算完算完毕后，就将后，就将计算算结果放到果放到CDB上，上，所有等待所有等待该计算算结果的寄存器和保留站（包括果的寄存器和保留站（包括store缓冲器）都同冲器）都同时从从CDB上上获得所需要的数据。得所需要的数据。2 u每个保留站有以下每个保留站有以下6个字段：个字段：nOp：要：要对源操作数源操作数进行的操作。行的操作。nQj，Qk：将：将产生源操作数的保留站号。生源操作数的保留站号。n等于等于0表示操作数已表示操作数已经就就绪且在且在Vj或或Vk中，中，或者不需要操作数。或者不需要操作数。nVj，Vk：源操作数的：源操作

44、数的值。n对于每一个操作数来于每一个操作数来说，V或或Q字段只有一字段只有一个有效。个有效。n对于于load来来说，Vk字段用于保存偏移量。字段用于保存偏移量。nBusy：为“yes”表示本保留站或表示本保留站或缓冲冲单元元“忙忙”。nA：仅load和和store缓冲器有冲器有该字段。开始是存放字段。开始是存放指令中的立即数字段，地址指令中的立即数字段，地址计算后存放有效地址。算后存放有效地址。2 uQi：寄存器状寄存器状态表。表。n每个寄存器在每个寄存器在该表中有表中有对应的一的一项，用于存放将，用于存放将把把结果写入果写入该寄存器的保留站的站号。寄存器的保留站的站号。n为0表示当前没有正在

45、表示当前没有正在执行的指令要写入行的指令要写入该寄存寄存器，也即器，也即该寄存器中的内容就寄存器中的内容就绪。2 u设有指令：有指令：MULF0,F2,F4ADDF2,F0,F62 2 2 2 例例4.1对于下述指令序列，于下述指令序列，给出当第一条指令完成出当第一条指令完成并写入并写入结果果时，Tomasulo算法所用的各信息表算法所用的各信息表中的内容。中的内容。L.D F6，34（R2）L.D F2，45（R3）MUL.DF0，F2，F4SUB.DF8，F2，F6DIV.DF10，F0，F6ADD.DF6，F8，F22 当采用当采用Tomasulo算法时，在上述给定的时刻，保算法时，在上

46、述给定的时刻，保留站、留站、load缓冲器以及寄存器状态表中的内容缓冲器以及寄存器状态表中的内容。指指 令令 指令状态表指令状态表 流出流出 执行执行 写结果写结果 L.D F6,34(R2)L.D F2,45(R3)MUL.DF0,F2,F4SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2 2 VkMem34+RegsR2RegF4Mem34+RegsR2 名称名称 保留站保留站 Load1Load2Add1Add2Add3Mult1Mult2BusynoyesyesyesnoyesyesOpLDSUBADDMULDIVVj Qj Load2Add1Load2

47、Mult1Qk Load2A45+RegsR3 寄存器状态表寄存器状态表 F0F2F4F6F8F10F30QiMult1Load2Add2Add1Mult2 2 Tomasulo算法的主要优点：算法的主要优点：u冲突冲突检测逻辑是分布的是分布的（通（通过保留站和保留站和CDB实现）n如果有多条指令已如果有多条指令已经获得了一个操作数，得了一个操作数，并同并同时在等待同一运算在等待同一运算结果，那么果，那么这个个结果一果一产生，就可以通生，就可以通过CDB同同时播送播送给所所有有这些指令，使它些指令，使它们可以同可以同时执行。行。n消除了消除了WAW冲突和冲突和WAR冲突冲突导致的停致的停顿n使

48、用保留站使用保留站进行寄存器行寄存器换名，并且操作数名，并且操作数一旦就一旦就绪就将之放入保留站。就将之放入保留站。2 4.4多指令流出技术多指令流出技术u如果每次只能流出一条指令（如果每次只能流出一条指令（单流出），流出），则CPI不可能小于不可能小于1。u要想要想进一步提高性能，使一步提高性能，使CPI1，就必，就必须采用采用多流出技多流出技术。2 单流出和多流出处理机执行指令的时空图单流出和多流出处理机执行指令的时空图2 提高流水并行处理的方法提高流水并行处理的方法u增加流水部件套数增加流水部件套数 超超标量量u合并多条指令操作合并多条指令操作码 超超长指令字指令字u细化流水部件段数化流

49、水部件段数 超流水超流水2 4.4.1超标量方法（超标量方法（Superscalar）u在在处理机内理机内设置多个可并行操作的功能部置多个可并行操作的功能部件和多条流水件和多条流水线，在一个，在一个时钟周期内启周期内启动（发射）多条指令射）多条指令进行并行行并行处理，使得理，使得CPI1。u超超标量方法是量方法是采用采用资源重复源重复的策略开的策略开发并并行性。行性。u超超级标量机主要是借助量机主要是借助对硬件硬件资源重复来源重复来实现空空间的并行操作。的并行操作。2 u采用超采用超标量技量技术时在每个在每个时钟周期流出周期流出的指令条数的指令条数不固定不固定，依代，依代码的具体情况而的具体情

50、况而定（有上限）。定（有上限）。u设这个上限个上限为n，就称，就称该处理机理机为n流出。流出。u可以通可以通过编译器器进行指令的静行指令的静态调度，度，也可以基于也可以基于Tomasulo算法算法进行行动态调度，度，以以实现超超标量技量技术。2 理想的理想的RISC机中指令流水的执行情况机中指令流水的执行情况理想的理想的RISC机机取指取指译码译码 执行执行 写回写回0123456T72 在超标量机中每个时钟周期可同时启动在超标量机中每个时钟周期可同时启动三条指令的情况三条指令的情况0123456T取指取指译码译码 执行执行 写回写回每拍启动每拍启动3 3条指令条指令要求并行度要求并行度=3=