第4章 指令级并行

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

2、度地挖掘出程序中存在的指令级并行。指令级并行。2021-7-1741. 流水线处理机的实际流水线处理机的实际CPIu流水线处理机的实际流水线处理机的实际CPI就是理想流水线就是理想流水线的的CPI加上各类停顿的时钟周期数：加上各类停顿的时钟周期数： CPI流水线流水线 = CPI理想理想 + 停顿停顿结构冲突结构冲突 + 停顿停顿数据冲突数据冲突+ 停顿停顿控制冲突控制冲突 uCPI理想理想即理想即理想CPI，是衡量流水线最高性，是衡量流水线最高性能的指标之一。能的指标之一。2021-7-175IPC（Instructions Per Cycle ）uIPC：每个时钟周期内完成的指令条数。：每

3、个时钟周期内完成的指令条数。uIPC是是CPI的倒数。的倒数。u提高提高IPC的途径之一是减少的途径之一是减少CPI流水线流水线 。2021-7-1762. 基本程序块基本程序块u基本程序块基本程序块：一段除了入口和出口以外不：一段除了入口和出口以外不包含其他分支的一个线性代码段。包含其他分支的一个线性代码段。u因为程序往往平均每因为程序往往平均每57条指令就会有一条指令就会有一个分支，而且指令之间还可能存在相关，个分支，而且指令之间还可能存在相关，所以在基本程序块中能开发的并行性是很所以在基本程序块中能开发的并行性是很有限的，很可能比基本块的大小要小很多。有限的，很可能比基本块的大小要小很多

4、。u为了明显地提高性能，必须跨越多个基本为了明显地提高性能，必须跨越多个基本块开发指令的并行性。块开发指令的并行性。2021-7-1773. 开发指令级并行常用的方法开发指令级并行常用的方法u（1）开发循环级并行）开发循环级并行u循环级并行（循环级并行（Looplevel parallelism）：循环程序不同迭代之间存在的并行性。循环程序不同迭代之间存在的并行性。u例：例：for （i=1； i500； i=i1） ai=ais；n在每一次循环的内部，没有任何的并行性。在每一次循环的内部，没有任何的并行性。n每一次循环都可以与其他的循环重叠并行执每一次循环都可以与其他的循环重叠并行执行。行。

5、u开发循环级并行性是增加指令之间并行性的最开发循环级并行性是增加指令之间并行性的最简单和最常用的方法。简单和最常用的方法。2021-7-178开发循环级并行的基本技术开发循环级并行的基本技术u采用循环展开技术采用循环展开技术u采用向量指令和向量数据表示采用向量指令和向量数据表示2021-7-179（2 2）解决相关与流水线冲突问题）解决相关与流水线冲突问题u相关相关是程序固有的一种属性，它反映了程序中是程序固有的一种属性，它反映了程序中指令之间的相互依赖关系。指令之间的相互依赖关系。u相关的三种类型：数据相关、名相关、控制相相关的三种类型：数据相关、名相关、控制相关。关。u如果两条指令相关，它

6、们就不能并行执行，或如果两条指令相关，它们就不能并行执行，或只能部分重叠执行。只能部分重叠执行。u由于相关的存在，使得指令流中的下一条指令由于相关的存在，使得指令流中的下一条指令不能在指定时钟周期执行，就是发生了不能在指定时钟周期执行，就是发生了流水线流水线冲突冲突。u相关的存在限制了指令级并行（相关的存在限制了指令级并行（ILP）的开发。）的开发。2021-7-1710u流水线冲突的三种类型：结构冲突、数据冲突、流水线冲突的三种类型：结构冲突、数据冲突、控制冲突。控制冲突。n结构冲突：由硬件资源冲突造成。结构冲突：由硬件资源冲突造成。n数据冲突：由数据相关和名相关造成。数据冲突：由数据相关和

7、名相关造成。n控制冲突：由控制相关造成。控制冲突：由控制相关造成。u具体的一次相关是否会导致具体的一次相关是否会导致实际冲突实际冲突的发生以的发生以及该冲突会带来多长的停顿，根据流水线的属及该冲突会带来多长的停顿，根据流水线的属性而定。性而定。2021-7-1711解决相关与冲突的方法解决相关与冲突的方法u 保持相关，但保持相关，但避免发生冲突避免发生冲突。n方法：指令调度，包括静态调度和动态调度。方法：指令调度，包括静态调度和动态调度。u通过代码变换，消除相关。通过代码变换，消除相关。2021-7-1712解决相关与冲突时需注意的问题解决相关与冲突时需注意的问题u由于相关的存在，在开发指令级

8、并行时，如果由于相关的存在，在开发指令级并行时，如果可能影响到程序的正确性，就必须可能影响到程序的正确性，就必须注意保持程注意保持程序顺序。序顺序。n程序顺序程序顺序：由源程序确定的在完全串行方式：由源程序确定的在完全串行方式下指令的执行顺序。下指令的执行顺序。u控制相关并不是一个必须严格保持的关键属性。控制相关并不是一个必须严格保持的关键属性。n当存在控制相关时，在对程序的正确性没有当存在控制相关时，在对程序的正确性没有影响的前提下，可以不遵守控制相关的依赖影响的前提下，可以不遵守控制相关的依赖关系，执行本来不该执行的指令。关系，执行本来不该执行的指令。2021-7-1713必须保持的最关键

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

10、的数据相关和控制相关，就能保持程序的数据流和异常行为。就能保持程序的数据流和异常行为。2021-7-1714u例：例： DADDU R2，R3，R4 BEQZ R2，L1 LW R1，0（R2）L1 ：u如果不保持关于如果不保持关于R2的数据相关，程序的执行结果的数据相关，程序的执行结果就会改变。就会改变。u如果不保持控制相关，把如果不保持控制相关，把LW指令移到指令移到BEQZ之前，之前，就有可能产生一个新的就有可能产生一个新的“访存保护访存保护”异常（如果异常（如果R20）。）。2021-7-1715u数据流数据流：指数据值从其产生者指令到其消费者：指数据值从其产生者指令到其消费者指令的实

11、际流动。指令的实际流动。n分支指令使得数据流具有分支指令使得数据流具有动态性动态性，因为它使，因为它使得给定指令的数据可以有多个来源。得给定指令的数据可以有多个来源。n仅仅保持数据相关性是不够的仅仅保持数据相关性是不够的，一条指令可，一条指令可能与多条先前的指令数据相关，程序顺序决能与多条先前的指令数据相关，程序顺序决定了哪条指令真正是所需数据的产生者。定了哪条指令真正是所需数据的产生者。u只有再加上保持控制顺序，才能够保持程序顺只有再加上保持控制顺序，才能够保持程序顺序。序。2021-7-1716u例：例： DADDU R1，R2，R3 BEQZ R4，L1 DSUBU R1，R5，R6L1

12、 ： OR R7，R1，R8uOR指令中使用的指令中使用的R1值取决于值取决于BEQZ指令分支的指令分支的是否成功。即是否成功。即OR与与DADDU或或DSUBU指令相关。指令相关。u必须通过保持控制相关，避免对数据流的修改，必须通过保持控制相关，避免对数据流的修改，以保证数据流的正确。以保证数据流的正确。uDSUBU不能被移到不能被移到BEQZ之前。之前。2021-7-1717u有时，不遵守控制相关既不影响异常行为，有时，不遵守控制相关既不影响异常行为，也不改变数据流。在这种情况下，可以大胆也不改变数据流。在这种情况下，可以大胆地进行指令调度，把失败分支中的指令调度地进行指令调度，把失败分支

13、中的指令调度到分支指令之前。到分支指令之前。 2021-7-1718u例：例：DADDU R1，R2，R3BEQZR12，SkipnextDSUBUR4，R5，R6DADDUR5，R4，R9Skipnext： OR R7，R8，R9u如果已知如果已知R4在在Skipnext后不再被使用，而且后不再被使用，而且DSUBU指令不会产生异常，那么就可以把指令不会产生异常，那么就可以把DSUBU指令移到指令移到BEQZ之前。之前。u因为这个移动不会改变数据流。因为这个移动不会改变数据流。2021-7-1719开发指令的并行性的方法开发指令的并行性的方法u硬件方法：指令的动态调度、动态分支预测、硬件方法

14、：指令的动态调度、动态分支预测、多指令流出技术。多指令流出技术。u软件方法：指令的静态调度、循环展开技术。软件方法：指令的静态调度、循环展开技术。u软硬件结合方法：显式并行指令计算软硬件结合方法：显式并行指令计算EPIC。2021-7-17204.5 循环展开和指令调度循环展开和指令调度u4.5.1 循环展开和指令调度的基本方法循环展开和指令调度的基本方法u为了充分发挥流水线的作用，必须设法让它满为了充分发挥流水线的作用，必须设法让它满负荷工作。因此要充分开发指令之间存在的并负荷工作。因此要充分开发指令之间存在的并行性，找出不相关的指令序列，让它们在流水行性，找出不相关的指令序列，让它们在流水

15、线上重叠并行执行。线上重叠并行执行。u增加指令间并行性最简单和最常用的方法增加指令间并行性最简单和最常用的方法n开发循环级并行性开发循环级并行性循环的不同迭代之间存循环的不同迭代之间存在的并行性。在的并行性。n在把循环展开后，通过重命名和指令调度来在把循环展开后，通过重命名和指令调度来开发更多的并行性。开发更多的并行性。2021-7-1721编译器指令调度能力的限制编译器指令调度能力的限制u编译器完成指令调度的能力受限于两个特性：编译器完成指令调度的能力受限于两个特性：n程序固有的指令级并行性；程序固有的指令级并行性；n流水线功能部件的执行延迟。流水线功能部件的执行延迟。2021-7-1722

16、浮点流水线延迟浮点流水线延迟uLoad指令的结果可以通过定向路径及时送给指令的结果可以通过定向路径及时送给store指指令，所以延迟为令，所以延迟为0，不用插入停顿。，不用插入停顿。产生结果的指令产生结果的指令 使用结果的指令使用结果的指令 延迟（时钟周期数）延迟（时钟周期数） 浮点计算浮点计算 另一个浮点计算另一个浮点计算 3 浮点计算浮点计算 浮点浮点store（S.D） 2 浮点浮点load（L.D） 浮点计算浮点计算 1 浮点浮点load（L.D） 浮点浮点store（S.D） 0 2021-7-1723u例例4.6 对于下面的源代码，转换成对于下面的源代码，转换成MIPS汇编语言，汇

17、编语言，在不进行指令调度和进行指令调度两种情况下，在不进行指令调度和进行指令调度两种情况下，分析其代码一次循环所需的执行时间。分析其代码一次循环所需的执行时间。nfor (i=1； i=1000； i+)nxi = xi + s；u解：解：u该循环的不同迭代之间不存在相关，所以多次迭该循环的不同迭代之间不存在相关，所以多次迭代可以并行执行。代可以并行执行。2021-7-1724uMIPS汇编语言代码：汇编语言代码：u假设假设R1的初值指向第一个元素，的初值指向第一个元素，8（R2）指向最）指向最后一个元素。后一个元素。Loop：L.D F0,0(R1) /取一个向量元素放入取一个向量元素放入F

18、0 ADD.D F4,F0,F2 /加上在加上在F2中的标量中的标量 S.D F4, 0(R1) /存结果存结果 DADDIU R1,R1, #8 /将指针减将指针减8（每个数据占（每个数据占8个字节）个字节）BNE R1,R2,Loop /若若R1不等于不等于R2，表示尚未结束，表示尚未结束， /转移到转移到Loop继续执行继续执行其中：其中： 整数寄存器整数寄存器R1：指向向量中的当前元素。：指向向量中的当前元素。 （初值为向量中最高端元素的地址）（初值为向量中最高端元素的地址） 浮点寄存器浮点寄存器F2：用于保存常数：用于保存常数s。2021-7-1725不进行指令调度的情况下，程序的实

19、际执行情况不进行指令调度的情况下，程序的实际执行情况Loop: L.D F0,0（R1） 1 （空转）（空转） 2 ADD.D F4,F0,F2 3 （空转）（空转） 4 （空转）（空转） 5 S.D F4, 0（R1） 6 DADDIU R1,R1，#8 7 （空转）（空转） 8 BNE R1,R2,Loop 9 （空转）（空转） 10u每个元素的操作需要每个元素的操作需要10个时钟周期，其中个时钟周期，其中5个是空个是空转周期。转周期。2021-7-1726指令调度以后，程序的执行情况指令调度以后，程序的执行情况Loop: L.D F0,0（R1） （空转）（空转） ADD.D F4,F0

20、,F2 （空转）（空转） （空转）（空转） S.D F4, 0（R1） DADDIU R1,R1,#8 （空转）（空转） BNE R1,R2,Loop （空转）（空转）Loop: L.D F0,0（R1） DADDIU R1,R1,#8 ADD.D F4,F0,F2 （空转）（空转） BNE R1,R2,Loop S.D F4, 8（R1） 因为修改指针因为修改指针R1的减的减8操作操作提前了，所以提前了，所以S.D指令中变指令中变址指针的偏移量要从址指针的偏移量要从0改为改为8.2021-7-1727 指令流出时钟指令流出时钟Loop: L.D F0, 0(R1) 1 DADDIU R1,

21、R1, #-8 2 ADD.D F4, F0, F2 3 （空转）（空转） 4 BNE R1, Loop 5 S.D F4，8(R1) 6u一个元素的操作时间从一个元素的操作时间从10个时钟周期个时钟周期减少到减少到6个个,其中其中5个周期是有指令执行个周期是有指令执行的，的，1个为空转周个为空转周期期。2021-7-1728例子中的问题及解决方案例子中的问题及解决方案u只有只有L.D、ADD.D和和S.D这这3条指令是有效条指令是有效操作，占用操作，占用3个时钟周期。而个时钟周期。而DADDIU、空转空转和和BEN这这3个时钟周期都是附加的循个时钟周期都是附加的循环控制开销。有效操作比例不高

22、。环控制开销。有效操作比例不高。u循环展开技术循环展开技术n把循环体的代码复制多次并按顺序排把循环体的代码复制多次并按顺序排列，然后相应调整循环的结束条件。列，然后相应调整循环的结束条件。2021-7-1729u例例4.7 将例将例4.6中的循环展开中的循环展开3次得到次得到4个循环体，个循环体，然后对展开后的指令序列在不调度和调度两种然后对展开后的指令序列在不调度和调度两种情况下，分析代码的性能。情况下，分析代码的性能。u设设R1的初值为的初值为32的倍数，即循环次数为的倍数，即循环次数为4的倍的倍数。因此不需要在循环体后面增加补偿代码。数。因此不需要在循环体后面增加补偿代码。u方法：消除冗

23、余的指令，并且不重复使用寄存方法：消除冗余的指令，并且不重复使用寄存器。器。2021-7-1730分配寄存器（不重复使用寄存器分配寄存器（不重复使用寄存器 ）uF0、F4：用于展开后的第：用于展开后的第1个循环体个循环体uF2：用于保存常数：用于保存常数uF6、F8：用于展开后的第：用于展开后的第2个循环体个循环体uF10、F12：用于展开后的第：用于展开后的第3个循环体个循环体uF14、F16：用于展开后的第：用于展开后的第4个循环体个循环体2021-7-1731展开后没有调度的代码展开后没有调度的代码 指令流出时钟指令流出时钟Loop:L.DF0,0(R1)1（空转）（空转）2ADD.D

24、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)18L.DF14,-24(R1)19（空转）（空转）20ADD.D F16,F14,F221（空转）（空转）22（空转）（空转）23S.DF16,-24(R1)24DADDIUR1,R1,#-3

25、225（空转）（空转）26BNER1,R2,Loop27（空转）（空转）282021-7-1732结果分析结果分析u这个循环每遍共使用了这个循环每遍共使用了28个时钟周期。个时钟周期。u有有4个循环体，完成个循环体，完成4个元素的操作。个元素的操作。平均每个元素使用平均每个元素使用28/4=7个时钟周期个时钟周期u原始循环的每个元素需要原始循环的每个元素需要10个时钟周期。个时钟周期。u节省的时间：从减少循环控制的开销中获得的。节省的时间：从减少循环控制的开销中获得的。u在整个展开后的循环中，实际指令只有在整个展开后的循环中，实际指令只有14条，其条，其他他14个周期都是空转。个周期都是空转。

26、u结论：效率并不高结论：效率并不高2021-7-1733对指令序列进行优化调度对指令序列进行优化调度 指令流出时钟指令流出时钟Loop: L.DF0,0(R1) 1L.DF6,-8(R1) 2L.DF10,-16(R1) 3L.DF14,-24(R1) 4ADD.DF4,F0,F2 5ADD.DF8,F6,F2 6ADD.DF12,F10,F2 7ADD.DF16,F14,F2 8S.DF4,0(R1) 9S.DF8,-8(R1) 10DADDIUR1,R1,#-32 12S.DF12,16(R1) 11BNER1,R2,Loop 13S.DF16,8(R1) 142021-7-1734结果分

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

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

29、储器地址是不同不同的循环迭代中访问的存储器地址是不同的，它们就是相互独立的，可以相互对调。的，它们就是相互独立的，可以相互对调。u注意新的相关性注意新的相关性 由于原循环不同次的迭代在展开后都到了由于原循环不同次的迭代在展开后都到了同一次循环体中，因此可能带来新的相关性。同一次循环体中，因此可能带来新的相关性。 2021-7-1737u静态调度静态调度n依靠编译器对代码进行静态调度，以减少相关依靠编译器对代码进行静态调度，以减少相关和冲突。和冲突。n不是在程序执行的过程中、而是在编译期间进不是在程序执行的过程中、而是在编译期间进行代码调度和优化。行代码调度和优化。n通过把相关的指令拉开距离来减

30、少可能产生的通过把相关的指令拉开距离来减少可能产生的停顿。停顿。u动态调度动态调度n在程序的执行过程中，依靠专门硬件对代码进在程序的执行过程中，依靠专门硬件对代码进行调度，减少数据相关导致的停顿。行调度，减少数据相关导致的停顿。4.2 指令的动态调度指令的动态调度2021-7-1738指令的动态调度的指令的动态调度的特点特点u能够处理一些在编译时情况不明的相关（比如涉能够处理一些在编译时情况不明的相关（比如涉及到存储器访问的相关），并简化了编译器。及到存储器访问的相关），并简化了编译器。u能够使本来是面向某一流水线优化编译的代码在能够使本来是面向某一流水线优化编译的代码在其他的流水线（动态调度

31、）上也能高效地执行。其他的流水线（动态调度）上也能高效地执行。u以硬件复杂性的显著增加为代价以硬件复杂性的显著增加为代价2021-7-17394.2.1 动态调度的基本思想动态调度的基本思想u到目前为止我们所使用流水线的最大的到目前为止我们所使用流水线的最大的局局限性：限性：指令必须按序流出和执行指令必须按序流出和执行u考虑下面一段代码：考虑下面一段代码：DIV.D F4，F0，F2SUB.D F10，F4，F6 ADD.D F12，F6，F14uSUB.D指令与指令与DIV.D指令关于指令关于F4相关，导致相关，导致流水线停顿。流水线停顿。uADD.D指令与流水线中的任何指令都没有指令与流水

32、线中的任何指令都没有关系，但也因此受阻。关系，但也因此受阻。2021-7-1740在前面的基本流水线中译码功能段的工作在前面的基本流水线中译码功能段的工作ID检测检测结构结构冲突冲突检测检测数据数据冲突冲突一旦一条指令受阻，其后的指令都将停顿。一旦一条指令受阻，其后的指令都将停顿。解决办法：解决办法：允许乱序执行允许乱序执行 2021-7-1741u为了允许乱序执行，将为了允许乱序执行，将5段流水线的译码阶段段流水线的译码阶段再分为两个阶段：再分为两个阶段：u流出流出（Issue，IS）：指令译码，检查是否存在）：指令译码，检查是否存在结构冲突。结构冲突。 u读操作数读操作数（Read Ope

33、rands，RO）：等待数据）：等待数据冲突消失，然后读操作数。冲突消失，然后读操作数。ISRO检测检测结构结构冲突冲突检测检测数据数据冲突冲突2021-7-1742u在前述在前述5段流水线中，顺序执行时是不会发生段流水线中，顺序执行时是不会发生WAR冲突和冲突和WAW冲突的。但乱序执行有可能冲突的。但乱序执行有可能发生。发生。u例：例： DIV.D F10, F0, F2 SUB.D F10, F4, F6 ADD.D F6, F8, F14存在反相关存在反相关存在输出相关存在输出相关可以通过使用寄存器重命名技术来消除相关。可以通过使用寄存器重命名技术来消除相关。 2021-7-1743u动

34、态调度的流水线支持多条指令同时处于执行当动态调度的流水线支持多条指令同时处于执行当中。中。n要求：要求：具有多个功能部件、或者流水功能部件、或者具有多个功能部件、或者流水功能部件、或者兼而有之。兼而有之。n假设具有假设具有多个功能部件。多个功能部件。u指令乱序完成带来的指令乱序完成带来的最大问题：最大问题：n异常处理比较复杂异常处理比较复杂n动态调度要保持正确的异常行为：只有那些在程序严动态调度要保持正确的异常行为：只有那些在程序严格按程序顺序执行时会发生的异常，才能真正发生。格按程序顺序执行时会发生的异常，才能真正发生。2021-7-1744u保持正确的异常行为：保持正确的异常行为：对于一条

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

36、现场（状态）与严格按程序顺序执行时指理机的现场（状态）与严格按程序顺序执行时指令令i i的现场不同。的现场不同。u发生不精确异常的发生不精确异常的原因：原因：n当发生异常（设为指令当发生异常（设为指令i）时，流水线可能已经执行完）时，流水线可能已经执行完按程序顺序是位于指令按程序顺序是位于指令i i之后的指令；之后的指令；n流水线可能还没完成按程序顺序是指令流水线可能还没完成按程序顺序是指令i i之前的指令。之前的指令。 u不精确异常使得在异常处理后难以接着继续执行不精确异常使得在异常处理后难以接着继续执行程序。程序。2021-7-17464.2.2 Tomasulo算法算法u核心思想核心思想

37、n记录和检测指令相关，操作数一旦就绪就立即执记录和检测指令相关，操作数一旦就绪就立即执行，把发生行，把发生RAW冲突冲突的可能性减少到最小；的可能性减少到最小；n通过寄存器换名来消除通过寄存器换名来消除WAR冲突冲突和和WAW冲突冲突。u。u原因：原因： 2021-7-1747IBM 360/91首先采用了首先采用了Tomasulo算法算法u（1）IBM 360/91的设计目标是基于整个的设计目标是基于整个360系列的统一指令集和编译器来实现高性能，系列的统一指令集和编译器来实现高性能，而不是设计和利用专用的编译器来提高性能，而不是设计和利用专用的编译器来提高性能，因此需要更多地依赖硬件。因此

38、需要更多地依赖硬件。uIBM 360体系结构只有体系结构只有4个双精度浮点寄存器，个双精度浮点寄存器，限制了编译器调度的有效性。限制了编译器调度的有效性。u360/91的访存时间和浮点计算时间都很长。的访存时间和浮点计算时间都很长。 （也是（也是Tomasulo算法要解决的问题）算法要解决的问题）1.寄存器换名寄存器换名可以消除可以消除WAR冲突和冲突和WAW冲突。冲突。2021-7-1748n考虑以下代码：考虑以下代码： DIV.DF0，F2，F4 ADD.DF6，F0，F8 S.DF6，0（R1） SUB.DF8，F10，F14 MUL.DF6， F10，F8 输出相关（输出相关（F6）导

39、致导致WAW冲突冲突反相关（反相关（F8）导致导致WAR冲突冲突 2021-7-1749u消除名相关消除名相关n引入两个临时寄存器引入两个临时寄存器S和和Tn把这段代码改写为：把这段代码改写为： DIV.DF0，F2，F4 ADD.DS，F0，F8 S.DS，0（R1） SUB.DT，F10，F14 MUL.DF6，F10，T 两个两个F6都换名为都换名为S 两个两个F8都都换名为换名为T 2021-7-1750基于基于Tomasulo算法的算法的MIPS处理器浮点部件的基本结构处理器浮点部件的基本结构 从从指指令令部部件件来来 浮浮点点寄寄存存器器FP store缓缓冲冲器器 load缓缓冲

40、冲器器 地地址址部部件件 load/store操操作作 浮浮点点操操作作 操操作作数数总总线线 操操作作总总线线 数数据据 1 1 存存储储部部件件 浮浮点点加加法法器器 浮浮点点乘乘法法器器 指指令令队队列列 地地址址 2 3 2 3 4 5 6 公公共共数数据据总总线线（CDB） 1 2 保保留留站站 标标识识 标标识识 2021-7-1751保留站（保留站（reservation station）u每个保留站中保存一条已经流出并等待到本功能部件每个保留站中保存一条已经流出并等待到本功能部件执行的指令（相关信息）。执行的指令（相关信息）。包括：操作码、操作数以及用于检测和解决冲突的信包括：

41、操作码、操作数以及用于检测和解决冲突的信息。息。u在一条指令流出到保留站的时候，如果该指令的源操在一条指令流出到保留站的时候，如果该指令的源操作数已经在寄存器中就绪，则将之取到该保留站中。作数已经在寄存器中就绪，则将之取到该保留站中。u如果操作数还没有计算出来，则在该保留站中记录将如果操作数还没有计算出来，则在该保留站中记录将产生这个操作数的保留站的标识。产生这个操作数的保留站的标识。u浮点加法器有浮点加法器有三三个保留站：个保留站：ADD1，ADD2，ADD3u浮点乘法器有浮点乘法器有两两个保留站：个保留站：MULT1，MULT2 u每个保留站都有一个每个保留站都有一个标识字段标识字段，唯一

42、地标识了该保留，唯一地标识了该保留站。站。 2021-7-1752公共数据总线公共数据总线CDBuCDB是是一条重要的数据通路一条重要的数据通路n所有功能部件的计算结果都是送到所有功能部件的计算结果都是送到CDB上，由它把上，由它把这些结果直接送到（播送到）各个需要该结果的地这些结果直接送到（播送到）各个需要该结果的地方。方。n在具有多个执行部件且采用多流出（即每个时钟周在具有多个执行部件且采用多流出（即每个时钟周期流出多条指令）的流水线中，需要采用多条期流出多条指令）的流水线中，需要采用多条CDB。2021-7-1753load缓冲器和缓冲器和store缓冲器缓冲器u用于存放读用于存放读/写

43、存储器的数据或地址写存储器的数据或地址 uload缓冲器缓冲器的作用：的作用：n存放用于计算有效地址的分量；存放用于计算有效地址的分量；n记录正在进行的记录正在进行的load访存，等待存储器的响应；访存，等待存储器的响应；n保存已经完成了的保存已经完成了的load的结果（即从存储器取来的的结果（即从存储器取来的数据），等待数据），等待CDB传输。传输。ustore缓冲器缓冲器的作用：的作用：n存放用于计算有效地址的分量；存放用于计算有效地址的分量；n保存正在进行的保存正在进行的store访存的目标地址，该访存的目标地址，该store正在正在等待存储数据的到达；等待存储数据的到达；n保存该保存该

44、store的地址和数据，直到存储部件接收。的地址和数据，直到存储部件接收。2021-7-1754u浮点寄存器浮点寄存器FPn共有共有16个浮点寄存器：个浮点寄存器：F0，F2，F4，F30。n它们通过一对总线连接到功能部件，并通过它们通过一对总线连接到功能部件，并通过CDB连接到连接到store缓冲器。缓冲器。u指令队列指令队列n指令部件送来的指令放入指令队列指令部件送来的指令放入指令队列n指令队列中的指令按先进先出的顺序流出指令队列中的指令按先进先出的顺序流出u运算部件运算部件n浮点加法器完成加法和减法操作浮点加法器完成加法和减法操作n浮点乘法器完成乘法和除法操作浮点乘法器完成乘法和除法操作

45、 2021-7-1755u在在Tomasulo算法中，寄存器换名是通过保留站算法中，寄存器换名是通过保留站和流出逻辑来共同完成的。和流出逻辑来共同完成的。n当指令流出时，如果其操作数还没有计算出来，当指令流出时，如果其操作数还没有计算出来，则将该指令中相应的寄存器号换名为将产生这个则将该指令中相应的寄存器号换名为将产生这个操作数的保留站的标识。操作数的保留站的标识。n指令流出到保留站后，其操作数寄存器号或者换指令流出到保留站后，其操作数寄存器号或者换成了数据本身（如果该数据已经就绪），或者换成了数据本身（如果该数据已经就绪），或者换成了保留站的标识，不再与寄存器有关系。成了保留站的标识，不再与

46、寄存器有关系。 2021-7-1756Tomasulo算法的特点算法的特点u冲突检测和指令执行控制是分布的。冲突检测和指令执行控制是分布的。u每个功能部件的保留站中的信息决定了什么时候每个功能部件的保留站中的信息决定了什么时候指令可以在该功能部件开始执行。指令可以在该功能部件开始执行。u计算结果通过计算结果通过CDB直接从产生它的保留站传送到直接从产生它的保留站传送到所有需要它的功能部件，而不用经过寄存器。所有需要它的功能部件，而不用经过寄存器。2021-7-1757指令执行的步骤指令执行的步骤u使用使用Tomasulo算法的流水线需算法的流水线需3段段：u流出流出：从指令队列的头部取一条指令

47、。：从指令队列的头部取一条指令。n如果该指令的操作所要求的保留站有空闲的，就把该如果该指令的操作所要求的保留站有空闲的，就把该指令送到该保留站（设为指令送到该保留站（设为r）。）。n如果其操作数在寄存器中已经就绪，就将这些操作数如果其操作数在寄存器中已经就绪，就将这些操作数送入保留站送入保留站r。n如果其操作数还没有就绪，就把将产生该操作数的保如果其操作数还没有就绪，就把将产生该操作数的保留站的标识送入保留站留站的标识送入保留站r。n一旦被记录的保留站完成计算，它将直接把数据送给一旦被记录的保留站完成计算，它将直接把数据送给保留站保留站r。（寄存器换名和对操作数进行缓冲，消除。（寄存器换名和对

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

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

50、要操作数。或者不需要操作数。nVj，Vk：源操作数的值。：源操作数的值。n对于每一个操作数来说，对于每一个操作数来说，V或或Q字段只有一字段只有一个有效。个有效。n对于对于load来说，来说，Vk字段用于保存偏移量。字段用于保存偏移量。nBusy：为：为“yes”表示本保留站或缓冲单元表示本保留站或缓冲单元“忙忙”。nA：仅：仅load和和store缓冲器有该字段。开始是存放缓冲器有该字段。开始是存放指令中的立即数字段，地址计算后存放有效地址。指令中的立即数字段，地址计算后存放有效地址。 2021-7-1760uQi：寄存器状态表。寄存器状态表。n每个寄存器在该表中有对应的一项，用于存放将每个

51、寄存器在该表中有对应的一项，用于存放将把结果写入该寄存器的保留站的站号。把结果写入该寄存器的保留站的站号。n为为0表示当前没有正在执行的指令要写入该寄存表示当前没有正在执行的指令要写入该寄存器，也即该寄存器中的内容就绪。器，也即该寄存器中的内容就绪。2021-7-1761u设有指令：设有指令： MUL F0,F2,F4 ADD F2,F0,F62021-7-17622021-7-17632021-7-17642021-7-1765例例4.1 对于下述指令序列，给出当第一条指令完成对于下述指令序列，给出当第一条指令完成并写入结果时，并写入结果时，Tomasulo算法所用的各信息表算法所用的各信息

52、表中的内容。中的内容。 L.D F6，34（R2） L.D F2，45（R3） MUL.D F0，F2，F4 SUB.D F8，F2，F6 DIV.D F10，F0，F6 ADD.D F6，F8，F2 2021-7-1766当采用当采用Tomasulo算法时，在上述给定的时刻，保算法时，在上述给定的时刻，保留站、留站、load缓冲器以及寄存器状态表中的内容缓冲器以及寄存器状态表中的内容。 指指 令令 指令状态表指令状态表 流出流出 执行执行 写结果写结果 L.D F6 , 34(R2) L.D F2 , 45(R3) MUL.DF0 , F2 , F4 SUB.D F8 , F6 , F2 D

53、IV.DF10 , F0 , F6 ADD.D F6 , F8 , F2 2021-7-1767Vk Mem34+RegsR2 RegF4 Mem34+RegsR2 名称名称 保留站保留站 Load1Load2Add1Add2Add3Mult1Mult2Busy no yes yes yes no yes yesOp LD SUB ADD MUL DIVVj Qj Load2 Add1 Load2 Mult1Qk Load2A 45+RegsR3 寄存器状态表寄存器状态表 F0 F2 F4 F6 F8 F10 F30 Qi Mult1 Load2 Add2 Add1 Mult2 2021-7-

54、1768Tomasulo算法的主要优点：算法的主要优点：u冲突检测逻辑是分布的冲突检测逻辑是分布的 （通过保留站和（通过保留站和CDB实现）实现）n如果有多条指令已经获得了一个操作数，如果有多条指令已经获得了一个操作数，并同时在等待同一运算结果，那么这个结并同时在等待同一运算结果，那么这个结果一产生，就可以通过果一产生，就可以通过CDB同时播送给所同时播送给所有这些指令，使它们可以同时执行。有这些指令，使它们可以同时执行。n消除了消除了WAW冲突和冲突和WAR冲突导致的停顿冲突导致的停顿n使用保留站进行寄存器换名，并且操作数使用保留站进行寄存器换名，并且操作数一旦就绪就将之放入保留站。一旦就绪

55、就将之放入保留站。 2021-7-17694.4 多指令流出技术多指令流出技术u如果每次只能流出一条指令（单流出），则如果每次只能流出一条指令（单流出），则CPI不可能小于不可能小于1。u要想进一步提高性能，使要想进一步提高性能，使CPI1，就必须采用，就必须采用多流出技术。多流出技术。2021-7-1770单流出和多流出处理机执行指令的时空图单流出和多流出处理机执行指令的时空图 IF 1 2 3 4 5 6 7 时时钟钟周周期期 指指令令 I1 I2 I3 ID EX MEM WBIF ID EX MEM WBIF ID EX MEM WB1 2 3 4 5 6 7 时时钟钟周周期期 指指令

56、令 I1 I2 I3 IF ID EX MEM WBIF IF ID ID EX EX MEM MEM WBWBIF ID EX MEM WBIF ID EX MEM WBIF ID EX MEM WBIF ID EX MEM WBIF ID EX MEM WBIF ID EX MEM WB单单流流出出时时空空图图 多多流流出出时时空空图图 2021-7-1771提高流水并行处理的方法提高流水并行处理的方法u增加流水部件套数增加流水部件套数 超标量超标量u合并多条指令操作码合并多条指令操作码 超长指令字超长指令字u细化流水部件段数细化流水部件段数 超流水超流水2021-7-17724.4.1

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

58、代码的具体情况，依代码的具体情况而定（有上限）。而定（有上限）。u设这个上限为设这个上限为n，就称该处理机为，就称该处理机为n流出。流出。u可以通过编译器进行指令的静态调度，可以通过编译器进行指令的静态调度，也可以基于也可以基于Tomasulo算法进行动态调度，算法进行动态调度，以实现超标量技术。以实现超标量技术。 2021-7-1774理想的理想的RISC机中指令流水的执行情况机中指令流水的执行情况理想的理想的RISC机机取指取指译码译码 执行执行 写回写回0123456T72021-7-1775在超标量机中每个时钟周期可同时启动在超标量机中每个时钟周期可同时启动三条指令的情况三条指令的情况

59、0123456T取指取指译码译码 执行执行 写回写回每拍启动每拍启动3 3条指令条指令要求并行度要求并行度=3=3（b b）超级标量机）超级标量机 配置多个功能部件配置多个功能部件多个译码器，寄存器多个译码器，寄存器端口，总线，能同时端口，总线，能同时执行多个操作。执行多个操作。2021-7-1776单发射与多发射单发射与多发射u发射：发射： 处理机从指令存储单元取得指令的过程处理机从指令存储单元取得指令的过程u单发射：单发射： 处理机在单时钟周期内只能取出一条指令供执行。处理机在单时钟周期内只能取出一条指令供执行。 处理机只有一个处理机只有一个IF 和和 ID部件，但可以有多个运部件，但可以

60、有多个运算部件。算部件。u多发射：多发射： 处理机在单时钟周期内可取出多条指令供执行。处理机在单时钟周期内可取出多条指令供执行。 处理机必须设置多个处理机必须设置多个IF 、ID 、WR等部件。等部件。2021-7-1777超标量机的典型结构超标量机的典型结构主主存存D-cacheD-cache存储器操作部件存储器操作部件ALU1 12 2条指令并行条指令并行取出并同时译码取出并同时译码I-cache2 2指指令令调调度度转移控制部件转移控制部件状态状态记录部件记录部件RF寄存器寄存器堆堆译码器译码器2021-7-1778指令执行部件指令执行部件的功能的功能u 存储器操作部件存储器操作部件：n