第06章 指令级并行-软件方法

1、张晨曦 编著华中科技大学 计算机学院2 0 1 3 年 4 月2 232326.1指令调度与循环展开6.2跨越基本块的静态流水指令调度6.3静态多指令流出: VLIW6.4显式并行指令计算EPIC6.5 开发更多的指令级并行第六章 指令级并行软件方法3 332326.1.1 循环展开调度的基本方法1. 1. 指令调度指令调度 通过改变指令在程序中的位置，将相关指通过改变指令在程序中的位置，将相关指令之间的距离加大到不小于指令执行延迟，将令之间的距离加大到不小于指令执行延迟，将相关指令转化为无关指令。相关指令转化为无关指令。 指令调度是循环展开的技术基础。指令调度是循环展开的技术基础。2. 2.

2、 编译器在完成这种指令调度时，受限于以下两编译器在完成这种指令调度时，受限于以下两 个特性：个特性： 程序固有的指令级并行性程序固有的指令级并行性 流水线功能部件的执行延迟流水线功能部件的执行延迟6.1 指令级并行的概念4 432326.1 指令级并行的概念表表6.2 6.2 假设的流水线延迟假设的流水线延迟产生结果指令产生结果指令使用结果指令使用结果指令延迟时钟周期数延迟时钟周期数浮点计算浮点计算另外的浮点操作另外的浮点操作3 3浮点计算浮点计算浮点数据存操作浮点数据存操作(SD)(SD)2 2浮点数据取操作浮点数据取操作(LD)(LD)浮点计算浮点计算1 1浮点数据取操作浮点数据取操作(L

3、D)(LD)浮点数据存操作浮点数据存操作(SD)(SD)0 0u 分支指令使用上一条指令的结果作为分支条件分支指令使用上一条指令的结果作为分支条件, , 将要等待一拍将要等待一拍u 分支指令有一个节拍的延迟槽分支指令有一个节拍的延迟槽5 53232例例6.16.1 对于下面的源代码，转换成对于下面的源代码，转换成MIPSMIPS汇编语言，汇编语言，在在不进行指令调度不进行指令调度和和进行指令调度进行指令调度两种情况下，两种情况下，分析代码一次循环的执行时间。分析代码一次循环的执行时间。 for (i=1; i=1000; i+)for (i=1; i=1000; i+) xi = xi + s

4、; xi = xi + s;6.1 指令级并行的概念6 63232解：解：(1)(1) 变量分配寄存器变量分配寄存器 整数寄存器整数寄存器R1R1：循环计数器，初值为：循环计数器，初值为=8000?=8000? 中最高端地址元素的地址。中最高端地址元素的地址。 浮点寄存器浮点寄存器F2F2：保存常数：保存常数S S。 假定最低端元素的地址为假定最低端元素的地址为8 8。 (2)(2) MIPSMIPS汇编语言后的程序汇编语言后的程序 Loop: LD F0,0(R1) Loop: LD F0,0(R1) / /* *0(R1)0(R1)即即x x的地址的地址* */ / ADDD F4,F0,

5、F2 ADDD F4,F0,F2 SD SD 0(R1),F4 0(R1),F4 SUBI R1,R1,#8 SUBI R1,R1,#8/ /* *为什么是为什么是8?8?* */ / BNEZ R1,Loop BNEZ R1,Loop6.1 指令级并行的概念7 73232(3)(3) 程序执行的实际时钟程序执行的实际时钟根据根据表表6-26-2中给出的的延迟，实际时钟如下：中给出的的延迟，实际时钟如下： 指令流出时钟指令流出时钟 Loop: LD F0, 0(R1) 1Loop: LD F0, 0(R1) 1 ( (空转空转) ) 2 2 ADDD F4, F0 , F2 3 ADDD F4

6、, F0 , F2 3 ( (空转空转) ) 4 4 ( (空转空转) ) 5 5 SD SD 0(R1), F4 0(R1), F4 6 6 SUBI R1, R1, #8 SUBI R1, R1, #8 7 7 ( (空转空转) ) 8 8 BNEZ R1, Loop 9 BNEZ R1, Loop 9 ( (空转空转) 10) 10每个元素的操作需要每个元素的操作需要1010个时钟周期，其中个时钟周期，其中5 5个个是空转周期。是空转周期。6.1 指令级并行的概念8 83232(4)(4) 指令调度以后，程序的执行情况指令调度以后，程序的执行情况SDSD放在分支指令的分支延迟槽中放在分支

7、指令的分支延迟槽中，BNEZBNEZ放在了空转周期！放在了空转周期！对存储器地址偏移量进行调整对存储器地址偏移量进行调整 指令流出时钟指令流出时钟Loop: LD F0, 0(R1) 1Loop: LD F0, 0(R1) 1 SUBI R1, R1 , #SUBI R1, R1 , #8 8 2 2 ADDD F4, F0 , F2 ADDD F4, F0 , F2 3 3 ( (空转空转) ) 4 4 BNEZ R1, LoopBNEZ R1, Loop 5 5 SD SD 8 8(R1), F4(R1), F4 6 6一个元素的操作时间从一个元素的操作时间从1010个时钟周期减少到个时钟

8、周期减少到6 6个个5 5个周期是有指令执行的，个周期是有指令执行的，1 1个空转周期。个空转周期。6.1 指令级并行的概念9 93232(5)(5) 例子中的问题及解决方案例子中的问题及解决方案只有只有LDLD、ADDDADDD和和SDSD这这3 3条指令是有效操作条指令是有效操作. .占用占用3 3个时钟周期个时钟周期而而SUBISUBI、空转空转和和BENZBENZ这这3 3个时钟周期都是个时钟周期都是附加附加的的循环控制开销循环控制开销。循环展开技术循环展开技术多次复制循环体并相应调整展开后的指令和循环多次复制循环体并相应调整展开后的指令和循环结束条件，增加有效操作时间与控制操作时间的

9、结束条件，增加有效操作时间与控制操作时间的比率。比率。也给编译器进行指令调度带来了更大的空间。也给编译器进行指令调度带来了更大的空间。6.1 指令级并行的概念10103232例例6.2 6.2 体现循环展开技术的特点体现循环展开技术的特点 将将例例6.16.1中的循环展开成中的循环展开成3 3次次得到得到4 4个个循循环体，再对展开后的指令序列在不调度和环体，再对展开后的指令序列在不调度和调度两种情况下，分析代码的性能。调度两种情况下，分析代码的性能。 假定假定R1R1的初值为的初值为3232的倍数，即循环的倍数，即循环次数为次数为4 4的倍数。的倍数。6.1 指令级并行的概念11113232

10、解：解：补偿代码问题补偿代码问题寄存器分配寄存器分配展开后的循环体内不重复使用寄存器。展开后的循环体内不重复使用寄存器。F0F0、F4F4：用于展开后的第：用于展开后的第1 1个循环体个循环体F2F2：保存常数：保存常数F6F6和和F8F8：用于展开后的第用于展开后的第2 2个循环体个循环体F10F10和和F12F12：用于第用于第3 3个循环体个循环体F14F14和和F16F16：用于第用于第4 4个循环体个循环体6.1 指令级并行的概念12123232(1)(1) 展开后没有调度的代码展开后没有调度的代码流出时钟流出时钟Loop:Loop:LD F0,0(R1)LD F0,0(R1) 1

11、1（空转）（空转） 2 2ADDD F4,F0,F2ADDD F4,F0,F2 3 3（空转）（空转） 4 4（空转）（空转） 5 5SD 0(R1),F4SD 0(R1),F4 6 6LD F6,LD F6,-8-8(R1)(R1) 7 7（空转）（空转） 8 8ADDD F8,F6,F2ADDD F8,F6,F2 9 9（空转）（空转） 1010（空转）（空转） 1111SD SD -8-8(R1),F8 12(R1),F8 12LD F10,-16(R1) 13LD F10,-16(R1) 13（空转）（空转） 1414流出时钟流出时钟ADDDADDDF12,F10,F2F12,F10,

12、F2 15 15（空转）（空转） 16 16 （空转）（空转） 1717SDSD-16(R1),F12-16(R1),F12 18 18LDLDF14,-24(R1) 19F14,-24(R1) 19（空转）（空转） 2020ADDDADDDF16,F14,F2F16,F14,F2 21 21（空转）（空转） 2222（空转）（空转） 2323SDSD-24(R1),F16 24-24(R1),F16 24SUBISUBIR1,R1,#R1,R1,#3232 25 25（空转）（空转） 2626BNEZBNEZR1,Loop 27R1,Loop 27（空转）（空转） 28286.1 指令级并行

13、的概念13133232结果分析结果分析: :这个循环每遍共使用了这个循环每遍共使用了2828个时钟周期个时钟周期有有4 4个个循环体，完成循环体，完成4 4个个元素的操作元素的操作平均每个元素使用平均每个元素使用28/4=728/4=7个时钟周期个时钟周期原始循环的每个元素需要原始循环的每个元素需要1010个时钟周期个时钟周期节省的时间节省的时间: :从从减少循环控制减少循环控制的开销中获得的的开销中获得的在整个展开后的循环中，实际指令只有在整个展开后的循环中，实际指令只有1414条，条，其它其它1313个周期都是空转。个周期都是空转。 效率并不高效率并不高6.1 指令级并行的概念141432

14、32(2)(2) 对指令序列进行优化调度对指令序列进行优化调度Loop:Loop:LDLDF0F0,0(R1),0(R1)1 1 LD LDF6F6,-8(R1),-8(R1)2 2 LD LDF10F10,-16(R1),-16(R1) 3 3 LD LDF14F14,-24(R1),-24(R1) 4 4 ADDD ADDDF4,F0,F2F4,F0,F25 5 ADDD ADDDF8,F6,F2F8,F6,F26 6 ADDD ADDDF12,F10,F2F12,F10,F2 7 7 ADDD ADDDF16,F14,F2F16,F14,F2 8 8 SD SD0(R1),F40(R1)

15、,F49 9 SD SD-8(R1),F8-8(R1),F81010 SUBI SUBIR1,R1,#32R1,R1,#32 12 12 SD SD16(R1),F1216(R1),F12 11 11 / /* *16-32=-1616-32=-16* */ / BNEZ BNEZR1,LoopR1,Loop 13 13 SD SD8(R1),F168(R1),F16 14 14 / /* *8-32=-248-32=-24* */ /6.1 指令级并行的概念指令流出时钟指令流出时钟15153232结果分析：结果分析：没有数据相关引起的空转等待没有数据相关引起的空转等待整个循环仅仅使用整个循环

16、仅仅使用了了1414个时钟周期个时钟周期平均每个元素的操作使用平均每个元素的操作使用14/4=3.514/4=3.5个时钟周期个时钟周期循环展开循环展开和和指令调度指令调度可以有效地提高循环级并可以有效地提高循环级并行性。行性。这种循环级并行性的提高实际是通过实现指令级这种循环级并行性的提高实际是通过实现指令级并行来达到的。并行来达到的。寄存器开销增大！寄存器开销增大！可以使用编译器来完成，也可以通过硬件来可以使用编译器来完成，也可以通过硬件来完成。完成。6.1 指令级并行的概念161632324. 4. 循环展开和指令调度时要注意的问题循环展开和指令调度时要注意的问题(1) (1) 保证正确

17、性保证正确性(2) (2) 注意有效性注意有效性(3) (3) 使用不同的寄存器使用不同的寄存器(4) (4) 尽可能减少循环控制中的测试指令和分支指令尽可能减少循环控制中的测试指令和分支指令(5) (5) 注意对存储器数据的相关性分析注意对存储器数据的相关性分析(6) (6) 注意新的相关性注意新的相关性5. 5. 实现循环展开的关键实现循环展开的关键 分析清楚代码中指令的相关性，然后通过分析清楚代码中指令的相关性，然后通过 指令调度来消除相关指令调度来消除相关. .6.1 指令级并行的概念171732326.5.1 相关性开发指令级并行的开发指令级并行的关键关键存在相关的两条指令，不能改变

18、它们的顺序。存在相关的两条指令，不能改变它们的顺序。相关是否导致流水线的空转，还与流水线的相关是否导致流水线的空转，还与流水线的组织与结构有关。组织与结构有关。程序中程序中的相关主要有以下三种的相关主要有以下三种 数据相关数据相关 名相关名相关 控制相关控制相关6.5 开发更多的指令级并行181832321. 1. 数据相关数据相关（Data dependenceData dependence）对于对于指令指令i i和和指令指令j j，如果，如果 (1) (1) 指令指令j j使用使用指令指令i i产生的结果，或者产生的结果，或者 (2) (2) 指令指令j j与与指令指令k k数据相关，数据

19、相关，指令指令k k与与指令指令i i数据相数据相 关，则关，则指令指令j j与与指令指令i i数据相关。数据相关。 数据相关具有传递性。数据相关具有传递性。数据相关是两条指令之间存在一个先写后读相关链。数据相关是两条指令之间存在一个先写后读相关链。相关链贯穿整个程序，是程序的内在特征。相关链贯穿整个程序，是程序的内在特征。这种相关链是导致流水线停顿的原因之一。这种相关链是导致流水线停顿的原因之一。6.5 开发更多的指令级并行19193232指令的相关指令的相关( (依赖依赖) )距离（距离（DistanceDistance） 两条指令之间的指令条数。两条指令之间的指令条数。分析数据相关的主要

20、工作分析数据相关的主要工作: : (1) (1) 确定指令的相关性，找到所有可能产生停确定指令的相关性，找到所有可能产生停 顿的地方。顿的地方。 (2) (2) 确定必须严格遵守的数据的计算顺序。确定必须严格遵守的数据的计算顺序。 (3) (3) 确定指令的最大相关距离，确定程序中可确定指令的最大相关距离，确定程序中可 能的最大并行性。能的最大并行性。6.5 开发更多的指令级并行202032322. 2. 名相关（名相关（Name dependenceName dependence）指令使用的寄存器或存储器称为指令使用的寄存器或存储器称为名名。如果两条指令使用相同的名，但是它们之间并如果两条指

21、令使用相同的名，但是它们之间并没有数据流，则称之为没有数据流，则称之为名相关名相关。指令指令j j与与指令指令i i之间名相关有以下两种：之间名相关有以下两种： (1) (1) 反相关反相关（anti-dependenceanti-dependence） (2) (2) 输出相关输出相关（output dependenceoutput dependence）6.5 开发更多的指令级并行21213232 消除名相关消除名相关名相关的指令之间没有数据交换。名相关的指令之间没有数据交换。如果一条指令中的名改变了，并不影响另外一如果一条指令中的名改变了，并不影响另外一条指令的执行。条指令的执行。通过改

22、变指令中操作数的名来消除名相关，这通过改变指令中操作数的名来消除名相关，这就是就是换名（换名（renamingrenaming）技术）技术。对于寄存器操作数进行换名称为对于寄存器操作数进行换名称为寄存器换名寄存器换名。 (register renaming)(register renaming)可以用编译器静态完成或硬件动态完成。可以用编译器静态完成或硬件动态完成。6.5 开发更多的指令级并行22223232例：例：我们对我们对例例6.26.2编译过程进行分析，来仔细考察编译过程进行分析，来仔细考察 换名的过程。换名的过程。 (1) (1) 首先，仅仅去除首先，仅仅去除4 4遍循环体中的分支指

23、令，遍循环体中的分支指令， 得到以下由得到以下由1717条指令构成的指令序列：条指令构成的指令序列：6.5 开发更多的指令级并行23233232Loop: LD F0, 0(R1)Loop: LD F0, 0(R1) ADDD F4, F0, F2 ADDD F4, F0, F2 SD 0(R1), F4 SD 0(R1), F4 SUBI SUBI R1R1, R1, #8, R1, #8 LD F0, 0( LD F0, 0(R1R1) ) ADDD F4, F0, F2 ADDD F4, F0, F2 SD 0( SD 0(R1R1), F4), F4 SUBI R1, SUBI R1,

24、 R1R1, #8, #8LD LD F0, 0(R1)F0, 0(R1)ADDDADDDF4, F0, F2F4, F0, F2SDSD 0(R1), F4 0(R1), F4SUBISUBIR1, R1, #8R1, R1, #8LDLD F0, 0(R1) F0, 0(R1)ADDDADDDF4, F0, F2F4, F0, F2SDSD 0(R1), F4 0(R1), F4SUBISUBIR1, R1, #8R1, R1, #8BNEZBNEZR1, LoopR1, Loop6.5 开发更多的指令级并行24243232(2) (2) 编译器可以通过对相关链上存储器访问偏移量的编译器可

25、以通过对相关链上存储器访问偏移量的直接调整，将前直接调整，将前3 3条条SUBISUBI指令消除掉，从而得到下面指令消除掉，从而得到下面一个一个1414条指令构成的指令序列：条指令构成的指令序列： 6.5 开发更多的指令级并行25253232Loop: LDLoop: LD F0, 0(R1) F0, 0(R1) ADDD F4, F0, F2 ADDD F4, F0, F2 SD SD 0(R1), F4 0(R1), F4 LD LD F0, -8(R1) F0, -8(R1) ADDD F4, F0, F2 ADDD F4, F0, F2 SD SD -8(R1), F4 -8(R1),

26、 F4 LDLD F0, -16(R1) F0, -16(R1) ADDD F4, F0, F2 ADDD F4, F0, F2 SD SD -16(R1), F4 -16(R1), F4 LD LD F0, -24(R1) F0, -24(R1) ADDD ADDD F4, F0, F2 F4, F0, F2 SD SD -24(R1), F4 -24(R1), F4 SUBI R1, R1, SUBI R1, R1, #32#32 BNEZ R1, Loop BNEZ R1, Loop6.5 开发更多的指令级并行26263232(3)(3)通过寄存器换名，通过寄存器换名，消除名相关。得到消

27、除名相关。得到右边的指令序列：右边的指令序列： Loop:Loop:LDLDF0, 0(R1)F0, 0(R1)ADDDADDDF4, F0, F2F4, F0, F2SDSD0(R1), F40(R1), F4LDLDF6F6, -8(R1), -8(R1)ADDDADDDF8, F6, F2F8, F6, F2SDSD-8(R1), F8-8(R1), F8LDLDF10F10, -16(R1), -16(R1)ADDDADDDF12, F10, F2F12, F10, F2SDSD-16(R1), F12-16(R1), F12LDLDF14F14, -24(R1), -24(R1)AD

28、DDADDDF16, F14, F2F16, F14, F2SDSD-24(R1), F16-24(R1), F16SUBISUBIR1, R1, #32R1, R1, #32BNEZBNEZR1, LoopR1, Loop换名操作需要较大换名操作需要较大的寄存器开销。的寄存器开销。 6.5 开发更多的指令级并行272732323 3控制相关（控制相关（control dependencecontrol dependence） 控制相关控制相关是指由分支指令引起的相关。是指由分支指令引起的相关。 典型的程序结构是典型的程序结构是“if-thenif-then”结构。结构。 看下面一个示例：看下

29、面一个示例： if p1if p1 S1; S1; S; S; if p2 if p2 S2; S2; 6.5 开发更多的指令级并行28283232 处理控制相关的处理控制相关的两个原则两个原则： (1) (1) 与控制相关的指令不能移到分支指令之与控制相关的指令不能移到分支指令之 前，即控制有关的指令不能调度到分支前，即控制有关的指令不能调度到分支 指令控制范围以外；指令控制范围以外； (2) (2) 与控制无关的指令不能移到分支指令之与控制无关的指令不能移到分支指令之 后，即控制无关的指令不能调度到分支后，即控制无关的指令不能调度到分支 指令控制范围以内。指令控制范围以内。6.5 开发更多

30、的指令级并行29293232再考察再考察例例6.26.2： 假设循环展开时，循环控制分支指令没有去除，假设循环展开时，循环控制分支指令没有去除，则指令序列如下：则指令序列如下： 6.5 开发更多的指令级并行30303232Loop: LDLoop: LDF0, 0(R1)F0, 0(R1)ADDDADDDF4, F0, F2F4, F0, F2SDSD0(R1), F40(R1), F4SUBISUBIR1, R1, #8R1, R1, #8BEQZBEQZR1, ExitR1, ExitLDLDF0, 0(R1)F0, 0(R1)ADDDADDDF4, F0, F2F4, F0, F2SDSD0